►Reeks 2 :   Uitgestelde Evaluatie
Reeks 2 :   Uitgestelde Evaluatie
1 Oefening:   my-if
2 Oefening:   Achterwaards-compatibele lazy evaluator
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.

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"))

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.

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)

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

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

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

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

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