Język programowania, w którym każde wyrażenie ma sens

Zgodnie z zaleceniem przesyłam ponownie z Przepełnienia stosu .

Ostatnio zastanawiałem się nad następującym problemem.

Rozważ kod standardowego „Hello world!” program:

main()
{
    printf("Hello World");

}

Teraz prawie każda zmiana w tym kodzie sprawi, że będzie on całkowicie bezużyteczny, w rzeczywistości prawie każda zmiana uniemożliwi kompilację kodu. Na przykład:

main(5
{
    printf("Hello World");

}

Teraz do właściwego pytania. Czy istnieje język programowania, w którym każda możliwa kombinacja symboli - czyli każde wyrażenie - ma sens? Próbowałem wymyślić jakieś rozwiązanie i wymyśliłem dwa:

1. Postfiks z ograniczoną liczbą zmiennych. Zasadniczo wszystkie zmienne są już zdefiniowane przed napisaniem jakiegokolwiek kodu i musisz z nimi pracować. Teoretycznie możesz wykonać dowolną liczbę operacji, tworząc łańcuch wielu prostych programów, z których każdy przekazuje wyniki innym. Kod może być zapisany jako ciąg znaków w notacji postfiksowej;

2. „Postfix” ze stosem zmiennych. Zmienne są przechowywane na stosie; każda operacja pobiera dwie zmienne z góry i umieszcza wynik na swoim miejscu. Program kończy się, gdy osiągnie ostatnią operację lub zmienną.

Osobiście nienawidzę obu z nich. Są nie tylko ograniczone, ale także nieeleganckie. Nie są to nawet prawdziwe rozwiązania, bardziej jak obejścia, w zasadzie „offshoring” części pracy do procesu zewnętrznego.

Czy ktoś ma jakiś pomysł, jak rozwiązać ten problem?

Redcode, język asemblera kryjący się za kodewars, został wyraźnie napisany, aby mieć bardzo niewiele instrukcji zatrzymania, ponieważ kod często ulega zniekształceniu, zanim w końcu się poddaje, a im więcej możliwości musi się zatrzymać, tym mniej interesująca jest gra.

W praktyce widać bardzo niewiele takich języków, ponieważ nie chcemy tylko, aby program był uruchamiany, chcemy, aby działał w oczekiwany sposób. Jeśli możesz napisać literówkę i zmienić sposób działania programu, musi on być akceptowalnie zbliżony do pierwotnego oczekiwanego zachowania lub programistów z wrzodem frustracji.

Istnieje pewien priorytet dla takich rzeczy, używając języków naturalnych zamiast języków formalnych, ale nie nazwałbym tego dużym polem, gdy porównasz je z użyciem języków formalnych. Jeśli interesują Cię takie języki programowania, to społeczność zajmująca się przetwarzaniem języka naturalnego jest tym, na co patrzę.

Kolejną dziedziną, na którą można spojrzeć, jest genetyka. Istnieje niezwykle niewiele sekwencji genetycznych, które są po prostu nieprawidłowe. Wiele z nich, które nie są bardzo skuteczne w reprodukcjach, ale bardzo niewiele nieważnych.

Idea uniwersalnej maszyny Turinga wykorzystuje właśnie taki „język programowania”: kodowanie maszyn Turinga jako liczb naturalnych, reprezentowanych na przykład w postaci binarnej, tak że każda liczba naturalna oznacza maszynę Turinga, tj. Program. W tym języku każdy ciąg zer i jedynek jest programem.

Jeśli obawiasz się, że niektóre liczby mogą kodować nieprawidłowe programy, możesz to zrobić krok po kroku w następujący sposób. Wyobraź sobie, że wypisujesz wszystkie ciągi znaków w zestawie znaków twojego języka programowania (powiedzmy Java), w kolejności leksykograficznej, zaczynając od ciągów o długości jeden, potem dwa, potem trzy, ... Następnie stwórz nowy język programowania, pozwalając na liczbę oznacza ty ciąg na liście, który jest prawidłowym programem Java. W nowym języku programowania programy są po prostu liczbami naturalnymi, a każda liczba naturalna jest poprawnym programem.$n$$n$

Jestem pewien, że istnieją również ezoteryczne języki programowania, w których każdy ciąg znaków jest programem; Jeśli jednak pytasz o ich listę, myślę, że twoje pytanie jest tutaj nie na temat.

Rozszerzenie języka programowania, aby każde wyrażenie miało sens, jest zawsze możliwe, ale nie interesujące. Na przykład możesz po prostu przypisać znaczenie „nic nie rób” dowolnemu wyrażeniu, które odrzuca język oryginalny.

Zaprojektowanie języka programowania, w którym każde wyrażenie ma sens w sposób „można go wykonać”, nie jest szczególnie przydatne. Dobry język programowania to nie tylko język, w którym małpa może pisać na klawiaturze i pisać prawidłowy program, ale język, w którym programiści mogą łatwo napisać program, który zamierzali napisać. Pisanie prawidłowych programów nie jest trudną częścią programowania: trudną częścią jest pisanie programu, który wykonuje to, czego się od niego oczekuje. Odrzucenie oczywiście niepoprawnych programów jest w tym względzie bardzo pomocne.

Innym sposobem rozwiązania tego problemu jest pełne zdefiniowanie semantyki wszystkich możliwych danych wejściowych, w tym określenie, jaki czas kompilacji, czas ładowania lub błąd wykonania powinny być generowane dla każdego wejścia, jeśli takie występują. Oznacza to, że „przerwanie programu po wydrukowaniu Syntax error at line 42w standardowym strumieniu błędów” jest częścią zdefiniowanej semantyki języka. Każde wyrażenie „ma sens”, ponieważ ma określone znaczenie. Czy to ma sens? Może - w końcu, jeśli program jest oczywiście zły, odrzucenie go jest przydatne.

Sprawdź Jot , kompletny język Turinga oparty na logice kombinatorycznej, w którym każda sekwencja zer i jedynek (w tym pusta sekwencja) jest poprawnym programem.

Dobrym przykładem jest biała spacja . We właściwym języku każda kombinacja operatorów jest poprawna. Operatory to spacja, tabulator i znak nowej linii (w szczególności „\ n”). Wszystkie pozostałe postacie są uważane za komentarze .

Ta odpowiedź, a nawet twoje pytanie (a także cała ta strona internetowa) są przykładami prawidłowych programów spacji (choć nie mogą robić nic szczególnie interesującego).

Chciałbym odnieść się do pomysłu wielu plakatów, że taki język byłby „bezużyteczny”. Być może pisanie ręczne z myślą o rozwiązaniu określonego zadania byłoby bezużyteczne dla ludzi. Jednak pomimo tego, że jest to większość przypadków użycia dla języków programowania, z pewnością nie jest to jedyny przypadek użycia. Przypomina się kilka przypadków użycia, w których taki język jest przydatny, i możemy poszukać w tych polach przykładów takich języków.

Po pierwsze aluzja Cort Ammon do genetyki jest na miejscu: przekształcenie programu w pytaniu (podstawiając )za 5) może być postrzegane jako mutacji . Ten rodzaj manipulacji jest powszechny w dziedzinie obliczeń ewolucyjnych ; w szczególności algorytmy genetyczne wykonują takie transformacje na łańcuchach , podczas gdy programowanie genetyczne przekształca programy . W obu przypadkach zwykle chcemy przypisać znaczenie każdej możliwości, ponieważ spowoduje to utworzenie najbardziej kompaktowej przestrzeni wyszukiwania.

Algorytmy genetyczne opierają się na jakiejś funkcji oceny ciągów; jeśli używamy interpretera języka programowania jako naszej funkcji oceny, mamy scenariusz, w którym użyteczny jest język programowania, który nadaje znaczenie wszystkim możliwym ciągom znaków. W programowaniu genetycznym zakłada się, że naszą funkcją oceny jest tłumacz języka programowania, ale możemy wybrać różne reprezentacje dla naszych programów; na przykład wiele systemów działa na abstrakcyjnych drzewach składniowych. Jeśli wybierzemy ciągi jako naszą reprezentację, wówczas odzyskamy ten sam scenariusz, co w przypadku algorytmów genetycznych.

Inną sytuacją, w której możemy chcieć, aby każdy ciąg znaków był poprawnym programem, jest liczenie programów. Jest to związane z odrzuceniem wspomnianym przez CodesInChaos, ale możemy preferować operowanie na ciągach zamiast liczb naturalnych z kilku powodów:

• Jeśli w języku jest jakaś struktura, np. możemy przypisać znaczenie podciąganiom, które mogą zostać utracone podczas tłumaczenia na liczby naturalne. W takim przypadku możemy preferować użycie łańcuchów, aby lokalnie uzasadniać i przekształcać podłańcuchy, zamiast reprezentować cały program jako liczbę. Jest to analogiczne do tego, w jaki sposób wolelibyśmy używać operacji bitowych na wyrażeniach int zamiast wyrażeń arytmetycznych, gdy każdy bit ma indywidualne znaczenie. Jest to zasadniczo uogólnienie scenariusza ewolucyjnego.
• Możemy chcieć generować programy na żądanie; na przykład możemy rozpocząć wykonywanie programu, który jest całkowicie nieokreślony, i generować (np. losowo) poszczególne instrukcje (np. znaki), gdy / jeśli wskaźnik instrukcji do nich dotrze. Jest to powszechne w algorytmicznej teorii informacji, gdzie program jest taśmą maszynową Turinga, a celem jest scharakteryzowanie zachowania losowo generowanych programów. Na przykład możemy sformułować Solomonoff przed dowolnymi ciągami jako prawdopodobieństwo, że uniwersalna maszyna Turinga z losową taśmą wyśle ​​ten ciąg.

Pod względem języków przykładowych wiele ewolucyjnych systemów obliczeniowych opiera się na językach stosu, takich jak rodzina Push . Umożliwiają one dowolne strumienie tokenów (które moglibyśmy reprezentować jako pojedyncze postacie). Czasami (podobnie jak w przykładzie Brainfuck BrainSlugs83) istnieją ograniczenia dotyczące równoważenia nawiasów; możemy jednak powiązać to z programami samoograniczającymi się , ponieważ taki ciąg znaków [może nie być poprawnym programem , ale jest prawidłowym prefiksem programu . Jeśli wyobrażamy sobie kompilator / interpreter odczytujący kod źródłowy ze standardowego wejścia, wówczas nie odrzuci takiego ciągu [, po prostu poczeka na więcej danych wejściowych przed kontynuowaniem.

Języki takie jak Binary Combinatory Logic i Binary Lambda Calculus powstały bezpośrednio z pracy nad algorytmiczną teorią informacji, np. z http://tromp.github.io/cl/cl.html

Ten projekt minimalistycznego uniwersalnego komputera był motywowany moim pragnieniem wymyślenia konkretnej definicji złożoności Kołmogorowa, która bada losowość poszczególnych obiektów.

Prawdziwe języki programowania mają przekazywać znaczenie ludziom , a nie komputerom. Ponieważ mnóstwo zabawnych tekstów z niemal przypadkowo przetasowanymi literami unoszącymi się wokół programu, ludzie mogą czytać bełkot i mieć z tego sens, nawet bez wyraźnego zauważenia manglingu. Pomyśl tylko, jak trudno jest znaleźć literówki i inne tego typu błędy w tekście.

Język programowania, o który prosisz, sprawiłby, że ludzie zrozumieliby to, co chcą przeczytać, a nie to, co zapisano. Debugowanie w językach, w których istnieje ograniczony zestaw oświadczeń prawnych, w których nie ma dużej dwuznaczności, jest już wystarczająco trudne. Dobre języki redukują możliwe interpretacje z powodu np. Transponowanych symboli lub literówek. Z tego samego powodu języki naturalne są również znane ze swojej nadmiarowości.

W brainfuck Programming Language , prawie każdy możliwy wyraz binarny można interpretować jako program. - Oznacza to, że możesz wziąć całkowicie dobry program, wpisać do niego kilka śmieci i nadal byłby on kompilowalny / interpretowalny bez żadnych problemów.

( Edycja: Okazuje się, że musisz dopasować nawiasy kwadratowe otwierające i zamykające, ale poza tym powyższe jest prawdziwe.)

Osiąga to za pomocą dwóch prostych metod:

1. Wszystkie polecenia, które rozumie, są jednobajtowe (w BF są to na przykład pojedyncze znaki ASCII *).

2. Wszystkie postacie, których nie rozumie, odrzuca jako komentarze.

Język programowania jest kompletnie Turinga (co oznacza, że ​​może zrobić wszystko, co każdy inny język może zrobić).

*: Okazuje się, że nie wszystkie polecenia BF są pojedynczymi bajtami ASCII - tzn. Nawiasy MUSZĄ być dopasowane - tak jak to jest, język nie spełnia tam pierwszych kryteriów. - Ale każdy język, który spełnia oba kryteria, spełniałby wymagania OP.