Schema (linguaggio di programmazione) - Scheme (programming language)

schema

Paradigmi	Multiparadigma : funzionale , imperativo , meta
Famiglia	Lisp
Progettato da	Guy L. Steele e Gerald Jay Sussman
Apparso per la prima volta	1975 ; 46 anni fa ( 1975 )
Rilascio stabile	R7RS/2013 ; 8 anni fa ( 2013 )
Disciplina di digitazione	Dinamico , latente , forte
Scopo	Lessicale
Estensioni dei nomi dei file	.scm, .ss
Sito web	www .scheme-reports .org
Principali implementazioni
Molti (vedi Implementazioni dello schema )
Influenzato da
ALGOL , Lisp , MDL
influenzato
Clojure , Common Lisp , Dylan , EuLisp , Haskell , Hop , JavaScript , Julia , Lua , MultiLisp , R , Racket , Ruby , Rust , S , Scala , T
Schema su Wikibooks

Scheme è un dialetto minimalista della famiglia di linguaggi di programmazione Lisp . Lo schema consiste in un piccolo nucleo standard con diversi strumenti per l'estensione del linguaggio.

Scheme è stato creato negli anni '70 presso il MIT AI Lab e rilasciato dai suoi sviluppatori, Guy L. Steele e Gerald Jay Sussman , tramite una serie di promemoria ora noti come Lambda Papers . È stato il primo dialetto di Lisp a scegliere l'ambito lessicale e il primo a richiedere implementazioni per eseguire l' ottimizzazione delle chiamate di coda , fornendo un supporto più forte per la programmazione funzionale e le tecniche associate come gli algoritmi ricorsivi. È stato anche uno dei primi linguaggi di programmazione a supportare continuazioni di prima classe . Ha avuto un'influenza significativa sullo sforzo che ha portato allo sviluppo di Common Lisp .

Il linguaggio Scheme è standardizzato nello standard ufficiale IEEE e in uno standard de facto chiamato Revised ⁿ Report on the Algorithmic Language Scheme (R n RS). Lo standard più ampiamente implementato è R5RS (1998). Lo standard più recente, R7RS, fornisce versioni "piccole" e "grandi" del linguaggio Scheme; lo standard linguistico "piccolo" è stato ratificato nel 2013. Scheme ha una base di utenti diversificata grazie alla sua compattezza ed eleganza, ma la sua filosofia minimalista ha anche causato ampie divergenze tra le implementazioni pratiche, tanto che lo Scheme Steering Committee lo definisce "il più linguaggio di programmazione unportable" e "una famiglia di dialetti" piuttosto che un singolo linguaggio.

Storia

Origini

Scheme è iniziato negli anni '70 come un tentativo di comprendere il modello di attore di Carl Hewitt , per il quale Steele e Sussman hanno scritto un "piccolo interprete Lisp" usando Maclisp e poi "hanno aggiunto meccanismi per creare attori e inviare messaggi". Scheme era originariamente chiamato "Schemer", nella tradizione di altre lingue derivate dal Lisp come Planner o Conniver . Il nome attuale derivava dall'uso da parte degli autori del sistema operativo ITS , che limitava i nomi dei file a due componenti di un massimo di sei caratteri ciascuno. Attualmente, "Schemer" è comunemente usato per riferirsi a un programmatore di Scheme.

R6RS

Un nuovo processo di standardizzazione del linguaggio è iniziato durante il workshop Scheme del 2003, con l'obiettivo di produrre uno standard R6RS nel 2006. Questo processo ha rotto con il precedente approccio R n RS dell'unanimità.

R6RS dispone di un sistema di moduli standard, che consente una suddivisione tra il linguaggio principale e le librerie. Sono state rilasciate una serie di bozze della specifica R6RS, la versione finale è la R5.97RS. Un voto positivo ha portato alla ratifica del nuovo standard, annunciato il 28 agosto 2007.

Attualmente le versioni più recenti di varie implementazioni di Scheme supportano lo standard R6RS. Esiste un'implementazione di riferimento portabile delle librerie proposte in fasi implicite per R6RS, chiamata psyntax, che si carica e si avvia correttamente su varie precedenti implementazioni di Scheme.

Una caratteristica di R6RS è il descrittore del tipo di record (RTD). Quando viene creato e utilizzato un RTD, la rappresentazione del tipo di record può mostrare il layout della memoria. Ha anche calcolato la maschera di bit del campo oggetto e le maschere di bit del campo oggetto dello schema mutabile e ha aiutato il raccoglitore di rifiuti a sapere cosa fare con i campi senza attraversare l'intero elenco dei campi salvati nell'RTD. RTD consente agli utenti di espandere l'RTD di base per creare un nuovo sistema di registrazione.

R6RS introduce numerose modifiche significative alla lingua. Il codice sorgente è ora specificato in Unicode e un ampio sottoinsieme di caratteri Unicode può ora apparire in Simboli e identificatori dello schema e ci sono altre modifiche minori alle regole lessicali. I dati sui caratteri sono ora specificati anche in Unicode. Molte procedure standard sono state spostate nelle nuove librerie standard, che a loro volta costituiscono una grande espansione dello standard, contenenti procedure e forme sintattiche che in precedenza non facevano parte dello standard. È stato introdotto un nuovo sistema di moduli e i sistemi per la gestione delle eccezioni sono ora standardizzati. Syntax-regole è stato sostituito con una struttura di astrazione sintattica più espressiva (syntax-case) che consente l'uso di tutto Scheme al momento dell'espansione macro. Sono ora necessarie implementazioni conformi per supportare la torre numerica completa di Scheme e la semantica dei numeri è stata ampliata, principalmente nella direzione del supporto per lo standard IEEE 754 per la rappresentazione numerica in virgola mobile.

R7RS

Lo standard R6RS ha causato polemiche perché si è visto che si è allontanato dalla filosofia minimalista. Nell'agosto 2009, lo Scheme Steering Committee, che sovrintende al processo di standardizzazione, ha annunciato l'intenzione di raccomandare di dividere Scheme in due lingue: un grande linguaggio di programmazione moderno per programmatori; e una versione piccola, un sottoinsieme della versione grande che conserva il minimalismo elogiato da educatori e implementatori casuali. Sono stati creati due gruppi di lavoro per lavorare su queste due nuove versioni di Scheme. Il sito Scheme Reports Process contiene collegamenti agli statuti dei gruppi di lavoro, alle discussioni pubbliche e al sistema di monitoraggio dei problemi.

La nona bozza di R7RS (piccolo linguaggio) è stata resa disponibile il 15 aprile 2013. Una votazione di ratifica di questa bozza si è conclusa il 20 maggio 2013, e la relazione finale è disponibile dal 6 agosto 2013, descrivendo "il "piccolo" linguaggio di quello sforzo: quindi non può essere considerato isolatamente come il successore di R6RS".

Caratteristiche distintive

Scheme è principalmente un linguaggio di programmazione funzionale . Condivide molte caratteristiche con altri membri della famiglia dei linguaggi di programmazione Lisp. La sintassi molto semplice di Scheme si basa su s-expressions , elenchi tra parentesi in cui un operatore prefisso è seguito dai suoi argomenti. I programmi schema sono quindi costituiti da sequenze di elenchi annidati. Le liste sono anche la principale struttura di dati in Scheme, portando a una stretta equivalenza tra codice sorgente e formati di dati ( omoiconicità ). I programmi Scheme possono creare e valutare facilmente parti di codice Scheme in modo dinamico.

La dipendenza dalle liste come strutture dati è condivisa da tutti i dialetti Lisp. Scheme eredita un ricco set di primitive di elaborazione delle liste come cons, carecdr dai suoi progenitori Lisp. Scheme utilizza variabili rigorosamente ma tipizzate dinamicamente e supporta procedure di prima classe . Pertanto, le procedure possono essere assegnate come valori alle variabili o passate come argomenti alle procedure.

Questa sezione si concentra principalmente sulle caratteristiche innovative del linguaggio, comprese quelle caratteristiche che distinguono Scheme dagli altri Lisps. Salvo diversa indicazione, le descrizioni delle funzioni si riferiscono allo standard R5RS.

Negli esempi forniti in questa sezione, la notazione "===> risultato" viene utilizzata per indicare il risultato della valutazione dell'espressione sulla riga immediatamente precedente. Questa è la stessa convenzione utilizzata in R5RS.

Caratteristiche fondamentali del design

Questa sottosezione descrive quelle caratteristiche di Scheme che lo hanno distinto dagli altri linguaggi di programmazione fin dai suoi primi giorni. Questi sono gli aspetti di Scheme che influenzano maggiormente qualsiasi prodotto del linguaggio Scheme, e sono gli aspetti che tutte le versioni del linguaggio di programmazione Scheme, dal 1973 in poi, condividono.

minimalismo

Scheme è un linguaggio molto semplice, molto più facile da implementare rispetto a molti altri linguaggi di pari potenza espressiva . Questa facilità è attribuibile all'uso del lambda calcolo per derivare gran parte della sintassi del linguaggio da forme più primitive. Ad esempio dei 23 costrutti sintattici basati sull'espressione s definiti nello standard R5RS Scheme, 14 sono classificati come forme derivate o di libreria, che possono essere scritte come macro che coinvolgono forme più fondamentali, principalmente lambda. Come dice R5RS (§3.1): "Il più fondamentale dei costrutti di associazione variabile è l'espressione lambda, perché tutti gli altri costrutti di associazione variabile possono essere spiegati in termini di espressioni lambda."

Forme fondamentali : define, lambda, quote, if, define-syntax, let-syntax, letrec-syntax, syntax-rules, set!

Forme derivate : do, let, let*, letrec, cond, case, and, or, begin, named let, delay, unquote, unquote-splicing, quasiquote

Esempio: una macro da implementare letcome espressione utilizzando lambdaper eseguire i binding delle variabili.

(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))))

Pertanto, l'utilizzo di letun'implementazione dello schema come definito sopra riscrive " (let ((a 1)(b 2)) (+ b a))" come " ((lambda (a b) (+ b a)) 1 2)", il che riduce il compito dell'implementazione a quello di codificare le istanze della procedura.

Nel 1998, Sussman e Steele hanno osservato che il minimalismo di Scheme non era un obiettivo di progettazione consapevole, ma piuttosto il risultato non intenzionale del processo di progettazione. "In realtà stavamo cercando di costruire qualcosa di complicato e abbiamo scoperto, casualmente, che avevamo accidentalmente progettato qualcosa che soddisfaceva tutti i nostri obiettivi ma era molto più semplice di quanto avessimo previsto... ci siamo resi conto che il lambda calcolo - un piccolo, semplice formalismo - potrebbe fungere da nucleo di un linguaggio di programmazione potente ed espressivo."

Ambito lessicale

Come la maggior parte dei linguaggi di programmazione moderni e a differenza dei Lisp precedenti come Maclisp , Scheme è lessicalmente scoperti: tutti i possibili collegamenti alle variabili in un'unità di programma possono essere analizzati leggendo il testo dell'unità di programma senza considerare i contesti in cui può essere chiamato. Ciò contrasta con lo scoping dinamico che era caratteristico dei primi dialetti Lisp, a causa dei costi di elaborazione associati ai metodi di sostituzione testuale primitivi utilizzati per implementare algoritmi di scoping lessicale nei compilatori e interpreti dell'epoca. In quei Lisps, era perfettamente possibile che un riferimento a una variabile libera all'interno di una procedura si riferisse a binding ben distinti esterni alla procedura, a seconda del contesto della chiamata.

L'impulso a incorporare lo scoping lessicale, che era un modello di scoping insolito nei primi anni '70, nella loro nuova versione di Lisp, venne dagli studi di Sussman su ALGOL . Ha suggerito che i meccanismi di scoping lessicale simili ad ALGOL avrebbero aiutato a realizzare il loro obiettivo iniziale di implementare il modello Actor di Hewitt in Lisp.

Le intuizioni chiave su come introdurre lo scoping lessicale in un dialetto Lisp sono state rese popolari nel Lambda Paper di Sussman e Steele del 1975, "Scheme: An Interpreter for Extended Lambda Calculus", dove hanno adottato il concetto di chiusura lessicale (a pagina 21), che era stata descritta in un AI Memo nel 1970 da Joel Moses , che attribuì l'idea a Peter J. Landin .

Lambda calcolo

La notazione matematica di Alonzo Church , il lambda calcolo, ha ispirato l'uso di "lambda" da parte di Lisp come parola chiave per introdurre una procedura, oltre a influenzare lo sviluppo di tecniche di programmazione funzionale che comportano l'uso di funzioni di ordine superiore in Lisp. Ma i primi Lisps non erano espressioni adatte del lambda calcolo a causa del loro trattamento delle variabili libere .

Un sistema lambda formale ha assiomi e una regola di calcolo completa. È utile per l'analisi utilizzando la logica e gli strumenti matematici. In questo sistema, il calcolo può essere visto come una detrazione direzionale. La sintassi del lambda calcolo segue le espressioni ricorsive di x, y, z, ..., parentesi, spazi, il punto e il simbolo . La funzione del calcolo lambda include: Primo, servire come punto di partenza di una potente logica matematica. In secondo luogo, può ridurre l'esigenza dei programmatori di considerare i dettagli di implementazione, poiché può essere utilizzato per imitare la valutazione della macchina. Infine, il calcolo lambda ha creato una meta-teoria sostanziale.

L'introduzione dell'ambito lessicale ha risolto il problema facendo un'equivalenza tra alcune forme di notazione lambda e la loro espressione pratica in un linguaggio di programmazione funzionante. Sussman e Steele hanno mostrato che il nuovo linguaggio potrebbe essere usato per derivare elegantemente tutta la semantica imperativa e dichiarativa di altri linguaggi di programmazione inclusi ALGOL e Fortran e l'ambito dinamico di altri Lisps, utilizzando espressioni lambda non come semplici istanze di procedura ma come "controllo strutture e modificatori ambientali". Hanno introdotto lo stile di continuazione insieme alla loro prima descrizione dello Schema nel primo dei Lambda Papers, e nei documenti successivi hanno proceduto a dimostrare la potenza grezza di questo uso pratico del lambda calcolo.

Struttura a blocchi

Scheme eredita la sua struttura a blocchi dai precedenti linguaggi strutturati a blocchi, in particolare ALGOL . In Scheme, i blocchi sono implementati da tre costrutti di associazione : let, let*e letrec. Ad esempio, il seguente costrutto crea un blocco in cui un simbolo chiamato varè legato al numero 10:

(define var "goose")
;; Any reference to var here will be bound to "goose"
(let ((var 10))
  ;; statements go here.  Any reference to var here will be bound to 10.
  )
;; Any reference to var here will be bound to "goose"

I blocchi possono essere annidati per creare strutture di blocchi arbitrariamente complesse in base alle esigenze del programmatore. L'uso della strutturazione a blocchi per creare associazioni locali riduce il rischio di collisione dello spazio dei nomi che potrebbe altrimenti verificarsi.

Una variante di let, let*, consente alle associazioni di fare riferimento a variabili definite in precedenza nello stesso costrutto, quindi:

(let* ((var1 10)
       (var2 (+ var1 12)))
  ;; But the definition of var1 could not refer to var2
  )

L'altra variante, letrec, è progettata per consentire a procedure mutuamente ricorsive di essere legate l'una all'altra.

;; Calculation of Hofstadter's male and female sequences as a list of pairs

(define (hofstadter-male-female n)
  (letrec ((female (lambda (n)
		     (if (= n 0)
			 1
			 (- n (male (female (- n 1)))))))
	   (male (lambda (n)
		   (if (= n 0)
		       0
		       (- n (female (male (- n 1))))))))
    (let loop ((i 0))
      (if (> i n)
	  '()
	  (cons (cons (female i)
		      (male i))
		(loop (+ i 1)))))))

(hofstadter-male-female 8)

===> ((1 . 0) (1 . 0) (2 . 1) (2 . 2) (3 . 2) (3 . 3) (4 . 4) (5 . 4) (5 . 5))

(Vedi le sequenze maschili e femminili di Hofstadter per le definizioni usate in questo esempio.)

Tutte le procedure legate in un singolo letrecpossono riferirsi l'una all'altra per nome, così come a valori di variabili definite in precedenza nello stesso letrec, ma possono non fare riferimento a valori definiti in seguito nello stesso letrec.

Una variante di let, la forma "named let", ha un identificatore dopo la letparola chiave. Questo lega le variabili let all'argomento di una procedura il cui nome è l'identificatore dato e il cui corpo è il corpo della forma let. Il corpo può essere ripetuto a piacimento chiamando la procedura. Il let denominato è ampiamente utilizzato per implementare l'iterazione.

Esempio: un semplice contatore

(let loop ((n 1))
  (if (> n 10)
      '()
      (cons n
	    (loop (+ n 1)))))

===> (1 2 3 4 5 6 7 8 9 10)

Come qualsiasi procedura in Scheme, la procedura creata nel let con nome è un oggetto di prima classe.

Ricorsione di coda corretta

Scheme ha un costrutto di iterazione, do, ma è più idiomatico in Scheme usare la ricorsione di coda per esprimere l' iterazione . Le implementazioni dello Scheme conformi agli standard sono necessarie per ottimizzare le chiamate in coda in modo da supportare un numero illimitato di chiamate in coda attive (R5RS sez. 3.5) - una proprietà che il report Scheme descrive come una corretta ricorsione in coda - rendendo sicuro per i programmatori di Scheme scrivere algoritmi iterativi utilizzando strutture ricorsive, a volte più intuitive. Le procedure ricorsive in coda e la forma denominatalet forniscono supporto per l'iterazione utilizzando la ricorsione in coda.

;; Building a list of squares from 0 to 9:
;; Note: loop is simply an arbitrary symbol used as a label. Any symbol will do.

(define (list-of-squares n)
  (let loop ((i n) (res '()))
    (if (< i 0)
        res
        (loop (- i 1) (cons (* i i) res)))))

(list-of-squares 9)
===> (0 1 4 9 16 25 36 49 64 81)

Continuazioni di prima classe

Le continuazioni in Scheme sono oggetti di prima classe . Scheme fornisce la procedura call-with-current-continuation(nota anche come call/cc) per catturare la continuazione corrente impacchettandola come una procedura di escape legata a un argomento formale in una procedura fornita dal programmatore. (R5RS sez. 6.4) Le continuazioni di prima classe consentono al programmatore di creare costrutti di controllo non locali come iteratori , coroutine e backtracking .

Le continuazioni possono essere utilizzate per emulare il comportamento delle istruzioni return nei linguaggi di programmazione imperativi. La seguente funzione find-first, data funzione funce lista lst, restituisce il primo elemento xin lsttale che (func x)restituisce true.

(define (find-first func lst)
  (call-with-current-continuation
   (lambda (return-immediately)
     (for-each (lambda (x)
		 (if (func x)
		     (return-immediately x)))
	  lst)
     #f)))

(find-first integer? '(1/2 3/4 5.6 7 8/9 10 11))
===> 7
(find-first zero? '(1 2 3 4))
===> #f

L'esempio seguente, un enigma del programmatore tradizionale, mostra che Scheme può gestire le continuazioni come oggetti di prima classe, legandole a variabili e passandole come argomenti alle procedure.

(let* ((yin
         ((lambda (cc) (display "@") cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display "*") cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

Quando viene eseguito, questo codice visualizza una sequenza di conteggio: @*@**@***@****@*****@******@*******@********...

Spazio dei nomi condiviso per procedure e variabili

A differenza di Common Lisp, tutti i dati e le procedure in Scheme condividono uno spazio dei nomi comune, mentre in Common Lisp le funzioni e i dati hanno spazi dei nomi separati che rendono possibile che una funzione e una variabile abbiano lo stesso nome e che richiedono una notazione speciale per fare riferimento a un funzione come valore. Questo è talvolta noto come distinzione " Lisp-1 vs. Lisp-2 ", riferendosi allo spazio dei nomi unificato di Scheme e agli spazi dei nomi separati di Common Lisp.

In Scheme, le stesse primitive utilizzate per manipolare e associare i dati possono essere utilizzate per associare le procedure. Non esiste un equivalente di Common Lisp defune #'primitive.

;; Variable bound to a number:
(define f 10)
f
===> 10
;; Mutation (altering the bound value)
(set! f (+ f f 6))
f
===> 26
;; Assigning a procedure to the same variable:
(set! f (lambda (n) (+ n 12)))
(f 6)
===> 18
;; Assigning the result of an expression to the same variable:
(set! f (f 1))
f
===> 13
;; functional programming:
(apply + '(1 2 3 4 5 6))
===> 21
(set! f (lambda (n) (+ n 100)))
(map f '(1 2 3))
===> (101 102 103)

Standard di implementazione

Questa sottosezione documenta le decisioni progettuali prese nel corso degli anni che hanno conferito a Scheme un carattere particolare, ma non sono i risultati diretti del progetto originario.

Torre numerica

Scheme specifica un insieme relativamente completo di tipi di dati numerici inclusi i tipi complessi e razionali , che è noto in Scheme come la torre numerica (R5RS sez. 6.2). Lo standard li tratta come astrazioni e non impegna l'implementatore a nessuna particolare rappresentazione interna.

I numeri possono avere la qualità dell'esattezza. Un numero esatto può essere prodotto solo da una sequenza di operazioni esatte che coinvolgono altri numeri esatti: l'inesattezza è quindi contagiosa. Lo standard specifica che due implementazioni qualsiasi devono produrre risultati equivalenti per tutte le operazioni risultanti in numeri esatti.

Lo standard R5RS specifica le procedure exact->inexacte inexact->exactche possono essere utilizzate per modificare l'esattezza di un numero. inexact->exactproduce "il numero esatto numericamente più vicino all'argomento". exact->inexactproduce "il numero inesatto che è numericamente più vicino all'argomento". Lo standard R6RS omette queste procedure dal report principale, ma le specifica come procedure di compatibilità R5RS nella libreria standard (rnrs r5rs (6)).

Nello standard R5RS, le implementazioni Scheme non sono richieste per implementare l'intera torre numerica, ma devono implementare "un sottoinsieme coerente coerente sia con gli scopi dell'implementazione che con lo spirito del linguaggio Scheme" (R5RS sez. 6.2.3). Il nuovo standard R6RS richiede l'implementazione dell'intera torre e "oggetti interi esatti e oggetti numeri razionali esatti di dimensioni e precisione praticamente illimitate e per implementare determinate procedure ... in modo che restituiscano sempre risultati esatti quando vengono forniti argomenti esatti" (R6RS punto 3.4, punto 11.7.1).

Esempio 1: aritmetica esatta in un'implementazione che supporta numeri complessi razionali esatti.

;; Sum of three rational real numbers and two rational complex numbers
(define x (+ 1/3 1/4 -1/5 -1/3i 405/50+2/3i))
x
===> 509/60+1/3i
;; Check for exactness.
(exact? x)
===> #t

Esempio 2: Stessa aritmetica in un'implementazione che non supporta né numeri razionali esatti né numeri complessi ma accetta numeri reali in notazione razionale.

;; Sum of four rational real numbers
(define xr (+ 1/3 1/4 -1/5 405/50))
;; Sum of two rational real numbers
(define xi (+ -1/3 2/3))
xr
===> 8.48333333333333
xi
===> 0.333333333333333
;; Check for exactness.
(exact? xr)
===> #f
(exact? xi)
===> #f

Entrambe le implementazioni sono conformi allo standard R5RS ma la seconda non è conforme a R6RS perché non implementa la torre numerica completa.

Valutazione ritardata

Scheme supporta la valutazione ritardata attraverso il delaymodulo e la procedura force.

(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(set! a 20)
(force eval-aplus2)
===> 22
(define eval-aplus50 (delay (+ a 50)))
(let ((a 8))
  (force eval-aplus50))
===> 70
(set! a 100)
(force eval-aplus2)
===> 22

Il contesto lessicale della definizione originale della promessa è preservato, e il suo valore è preservato anche dopo il primo utilizzo di force. La promessa viene valutata una sola volta.

Queste primitive, che producono o gestiscono valori noti come promises , possono essere utilizzate per implementare costrutti di valutazione pigri avanzati come streams .

Nello standard R6RS, queste non sono più primitive, ma sono invece fornite come parte della libreria di compatibilità R5RS (rnrs r5rs (6)).

In R5RS, viene fornita un'implementazione suggerita di delaye force, implementando la promessa come una procedura senza argomenti (un thunk ) e utilizzando la memoizzazione per garantire che venga valutata una sola volta, indipendentemente dal numero di volte in cui forceviene chiamata (R5RS sez. 6.4 ).

SRFI 41 consente l'espressione di sequenze finite e infinite con straordinaria economia. Ad esempio, questa è una definizione della sequenza di Fibonacci utilizzando le funzioni definite in SRFI 41:

;; Define the Fibonacci sequence:
(define fibs
  (stream-cons 0
    (stream-cons 1
      (stream-map +
        fibs
        (stream-cdr fibs)))))
;; Compute the hundredth number in the sequence:
(stream-ref fibs 99)
===>  218922995834555169026

Ordine di valutazione degli argomenti della procedura

La maggior parte dei Lisps specifica un ordine di valutazione per gli argomenti della procedura. Lo schema no. L'ordine di valutazione, compreso l'ordine in cui viene valutata l'espressione nella posizione dell'operatore, può essere scelto da un'implementazione su base call-by-call e l'unico vincolo è che "l'effetto di qualsiasi valutazione simultanea dell'operatore e le espressioni degli operandi sono vincolate ad essere coerenti con un certo ordine sequenziale di valutazione." (R5RS sez. 4.1.3)

(let ((ev (lambda(n) (display "Evaluating ")
                     (display (if (procedure? n) "procedure" n))
                     (newline) n)))
  ((ev +) (ev 1) (ev 2)))
===> 3

ev è una procedura che descrive l'argomento passato, quindi restituisce il valore dell'argomento. A differenza di altri Lisps, l'aspetto di un'espressione nella posizione dell'operatore (il primo elemento) di un'espressione Scheme è abbastanza legale, purché il risultato dell'espressione nella posizione dell'operatore sia una procedura.

Chiamando la procedura "+" per aggiungere 1 e 2, le espressioni (ev +), (ev 1) e (ev 2) possono essere valutate in qualsiasi ordine, purché l'effetto non sia come se fossero valutate in parallelo . Pertanto le tre righe seguenti possono essere visualizzate in qualsiasi ordine dallo Schema standard quando viene eseguito il codice di esempio sopra, sebbene il testo di una riga non possa essere intercalato con un'altra perché ciò violerebbe il vincolo di valutazione sequenziale.

Valutando 1

Valutando 2

Procedura di valutazione

Macro igieniche

Nello standard R5RS e anche nei report successivi, la sintassi di Scheme può essere facilmente estesa tramite il sistema macro. Lo standard R5RS ha introdotto un potente sistema di macro igienico che consente al programmatore di aggiungere nuovi costrutti sintattici al linguaggio utilizzando un semplice sottolinguaggio di pattern matching (R5RS sez 4.3). In precedenza, il macrosistema igienico era stato relegato in un'appendice dello standard R4RS, come sistema di "alto livello" accanto a un macrosistema di "basso livello", entrambi trattati come estensioni dello schema piuttosto che come parte essenziale di la lingua.

Le implementazioni del macrosistema igienico, chiamato anche syntax-rules, sono necessarie per rispettare l'ambito lessicale del resto del linguaggio. Ciò è assicurato da regole speciali di denominazione e ambito per l'espansione delle macro ed evita errori di programmazione comuni che possono verificarsi nei sistemi macro di altri linguaggi di programmazione. R6RS specifica un sistema di trasformazione più sofisticato, syntax-case, che è disponibile da tempo come estensione del linguaggio allo schema R5RS.

;; Define a macro to implement a variant of "if" with a multi-expression
;; true branch and no false branch.
(define-syntax when
  (syntax-rules ()
    ((when pred exp exps ...)
      (if pred (begin exp exps ...)))))

Le invocazioni di macro e procedure hanno una stretta somiglianza - entrambe sono espressioni s - ma vengono trattate in modo diverso. Quando il compilatore incontra un'espressione s nel programma, verifica prima se il simbolo è definito come una parola chiave sintattica all'interno dell'ambito lessicale corrente. In tal caso, tenta di espandere la macro, trattando gli elementi nella coda dell'espressione s come argomenti senza compilare il codice per valutarli, e questo processo viene ripetuto in modo ricorsivo finché non rimangono chiamate macro. Se non è una parola chiave sintattica, il compilatore compila il codice per valutare gli argomenti nella coda dell'espressione s e quindi valutare la variabile rappresentata dal simbolo all'inizio dell'espressione s e chiamarla come procedura con la le espressioni di coda valutate passate come argomenti effettivi.

La maggior parte delle implementazioni dello schema fornisce anche sistemi macro aggiuntivi. Tra quelli popolari ci sono le chiusure sintattiche , le macro di rinomina esplicite e define-macro, un sistema di macro non igienico simile al defmacrosistema fornito in Common Lisp .

L'incapacità di specificare se una macro è igienica o meno è uno dei difetti del sistema macro. Modelli alternativi per l'espansione, come i set di oscilloscopi, forniscono una potenziale soluzione.

Ambienti e valutazione

Prima di R5RS, Scheme non aveva un equivalente standard della evalprocedura che è onnipresente in altri Lisps, sebbene il primo Lambda Paper l'avesse descritto evaluatecome "simile alla funzione LISP EVAL" e il primo Revised Report nel 1978 lo abbia sostituito con enclose, che ha preso due argomenti . La seconda, la terza e la quarta relazione revisionate hanno omesso qualsiasi equivalente di eval.

La ragione di questa confusione è che in Scheme con il suo ambito lessicale il risultato della valutazione di un'espressione dipende da dove viene valutata. Ad esempio, non è chiaro se il risultato della valutazione della seguente espressione debba essere 5 o 6:

(let ((name '+))
  (let ((+ *))
    (evaluate (list name 2 3))))

Se viene valutato nell'ambiente esterno, dove nameè definito, il risultato è la somma degli operandi. Se viene valutato nell'ambiente interno, dove il simbolo "+" è stato associato al valore della procedura "*", il risultato è il prodotto dei due operandi.

R5RS risolve questa confusione specificando tre procedure che restituiscono ambienti e fornendo una procedura evalche accetta un'espressione S e un ambiente e valuta l'espressione nell'ambiente fornito. (R5RS sez. 6.5) R6RS estende questo fornendo una procedura chiamata environmentcon la quale il programmatore può specificare esattamente quali oggetti importare nell'ambiente di valutazione.

Con lo schema moderno (di solito compatibile con R5RS) per valutare questa espressione, è necessario definire una funzione evaluateche può assomigliare a questa:

(define (evaluate expr)
   (eval expr (interaction-environment)))

interaction-environment è l'ambiente globale dell'interprete.

Trattamento dei valori non booleani nelle espressioni booleane

Nella maggior parte dei dialetti di Lisp incluso Common Lisp, per convenzione il valore NILrestituisce il valore false in un'espressione booleana. In Scheme, dallo standard IEEE nel 1991, tutti i valori tranne #f, incluso NILl'equivalente di 's in Scheme che è scritto come '(), restituiscono il valore true in un'espressione booleana. (R5RS sez. 6.3.1)

Dove la costante che rappresenta il valore booleano di true è Tnella maggior parte dei Lisps, in Scheme è #t.

Disgiunzione dei tipi di dati primitivi

In Scheme i tipi di dati primitivi sono disgiunti. Solo uno dei seguenti predicati può essere vero per qualsiasi oggetto Scheme: boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?. (R5RS sez 3.2)

All'interno del tipo di dati numerico, invece, i valori numerici si sovrappongono. Ad esempio, un valore intero soddisfa tutti i integer?, rational?, real?, complex?e number?predicati allo stesso tempo. (R5RS sez 6.2)

Predicati di equivalenza

Scheme ha tre diversi tipi di equivalenza tra oggetti arbitrari denotati da tre diversi predicati di equivalenza , operatori relazionali per testare l'uguaglianza eq?, eqv?e equal?:

• eq?valuta fino a #fmeno che i suoi parametri non rappresentino lo stesso oggetto dati in memoria;
• eqv?è generalmente uguale a eq?ma tratta oggetti primitivi (es. caratteri e numeri) in modo speciale in modo che i numeri che rappresentano lo stesso valore siano eqv?anche se non si riferiscono allo stesso oggetto;
• equal?confronta strutture di dati come elenchi, vettori e stringhe per determinare se hanno struttura e eqv?contenuti congruenti . (R5RS sez. 6.1)

Esistono anche operazioni di equivalenza dipendenti dal tipo in Scheme: string=?e string-ci=?confronta due stringhe (quest'ultima esegue un confronto indipendente dalle maiuscole); char=?e char-ci=?confrontare i caratteri; =confronta i numeri

Commenti

Fino allo standard R5RS, il commento standard in Scheme era un punto e virgola, che rende il resto della riga invisibile a Scheme. Numerose implementazioni hanno supportato convenzioni alternative che consentono ai commenti di estendersi per più di una singola riga e lo standard R6RS ne consente due: un'intera espressione s può essere trasformata in un commento (o "commentato") facendolo precedere da #;(introdotto in SRFI 62) e un commento multilinea o "commento di blocco" può essere prodotto circondando il testo con #|e |#.

Input Output

L'input e l'output dello schema si basano sul tipo di dati della porta . (R5RS sez 6.6) R5RS definisce due porte di default, accessibili con le procedure current-input-porte current-output-port, che corrispondono alle nozioni Unix di standard input e standard output . La maggior parte delle implementazioni fornisce anche current-error-port. Il reindirizzamento dell'input e dell'output standard è supportato nello standard da procedure standard come with-input-from-filee with-output-to-file. La maggior parte delle implementazioni fornisce porte di stringa con capacità di reindirizzamento simili, consentendo l'esecuzione di molte normali operazioni di input-output su buffer di stringa anziché su file, utilizzando procedure descritte in SRFI 6. Lo standard R6RS specifica procedure di porta molto più sofisticate e capaci e molti nuovi tipi di porta.

I seguenti esempi sono scritti in rigoroso schema R5RS.

Esempio 1: con output predefinito su (current-output-port):

(let ((hello0 (lambda() (display "Hello world") (newline))))
  (hello0))

Esempio 2: come 1, ma utilizzando l'argomento porta opzionale per le procedure di output

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (hello1 (current-output-port)))

Esempio 3: come 1, ma l'output viene reindirizzato a un file appena creato

;; NB: with-output-to-file is an optional procedure in R5RS
(let ((hello0 (lambda () (display "Hello world") (newline))))
  (with-output-to-file "helloworldoutputfile" hello0))

Esempio 4: come 2, ma con il file esplicito aperto e la porta chiusa per inviare l'output al file

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p)))
      (output-port (open-output-file "helloworldoutputfile")))
  (hello1 output-port)
  (close-output-port output-port))

Esempio 5: come 2, ma utilizzando call-with-output-file per inviare l'output a un file.

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (call-with-output-file "helloworldoutputfile" hello1))

Analoghe procedure sono previste per l'input. Lo schema R5RS fornisce i predicati input-port?e output-port?. Per l'input e l'output dei caratteri, vengono forniti write-char, read-char, peek-chare char-ready?. Per scrivere e leggere le espressioni Scheme, Scheme fornisce reade write. In un'operazione di lettura, il risultato restituito è l'oggetto di fine file se la porta di input ha raggiunto la fine del file e questo può essere verificato utilizzando il predicato eof-object?.

Oltre allo standard, SRFI 28 definisce una procedura di formattazione di base simile alla formatfunzione di Common Lisp , da cui prende il nome.

Ridefinizione delle procedure standard

In Scheme, le procedure sono legate alle variabili. In R5RS lo standard linguistico imponeva formalmente che i programmi potessero modificare le associazioni variabili delle procedure integrate, ridefinendole in modo efficace. (R5RS "Cambiamenti lingua") Ad esempio, si può estendere +l'accettazione di stringhe e numeri ridefinendolo:

(set! +
      (let ((original+ +))
        (lambda args
          (apply (if (or (null? args) (string? (car args)))
                     string-append
                     original+)
                 args))))
(+ 1 2 3)
===> 6
(+ "1" "2" "3")
===> "123"

In R6RS ogni associazione, comprese quelle standard, appartiene a qualche libreria e tutte le associazioni esportate sono immutabili. (R6RS sez 7.1) Per questo motivo è vietata la ridefinizione delle procedure standard per mutazione. È invece possibile importare una procedura diversa sotto il nome di una standard, che in effetti è simile alla ridefinizione.

Nomenclatura e convenzioni di denominazione

Nello schema standard, le procedure che convertono da un tipo di dati a un altro contengono la stringa di caratteri "->" nel nome, i predicati terminano con un "?" e le procedure che modificano il valore dei dati già allocati terminano con "!". Queste convenzioni sono spesso seguite dai programmatori di Scheme.

In contesti formali come gli standard Scheme, la parola "procedura" viene utilizzata preferibilmente rispetto a "funzione" per riferirsi a un'espressione lambda oa una procedura primitiva. Nell'uso normale, le parole "procedura" e "funzione" sono usate in modo intercambiabile. L'applicazione della procedura è talvolta indicata formalmente come combinazione .

Come in altri Lisps, il termine " thunk " è usato in Scheme per riferirsi a una procedura senza argomenti. Il termine "correzione di coda corretta" si riferisce alla proprietà di tutte le implementazioni di Scheme, che eseguono l'ottimizzazione delle chiamate di coda in modo da supportare un numero indefinito di chiamate di coda attive .

La forma dei titoli dei documenti standard da R3RS, "Revised ⁿ Report on the Algorithmic Language Scheme", è un riferimento al titolo del documento standard ALGOL 60 , "Revised Report on the Algorithmic Language Algol 60," La pagina di riepilogo di R3RS è strettamente modellato sulla pagina Riepilogo del Rapporto ALGOL 60.

Revisione di moduli e procedure standard

Il linguaggio è formalmente definito negli standard R5RS (1998) e R6RS (2007). Descrivono "moduli" standard: parole chiave e sintassi di accompagnamento, che forniscono la struttura di controllo del linguaggio e procedure standard che svolgono compiti comuni.

Moduli standard

Questa tabella descrive i moduli standard in Scheme. Alcune forme appaiono in più di una riga perché non possono essere facilmente classificate in un'unica funzione nella lingua.

I moduli contrassegnati con "L" in questa tabella sono classificati come moduli "libreria" derivati ​​nello standard e sono spesso implementati come macro utilizzando moduli più fondamentali nella pratica, rendendo il compito di implementazione molto più semplice rispetto ad altri linguaggi.

Si noti che beginè definita come una sintassi di libreria in R5RS, ma l'espansore deve conoscerla per ottenere la funzionalità di giunzione. In R6RS non è più una sintassi di libreria.

Procedure standard

Le due tabelle seguenti descrivono le procedure standard nello schema R5RS. R6RS è molto più ampio e un riassunto di questo tipo non sarebbe pratico.

Alcune procedure vengono visualizzate in più di una riga perché non possono essere facilmente classificate in un'unica funzione nel linguaggio.

Le procedure per stringhe e caratteri che contengono "-ci" nei loro nomi eseguono confronti indipendenti dalle maiuscole tra i loro argomenti: le versioni maiuscole e minuscole dello stesso carattere sono considerate uguali.

Le implementazioni di - e / che richiedono più di due argomenti sono definite ma lasciate facoltative in R5RS.

Richieste di schema per l'attuazione

A causa del minimalismo di Scheme, molte procedure comuni e forme sintattiche non sono definite dallo standard. Al fine di mantenere il linguaggio di base piccolo ma facilitare la standardizzazione delle estensioni, la comunità Scheme ha un processo "Scheme Request for Implementation" (SRFI) mediante il quale le librerie di estensioni vengono definite attraverso un'attenta discussione delle proposte di estensione. Ciò promuove la portabilità del codice. Molti degli SRFI sono supportati da tutte o dalla maggior parte delle implementazioni dello schema.

Gli SRFI con un supporto abbastanza ampio in diverse implementazioni includono:

• 0: costrutto di espansione condizionale basato su funzionalità
• 1: libreria elenco
• 4: tipi di dati vettoriali numerici omogenei
• 6: porte stringa di base
• 8: ricevere, vincolante a più valori
• 9: definizione dei tipi di record
• 13: libreria di stringhe
• 14: libreria di set di caratteri
• 16: sintassi per procedure di arieta variabile
• 17: insieme generalizzato!
• 18: Supporto multithreading
• 19: tipi di dati temporali e procedure
• 25: primitive di array multidimensionali
• 26: notazione per la specializzazione dei parametri senza currying
• 27: sorgenti di bit casuali
• 28: stringhe di formato base
• 29: localizzazione
• 30: commenti su più righe nidificati
• 31: un modulo speciale per la valutazione ricorsiva
• 37: args-fold: un processore di argomenti del programma
• 39: oggetti parametro
• 41: flussi
• 42: comprensioni ansiose
• 43: libreria vettoriale
• 45: primitive per esprimere algoritmi pigri iterativi
• 60: interi come bit
• 61: una cond clausola più generale
• 66: vettori di ottetti
• 67: confrontare le procedure

implementazioni

Il design elegante e minimalista ha reso Scheme un obiettivo popolare per i progettisti di lingue, gli appassionati e gli educatori e, a causa delle sue dimensioni ridotte, quelle di un tipico interprete , è anche una scelta popolare per i sistemi incorporati e lo scripting . Ciò ha portato a decine di implementazioni, la maggior parte delle quali differisce l'una dall'altra così tanto che il porting di programmi da un'implementazione all'altra è piuttosto difficile, e le dimensioni ridotte del linguaggio standard significa che scrivere un programma utile di grande complessità in standard, lo schema portatile è quasi impossibile. Lo standard R6RS specifica un linguaggio molto più ampio, nel tentativo di ampliare il suo appeal sui programmatori.

Quasi tutte le implementazioni forniscono un ciclo di lettura-valutazione-stampa tradizionale in stile Lisp per lo sviluppo e il debug. Molti compilano anche programmi Scheme in binari eseguibili. Anche il supporto per l'incorporamento del codice Scheme in programmi scritti in altri linguaggi è comune, poiché la relativa semplicità delle implementazioni Scheme lo rende una scelta popolare per l'aggiunta di funzionalità di scripting a sistemi più grandi sviluppati in linguaggi come C . Gli interpreti Gambit , Chicken e Bigloo Scheme compilano Scheme in C, il che rende l'incorporamento particolarmente facile. Inoltre, il compilatore di Bigloo può essere configurato per generare bytecode JVM e dispone anche di un generatore di bytecode sperimentale per .NET .

Alcune implementazioni supportano funzionalità aggiuntive. Ad esempio, Kawa e JScheme forniscono l'integrazione con le classi Java e i compilatori Scheme to C spesso facilitano l'uso di librerie esterne scritte in C, fino a consentire l'incorporamento del codice C effettivo nel sorgente Scheme. Un altro esempio è Pvts , che offre una serie di strumenti visivi per supportare l'apprendimento di Scheme.

utilizzo

Lo schema è ampiamente utilizzato da un certo numero di scuole; in particolare, un certo numero di corsi introduttivi di Informatica utilizza Scheme in combinazione con il libro di testo Struttura e interpretazione dei programmi per computer (SICP). Negli ultimi 12 anni, PLT ha gestito il progetto ProgramByDesign (precedentemente TeachScheme!), che ha esposto quasi 600 insegnanti delle scuole superiori e migliaia di studenti delle scuole superiori alla programmazione rudimentale di Scheme. MIT vecchia classe di programmazione introduttivo 's 6.001 è stato insegnato in Scheme, Anche se 6.001 è stato sostituito da corsi più moderni, SICP continua ad essere insegnato al MIT. Allo stesso modo, la classe introduttiva all'UC Berkeley , CS 61A, è stata insegnata fino al 2011 interamente in Scheme, salvo deviazioni minori in Logo per dimostrare l'ambito dinamico. Oggi, come il MIT, Berkeley ha sostituito il programma con una versione più moderna che viene insegnata principalmente in Python 3 , ma il programma attuale è ancora basato sul vecchio curriculum e parti della classe sono ancora insegnate in Scheme.

Il libro di testo How to Design Programs di Matthias Felleisen, attualmente alla Northeastern University, è utilizzato da alcuni istituti di istruzione superiore per i loro corsi introduttivi di informatica. Sia la Northeastern University che il Worcester Polytechnic Institute utilizzano Scheme esclusivamente per i loro corsi introduttivi Fundamentals of Computer Science (CS2500) e Introduction to Program Design (CS1101), rispettivamente. Rose-Hulman utilizza Scheme nel suo corso più avanzato sui concetti di linguaggio di programmazione. Anche il corso principale della Brandeis University , Struttura e interpretazioni dei programmi per computer (COSI121b), è tenuto esclusivamente in Scheme dall'informatico teorico Harry Mairson . La classe introduttiva dell'Università dell'Indiana , C211, è insegnata interamente in Scheme. Una versione autodidattica del corso, CS 61AS, continua a utilizzare Scheme. Anche i corsi introduttivi di informatica a Yale e Grinnell College sono tenuti in Scheme. Anche Programming Design Paradigms, un corso obbligatorio per gli studenti laureati in informatica presso la Northeastern University , utilizza ampiamente Scheme. Anche il precedente corso introduttivo di Informatica presso l'Università del Minnesota - Twin Cities, CSCI 1901, utilizzava Scheme come linguaggio principale, seguito da un corso che introduceva gli studenti al linguaggio di programmazione Java; tuttavia, seguendo l'esempio del MIT, il dipartimento ha sostituito il 1901 con il CSCI 1133 basato su Python, mentre la programmazione funzionale è trattata in dettaglio nel corso del terzo semestre CSCI 2041. Nell'industria del software, Tata Consultancy Services , la più grande società di consulenza software dell'Asia , utilizza Scheme nel suo programma di formazione di un mese per neolaureati.

Lo schema è/è stato utilizzato anche per quanto segue:

• Il Document Style Semantics and Specification Language (DSSSL), che fornisce un metodo per specificare i fogli di stile SGML , utilizza un sottoinsieme Scheme.
• Il noto editor di grafica raster open source GIMP utilizza TinyScheme come linguaggio di scripting .
• Guile è stato adottato dal progetto GNU come linguaggio di scripting ufficiale e tale implementazione di Scheme è incorporata in applicazioni come GNU LilyPond e GnuCash come linguaggio di scripting per le estensioni. Allo stesso modo, Guile era il linguaggio di scripting per l' ambiente desktop GNOME e GNOME ha ancora un progetto che fornisce collegamenti Guile al suo stack di librerie. C'è un progetto per incorporare Guile in GNU Emacs , il programma di punta di GNU, che sostituisce l'attuale interprete Emacs Lisp .
• Elk Scheme è utilizzato da Synopsys come linguaggio di scripting per i suoi strumenti CAD tecnologici (TCAD) .
• Shiro Kawai, programmatore senior del film Final Fantasy: The Spirits Within , ha utilizzato Scheme come linguaggio di scripting per la gestione del motore di rendering in tempo reale.
• Google App Inventor per Android utilizza Scheme, dove Kawa viene utilizzato per compilare il codice Scheme fino ai codici byte per la Java Virtual Machine in esecuzione su dispositivi Android.

Guarda anche

• Elementi essenziali dei linguaggi di programmazione , libro di testo che utilizza Scheme come base

Riferimenti

Ulteriori letture

• Introduzione allo schema e alla sua implementazione ( un mirror )
• Christopher T. Haynes (1999-06-22). "L'esperienza di standardizzazione del linguaggio di programmazione dello schema" .
• Guy L. Steele Jr. , Richard P. Gabriel . "L'evoluzione del Lisp" (PDF) .
• Gerald Sussman e Guy Steele , SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349 , MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, dicembre 1975.

link esterno

• Schema a Curlie
• Programmazione di schemi su Wikibooks
• Scrivi uno schema in 48 ore su Wikibooks
• Mezzi relativi a Scheme (linguaggio di programmazione) su Wikimedia Commons
• Bookmarklet che aggiunge lo schema interattivo REPL a qualsiasi sito web