Scheme

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Scheme er et funksjonelt programmeringsspråk i Lisp-familien. Scheme ble introdusert til den akademiske verden av Guy L. Steely og Gerald Jay Sussman gjennom flere artikler på 1970-tallet kalt «the lambda papers». Disse artiklene beskrev egenskapene til Scheme og gav en kompilator kalt «RABBIT» som kompilerte Scheme-kode til et subset av MacLISP (en tidlig Lisp dialekt). I dag er Scheme standardisert, og det finnes en rekke kompilatorer og tolkere for språket.

Sammen med Common Lisp er Scheme blant de mest brukte Lisp-dialektene. To ting som skilte Scheme fra andre Lisp-dialekter fra sin tid er at variabler har leksikalt skop («lexical scope») og at implementasjoner må garantere halekall-optimalisering («tailcall optimalization»).

Scheme følger en minimalistisk filosofi. Programmeringsspråkets syntaks er ekstremt enkel sammenlignet med andre språk, og antallet innebygde prosedyrer er relativt begrenset. Scheme brukes i dag hovedsakelig i akademiske miljøer, og har tradisjonelt blitt brukt i forskning på kunstig intelligens.

Standardisering[rediger | rediger kilde]

Det er to standarder som definerer Scheme; en offisiell IEEE-standard, og en de facto standard kalt «Revised Report on the Algorithmic Language Scheme», forkortet til RnRS, der n betegner revisjonen. Den siste revisjonen av RnRS heter R6RS og utvider språket, blant annet med et standardbibliotek.

Grunnet Scheme sitt begrensede antall innebygde funksjoner, tilbyr mange implementasjoner funksjonalitet som ikke omfattes av standardene nevnt ovenfor. I fellesskap har derfor utviklere bak forskjellige Scheme-implementasjoner laget flere «Scheme Requests for Implementation» (SRFI). En SRFI definerer utvidelser av språket som brukere kan benytte på tvers av forskjellige implementasjoner.

Egenskaper[rediger | rediger kilde]

Scheme er en veldig simplistisk Lisp-dialekt, med kun det mest nødvendige av datatyper og funksjoner tilgjengelig. Schemes filosofi er å, istedenfor å bygge ut språket med nye primitive datatyper og operasjoner, og dermed gjøre det stort og komplekst, være et enkelt og effektivt språk der slike nye finesser lett kan legges til av programmereren. Det er likevel en rekke Scheme-implementasjoner som kommer med mange medfølgende bibliotek.

Syntaks[rediger | rediger kilde]

Det er syntaksen til Lisp som i hovedsak er kilden til kritikk av språket. Uttrykk i Scheme skrives på såkalt listeform. En liste er ett eller flere elementer etter hverandre, omringet av parenteser. Et element kan være et atom (et primitivt «objekt» som f.eks. et tall eller et symbol), eller en kombinasjon, som er underlister i lista. I Scheme evalueres en liste ved å evaluere det første elementet i lista, for å få en funksjon. Denne funksjonen blir kalt med resultatet av å evaluere resten av elementene i lista. Et enkelt uttrykk kan se slik ut:

 (+ 1 2 (- 9 3) 2)

Her har vi en liste med symbolet +, to tall, kombinasjonen (- 9 3), og et tall. Kombinasjonen (- 9 3) er i seg selv en et uttrykk med symbolet – og to tall. Her vil + evalueres ved at symbolet blir slått opp i listen over variabelbindinger, og resultere i funksjonen for addisjon, som kalles med resultatet av å evaluere de andre elementene i lista som argument. 1 og 2 vil evaluere til seg selv, kombinasjonen (- 9 3) vil evalueres på samme måte, og 2 vil evaluere til seg selv. Vi får 11 som resultat.

Numerisk tårn[rediger | rediger kilde]

Scheme har et relativt godt utvalg av datatyper for tall. RnRS standardene legger ikke noen føring på hvordan tall skal representeres i minne. Det er definert et såkalt numerisk tårn som består av abstrakte datatyper for komplekse tall, reelle tall, rasjonale tall og heltall. Mens det er frivillig å implementere hele det numeriske tårnet i R5RS, er det påkrevd av R6RS.

Predikatene complex?, real?, rational? og integer? gjenkjenner hver enkel type, mens predikatet number? gjenkjenner alle. Dersom et tall er et heltall, så vil det også være et rasjonelt tall, et reelt tall og et komplekst tall. Mens et rasjonalt tall som 5/8 vil også være et reelt og komplekst tall, men ikke et heltall.

Implementasjoner må også skille mellom presise (exact?) og upresise (inexact?) tall. Et tall-objekt er presist dersom det enten er skrevet som en presis konstant, eller dersom det er resultatet av en presise operasjon utført på presise tall. Et tall-objekt kan være upresis dersom det er skrevet som et upresist tall, dersom det er resultatet av en upresis operasjon eller dersom det kommer fra en presis operasjon utført på upresise tall. R5RS standarden krever at dersom to implementasjoner kommer fram til et presist resultat fra en beregning som ikke involverer upresiste tall, så vil resultatene være matematisk like.

Funksjonskall[rediger | rediger kilde]

Siden man i Lisp må skrive alle funksjonskall i egne lister, med funksjonsnavnet først, gir det en rekke fordeler. Det er ingen forskjell på operatører og funksjoner, som det er i andre språk -- det er ingen syntaktisk måte man kan skille mellom brukerdefinerte funksjoner og primitive operatører, slik som det er i mange andre språk der man skriver operatører mellom argumentene, mens funksjoner kalles på andre måter. Dermed er det naturlig nok heller ingen form for operatør-prioritet i Lisp, siden alle funksjonskall er skrevet i egne lister. De negative sidene med prefiksnotasjon og lister er at det ikke følger den vanlige matematiske notasjonen, og dermed krever det en tilvenning å sette seg inn i Scheme, spesielt når man skal skrive matematiske uttrykk.

Scheme har bare én løkkefunksjon, kalt do. Andre former for iterasjon og løkker blir gjort ved hjelp av rekursjon. I Lisp skrives data og kode med samme syntaks. Det betyr at man kan bygge opp uttrykk som deretter kan evalueres. Et eksempel på dette:

 (define (lag-addisjon a b c)
   (list '+ a b c))

Her defineres en funksjon, lag-addisjon som tar tre argumenter, a, b og c. Denne funksjonen returnerer en liste med symbolet + og de tre argumentene. Merk at + blir skrevet med en apostrof foran. Dette er for å hindre at Scheme -- ved å følge evalueringsreglene forklart ovenfor -- evaluerer symbolet og lager en liste av funksjonsobjektet for addisjon istedenfor bare symbolet. Når en funksjon blir kalt, er det resultatet av det siste uttrykket i funksjonskoden som er returverdien for funksjonen. Siden listen lag-addisjon returnerer er skrevet som et uttrykk (med funksjonsnavnet først), kan det evalueres:

 (eval (lag-addisjon 1 2 3))
 => 6

eval er Scheme-interpreteret. Det blir kalt med resultatet av å kalle lag-addisjon, som er listen (+ 1 2 3), som argument. Svaret vi får er 6.

I Scheme er funksjoner primitive datatyper, akkurat som tall, strenger, symboler, osv. Det betyr at funksjoner kan sendes til andre funksjoner som argument, og funksjoner kan returnere andre funksjoner som returverdi. Sistnevnte, en funksjon som returneres av en annen funksjon, kalles en closure. En closure har fortsatt tilgang til variablene som var bundet i funksjonen som returnerte den. Dette gjør at closures kan brukes som objekter (i objektorientert sammenheng), med lokale variabler. Dette kan illustreres med følgende eksempel:

 (define (lag-person navn alder)     ; definer funksjonen lag-person
   (lambda (operasjon)               ; lag et funksjonsobjekt som tar et argument kalt operasjon
     (case operasjon                 ; se om operasjon er lik symbolet navn eller alder og returner henholdsvis navn og alder
       ('navn navn)
       ('alder alder))))

Her defineres en funksjon, lag-person som returnerer et funksjonsobjekt som representerer en person. Dette gjøres ved å lage en funksjon med lambda. Funksjonen tar et argument, som er en operasjon som objektet skal utføre. Vi kan bruke det slik (pilen «=>» viser hva hvert uttrykk evaluerer til):

 (define en-person (lag-person "Lars" 23))
 (en-person 'navn)
 => "Lars"
 (en-person 'alder)
 => 23

Dette viser bare litt av hvilke abstraksjoner og muligheter closures gir.

Scheme-implementasjoner[rediger | rediger kilde]

Eksterne lenker[rediger | rediger kilde]