Haupt >> Computerprogrammierung >> Schema (Programmiersprache)

Schema (Programmiersprache)

Paradigma: Multi-Paradigma: funktional, prozedural
Erschien in: 1970er
Entworfen von: Guy L. Steele und Gerald Jay Sussman
Schreibdisziplin: stark, dynamisch
Wichtige Implementierungen: PLT-Schema, MIT-Schema, Schema48, Huhn, Gambit-C, Guile, Bigloo, Chez-Schema, STk, Larceny, SCM
Dialekte: viele
Beeinflusst von: Lisp, ALGOL
Beeinflusst: Common Lisp, JavaScript, Ruby

Planen ist eine Programmiersprache mit mehreren Paradigmen. Es ist ein Lisp-Dialekt, der unterstützt funktionell und prozedurale Programmierung. Es wurde in den 1970er Jahren von Guy L. Steele und Gerald Jay Sussman entwickelt. Scheme wurde der akademischen Welt durch eine Reihe von Artikeln vorgestellt, die jetzt als Sussman and Steele's Lambda Papers bezeichnet werden. Es gibt zwei Standards, die die Scheme-Sprache definieren: der offizielle IEEE-Standard und ein De-facto-Standard namens the Überarbeitet n Bericht über das algorithmische Sprachschema , fast immer mit R abgekürzt n RS, wo n ist die Revisionsnummer. Der aktuelle Standard ist R5RS , und R6RS befindet sich in der Entwicklung.

Die Philosophie von Scheme ist minimalistisch. Scheme bietet so wenige primitive Begriffe wie möglich und lässt alles andere, wo es praktikabel ist, von Programmierbibliotheken bereitstellen.

Scheme war der erste Dialekt von Lisp, der den statischen (auch bekannt als lexikalischen) Gültigkeitsbereich dem dynamischen Variablenbereich vorzog. Es war auch eine der ersten Programmiersprachen, die erstklassige Fortsetzungen unterstützte.



Herkunft

Scheme begann als Versuch, das Schauspielermodell von Carl Hewitt zu verstehen. Scheme wurde ursprünglich 'Schemer' genannt, in der Tradition anderer von Lisp abgeleiteter Sprachen wie Planner oder Conniver. Der aktuelle Name resultierte aus der Verwendung des ITS-Betriebssystems durch die Autoren, das Dateinamen auf zwei Komponenten mit jeweils höchstens sechs Zeichen beschränkte. Derzeit wird 'Schemer' häufig verwendet, um sich auf einen Scheme-Programmierer zu beziehen.

Zukunft

Beim Scheme-Workshop 2003 begann ein neuer Sprachstandardisierungsprozess mit dem Ziel, 2006 einen R6RS-Standard zu erstellen. Er bricht mit dem früheren RnRS-Ansatz der Einstimmigkeit. R6RS verfügt über ein Standardmodulsystem; ermöglicht eine Aufteilung zwischen der Kernsprache und den Bibliotheken.

Unterscheidungsmerkmale

Scheme ist eine minimalistische Sprache. Der aktuelle Sprachstandard umfasst nur 50 Seiten, einschließlich einer denotationalen Semantik für den Sprachkern. Die nächste Überarbeitung des Standards wird erweitert, um mehrere Bibliotheken zu beschreiben.

Wie alle Lisp-Dialekte hat Scheme wenig Syntax. Es gibt keine Vorrangregeln für Operatoren, da für alle zusammengesetzten Formen eine vollständig verschachtelte und eingeklammerte Notation verwendet wird.

Das Makrosystem von Scheme ermöglicht es dem Benutzer, der Sprache neue syntaktische Konstrukte hinzuzufügen. Es respektiert den lexikalischen Geltungsbereich des Rests der Sprache, wodurch allgemeine Programmierfehler vermieden werden, die in den Makrosystemen anderer Programmiersprachen auftreten können.

Prozeduren im Schema sind erstklassige Werte, die für Funktionale Programmierung .

Der call-with-current-continuation-Operator von Scheme ermöglicht es dem Benutzer, nicht lokale Steuerungskonstrukte zu erstellen, die in andere Sprachen eingebaut werden müssen, wie z. B. Iteratoren, Co-Routinen und Backtracking.

Sprachelemente

Kommentare

Jedem Kommentar ist ein Semikolon (;) vorangestellt und erstreckt sich über den Rest der Zeile. Einige Implementierungen erlauben Kommentaren, sich über mehrere Zeilen zu erstrecken, indem sie mit einem #|...|# (möglicherweise verschachtelt) umbrochen werden. Bei anderen Implementierungen kann ein ganzer S-Ausdruck auskommentiert werden, indem ihm ein #; vorangestellt wird.

Variablen

Variablen werden dynamisch typisiert. Variablen werden durch a gebunden definieren , a Lassen Ausdruck und ein paar andere Scheme-Formen. Variablen, die auf der obersten Ebene mit einem Define gebunden sind, sind in globale Reichweite .

 (define var1 value)

In einem Let gebundene Variablen sind im Bereich des Let-Bodys.

 (let ((var1 value))
   ...
   ; scope of var1
   ...)

Funktionen

1  (define fun
     (lambda (arg1 arg2)
       ...))
2  (define (fun arg1 arg2)
     ...)
3  (fun value1 value2)
4  (apply fun (list value1 value2))

Funktionen sind erstklassige Objekte in Scheme. Sie können Argumente für andere Funktionen sein und von diesen zurückgegeben werden. Sie können Variablen zugewiesen werden. Zum Beispiel eine Funktion mit zwei Argumenten arg1 und arg2 ist in Zeile 1 definiert und Zeile 2 ist eine Abkürzung davon. Zeile 3 zeigt, wie Funktionen angewendet werden. Beachten Sie, dass die angewendete Funktion an der ersten Position der Liste steht, während der Rest der Liste die Argumente enthält. Die Funktion apply nimmt das erste Argument und wendet es auf eine gegebene Liste von Argumenten an, sodass der vorherige Funktionsaufruf auch so geschrieben werden kann, wie es in Zeile 4 zu sehen ist.

In Scheme werden Funktionen in zwei grundlegende Kategorien unterteilt: Prozeduren und Primitive. Alle Primitive sind Prozeduren, aber nicht alle Prozeduren sind Primitive. Primitive sind vordefinierte Funktionen in der Scheme-Sprache. These include +, -, *, /, set!, car, cdr, and other basic procedures. Prozeduren sind benutzerdefinierte Funktionen. In mehreren Variationen von Scheme kann ein Benutzer ein Grundelement neu definieren. Zum Beispiel der Code

(define (+ x y)
  (- x y))

oder einfach

(define + -)

definiert das Grundelement + tatsächlich neu, um eine Subtraktion anstelle einer Addition durchzuführen.

Listen

Scheme verwendet die Datenstruktur der verketteten Liste in der gleichen Form, wie sie in Lisp existiert. 'list' erstellt eine neue verknüpfte Listenstruktur, zum Beispiel:

(list 1 2 3) (list (list 1 2) 3)

„Auto“ (ausgesprochen: [k�`r] Hören ) gibt den Wert des Kopfknotens der Liste an, zum Beispiel:

(car (list 1 2 3))

gibt

1

und

(car (list (list 1 2) 3))

gibt

(1 2)

„cdr“ (ausgesprochen „könnte“ ['Trauer Hören ] oder ['kudər]) gibt die Liste nach dem Kopfknoten an, zum Beispiel:

(cdr (list 1 2 3))

gibt

(2 3)

und

(cdr (list (list 1 2) 3)

gibt

(3)

'cons' erstellt eine neue Liste mit einem bestimmten Autowert und einer cdr-Liste, zum Beispiel:

(cons 1 (list 2 3))

gibt

(1 2 3)

und

(cons (list 1 2) (list 3))

gibt

((1 2) 3)
  Ein Box- und Zeigerdiagramm


Jeder Knoten in der verknüpften Liste ist eine Cons-Zelle, die auch als Paar bezeichnet wird. Wie das Namenspaar andeutet, besteht eine Cons-Zelle aus zwei Werten: Der erste ist das Auto und der zweite die cdr. Zum

(list 1 2 3)

Es gibt drei Cons-Zellen oder Paare. Die erste Cons-Zelle hat die Nummer 1 im ersten Slot und einen Zeiger auf die zweite Cons-Zelle im zweiten. Die zweite Cons-Zelle hat die Nummer 2 im ersten Slot und einen Zeiger auf die dritte Cons-Zelle im zweiten Slot. Die dritte Cons-Zelle hat die Nummer 3 im ersten Slot und eine Nullkonstante im zweiten Slot. Die Nullkonstante wird normalerweise durch '() oder (quote ()) dargestellt. Die Cons-Funktion konstruiert diese Cons-Zellen, weshalb

(cons 1 (list 2 3))

gibt die Liste

(1 2 3)

Wenn beide Argumente keine Listen sind, wird ein Paar erstellt, das durch einen Punkt dargestellt wird. Zum Beispiel

(cons 1 2)

gibt

(1 . 2)

wobei die Cons-Zelle in ihren Slots aus 1 und 2 besteht, anstatt aus einem Zeiger auf eine andere Cons-Zelle in ihrem zweiten Slot.

Die Namen der beiden primitiven Operationen zum Zerlegen von Listen, car und cdr, stammen ursprünglich aus Assembler-Makros für den IBM 704; Sie standen für 'Inhalt des Adressregisters' bzw. 'Inhalt des Dekrementregisters'.

Datentypen

Andere übliche Datentypen in Scheme neben Funktionen und Listen sind: Integer, rationale, reelle, komplexe Zahlen, Symbole, Strings und Ports. Die meisten Scheme-Implementierungen bieten auch Assoziationslisten, Hash-Tabellen, Vektoren, Arrays und Strukturen. Seit dem IEEE Scheme-Standard und dem R4RS Scheme-Standard hat Scheme behauptet, dass alle oben genannten Typen dies sind disjunkt , das heißt, kein Wert kann zu mehr als einem dieser Typen gehören; Einige alte Implementierungen von Scheme sind jedoch älter als diese Standards, so dass #f und '() auf denselben Wert verweisen, wie dies in Common Lisp der Fall ist.

Die meisten Scheme-Implementierungen bieten einen vollständigen Zahlenturm sowie exakte und ungenaue Arithmetik.

Wahr und falsch werden durch #t und #f dargestellt. Tatsächlich ist nur #f wirklich falsch, wenn ein boolescher Typ erforderlich ist, alles andere wird als wahr betrachtet, einschließlich der leeren Liste. Symbole können mindestens auf folgende Weise erstellt werden:

 'symbol
 (string->symbol "symbol")

Gleichberechtigung

Das Schema hat drei verschiedene Gleichheitstypen: 'eq?' gibt #t zurück, wenn seine Parameter dasselbe Datenobjekt im Speicher darstellen; 'eqv?' is generally the same as eq? but treats some objects (eg. characters and numbers) specially so that numbers that are = are eqv? even if they are not eq?; equal? vergleicht Datenstrukturen wie Listen, Vektoren und Strings, um festzustellen, ob sie eine kongruente Struktur und einen eqv? Inhalt haben.

Typabhängige Äquivalenzoperationen existieren auch in Schema: string=?; vergleicht zwei Strings; char=? vergleicht Zeichen; = vergleicht Zahlen.

Kontrollstrukturen

Bedingte Bewertung

 (if test then-expr else-expr)

The test expression is evaluated, and if the evaluation result is true (anything other than #f) then the then-expr is evaluated, otherwise else-expr is evaluated.

Eine Form, die bequemer ist, wenn Bedingungen verschachtelt sind, ist cond:

 (cond (test1 expr1 ...)
       (test2 expr2 ...)
       ...
       (else exprn))

Der erste Ausdruck, für den der Test wahr ergibt, wird ausgewertet. Wenn alle Tests #f ergeben, wird die Klausel else ausgewertet.

Eine Variante der cond-Klausel ist

 (cond ...
       (test => expr)
       ...)

In diesem Fall sollte expr zu einer Funktion ausgewertet werden, die ein Argument akzeptiert. Wenn test als wahr ausgewertet wird, wird die Funktion mit dem Rückgabewert von test aufgerufen.

Schleifen

Schleifen in Scheme haben normalerweise die Form einer Schwanzrekursion. Scheme-Implementierungen sind erforderlich, um Endaufrufe zu optimieren, um die Verwendung von Stapelspeicherplatz nach Möglichkeit zu eliminieren, sodass beliebig lange Schleifen unter Verwendung dieser Technik ausgeführt werden können.

Ein klassisches Beispiel ist die Fakultätsfunktion, die nicht schwanzrekursiv definiert werden kann:

 (define (factorial n)
   (if (= n 0)
     1
     (* n (factorial (- n 1)))))
 (factorial 5)
 ;; => 120

Dies ist eine direkte Übersetzung der mathematisch rekursiven Definition der Fakultät: die Fakultät von Null (normalerweise geschrieben 0! ) ist gleich 1, während die Fakultät jeder größeren natürlichen Zahl n ist definiert als n ! = n * ( n −1)! .

Die einfache Rekursion ist jedoch von Natur aus weniger effizient, da das Scheme-System einen Stapel verwalten muss, um die Rückgaben aller verschachtelten Funktionsaufrufe zu verfolgen. Eine tail-rekursive Definition ist eine, die sicherstellt, dass im rekursiven Fall der äußerste Aufruf einer zurück zum Anfang der wiederkehrenden Funktion ist. In diesem Fall wiederholen wir nicht die Funktion factorial selbst, sondern eine Hilfsroutine mit zwei Parametern, die den Zustand der Iteration darstellen:

 (define (factorial n)
   (let loop ((total 1)
              (i n))
     (if (= i 0)
       total
       (loop (* i total) (- i 1)))))
 (factorial 5)
 ;; => 120

Eine Funktion höherer Ordnung wie z Karte , die eine Funktion auf jedes Element einer Liste anwendet, kann nicht-schwanzrekursiv definiert werden:

 (define (map f lst)
   (if (null? lst)
     lst
     (cons (f (car lst))
           (map f (cdr lst)))))
 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;;  => (1 4 9 16)

oder kann auch tail-rekursiv definiert werden:

 (define (map f lst)
   (let loop ((lst lst)
              (res '()))
     (if (null? lst)
       (reverse res)
       (loop (cdr lst)
             (cons (f (car lst)) res)))))
 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;; => (1 4 9 16)

In beiden Fällen ist die schwanzrekursive Version aufgrund ihres geringeren Platzbedarfs vorzuziehen.

Für grundlegende Schleifen unterstützt Scheme eine einfache tun Iterator-Konstrukt:

 (do ((<variable1> <init1> <step1>)
    ...)
  (<test> <expression> ...)
  <command> ...)

Zum Beispiel:

 (let ((x '(1 3 5 7 9)))
   (do ((x x (cdr x))
        (sum 0 (+ sum (car x))))
      ((null? x) sum)))

Input-Output

Schema hat das Konzept von Häfen zu lesen oder zu schreiben. R5RS definiert zwei Standardports, auf die mit den Funktionen current-input-port und current-output-port zugegriffen werden kann, die den Unix-Begriffen von stdin und stdout entsprechen. Die meisten Implementierungen bieten auch current-error-port.

Beispiele

Hallo Welt

 (begin
   (display "Hello, World!")
   (newline))

OOP nach Liste (Assoziationsliste)

 ;; OOP(object-oriented programming) by alist(association list) example
 (define (cat-construct age color size) ;; constructor
   (list (cons 'age age)
         (cons 'color colour)
         (cons 'size size)))
 ;; cat meows (its age) times
 (define (cat-meow cat)
   (let loop ((iteration (cdr (assoc 'age cat))))
     (if (> iteration 0)
         (begin
           (display "Meow!\n")
           (loop (- iteration 1))))))
 (define billy (cat-construct 3 'white 'small))
 (display "billy's age: ")
 (display (cdr (assoc 'age billy))) (newline)
 (display "billy's color: ")
 (display (cdr (assoc 'colour billy))) (newline)
 (cat-meow billy)

Schemacode finden Sie in den folgenden Artikeln:

  • Arithmetisch-geometrisches Mittel
  • Kirchennummer
  • Fortsetzungspass-Stil
  • Anruf-mit-aktueller-Fortsetzung (auch bekannt als „Anruf/cc“)
  • Curry
  • Fibonacci zahlen programm
  • wikibooks:Transwiki:Liste der Hallo-Welt-Programme
  • Endlosschleife
  • Schwanzrekursion
  • Warteschlange
  • Quine (Computer)