PROGRAMMASTRUCTUUR

Speciale en lexicale variabelen

De parameters in een functiedefinitie (lambda-expressie) zijn een voorbeeld van lexicale variabelen in LISP. Ze hebben een lexicale scope. D.w.z. dat ze alleen gebonden zijn in een beperkte lexicale omgeving (in dit geval de body van de functiedefinitie). Daarbuiten is de parameter niet gebonden. Vanop geen enkel andere plaats in het programma kan je er naar verwijzen. Dat impliceert dat parameternamen gelijk kunnen zijn aan al bestaande variabele namen zonder dat er verwarring optreedt.

> (define lijst '(appels en peren)) 
; lijst gebonden aan (appels en peren)
(APPELS EN PEREN)
> (define foo 
      (lambda (lijst)
        (first lijst)))
FOO
> (foo '(1 2 3)) ; lijst gebonden aan (1 2 3) tijdens evaluatie.
1
> lijst          
(APPELS EN PEREN) ; lijst nog steeds gebonden aan (APPELS EN PEREN)

Er zijn ook variabelen die een onbepaalde of globale scope hebben (je kan er vanop om het even welke plaats in het programma naar verwijzen (speciale variabelen). De variabele lijst, gebonden aan de lijst (appels en peren) in het vorige voorbeeld is zo'n speciale variabele. Het is een goede programmeerstijl om speciale variabelen in je programma's steeds aan te duiden met asterisken. M.a.w. gebruik *lijst* in plaats van lijst.

> (define *klinker-lijst*
     '(a e i o u y))

LET en LET*

LET en LET* zijn special forms die symbolen binden aan waarden of procedures op een lexicale manier (locale variabelen). De syntaxis van de drie special forms is dezelfde: (LET ((variabelenaam expressie)*) expressie+). Het keyword LET wordt gevolgd door een variabelenlijst, gevolgd door een body gevormd door 1 of meer expressies die geëvalueerd worden met de variabelen lexicaal gebonden binnen de body, maar niet daarbuiten. De variabelenlijst bestaat uit een aantal sublijsten met als eerste element telkens de naam van de lokale variabele, en als tweede element een expressie die evalueert naar de initiële waarde van de variabele. Bij LET worden de initialiseringen berekend alvorens de variabelen worden gebonden; bij LET* gebeurt initialisering en binding sequentieel zodat initialiseringen van de volgende variabelen gebruik kunnen maken van waarden van eerdere variabelen.

> (define *lijst* '(het leven is hard))
(HET LEVEN IS HARD)
> (let ((eerste-twee (list (car *lijst*)(cadr *lijst*)))
        (lengte (length *lijst*)))
    (list eerste-twee lengte))
((HET LEVEN) 4)
> eerste-twee
>>Error: The symbol EERSTE-TWEE has no value
Een LET-expressie wordt vaak gebruikt om naast de parameters nog meer lexicale variabelen te binden binnen een functiedefinitie.
> (define afkorting 
    (lambda (lijst)
      (let ((eerste-twee (list (first lijst)(second lijst)))
            (lengte (length lijst)))
        (list eerste-twee lengte))))
AFKORTING

> (afkorting '(het gieren van de herfststorm))
((HET GIEREN) 5)

Merk op dat in de LET-expressie gebruik kan gemaakt worden van de parameterlijst (de let-expressie behoort immers tot de body van de functiedefinitie. Andersom kan in de body van de lambda (buiten de body van de let) geen gebruik worden gemaakt van de lexicale variabelen gedefinieerd door de LET-expressie.

> (define afkorting 
    (lambda (lijst)
      (let ((eerste-twee (list (car lijst)(cadr lijst)))
            (lengte (length lijst)))
         lengte)
      (list eerste-twee lengte)))
AFKORTING

> (afkorting '(het gieren van de herfststorm))
ERROR: unbound variable:  eerste-twee

Zoals gezegd kan in een LET-expressie de expressie die de initiële waarde van één van de variabelen beschrijft geen gebruik maken van de LET-variabelen die daarvoor al werden geïnitialiseerd.

> (let ((x 1)
        (y (+ x 1)))
   (+ x y))
>>Error: The symbol X has no value ; (Bedoeld wordt de x in (+ x 1))

Omwille van deze reden wordt LET wel eens parallel genoemd (het lijkt alsof alle variabelen tegelijk worden gebonden). Met LET* kan een sequentiële variabelebinding veroorzaakt worden, waarbij expressies om variabelen te initialiseren wel gebruik kunnen maken van de waarde van eerder gedefinieerde variabelen.

> (let* ((x 1)
         (y (+ 1 x)))
    (+ x y))
3

Als een variabele of parameter, lexicaal of globaal, eenmaal gedefinieerd is, kan zijn waarde worden gewijzigd met (SET! symbool expressie). Deze special form neemt twee argumenten: een symbool waaraan de variabele waarde gebonden is, en een expressie die wordt geëvalueerd tot de nieuwe waarde van de variabele.

> (define foo 12)
12
> (+ 1 foo)
13
> foo
12
> (set!  foo (+ 1 foo))
13
>
foo
13

Blokstructuur

Een Scheme programma bestaat uit een verzameling functiedefinities. Functiedefinities hebben een impliciete blokstructuur. Dit betekent dat bij een reeks expressies in een LET, LAMBDA, en op andere plaatsen, deze expressie na elkaar geëvalueerd worden. Er is ook een primitief, (BEGIN expressie+) die een expliciete blokstructuur mogelijk maakt, wat bijvoorbeeld nuttig is wanneer meer dan 1 expressie moet worden uitgevoerd op een argumentplaats waar slechts 1 expressie voorzien is door de syntaxis van de operator.

> (define x 23)

> (set! x (begin 
             (define y 13) 
             (+ x y)))
36

Functionele argumenten

Een interessante eigenschap van SCHEME is dat procedures eerste klasse datatypes zijn. Dit betekent dat procedures net zoals andere datatypes zoals strings, lijsten en symbolen, gecreëerd, gemanipuleerd en gebruikt kunnen worden, in tegenstelling tot de meeste programmeertalen waar procedures een speciale, beperkte, rol spelen.

De meest opvallende uiting hiervan is dat procedures zonder restricties als argumenten van andere procedures kunnen worden gebruikt. Er zijn een aantal voorgedefinieerde functies die een functie als argument nemen.

> (apply + '(1 2 3))                          ; = (+ 1 2 3)
6
> (apply string-append '("aap" "noot" "mies"))
"aapnootmies"
> (apply cons '(1 2))                         ; = (cons 1 2)
(1 . 2)
> (map + '(1 2 3) '(4 5 6)) ; = (list (+ 1 4)(+ 2 5)(+ 3 6))
(5 7 9)
> (map string-append '("aap" "noot" "mies") '("mies" "noot" "aap"))
("aapmies" "nootnoot" "miesaap")
> (apply + (map max '(1 2 3 4 5 6) '(6 5 4 3 2 1)))
30
> (let ((v (make-vector 5)))
    (for-each (lambda (i)
               (vector-set! v i (+ i i)))
              '(0 1 2 3 4))
    v)  
#(0 2 4 6 8)

Flexibele argumenten in LAMBDA-expressies

Tenslotte zijn er nog twee varianten van de syntaxis van LAMBDA die het mogelijk maken te werken met argumenten verzameld in een lijst. Dat is vooral nuttig wanneer we niet kunnen voorzien hoeveel argumenten er zullen meegegeven worden:

(LAMBDA parameternaam expressie+)

(LAMBDA (parameternaam* . parameternaam) expressie+)

> (define foo
    (lambda x x))
FOO
> (foo 1 'b 3 'd)
(1 b 3 d)

> (define foo
    (lambda (x y . z)
      (list x y z)))
FOO

> (foo 1 2 3 4 5)
(1 2 (3 4 5))

Iteratie

De definitie van de SCHEME standaard schrijft voor dat staartrecursie even efficiënt als iteratie geïmplementeerd moet worden. Dat betekent dat iteratie in principe overbodig is, en alle iteratieve problemen via recursie kunnen worden beschreven zonder efficiëntieverlies. Toch zijn er enkele special forms die toelaten iteratieve procedures te definiëren.

Voor iteratie in Scheme kan

(DO ((var-naam init-expr update-expr)*) (test-expr expr*) expr* )

worden gebruikt. De special form DO heeft als eerste argument een lijst met ingebedde lijsten; één voor elke lokale variabele. Een variabele lijst bestaat uit minstens twee en eventueel drie elementen: de naam van de variabele, de initiële waarde, en optioneel de manier waarop de waarde bij elke iteratie moet worden aangepast. Het tweede argument is een lijst met als eerste element een test die bepaalt wanneer de iteratie stopt, en als volgende elementen 0 of meer expressies die uitgevoerd worden wanneer de test niet-#f oplevert. De waarde van de laatst uitgevoerde expressie (of het resultaat van de test wanneer er geen expressies zijn) is meteen ook de waarde van de hele DO-expressie. Tenslotte heeft de DO-expressie nog 0 of meer expressies die de body van de DO-expressie uitmaken, en die bij elke iteratie worden uitgevoerd. De volgende expressie is een iteratieve definitie van length.

> (define iterative-length
    (lambda (lis)
      (do ((lst lis (cdr lst))            ; variabele naam + initiele
                                          ; waarde + update
           (counter 0 (+ 1 counter)))
          ((null? lst) counter))))        ; test + resultaat
                                          ; geen `body'

> (iterative-length  '(het leven is hard))
4

; Met body en zonder `update'

> (define iterative-length
    (lambda (lis)
      (do ((lst lis (cdr lst))
           (counter 0))
          ((null? lst) counter)
        (set! counter (+ counter 1)))))

Walter Daelemans <Walter.Daelemans@kub.nl>
Last modified: Tue Mar 18 14:46:58 1997