Historia języka programowania Scheme - History of the Scheme programming language

Historia języka programowania Scheme rozpoczyna się wraz z rozwojem wcześniejszych członków rodziny języków Lisp w drugiej połowie XX wieku. W okresie projektowania i rozwoju Scheme projektanci języków Guy L. Steele i Gerald Jay Sussman wydali wpływową serię notatek AI Massachusetts Institute of Technology (MIT), znaną jako Lambda Papers (1975-1980). Zaowocowało to wzrostem popularności języka i erą standaryzacji począwszy od 1990 roku. Znaczna część historii Scheme została udokumentowana przez samych programistów.

Pre-historia

Na rozwój Scheme duży wpływ mieli dwaj poprzednicy, którzy różnili się od siebie: Lisp zapewnił ogólną semantykę i składnię, a ALGOL zapewnił zakres leksykalny i strukturę blokową. Schemat jest dialektem Lispu, ale Lisp ewoluował; dialekty Lispu, z których wyewoluował Scheme – chociaż były wówczas w głównym nurcie – różnią się zupełnie od jakiegokolwiek współczesnego Lispu.

Seplenienie

Lisp został wynaleziony przez Johna McCarthy'ego w 1958 roku, gdy pracował w Massachusetts Institute of Technology (MIT). McCarthy opublikował swój projekt w artykule w Communications of the ACM w 1960 roku, zatytułowanym „Recursive Functions of Symbolic Expressions and Their Computing by Machine, Part I” (Część II nigdy nie została opublikowana). Pokazał, że za pomocą kilku prostych operatorów i notacji funkcji można zbudować język Turinga dla algorytmów.

Użycie wyrażeń s, które charakteryzują składnię języka Lisp, początkowo miało być środkiem tymczasowym w oczekiwaniu na rozwój języka wykorzystującego to, co McCarthy nazwał „ m-wyrażeniami ”. Na przykład wyrażenie m car[cons[A,B]]jest równoważne z wyrażeniem s (car (cons A B)). Wyrażenia S okazały się jednak popularne, a wiele prób wprowadzenia wyrażeń m nie zostało przyjętych.

Pierwsza implementacja Lispa została wykonana na IBM 704 przez Steve'a Russella , który przeczytał artykuł McCarthy'ego i zakodował funkcję eval, którą opisał w kodzie maszynowym. Znajome (ale zagadkowe dla nowicjuszy) nazwy CAR i CDR używane w Lispie do opisu elementu nagłówka listy i jej ogona, wyewoluowały z dwóch poleceń języka asemblera IBM 704 : Contents of Address Register i Contents of Decrement Register, z których każda została zwrócona zawartość 15-bitowego rejestru odpowiadającego segmentom 36-bitowego słowa instrukcji IBM 704 .

Pierwszy kompletny kompilator Lisp, napisany w Lispie, został zaimplementowany w 1962 roku przez Tima Harta i Mike'a Levina z MIT. Ten kompilator wprowadził model Lisp kompilacji przyrostowej, w którym skompilowane i zinterpretowane funkcje mogą się swobodnie mieszać.

Dwa warianty Lispa najbardziej znaczące w rozwoju Scheme zostały opracowane w MIT: LISP 1.5 opracowany przez McCarthy'ego i innych oraz Maclisp – opracowany dla MIT Project MAC , bezpośredni potomek LISP 1.5. który działał na systemach PDP-10 i Multics .

Od samego początku Lisp był ściśle związany ze społecznością badawczą nad sztuczną inteligencją (AI), zwłaszcza nad PDP-10 . Na 36-bitowy rozmiar słowa w PDP-6 i PDP-10 wpłynęła użyteczność posiadania dwóch 18-bitowych wskaźników Lisp w jednym słowie.

ALGOL

ALGOL 58 , pierwotnie nazywany IAL od „International Algorithmic Language”, został opracowany wspólnie przez komitet europejskich i amerykańskich informatyków na spotkaniu w 1958 w ETH Zurich . ALGOL 60 , późniejsza wersja opracowana na spotkaniu ALGOL 60 w Paryżu i obecnie powszechnie nazywana ALGOL , stała się standardem publikacji algorytmów i miała głęboki wpływ na przyszły rozwój języka, pomimo braku sukcesu komercyjnego języka i jego ograniczeń. Tony Hoare zauważył: „Oto język tak daleko wyprzedzający swoje czasy, że był nie tylko ulepszeniem swoich poprzedników, ale także prawie wszystkich jego następców”.

ALGOL wprowadził wykorzystanie struktury blokowej i zakresu leksykalnego. Znany był również z trudnego mechanizmu przekazywania parametrów domyślnych wywołania po nazwie , który został zdefiniowany tak, aby podczas wykonywania procedury lub funkcji wymagać tekstowego podstawienia wyrażenia reprezentującego parametr roboczy w miejsce parametru formalnego, powodując jego ponowne -oceniany za każdym razem, gdy jest odwoływany podczas wykonywania. Realizatorzy ALGOL opracowali mechanizm, który nazwali thunk , który przechwytuje kontekst parametru roboczego, umożliwiając jego ocenę podczas wykonywania procedury lub funkcji.

Carl Hewitt, model aktora i narodziny Scheme

W 1971 roku Sussman, Drew McDermott i Eugene Charniak opracowali system o nazwie Micro-Planner, który był częściową i nieco niezadowalającą implementacją ambitnego projektu Carla Hewitta Planner . Sussman i Hewitt pracowali razem z innymi nad Muddle, później przemianowanym na MDL , rozszerzonym Lispie, który stanowił element projektu Hewitta. Drew McDermott i Sussman w 1972 opracowali oparty na Lisp język Conniver , który zrewidował użycie automatycznego śledzenia wstecznego w Planner, które ich zdaniem było bezproduktywne. Hewitt miał wątpliwości, czy „włochata struktura kontrolna” w Conniver była rozwiązaniem problemów z Plannerem. Pat Hayes zauważył: „Ich rozwiązanie [Sussman i McDermott], dające użytkownikowi dostęp do prymitywów implementacji Plannera, jest jednak czymś w rodzaju kroku wstecznego (jaka jest semantyka Connivera?)”

W listopadzie 1972 roku Hewitt i jego uczniowie wymyślili model obliczeń Aktora jako rozwiązanie problemów z Plannerem. Opracowano częściową implementację Actorsów o nazwie Planner-73 (później PLASMA). Steele, wówczas absolwent MIT, śledził te zmiany i wraz z Sussmanem postanowili wdrożyć wersję modelu Aktora we własnym „małym Lispie” opracowanym na Maclisp , aby lepiej go zrozumieć. Na tej podstawie zaczęli rozwijać mechanizmy tworzenia aktorów i wysyłania wiadomości.

Wykorzystanie zakresu leksykalnego przez PLAZMĘ było podobne do rachunku lambda . Sussman i Steele postanowili spróbować modelować aktorów w rachunku lambda. Nazwali swój system modelowania Schemer, ostatecznie zmieniając go na Scheme, aby dopasować go do ograniczenia sześciu znaków w systemie plików ITS na swoim DEC PDP-10 . Wkrótce doszli do wniosku, że Aktorzy są zasadniczo zamknięciami, które nigdy nie powracają, ale zamiast tego wywołują kontynuację , i dlatego zdecydowali, że zamknięcie i Aktor są, dla celów ich badania, zasadniczo identycznymi koncepcjami. Wyeliminowali to, co uważali za zbędny kod iw tym momencie odkryli, że napisali bardzo mały i sprawny dialekt Lispu. Hewitt pozostawał krytyczny wobec „włochatej struktury kontrolnej” w Scheme i uważał prymitywy (np. START!PROCESS, STOP!PROCESS, i EVALUATE!UNINTERRUPTIBLY) użyte w implementacji Scheme za krok wstecz.

25 lat później, w 1998 roku, Sussman i Steele stwierdzili, że minimalizm Scheme nie jest świadomym celem projektowym, ale raczej niezamierzonym wynikiem procesu projektowania. „Właściwie próbowaliśmy zbudować coś skomplikowanego i odkryliśmy, przypadkowo, że przypadkowo zaprojektowaliśmy coś, co spełniło wszystkie nasze cele, ale było znacznie prostsze niż zamierzaliśmy… zdaliśmy sobie sprawę, że rachunek lambda – mały, prosty formalizm – może służyć jako rdzeń potężnego i ekspresyjnego języka programowania”.

Z drugiej strony, Hewitt pozostał krytyczny wobec rachunku lambda jako podstawy do pisania obliczeń „Rzeczywista sytuacja jest taka, że rachunek λ jest w stanie wyrazić pewne rodzaje sekwencyjnych i równoległych struktur kontrolnych, ale generalnie nie współbieżność wyrażoną w model Aktora. Z drugiej strony model Aktora jest w stanie wyrazić wszystko w rachunku λ i nie tylko”. Odniósł się również krytycznie do aspektów Scheme, które wywodzą się z rachunku lambda, takich jak poleganie na funkcjach kontynuacji i brak wyjątków.

Dokumenty Lambda

W latach 1975-1980 Sussman i Steele pracowali nad rozwinięciem swoich pomysłów dotyczących korzystania z rachunku lambda, kontynuacji i innych zaawansowanych koncepcji programowania, takich jak optymalizacja rekurencji ogona , i opublikowali je w serii notatek AI, które zostały wspólnie nazwane Lambda Papers .

Lista artykułów

1975: Schemat: interpreter rozszerzonego rachunku lambda
1976: Lambda: ostateczny imperatyw
1976: Lambda: ostateczny deklaratywny
1977: Obalanie mitu „kosztownego wywoływania procedur”, czyli implementacji wywoływania procedur uważanych za szkodliwe, czyli lambda: ostateczne GOTO
1978: Sztuka tłumacza lub kompleks modułowości (Części zero, pierwsza i druga)
1978: RABBIT: kompilator SCHEME
1979: Projektowanie procesorów opartych na LISP lub SCHEME: dialekt LISP lub skończone wspomnienia uważane za szkodliwe lub LAMBDA: ostateczny kod operacyjny
1980: Optymalizacja kompilatora na podstawie wyświetlania LAMBDA jako RENAME + GOTO
1980: Projekt procesora opartego na Lispie

Wpływ

Schemat był pierwszym dialektem Lispa, który wybrał zakres leksykalny . Był to również jeden z pierwszych języków programowania po języku definicyjnym Reynolda, który wspierał kontynuacje pierwszej klasy . Miał duży wpływ na wysiłek, który doprowadził do rozwoju jej siostrzanego języka, Common Lisp , w którym współpracował Guy Steele.

Normalizacja

Język programu jest ustandaryzowany w oficjalnym standardzie Instytutu Inżynierów Elektryków i Elektroników (IEEE) oraz w de facto standardzie zwanym Revised ⁿ Report on the Algorithmic Language Scheme (R n RS). Najszerzej wdrażanym standardem jest R5RS (1998), a nowy standard, R6RS , został ratyfikowany w 2007 roku.

1955	1965	1970	1975	1980	1985	1990	1995	2000	2005	2010
LISP 1, 1,5, LISP 2 ^(opuszczony)
	Maclisp
		Interlisp
		MDL (język programowania)
			Lisp Maszyna Lisp
			Schemat				R5RS		R6RS	R7RS mały
			ZERO
				ZIL (język implementacji Zork)
				Franz Lisp
				Wspólne seplenienie
				Le Lisp
					T
					Schemat Cheza
					Emacs Lisp
					AutoLISP
					PicoLisp
						EuLisp
						ISLISP
						OpenLisp
						Schemat PLT				Rakieta
						GNU Guile
								Wizualny LISP
									Clojure
									Łuk
									LFE
										Hy

Languages

In other projects