Reeks 2 : Uitgestelde Evaluatie

8.9

Reeks 2 : Uitgestelde Evaluatie

Deze oefeningenreeks behandelt de luie evaluator (lazy evaluator) uit hoofdstuk 4.2. Je kan de nodige bestanden voor deze evaluator vinden op de algemene website van het vak onder de sectie “notes”. De oefeningen (en later ook de oplossingen) kan je vinden op de oefeningenwebsite. De luie evaluator start je door het bestand "icp_3_leval.scm" te evalueren in DrRacket.

De luie evaluator verschilt van de meta-circulaire evaluator uit deel 1a. Argumenten voor een procedure-applicatie worden pas geëvalueerd wanneer hun waarde nodig is tijdens het evalueren van de body van deze procedure. De procedure apply van de evaluator neemt daarom niet langer de lijst van waarden waarnaar deze argumenten evalueerden, maar een lijst van “uitgestelde waarden” (thunks). Zulk een “uitgestelde waarde” (thunk) verpakt als het ware een expressie (deze waarvan de evaluatie uitgesteld wordt) samen met een omgeving. Wanneer de evaluator later de eigenlijke waarde van de ingepakte expressie nodig heeft, wordt deze alsnog geëvalueerd in de omgeving waarmee zij verpakt werd (zie force-it en actual-value). Dit gebeurt wanneer een uitgestelde waarde (i) doorgegeven moet worden aan een primitieve procedure (ii) zelf gebruikt wordt als procedure (m.a.w wanneer zij zich in de operator positie van een procedure-applicatie bevindt) (iii) gebruikt wordt als test-expressie van een if.

1 Oefening: my-if

In de luie evaluator hoeven controle-structuren zoals if niet langer als een speciale vorm (special form) geïmplementeerd te worden. De gebruiker van de evaluator kan deze namelijk net zo goed zelf als compound procedure implementeren. Implementeer op de read-eval-print loop van de luie evaluator de compound procedure my-if. Deze procedure mag een beroep doen op de special form cond.

> (define (my-if pred? consequent alternative)
    (cond
      (pred? consequent)
      (else alternative)))
;;; L-Eval value:
ok

Bespreek waarom dit niet mogelijk was op de read-eval-print loop van de meta-circulaire evaluator. Laat je inspireren door volgende expressie:

> (my-if true
(display "ja")
(display "neen"))
ja
;;; L-Eval value:
#<void>

De evaluatie toont enkel "ja" op het scherm onder de luie evaluator. Onder een ijverige evaluator zou er echter "janeen" (of "neeenja") op het scherm geprint zijn omdat alle argumenten van een procedure-applicatie geëvalueerd moeten zijn alvorens aan de body van de procedure (in dit geval my-if) te beginnen.

Bedenk een procedure die je wel kan schrijven aan de hand van de lazy my-if procedure, die je niet zo had kunnen schrijven aan de hand van de if special form. Bespreek ook waarom dit verschil bestaat.

Special forms zijn geen "first class" elementen: je kan ze niet als parameter meegeven, of als waarde teruggeven uit een procedure-aanroep, of in datastructuren steken. Met lazy proceduren kan dit wel, waardoor de volgende interactie mogelijk is, terwijl dit met my-if vervangen door if niet mogelijk was geweest:
; Met deze definitie voor map:
> (define (map f l1 l2 l3)
    (if (or (null? l1) (null? l2) (null? l3))
        '()
        (cons (f (car l1) (car l2) (car l3))
              (map f (cdr l1) (cdr l2) (cdr l3)))))
;;; L-Eval value:
ok
; Werkt dit feilloos:
> (map my-if
       (list (> 1 2)  (> 2 1)  (> 1 1)  (> 2 2))
       (list 'first   'second  'third   'fourth)
       (list 'not-1st 'not-2nd 'not-3rd 'not-4th))
;;; L-Eval value:
(not-1st second not-3rd not-4th)
; Terwijl dit niet mogelijk is:
> (map if
       (list (> 1 2)  (> 2 1)  (> 1 1)  (> 2 2))
       (list 'first   'second  'third   'fourth)
       (list 'not-1st 'not-2nd 'not-3rd 'not-4th))
Unbound variable 'if

2 Oefening: Achterwaards-compatibele lazy evaluator

De lazy evaluator staat toe om programma’s te schrijven die voorheen niet geschreven konden worden zonder expliciet elementen te delayen. Sommige programma’s die in de ’gewone’ evaluator werken, werken echter niet correct in de lazy evaluator. Specifiek zijn imperatieve programma’s met side-effects het slachtoffer van de gewijzigde evaluatiesemantiek.

Om het mogelijk te maken om ’gewone’ Scheme uit te voeren, maar toch gebruik te kunnen maken van de eenvoudigere manier om expressies te delayen, is de volgende middenweg mogelijk: een lazy evaluator die argumenten enkel lazy evalueert als dat expliciet gevraagd wordt in de definitie van de lambda. We kunnen bv. de annotaties lazy en lazy-memo invoeren, zodat de volgende code een functie f definieert die lazy is in argument c, en een functie g die lazy is in argumenten x en y, en voor y automatisch memoizeert:

(define (f a b (lazy c))
body)
(define (g (lazy x) (lazy-memo y))
body)

Schrijf de accessoren waarmee 'lazy en 'lazy-memo argumenten onderscheiden kunnen worden van elkaar, en van ’gewone’ argumenten.

(define (lazy? var-decl)
  (tagged-list? var-decl 'lazy))
(define (memo? var-decl)
  (tagged-list? var-decl 'lazy-memo))
(define tagged-declaration? pair?)
(define (parameter-name var-decl)
  (if (tagged-declaration? var-decl)
      (cadr var-decl)
      var-decl))
(define first-variable car)
(define rest-variables cdr)

Pas force-it aan om het onderscheid te maken tussen 'thunks, 'thunk-memoizables, 'evaluated-thunk, en de rest.

Maak het onderscheid tussen 'thunk, 'thunk-memoizable, en 'evaluated-thunk. Memoize waar nodig.
(define (force-it obj)
  (cond ((thunk? obj)
         ; Evalueren, maar niet thunkify'en:
         (actual-value (thunk-exp obj) (thunk-env obj)))
        ((thunk-memoizable? obj)
         ; Evalueren, en thunkify'en:
         (let ((result (actual-value (thunk-exp obj) (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           (set-car! (cdr obj) result)
           (set-cdr! (cdr obj) '())
           result))
        ((evaluated-thunk? obj)
         ; Was reeds geëvalueerd:
         (thunk-value obj))
        (else
         ; Is nooit een thunk geweest:
         obj)))

Pas delay-it aan. Afhankelijk van of de declaratie van de te-delayen expressie de tag 'lazy of 'lazy-memo heeft, of ongetagd is.

(define (delay-it decl exp env)
  (cond ((not (tagged-declaration? decl))
         ; Geen tag: 'gewoon' applicative-order evaluatie
         (eval exp env))
        ((lazy? decl)
         (list 'thunk exp env))
        ((memo? decl)
         (list 'thunk-memoizable exp env))
        (else (error "Ongeldige tag in declaratie"))))

Pas apply aan, zodat deze gebruik maakt van de nieuwe accessoren, en de gewijzigde signatuur van delay-it.

In apply moet parameter-name gemapt worden over de lijst van parameters van een procedure (vermits sommigen daarvan nu niet meer a, maar bv. (lazy a) zijn). Ook moet aan list-of-delayed-args de procedure-argumenten meegegeven worden, vermits delay-it daar aangeroepen wordt, en nu een referentie naar de declaratie nodig heeft.
(define (apply procedure arguments env)
  (cond ((primitive-procedure? procedure)
         ; ... ongewijzigd ...)
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (let ((params (procedure-parameters procedure)))
            (extend-environment
             ; Namen uit parameter-lijst halen:
             (map parameter-name params)
             ; Parameters (definities) meegeven:
             (list-of-delayed-args params arguments env)
             (procedure-environment procedure)))))
        (else (error "Unknown procedure type -- APPLY" procedure))))

Voer tenslotte nog een kleine wijziging door aan list-of-delayed-args om de gewijzigde functiesignatuur te ondersteunen.

Hier moet tenslotte de declaratie meegegeven worden aan delay-it, en bij de recursieve aanroep door de lijst van declaraties gecdrd worden.
(define (list-of-delayed-args var-decls exps env)
  (if (no-operands? exps)
      '()
      (cons (delay-it (first-variable var-decls)
                      (first-operand exps) env)
            (list-of-delayed-args (rest-variables var-decls)
                                  (rest-operands exps)
                                  env))))

1	Oefening: my-if
2	Oefening: Achterwaards-compatibele lazy evaluator