Jakie właściwości języka programowania uniemożliwiają kompilację?

71

Pytanie:

„Niektóre właściwości języka programowania mogą wymagać, aby jedynym sposobem na napisanie w nim kodu jest interpretacja. Innymi słowy, kompilacja do natywnego kodu maszynowego tradycyjnego procesora nie jest możliwa. Jakie są te właściwości?”

Kompilatory: zasady i praktyka Parag H. Dave i Himanshu B. Dave (2 maja 2012)

Książka nie daje żadnych wskazówek na temat odpowiedzi. Próbowałem znaleźć odpowiedź na Koncepcje języków programowania (SEBESTA), ale bezskutecznie. Wyszukiwania w sieci również były mało przydatne. Czy masz jakieś wskazówki?

Anderson Nascimento Nunes
źródło
31
Słynie, że Perla nie można nawet przeanalizować . Poza tym twierdzenie wydaje się trywialnie błędne bez dalszych założeń: jeśli istnieje interpreter, zawsze mogę umieścić interpreter i kod w jednym pliku wykonywalnym, voila.
Raphael
4
@Raphael: Fajny pomysł, ale ... 1) Zakładasz, że kod jest dostępny przed uruchomieniem. Nie dotyczy to użycia interaktywnego. Jasne, możesz użyć kompilacji just-in-time do natywnego kodu instrukcji bash lub zawartości stosu PostScript, ale to dość szalony pomysł. 2) Twój pomysł nie kompiluje kodu: pakiet nie jest skompilowaną wersją kodu, ale nadal interpreterem kodu.
reinierpost
7
W dawnych dobrych czasach miałem samodzielną edycję programów gwbasic (gwbasic przechowuje podstawowe programy w formie kodu bajtowego). Obecnie nie mogę wymyślić rozsądnego sposobu na skompilowanie ich do natywnego kodu maszynowego przy jednoczesnym zachowaniu możliwości samodzielnej edycji.
PlasmaHH
15
@PlasmaHH: Kod samodopasowujący sięga 1948 r. Pierwszy kompilator został napisany w 1952 r. Koncepcja natywnego kodu została wynaleziona w natywnym kodzie maszynowym.
Mooing Duck
10
@reinierpost Raphael zajmuje teoretyczne stanowisko w tej sprawie. Ma tę zaletę, że pokazuje koncepcyjne ograniczenia pytania. Kompilacja jest tłumaczeniem z języka S na język T. Język T może być rozszerzeniem S, do którego można dodać kod tłumaczący w innym języku. Tak więc łączenie S i jego tłumacza jest programem w języku T. Wydaje się absurdalne dla inżyniera, ale pokazuje, że sformułowanie pytania nie jest łatwe. Jak odróżnić akceptowalny proces kompilacji od niedopuszczalnego (takiego jak Raphael) z inżynierskiego punktu widzenia?
babou

Odpowiedzi:

61

Różnica między kodem interpretowanym a skompilowanym jest prawdopodobnie fikcją, jak podkreśla komentarz Raphaela :

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

Faktem jest, że kod jest zawsze interpretowany przez oprogramowanie, sprzęt lub kombinację obu tych elementów, a proces kompilacji nie jest w stanie stwierdzić, który z nich będzie.

To, co postrzegasz jako kompilację, to proces tłumaczenia z jednego języka (dla źródła) na inny język (dla celu). I interpreter dla jest zazwyczaj różni się od tłumacza T .T SSTST

Skompilowany program jest tłumaczony z jednej formy syntaktycznej na inną formę syntaktyczną P T , tak, że biorąc pod uwagę zamierzoną semantykę języków S i T , P S i P T mają takie samo zachowanie obliczeniowe, do kilku rzeczy, które zazwyczaj próbują zmienić, ewentualnie zoptymalizować, na przykład złożoność lub prostą wydajność (czas, przestrzeń, powierzchnia, zużycie energii). Staram się nie mówić o równoważności funkcjonalnej, ponieważ wymagałoby to precyzyjnych definicji.PSP.T.S.T.P.S.P.T.

Niektóre kompilatory zostały w rzeczywistości wykorzystane po prostu do zmniejszenia rozmiaru kodu, a nie do „poprawienia” wykonania. Tak było w przypadku języka używanego w systemie Plato (choć nie nazywali go kompilacją).

Można rozważyć kod pełni skompilowane, jeśli po procesie kompilacji, których już nie potrzebujemy tłumacza . Przynajmniej jest to jedyny sposób, w jaki mogę odczytać twoje pytanie, jako pytanie inżynieryjne, a nie teoretyczne (ponieważ teoretycznie zawsze mogę przebudować tłumacza).S.

Jedną z rzeczy, które mogą powodować problemy, jest meta-okólnik . Wtedy program będzie manipulował strukturami składniowymi we własnym języku źródłowym , tworząc fragment programu, który jest następnie interpretowany tak, jakby był częścią oryginalnego programu. Ponieważ możesz tworzyć dowolne fragmenty programu w języku S w wyniku dowolnego obliczenia manipulującego bezsensownymi fragmentami składniowymi, zgaduję, że możesz prawie uniemożliwić (z technicznego punktu widzenia) skompilowanie programu do języka , tak aby teraz generuje fragmenty . Stąd potrzebny będzie interpreter dla lub przynajmniej kompilator od doS.S.T S S T ST.T.S.S.T. do kompilacji w locie wygenerowanych fragmentów w (patrz także ten dokument ).S.

Ale nie jestem pewien, jak można to właściwie sformalizować (i nie mam na to teraz czasu). I niemożliwe jest wielkie słowo dla kwestii, które nie są sformalizowane.

Dalsze uwagi

Dodano po 36 godzinach. Możesz pominąć tę bardzo długą kontynuację.

Wiele komentarzy do tego pytania pokazuje dwa poglądy na problem: pogląd teoretyczny, który postrzega go jako pozbawiony znaczenia, oraz pogląd inżynieryjny, który niestety nie jest tak łatwo sformalizowany.

Istnieje wiele sposobów spojrzenia na interpretację i kompilację, a ja postaram się naszkicować kilka. Spróbuję być tak nieformalny, jak tylko potrafię

Schemat nagrobków

Jedną z wczesnych formalizacji (od początku lat 60. do końca 1990) są diagramy T lub Tombstone . Te diagramy przedstawiają w możliwych do skomponowania elementach graficznych język implementacji interpretera lub kompilatora, język źródłowy jest interpretowany lub kompilowany, a język docelowy w przypadku kompilatorów. Bardziej rozbudowane wersje mogą dodawać atrybuty. Te reprezentacje graficzne można postrzegać jako aksjomaty, reguły wnioskowania, przydatne do mechanicznego uzyskiwania generacji procesora z dowodu ich istnienia z aksjomatów à la Curry-Howard (choć nie jestem pewien, czy zrobiono to w latach sześćdziesiątych :).

Częściowa ocena

Innym interesującym poglądem jest paradygmat oceny częściowej . Przyjmuję prosty pogląd na programy jako rodzaj implementacji funkcji, która oblicza odpowiedź na podstawie niektórych danych wejściowych. Następnie tłumacza dla języka S to program, który ma program p S napisane w S i danych d dla tego programu, i oblicza wynik Według semantyki S . Częściowa ocena jest techniką specjalizujący program dwoma argumentami 1 i 2 , gdy tylko jeden argument, powiedzmy do 1jaS.S.pS.S.reS.za1za2)za1, jest znany. Celem jest szybsza ocena, gdy w końcu otrzymasz drugi argument . Jest to szczególnie przydatne, jeśli 2 zmienia się częściej niż o 1 jako koszt częściowej oceny z pomocą 1 mogą być amortyzowane wszystkich obliczeń, gdzie tylko 2 zmienia się.za2)za2)za1za1za2)

Jest to częsta sytuacja w projektowaniu algorytmów (często temat pierwszego komentarza na temat SE-CS), kiedy pewna bardziej statyczna część danych jest wstępnie przetwarzana, tak że koszt wstępnego przetwarzania może być amortyzowany we wszystkich aplikacjach algorytmu z bardziej zmiennymi częściami danych wejściowych.

Taka jest również sytuacja tłumaczy, ponieważ pierwszym argumentem jest program do wykonania, który zwykle jest wykonywany wiele razy z różnymi danymi (lub ma wiele części wykonywanych z różnymi danymi). Dlatego naturalną ideą stało się specjalizowanie tłumacza do szybszej oceny danego programu poprzez częściową ocenę go w tym programie jako pierwszy argument. Może to być postrzegane jako sposób kompilacji programu, i przeprowadzono znaczące prace badawcze dotyczące kompilacji poprzez częściową ocenę interpretera na jego pierwszym argumencie (programowym).

Twierdzenie Smn

Zaletą częściowego podejścia do oceny jest to, że zakorzenia się ona w teorii (choć teoria może być kłamcą), zwłaszcza w twierdzeniu Kleene'a Smn . Próbuję tu przedstawić intuicyjnie, mając nadzieję, że nie zdenerwuje to czystych teoretyków.

Biorąc pod uwagę numerację Gödela funkcji rekurencyjnych, możesz postrzegać φ jako swój sprzęt, tak że biorąc pod uwagę numer Gödela p (odczyt kodu obiektowego ) programu φ p jest funkcją zdefiniowaną przez p (tj. Obliczoną przez kod obiektu na twoim sprzęcie ).φφpφpp

W najprostszej formie twierdzenie to znajduje się w Wikipedii w następujący sposób (do niewielkiej zmiany notacji):

Biorąc pod uwagę numerację Gödela funkcji rekurencyjnych, istnieje pierwotna funkcja rekurencyjna σ dwóch argumentów o następującej właściwości: dla każdej liczby Gödela q częściowej funkcji obliczalnej f z dwoma argumentami wyrażenia φ σ ( q , x ) ( y ) i f ( x , y ) określa się dla tych samych kombinacji liczb naturalnych, x i Y , a ich wartości są takie same dla każdej takiej kombinacji. Innymi słowy, następująca ekstensywna równość funkcji obowiązuje dla każdegoφσqfaφσ(q,x)(y)fa(x,y)xy : xφσ(q,x)λy.φq(x,y).

Teraz, biorąc za interpreter I S , x jako kod źródłowy programu p S , ay jako dane d dla tego programu, możemy napisać: qjaS.xpS.ydφσ(IS,pS)λd.φIS(pS,d).

może być postrzegana jako wykonanie tłumacza I S na sprzęcie, czyli jako czarnej skrzynki gotowy do interpretowania programów napisanych w języku S .φISISS

Funkcja może być postrzegana jako funkcja, która specjalizuje interpreter I S dla programu P S , tak jak w częściowej ocenie. Zatem liczba Gödel σ ( I S , P S ) można zobaczyć, że zawiera kod wynikowy jest zestawiane wersja programu s S .σISPSσ(IS,pS)pS

Więc funkcja może być postrzegane jako funkcja, która przyjmuje jako argument kod źródłowy programu q S napisany w języku S i zwraca wersję kodu obiektowego dla tego programu. Więc C S jest zwykle nazywane kompilator.CS=λqS.σ((IS,qS)qS.S.doS.

Kilka wniosków

Jednak, jak powiedziałem: „teoria może być kłamcą”, a nawet może wydawać się taką. Problem polega na tym, że nic nie wiemy o funkcji . W rzeczywistości istnieje wiele takich funkcji i sądzę, że dowód twierdzenia może posłużyć się bardzo prostą definicją, która z technicznego punktu widzenia może nie być lepsza niż rozwiązanie zaproponowane przez Raphaela: po prostu połączyć kod źródłowy q S do interpretera I S . Zawsze można to zrobić, abyśmy mogli powiedzieć: kompilacja jest zawsze możliwa.σqS.jaS.

Sformalizowanie bardziej restrykcyjnego pojęcia, czym jest kompilator, wymagałoby bardziej subtelnego podejścia teoretycznego. Nie wiem, co można było zrobić w tym kierunku. Bardzo realna praca nad częściową oceną jest bardziej realistyczna z inżynieryjnego punktu widzenia. Istnieją oczywiście inne techniki pisania kompilatorów, w tym ekstrakcja programów z dowodu ich specyfikacji, opracowana w kontekście teorii typów, w oparciu o izomorfizm Curry-Howarda (ale wychodzę poza zakres moich kompetencji) .

Moim celem tutaj było wykazanie, że uwaga Rafaela nie jest „szalona”, ale rozsądne przypomnienie, że rzeczy nie są oczywiste, a nawet proste. Mówienie, że coś jest niemożliwe, jest mocnym stwierdzeniem, które wymaga precyzyjnych definicji i dowodu, choćby po to, aby dokładnie zrozumieć, w jaki sposób i dlaczego jest to niemożliwe . Ale zbudowanie odpowiedniej formalizacji, aby wyrazić taki dowód, może być dość trudne.

To powiedziawszy, nawet jeśli konkretnej funkcji nie da się skompilować, w sensie zrozumiałym dla inżynierów, standardowe techniki kompilacji można zawsze zastosować do części programów, które nie używają takiej funkcji, jak zauważa odpowiedź Gillesa.

Aby podążać za kluczowymi uwagami Gillesa, że ​​w zależności od języka pewne rzeczy mogą być zrobione w czasie kompilacji, podczas gdy inne muszą być wykonane w czasie wykonywania, a zatem wymagają określonego kodu, widzimy, że koncepcja kompilacji jest w rzeczywistości źle zdefiniowany i prawdopodobnie nie da się go zdefiniować w zadowalający sposób. Kompilacja jest jedynie procesem optymalizacji, co starałem się pokazać w częściowej części oceny , gdy porównałem ją ze statycznym przetwarzaniem danych w niektórych algorytmach.

Jako złożony proces optymalizacji koncepcja kompilacji należy do kontinuum. W zależności od charakterystyki języka lub programu niektóre informacje mogą być dostępne statycznie i pozwalają na lepszą optymalizację. Inne rzeczy należy odłożyć na czas wykonywania. Kiedy wszystko idzie naprawdę źle, wszystko musi być zrobione w czasie wykonywania przynajmniej dla niektórych części programu, a dołączenie kodu źródłowego do interpretera to wszystko, co możesz zrobić. Więc to wiązanie jest tylko dolną częścią tego kontinuum kompilacji. Wiele badań nad kompilatorami dotyczy znalezienia sposobów na statyczne wykonanie tego, co kiedyś robiono dynamicznie. Dobrym przykładem wydaje się zbieranie śmieci w czasie kompilacji.

Zauważ, że powiedzenie, że proces kompilacji powinien generować kod maszynowy, nie jest pomocne. Właśnie to może zrobić pakiet, ponieważ interpreter jest kodem maszynowym (cóż, kompilacja krzyżowa może stać się nieco bardziej złożona).

Babou
źródło
3
niemożliwe to duże słowo” Bardzo, bardzo duże słowo. =)
Brian S
3
Jeśli zdefiniuje się „kompilację” w odniesieniu do sekwencji kroków, które odbywają się całkowicie, zanim program wykonawczy otrzyma swoje pierwsze wejście, i interpretacja jako proces przepływu programu sterującego danymi za pomocą środków, które nie są częścią abstrakcyjnego modelu maszyny programu , a następnie, aby język został skompilowany, kompilator musi mieć możliwość zidentyfikowania przed rozpoczęciem wykonywania każdego możliwego znaczenia, jakie może mieć konstrukcja języka. W językach, w których konstrukcja języka może mieć nieograniczoną liczbę znaczeń, kompilacja nie będzie działać.
supercat
@BrianS Nie, nie jest i nie można udowodnić inaczej;)
Michael Gazonda
@ superupat To wciąż nie jest definicja. Jakie jest „znaczenie” konstrukcji języka?
Rhymoid
Podoba mi się koncepcja oglądania kompilatora / tłumacza jako częściowego wykonania!
Bergi
17

W rzeczywistości nie chodzi o to, żeby kompilacja była niemożliwa . Jeśli język można interpretować¹, to można go skompilować w trywialny sposób, łącząc interpreter z kodem źródłowym. Pytanie dotyczy tego, jakie cechy językowe sprawiają, że jest to jedyny sposób.

Tłumacz to program, który pobiera kod źródłowy jako dane wejściowe i zachowuje się zgodnie z semantyką tego kodu źródłowego. Jeśli konieczny jest tłumacz, oznacza to, że język zawiera sposób interpretacji kodu źródłowego. Ta funkcja nazywa się eval. Jeśli tłumacz jest wymagany jako część środowiska wykonawczego języka, oznacza to, że język obejmuje eval: albo evalistnieje jako prymityw, albo może być w jakiś sposób zakodowany. Języki znane jako języki skryptowe zwykle zawierają pewną evalfunkcję, podobnie jak większość dialektów Lisp .

To, że zawiera język eval, nie oznacza, że ​​nie można go skompilować do kodu natywnego. Na przykład istnieją optymalizujące kompilatory Lisp, które generują dobry kod macierzysty, a mimo to obsługują eval; evalKod można interpretować lub kompilować w locie.

evaljest najlepszą funkcją tłumacza, ale istnieją też inne funkcje, które wymagają czegoś od tłumacza. Rozważ niektóre typowe fazy kompilatora:

  1. Rozbiór gramatyczny zdania
  2. Sprawdzanie typu
  3. Generowanie kodu
  4. Łączenie

evaloznacza, że ​​wszystkie te fazy muszą być wykonywane w czasie wykonywania. Istnieją inne funkcje, które utrudniają kompilację natywną. Biorąc to od dołu, niektóre języki zachęcają do późnego łączenia, zapewniając sposoby, w jakie funkcje (metody, procedury itp.) I zmienne (obiekty, referencje itp.) Mogą zależeć od nielokalnych zmian kodu. Utrudnia to (ale nie jest niemożliwe) generowanie wydajnego kodu natywnego: łatwiej jest przechowywać odwołania do obiektów jako wywołania na maszynie wirtualnej i pozwolić silnikowi VM obsługiwać powiązania w locie.

Ogólnie rzecz biorąc, refleksja powoduje, że języki trudno kompilować do kodu natywnego. Niezwykły prymityw jest ekstremalnym przypadkiem refleksji; wiele języków nie posuwa się tak daleko, ale mimo to semantykę definiuje się w kategoriach maszyny wirtualnej, pozwalając na przykład na kod wyszukujący klasę według nazwy, sprawdzający jej dziedzictwo, wymieniający jej metody, wywołujący metodę itp. Java z JVM i C # z .NET to dwa znane przykłady. Najprostszym sposobem implementacji tych języków jest skompilowanie ich do kodu bajtowego , ale istnieją jednak natywne kompilatory (wiele na czas ), które kompilują przynajmniej fragmenty programu, które nie używają zaawansowanych funkcji odbijania.

Sprawdzanie typu określa, czy program jest poprawny. Różne języki mają różne standardy dotyczące ilości analiz przeprowadzanych w czasie kompilacji w czasie wykonywania: język jest znany jako „typowany statycznie”, jeśli wykonuje wiele kontroli przed uruchomieniem kodu, i „typowany dynamicznie”, jeśli nie. Niektóre języki zawierają funkcję dynamicznego rzutowania lub funkcję odznaczania i sprawdzania typu; te funkcje wymagają osadzenia sprawdzania typu w środowisku wykonawczym. Jest to ortogonalne w stosunku do wymagań dołączania generatora kodu lub interpretera do środowiska wykonawczego.

¹ Ćwiczenie: zdefiniuj język, którego nie można interpretować.

Gilles
źródło
(1) Nie zgadzam się na dołączenie interpretera z kodem źródłowym liczącym się jako kompilacja, ale reszta twojego posta jest doskonała. (2) Całkowicie zgadzam się co do eval. (3) Nie rozumiem, dlaczego odbicie utrudniałoby kompilację języków do kodu natywnego. Cel C ma odbicie i (zakładam) jest zwykle kompilowany. (4) Niejasno powiązana uwaga, metamagiczny szablon C ++ jest zazwyczaj interpretowany, a nie kompilowany, a następnie wykonywany.
Mooing Duck
Właśnie do mnie dotarło, Lua jest skompilowana. Po evalprostu kompiluje kod bajtowy, a następnie jako oddzielny krok plik binarny wykonuje kod bajtowy. I na pewno ma to odzwierciedlenie w skompilowanym pliku binarnym.
Mooing Duck
Na maszynie Harvard Architecture kompilacja powinna dawać kod, do którego nigdy nie trzeba uzyskiwać dostępu jako „danych”. Uważam, że informacje z pliku źródłowego, które ostatecznie muszą być przechowywane jako dane, a nie kod, nie są tak naprawdę „kompilowane”. Nie ma nic złego w tym, że kompilator przyjmuje deklarację jak int arr[] = {1,2,5};i generuje sekcję danych inicjowanych zawierającą [1,2,5], ale nie opisałbym jej zachowania jako tłumaczenia [1,2,5] na kod maszynowy. Jeśli prawie cały program musi zostać zapisany jako dane, to jaka część tego naprawdę byłaby „skompilowana”?
supercat
2
@ superupat To właśnie matematycy i informatycy rozumieją jako trywialny. Pasuje do definicji matematycznej, ale nic ciekawego się nie dzieje.
Gilles
@Gilles: Jeśli termin „kompiluj” jest zarezerwowany do tłumaczenia na instrukcje maszynowe (bez zachowania powiązanych „danych”) i akceptuje to w języku kompilacyjnym, zachowanie deklaracji tablicowej nie polega na „kompilowaniu” tablicy, to w niektórych językach nie można skompilować żadnej znaczącej części kodu.
supercat
13

Myślę, że autorzy zakładają, że kompilacja oznacza

  • program źródłowy nie musi być obecny w czasie wykonywania, oraz
  • kompilator lub interpreter nie musi być obecny w czasie wykonywania.

Oto kilka przykładowych funkcji, które mogłyby sprawić problemy, jeśli nie „niemożliwe” dla takiego schematu:

  1. Jeśli możesz zapytać o wartość zmiennej w czasie wykonywania, odwołując się do zmiennej po jej nazwie (która jest ciągiem), będziesz potrzebować, aby nazwy zmiennych były dostępne w czasie wykonywania.

  2. Jeśli możesz wywołać funkcję / procedurę w czasie wykonywania, odwołując się do jej nazwy (która jest ciągiem), wtedy będziesz potrzebować nazw funkcji / procedury w czasie wykonywania.

  3. Jeśli możesz zbudować program w czasie wykonywania (jako ciąg), powiedzmy, uruchamiając inny program lub czytając go z połączenia sieciowego itp., Wtedy będziesz potrzebował interpretera lub kompilatora w czasie wykonywania, aby uruchom ten program.

Lisp ma wszystkie trzy funkcje. Tak więc systemy Lisp zawsze mają tłumacza załadowanego w czasie wykonywania. Języki Java i C # mają nazwy funkcji dostępne w czasie wykonywania oraz tabele, aby sprawdzić, co one oznaczają. Prawdopodobnie języki takie jak Basic i Python również mają nazwy zmiennych w czasie wykonywania. (Nie jestem tego w 100% pewien).

Uday Reddy
źródło
Co się stanie, jeśli „interpreter” zostanie wkompilowany w kod? Na przykład, używając tabel wysyłania do wywoływania metod wirtualnych, czy są one przykładem interpretacji lub kompilacji?
Erwin Bolwidt,
2
„kompilator lub tłumacz nie musi być obecny w czasie wykonywania”, co? Cóż, jeśli to prawda, to w głębokim sensie C nie można „skompilować” na większości platform. Środowisko wykonawcze C nie ma wiele do zrobienia: uruchamianie, konfigurowanie stosów itp. Oraz zamykanie w celu atexitprzetworzenia. Ale wciąż musi tam być.
pseudonim
1
„Systemy Lisp zawsze mają tłumacza załadowanego w czasie wykonywania.” - Niekoniecznie. Wiele systemów Lisp ma kompilator w czasie wykonywania. Niektórzy nawet nie mają tłumacza.
Jörg W Mittag
2
Niezła próba, ale en.wikipedia.org/wiki/Lisp_machine#Technical_overview . Kompilują Lisp i są zaprojektowane do wydajnego wykonywania wyniku.
Peter A. Schneider,
@Pseudonim: Środowisko wykonawcze C to biblioteka, a nie kompilator ani interpreter.
Mooing Duck
8

możliwe jest, że obecne odpowiedzi „przewyższają” oświadczenie / odpowiedzi. być może to, o czym wspominają autorzy, to następujące zjawisko. wiele języków ma polecenie „ewaluacyjne”; np. patrz eval javascript, a jego zachowanie jest powszechnie badane jako specjalna część teorii CS (np. Lisp). funkcją tego polecenia jest ocena ciągu w kontekście definicji języka. dlatego w rzeczywistości ma podobieństwo do „wbudowanego kompilatora”. kompilator nie może znać zawartości łańcucha, dopóki nie zostanie uruchomiony. dlatego kompilacja wyniku eval do kodu maszynowego nie jest możliwa w czasie kompilacji.

inne odpowiedzi wskazują, że rozróżnienie języków interpretowanych i skompilowanych może w wielu przypadkach znacznie się rozmyć, szczególnie w przypadku bardziej nowoczesnych języków, takich jak Java z kompilatorem „just in time”, czyli „Hotspot” (silniki javascript, np. V8, coraz częściej używają tej samej techniki). „eval-like” funkcjonalność jest z pewnością jedną z nich.

vzn
źródło
2
V8 jest dobrym przykładem. Jest to czysty kompilator, nigdy nie ma żadnej interpretacji. Jednak nadal obsługuje pełną semantykę ECMAScript, w tym nieograniczoną eval.
Jörg W Mittag
1
Lua robi to samo.
Mooing Duck
3

LISP jest okropnym przykładem, ponieważ został pomyślany jako rodzaj „maszynowego” języka wyższego poziomu jako podstawa dla „prawdziwego” języka. Ten „prawdziwy” język nigdy się nie zmaterializował. Maszyny LISP zostały zbudowane na pomyśle wykonywania (w znacznej części) LISP w sprzęcie. Ponieważ interpreter LISP jest tylko programem, w zasadzie można go zaimplementować w obwodach. Być może niepraktyczne; ale dalekie od niemożliwego.

Ponadto istnieje wiele tłumaczy programowanych w krzemie, zwykle nazywanych „CPU”. Często przydatna jest interpretacja (jeszcze nieistniejąca, niedostępna…) kodów maszynowych. Np. Linux x86_64 został po raz pierwszy napisany i przetestowany na emulatorach. Gdy układy pojawiły się na rynku, dostępne były pełne dystrybucje, nawet dla początkujących użytkowników / testerów. Java jest często kompilowana do kodu JVM, który jest interpreterem, który nie byłby zbyt trudny do napisania w krzemie.

Większość „interpretowanych” języków jest kompilowana do postaci wewnętrznej, która jest optymalizowana, a następnie interpretowana. Tak np. Robią Perl i Python. Istnieją również kompilatory dla języków, które mają być interpretowane, takie jak powłoka Unix. Z drugiej strony możliwe jest tłumaczenie tradycyjnie skompilowanych języków. Jednym z dość ekstremalnych przykładów, które widziałem, był edytor, który używał interpretowanego języka C jako języka rozszerzenia. To C może działać normalnie, ale proste programy bez problemów.

Z drugiej strony współczesne procesory przyjmują nawet dane wejściowe „języka maszynowego” i tłumaczą je na instrukcje niższego poziomu, które są następnie ponownie porządkowane i optymalizowane (tj. „Kompilowane”) przed przekazaniem do wykonania.

Całe to rozróżnienie między „kompilatorem” a „tłumaczem” jest naprawdę dyskusyjne, gdzieś na stosie znajduje się ostateczny interpreter, który pobiera „kod” i wykonuje go „bezpośrednio”. Dane wejściowe od programisty podlegają transformacjom wzdłuż linii, która nazywa się „kompilacją”, po prostu rysuje dowolną linię w piasku.

vonbrand
źródło
1

W rzeczywistości istnieje duża różnica między interpretacją jakiegoś programu podstawowego a uruchomieniem asemblera. Istnieją obszary pośrednie z kodem P / kodem bajtu z kompilatorami just-in-time lub bez nich. Spróbuję więc podsumować niektóre punkty w kontekście tej rzeczywistości.

  • Jeśli sposób analizowania kodu źródłowego zależy od warunków w czasie wykonywania, napisanie kompilatora może stać się niemożliwe lub tak trudne, że nikt nie będzie się tym przejmować.

  • Kod, który sam się modyfikuje, jest w ogólnym przypadku niemożliwy do skompilowania.

  • Program, który korzysta z funkcji podobnej do eval, zwykle nie może zostać całkowicie skompilowany z wyprzedzeniem (jeśli uważasz, że ciąg znaków dostarczany do niego jest częścią programu), chociaż jeśli zamierzasz wielokrotnie uruchamiać ewaluowany kod, nadal może być przydatne, aby funkcja podobna do eval wywoływała kompilator. Niektóre języki udostępniają interfejs API dla kompilatora, aby to ułatwić.

  • Możliwość odwoływania się do rzeczy po imieniu nie wyklucza kompilacji, ale potrzebujesz tabel (jak wspomniano). Wywoływanie funkcji po imieniu (jak IDispatch) wymaga dużo pracy hydraulicznej, do tego stopnia, że ​​myślę, że większość ludzi zgodzi się, że skutecznie mówimy o interpretatorze wywołań funkcji.

  • Słabe pisanie (bez względu na definicję) utrudnia kompilację i być może wynik jest mniej wydajny, ale często nie niemożliwy, chyba że różne wartości wyzwalają różne analizy. Istnieje tutaj przesuwna skala: jeśli kompilator nie może wydedukować rzeczywistego typu, będzie musiał emitować rozgałęzienia, wywołania funkcji i takie, których inaczej by nie było, skutecznie osadzając bity interpretera w pliku wykonywalnym.

Anonimowy Tchórz
źródło
1

przypuszczam, że główną cechą języka programowania, która uniemożliwia kompilatorowi języka (w ścisłym tego słowa znaczeniu, patrz także samozamykanie ) jest funkcja samodzielnej modyfikacji . Oznacza to, że język pozwala na zmianę kodu źródłowego w czasie wykonywania (sth kompilatora generującego, stały i statyczny, kod obiektowy nie może tego zrobić). Klasycznym przykładem jest Lisp (patrz także Homoiconicity ). Podobna funkcjonalność jest zapewniona przy użyciu konstrukcji języka, takiej jak eval , zawartej w wielu językach (np. JavaScript). Eval faktycznie wywołuje interpretera (jako funkcję) w czasie wykonywania .

Innymi słowy, język może reprezentować swój własny meta-system (patrz także Metaprogramowanie )

Zauważ, że odbicie języka w sensie zapytania o metadane określonego kodu źródłowego i ewentualnie modyfikowanie tylko metadanych (takie jak mechanizm odbicia Java lub PHP) nie jest problematyczne dla kompilatora, ponieważ już je zawiera metadane w czasie kompilacji i w razie potrzeby mogą je udostępnić skompilowanemu programowi.

Kolejną cechą, która utrudnia lub nie jest najlepszą opcją (ale nie niemożliwą) kompilację, jest schemat pisania używany w języku (tj. Pisanie dynamiczne vs. pisanie statyczne i pisanie mocne vs. pisanie swobodne). Utrudnia to kompilatorowi przechowywanie całej semantyki w czasie kompilacji, dlatego część kompilatora (innymi słowy interpreter) staje się częścią generowanego kodu, który obsługuje semantykę w czasie wykonywania . Innymi słowy, nie jest to kompilacja, ale interpretacja .

Nikos M.
źródło
LISP jest okropnym przykładem, ponieważ został pomyślany jako sprt
vonbrand
@vonbrand, może, ale wyświetla zarówno koncepcję homoiconicity, jak i jednolitą dualność kodu danych
Nikos M.,
-1

Uważam, że pierwotne pytanie nie jest dobrze sformułowane. Autorzy pytania mogli chcieć zadać nieco inne pytanie: jakie właściwości języka programowania ułatwiają napisanie dla niego kompilatora?

Na przykład łatwiej jest napisać kompilator dla języka bezkontekstowego niż dla języka kontekstowego. Gramatyka definiująca język może mieć również problemy, które utrudniają kompilację, takie jak dwuznaczności. Takie problemy można rozwiązać, ale wymagają dodatkowego wysiłku. Podobnie, języki zdefiniowane przez nieograniczoną gramatykę są trudniejsze do przeanalizowania niż języki kontekstowe (patrz Hierarchia Chomsky'ego ). Według mojej wiedzy najczęściej używane języki programowania proceduralnego są zbliżone do kontekstu, ale zawierają kilka elementów kontekstowych, co czyni je stosunkowo łatwymi do skompilowania.

Georgie
źródło
2
Pytanie ma wyraźnie sprzeciwić się / porównać kompilatory i tłumaczy. Chociaż mogą działać inaczej i zwykle działają inaczej niż powyższy przypadek limitu @Raphael, mają dokładnie takie same problemy dotyczące analizy składni i niejednoznaczności. Zatem składnia nie może być problemem. Uważam również, że problem składniowy nie jest obecnie głównym problemem w pisaniu kompilatorów, chociaż miał miejsce w przeszłości. Nie jestem zwycięzcą: wolę komentować.
babou
-1

Pytanie ma prawidłową odpowiedź, tak oczywistą, że zwykle jest pomijane jako trywialne. Ale ma to znaczenie w wielu kontekstach i jest głównym powodem istnienia języków interpretowanych:

Kompilowanie kodu źródłowego w kod maszynowy jest niemożliwe, jeśli nie masz jeszcze kodu źródłowego.

Tłumacze dodają elastyczności, a w szczególności elastyczności działania kodu, który nie był dostępny podczas kompilacji projektu bazowego.

tylerl
źródło
2
„Zgubiłem kod źródłowy” nie jest własnością języka programowania, ale konkretnego programu, więc nie odpowiada na pytanie. I na pewno trzeba cytat za twierdzenie, że unikając utraty kod źródłowy jest „głównym powodem, dlaczego istnieją języki interpretowane”, lub nawet powód, dla którego istnieje.
David Richerby,
1
@DavidRicherby Wydaje mi się, że przykładem użycia tyleri jest interpretacja interaktywna, tj. Kod wprowadzany w czasie wykonywania. Zgadzam się jednak, że to nie wchodzi w zakres pytania, ponieważ nie jest to cecha języka.
Raphael
@DavidRicherby i Raphael, mówię, że autor tego postu sugeruje (to, co opisuję w mojej odpowiedzi) jako funkcję auto-modyfikacji, która oczywiście jest konstrukcją językową z założenia, a nie artefaktem jakiegoś konkretnego programu
Nikos M.