Programowanie wnioskowania o własnym kodzie źródłowym

15

Inspiracją dla tego pytania jest następujące (niejasne) pytanie: Jakie są podstawy programowania / logiczne podstawy posiadania sztucznej inteligencji, która mogłaby rozumować własny kod źródłowy i go modyfikować?

To wcale nie jest rygorystyczne, więc oto moja próba wyciągnięcia z tego konkretnego pytania. Interesują mnie dwie rzeczy:

(A) Język programowania P, który może reprezentować własne programy i nimi manipulować jako program typu danych (np. Jako AST). (W razie potrzeby obiekt typu Program można przekonwertować na ciąg znaków, który jest tekstem poprawnego programu w tym języku. Byłoby to przeciwieństwo działania kompilatora.)

(B) Metoda uzasadnienia tego, co robi program w języku P. Oto dwa poziomy, o których myślę:

Inny język Q (z możliwościami dowodzenia twierdzeń), który modeluje to, co robi program P. Powinien być w stanie wyrazić i udowodnić takie stwierdzenia, jak „wynik działania Programu p jest foo”.
Sposób na uzasadnienie tego, co program p: Program robi w języku P. (Więc bierzemy P = Q powyżej.)

W jakim stopniu wdrożono coś takiego lub jaki jest postęp w tym kierunku? Jakie są praktyczne przeszkody? W świetle pierwotnej intencji pytania, jaki jest najlepszy sposób sformalizowania problemu?

*

Jak pokazują odpowiedzi (dzięki!), Zarówno (A), jak i (B1) można wykonać osobno, choć wydaje się, że robienie ich razem jest raczej pytaniem badawczym.

Oto kilka moich pierwszych przemyśleń na pytanie (ostrzeżenie: raczej niejasne). Zobacz także moje komentarze do odpowiedzi Martina Bergera.

Interesuje mnie język programowania modelujący ten sam język programowania, a nie prostszy (więc P = Q powyżej). Byłby to „dowód koncepcji” programu zdolnego do „rozumowania własnego kodu źródłowego”. Zależnie wpisane języki programowania mogą dawać gwarancje dotyczące wyników jego funkcji, ale nie liczy się to jako „rozumowanie własnego kodu źródłowego” bardziej niż „Witaj świecie!” liczy się jako quine w języku, który automatycznie wydrukuje nagi ciąg --- musi istnieć jakiś cytat / odnośnik. Tutaj analogiem jest typ danych reprezentujący Program.

Wydaje się, że jest to dość duży projekt - im prostszy język, tym trudniej jest wyrazić wszystko w nim; im bardziej skomplikowany język, tym więcej pracy trzeba wykonać, aby go wymodelować.

W duchu twierdzenia o rekurencji program może następnie „pobrać” własny kod źródłowy i zmodyfikować go (tj. Wygenerować zmodyfikowaną wersję samego siebie). (B2) następnie mówi nam, że program powinien móc wyrazić gwarancję na zmodyfikowany program (powinien on mieć możliwość ponownego wystąpienia, tj. Powinien być w stanie wyrazić coś o wszystkich przyszłych modyfikacjach -?).

pl.programming-languages ai.artificial-intel recursion Holden Lee
źródło

1

Dlaczego potrzebujesz, aby język działał jako twierdzenie twierdzenia, aby ustalić, że „wynik uruchomienia Programu p jest foo”? Język może po prostu uruchomić p! Rzeczywiście tak się dzieje.

Martin Berger,

3

en.wikipedia.org/wiki/Reflection_(computer_programming)

Kaveh

3

Zauważ, że w zasadzie każdy język, który może zaimplementować tłumacza, może robić rzeczy, których potrzebujesz. W bardziej matematyczny sposób twierdzenie o rekurencji dotyczy każdego wystarczająco mocnego modelu obliczeń. Niektóre języki programowania tylko to ułatwiają, ponieważ są wbudowane. To samo dotyczy rozumowania: możesz zaimplementować dowolny system wnioskowania w tych językach. Oczywiście nie można oczekiwać, że wszystko się wyjaśni, np. Problem z zatrzymaniem programów.

Kaveh

2

Myślę, że pytanie nie jest bardzo jasne. Powinieneś rzucić okiem na języki programowania, takie jak Python, Java oraz te wymienione przez Martina w odpowiedzi i wyjaśnić pytanie, aby albo było jasne, że spełniają one to, czego szukasz, a jeśli nie, dlaczego nie.

Kaveh

1

@HoldenLee Jeśli chodzi o „P = Q”, ustaloną terminologią jest „homogeniczne metaprogramowanie”, co jest przeciwieństwem „heterogenicznego metaprogramowania”, gdzie P

Q.

\neq

$\neq$

Martin Berger

14

Myślę, że pytasz o dwie różne rzeczy.

Zdolność języka programowania do reprezentowania wszystkich swoich programów jako danych.
Rozumowanie programów jako danych.

Do celów analitycznych warto je rozdzielić. Skoncentruję się na tym pierwszym.

Zdolność do reprezentowania języków programowania, manipulować (i bieg) swoje programy jako dane idzie pod określeniami takimi jak meta-programowania lub homoikoniczność .

W (niezręczny) sposób wszystkie dobrze znane języki programowania mogą wykonywać meta-programowanie, a mianowicie przy użyciu typu danych ciągu wraz z możliwością wywoływania programów zewnętrznych (kompilatora, konsolidatora itp.) Na ciągach znaków (np. Zapisując je do pliku najpierw system). Jednak prawdopodobnie nie to masz na myśli. Prawdopodobnie masz na myśli niezłą składnię. Ciągi nie są ładną składnią do reprezentacji programu, ponieważ prawie wszystkie ciągi nie reprezentują programów, tzn. Typ danych ciągów zawiera wiele „śmieci”, gdy są postrzegane jako mechanizm reprezentacji programu. Co gorsza, algebra operacji ciągów nie ma zasadniczo żadnego związku z algebrą budowy programu.

To, co prawdopodobnie masz na myśli, jest o wiele ładniejsze. Np. Jeśli jest programem, to to , ale jako dane, pod ręką do manipulacji i analizy. Jest to często nazywane cytatem . W praktyce oferta cenowa jest nieelastyczna, dlatego zamiast niej używamy quasi-oferty , która jest uogólnieniem oferty, w której oferta może zawierać „dziury”, w których można uruchamiać programy dostarczające dane do „wypełnienia” dziur. Na przykład to quasi-cytat reprezentujący warunek, w którym zamiast warunku mamy dziurę $P$ $\newcommand{\QUOTE}[1]{\langle #1\rangle}\QUOTE{P}$ $P$

⟨ ja fa [\cdot] t h mi n 7 mi l s mi 8 + 9 ⟩

$\newcommand{\SYNTAX}[1]{\mathsf{#1}} \newcommand{\IF}[3]{\SYNTAX{if}\; #1 \; \SYNTAX{then}\; #2\; \SYNTAX{else}\; #3}\QUOTE{\IF{[\cdot]}{7}{8+9}}$

[\cdot]

$[\cdot]$ . Jeśli program ocenia dane , to quasi-cytat ocenia dane

M

$M$

⟨ x > 0 ⟩

$\QUOTE{x > 0}$

⟨ ja fa [M.] t h mi n 7 mi l s mi 8 + 9 ⟩

$\QUOTE{\IF{[M]}{7}{8+9}}$

⟨ ja fa x > 0 t h mi n 7 mi l s mi 8 + 9 ⟩ .

$\QUOTE{\IF{x > 0}{7}{8+9}}.$

(Zauważ, że jest normalnym programem (nie programem jako danymi), który zwraca cytowany program, tj. Program jako dane.) Aby to zadziałało, potrzebujesz typu danych do reprezentowania programów. Zazwyczaj ten typ danych nazywa się AST (abstrakcyjne drzewo składniowe) i można zobaczyć (quasi -) cytaty jako mechanizmy skrótów dla AST. $M$

Kilka języków programowania oferuje quasi-cytaty i inne funkcje meta-programowania. To Lisp z funkcją makrowania pionierem tej zdolności do traktowania programów jako danych. Być może niestety moc makr opartych na Lisp od dawna spoczywała w dużej mierze na minimalistycznej składni Lisp; dopiero w MetaML (1) okazało się, że nowoczesny język o bogatej składni jest zdolny do metaprogramowania. Od tego czasu MetaOCaml (2) (potomek MetaML, ważny dla jego przełomu w wciąż trwających poszukiwaniach rozwiązania problemu pisania programów jako dane), Template Haskell (3) i Converge (4) (pierwszy język do uzyskać wszystkie kluczowe funkcje metaprogramowania w mojej opinii) pokazały, że w wielu nowoczesnych językach programowania można umieścić metaprogramowanie. Ważne jest, aby zdać sobie sprawę, że możemy to zrobićdowolny język programowania i zamień go w język meta-programowania który jest wraz z możliwością reprezentowania (i oceny) własnych programów jako danych. $L$ $L_{mp}$ $L$

Reprezentację wyniku działania programu, podanego jako dane, osiąga się przez dodanie funkcji która pobiera program (podany jako dane) jako dane wejściowe i uruchamia go , zwracając swój wynik. Np. Jeśli jest programem oceniającym na 17 i , wersja (quasi-) cytowana , tj. jako dane, to również również zwraca 17. Istnieją różne sposoby subtelności tutaj, które tutaj ignoruję, takie jak pytanie kiedy $\newcommand{\EVAL}{\mathsf{eval}}\EVAL(\cdot)$ $P$ $\QUOTE{P}$ $P$ $P$ $\EVAL(\QUOTE{P})$ programy meta-programowane są oceniane (co powoduje rozróżnienie między meta-programowaniem w czasie kompilacji a czasem wykonywania), co zrobić z typami lub błędnymi ocenami, co dzieje się ze zmiennymi powiązanymi i swobodnymi w procesie przechodzenia od do lub odwrotnie. $P$ $\QUOTE{P}$

Jeśli chodzi o drugi wymiar, rozumowanie programów podanych jako dane. Gdy tylko przekształcisz programy w dane, są one „normalnymi” danymi i można je traktować jako dane. Możesz używać wszelkiego rodzaju technologii sprawdzających, np. Typy zależne lub umowy, interaktywne dowody twierdzeń lub zautomatyzowane narzędzia, jak zauważył Joshua. Będziesz jednak musiał przedstawić semantykę swojego języka w procesie rozumowania. Jeśli ten język, tak jak tego potrzebujesz, ma zdolności metaprogramowania, sprawy mogą stać się nieco trudne i nie wykonano wiele pracy w tym kierunku, przy czym (5) jest jedyną logiką programu w tym celu. Istnieją również prace Curry'ego-Howarda nad wnioskami dotyczącymi metaprogramowania (6, 7, 8). Zauważ, że te podejścia oparte na logice, a podejście oparte na typach (2) może rzeczywiście wyrażać właściwości, które zachowują się na wszystkich przyszłych etapach metaprogramowania. Poza (2) żaden z tych dokumentów nie został wdrożony.

Podsumowując: to, o co prosiłeś, zostało zaimplementowane, ale jest dość subtelne i wciąż istnieją otwarte pytania, w szczególności dotyczące typów i usprawnionego rozumowania.

W. Taha. Programowanie wieloetapowe: jego teoria i zastosowania .
W. Taha i MF Nielsen. Klasyfikatory środowiskowe .
T. Sheard i S. Peyton Jones. Szablon meta-programowania dla Haskell .
L. Tratt. Metaprogramowanie w czasie kompilacji w dynamicznie pisanym języku OO .
M. Berger, L. Tratt, Program Logics for Homogeneous Meta-Programming .
R. Davies, F. Pfenning, Analiza modalna obliczeń etapowych .
R. Davies, Podejście czasowo-logiczne do analizy czasu wiązania .
T. Tsukada, A. Igarashi. Logiczna podstawa dla klasyfikatorów środowiska .

Martin Berger
źródło

Masz rację - język programowania P może różnić się od języka Q, który wyraża twierdzenia / dowody dotyczące programów w tym języku (na przykład w języku Coq). Twierdzenie, o którym myślę, wygląda następująco: Załóżmy, że mamy starannie zaprojektowany program A_1. Thm: Dla każdego n następujące wstrzymania: Program A_n wyświetli (m_n, A_ {n + 1}), gdzie m_n jest liczbą całkowitą, A_ {n + 1} to inny program (np. Uzyskany przez modyfikację A_n w jakiś sposób) i dla wszystkich n mamy m_n> 0.

Holden Lee,

(Wersja science fiction jest taka, że mamy „dowód”, że program, który sam się modyfikuje, nigdy nie naciska przycisku uruchamiającego pocisk nuklearny, powiedzmy, lub że program zawsze zoptymalizuje określoną ilość.)

Holden Lee

Dlatego chciałem wprowadzić rozróżnienie między uruchomieniem programu a wnioskiem o wynikach programu - chcemy poznać właściwości tego, co zrobi przed uruchomieniem, bez uruchamiania. Zauważ, że jeśli chcemy, aby A_n był w stanie „zmodyfikować swój kod źródłowy” w celu wytworzenia A_ {n + 1}, P musi koniecznie mieć zdolności metaprogramowania (co stawia nas w pozycji (5)).

Holden Lee,

Nadal wydaje mi się, że byłoby interesujące dla P = Q. Hipotetycznie A jest programem sztucznej inteligencji, a sposobem, który mógłby się zmodyfikować, jest rozumowanie własnego kodu - na przykład zapisywanie twierdzeń o bitach kodu, ich dowodzenie, a dopiero potem modyfikowanie jego kodu. Wydaje się, że P musiałby mieć zdolności Q.

Holden Lee

@HoldenLee Można pisać programy takie jak A_n. Jeśli używasz ciągów znaków jako reprezentatywnych dla programów, możesz to zrobić trywialnie w dowolnym języku, jeśli chcesz quasi-cudzysłowy lub podobne, jest to możliwe np. W Converge. Nie rozumiem roli m_n w konstrukcji.

Martin Berger,

6

Nie, nie ma obecnego systemu, który wykonuje wszystkie cztery kroki w twoim systemie. Jeśli chcesz zaprojektować system, jednym z pierwszych wymagań jest język homoiconic. Przynajmniej chciałbyś, aby Twój podstawowy język programowania był jak najmniejszy, aby po wejściu do systemu i rozpoczęciu samodzielnej interpretacji działał. Dlatego potrzebujesz interpretera międzykolistego, który był pionierem w seplenieniu. Inne języki również to zrobiły, ale istnieje wiele badań dotyczących seplenienia.

Pierwszym krokiem, jeśli chcesz to zrobić, jest posiadanie języka homoiconic, takiego jak Lisp, lub jakiegoś frameworka, w którym możesz przekonać się o działającym programie. Używa się do tego Lisp tylko dlatego, że możesz zdefiniować interpreter międzykręgowy w języku lub po prostu traktować swój kod jako dane. Najważniejsze jest traktowanie kodu jako danych. Dyskusje na temat tego, co homoiconic oznacza na wiki wiki c2.

Na przykład w Lisp typ danych „Program” jest prawidłowymi programami lisp. Przekazujesz programy lisp do tłumacza, a on coś oblicza. Zostanie odrzucony przez tłumacza, jeśli nie zaprogramujesz prawidłowego „Programu”.

Dlatego język homoiconic spełnia trzy z twoich wymagań. Możesz nawet w lisp zdefiniować ideę formalnego programu.

Czy możesz modelować seplenienie w seplenienie? Tak, często odbywa się to głównie jako ćwiczenie na końcu podręcznika programowania sepleniego, aby sprawdzić swoje umiejętności. SICP

W chwili obecnej czwarty numer jest pytaniem badawczym, a poniżej znalazłem próbę odpowiedzi na to pytanie.

Powiedziałbym, że istnieje wiele rodzajów programów, które próbują to zrobić. Poniżej znajdują się wszystkie programy, o których wiem.

JSLint jest przykładem analizatora statycznego, który pobiera kod maszynowy lub inny język i wyraźnie szuka błędów. Następnie prosi programistę, aby to poprawił.
Coq to środowisko, które pozwala określić dowody przy użyciu języka programowania. Ma taktykę, w której sugeruje sposoby rozwiązania problemu. Mimo to oczekuje się od człowieka wykonania pracy. Coq używa typów zależnych do pracy, a zatem jest bardzo teoretyczny. Jest bardzo popularny wśród informatyków i osób pracujących nad teorią typów homotopii.
Z drugiej strony ACL2 to automatyczna przysłowiowa twierdzenie. Ten system sprawdzi wyciągi oparte na czymś, co programujesz.
ACL2 i Coq mają wtyczkę oprogramowania, która łączy ich system z systemem uczenia maszynowego . Do szkolenia tych systemów wykorzystywane są wcześniej napisane programy. Z mojego zrozumienia systemy te dodają kolejną cechę, w której masz nie tylko swoją taktykę, ale sugerujesz twierdzenia, które pomagają w rozwoju dowodów.

Poniżej znajduje się podstawa tego, co oznacza twoje pytanie.

gcc jest przykładem kompilatora optymalizacyjnego, który może brać siebie jako dane wejściowe, a następnie wypuszczać zoptymalizowaną wersję samego siebie. Idea kompilatora, który tłumaczy programy z jednej reprezentacji na drugą i poprawia prędkość z powodu niektórych flag optymalizacji jest bardzo dobrze zrozumiana. Po uruchomieniu kompilatora i wygenerowaniu prawidłowego kodu maszynowego można dodać optymalizację i ponownie skompilować kompilator, dzięki czemu jest on bardziej wydajną wersją samego siebie.

Joshua Herman
źródło

1

Nie ma potrzeby, aby język był jak najmniejszy. Możesz dodać odpowiednie funkcje metaprogramowania do dowolnego języka. Wykazała to praca MetaML firmy Taha. Rzeczywiście dodanie możliwości metaprogramowania jest mechaniczne.

Martin Berger,

1

Nie zgadzam się również z tym, że „żaden obecny system nie wykonuje wszystkich czterech kroków”. Pytanie 4 dotyczy tylko uruchamiania programów podanych jako kod. Jest to całkowicie możliwe, w rzeczywistości robi to nawet ewaluacja Javascript.

Martin Berger,

@MartinBerger mam na myśli to, że jądro rdzenia jest tak minimalne, jak to możliwe. Jeśli nawet zaczniesz mieć nadzieję, że Twój system wykona numer 4, będziesz potrzebować systemu, w którym będziesz mógł szkolić nie tylko ludzi, ale także komputery, więc skorzystaj z minimalnego systemu i bibliotek, które są zakodowane ten system jak meta szablon programowania

Joshua Herman

To zależy od tego, o czym (4) mówimy. Pierwotne pytanie zawiera dwa ich opracowania. Pierwszy jest trywialny, wystarczy uruchomić program. Drugi może być obsługiwany przez logikę, którą cytowałem jako (5) w mojej odpowiedzi na system pisania (2). Później jest zaimplementowany w MetaOCaml. Istnieje jednak pole do dalszych badań: ani (2), ani (5) nie radzą sobie z dowolnymi formami metaprogramowania, a właściwości gwarantowane przez (2) są nieco słabe (w końcu jest to system pisania z wnioskowaniem typu) .

Martin Berger,

1

Jeśli chodzi o „minimalizowanie jądra rdzenia”: nie jest to wymagane. Możesz dodać pełne metaprogramowanie do dowolnego języka.

Martin Berger,

5

Jak wspomniano w odpowiedzi @ user217281728, istnieje pewien rodzaj maszyn związanych bardziej z wnioskami i sztuczną inteligencją, zwany maszynami Gödela

Maszyna Gödel to samodoskonalący się program komputerowy opracowany przez Jürgena Schmidhubera, który optymalnie rozwiązuje problemy. Wykorzystuje rekurencyjny protokół samodoskonalenia, w którym przepisuje własny kod, gdy może udowodnić, że nowy kod zapewnia bardziej optymalną strategię. Maszyna została wynaleziona przez Jürgena Schmidhubera, ale nosi imię Kurta Gödela, który zainspirował teorie matematyczne.

Przywołana publikacja Jürgena Schmidhubera na temat „Maszyny Goedela: uniwersalne rozwiązywanie problemów z samodzielnymi odniesieniami, które zapewniają optymalne samodoskonalenia”, (2006) arXiv: cs / 0309048v5

Sposób, w jaki maszyna działa w celu wdrożenia meta-uczenia się, składa się z dwóch etapów:

Uczenie się na podstawie danych (poziom 1, ucz się)
Wykorzystywanie wyuczonych danych do modyfikowania / optymalizacji kodu źródłowego / algorytmu (poziom 2, naucz się uczyć)

Ponieważ maszyna modyfikuje swoje własne źródło, jest autoreferencyjna, tzn. Ma właściwość samokodyfikacji (patrz także tutaj ).

W tym sensie może modyfikować sam algorytm uczenia się w ścisłym sensie (udowadniając optymalne samomodyfikacje). Występują problemy z odniesieniem do siebie i nierozstrzygalnością, które w tym przypadku przybierają postać:

.. maszyna Gödela z nieograniczonymi zasobami obliczeniowymi musi zignorować te samodoskonalenia, których skuteczności nie może udowodnić

Innymi językami (i powiązanymi z nimi maszynami tłumaczącymi), które mają właściwość auto-modyfikacji, są na przykład LISP .

W LISP kod i dane są wymienne lub kod źródłowy AST jest dostępny jako dane w programie LISP i może być modyfikowany jako dane. Z drugiej strony dane mogą być postrzegane jako AST dla niektórych kodów źródłowych.

aktualizacja

Istnieją również inne maszyny , takie jak maszyny samoregulujące (między innymi), które łączą samodzielne odniesienie , samoreprodukcję i autoprogramowanie .

Interesującym aspektem powyższego jest to, że samo-odniesienia nie jest problematyczne, w ogóle, a nie jest to konieczne, element samoreprodukcji / samoprogramujący automatów .

Więcej informacji (i więcej publikacji) można znaleźć w JP Moulin, CR Biologies 329 (2006)

abstrakcyjny

Żywe systemy potrafią odpowiednio reagować na nieprzewidywalne środowisko. Ten rodzaj samoorganizacji wydaje się działać jako maszyna samoregulująca, tj. Oprganizacja zdolna do samodzielnej modyfikacji. Do tej pory proponowane modele samoorganizacji istot żywych są funkcjami rozwiązań systemów różnicowych lub funkcjami przejściowymi automatów. Funkcje te są stałe i dlatego modele te nie mogą modyfikować swojej organizacji. Z drugiej strony informatyka proponuje wiele modeli posiadających właściwości systemów adaptacyjnych istot żywych, ale wszystkie te modele zależą od porównania celu i wyników oraz genialnego doboru parametrów przez programistów, podczas gdy programiści nie mają zamiaru ani wybór w żywych systemach. $\mathbb{m}_\mathbb{sp}$ $\mathbb{M}_\mathbb{sp}$

Nikos M.
źródło

3

Ten artykuł autorstwa Jurgena Schmidthubera może być interesujący:

http://arxiv.org/pdf/cs/0309048.pdf

NietzscheanAI
źródło

plz dać podsumowanie przynajmniej

vzn

Programowanie wnioskowania o własnym kodzie źródłowym

Odpowiedzi: