Ordning
| Programmeringssprog _ | |
|---|---|
 | |
| Forfatter | Guy L. Steele , Gerald Jay Sussman |
| Oprindelsesdato | 1970 |
| Nyeste version | R7RS (2013) |
| Brug | Sproglig |
| Paradigmer | Funktionel , proceduremæssig , metaprogrammering |
| Skrivning | Stærk, dynamisk |
| Almindelige udvidelser | .scm .ss |
| Påvirket af | Lisp , ALGOL og MDL |
| Referenceimplementering | |
| Internet side | www.scheme-reports.org/ |
Scheme er et funktionelt programmeringssprog , en dialekt af Lisp , som det bevarer alle egenskaberne af, som blev udviklet i 1970'erne af Guy L. Steele og Gerald Jay Sussman , som introducerede det til den akademiske verden med en række artikler kendt som le Lambda Papers og i bogen Structure and Interpretation of Computer Programs , brugt i årtier som tekst i nogle informationsvidenskabelige eksamener. GNOME desktop-manageren inkorporerer Scheme Guile -fortolkeren .
Eksempel på programmer
Hej verden
Følgende eksempel viser teksten "Hej verden".
( "Hello World!" display ) ( newline )
Nogle mere komplekse eksempler
Følgende eksempel beregner den største fælles divisor af de numeriske argumenter x og y.
( definer ( mcd x y )
( cond (( = x y ) x )
(( > x y ) ( mcd ( - x y ) y ))
( else ( mcd x ( - y x )))))
Følgende eksempel bruges til at vende rækkefølgen af tegn i en streng; for eksempel fra "abcdef" får vi "fedcba".
( define ( sl w ) ( substring w ( sub1 ( string-længde w )) ( string-længde w )))
( define ( dl w ) ( substring w 0 ( sub1 ( string-længde w )))
( define ( omvendt s w )
( if ( = ( streng-længde s ) 0 ) w
( omvendt ( dl s ) ( streng-tilføj w ( sl s )))))
Dette gør i stedet det samme som eksemplet ovenfor, men bruger nogle Scheme-funktioner.
( define ( reverse s ) ( reversem s " " ) ) ; halerekursion
( define ( reverse2 w )
( list-> string ( reverse ( streng - > liste w ))) ) ; standard
Denne funktion bruges til at vide, om et tal er primtal:
( definer ( primtal? m n s )
( hvis ( = ( sub1 n ) s ) "er primtal"
( hvis ( = 0 ( resterende n ( add1 s )))) ( string-append "er ikke primtal, det er deleligt med : " ( tal-> streng ( add1 s )))
( first? m n ( add1 s )))))
( definer ( first? n ) ( first? m n 1 ))
Programmering
I modsætning til de fleste andre programmeringssprog bruger Scheme en præfiksnotation, som er en notation, hvor du i stedet for at skrive (2 + 3) skriver (+ 2 3). Denne notation forplanter sig til alle funktioner, så hvis vi har en N-ær funktion f, vil dens repræsentation være (f argument1 argument2 ... argumentN).
Datatyper
Skemaet implementerer alle typer grundlæggende data: booleaner, tal, tegn, strenge, vektorer. Det inkluderer dog også specielle typer, herunder lister (par), porte (datastrømme), symboler og procedurer.
For at genkende disse typer data giver Scheme særlige funktioner, hvis identifikator har formatet "typeDiD?" som returnerer den boolske TRUE, hvis argumentet, der sendes, er i formatet datatype. Her er en oversigtstabel:
| Fungere | Forklaring |
|---|---|
(boolean? argomento) |
er argumentet boolsk? |
(number? argomento) |
er argumentet et tal? |
(char? argomento) |
argumentet er en karakter? |
(string? argomento) |
er argumentet en streng? |
(vector? argomento) |
er argumentet en vektor? |
(list? argomento) |
er emnet en liste? |
(port? argomento) |
argumentet er en dør? |
(symbol? argomento) |
er argumentet et symbol? |
(procedure? argomento) |
argumentet er en procedure? |
Lad os nu se på nogle detaljer om disse typer data.
Booleans
De er angivet med hash-tegnet og bogstavet T (SAND) for sand og F (FALSK) for falsk. Så #T er sandt, mens #F er falsk.
Funktionerne på booleanerne er de sædvanlige:
| Fungere | Resultat returneret |
|---|---|
(not arg) |
afviser arg. falsk-> sand og sand-> falsk |
(and arg1 arg2 ...) |
falsk, falsk-> falsk falsk, sand-> falsk sand, sand-> sand |
(or arg1 arg2 ....) |
falsk, falsk-> falsk falsk, sand-> sand sand, sand-> sand |
Tal
Numeriske konstanter skrives efter de sædvanlige regler. Forskellige typer numeriske data er tilgængelige: positive og negative tal, tal med kommaer, tal i eksponentiel notation og komplekse tal. For at genkende, hvilken klasse af tal et taludtryk tilhører, kan du bruge en af følgende funktioner, igen udpeget af et spørgsmålstegns-id, som returnerer en boolsk værdi:
| Fungere | Resultat returneret |
|---|---|
(integer? argomento) |
argumentet er et heltal |
(rational? argomento) |
argumentet er et rationelt tal |
(real? argomento) |
argumentet er reelt |
(complex? argomento) |
argumentet er et komplekst tal |
Det er også muligt at angive nummereringsgrundlaget ved hjælp af #fN, hvor f er grundtallet og N et tal:
| Mulige baser | Basistype |
|---|---|
#bN |
N er binær |
#oN |
N er oktal |
#dN |
N er decimal |
#xN |
N er hexadecimal |
- dN bruges praktisk talt aldrig, da grundtallet er decimal som standard.
Så er der følgende booleske (spørgsmålstegn) og konverteringsfunktioner:
| Funktioner | funktionalitet |
|---|---|
(exact? espressione) |
Giver udtrykket et nøjagtigt tal? |
(inexact? espressione) |
Giver udtrykket et omtrentligt tal? |
(exact->inexact espressione) |
Tilnærme værdien af udtrykket |
(inexact->exact espressione) |
Konverterer en omtrentlig værdi til en nøjagtig værdi. |
For yderligere at klassificere tal, for eksempel mellem positive og negative, eller lige og ulige, giver Scheme følgende primitiver:
| Funktioner | funktionalitet |
|---|---|
(zero? numero) |
Er tallet et nul? |
(positive? numero) |
Er tallet positivt? |
(negative? numero) |
Er tallet negativt? |
(odd? numero) |
Er tallet ulige? |
(even? numero) |
Er nummeret lige? |
Så som på de fleste sprog er der naturligvis både aritmetiske operatorer og mange matematiske funktioner tilgængelige.
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(+ arg1 arg2 ... argN) |
arg1 + arg2 + ... + argN | numerisk |
(- arg1 arg2 ... argN) |
arg1-arg2 -...- argN | numerisk |
(* arg1 arg2 ... argN) |
arg1 * arg2 * ... * argN | numerisk |
(/ arg1 arg2 arg3... argN) |
(.. (arg1 / arg2) / arg3) ... / argN | numerisk |
(log arg) |
naturlig log af arg | numerisk |
(exp arg) |
eksponentiel af arg | numerisk |
(sin arg) |
sinus af arg | numerisk |
(cos arg) |
cosinus af arg | numerisk |
(tan arg) |
tangens af arg | numerisk |
(asin arg) |
arcsine af arg | numerisk |
(acos arg) |
arccosinus af arg | numerisk |
(atan arg) |
arctangens af arg | numerisk |
(sqrt arg) |
kvadratrod arg | numerisk |
(expt base potenza) |
base ^ magt | numerisk |
(abs arg) |
absolut værdi af arg | numerisk |
(quotient arg1 arg2) |
heltalsresultat af arg1 / arg2 divisionen | numerisk |
(remainder arg1 arg2) |
(positiv) resten af divisionen | numerisk |
(modulo arg1 arg2) |
resten af divisionen | numerisk |
(ceiling arg) |
tag af arg (tilnærmelse af heltalsdelen opad) | numerisk |
(floor arg) |
arg floor (tilnærmelse af hele delen ned) | numerisk |
(round arg) |
generisk tilnærmelse af arg | numerisk |
(truncate arg) |
trunkering af arg | numerisk |
(max arg1 ... argN) |
maksimal værdi mellem arg1 og argN | numerisk |
(min arg1 ... argN) |
minimumsværdi mellem arg1 og argN | numerisk |
(gcd arg1 ... argN) |
største fælles faktor mellem arg1..e .. argN | numerisk |
(lcm arg1 ... argN) |
mindste fælles multiplum mellem arg1 .. og .. argN | numerisk |
(numerator arg) |
tæller af arg | numerisk |
(denominator arg) |
nævner af arg | numerisk |
(= arg1 arg2 ... argN) |
arg1 = arg2 = ... = argN? | boolesk |
(< arg1 arg2 ... argN) |
arg1 <arg2 <... <argN? | boolesk |
(> arg1 arg2 ... argN) |
arg1> arg2> ...> argN? | boolesk |
(>= arg1 arg2 ... argN) |
arg1> = arg2> = ...> = argN? | boolesk |
(<= arg1 arg2 ... argN) |
arg1 <= arg2 <= ... <= argN? | boolesk |
Tegn
I Skema er tegnene angivet med en hash, efterfulgt af en omvendt skråstreg og det tegn, der skal udtrykkes (uden omvendt skråstreg ville der være tvetydighed mellem tegnene T og F og booleanerne TRUE og FALSE).
Blandt de relevante funktioner finder vi:
| Funktioner | Resultat returneret |
|---|---|
(char=? char1 char2) |
Er char1 det samme som char2? |
(char<? char1 char2) |
Er char1 leksikografisk ringere end char2? |
(char>? char1 char2) |
Er char1 leksikografisk overlegen i forhold til char2? |
(char<=? char1 char2) |
er char1 leksikografisk ikke bedre end char2? |
(char>=? char1 char2) |
er char1 leksikografisk ikke ringere end char2? |
Der er også ci-versionen af disse funktioner, der ikke skiller mellem store og små bogstaver: vi har derfor char-ci = ?, char-ci <?, char-ci <= ?, og så videre.
Andre funktioner, der fungerer på tegn, er følgende:
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(char? arg) |
er arg en karakter? | boolesk |
(char-alphabetic? arg) |
er arg et alfabetisk tegn? | boolesk |
(char-numeric? arg) |
arg er et tegn, der repræsenterer et tal? | boolesk |
(char-whitespace? arg) |
arg er et blanktegn? | boolesk |
(char-upper-case? arg) |
arg er et stort alfabet? | boolesk |
(char-lower-case? arg) |
arg er et lille alfabet? | boolesk |
(char->integer arg) |
karakteren omdannes til et tal | numerisk |
(integer->char arg) |
tallet omdannes til et tegn | Karakter |
(char-upcase arg) |
det alfabetiske tegn bliver stort | Karakter |
(char-downcase arg) |
det alfabetiske tegn bliver små bogstaver | Karakter |
Strings
Strengene i skemaet er repræsenteret i dobbelte anførselstegn (eksempel: "dette er en streng"). Nogle funktioner til strengstyring er følgende:
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(make-string n) |
skabe en lang streng n | snor |
(make-string n ch) |
skaber en lang streng n, der kun består af tegnet ch | snor |
(string char1 char2 ..charN) |
opretter en streng bestående af tegnene char1, char2, ... charN | snor |
(string-length str) |
returnerer størrelsen af str | numerisk |
(string-ref str idx) |
returnerer tegnet ved position idx i strengen str | Karakter |
(substring str beg end) |
returnerer den del af strengen str, der er indeholdt mellem de to indekser start og end | snor |
(string-set! str idx ch) |
erstatter med ch, tegnet ved position idx i strengen str | snor |
(string-append str1 str2...strN) |
sammenkæder str1, str2, ..., strN | snor |
(string-copy str) |
returnerer en kopi af strengen str | snor |
(string->list str) |
returnerer en liste bestående af tegnene i strengen str | liste |
(list->string lst) |
returnerer en streng bestående af tegnene fra den første liste | snor |
Hvad angår tegn, har vi strengsammenligningsoperatorer, som er analoge med dem for tegn. De vigtigste er anført nedenfor og findes også i string-ci-versionen (ufølsom mellem store og små bogstaver):
| Funktioner | Resultat returneret |
|---|---|
(string=? str1 str2) |
Er str1 det samme som str2? |
(string<? str1 str2) |
Er str1 leksikografisk ringere end str2? |
(string>? str1 str2) |
Er str1 leksikografisk overlegen str2? |
(string<=? str1 str2) |
er str1 leksikografisk ikke overlegen i forhold til str2? |
(string>=? str1 str2) |
er str1 leksikografisk ikke ringere end str2? |
Lister
Som angivet ovenfor er lister en bestemt type data. Ligesom arrays repræsenterer de ordnede samlinger af elementer; i modsætning til arrays kan elementer være heterogene (af forskellige typer) og kan heller ikke indekseres. Listerne er lavet som par: (2 3) repræsenterer et eksempel på en liste, som åbenlyst er et par; men også (2 3 4) er faktisk et par, dannet af det første element (2) og af alle de andre (3 4). Til gengæld er "alle andre"-elementet et par dannet af dets første element (3) og alle de andre (i dette tilfælde kun 4). Listen beskrives så meget naturligt i rekursive termer.
En liste kan indeholde enhver type data, såsom tegn, strenge, booleaner og endda andre lister (eksempel: "(2 3 (4 5))"); som nævnt kan de også indeholde blandede datatyper (eksempel: "(# \ T 4 (4 #F (" streng ")))").
De to grundlæggende funktioner til at handle på lister refererer til den rekursive definition nævnt ovenfor: vi har således funktionen car , som returnerer det første element, og cdr , som returnerer det andet element ("alle andre"-elementet).
De vigtigste funktioner, som Scheme giver til lister, er som følger:
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(list arg1 arg2 ... argN) |
konstruerer en liste bestående af arg1, arg2, ..., argN argumenter | liste |
(pair? lst) |
er den første liste ikke tom? | boolesk |
(car lst) |
returnerer det første element i den første liste | blandet |
(cdr lst) |
returnerer listen dannet af elementerne fra det andet til det sidste element i listen lst | liste |
(cadr lst) |
returnerer det første element af listen, der ville blive opnået ved at kalde(cdr lst) |
blandet |
(cons arg lst) |
returnerer en liste med arg i første omgang | liste |
(append lst1 lst2) |
sammenkæder de to lister lst1 og lst2 | liste |
(length lst) |
returnerer antallet af elementer på listen | numerisk |
(reverse lst) |
vender elementerne i listen om | liste |
Vi bemærker, at der i denne liste er aggregerede funktioner, der svarer til sammensætningen af bil og cdr: udtrykket (cdr (cdr lst)) kan skrives mere kortfattet som cddr (lst), mens (car (cdr lst)) er kan syntetisere med cadr (lst).
Skema præsenterer derefter andre sammensatte funktioner, hvoraf nogle simulerer funktioner på vektorer, og andre konverteringen af liste til vektor og omvendt:
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(null? lst) |
er den første liste tom? | boolesk |
(set-car! lst arg) |
sæt den første position til arg-værdien | liste |
(set-cdr! lst arg) |
sæt den anden position til arg-værdien | liste |
(list-ref lst k) |
returnerer elementet på position k på den første liste | blandet |
(list->vector lst) |
returnerer en vektor dannet af elementerne i listen lst | vektor |
(vector->list vctr) |
returnerer en liste bestående af elementerne vel vektor vctr | vektor |
Særlige funktioner, der virker på lister, er funktionerne anvende, kort og for hver:
| Funktioner | Resultat returneret |
|---|---|
(apply f lst) |
udfører funktionen f ved at bruge dem på listen som elementer |
(map f lst1...lstN) |
udfører funktion f på elementer i samme indeks som listen |
(for-each f lst1...lstN) |
udfører funktion f på listeelementer |
For at forklare bedre, lad os tage et eksempel:
> (definer lst1 (liste 2 3 4 5 6)) > (anvend + lst1) >> 20 > (definer lst2 (liste 1 2 3 4 5)) > (kort + lst1 lst2) >> (3 5 7 9 11)
Vektorer
Vektorer er standardarrays, det vil sige, de er en struktur, der kun indeholder én type data. De er repræsenteret som lister med et hash-præfiks, det vil sige # (el1 el2 ... elN), hvor el1 har indeks 0, og elN har indeks N-1.
Funktionerne, som Scheme giver til styring af vektorer, er som følger:
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(vector arg1 arg2 ... argN) |
konstruerer en vektor dannet af elementerne arg1, arg2, ..., argN | vektor |
(make-vector n) |
konstruerer en vektor dannet af n tomme elementer | vektor |
(make-vector n arg) |
konstruerer en vektor dannet af n elementer af typen arg | vektor |
(vector-length vctr) |
returnerer antallet af elementer i vctr-vektoren | numerisk |
(vector-ref vctr idx) |
returnerer elementet i idx-positionen af vctr-vektoren | vektor |
(vector-set! vctr idx arg) |
indstiller vektorelementet vctr ved idx-indekset til værdien arg | vektor |
Døre
Porte er objekter, der repræsenterer datastrømme. Adskillige funktioner er tilgængelige på portene, blandt hvilke vi finder læsning / skrivning fra standardinput / output (læse / skrive tegn fra / til terminalen, svarende til printf- og scanf-funktionerne i C-sproget) og filhåndtering. Portene kan åbnes i input (læse data) og i output (skrive data).
Nogle af de funktioner, som ordningen tilbyder, er som følger:
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(input-port? arg) |
arg er en inputport? | boolesk |
(output-port? arg) |
arg er en udgangsport? | boolesk |
(open-input-file str) |
åbner en fil, hvis navn er strengen str som inputport | bringer |
(open-output-file str) |
åbner en fil, hvis navn er strengen str som outputport | bringer |
(close-input-file str) |
lukker en fil, hvis navn er strengen str, åbnet i input | ikke noget |
(close-output-file str) |
lukker en fil, hvis navn er strengen str, åbnet i output | ikke noget |
Læser data
Dataaflæsninger, kaldet "input operationer", foregår gennem følgende funktioner:
| Funktioner | Resultat returneret | fyr |
|---|---|---|
(read-char port) |
returnerer det næste tegn fra portport | Karakter |
(peek-char port) |
returnerer det næste tegn fra portporten (men flytter ikke markøren) | Karakter |
(read port) |
aflæses fra dørporten | blandet |
(eof-object port) |
er vi i slutningen af filen? | boolesk |
Bemærk: hvis portporten ikke er angivet på read-char og read, sker aflæsningen fra standardindgangen (aflæsning fra konsollen).
Skrivning af data
Dataskrivning, kaldet "outputoperationer", sker gennem følgende funktioner:
| Funktioner | Resultat returneret |
|---|---|
(write-char char port) |
skriver char-tegnet til portport |
(write obj port) |
skriv objekt obj til portport |
(display obj port) |
vis objektet gennem porten |
(newline port) |
skriver en tom linje på portporten |
Bemærk: hvis portporten ikke er angivet på skrive-char og skriv, foregår skrivningen på standardudgangen (skrivning på konsollen).
Definition af procedurer
Definition af en data
I Scheme foretages definitionen af en data af enhver type gennem funktionen define:
Definition af en numerisk værdi: (definer mit_nummer 3)
Definition af en streng: (definer min_streng "Hello World")
Definition af en liste: (definer min_liste (liste #T 6 2 # / G))
Derfor bruges define også til procedurer. Den enkleste måde at oprette en procedure, der tager en række argumenter, har følgende struktur:
(definer (min_procedure arg1 arg2 ... argN) ...)
Lambdafunktionen er tilgængelig i Scheme for at oprette unavngivne procedurer. Det giver os en alternativ måde at definere en procedure på, ved at skabe en anonym procedure og tildele den, som om det var en konventionel værdi, til en variabel.
Definition af en procedure ved hjælp af lambda-funktionen:
(definer min_procedure
(lambda (arg1 arg2 ... argN)
...))
Lambda tillader også definition af procedurer inden for andre procedurer.
Fundamental Constructs
Simpel betingelse (hvis)
Efter at have set typerne af data og funktionerne til at operere på dem, og efter at have forstået, hvordan man definerer en procedure, lad os gå videre til de grundlæggende konstruktioner.
If-konstruktionen ser sådan ud:
(hvis condition_expression_in_case_the_condition_er_true
any_expression_in_case_the_condition_is_ false)
; siger, hvis det leverede argument er lig med eller forskelligt fra 5
( definer ( test_if arg1 ) (
if ( = arg1 5 ) " det leverede argument er 5"
"det leverede argument er forskelligt fra 5" ))
Med andre ord kan vi sige, at Scheme's if også indeholder det andet af de andre programmeringssprog.
Sammensat tilstand (kond)
Det svarer til en kæde af multipler, hvis, og ser sådan ud:
(kond (første_betingelse udtryk) (anden_betingelse udtryk) ... (andet udtryk))
Der er et par ting at bemærke:
- andet er ikke obligatorisk: Hvis de angivne betingelser er udtømmende, det vil sige, at de dækker 100 % af de mulige tilfælde, kan det udelades. Tværtimod, i mangel af andet, i det tilfælde, hvor der ikke er opstået noget tilfælde, vil der blive genereret en Runtime- fejl .
- Det er en afledt funktion, der kan implementeres gennem hvis og begynde konstruktionen.
Betingelse baseret på den værdi, der returneres af et udtryk (case)
Det er et udtryk, der er underlagt en betingelse, hvis resultat afhænger af den værdi, som udtrykket selv antager. Mulige værdier er angivet i strukturen som val1, val2, val3:
(casusudtryk_som_er_vurderet ((val1) udtryk) ((val2) udtryk) ... (andet udtryk))
Som med vilkårskonstruktionen er den anden valgfri.
Udtryksblokke (begynd)
For at udtrykke en blok af udtryk i Scheme bruger vi startfunktionen:
(begynd første_udtryk
andet_udtryk
...
n-te_udtryk)
Dette giver dig mulighed for at specificere flere udtryk (dem, der er omgivet af start) på et punkt, hvor et enkelt udtryk er syntaktisk nødvendigt. Et typisk eksempel er i ifs.
En ikke-fundamental konstruktion (do)
Da det er et funktionelt sprog, ville det i Scheme være rart altid at kunne bruge if og rekursion . Så vidt det er muligt i teorien, hjælper denne løsning ikke altid på læsbarheden, og den giver heller ikke nødvendigvis anledning til den mest algoritmisk effektive eller naturlige løsning. Scheme giver derefter konstruktionen do, som giver dig mulighed for at udføre loops. I dette spiller do-konstruktionen en lignende rolle som for og mens for andre programmeringssprog.
Do kommer i mange former. Den første, der ligner mens-konstruktionen af java, er følgende:
(gør () (condition_of_exit, if any_expression_to_execute_before_the_exit) første_udtryk_af_ sløjfe andet_udtryk_af_ cyklus ... n-te_udtryk_af_ cyklus)
Se på udgangsbetingelsen: hvis det er sandt, evalueres følgende udtryk sekventielt (første_udtryk_af_cyklus, anden_udtryk_af_cyklus ... n-te_udtryk_af_cyklus). Udførelsen gentages derefter, med en ny kontrol af udgangstilstanden. Når dette mislykkes, udføres det (valgfrie) udtryk, der følger efter det, og derefter slutter løkken.
Den anden form ligner meget den generiske for konstruktioner:
(do ((variable_initial_value_of_variable_ update_expression)) (condition_of_exit, if any_expression_to_execute_before_the_exit) første_udtryk_af_ sløjfe andet_udtryk_af_ cyklus ... n-te_udtryk_af_ cyklus)
Variablen initialiseres til en bestemt værdi; ved hver efterfølgende iteration opdateres variablen ved at udføre update_expression, som kan omfatte en forøgelse eller reduktion af variablen, men også en mere generel operation. For hvert andet aspekt foregår udførelsen som i det foregående tilfælde, hvor dog exit_condition typisk er opfyldt i henhold til de værdier, der antages af cyklusvariablen.
; eksempel, der viser naturlige tal, der er lavere end variablen tal
( define ( test_do number )
( do (( index 0 ( + index 1 )))
(( > = index number ))
( display index )
( newline )
))
Programmering i skema
Som allerede nævnt er Scheme særligt velegnet til at udtrykke algoritmer i en rekursiv form .
Simpel rekursion opnås ved at kalde selve proceduren én gang. Antag for eksempel, at vi ikke har *-operatoren tilgængelig, og at vi ønsker at definere multiplikationen mellem heltal ved successive additioner. Da k * n svarer til k + k + ... + k, med k gentaget n gange, så kan vi skrive følgende kode:
( definer ( molt a b )
( hvis ( = a 0 ) 0
( + b ( molt ( - a 1 ) b ))))
I dette eksempel kaldes moltfunktionen i sin egen kode.
Hvordan virker rekursion? Antag, at vi har (molt 3 4): det forventede resultat er 3 * 4 = 12. Lad os se nærmere på strømmen af udførelse:
> (molt 3 4) [første iteration: rekursion] (+ 4 (molt (- 3 1) 4)) [anden iteration: rekursion] (+ 4 (+ 4 (molt (- 2 1) 4))) [tredje iteration: rekursion] (+ 4 (+ 4 (+ 4 (molt (- 1 1) 4)))) [fjerde iteration: vi er i den tilstand, hvor a er lig med 0, vi erstatter (molt 0 4) med 0] (+ 4 (+ 4 (+ 4 0))) [første opløsning] (+ 4 (+ 4 4)) [anden opløsning] (+ 4 8) [retur af resultat] 12
En anden type rekursion involverer en rekursion, der ved hver iteration kan foretage forskellige opkald, afhængigt af de forhold, der opstår. Lad os se et eksempel på dette ved hjælp af Fibonacci-sekvensen .
( definer ( fibonacci n )
( cond ( ( = n 1 ) 1 )
(( = n 2 ) 2 )
( else ( + ( fibonacci ( - n 1 )) ( fibonacci ( - n 2 ))))))
Selvom det er muligt at beskrive udførelsesflowet som ovenfor, vokser det meget hurtigt (se Computational Complexity Theory ), og vil derfor ikke blive rapporteret.
Forskellige programmeringseksempler i Scheme
Et eksempel på et program, der interagerer med brugeren:
( definer ( maxpot b n k ) ( hvis ( ikke ( > = n ( expt b k ))) ( sub1 k ) ( maxpot b n ( add1 k ))))
( definer b 0 )
( definer n 0 )
( citat "Nu vil den maksimale effekt blive beregnet for b ^ k <= n" )
( citat "Indsæt nu b:" )
( sæt! B ( læs ))
( citat "Indsæt nu n:" )
( sæt! N ( læs ) )
( if ( og ( > b 1 ) ( > n 0 ))
( string-append "Den maksimale effekt, der opfylder b ^ k <= ne:" ( tal-> streng ( maxpot b n 0 )))
( citat "E 'der opstod en fejl: du skal have sat b <= 1 og/eller n <= 0 " ))
Implementering af rundbords- (eller Cæsars) problem:
( definer ( aski s ) ; position i ASCII
( char-> heltal ( string-ref s 0 )))
( definer ( retro s ) ; fra ASCII til streng
( liste-> streng ( liste ( heltal-> tegn ) )))
( define ( dl s ) ; slet sidste "char"
( substring s 0 ( - ( string-length s ) 1 )))
( define ( sl s ) ; vælg sidste "char"
( substring s ( - ( string-length s ) s ) ) 1 ) ( strenglængde s )))
( definer ( lwc? s ) ( og ( > ( aski s ) 96 ) ( < ( aski s ) 123 ))) ; små bogstaver?
( definer ( upc? s ) ( og ( > ( aski s ) 64 ) ( < ( aski s ) 91 ))) ; store bogstaver?
( define ( modGC old n new ) ; modul gcesare
( define ( h s ) ( modGC ( dl old ) n ( string-append ( retro s ) new )) ; hovedapplikation hale-rekursion
; (aski (sl old)) er enhedskarakteren i tal, ville det være godt at omdøbe det !, med en let ch for eksempel, men hvor? samt (sl old) ...
; den anden og tredje betingelse skal kombineres til en, hvortil to skal ændres tegn..min (65 eller 97) og max (90 eller 122)
( cond (( string =? "" old ) new ) ; exit condition
(( og ( lwc? ( sl old )) ( > ( + n ( aski ( sl gammel ))) 122 )) ( h ( + 97 ( - ( sub1 n ) ( - 122 ( aski ( sl gammel ))))))) ; overførselsstyring
(( og ( upc? ( sl gammel ) ) ( > ( + n ( aski ( sl gammel ))) 90 )) ( h ( + 65 ( - ( sub1 n ) ( - 90 ( aski ( sl gammel )))))))
(( ikke ( eller ( lwc ? ( sl gammel )) ( upc? ( sl gammel )))) ( h ( aski ( sl gammel )))) ; undtagelser: tal, mellemrum osv.
( else ( h ( + n ( aski ( sl gammel )))) ))) ))))) ; vi er normale, alfabetet behøver ikke engang at starte fra begyndelsen
( define ( gcesare old n w ) ( if ( og ( < n 26 ) ( > n 0 ))
( cond (( string =? w "cod) " ) ( modGC old n "" )) (( string =? w "dec" ) ( modGC old ( - 26 n ) "" )) ( ellers "ugyldig mulighed, prøv igen med dec eller cod" ))
"n skal være et tal , mellem 0 og 26, ekstremer udelukket! " ))
Et mere komplekst eksempel, Tic Tac Toe-spillet (simpel ASCII-implementering):
( define n 0 ) ; input
( define ( slst? l ) ( if ( null? l ) #t ( if ( nummer? ( car l ))) #f ( slst? ( cdr l ))))) ; symbolsk liste ?
( define ( view l ) ( start ( display "Den aktuelle situation er følgende: \ n" ) ; Viewer ^ _ ^
( display ( cons ( car l ) ( cons ( cadr l ) ( list ( caddr l ))) ) ) ( newline )
( display ( cons ( cadddr l ) ( cons ( cadddr ( cdr l )) ( list ( cadddr ( cddr l ))))) ( newline )
( display ( cdddr ( cdddr l ))) ( newline ) ))
( define ( free? l e ) ( if ( null? l ) #f ( if ( not ( lig? ( car l ) e )) ( free? ( cdr l ) e ) #t )))
( define ( tr l e s ) ; find and replace
( if ( lig? ( car l ) e ) ( cons s ( cdr l ))
( cons ( car l ) ( tr ( cdr l ) e s ))))
( define ( win l wpos ) ( cond (( null? wpos ) #f ) ; vinderposition? -> gå for at vinde? ..
(( eqc? ( car wpos ) l ) #t )
( else ( win l ( cdr ) wpos )) )))
( define ( win? l ) ( win l ' (( 1 2 3 ) ( 4 5 6 ) ( 7 8 9 ) ( 1 4 7 ) ( 2 5 8 ) ( 3 6 9 ) ( 1 ) 5 9 ) ( 7 5 3 )))) ; vinderpositioner
( definer ( eqc? L1 l2 ) ( if ( null ? L1 ) #t ( if ( cc l2 ( bil l1 ))) ( eqc? ( Cdr l1 ) l2 ) #f ) )) ; elementerne i listen <l1> vises i li er <l2>? ( define ( cc l e ) ( if ( null? l ) #f ( if ( lig? ( car l ) e ) #t ( cc ( cdr l ) e ))) ) ; <e> er indeholdt i liste <l>? ( define ( wplay genlst plslst mnslst turn ) ( let (( wis ' ( vis "Player won:" ))) ( se genlst ) ( cond (( win? plslst ) ( eval wis ) ( vis "+" )) (( win? mnslst ) ( eval wis ) ( vis "-" )) (( slst? genlst ) ( vis "Uafgjort, ingen vandt!" )) ( else ( start ( vis "Indtast et tal, fra 1 til 9, det er din turn " ) ( display turn ) ( newline ) ( set! N ( read )) ( display " Du indtastede: " ) ( display n ) ( newline ) ( if ( nummer? N ) ( if ( < n 10 ) ( if ( free? genlst n ) [ if ( lig? turn '+ ) ( wplay ( tr genlst n ' + ) ( append plslst ( list n )) mnslst '- ) ( wplay ( tr genlst n ' - ) plslst ( append mnslst ( liste n )) '+ )] ( start ( vis "Det indtastede sted er besat \ n" ) ( wplay genlst plslst mnslst tur ))) ( start ( vis "Det indtastede sted er ikke-eksisterende \ n " ) ( wplay genlst plslst mnslst tur ))) ( start ( vis " Stedet er angivet med et tal fra 1 til 9 \ n " ) ( wplay genlst plslst mnslst tur ))))))) ( definer spil ( start ( vis "Spilstart, start +. \ n" ) ( wplay ( liste 1 2 3 4 5 6 7 8 9 ) ( liste '+ ) ( liste ' - ) '+ )))
Andre projekter
Wikimedia Commons indeholder billeder eller andre filer på Scheme
Eksterne links
Implementeringer
- ( EN ) Racket (dialekt af Scheme) inkluderer en fortolker og en Open Source Scheme-to-C compiler til alle operativsystemer
- ( EN ) Chez Scheme freeware fortolker til Microsoft Windows og Unix
- Kylling Scheme - til - C compiler
- ( EN ) Bigloo Scheme-to-C og Scheme-to-Java compiler
- ( EN ) Kawa Scheme-miljø skrevet i Java , som kompilerer Scheme-kode i Java-bytekode
Andre ressourcer
- ( EN ) En stor samling af ordningens ressourcer på schemers.org .
- ( EN ) Scheme Requests for Implementation (SRFI) , på srfi.schemers.org .
- ( EN ) Sådan designes programmer , på htdp.org .
- En bibliografi om ordningsrelateret forskning med links til mange akademiske artikler, herunder de originale Lambda Papers
