Ewaluator metakołowy

W informatyce meta -kołowy oceniający ( MCE ) lub tłumacz meta-kołowy ( MCI ) jest tłumaczem , który definiuje każdą cechę języka interpretowanego przy użyciu podobnej funkcji języka gospodarza tłumacza. Na przykład interpretacja aplikacji lambda może być zaimplementowana przy użyciu funkcji application. Ocena meta-okrągła jest najbardziej widoczna w kontekście Lispa . Samotłumacz _ jest tłumaczem metakołowym, w którym język tłumaczony jest prawie identyczny z językiem gospodarza; te dwa terminy są często używane jako synonimy.

Historia

Rozprawa Corrado Böhma opisuje projekt samoobsługowego kompilatora. Ze względu na trudność kompilacji funkcji wyższego rzędu wiele języków zostało zamiast tego zdefiniowanych za pomocą tłumaczy, przede wszystkim Lispa. Sam termin został ukuty przez Johna C. Reynoldsa i spopularyzowany dzięki jego użyciu w książce Structure and Interpretation of Computer Programs .

Tłumacze sami

Tłumacz własny to tłumacz metakołowy, w którym język gospodarza jest również językiem tłumaczonym. Tłumacz automatyczny pełni funkcję uniwersalną dla danego języka i może być pomocny w nauce niektórych aspektów języka. Samodzielny interpretator zapewni okrągłą, bezsensowną definicję większości konstrukcji językowych, a tym samym zapewni niewielki wgląd w semantykę języka interpretowanego, na przykład strategię oceny . Zajęcie się tymi kwestiami prowadzi do powstania bardziej ogólnego pojęcia „tłumacza definicji”.

Samodzielna interpretacja w totalnych językach programowania

Wszystkie funkcjonalne języki programowania, które są silnie normalizujące, nie mogą być kompletne Turinga , w przeciwnym razie można by rozwiązać problem zatrzymania, sprawdzając, czy program sprawdza typ. Oznacza to, że istnieją obliczalne funkcje, których nie można zdefiniować w całym języku. W szczególności niemożliwe jest zdefiniowanie samointerpretatora w całkowitym języku programowania, na przykład w jakimkolwiek typowanym rachunku lambda , takim jak rachunek lambda o prostym typie , System F Jeana-Yvesa Girarda lub Thierry Coquand rachunek konstrukcji . Tutaj przez „autointerpretator” rozumiemy program, który przyjmuje reprezentację terminu źródłowego w jakimś prostym formacie (takim jak ciąg znaków) i zwraca reprezentację odpowiedniego znormalizowanego terminu. Ten wynik niemożliwości nie dotyczy innych definicji „autointerpretatora”. Na przykład niektórzy autorzy określali funkcje typu ${\ Displaystyle$ autointerpretatory, gdzie jest typem $\ pi \, \ tau \ do \ tau$ z reprezentacji ${\ displaystyle \ tau}$ -wpisane terminy. Aby uniknąć nieporozumień, będziemy odnosić się do tych funkcji jako do samorozpoznawania . Brown i Palsberg wykazali, że osoby samorozpoznające można zdefiniować w kilku językach silnie normalizujących, w tym w Systemie F i Systemie F _ω . Okazało się to możliwe, ponieważ typy zakodowanych terminów odzwierciedlane w typach ich reprezentacji uniemożliwiają skonstruowanie argumentu diagonalnego . W swoim artykule Brown i Palsberg twierdzą, że obalają „konwencjonalną mądrość”, że samointerpretacja jest niemożliwa (i odwołują się do Wikipedii jako przykładu konwencjonalnej mądrości), ale tak naprawdę obalają niemożność samorozpoznania, odrębne pojęcie. W swojej dalszej pracy przechodzą na bardziej szczegółową terminologię „samorozpoznającą”, w szczególności odróżniając ją od „samooceny”, typu π τ → π $pi \, \ tau \ do \pi \,\tau }$ . Uznają również, że wdrożenie samooceny wydaje się trudniejsze niż samorozpoznanie, i pozostawiają wdrożenie tej pierwszej w silnie normalizującym języku jako problem otwarty.

Używa

W połączeniu z istniejącą implementacją języka, tłumacze meta-kołowe zapewniają podstawowy system, z którego można rozszerzyć język, albo w górę, dodając więcej funkcji, albo w dół, kompilując funkcje zamiast ich interpretacji. Są również przydatne do pisania narzędzi ściśle zintegrowanych z językiem programowania, takich jak zaawansowane debuggery. ^{[ Potrzebne źródło ]} Język zaprojektowany z myślą o implementacji meta-kołowej jest często bardziej odpowiedni do budowania języków w ogóle, nawet tych całkowicie różnych od języka hosta. ^{[ potrzebne źródło ]}

Przykłady

Wiele języków ma jedną lub więcej implementacji metakołowych. Poniżej znajduje się częściowa lista.

Niektóre języki z implementacją metakołową zaprojektowaną od dołu do góry, w zgrupowanym porządku chronologicznym:

Lisp , 1958
- Schemat , 1975
  - Picco , 1997
  - ActorScript, 2009?
- Clojure , 2007
Czwarty , 1968
- PostScript , 1982
Prolog , 1972
TeX , oparty na pierwotnym TeX-u, 1978
Smalltalk , 1980
Rebol , 1997
- Czerwony , 2011
Czynnik , 2003

Niektóre języki z implementacją metacykliczną za pośrednictwem stron trzecich:

Java przez Jikes RVM , Squawk , Maxine lub GraalVM's Espresso
Scala przez Metascalę
JavaScript przez Narcissus lub JS-Interpreter
Oz przez Glindę
Pythona przez PyPy
Ruby przez Rubiniusa
Lua przez Metaluę

Zobacz też

Linki zewnętrzne

Struktura i interpretacja programów komputerowych (SICP) , wersja online pełnej książki, dostęp 2009-01-18.
Metascala