History of the Scheme programming language

The history of the programming language Scheme begins with the development of earlier members of the Lisp family of languages during the second half of the twentieth century. During the design and development period of Scheme, language designers Guy L. Steele and Gerald Jay Sussman released an influential series of Massachusetts Institute of Technology (MIT) AI Memos known as the Lambda Papers (1975–1980). This resulted in the growth of popularity in the language and the era of standardization from 1990 onward. Much of the history of Scheme has been documented by the developers themselves.^[1]

The development of Scheme was heavily influenced by two predecessors that were quite different from one another: Lisp provided its general semantics and syntax, and ALGOL provided its lexical scope and block structure. Scheme is a dialect of Lisp but Lisp has evolved; the Lisp dialects from which Scheme evolved—although they were in the mainstream at the time—are quite different from any modern Lisp. Scheme falls within the large Lisp family of languages that includes Common Lisp, Scheme, ISLisp, EuLisp, XLisp, and AutoLisp.

Lisp was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT). McCarthy published its design in a paper in Communications of the ACM in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"^[2] (Part II was never published). He showed that with a few simple operators and a notation for functions, one can build a Turing-complete language for algorithms.

The use of s-expressions which characterize the syntax of Lisp was initially intended to be an interim measure pending the development of a language employing what McCarthy called "m-expressions". As an example, the m-expression car[cons[A,B]] is equivalent to the s-expression (car (cons A B)). S-expressions proved popular, however, and the many attempts to implement m-expressions failed to catch on.

Die erste Implementierung von Lisp erfolgte auf einer IBM 704 durch Steve Russell , der McCarthys Artikel gelesen und die darin beschriebene eval-Funktion in Maschinencode umgesetzt hatte. Die in Lisp geläufigen (aber für Neulinge verwirrenden) Bezeichnungen CAR und CDR für das erste und das letzte Element einer Liste entwickelten sich aus zwei IBM-704- Assemblerbefehlen: „Contents of Address Register“ und „Contents of Decrement Register“. Jeder dieser Befehle gab den Inhalt eines 15-Bit-Registers zurück, das Segmenten eines 36-Bit -IBM-704-Befehlsworts entsprach .

Der erste vollständige Lisp-Compiler, geschrieben in Lisp, wurde 1962 von Tim Hart und Mike Levin am MIT implementiert. ^{[ 3 ]} Dieser Compiler führte das Lisp-Modell der inkrementellen Kompilierung ein, bei dem kompilierte und interpretierte Funktionen frei miteinander vermischt werden können.

Die beiden für die Entwicklung von Scheme wichtigsten Lisp-Varianten wurden beide am MIT entwickelt: LISP 1.5 ^{[ 4 ],} entwickelt von McCarthy und anderen, und Maclisp ^{[ 5 ]} , entwickelt für das MIT- Projekt MAC , ein direkter Nachfolger von LISP 1.5, das auf den Systemen PDP-10 und Multics lief.

Seit seinen Anfängen war Lisp eng mit der Forschungsgemeinschaft für künstliche Intelligenz (KI) verbunden, insbesondere auf dem PDP-10 . Die 36-Bit-Wortgröße des PDP-6 und PDP-10 wurde durch die Nützlichkeit beeinflusst, zwei 18-Bit- Lisp- Zeiger in einem Wort unterzubringen . ^{[ 6 ]}

ALGOL 58 , ursprünglich IAL (für „International Algorithmic Language“) genannt, wurde 1958 von einem Komitee europäischer und amerikanischer Informatiker auf einem Treffen an der ETH Zürich gemeinsam entwickelt . ALGOL 60 , eine spätere Überarbeitung, die auf dem ALGOL-60-Treffen in Paris entstand und heute allgemein als ALGOL bekannt ist , wurde zum Standard für die Veröffentlichung von Algorithmen und hatte trotz des mangelnden kommerziellen Erfolgs und der Einschränkungen der Sprache einen tiefgreifenden Einfluss auf die zukünftige Sprachentwicklung. Tony Hoare bemerkte dazu: „Diese Sprache war ihrer Zeit so weit voraus, dass sie nicht nur eine Verbesserung gegenüber ihren Vorgängern, sondern auch gegenüber nahezu allen ihren Nachfolgern darstellte.“ ^{[ 7 ]}

ALGOL führte die Verwendung von Blockstrukturen und lexikalischen Gültigkeitsbereichen ein. Es war außerdem berüchtigt für seinen umständlichen Mechanismus zur Übergabe von Standardparametern per Namensaufruf . Dieser erforderte, dass der formale Parameter während der Ausführung einer Prozedur oder Funktion durch den Ausdruck, der den Arbeitsparameter repräsentierte, ersetzt wurde. Dadurch musste der Arbeitsparameter bei jedem Zugriff neu ausgewertet werden. Die ALGOL-Implementierer entwickelten daraufhin einen Mechanismus namens „ Thunk“ , der den Kontext des Arbeitsparameters erfasste und so dessen Auswertung während der Ausführung der Prozedur oder Funktion ermöglichte.

1971 entwickelten Sussman, Drew McDermott und Eugene Charniak ein System namens Micro-Planner , eine unvollständige und unbefriedigende Implementierung von Carl Hewitts ambitioniertem Planner- Projekt. Sussman und Hewitt arbeiteten gemeinsam mit anderen an Muddle (später MDL) , einer erweiterten Lisp-Sprache, die Bestandteil von Hewitts Projekt war. 1972 entwickelten Drew McDermott und Sussman die Lisp-basierte Sprache Conniver , die die ihrer Ansicht nach unproduktive automatische Rückverfolgung in Planner überarbeitete. Hewitt bezweifelte, dass die komplexe Kontrollstruktur von Conniver eine Lösung für die Probleme von Planner darstellte. Pat Hayes bemerkte: „Ihre [Sussman und McDermott] Lösung, dem Benutzer Zugriff auf die Implementierungsprimitive von Planner zu gewähren, ist jedoch ein Rückschritt (welche Semantik hat Conniver?).“ ^{[ 8 ]}

Im November 1972 entwickelten Hewitt und seine Studenten das Aktormodell als Lösung für die Probleme mit Planner. ^{[ 9 ]} Eine Teilimplementierung von Aktoren wurde unter dem Namen Planner-73 (später PLASMA) entwickelt. Steele, damals Doktorand am MIT, hatte diese Entwicklungen verfolgt, und er und Sussman beschlossen, eine Version des Aktormodells in ihrem eigenen, auf Maclisp basierenden „Tiny Lisp“ zu implementieren , um das Modell besser zu verstehen. Darauf aufbauend begannen sie, Mechanismen zur Erstellung von Aktoren und zum Versenden von Nachrichten zu entwickeln. ^{[ 10 ]}

Die Verwendung des lexikalischen Gültigkeitsbereichs in PLASMA ähnelte dem Lambda-Kalkül . Sussman und Steele beschlossen, Aktoren im Lambda-Kalkül zu modellieren. Sie nannten ihr Modellierungssystem Schemer und änderten es später in Scheme, um die Sechs-Zeichen-Beschränkung des ITS- Dateisystems auf ihrer DEC PDP-10 einzuhalten . Bald kamen sie zu dem Schluss, dass Aktoren im Wesentlichen Closures sind, die nie zurückkehren, sondern stattdessen eine Fortsetzung aufrufen . Daher entschieden sie, dass Closure und Aktor für ihre Untersuchung im Wesentlichen identische Konzepte sind. Sie eliminierten den ihrer Ansicht nach redundanten Code und entdeckten dabei, dass sie einen sehr kleinen und leistungsfähigen Lisp-Dialekt geschrieben hatten. Hewitt blieb kritisch gegenüber der „komplexen Kontrollstruktur“ in Scheme ^{[ 11 ] [ 12 ]} und betrachtete die in der Scheme-Implementierung verwendeten Primitiven (z. B. `int` START!PROCESS, STOP!PROCESS`string` und ` EVALUATE!UNINTERRUPTIBLYstring`) als Rückschritt.

25 Jahre später, 1998, stellten Sussman und Steele fest, dass der Minimalismus von Scheme kein bewusstes Designziel, sondern vielmehr ein unbeabsichtigtes Ergebnis des Designprozesses war. „Wir wollten eigentlich etwas Kompliziertes entwickeln und entdeckten dabei zufällig, dass wir versehentlich etwas entworfen hatten, das all unsere Ziele erfüllte, aber viel einfacher war als beabsichtigt … Wir erkannten, dass der Lambda-Kalkül – ein kleiner, einfacher Formalismus – als Kern einer leistungsstarken und ausdrucksstarken Programmiersprache dienen konnte.“ ^{[ 10 ]}

Andererseits blieb Hewitt dem Lambda-Kalkül als Grundlage für Berechnungen gegenüber kritisch und schrieb: „Tatsächlich kann der λ-Kalkül zwar einige Arten sequentieller und paralleler Kontrollstrukturen ausdrücken, aber im Allgemeinen nicht die im Aktormodell ausgedrückte Nebenläufigkeit. Das Aktormodell hingegen kann alles im λ-Kalkül und mehr ausdrücken.“ Er kritisierte auch Aspekte von Scheme, die sich vom Lambda-Kalkül ableiten, wie die Abhängigkeit von Fortsetzungsfunktionen und das Fehlen von Ausnahmen. ^{[ 13 ]}

Zwischen 1975 und 1980 arbeiteten Sussman und Steele an der Weiterentwicklung ihrer Ideen zur Verwendung des Lambda-Kalküls, Fortsetzungen und anderer fortgeschrittener Programmierkonzepte wie der Optimierung der Endrekursion und veröffentlichten diese in einer Reihe von KI-Memos , die zusammenfassend als Lambda Papers bezeichnet wurden . ^{[ 14 ]}

• 1975: Scheme: Ein Interpreter für den erweiterten Lambda-Kalkül
• 1976: Lambda: Das ultimative Gebot
• 1976: Lambda: Die ultimative Deklarativfunktion
• 1977: Die Entlarvung des Mythos vom „teuren Prozeduraufruf“ oder: Prozeduraufruf-Implementierungen, die als schädlich gelten, oder: Lambda: Die ultimative GOTO-Funktion
• 1978: Die Kunst des Interpreten oder der Modularitätskomplex (Teile Null, Eins und Zwei)
• 1978: RABBIT: Ein Compiler für SCHEME
• 1979: Entwurf von LISP-basierten Prozessoren, oder SCHEME: Ein Dialekt von LISP, oder Finite Memories Considered Harmful, oder LAMBDA: Der ultimative Opcode
• 1980: Compileroptimierung basierend auf der Betrachtung von LAMBDA als RENAME + GOTO
• 1980: Entwurf eines Lisp-basierten Prozessors

Scheme war der erste Lisp-Dialekt, der sich für lexikalischen Gültigkeitsbereich entschied . Es war auch eine der ersten Programmiersprachen nach Reynolds' Definitional Language ^{[ 15 ]} , die First-Class -Continuations unterstützte . Es hatte großen Einfluss auf die Bemühungen, die zur Entwicklung seiner Schwestersprache Common Lisp führten , zu der Guy Steele mitwirkte. ^{[ 16 ]}

Die Programmiersprache Scheme ist im offiziellen Standard des Institute of Electrical and Electronics Engineers (IEEE) ^{[ 17 ]} und im De-facto-Standard „ Revised ^Report on the Algorithmic Language Scheme“ ( RnRS ) standardisiert . Der am weitesten verbreitete Standard ist R5RS (1998) ^{[ 18 ]} , und ein neuer Standard, R6RS [ ^{19 ],} wurde 2007 ratifiziert. ^{[ 20 ]} Neben den RnRS-Standards existieren auch Scheme Requests for Implementation- Dokumente ⁽ SRI ), die zusätzliche Bibliotheken enthalten, welche von Scheme-Implementierungen hinzugefügt werden können.