SCHEME VOORPROEFJE

De bedoeling van dit hoofdstuk is om op een informele, intuïtieve manier een indruk te geven van hoe Scheme programma's ontwikkeld worden.

Afhankelijk van de machine waarop gewerkt wordt en de gebruikte implementatie van Scheme zullen sommige details er anders uitzien dan hier beschreven. Het is daarom altijd aan te raden de handleiding bij het gebruikte systeem te lezen. Kijk hier voor informatie over het in deze cursus gebruikte systeem.

Als het Scheme programma wordt opgestart, kom je terecht in de Lisp Listener. Je kan de listener zien als een soort dialoogsysteem waarmee je kan converseren in Scheme. Wanneer je een getal intikt, of een woord met betekenis zoals pi en daarna de return toets, krijg je als ``antwoord'' het getal of de waarde van het woord.

> 25 
25
> pi 
3.141592654

Het teken > stelt de prompt van de LISP interpreter voor, een signaal van het systeem aan de gebruiker om een Scheme expressie als input te geven. De prompt kan er anders uitzien bij andere systemen.

Net zoals het Nederlands of een andere natuurlijke taal zijn er woorden en zinnen in SCHEME. Een zin is een reeks van woorden tussen twee ronde haakjes. Vanaf nu laten we het intikken van return weg in de voorbeelden.

> (+ 3 4)
7
> (- pi 3)
0.141592654

In Scheme staan de werkwoorden (operatoren) vooraan, en de substantieven (argumenten) volgen het ``werkwoord''. Het is ook mogelijk om ``ingebedde zinnen'' te gebruiken. De meest ingebedde zin wordt eerst verwerkt, en het resultaat van die verwerking wordt gebruikt bij de verwerking van de een niveau minder ingebedde zin. Er is geen beperking aan het aantal mogelijke inbeddingen.

> (+ pi (- 6 3))
6.141592654
> (+ 2 (* 3 1) (- 2 (/ 15 3)))
2

Het gebruik van een goede indentatie kan meervoudig ingebedde Scheme expressies beter leesbaar maken.

> (+ 2
     (* 3 1)
     (- 2
        (/ 15 3)))
2

Scheme is dus gebaseerd op de toepassing van procedures (ook functies genoemd) op argumenten. Een functietoepassing of aanroep levert een waarde op, of een waarde en een neveneffect (neveneffecten zijn bijvoorbeeld het binden van een variabele aan een waarde, het printen van iets op het scherm of in een file). Merk op dat Scheme gebruik maakt van Poolse notatie (prefixnotatie): een funtieaanroep is een lijst van symbolen, waarbij het eerste element van de lijst een functienaam is (operator), en de overige elementen `operands' die verwijzen naar de argumenten van de functieaanroep.

Functiesamenstelling wordt uitgedrukt door een functieaanroep als argument in een andere functieaanroep te gebruiken. De waarde van de eerste functieaanroep wordt dan als argument in de tweede gebruikt (de waarde wordt doorgegeven aan de tweede functie.

> (expt (+ 23 13) 3)   ; Het resultaat van (+ 23 13) wordt `doorgegeven'
46656                  ; als eerste argument aan de functie expt

> (expt (+ 23 13) 3)   ; Het resultaat van (+ 23 13) wordt `doorgegeven'
46656                  ; als eerste argument aan de functie expt

De listener wacht met antwoorden tot de laatste sluithaak van de expressie ingetikt is. Spaties en ``returns'' worden genegeerd tot dat het geval is. Daarnaast wordt ook alles genegeerd wat op dezelfde regel de puntkomma (;) volgt. Dat is dan ook de manier om commentaar aan te brengen in een programma.

> (+ 1 3)   ; Wat de puntkomma volgt op dezelfde regel wordt genegeerd
4
>
;; Dit dus ook

Een LISP programmeeromgeving bestaat uit ten minste twee sub-programma's: naast de listener is er meestal ook een editor; een programma waarin Scheme code kan worden ingetikt. Zo'n editor kent wat Scheme syntaxis en help bijvoorbeeld bij het aanbrengen van een duidelijke indentatie, bij het intikken van het juiste aantal sluithaakjes, en bij de interactie tussen listener en editor. In wat volgt gaan we bij voorbeelden uit van de (onrealistische) veronderstelling dat alle interactie via de LISP listener gebeurt. Lees de handleiding bij het gebruikte systeem voor informatie over interactie tussen editor en listener, en over nuttige editor en listener commando's als save en load.

Een Scheme programma wordt opgebouwd door interactief procedures te definiëren die gebruik maken van primitieve (voorgedefinieerde) procedures, of andere, door de gebruiker gedefinieerde, procedures. Procedures zijn bijv. +, - *, / , maar ook procedures als random.

> (random 10)
2
> (random 10)
5
> (random 2)
0

De procedure random neemt 1 argument, een positief getal, en retourneert een willekeurig getal tussen 0 en dat positief getal (maar niet het getal zelf). Stel dat je zelf een procedure ``kop of munt'' zou wilen definiëren, dan kan je dat door gebruik te maken van de al bestaande procedure random.

> (define (kop-of-munt)
    (if (= 0 (random 2))
        'kop
        'munt))
KOP-OF-MUNT
> (kop-of-munt)
MUNT
> (kop-of-munt)
KOP

Een systematische bespreking van de syntaxis en semantiek van de verschillende voorgedefinieerde procedures in Scheme stellen we uit tot later. Intuïtief kan je bovenstaande definitie als volgt begrijpen: definieer een procedure met naam kop-of-munt, zonder argumenten, ALS een aanroep van random met argument 2 nul oplevert, DAN is het resultaat kop, ANDERS is het resultaat munt.

Voorbeeld: een natuurlijke taal generator

Het volgende simplistische programma (uit Norvig, 1992) produceert expressies in natuurlijke taal. De preciese betekenis van de gebruikte functies zal uiteraard later uitgelegd worden, maar het voorbeeld geeft een eerste indruk van hoe SCHEME programma's opgesteld worden: als verzamelingen van onafhankelijke functies die waarden doorgeven aan andere functies.

Om een zin te produceren, construeren we eerst een NP, en daarna een VP. APPEND is een voorgedefinieerde procedure die twee of meer lijsten ``aan elkaar plakt''.

(define (S) (append (NP) (VP)))  

Op de zelfde manier definiëren we procedures voor NP en VP.

(define (NP) (append (DET) (N)))   

(define (VP) (append (V) (NP)))

Nu zitten we met een probleem: DET, N, en V zijn lexicale categorieën, we hebben dus een woordenboek nodig om ze te produceren. We gaan er hier van uit dat we een procedure schrijven die gegeven een lijst voorbeelden van een lexicale categorie, daar 1 willekeurig uit selecteert. Voor die willekeurige selectie gebruiken we natuurlijk de al bekende procedure random .

(define (DET) (een-van '(een)))

(define (V) (een-van '(roept eet ziet))) 

(define (N) (een-van '(jongen meisje banaan hond)))

Tenslotte de definitie van een-van: definieer een procedure een-van die als argument een lijst neemt. De procedure retourneert een willekeurig element uit die lijst door (i) de procedure random uit te voeren met als argument de lengte van de input lijst, wat een getal tussen 0 en de lengte van de lijst oplevert, en (ii) het element van de inputlijst te nemen dat correspondeert met die positie. De procedures length en list-ref zijn voorgedefinieerd in Scheme.

(define (een-van lijst)
  (list 
    (list-ref lijst 
              (random (length lijst)))))

Enkele voorbeelden:

> (S)
(EEN JONGEN ROEPT EEN MEISJE)
> (VP)
(ZIET EEN JONGEN)
> (N)
(BANAAN)
> (NP)
(EEN HOND)

;;; De volgorde van funtieaanroepen ziet er zo uit:

> (s)
--> S
----> NP                             S roept NP op
------> DET                          NP roept DET op
<------ DET (een)                    DET retourneert (een)
------> N                            NP roept N op
<------ N (banaan)                   N retourneert (banaan)
<---- NP (een banaan)                NP retourneert (een banaan)
----> VP                             S roept VP op
------> V                            VP roept V op
<------ V (roept)                    etc.
------> NP
--------> DET
<-------- DET (een)
--------> N
<-------- N (meisje)
<------ NP (een meisje)
<---- VP (roept een meisje)
<-- S (een banaan roept een meisje)

(een banaan roept een meisje)

> (trace s np vp det v n)
> (s)
  ... trace ...
> (untrace)