Meest voorkomende fouten in Scheme
Op basis van oplossingen van examenvragen van de voorgaande jaren werd een lijstje opgesteld met veel voorkomende fouten die gemaakt worden tegen de programmeertaal Scheme. Alle nuttige opmerkingen, wijzigingen en aanvullingen op dit lijstje zijn welkom, en zullen - indien relevant - in de toekomst mee opgenomen worden.
Op het examen zou je de fouten die hier opgesomd worden niet meer mogen maken.
1 Lijsten
a) Veel mensen maken op het einde van de cursus nog steeds fouten tegen het gebruiken van cons, car en cdr. Dergelijke fouten zijn echt onaanvaardbaar. Ziehier de belangrijkste regels voor een juist gebruik ervan:
(cons (car P) (cdr P)) = P waarbij P een pair (d.w.z. een cons-cel) is
(car (cons A B)) = A waarbij A en B om het even wat zijn
(cdr (cons A B)) = B waarbij A en B om het even wat zijn
Opmerking: met bovenstaande gelijkheden wordt equal? bedoeld en niet eq?. De expressies zijn immers niet eq? omdat er aan de linkerkant telkens een nieuwe cons-cel aangemaakt wordt. (De inhouden van deze cons-cellen zijn echter wel gelijk.) Zie sectie 4 over gelijkheid van expressies voor meer uitleg over het verschil tussen eq? en equal?.
b) Ook wordt het verschil in gebruik van cons, append en list niet altijd goed begrepen. Daarom een opsomming van de manieren waarop deze operaties wel gebruikt kunnen/moeten worden.
Syntax |
| Voorbeeld |
| Output-representatie |
(cons iets atoom) |
| (cons 'a 'c) |
| (a . c) |
| (cons '(a b) 'c) |
| ((a b) . c) | |
(cons iets lijst) |
| (cons 'a '(c d)) |
| (a c d) |
| (cons '(a b) '(c d)) |
| ((a b) c d) | |
(append lijst lijst) |
| (append '(a b) '(c d)) |
| (a b c d) |
(list iets1 ... ietsn) |
| (list 'a 'b 'c) |
| (a b c) |
c) Slechts in het volgende uitzonderlijke geval kan je een append vervangen door een cons.
(append (list iets list)) = (cons iets lijst)
Dezelfde opmerking als eerder kan gemaakt worden over bovenstaande gelijkheid.
(define (atom? x) (not (pair? x)))
> (atom? '()) #t
In de praktijk betekent dit dat als je een conditie wilt schrijven die zowel test op atom? als op null?, de volgende volgorde gerespecteerd moet worden
(define (proc lst) (cond ((null? lst) ...) ((atom? lst) ...) (...)))
Immers, indien je eerst op atoom test en dan pas op de lege lijst, zal je nooit in de tak overeenstemmend met de lege lijst terechtkomen, omdat dit geval reeds wordt opgevangen in de tak die test op atom?.
Opmerking: In sommige Scheme versies (bvb. EdScheme 4.2) bestaat een voorgedefinieerd predicaat atom? dat enigszins anders werkt. Dit predicaat geeft alleen #t voor echte atomen (dus niet voor de lege lijst) en geeft #f voor ale andere dingen. Met dit predicaat stelt het bovenstaande probleem zich niet. De predicaten atom? en null? zijn dan immers complementair.
2 Quoting
Ziehier een aantal fouten die te maken hebben met het verschil tussen wel of geen quoting a) Een typische fout is (list a b c) te schrijven als je eigenlijk (list 'a 'b 'c) bedoelt (of omgekeerd).
(list a b c) => maakt een lijst van de waarden van de variabelen a, b en c
(list 'a 'b 'c) => maakt een lijst van de symbolen a, b en c
'(a b c) => maakt een lijst van de symbolen a, b en c
(define (bubble-sort data) ...) (define (quick-sort data) ...) (define (insertion-sort data) ...)
(define sorteer-algoritmes (list bubble-sort quick-sort insertion-sort))
(define sorteer-algoritmes '(bubble-sort quick-sort insertion-sort))
(define sorteer-algoritmes (list 'bubble-sort 'quick-sort 'insertion-sort))
(define sorteer-algoritmes (bubble-sort quick-sort insertion-sort))
3 Special Forms
Special forms in Scheme zijn de functies die een speciaal evaluatie-gedrag hebben. Enkele van de meest gekende special forms zijn: if, cond,and,or,define,lambda, let,set!,... Het is belangrij kdat je voor elk van deze special forms weet welk speciaal evaluatie-gedrag ze hebben.
a) (if <condition> <consequence> <alternative>) heeft als speciaal evaluatie-gedrag dat UITSLUITEND die tak die overeenstemt met de waarheidswaarde van de conditie zal worden geëvalueerd. De andere tak wordt volledig genegeerd. Dit is een voorbeeld van lazy evalutation: alleen wat echt nodig is wordt geëvalueerd, de rest wordt genegeerd.
b) Ook de and en de or werken met lazy evaluation:
(or A1 ... An)
=> geeft eerste argument terug dat "TRUE" is en evalueert de andere argumenten niet.
=> geeft #f terug alleen als alle argumenten #f zijn.
(and A1 ... An)
=> geeft eerste argument terug dat #f is en evalueert de andere argumenten niet.
=> geeft #t terug alleen als alle argumenten "TRUE" zijn.
Let op: onder "TRUE" verstaan we alles dat niet #f is. M.a.w. behalve #t worden getallen, procedures, karakters, ... ook allemaal als "TRUE" beschouwd. De booleaanse operatoren and en de or kunnen dus ook opgeroepen worden wanneer niet alle argumenten #t of #f teruggeven, maar eventueel ook een getal,...
> (or #f (> 1 2) (+ 3 1) #t) 4
> (and #t (< 1 2) (* 7 1)) 7
(cond ((<= n 1) (display "n is kleiner dan 1")) ((> n 1) (display "n is groter dan 1")) ((<= n 3) (display " en kleiner dan 3")))
(cond ((<= n 1) (display "n is kleiner dan 1")) ((> n 1) (if (< n 3) (display "n is groter dan 1 en kleiner dan 3"))) (else (display "n is groter dan 3")))
Merk op dat de geneste if-clausule geen alternative heeft. Dit betekent echter NIET dat daardoor in de overblijvende condities uit de buitenliggende conditional wordt verder gezocht. Indien n = 2 wordt er afgedrukt: "n is groter dan 1 en kleinder dan 3". Indien n = 4 komen we eerst in de tak (> n 1) van de conditie, en dan in de ontbrekende alternative van de if. Omdat dit deel ontbreekt is het uiteindelijke resultaat dan ook ongedefiniëerd. (In de bovenstaande code zal de else tak van de conditional trouwens NOOIT uitgevoerd worden, omdat de eerste twee takken reeds alle mogelijke gevallen behandelen).
4 Gelijkheid van expressies
In Scheme zijn er drie belangrijke predicaten (d.w.z. procedures die uitsluitend #t of #f teruggeven) die kunnen gebruikt worden om te controleren of twee expressies equivalent zijn. Deze zijn: eq?, equal? en eqv?. Er bestaat een zekere relatie tussen deze drie predicaten, nl:
Indien (eq? <expr1> <expr2>) dan zeker ook (eqv? <expr1> <expr2>) en analoog:
Indien (eqv? <expr1> <expr2>) dan zeker ook (equal? <expr1> <expr2>) en door transitiviteit dus ook:
Indien (eq? <expr1> <expr2>) dan (scheme (eualq? <expr1> <expr2>)).
De omgekeerde implicaties gelden echter niet noodzakelijk. Wat zijn dan precies de verschillen tussen de verschillende predicaten?
a) (eq? <expr1> <expr2>) is eigenlijk niet meer dan een vergelijking van geheugenadressen, en is alleen maar #t indien expr1 en expr2 in het geheugen op hetzelfde adres te vinden zijn. In alle andere gevallen is eq? ofwel #f ofwel onbepaald.
b) (eqv? <expr1> <expr2>) geeft kort gezegd altijd #t terug indien expr1 en expr2 "normaal gezien" als hetzelfde object zouden moeten beschouwd worden. Enkele voorbeelden van expressies die "normaal gezien" hetzelfde zouden moeten zijn worden gegeven in de R5RS.
c) (equal? <expr1> <expr2>) tenslotte laat zelfs toe diep-geneste data-structuren zoals pairs, vectoren, lijsten en strings met elkaar te vergelijken doordat op recursieve wijze het eqv? predicaat wordt opgeroepen voor de basiscomponenten. Een vuistregel is dat de twee expressies equal? zijn indien ze hetzelfde afgedrukt worden. Voor circulaire data-structuren kan equal? falen.
d) Tenslotte zijn er nog enkele andere vergelijkende predicaten zoals:
= voor gelijkheid op getallen;
string=? voor gelijkheid op strings;
char=? voor gelijkheid op karakters;
enz...
Om deze uitleg af te ronden volgen nog enkele verduidelijkende voorbeelden:
* Alhoewel (equal? (cons 'a 'b) (cons 'a 'b)) als resultaat #t geeft omdat beide argumenten dezelfde structuur hebben, geeft (eq? (cons 'a 'b) (cons 'a 'b)) als resultaat #f omdat beide argumenten een andere cons-cel in het geheugen voorstellen. (Telkens cons wordt opgeroepen stelt dit een nieuwe geheugencel voor.) Voor eqv? is het resultaat ook #f omdat eqv? voor pairs, vectoren en strings om efficiëntieredenen slechts de geheugenadressen vergelijkt).
* (eqv? 2 2) is #t omdat twee gelijke getallen normaal gezien toch hetzelfde zoudenmoeten voorstellen. Bijgevolg is dus ook (equal? 2 2) true. Maar (eq? 2 2) is onbepaald. (D.w.z. in sommige versies #t en in andere #f, afhankelijk van de implementatie van getallen.)
* Voor nog meer voorbeelden verwijzen we naar de R5RS.
5 Definities
Slechts in SOMMIGE Scheme-implementaties is het toegelaten om defines te nesten binnenin een andere, maar zelfs dan MOET elke geneste define steeds helemaal in het begin staan van de body van de daarbuiten liggende define. Als je dit niet doet krijg je een foutmelding in de stijl van Ill-placed define. Schrijf dus niet:
(define (foo x) (if (= x 1) (begin (define a 1) a) (begin (define b 0) b)))
maar wel:
(define (foox) (define a 1) (define b 0) (if (= x 1) a b))
(define (foo x) (let ((a 1) (b 0)) (if (= x 1) a b)))
6 Groeperen en combineren van expressies
(begin expressie1 expressie2 ... expressieN)
De expressies worden geëvalueerd van links naar rechts en ALLEEN de waarde van de laatste expressie wordt teruggegeven. De resultaten van de andere expressies worden genegeerd. Een dergelijke is dus alleen maar nuttig om expressies te groeperen die side-effects (zoals input en output) hebben, bijvoorbeeld:
(begin (display "Hello ") (display "world"))
Een fout die vaak gemaakt wordt is het gebruik van een begin om expressies te groeperen waarvan de resultaten wel belangrijk zijn. Een voorbeeld hiervan wordt verderop gegeven.
b) Juist dezelfde opmerking geldt voor het gebruik van een else-tal in een cond. Het is toegelaten om in deze else-tak meerdere expressies te schrijven. Elk van deze expressies zal in volgorde van links naar rechts geëvalueerd owrden (en kan dus eventueel side-effects negeren), maar alleen het resultaat van de laatste expressie zal teruggegeven worden:
(else ... ... ...) => Alleen het resultaat van het laatste statement telt!
c) Bij het schrijven van een boomrecursieve procedure wordt vaak vergeten de geaccumuleerde deelresultaten te combineren. Bijvoorbeeld:
(define (treeproc tree ...) (cond ((null? tree) ...) ((atom? tree) ...) (else (... => vergeet niet hier iets in te vullen! (treeproc (car tree) ...) (treeproc (cdr tree) ...)))))
Indien je gewoon zou schrijven:
(else (treeproc (car tree) ...) (treeproc (cdr tree) ..))
Natuurlijk is het ook verkeerd om gewoon begin in te vullen, omdat er dan nog steeds niets met het resultaat van (treeproc (car tree)) gebeurt.
7 Destructieve operaties
Enkele misconcepties met betrekking tot het gebruik van destructieve operaties zijn:
a) Een set!, set-car! of set-cdr! geeft niet noodzakelijk het verwachte resultaat terug. Dit hangt sterk af van de gebruikte Scheme versie.
(set! x 5) => #undefined (in Gambit Scheme)
(set! x 5) => 5 (in PC Scheme)
(set! x 5) => ??? (in andere Scheme versies)
Volgens de Scheme standaard is het resultaat van een set! ongedefinieerd. Schrijf je programma’s dus steeds in de veronderstelling dat je NIET weet wat het resultaat van een destructieve operatie zal zijn, anders heb je incompabiliteiten met andere Scheme versies.
b) set! dient enkel om een identifier van een waarde te voorzien. Gebruik dus enkel (set! x 5), waarbij x een variabele is, en niet zoiets als (set! (car x) 5) of (set! (cdr x) 5). Als je de car of de cdr van een cons-cel wilt veranderen gebruik dan steeds set-car! en set-cdr!.
8 Stijlfouten
Deze paragraaf beschrijft enkel fouten die niet echt fouten zijn in de strikte zin van het woord, maar die wel een invloed kunnen hebben op de leesbaarheid of performantie van een programma.
a) Kies steeds goede en leesbare namen voor je variabelen. Gebruik bijvoorbeeld zo weinig mogelijk variabelen van 1 enkele niets-zeggende letter. Een andere typische stijlfout is de naam iter te gebruiken voor procedures die geen iteratief proces genereren. Waar je ook voor moet opletten is geen voorgedefinieerde keywords (zoals begin of list) als variabele-namen te gebruiken. Dit kan immers nogaal eens voor moeilijk op te sporen fouten zorgen.
b) Gebruik lokale definities om code-duplicatie te vermijden. Veronderstel bijvoorbeeld dat er een functie (calculate x) is gedefinieerd, en dat je ergens anders iets hebt staan van de vorm:
(calculate a) ... (calculate a) ... ... ... (calculate a) ... (calculate a)
(let ((calc (calculate a))) calc ... calc ... ... ... calc ... calc)
Dit is trouwens niet alleen een stijlfout, maar kan ook een sterk verschil in efficiëntie betekenen. Merk wel op dat bovenstaande oplossing alleen maar geldt als calculate een functie is zonder side-effects.
c) Een andere stijlfout is een overdreven gebruik van display om informatie op het scherm af te drukken. Elke functie in Scheme geeft uiteindelijk een resultaat terug. Het is dus meestal niet nodig dit resultaat op het scherm af te drukken d.m.v. een display. Scheme zorgt er uiteindelijk zelf wel voor dat het eindresultaat in het interaction window terecht komt.
d) Onthoud bovendien dat het resultaat van een display of newline onbepaald is (d.w.z. afhankelijk van de gebruikte Scheme-versie). Het is dus aangeraden het resultaat dat hieruit komt niet expliciet te gebruiken/
e) Ten gevolge van het speciale evaluatie-gedrag van een and is het SOMS mogelijk om expressies te groeperen d.m.v. een and i.p.v. een begin.
(and (display "Hello ") (display "world"))
Dit werkt op dezelfde manier als een begin-statement, op voorwaarde dat geen van de gegroepeerde expressies een #f teruggeeft, Nochtans getuigt dit niet van een mooie programeerstijl, en wel om de volgende redenen:
* Je misbruikt and om dingen te doen waarvoor die eigenlijk niet gemaakt is. Dit komt de leesbaarheid van een programma niet ten goede.
* Je moet nagaan of geen enkele van de expressies #f teruggeeft, anders werkt dit truckje niet of verkeerd.
* Er is geen enkele reden om het met een and te schrijven, want het kan ook met een begin-statement dat er wel speciaal voor ontworpen is.
(if (< 3 4) #t #f)
Hier schrijf je dus eigenlijk: als (< 3 4) naar #t evalueert, geeft dan #t terug. Als het naar #f evalueert, geef dan #f terug. Veel korter en mooier is dus om te schrijven:
(< 3 4)
dat immers ook #t als de test naar #t evalueert en #f als de test naar #f evalueert.