Introducere în schema

Ken Diki (traducere Alexei DESYATNIKOV)

O viziune alternativă a lumii

Fiecare limbaj de programare este definit în termeni de lume, care permite (sau nu permite) utilizarea. Această serie de articole descrie perspectiva asupra lumii Schemei limbaj de programare ( „lume schematică“). Această lume include multe elemente de programare moderne: sprijini diferite paradigme de programare ușor combinabile abstractii, reutilizabile, abilitatea de a crea limbajul „ascuțit“ sub o anumită aplicație, o distincție clară între părțile mobile și non-portabile ale programului, scalabilitate de la instrumentele individuale de software grave sisteme.

Schema a început ca un experiment în proiectarea limbaj de programare pentru a testa unele dintre dispozițiile de bază ale teoriei programării. Acum, ea devine locația multor universități celebre (cum ar fi MIT - Institutul Tehnic din Massachusetts), ca un prim limbaj de programare de a fi studiate. În plus, schema utilizată în industria de către companii precum decembrie Texas Instruments. Tektronix. Hewlett Packard și Sun.

Care este schema?

Conducerea - este un limbaj foarte mic, „pur“, care este (foarte important!) Distractiv de utilizat. Schema a fost proiectat astfel încât un număr mic de proiectare universal poate fi folosit cu ușurință în diferite stiluri de programare: funcțional, orientat-obiect și imperative. Standardul de limbă durează doar aproximativ 50 de pagini (!), Inclusiv definirea formală a semanticii. Sistemul se bazează pe un model formal al lambda-calcul, deci aici este plin de caracteristici, ușor de-teoreticieni; Acest lucru vă permite să construiască destul de ușor software-ul inteligent de dezvoltare a aplicațiilor.

Schema are un mecanism de definire a domeniului lexicale, norme uniforme de calcul și de înțelegere uniformă a tipurilor de date. Schema nu are nici un concept pointer, variabile neinițializate, structuri ciclice speciale sau de management detaliate de stocare.

Pe ce sistem similar? Ei bine, se pare ca o Lisp. Nu lasa ca sperie: scheme de aspect poate fi modificat (și prin aceasta vom face în viitor). Ceea ce contează cu adevărat este conceptele care stau la baza schemelor și posibilitatea de utilizare a acestora. Deci, să compare schema și unele limbaj de programare „clasic“ - de exemplu, Si. Poate că știți deja că circuitul utilizează notatia prefix, spre deosebire de infix C:

În schema, toate tipurile de date sunt echivalente. Tot ce se poate face cu un singur tip de date se poate face cu toate celelalte. Acest lucru este foarte diferit de cele mai multe limbaje de programare, care au operațiuni speciale pentru anumite tipuri de date, precum și utilizarea anumitor alte tipuri de date limitate în mod specific. În cele mai multe limbi, de exemplu, numere au drepturi speciale: ele pot fi utilizate fără a le atribui nume (imaginați-vă că, de exemplu, că în BASIC fiecare număr ar trebui să alocați un nume înainte de a utiliza!). Funcția, în schimb, sunt limitate: acestea trebuie să aibă un nume.

În schema, funcțiile fără un nume creat folosind lambda cuvinte cheie:

(Lambd a (x) (x * x)); Rezultatul - funcția!

(Definește sq (lambda (x) (x * x))

((Lambda (x) (x * x)) 9); 27

((If (foo x) * +) 2 3 4?); dacă (foo? x) este adevărată.

(Definiți (curried-add x) (lambda (y) (+ x y))

(Definirea add3 (curried-add 3)); add3 - funcția

((Curried-adaugă 3) 7); 10

- variabilă poate cuprinde orice tip de valoare;

- nume se referă la valori; Numele nu sunt necesare;

- Expresia - una sau mai multe forme între paranteze;

- în scopul de a evalua expresia, trebuie să calculeze mai întâi valoarea tuturor formelor între paranteze, și apoi se aplică valoarea primei forme pentru restul; expresii imbricate sunt de asemenea considerate forme;

- când funcția este calculată, ea „își amintește“ stare „mediu“, în care a fost creat (deci se adaugă 3 amintește că X este egal cu trei la începuturile sale, adică la momentul calculării expresiei (lambda (y) (+ xy)) 7)).

(Definește sq (lambda (x) (x * x))

Există șapte tipuri de expresii:

- constantă: "string" „foo # \ Z 3

- Proceduri de aplicare: (cube37)

- condiție. (În cazul în care (

(Desigur, această listă conține nu toate variantele de expresii)

Circuitul are un set obișnuit de tipuri de date:

- litere (caractere): # \ un # \ A \ #space # \ NEWLINE

- string (string): "șir de text"

- tablouri (vectori - vector): # (1 februarie "șir de caractere" # \ x5)

- liste (listă): (un pic (lista) (liste))

- Numărul (numerele): 47 1/3 2.3 4.3e14 1 + 3i

- valori logice (.. boolean adevărat și fals, respectiv): # t # f

- porturi (de exemplu, fișiere sau conexiuni de rețea deschise)

- simboluri (simboluri utilizate în mod obișnuit pentru a se referi la variabile.): aceasta-este-un-symbolfooa32> adfasf23 @ # $%!<

- vectorul poate fi compus din oricare dintre aceste obiecte;

- Simbolul poate conține litere ale alfabetului englezesc, numere și litere + -. * / <=>. $% _

- caractere care nu sunt sensibile la caz (de exemplu, simboluri SIMBOL și SIMBOLUL identice)

- Simbolurile sunt utilizate pentru a desemna variabile (dar nu numai!)

- prin acord (pentru comoditate) predicatele (expresii ale testului valori) de capăt într-un semn de întrebare, și „periculoase“ (modificarea valorii variabilei) funcționează se termină cu un semn de exclamare

Numerele sunt deosebit de interesante în schema: fiecare număr întreg (întreg) este o fracție (rațională), fracțiune - un număr real (real), precum și un număr real - complexul (complex). Numerele sunt clasificate pe baza preciziei (exactă sau aproximativă - exactă / inexactă):

Schema de Filosofie

Una dintre caracteristicile frumoase ale sistemului, care inițial multe confuz - nu există restricții. Schema este foarte expresiv: programator poate „vorbi“ limba de un gând (acțiune), în moduri complet diferite. În schema de programator are libertatea - și responsabilitatea - „vorbi“, exact așa cum vrea el. In multe alte limbaje de programare, uneori, trebuie să caute pentru unele „soluții“ pentru a le ajunge la dorit și în schema nu este pur și simplu necesar.

Pentru a „încălzi“ să construiască o structură de date „pereche» (pereche). Perechea este format din două elemente obținute prin intermediul funcțiilor de acces PRIMUL și AL DOILEA (primul și al doilea, respectiv). Funcția va fi numită PAIR împerechere. Următoarele relații trebuie să dețină: (prima (pair12)) este egal cu 1, (a doua (pair1 2)) este egal cu 2. Pentru cei care cunosc Lisp acest lucru nu este nimic neobișnuit. Cu toate acestea, cât de multe moduri diferite, putem pune în aplicare acest trio: PAIR. PRIMUL. A DOUA?

; puteți pur și simplu (defini vectorul PAIR). dar mai bine stilistic

(Definiți (împerechea un b) (vector a b))

(Definiți (FIRST aPair) (vector-ref aPair 0))

(Definiți (A DOUA aPair) (vector-ref aPair 1))

; 2. Funcțiile de alegere

; Nu uita domeniul de aplicare lexicale:

; fiecare funcție pentru a crea funcții PERECHE, va aminti

; valorile a și b în momentul în care

(Definiți (împerechea un b) (lambda (bool) (în cazul în care bool a b)))

(Definiți (FIRST aPair) (aPair #t))

(Definiți (A DOUA aPair) (aPair #F))

; 3. Schimb de mesaje

(Definiți (PAIR (a b)

(Cazul msg; caz de proiectare pentru fiecare msg valoare

; ia măsuri adecvate

((Întâi) a); în cazul în care mesajul - un simbol mai întâi.

; apostrof ( „) simbolul pentru a calcula valoarea interzice

; (Fără ar fi o greșeală „nu este variabilă“)

(Definiți (PRIMUL aPair) (aPair „mai întâi))

(Definiți (A DOUA aPair) (aPair „a doua))

; 4. Aliasuri: deja în schemă are un tip de date „pereche“!

(Definirea cons PAIR)

(Definiți prima mașină)

(Definiți A DOUA cdr)

; 5. funcții Lambda (funcții de transfer ca și ceilalți parametri

(Definiți (împerechea un b) (lambda (proc) (proc a b)))

(Definiți (FIRST aPair) (aPair (lambda (x y) x)))

(Definiți (A DOUA aPair) (aPair (lambda (x y) y)))

Punctul de toate cele de mai sus: chiar și cele mai simple lucruri se poate face în moduri foarte diferite.

Acum, că ne-am încălzit, să ne uităm la bun factorial vechi (amintiți-vă: factorialul - produsul tuturor numere întregi de la 1 la numărul dat).

Pentru a începe cu - definiția recursiv:

Când am (Ken Diki) a studiat prima definitie recursiva ca aceasta, cel mai dificil de înțeles modul în care o amprentă latentă funcții de stat sunt stocate pe stivă. conversie cod mic, ceea ce face stiva vizibil.

; Funcția de identitate se întoarce pur și simplu argumentul său

(Definiți (valoare de identitate) valoare)

; Salvați forma, fapt funcția

; (Acum doar cauzează funcția cfact)

(Definiți (fapt n) (n identitate cfact))

; O functie cfact - calculeaza factorialul

(Definiți (cfact n k)

(Lambda (rezultat) (k (* n rezultat))))))

cfact Funcția - versiunea funcția de fapt. Utilizați „continuarea“. În loc de a se întoarce rezultatul de fiecare dată când o funcție devine un argument în plus, o „continuare“, care se numește cu rezultatele funcției.

Să vedem cum se va transforma apelul (fact3):

(Fapt 3) devine (cfact 3 identitate)

(Cfact 3 identitate) devine

(Identitate (* 3 rezultat)))); k '

Aceasta, la rândul său, este convertit în

(Lambda (rezultat ') ;; k' '

(Identitate (* 3 rezultat))); Funcția k '

(* 2 rezultat „)); Argumentul a trecut la k '

((Lambda (rezultat ') ;; k' '

(Identitate (* 3 rezultat))) (* 2 rezultat „))

((Lambda (rezultat) (identitate (* 3 rezultat))) (* 02 ianuarie))

(Identitate (* 3 (* 2 1)))

Este - nu este un exemplu de modul în care lucrurile simple pot fi ușor de făcut teribil de complicat. De ce facem asta? Ideea că putem controla, care este de obicei ascuns în stivă. Acest lucru vă permite să faceți unele lucruri interesante. Putem ignora o „a continuat“ și în loc să folosească mai mult. Putem controla, de exemplu calcule, pe termen lung. În cazul în care durează mai mult decât era de așteptat, ne putem menține nostru a continuat ( „unde suntem“) și să încerce o abordare diferită pentru rezolvarea problemei. În cazul în care noua opțiune este mai rău, putem reveni la salvat „continua“ și să continue calculul. Desigur, ne putem menține eforturile noastre de a face mai bine în cazul în care, dacă într-adevăr obține o mai bună ...

Astfel, utilizarea de „continuare“ vă permite să construiască structuri foarte interesante și flexibile de control. Să ne uităm acum la factorialul cealaltă parte. Fiecare apel recursiv pur și simplu pune pe stiva este un alt factor. Dar nu putem folosi stiva, dacă vom introduce „baterie“ suplimentar peremennuyu-. Desigur, înainte de a calcula bateria trebuie să fie 1 (din x * 1 = x).

; Vom defini o funcție pentru a calcula o baterie

(Definiți (acc _n cfact)

(Cfact (- _n 1) (* _n acc))

; Noi numim această funcție cu o baterie de 1

Aparent, această caracteristică pare a fi recursive. Cu toate acestea, nu este. Schema are conceptul de „recursie coadă“, care elimină necesitatea ciclurilor convenționale. Fiecare funcție care se numește în poziția „coada“ (de exemplu, ca ultima acțiune) - este doar un ciclu.

Deci, am convertit o funcție recursivă într-o iterativ, ciclică. Sunt formale (teoretic „corectă“) calea acestei transformări; dar o caracteristică frumos a sistemului este că aceste schimbări sunt simple și intuitive. În mod corespunzător programele de lucru pot fi scrise rapid, chiar dacă la început, ei pot lucra încet și necesită o mulțime de memorie. După depanare algoritmul lor este ușor să se transforme într-o mult mai eficient - și, de asemenea, să funcționeze corect! Programe de transformare pentru programator cu experiență în Schema devine a doua natură.

Circuitul are mai multe avantaje importante față de alte limbi. elegant simplu, structura sa omogenă și sintaxa triviale evită diferite „ocazii speciale.“ Expresia ei face posibil să nu pierdeți timpul în căutarea workarounds: programator poate concentra pe ceea ce trebuie să facă, dar nu și cum să o facă. Schema suporta mai multe stiluri de programare, inclusiv astăzi șold, orientat-obiect, - astfel încât programatorul nu trebuie să se adapteze în cadrul schemei; el poate folosi stilul sau metoda de rezolvare a problemelor, care a folosit pentru a. Schema formală face dovada corectitudinii programelor mult mai ușor. abstractizare puternică vă permit să se separe părți ale programului, care pot fi reutilizate, în parte, „ascuțit“, în conformitate cu sistemul specific de limbă / operare problemă / implementare. Ușurința de a combina diferite funcții și de a crea pe baza lor de noi modele vă permite să creați biblioteci întregi sunt bine stabilite, componente universale.

Cu alte cuvinte, dacă doriți să scrie complexe, corectați programul, dar nu doresc să-și petreacă anii, planul - ceea ce ai nevoie pentru a reuși!

O listă scurtă de cea mai cunoscută a schemei.

Schema Chez și MacScheme - unele dintre cele mai bune implementari comerciale; Cu toate acestea, există multe compilatoare gratuite și scheme de interpreți pentru scopuri educaționale și de muncă serioasă.

Una dintre cele mai bune sisteme pentru Windows și Linux - MzScheme. și construit pe baza lui MrEd (sistem portabil pentru crearea de interfață grafică cu utilizatorul) și DrScheme (probabil, mediul de dezvoltare mai convenabil a celor existente).

Deci, aici este o listă parțială a schemei: