Er zijn verschillende technieken en stijlen waarin een idee kan worden omgezet in SCHEME. Sommige daarvan zijn meer bottom up, andere meer top down. Een typische manier van bottom up code-ontwikkeling is vertrekkend van een specificatie in natuurlijke taal van een probleem, stukken daarvan vertalen naar SCHEME code, deze stukjes code interactief uittesten en tenslotte stukjes werkende code in functiedefinities incorporeren. Een bottom up methode is aangewezen voor kleine, relatief eenvoudige problemen, of voor het coderen van kleine onderdelen (modules) in de oplossing van grotere problemen. In het bekende faculteit voorbeeld zou de vertaling van tekst naar code op de volgende manier kunnen verlopen.
Om de faculteit van een getal te berekenen: als het getal gelijk is
aan 0 dan is het resultaat 1, als het getal groter is dan 0 is het
resultaat het product van het getal met de toepassing van faculteit op
het getal min 1.
Als (if
het getal gelijk is aan nul (zero? getal)
dan is het resultaat 1, 1
als (if
het getal groter is dan 0 (> getal 0)
dan is het resultaat
het product (*
van het getal getal
met de toepassing van faculteit (faculteit
op het getal min 1 (- getal 1)
Tenslotte moet alleen de LAMBDA toegevoegd worden, de indentatie wat
verzorgd, en de procedure gebonden aan een symbool met DEFINE.
(define faculteit
(lambda (getal)
(if (zero? getal)
1
(if (> getal 0)
(* getal (faculteit (- getal 1)))))))
> (faculteit 4)
24
> (faculteit 0)
1
Voor meer complexe problemen is een top down benadering meer aangewezen. In een top down perspectief wordt het probleem vertaald naar code door het te vertalen naar minder complexe sub-problemen, die op hun beurt weer verder uiteengerafeld worden tot nog meer eenvoudige sub-problemen, tot een niveau wordt bereikt waarin elke subtaak of sub-probleem via een bottom-up benadering kan worden gecodeerd als een relatief korte functie. Deze methode wordt wel eens functionele decompositie genoemd, of top down stepwise refinement.
Een tweede basisprincipe van een goede top down programmeerstijl is abstractie. Die abstractie speelt zowel op functie niveau als op data niveau. De code moet een abstracte, implementatie-onafhankelijke analyse van het op te lossen probleem weerspiegelen, en de ``ruige'' implementatiedetails moeten worden verborgen voor de gebruiker van de code achter een conceptuele representatie. Meestal zijn er verschillende alternatieve manieren waarop een specifiek probleem of sub-probleem kan worden gecodeerd. Het idee van abstractie is om de gebruiker van de code hiermee niet lastig te vallen. Wat telt is de conceptuele beschrijving van de oplossing van het probleem in termen van elkaar aanroepende SCHEME functies en datastructuren die de structuur van het probleem weergeven.
Functionele programmeertalen lenen zich goed tot een programmeerstijl waarin functionele decompositie en abstractie worden gecombineerd en elkaar wederzijds versterken.
Een recursieve functie is een functie in de body waarvan de functie zelf aangeroepen wordt (met andere argumenten). De eerder besproken functie faculteit is een recursieve functie. Stel bijvoorbeeld dat je zelf de functie lengte zou willen definiëren. De lengte van de lege lijst is 0, en de lengte van elke andere lijst is gelijk aan de lengte van de lijst met een element minder (de rest) + 1.
(define my-length
(lambda (lijst)
(if (null? lijst) 0
(+ 1 (my-length (cdr lijst))))))
Stel dat de functie wordt aangeroepen met als argument de lijst (aap noot). Deze lijst is niet leeg, dus wordt 1 opgeteld bij het resultaat van de evaluatie van (my-length '(noot)). Die lijst is ook niet leeg dus wordt de oorspronkelijke 1 bijgeteld bij 1 + het resultaat van de evaluatie van (my-length '()), wat 0 oplevert. Het resultaat is dus 1+1+0=2. De meeste LISP systemen kennen een special form TRACE die een overzicht geeft van het controleverloop van (recursieve) functies. Het tracen van functies (al dan niet recursief) kan nuttig zijn bij het testen en debuggen van programma's.
(trace my-length) (MY-LENGTH) > (my-length '(het leven is hard)) 1 Enter MY-LENGTH (HET LEVEN IS HARD) | 2 Enter MY-LENGTH (LEVEN IS HARD) | 3 Enter MY-LENGTH (IS HARD) | | 4 Enter MY-LENGTH (HARD) | | 5 Enter MY-LENGTH () | | 5 Exit MY-LENGTH 0 | | 4 Exit MY-LENGTH 1 | 3 Exit MY-LENGTH 2 | 2 Exit MY-LENGTH 3 1 Exit MY-LENGTH 4 4
De vorm van recursie in my-length is enkelvoudig en constructief. Bij enkelvoudige recursie wordt de functie slechts eenmaal opgeroepen in de body van de definitie. Bij meervoudige recursie wordt de functie twee of meer keer opgeroepen (met verschillende argumenten). Deze laatste vorm van recursie wordt vaak gebruikt wanneer een complexe expressie moet geanalyseerd worden op een of andere manier. Er zal dan in de body een recursieve aanroep van de functie gebeuren op de CAR en op de CDR van de complexe expressie. Bijvoorbeeld zoals in de volgende functie die het aantal getallen in een complexe expressie telt.
(define tel-getallen
(lambda (x)
(if (number? x)
1
(if (null? x)
0
(if (list? x)
(+ (tel-getallen (car x))
(tel-getallen (cdr x)))
0)))))
TEL-GETALLEN
> (tel-getallen '(a (9)(e f ((6) d) 5)))
3
Bij constructieve recursie wordt een functie-aanroep ``omgezet'' naar een recursieve aanroep waarop daarna een bewerking wordt uitgevoerd (bij MY-LENGTH was dat 1 bijtellen, bij FACULTEIT was dat een getal vermenigvuldigen. Wanneer we er in slagen een recursieve functie te schrijven die een functie-aanroep reduceert tot een recursieve aanroep zonder dat er een bewerking op uitgevoerd wordt, hebben we te maken met staartrecursie. Deze vorm van recursie is veel efficiënter dan constructieve recursie omdat minder geheugen in beslag wordt genomen door tussenoplossingen.
> (define my-length-staart
(lambda (lis accu)
(if (null? x)
accu
(my-length-staart (cdr x) (+ 1 accu)))))
MY-LENGTH-STAART
> (my-length-staart '(het leven is hard) 0)
4
Er zijn een aantal stappen die doorlopen worden bij het opstellen van een recursieve definitie.
Definieer LEAVES, met als argument een complexe expressie (boom), en
als resultaat een lijst van de bladeren van de boom.
Bijv. (leaves '(a (b (c d)) e)) -> (A B C D E)
1. Eindcondities
(null? tree) ; Lege lijst
(not (list? tree)) ; Symbool of ander leaf
2. Resultaat eindcondities
(null? tree) => () ; geen leaves in de lege lijst
(not (list? tree)) => (list tree) ; 1 leaf in elke niet-lijst
3. Van typisch geval naar eindgeval
tree = lijst =>
combineer (leaves (car tree)) met (leaves (cdr tree))
4. Hoe combineren
(append (leaves (car tree))(leaves (cdr tree)))
5. Integratie
(define leaves
(lambda (tree)
(if (null? tree)
'()
(if (not (list? tree))
(list tree)
(append (leaves (car tree))
(leaves (cdr tree)))))))