Hoofdstuk 3 Scheme

3.1 Algemene introductie in Scheme

We gaan in dit hoofdstuk met hoge snelheid door de basis van Scheme heen. Verder uitdiepen van allerlei constructies doen we in de volgende hoofdstukken aan de hand van voorbeelden en oefeningen.

Wil je meer weten over Scheme, dan zijn hier een paar goede online bronnen en boeken:

Er is ook een uitstekende serie video-lessen: Computer Science 61A

3.2 Syntax

Zoals gezegd heeft Scheme weinig syntax. Syntax is zoiets als de grammatica van de programmeertaal. Zoek het woord maar eens op Wikipedia.

De belangrijkste constructies en elementen zijn:

Het belangrijkste om te ontdekken wanneer je met Scheme gaat werken is welke rol een element op een bepaald moment vervult. De plaats waar iets in een constructie staat is van cruciaal belang: twee identieke woorden kunnen in een andere context iets heel anders betekenen. Daar komen we zo op terug.

3.3 Vaak gebruikte functies

De uitleg over wat functies zijn en hoe je ze zelf kunt maken staat een stuk verderop in deze pagina. Het volgende rijtje functies is handig om altijd bij de hand te hebben, daarom staat het op deze plek.

cons lijkt op append maar het eerste element wordt integraal in de nieuwe lijst geplaatst. Als het eerste element een lijst is dan krijg je dus een lijst binnen een lijst. Zie ook het hoofdstuk over lijsten.

first en rest zijn niet in alle dialecten van Scheme beschikbaar. De oorspronkelijke namen zijn car en cdr. De oorsprong daarvan ligt bij een Lisp versie op de IBM 704, waarbij car stond voor "Contents of Address part of Register" en cdr voor "Contents of Decrement part of Register".

car en cdr werken in alle Scheme versies en zijn in uitzonderlijke gevallen veelzijdiger dan first en rest. (Bron: Structure and Interpretation of Computer Programs 2nd Edition, page 85)

first en rest werken alleen met lijsten, terwijl car en cdr ook met pairs kunnen werken.

Bovendien zijn er handige functies als cadr, caddr, cddr, cdddr etc... Zoek die maar eens op.

3.4 Uitprobeersels

Zonder uitleg. Probeer maar uit (vandaar de titel), kijk wat er gebeurt en of je er enige logica in kunt ontdekken.

a

x

1

42

'a

'melodie

"melodie"

2+3

+

(+)

(+ 2)

(2 +)

(25 + 19)

(+ 25 19)

3.5 Haakjes, haakjes en nog meer haakjes

Je zag dat (+ 2) wel mag maar (2 +) niet. Kennelijk maakt het uit op welke plaats binnen de haakjes de dingen staan. Dit zijn de regels:

We kunnen nu wat eenvoudige sommen maken:

(+ 8 22)

(* 4 5)

(* (+ 7 3) 10)

Schrijf zelf uit hoe je in Scheme deze som uitrekent: 7 keer 6 min 2 en het resultaat daarvan gedeeld door 4

Haakjes komen altijd voor in paren. Een openingshaakje dat niet wordt afgesloten of een sluithaakje zonder openingshaakje levert een foutmelding op bij het uitvoeren van je programma.

XKCD unmatched parenthesis

3.6 Symbolen, strings en identifiers

Dat is lastig uit te leggen. Misschien helpt het als we het zo bekijken:

Het symbool 'cis kunnen we gebruiken als een symbolische weergave van de noot cis, ofwel de verhoging van c. Voor Scheme heeft cis geen betekenis maar voor ons wel. Zo'n symbool stelt ons in staat om een abstractie van de werkelijkheid te maken. We kunnen ook symbolen maken als 'bes en 'do 're 'mi 'g-sleutel, 'dorisch en 'phrygisch. Ook deze symbolen hebben voor ons een bepaalde betekenis maar voor Scheme zijn het gewoon letterlijke namen.

De string "cis" is een woord, of eigenlijk een stuk tekst. We kunnen ook langere strings maken zoals "De noot cis is een verhoging van de noot c". Zulke strings zijn bijvoorbeeld handig om vanuit je programma mededelingen te doen aan de gebruiker van het programma.

Wat is dan het verschil tussen een symbool en een string? Een symbol kun je niet aan de gebruiker laten zien. Bovendien kun je geen symbol maken dat uit meerdere woorden bestaat: 'De noot cis is....

Een string is samengesteld uit letters en die kun je met allerlei functies bewerken. Bij symbols kan dat niet: een symbol wordt niet gezien als een rijtje letters. De naam van een symbol is niet te splitsen.

Identifiers verdienen een aparte sectie.

3.7 Identifiers

Een identifier is in veel gevallen wat in andere programmeertalen een variabele genoemd wordt. Het is dan een soort label dat je ergens op plakt om het later terug te kunnen vinden.

Neem bijvoorbeeld de expressie '(do re mi fa)

Dit definieert een lijst van vier elementen. Maar wat kun je hier nou mee? Vrij weinig. Nadat je deze lijst gemaakt hebt heb je geen mogelijkheid om hem later nog eens op te roepen.

(define tetrachord '(do re mi fa))

Op deze manier heb je het lijstje een naam gegeven. Je kunt de lijst nu steeds als je hem nodig hebt weer oproepen door de naam te geven:

tetrachord

Nu kun je deze identifier ook weer in andere expressies gebruiken. Neem als voorbeeld de functies first en rest. Daarmee kun je het eerste element van een lijst opvragen, of de lijst met alle elementen behalve het eerste element:

(first tetrachord)

(rest tetrachord)

Het effect is in dit geval hetzelfde als (first '(do re mi fa)) en (rest '(do re mi fa)) maar het is veel flexibeler geworden.

Met define kun je dus labels plakken op constructies die je later nog eens wilt gebruiken.

Je kunt ook bestaande identifiers een andere naam geven:

(define hexachord '(T T S T T)) maakt een identifier 'hexachord'

(define hc hexachord) maakt een identifier 'hc' die wijst naar 'hexachord'

(first hc)

(rest hc)

(first (rest hc))

Nog een paar voorbeelden:

(define b 4)

(define cis 61)

(define toonsoort 'c-major)

Nu kun je aan Racket vragen wat de 'inhoud' van deze identifiers is, dus waar ze naar verwijzen, gewoon met de naam van de identifier:

b
cis
toonsoort

3.8 Expressies

Expressies geven relaties aan tussen elementen. Je kunt bijvoorbeeld twee getallen met elkaar vergelijken en uitspraken doen of ze gelijk zijn of dat het ene getal groter is dan het andere. Je kunt ook tot uitdrukking brengen of iets waar is of niet waar.

(> 5 4) is 5 groter dan 4?

(> 4 5) is 4 groter dan 5?

(= 5 4) is 5 gelijk aan 4?

(>= 5 4) is 5 groter dan of gelijk aan 4?

(and (< x 10) (> x 2)) is x kleiner dan tien EN groter dan 2? (Ofwel: ligt x tussen 2 en 10?)

(eq? noot 'cis) is de noot een 'cis?

3.9 Beslissingen

De meeste programma's die je schrijft worden niet altijd in één keer op precies dezelfde manier van boven naar beneden doorlopen. Op die manier zou je nooit kunnen reageren op iets dat een gebruiker doet of iets dat op een bepaald tijdstip moet gebeuren, om maar eens wat te noemen. Er zullen dus beslissingen genomen moeten worden. Scheme kent enkele varianten waarvan we if en when hier bespreken.

if en when gebruik je wanneer je op basis van een voorwaarde iets wilt uitvoeren. Het verschil tussen deze twee is dat je bij de if een alternatief moet geven voor wanneer niet aan de voorwaarde voldaan wordt en bij de when kan (en hoeft) dat niet.

Algemene vorm:

(if (condition) (then) (else))

(when (condition) (then))

Hierbij wordt het 'then' deel uitgevoerd als de condition waar is, of true, wat in Scheme wordt aangegeven met #t. Het 'else' deel wordt uitgevoerd als de condition onwaar is, of false, wat in Scheme wordt aangegeven met #f.

Voorbeelden:

(if (> input 0) (verwerk input) (probeer-opnieuw))

(when (equal? interval 'T) (display "Tonos"))

3.9.1 Diverse condities in een keer beoordelen

Kijk eens naar de volgende code:

(when (< fase 0.2) (attack 3))
(when (< fase 0.4) (sustain 20))
(when (< fase 0.6) (decay 5))
(when (< fase 0.8) (release 7))
 
 
(if (< fase 0.2) (attack 3)
  (if (< fase 0.4) (sustain 20)
    (if (< fase 0.6) (decay 5)
      (if (< fase 0.8) (release 7) 0))))

Er wordt telkens een vergelijking gedaan. Als de vergelijking waar is dan wordt de functie erna uitgevoerd en anders ga ja naar de 'else' van de if, waar dan weer een volgende if staat.

Dit wordt al snel onoverzichtelijk. Een constructie die beter geschikt is voor meerdere vergelijkingen is cond. Het voorbeeld van zojuist zou je met cond zo opschrijven:

(cond ((< fase 0.2) (attack 3))
      ((< fase 0.4) (sustain 20))
      ((< fase 0.6) (decay 5))
      ((< fase 0.8) (release 7))
      (else 0))

De laatste regel met else is optioneel.

3.10 Functies, procedures en data

Bij de CSD lessen noemen we alle doe-dingen functies en alle passieve elementen zijn data. Als je in documentatie over Scheme de term procedure tegenkomt dan mag je daar ook functie lezen. Als je hier meer over wilt weten kun je de rest van deze paragraaf doorlezen.

In Scheme zijn functies en data gelijkwaardig. Aan de hand van de plaats binnen een constructie wordt bepaald of een element een functie of data is: in het algemeen is het eerste element in een niet-gequote lijst een functie en de andere elementen zijn data waar die functie iets mee doet.

In theorie is een functie iets anders dan een procedure. In veel gevallen worden deze benamingen echter door elkaar gebruikt. Het verschil is enigszins academisch: Een functie geeft een resultaat terug en een procedure voert opdrachten uit. In pure functionele talen is eigenlijk alles een functie. Strikt genomen hebben die geen procedures.

In de praktijk zal vaak blijken dat een functie behalve een resultaat berekenen ook nog wel wat dingen uitvoert. Het onderscheid tussen functie en procedure wordt dan wel erg klein. En als een procedure dan ook nog eens in een aantal gevallen een resultaat kan teruggeven wordt het helemaal verwarrend.

3.11 Functies gebruiken

In een gewone lijst (dus zonder quote) wordt het eerste element als functie gebruikt. Een functie kan een taak uitvoeren en is daarmee het actieve element van de lijst. Eventuele andere elementen zijn passieve elementen. Die doen uit zichzelf niets, maar de functie kan ze wel gebruiken. Voorbeeld:

(teken-cirkel straal middelpunt)

Hier is teken-cirkel het actieve element: de functie die een cirkel kan tekenen. Deze functie heeft informatie nodig om te weten hoe groot die cirkel moet zijn en waar op het tekenvel het ding terecht moet komen. Dat zijn de elementen straal en middelpunt.

3.12 Zelf functies maken

Het plakken van labels met 'define' is niet beperkt tot passieve constructies. Je kunt er ook functies mee maken.

De meest eenvoudige vorm van een functie in Scheme is als volgt:

(define (hoi) (display "Hallo"))

Hierbij is 'hoi' de naam van de functie en wanneer je de functie uitvoert zal deze Hallo op het scherm laten zien. Dat is namelijk wat de functie display doet: teksten laten zien.

Uit zichzelf doet de functie 'hoi' niets. Je zult hem moeten activeren. Dat noemen we in het Nederlands 'aanroepen' en in het Engels 'call'. Het leuke is dat je de functie maar één keer hoeft te maken en hem daarna zo vaak kunt aanroepen als je maar wilt:

(hoi)
(hoi)
(hoi)

NB: Merk op dat er haakjes om 'hoi' heen staan. Als je het zo zou opschrijven:

(define hoi (display "Hallo"))

dan wordt 'hoi' niet als functie gemaakt maar gaat hij het resultaat van (display "Hallo") bevatten, op een manier die we al kennen:

(define hoi (+ 2 3))

Op zich niet fout, maar in dit geval niet wat je wilt.

3.12.1 Een functie met een parameter

De functie die het kwadraat van een getal uitrekent door het met zichzelf te vermenigvuldigen maak je als volgt:

(define (kwadraat x) (* x x))

Nogmaals: Merk op dat er haakjes om 'kwadraat x' heen staan waarmee je aangeeft dat 'kwadraat' een functie is en dat x de (in dit geval enige) parameter is.

En zo kun je je nieuwe functie gebruiken:

(kwadraat 4)
(kwadraat 5)
(kwadraat 10)

Een groot verschil tussen de functie 'hoi' en de functie 'kwadraat' is dat 'hoi' geen resultaat teruggeeft en 'kwadraat' wel. Met het resultaat van 'kwadraat' kun je verder werken, terwijl 'hoi' na zijn werk gedaan te hebben geen nut meer heeft.

Dit kan wel: (+ (kwadraat 5) (kwadraat 4))

en dit niet: (+ (hoi) (hoi))

Functies geven niet alleen getallen als resultaat. We zullen later zien dat ze allerlei dingen kunnen teruggeven zoals lijsten en zelfs functies! Wanneer functies als resultaat een functie kunnen hebben kunnen we met recht spreken van een functionele programmeertaal.

3.12.2 Een functie met meer parameters

Vaak wil je meer dan één parameter aan een functie geven. Neem bijvoorbeeld het uitrekenen van het aantal PCM-samples die afgespeeld worden in een stukje muziek van 10 seconden. Daarvoor moet je niet alleen de tijdsduur (10 seconden) opgeven maar ook de samplerate. Het product van die twee levert het aantal samples.

(define (bereken-aantal-samples tijdsduur samplerate)
  (* tijdsduur samplerate))

Deze functie kun je als volgt aanroepen:

(bereken-aantal-samples 10 48000)

Het getal 10 wordt ingevuld voor de tijdsduur en het getal 48000 voor de samplerate. Dit gaat van links naar rechts. Je kunt op deze manier niet aangeven of het getal 48000 bedoeld is voor de tijdsduur of de samplerate.

3.12.3 Een functie met optionele parameters

Soms is het handig om als je niet verplicht bent om alle parameters te specificeren, maar aan de functie over te laten om ze een standaardwaarde te geven. Dat geef je als volgt aan:

(define (bereken-aantal-samples tijdsduur (samplerate 48000))
  (* tijdsduur samplerate))

Voor de leesbaarheid mag je de ronde haakjes ook vervangen door [ en ] zodat het er zo uit gaat zien:

(define (bereken-aantal-samples tijdsduur [samplerate 48000])
  (* tijdsduur samplerate))

Je kunt deze functie aanroepen met één of twee getallen:

(bereken-aantal-samples 10)

(bereken-aantal-samples 10 44100)

3.13 Lijsten

Een lijst in Scheme is een set haakjes met een aantal items ertussen. Hier zijn een paar voorbeelden:

(+ 200 25) een expressie

'() een lege lijst

'(c d e f g a b) een lijst met notennamen

(speel-melodie '(d d g d c)) een lijst met twee elementen waarvan het tweede element een lijst notennamen is

(define melodie '(c d e f g a b)) een lijst een naam geven

(speel-melodie melodie) verder werken met de lijst aan de hand van zijn naam

Korte conclusie: in Scheme is bijna alles een lijst of komt voor in een lijst.

3.13.1 Alles in Scheme draait om lijsten

Omdat lijsten binnen Scheme zo belangrijk zijn, bestaan er al veel functies die je kunt gebruiken om iets met lijsten te doen.

Wat zou je zoal met lijsten willen doen:

Hier volgen wat handige functies met een korte beschrijving. Realiseer je dat deze functies de lijst(en) die je erin stopt niet veranderen. Het resultaat is altijd een nieuwe lijst, een element of een andere constructie en de oorspronkelijke gegevens blijven intact. Dit noemen we 'immutable'.

3.13.1.1 Creatie

list maakt een nieuwe lijst die is samengesteld uit de elementen die je opgeeft.

append maakt een nieuwe lijst door lijsten die je opgeeft aan elkaar te plakken.

cons maakt een nieuwe lijst door een lijst uit te breiden met één element aan het begin.

Helaas kun je dit niet omdraaien om een element aan het einde van een lijst te plakken want dan krijg je zoiets:

********************************************************************
Vraag: hoe kun je dan wel een element achter aan een lijst plakken?
********************************************************************

3.13.1.2 Uitbreiden of inkorten

first geeft het eerste element uit een lijst, als de lijst niet leeg is

rest geeft de lijst zonder het eerste element, als de lijst niet leeg is. Als de lijst 1 element bevat krijg je een lege lijst terug.

3.13.1.3 Hoeveel elementen bevat de lijst?

length geeft de lengte van de lijst

3.13.1.4 Elementen zoeken of aanwijzen

member zoekt een element in een lijst op en als het gevonden wordt dan krijg je de rest van de lijst terug, beginnend bij dat element. Om precies te zijn: beginnend bij de eerste vindplaats van het element. Als het element meerdere keren in de lijst voorkomt zal het dus in het resultaat ook weer voorkomen.

take geeft een lijst die een deel van de oorspronkelijke lijst bevat, beginnend bij het eerste element. Je kunt aangeven hoeveel elementen je wilt.

list-tail geeft net als take een lijst die een deel van de oorspronkelijke lijst bevat, maar nu gerekend vanaf een positie die je zelf kunt aangeven tot en met het einde van de lijst. Let op: die positie begint te tellen bij 0, dus het tweede element heeft positie 1.

Met first krijg je het eerste element uit een lijst. Zo zijn er ook second voor het tweede element, third voor het derde enzovoort tot en met ninth voor het negende element. First zul je vaak gebruiken, misschien second en third ook nog wel maar de rest is vrij nutteloos. Als je het vierde element nodig hebt kun je beter list-ref gebruiken. De volgende voorbeelden leveren hetzelfde resultaat op:

`(fourth '(a b c d e f))`
 
`(list-ref '(a b c d e f) 3)` ; index 3 wijst naar het vierde element!
 
`(first (rest (rest (rest '(a b c d e f)))))`

3.13.1.5 De volgorde van elementen veranderen

reverse draait de volgorde van een lijst om

shuffle geeft de lijst in een willekeurige volgorde terug. Het aantal elementen blijft hetzelfde

In de Racket-documentatie staan nog veel meer functies, maar de meeste heb je nog niet nodig of kun je zelf maken door de bovenstaande op een slimme manier te combineren.

3.14 Lijsten binnen lijsten

Je hebt hier al voorbeelden van gezien: een lijst kan ook weer een of meer lijsten bevatten en die kunnen op hun beurt ook weer lijsten bevatten. Dit kun je grafisch als volgt weergeven:

3.15 Grote en kleine letters

Scheme is, net als veel andere programmeertalen case sensitive, wat betekent dat hoOfDLetTers En klEIne leTTers als verschillend gezien worden.

3.16 Foutmeldingen in Racket

3.16.1 Verkeerd type van argumenten -> Contract violation

Strings of symbolen kun je niet bij elkaar optellen, getallen kun je niet met string-append aan elkaar plakken, uit een lege lijst kun je geen elementen lezen. Dat zijn een paar voorbeelden die een contract violation opleveren.

(+ 'a 'b)
+: contract violation
  expected: number?
  given: 'a
 
(string-append 12 34)
string-append: contract violation
  expected: string?
  given: 12
 
(car '())
car: contract violation
  expected: pair?
  given: '()

3.16.2 Verkeerd aantal argumenten -> Arity mismatch

Een Scheme functie verwacht in de meeste gevallen een vooraf vastgesteld aantal argumenten. Als je er teveel of te weinig geeft krijg je een arity mismatch.

Voorbeeld: maak een functie telop die twee argumenten verwacht:

(define (telop a b) (+ a b))

Roep nu de functie aan met maar één element:

(telop 5)
telop: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 1
  arguments...:
   5

Nog een paar voorbeelden:

(list-ref '(a b c))
list-ref: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 1
 
(cons 1 2 3)
cons: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 3

3.16.3 Buiten grenzen lezen of schrijven

Met list-ref kun je elementen in een lijst aanwijzen op basis van hun volgnummer. Als je naar een plaats wijst die niet bestaat dan krijg je een foutmelding.

(list-ref '(a b c) 5)
list-ref: index too large for list
  index: 5
  in: '(a b c)
 
(list-ref '(a b c) -2)
list-ref: contract violation
  expected: exact-nonnegative-integer?
  given: -2

3.16.4 Dingen die niet bestaan -> Undefined

Je kunt een functie pas gebruiken als je die eerst gemaakt hebt, bijvoorbeeld met define. Hetzelfde geldt voor variabelen.

compositie
compositie: undefined;
 cannot reference undefined identifier
 
(doe-iets 1 2 3)
doe-iets: undefined;
 cannot reference undefined identifier