Sistem

Sistem limbaj de programare
Calculul simbolului Lambda
Autor	Guy L. Steele , Gerald Jay Sussman
Data de origine	1970
Ultima versiune	R7RS (2013)
Utilizare	Lingvistic
Paradigme	Funcțional , procedural , metaprogramare
Tastare	Puternic, dinamic
Extensii comune	.scm .ss
Influențată de	Lisp , ALGOL și MDL
Implementare referință
Site-ul web	www.scheme-reports.org/
Editați datele pe Wikidata · Manual

Scheme este un limbaj de programare funcțional , un dialect al lui Lisp, care păstrează toate caracteristicile, care a fost dezvoltat în anii 1970 de Guy L. Steele și Gerald Jay Sussman , care l-au introdus în mediul academic cu o serie de articole cunoscute sub numele de le Lambda Papers și în cartea Structura și interpretarea programelor de calculator , folosită de zeci de ani ca text în unele examene de științe ale informației. Managerul de desktop GNOME încorporează interpretul Scheme Guile .

Exemple de programe

Salut Lume

Următorul exemplu afișează textul „Hello world”.

 (Afișați „Hello World!”)
( linie nouă )

Câteva exemple mai complexe

Următorul exemplu calculează cel mai mare divizor comun al argumentelor numerice x și y.

 ( definiți ( mcd x y )
  ( cond (( = x y ) x )
        (( > x y ) ( mcd ( - x y ) y ))
        ( else ( gcd x ( - y x ))))))

Următorul exemplu este folosit pentru a inversa ordinea caracterelor dintr-un șir; de exemplu, din „abcdef” obținem „fedcba”.

 (Defini (sl w) (substring w (sub1 (string de lungime w)) (string de lungime w)))
(Defini (dl w) (subșir w 0 (sub1 (string de lungime w))))
( definiți ( reversem s w )
   ( if ( = ( string-length s ) 0 ) w
      ( reversem ( dl s ) ( string-append w ( sl s )))))

În schimb, acest lucru face același lucru ca și exemplul de mai sus, dar folosind unele funcții Scheme.

 ( definiți ( inversa s ) ( reversem s "" )) ; recursivitatea cozii
( definiți ( invers2 w )
  ( list-> șir ( invers ( șir-> listă w )))) ; standard

Această funcție este utilizată pentru a ști dacă un număr este prim:

 ( definiți ( primul? m n s )
  ( dacă ( = ( sub1 n ) s ) "este prim"
  ( În cazul în care (= 0 (rest n (ADD1 s))) (string-Adăugare "nu este prim, este divizibil cu:" (> string (numeric ADD1 s)))
      ( primul? m n ( add1 s ))))))
( definește ( primul? n ) ( primul? m n 1 ))

Schița programării în schemă

Spre deosebire de majoritatea celorlalte limbaje de programare, Scheme folosește o notație de prefix, care este o notație în care în loc să scrieți (2 + 3) scrieți (+ 2 3). Această notație se propagă la toate funcțiile, astfel încât dacă avem o funcție N-ary f, reprezentarea acesteia va fi (f argument1 argument2 ... argumentN).

Tipuri de date

Schema implementează toate tipurile de date fundamentale: booleeni, numere, caractere, șiruri, vectori. Cu toate acestea, include și tipuri speciale, inclusiv liste (perechi), porturi (fluxuri de date), simboluri și proceduri.

Pentru a recunoaște aceste tipuri de date, Scheme oferă anumite funcții al căror identificator are formatul "typeDiD?" care returnează adevăratul boolean dacă argumentul trecut este în formatul tipului de date. Iată un tabel rezumat:

Să vedem acum câteva detalii despre aceste tipuri de date.

Booleeni

Acestea sunt indicate prin caracterul hash și litera T (TRUE) pentru adevărat și F (FALSE) pentru fals. Deci #T este adevărat, în timp ce #F este fals.

Funcțiile pe booleeni sunt cele obișnuite:

Numeric

Constantele numerice sunt scrise conform regulilor uzuale. Sunt disponibile diferite tipuri de date numerice: numere pozitive și negative, numere cu virgule și numere în notație exponențială. Pentru a recunoaște la ce clasă de numere aparține o expresie numerică, puteți utiliza una dintre următoarele funcții, din nou desemnate printr-un identificator de semn de întrebare, care returnează o valoare booleană:

De asemenea, este posibil să specificați baza de numerotare folosind #fN, unde f este baza și N un număr:

1. dN nu este practic folosit niciodată, deoarece baza este zecimală în mod implicit.

Apoi, există următoarele funcții booleene (semn de întrebare) și conversie:

Pentru a clasifica în continuare numerele, de exemplu între pozitiv și negativ, sau par și impar, Scheme oferă următoarele primitive:

Evident, atunci, ca în majoritatea limbilor, sunt disponibili atât operatori aritmetici, cât și multe funcții matematice.

Personaje

În Schemă, caracterele sunt indicate cu un hash, urmat de o bară inversă și de caracterul care trebuie exprimat (fără bară inversă, ar exista ambiguitate între caracterele T și F și booleenii ADEVĂRAT și FALS).

Printre funcțiile relevante găsim:

Există, de asemenea, versiunea ci a acestor funcții, insensibilă la majuscule: avem deci char-ci =?, Char-ci <?, char-ci <=? Și așa mai departe.

Alte funcții care operează pe caractere sunt următoarele:

Siruri de caractere

Șirurile din schemă sunt reprezentate prin ghilimele duble (exemplu: „acesta este un șir”). Unele funcții pentru gestionarea șirurilor sunt următoarele:

În ceea ce privește caracterele, avem operatori de comparare a șirurilor, care sunt analogi cu cei pentru caractere. Principalele sunt enumerate mai jos și există, de asemenea, în versiunea string-ci (insensibilă la majuscule):

Liste

După cum sa specificat mai sus, listele reprezintă un anumit tip de date. La fel ca tablourile, ele reprezintă colecții ordonate de elemente; spre deosebire de tablouri, elementele pot fi eterogene (de diferite tipuri) și, de asemenea, nu pot fi indexate. Listele sunt realizate ca perechi: (2 3) reprezintă un exemplu de listă care este evident o pereche; dar și (2 3 4) este de fapt un cuplu, format din primul element (2) și de toate celelalte (3 4). La rândul său, elementul „toți ceilalți” este o pereche formată din primul său element (3) și de toți ceilalți (în acest caz doar 4). Lista este apoi descrisă foarte natural în termeni recursivi.

O listă poate conține orice tip de date, cum ar fi caractere, șiruri, booleeni și chiar alte liste (exemplu: "(2 3 (4 5))"); așa cum am menționat, pot conține și tipuri de date mixte (exemplu: "(# \ T 4 (4 #F (" șir ")))").

Cele două funcții fundamentale pentru acționarea pe liste se referă la definiția recursivă menționată mai sus: avem astfel funcția car , care returnează primul element și cdr , care returnează al doilea element (elementul „toți ceilalți”).

Principalele funcții pe care le oferă Scheme pentru liste sunt următoarele:

Observăm că în această listă există funcții agregate care corespund compoziției car și cdr: expresia (cdr (cdr lst)) poate fi scrisă mai succint ca cddr (lst), în timp ce (car (cdr lst)) este can sintetizează cu cadr (lst).

Schema prezintă apoi alte funcții compuse, dintre care unele simulează funcții pe vectori, iar altele conversia listei în vector și invers:

Funcțiile speciale care acționează pe liste sunt aplicarea, harta și pentru fiecare funcție:

Pentru a explica mai bine, să luăm un exemplu:

 > (definiți lst1 (lista 2 3 4 5 6))
> (aplicați + lst1)
>> 20
> (definiți lst2 (lista 1 2 3 4 5))
> (hartă + lst1 lst2)
>> (3 5 7 9 11)

Vectori

Vectorii sunt tablouri standard, adică sunt o structură care conține un singur tip de date. Ele sunt reprezentate ca liste cu un prefix hash, adică # (el1 el2 ... elN), unde el1 are index 0 și elN are index N-1.

Funcțiile pe care le oferă Scheme pentru gestionarea vectorilor sunt următoarele:

Ușile

Porturile sunt obiecte care reprezintă fluxuri de date. Numeroase funcții sunt disponibile pe porturi, printre care găsim citirea / scrierea de la intrarea / ieșirea standard (citirea / scrierea caracterelor de la / către terminal, similar cu funcțiile printf și scanf în limbajul C) și gestionarea fișierelor. Porturile pot fi deschise în intrare (citirea datelor) și în ieșire (scrierea datelor).

Unele dintre funcțiile oferite de schemă sunt următoarele:

Citirea datelor

Citirile de date, numite „operații de intrare”, au loc prin următoarele funcții:

Notă: dacă portul portului nu este specificat pe read-char și read, citirea are loc de la intrarea standard (citirea de pe consolă).

Scrierea datelor

Scrierile de date, numite „operații de ieșire”, au loc prin următoarele funcții:

Notă: dacă portul portului nu este specificat pe write-char și write, scrierea are loc pe ieșirea standard (scriere pe consolă).

Definiția procedurilor

Definiția unei date

În Scheme, definiția datelor de orice tip se face prin funcția de definire:

 Definiția unei valori numerice:
(definiți numărul meu 3)

Definiția unui șir:
(definiți șirul_meu „Hello World”)

Definiția unei liste:
(definiți lista_meu (lista # T 6 2 # / G))

Prin urmare, define este folosit și pentru proceduri. Cea mai simplă modalitate de a crea o procedură care acceptă mai multe argumente are următoarea structură:

 (definește (procedura mea_arg1 arg2 ... argN)
  ...)

Funcția lambda este disponibilă în Scheme pentru a crea proceduri nenumite. Ne oferă o modalitate alternativă de a defini o procedură, prin crearea unei proceduri anonime și atribuirea acesteia, ca și cum ar fi o valoare convențională, unei variabile.

Definiția unei proceduri, utilizând funcția lambda:

 (definiți_procedura mea
  (lambda (arg1 arg2 ... argN)
    ...))

Lambda permite, de asemenea, definirea procedurilor în cadrul altor proceduri.

Construcții fundamentale

Stare simplă (dacă)

După ce am văzut tipurile de date și funcțiile pentru a le opera și după ce am înțeles cum să definim o procedură, să trecem la constructele fundamentale.

Construcția if arată astfel:

 (dacă condiția_expresie_în_caz_ condiția_este_adevărată
               event_expression_in_case_the_condition_is_ false)

; spune dacă argumentul dat este egal sau diferit de 5
( definește ( test_if arg1 )
  ( dacă ( = arg1 5 ) "argumentul dat este 5"
                 „argumentul furnizat este diferit de 5” ))

Cu alte cuvinte, s-ar putea spune că Scheme's conține și celelalte limbaje de programare.

Stare compusă (cond)

Este echivalent cu un lanț de multipli dacă și arată astfel:

 (cond
  (expresie first_condition)
  (a doua expresie condiție)
  ...
  (altfel expresie))

Există câteva lucruri de remarcat:

1. celălalt nu este obligatoriu: dacă condițiile specificate sunt exhaustive, adică acoperă 100% din cazurile posibile, acesta poate fi omis. Dimpotrivă, în absența altcuiva, în cazul în care nu s-a produs niciun caz, va fi generată o eroare de rulare .
2. Este o funcție derivată, implementabilă prin construcția if și begin.

Condiție bazată pe valoarea returnată de o expresie (caz)

Este o expresie supusă unei condiții, al cărei rezultat depinde de valoarea asumată de expresia însăși. Valorile posibile sunt specificate în structură ca val1, val2, val3:

 (expresie de caz_care_este_evaluată
  ((val1) expresie)
  ((val2) expresie)
  ...
  (altfel expresie))

Ca și în cazul construcției cond, celălalt este opțional.

Blocuri de expresie (începe)

Pentru a exprima un bloc de expresii în Schemă, folosim funcția begin:

 (începe first_expression
       a doua_expresie
       ...
       n-a_expresie)

Acest lucru vă permite să specificați mai multe expresii (cele cuprinse de begin) într-un punct în care o singură expresie este necesară din punct de vedere sintactic. Un exemplu tipic este în ifs.

Un construct non-fundamental (a face)

Fiind un limbaj funcțional, în Scheme ar fi frumos să puteți folosi întotdeauna dacă și recursivitate . În măsura în care este posibil în teorie, această soluție nu ajută întotdeauna la lizibilitate și nici nu dă naștere neapărat la soluția algoritmică cea mai eficientă sau naturală. Schema oferă apoi constructul do, care vă permite să executați bucle. În acest sens, constructul do joacă un rol similar cu pentru și în timp ce altor limbaje de programare.

Do vine în multe forme. Primul, care arată ca construcția while a java, este următorul:

 (face ()
  (condition_of_exit, dacă există_expresie_pentru_executare_înainte_exitarea)
  first_expression_of_ loop
  a doua_expresie_de_ ciclu
  ...
  n-a_expresia_ciclului)

Uită-te la condiția de ieșire: dacă este adevărată, următoarele expresii sunt evaluate secvențial (prima_expresie_de_ ciclu, a doua_expresie_de_ ciclu ... n-a_expresie_de_ ciclu). Execuția este apoi iterată, cu o nouă verificare a condiției de ieșire. Când acest lucru eșuează, expresia (opțională) care urmează este executată, iar apoi bucla se termină.

A doua formă seamănă mult cu genericul pentru constructe:

 (faceți ((variabilă_initială_valoră_de_expresie_actualizare_variabilă))
  (condition_of_exit, dacă există_expresie_pentru_executare_înainte_exitarea)
  first_expression_of_ loop
  a doua_expresie_de_ ciclu
  ...
  n-a_expresia_ciclului)

Variabila este inițializată la o anumită valoare; la fiecare iterație ulterioară, variabila este actualizată prin executarea update_expression, care poate include o creștere sau scădere a variabilei, dar și o operație mai generală. Pentru orice alt aspect, execuția are loc ca în cazul anterior, unde totuși condiția exit_ este îndeplinită în mod obișnuit în funcție de valorile asumate de variabila de ciclu.

 ; exemplu care afișează numere naturale mai mici decât numărul variabil
( definește ( test_do number )
( faceți (( index 0 ( + index 1 )))
    (( > = număr index ))
    ( afișare index )
    ( linie nouă )
)))

Program în schemă

După cum sa menționat deja, Schema este adecvată în special pentru exprimarea algoritmilor într-o formă recursivă .

Recursivitatea simplă se realizează apelând procedura în sine o singură dată. De exemplu, să presupunem că operatorul * nu este disponibil și că dorim să definim multiplicarea între numere întregi prin adunări succesive. Deoarece k * n este echivalent cu k + k + ... + k, cu k repetat de n ori, atunci putem scrie următorul cod:

 ( defini ( molt a b )
  ( dacă ( = a 0 ) 0
   ( + b ( molt ( - a 1 ) b ))))

În acest exemplu, funcția molt este numită în propriul cod.

Cum funcționează recursivitatea? Să presupunem că avem (molt 3 4): rezultatul așteptat este 3 * 4 = 12. Să aruncăm o privire mai atentă asupra fluxului de execuție:

 > (molt 3 4)
[prima iterație: recursivitate]
  (+ 4 (molt (- 3 1) 4))
[a doua iterație: recursivitate]
  (+ 4 (+ 4 (molt (- 2 1) 4)))
[a treia iterație: recursivitate]
  (+ 4 (+ 4 (+ 4 (molt (- 1 1) 4))))
[a patra iterație: suntem în condiția în care a este egal cu 0, înlocuim (molt 0 4) cu 0]
  (+ 4 (+ 4 (+ 4 0)))
[prima rezoluție]
  (+ 4 (+ 4 4))
[a doua rezoluție]
  (+ 4 8)
[returnarea rezultatului]
  12

Un al doilea tip de recursivitate implică o recursivitate care la fiecare iterație poate efectua apeluri diferite, în funcție de condițiile care apar. Să vedem un exemplu folosind secvența Fibonacci .

 ( definiți ( fibonacci n )
  ( cond (( = n 1 ) 1 )
        (( = n 2 ) 2 )
        ( else ( + ( Fibonacci ( - n 1 )) ( Fibonacci ( - n 2 ))))))

Deși este posibil să se descrie fluxul de execuție ca mai sus, acesta crește foarte repede (vezi Teoria complexității computaționale ) și, prin urmare, nu va fi raportat.

Diverse exemple de programare în Scheme

Un exemplu de program care interacționează cu utilizatorul:

 (Define (maxpot b n k) ( în cazul în care (nu (> = n (Expt b k))) (sub1 k) (maxpot b n (ADD1 k))))
( definiți b 0 )
( definiți n 0 )
( citați „Acum puterea maximă va fi calculată pentru b ^ k <= n” )
( citați „Inserați acum b:” )
( set! b ( citire ))
( citați „Inserați acum n:” )
( set! n ( citit ))
( dacă ( și ( > b 1 ) ( > n 0 )) 
(String-append "Puterea maximă care satisface b ^ k <= ne:" (numeric și > string (maxpot b n 0)))
( citat "A apărut o eroare: trebuie să fi setat b <= 1 și / sau n <= 0" ))

Implementarea problemei mesei rotunde (sau a lui Caesar):

 ( definiți ( aski s ) ; poziția în ASCII
  ( char-> întreg ( șir-ref s 0 )))

(Defini (spate e) din ASCII în șir
  ( list- > string ( list ( integer-> char s ))))

( definiți ( dl s ) ; ștergeți ultimul "char"
  (Substring s 0 (- (string lungime s) 1)))
( definiți ( sl s ) ; selectați ultimul „char”
  ( substring s ( - ( string-length s ) 1 ) ( string-length s )))

( definește ( lwc? s ) ( și ( > ( aski s ) 96 ) ( < ( aski s ) 123 ))) ; minuscule?
( definiți ( upc? s ) ( și ( > ( aski s ) 64 ) ( < ( aski s ) 91 ))) ; majuscule?

( define ( modGC vechi n nou ) ; modul gcesare
( define ( h s ) ( modGC ( dl old ) n ( string-append ( back s ) new )))) ;
; (aski (sl old)) este unitatea de caractere în număr, ar fi bine să o redenumiți!, cu un let ch de exemplu, dar unde? precum și (sl vechi) ...
; a doua și a treia condiție ar trebui combinate într-una la care trebuie schimbate două caractere..min (65 sau 97) și maxim (90 sau 122)
          ( cond (( string =? "" old ) new ) ; condiție de ieșire
                (( și ( lwc? ( sl vechi )) ( > ( + n ( aski ( sl vechi ))) 122 )) ( h ( + 97 ( - ( sub1 n ) ( - 122 ( aski ( sl vechi )))) ))) ; managementul reportării
                (( și ( upc? ( sl vechi )) ( > ( + n ( aski ( sl vechi ))) 90 )) ( h ( + 65 ( - ( sub1 n ) ( - 90 ( aski ( sl vechi )))) )))
                (( nu ( sau ( lwc? ( sl vechi )) ( upc? ( sl vechi )))) ( h ( aski ( sl vechi ))))) ; excepții: numere, spațiu alb etc.
                ( else ( h ( + n ( aski ( sl old )))))))) ; suntem în normalitate, alfabetul nici nu trebuie să înceapă de la început
( definiți ( gcesare vechi n w ) ( dacă ( și ( < n 26 ) ( > n 0 ))
    ( cond (( șir =? w "cod" ) ( modGC vechi n "" )) (( șir =? w "dec" ) ( modGC vechi ( - 26 n ) "" )) ( altfel "opțiune nevalidă, încercați din nou cu dec sau cod " ))
 "n trebuie să fie un număr, între 0 și 26, extreme excluse!" )))

Un exemplu mai complex, jocul Tic Tac Toe (implementare simplă ASCII):

 ( definiți n 0 ) ; intrare
( define ( slst? l ) ( if ( nul? l ) #t ( if ( number? ( car l )) #f ( slst? ( cdr l ))))) ; listă simbolică?
( definiți ( vizualizați l ) ( începeți ( afișați "Situația curentă este următoarea: \ n" ) ; Vizualizator ^ _ ^
                         ( afișaj ( contra ( mașină l ) ( contra ( cadr l ) ( listă ( caddr l ))))) ( linie nouă )
                         ( afișare ( contra ( cadddr l ) ( contra ( cadddr ( cdr l )) ( listă ( cadddr ( cddr l )))))) ( newline )
                         ( afișaj ( cdddr ( cdddr l ))) ( linie nouă )))
( definiți ( gratuit? l e ) ( dacă ( nul? l ) #f ( dacă ( nu ( egal? ( mașina l ) e )) ( gratuit? ( cdr l ) e ) #t )))
( definiți ( tr l și s ) ; găsiți și înlocuiți
    ( if ( egal? ( car l ) e ) ( contra s ( cdr l ))
        ( contra ( car l ) ( tr ( cdr l ) e s ))))
( define ( win l wpos ) ( cond (( null? wpos ) #f ) ; poziția câștigătoare? -> mergi să câștigi? ..
                           (( eqc? ( auto wpos ) l ) #t )
                           ( altfel ( câștiga 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 )))) ; poziții câștigătoare
( definește ( eqc? l1 l2 ) ( if ( nul? l1 ) #t ( if ( cc l2 ( car l1 )) ( eqc? ( cdr l1 ) l2 ) #f ))) ; elementele listei <l1> apar în listă <l2>?
( definește ( cc l e ) ( if ( nul? l ) #f ( if ( egal? ( car l ) e ) #t ( cc ( cdr l ) e )))) ; <e> este conținut în listă < eu>?
( definiți ( wplay genlst plslst mnslst turn )
( let (( wis ' ( afișează „Jucătorul câștigat:” ))) 
( vezi genlst )
  ( cond (( win? plslst ) ( eval wis ) ( display "+" ))
        (( win? mnslst ) ( eval wis ) ( afișează "-" ))
        (( slst? genlst ) ( afișați „ Remiză , nimeni nu a câștigat!” ))
        ( altfel ( începeți ( afișați „Introduceți un număr, de la 1 la 9, este rândul vostru” ) ( afișați rândul ) ( linie nouă )
                (Set! N (citit)) (afișați „Ați introdus:”) (Fără afișaj) (linie nouă)
                ( dacă ( număr? n )
                    ( dacă ( < n 10 ) 
                       ( dacă ( gratuit? genlst n )
                         [ if ( equal? turn '+ ) ( wplay ( tr genlst n ' + ) ( append plslst ( list n )) mnslst '- )
                                              ( wplay ( tr genlst n '- ) plslst ( append mnslst ( list n )) ' + )]
                        ( începeți ( afișați „Locul introdus este ocupat \ n" ) ( wplay genlst plslst mnslst turn )))
                      ( începe ( afișează „Locul introdus nu există \ n” ) ( wplay genlst plslst mnslst turn )))
                 ( începeți ( afișați „Locul este indicat printr-un număr de la 1 la 9 \ n" ) ( wplay genlst plslst mnslst turn ))))))))
( definiți jocul ( începeți ( afișați „Jocul începe, începe +. \ n” )) ( wplay ( lista 1 2 3 4 5 6 7 8 9 ) ( lista '+ ) ( lista ' - ) '+ )))

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere pe Scheme

linkuri externe

Implementări

• ( EN ) Interpretor Drscheme Open Source pentru toate sistemele de operare
• ( EN ) Interpret gratuit pentru Chez Scheme pentru Microsoft Windows și Unix
• ( EN ) Compilator Scheme-to-C de pui
• ( EN ) Bigloo Scheme-to-C și Scheme-to-Java compilator
• ( EN ) Mediul Kawa Scheme scris în Java , care compilează codul Scheme în bytecode Java

Alte resurse

• ( RO ) O mare colecție de resurse ale schemei , pe schemers.org .
• ( EN ) Scheme Cereri de implementare (SRFI) , la srfi.schemers.org .
• ( RO ) Cum se proiectează programe , pe htdp.org .
• (EN) O bibliografie privind cercetările legate de schemă , cu legături către multe articole academice, inclusiv lucrări originale Lambda

Portal IT : accesați intrările Wikipedia care se ocupă cu IT