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

23

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?

użytkownik1561358
źródło
48
Biorąc pod uwagę, kompilator , należy utworzyć nowy kompilator , które działa następująco: danego źródła , przekazać go do . Jeśli jest z niego zadowolony i tworzy plik wykonywalny, to tyle, ale jeśli narzeka, wypisz plik wykonywalny, który wypisuje Kompilator akceptuje każdy ciąg jako prawidłowy program. C ' s C, C, C, C 'CCsCCCYou are a bimbo.C
Andrej Bauer
1
BF potrzebuje pasujących [ ]poleceń (zgodnie ze stroną Wiki). Moją myślą było przyjrzenie się kodom procesora. Ale nawet wtedy niektóre wzorce mogą powodować problemy (np. Jeśli kod operacji ma 3 bity, ale twój program ma tylko 2 bity). Z wyjątkiem tego problemu, który może być uzupełniony dodatkowymi 0 bitami, można pomyśleć na dowolnym procesorze z kompletny zestaw kodów operacyjnych, który spełni twierdzenie „każdy łańcuch jest prawidłowym programem”. Może bez znaczenia, ale wciąż aktualne.
Ran G.
1
Niech twój sprzęt będzie procesorem Z-80 z 64k RAM. Napisz kompilator, który po prostu kopiuje kod źródłowy zakodowany w ASCII do pamięci 64k (w razie potrzeby obcinając lub uzupełniając zero). Ten kompilator nigdy nie podaje błędu składniowego.
Ben Crowell,
1
@RanG. „Kompilator”, który przetwarza dowolny strumień bitów i naprawia go, aby był poprawnym bitem kodu obiektowego dla danego procesora, moim zdaniem spełniałby wymagania OP. Prawdopodobnie nie byłoby to strasznie trudne nawet dla systemów ze złożonymi zestawami instrukcji, takimi jak x86. Wiele lat temu przeczytałem artykuł na temat ważności losowych bajtów jako programów x86 i okazało się, że x86 był w rzeczywistości znacznie bardziej wytrzymały niż pierwotnie spodziewali się autorzy.
otakucode
2
Bez dalszych warunków to pytanie jest nudne: komentarz Andreja i odpowiedź Davida dają „trywialne” odpowiedzi. Musisz precyzyjniej ustalić, co chcesz.
Raphael

Odpowiedzi:

31

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.

Cort Ammon - Przywróć Monikę
źródło
1
Genetyka nie wydaje się dobrym przykładem. Pod względem ważności lub nieprawidłowości, czy mówisz tylko o replikacji? Ponieważ oczywiście każdy ciąg znaków będzie poprawnym programem dla języka, w którym jest jedyna możliwa instrukcja replicate this string. Nie jest to jednak naprawdę znaczący język programowania, ponieważ nie ma go w pobliżu Turing Complete.
tel.
2
@tel: Cort prawdopodobnie mówi o syntezie białek poprzez mRNA, a nie o replikacji. Prawie każdą sekwencję genetyczną można transkrybować, a następnie wprowadzić do maszyny do syntezy białek: czy białko, które wychodzi, jest wystarczająco stabilne, aby nie uległo degradacji do czasu budowy, a jeśli tak, to czy robi coś pożytecznego organizm to kolejna sprawa ...
Steve Jessop
3
Kod genetyczny nie jest kodem do reprodukcji. Jest to (ogólnie) kod białka. To, czy białko jest przydatne, jest często innym pytaniem. Oczywiście, że robi się ciekawiej. Niektóre fragmenty „kodu” w sekwencji genetycznej są bardziej podobne do instrukcji w stylu „tego kodu kilka linii dalej - czasem należy go po prostu zignorować”. Istnieje wiele fajnych „programów”, które napisały komórki i wirusy, walcząc ze sobą.
Joel
TECO to kolejny przykład w świecie rzeczywistym.
cjm
1
@cjm wow. „Interfejs API jest gotowy nie po zakończeniu dodawania wszystkiego, ale po zakończeniu wyjmowania”. Jeśli nie jesteś TECO, to skończysz, gdy zabraknie ci znaków, aby przypisać znaczenie.
Cort Ammon - Przywróć Monikę
16

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.nnn

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.

David Richerby
źródło
13

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.

Gilles „SO- przestań być zły”
źródło
12

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.

Petr Pudlák
źródło
2
To nie jest odpowiedź na informatykę .
Raphael
2
@Abdulrhman Łatwo jest zdefiniować bijection między ciągami binarnymi i liczbami naturalnymi. Możesz więc zakodować dowolny program jako liczbę naturalną, jeśli chcesz.
CodesInChaos
7
@Raphael Proszę opracować lub zasugerować poprawkę odpowiedzi, chętnie ją poprawię, jeśli uzasadnisz swoją krytykę.
Petr Pudlák
+1, miałem zamiar dać podobną odpowiedź dla fikcyjnego języka programowania opartego na liczbach naturalnych, ale to jest podobne. AFAIK nie ma programowania (w praktyce), które ma tę funkcję, ale można zbudować jeden za pomocą samych liczb, powiedzmy, gdzie każda kombinacja ma znaczenie (działają zarówno jako operatory, jak i operandy) To jest klucz
Nikos M.
8

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).

Slebetman
źródło
Właśnie o tym myślałem po opublikowaniu mojej pieprzonej odpowiedzi (Twoja jest lepsza, ponieważ jest poprawna), ale zastanawiam się - czy pusty program jest nadal programem? (tj. jeśli brakuje tych trzech znaków w całym strumieniu plików). - Gdyby w moim samochodzie brakowało wszystkich rzeczy, które sprawiły, że był to samochód, czy nadal byłby to samochód?
BrainSlugs83
To nie jest odpowiedź na informatykę . (Również „każdy ciąg białych znaków”! = „Każdy ciąg znaków”.)
Raphael
2
@Raphael: Ale każdy możliwy ciąg (łącznie z tymi, które nie zawierają białych znaków) są poprawnymi programami białych znaków - zauważ, że każdy znak, który nie jest
białym
2
@slebetman Zbyt dosłownie interpretujesz moje nawiasy. Mówiłem o niesparowanych tokenach pętli. Niektóre podobne problemy w białych znakach mogą być następujące: Czy powrót bez wcześniejszego połączenia działa? (zakodowane jako [LF][Tab][LF]) Co się stanie, jeśli wyskoczysz z pustego stosu? Co się stanie, jeśli przejdziesz do niezdefiniowanej etykiety? Co się stanie, jeśli zdefiniujesz zduplikowane etykiety?
CodesInChaos
7

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.

Warbo
źródło
2

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.

vonbrand
źródło
0

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.

BrainSlugs83
źródło
2
To nie tylko nie odpowiada na pytanie, ale nie jest odpowiedzią informatyczną .
Raphael
1
Możesz przedefiniować język, aby posługiwać się nimi w rozsądny sposób. np. wstawiając wystarczającą liczbę nawiasów otwierających na początku programu i nawiasów zamykających na końcu programu, aby był zrównoważony. Łatwo jest napisać interpreter, który obsługuje programy tak, jakby te nawiasy istniały bez faktycznego przepisywania programu. Oczywiście rozpoczęcie programu pieprzenia mózgu z nawiasem otwierającym jest raczej bezużyteczne, ponieważ zignoruje wszystko, aż do pasującego nawiasu zamykającego.
CodesInChaos
1
@Raphael OP zadał pytanie: „Czy istnieje język programowania, w którym każda możliwa kombinacja symboli - to znaczy każde wyrażenie - ma sens?” - moja odpowiedź brzmi: „tak, oto przykład, który się zbliża, a oto teoria ”. - poza ustaleniem dokładnych zasad dla jednej klasy języków, które spełniałyby wymagania PO, nie jestem pewien, jak wiele jest tutaj miejsca na naukę . Czy możesz podać przykład lub link do zasobu tego, co dokładnie chcesz tutaj zobaczyć? -- Dziękuję Ci.
BrainSlugs83
2
David i Gilles udzielają odpowiedzi z zakresu informatyki. Badają zasady i nie mówią tylko: „język X robi to (prawie)”. Jeśli przeczytasz ich odpowiedzi, dowiesz się, że odpowiedzi z drugiej formy są również nudne. To nie twoja wina, ale OP - pytanie (jako pytanie z informatyki) jest nudne; istnieje fałszywe poczucie złożoności.
Raphael
Można łatwo „naprawić” BF, aby akceptować dowolny ciąg: udajesz, że ]na końcu źródła jest wystarczająca liczba znaków, aby dopasować wszystkie niedopasowane litery [, a [na początku wystarczająca liczba, aby dopasować wszystkie niedopasowane ]. Semantykę [i ]można łatwo zmienić, aby stały się równoważne z tym. (np. jeśli nie ma dopasowania, ]to [po prostu zatrzymuje wykonywanie, jeśli bajt na wskaźniku danych wynosi zero. ]po prostu przeskakuje na początek programu w podobnej sytuacji). Wynikowym językiem byłoby ukończenie Turinga i zaakceptowanie dowolnego łańcucha.
Nathaniel