rachunek z odbiciem

23

Szukam prostego rachunku, który obsługuje rozumowanie na temat refleksji , a mianowicie introspekcji i manipulacji uruchomionymi programami.

Czy istnieje nietypowe rozszerzenie -calculus, które umożliwia konwersję -terms do postaci, którą można manipulować składniowo, a następnie oceniać? $\lambda$ $\lambda$

Wyobrażam sobie, że rachunek składa się z dwóch głównych dodatkowych terminów:

$\mathtt{reflect}\ v$ : przyjmuje i tworzy reprezentację podlegającą modyfikacjom w manipulacji składniowej. $v$ $v$
$\mathtt{eval}\ v$ : przyjmuje składniową reprezentację terminu i ocenia go.

Aby wesprzeć refleksję, wymagana jest składniowa reprezentacja terminów. Wyglądałoby to tak:

$\lambda x.e$ byłby reprezentowany jako termin , gdzie jest odzwierciedloną wersją , $(\mathsf{LAM}\ R(e))$ $R(e)$ $e$
$e\ e'$ byłoby reprezentowane jako termin , a $(\mathsf{APP}\ R(e)\ R(e'))$
$x$ byłoby reprezentowane jako . $(\mathsf{VAR}\ x)$

Dzięki tej reprezentacji dopasowanie wzorców może być użyte do manipulowania terminami.

Ale mamy problem. i muszą być zakodowane jako terminy, podobnie jak dopasowanie wzorca. Radzenie sobie z tym wydaje się proste, dodając , i , ale czy będę musiał dodać inne warunki, aby wesprzeć ich manipulację? $\mathtt{reflect}$ $\mathtt{eval}$ $\mathsf{REFLECT}$ $\mathsf{EVAL}$ $\mathsf{MATCH}$

Należy dokonać wyboru projektu. Do czego powyższa funkcja powinna z i ? Czy przekształca ciało, czy nie? $R(-)$ $\mathtt{reflect}$ $\mathtt{eval}$ $R(-)$

Ponieważ nie jestem tak bardzo zainteresowany badaniem samego odbicia - rachunek różniłby się jako narzędzie do innych badań - nie chcę wymyślać koła na nowo.

Czy są jakieś kalkulatory, które pasują do tego, co właśnie opisałem?

O ile mogę stwierdzić, kalkulacje takie jak MetaML, zasugerowane w komentarzu, idą daleko, ale nie obejmują zdolności do dopasowywania wzorców i dekonstruowania fragmentów kodu, które zostały już zbudowane.

Jedno, co chciałbym móc zrobić, to:

$\mathtt{let}\ x=\lambda y.y\ \mathtt{in}\ \mathtt{reflect}\ x \to (\mathsf{LAM}\ (\mathsf{VAR}\ y)\ (\mathsf{VAR}\ y))$

Następnie wykonaj dopasowanie wzorca dla wyniku, aby zbudować zupełnie inne wyrażenie.

Z pewnością nie jest to konserwatywne rozszerzenie rachunku -kalkultu, a meta-teoria prawdopodobnie będzie brzydka, ale taki jest sens mojej aplikacji. Chcę rozbić -abstrakcje na części. $\lambda$ $\lambda$

— Dave Clarke
źródło

MetaML jest pisanym na maszynie językiem refleksyjnym, w którym operator bracketing wykonuje ODBICIE i rozpakowuje EVAL. Pisanie jest proste, ale możesz zobaczyć fragment odziedziczony z modalnego S4, działający jak ten papier, który może ci pomóc.

— ex0du5,

@ ex0du5: Dzięki, ale to nie idzie wystarczająco daleko, o ile mogę powiedzieć. Jasne, potrafię budować kod na różnych etapach, ale wydaje mi się, że nie jestem w stanie rozerwać terminów na części. (Przeczytam dokładniej, aby zobaczyć, czy coś przeoczyłem.)

— Dave Clarke

Schemat (bez zmienności i innych komplikacji)?

— Gilles „SO- przestań być zły”

@Gilles: Schemat to język programowania, a nie rachunek różniczkowy. Co więcej, nie sądzę, że może robić to, co chcę.

— Dave Clarke

@DaveClarke Język programowania to rachunek z wieloma brodawkami. Na pierwszy rzut oka wydaje się, że rdzeń Schematu jest odpowiedni, ale nie dałem wam wystarczająco dużo przemyśleń, aby się upewnić. Jak myślisz, co by nie zadziałało? (Wejdź na czat, jeśli chcesz.)

— Gilles „SO- przestań być zły”

15

Jean Louis Krivine wprowadził abstrakcyjny rachunek różniczkowy, który rozszerza „Krivine Machine” w bardzo nietrywialny sposób (zauważ, że maszyna Krivine już obsługuje instrukcję call / cc z lisp):

Wprowadza operator „cytowania” w tym artykule zdefiniowanym w następujący sposób: jeśli jest -term, zanotuj obraz przez jakiś bijection od terminów lambda do liczb naturalnych. Zanotuj cyfrę kościoła, która odpowiada . Krivine definiuje operatora według reguły oceny: Wierzę, że czarodziejstwo Kleene pokaże, że to wystarczy, aby zrobić to, co chcesz: tj. Zdefiniować ofertę i ewaluację operatory, jeśli jest obliczalne. $\phi$ $\lambda$ $n_\phi$ $\phi$ $\pi: \Lambda \rightarrow \mathbb{N}$ $\overline{n}$ $n\in\mathbb{N}$ $\chi$

χ ϕ \to ϕ \bar{n_{ϕ}}

$\chi\ \phi \rightarrow \phi\ \overline{n_\phi}$

π

$\pi$

Pamiętaj, że Krivine jest niezwykle trudny do przeczytania (proszę nie wściekaj się, jeśli to przeczytasz, Jean-Louis!), A niektórzy badacze podjęli charytatywną próbę wydobycia treści technicznych w bardziej czytelny sposób. Możesz spróbować zapoznać się z tymi notatkami Christophe Raffali.

Mam nadzieję że to pomoże!

Przyszło mi do głowy, że istnieje inne odniesienie, które może być istotne dla twoich zainteresowań: rachunek czystego wzoru Jaya i Kesnera formalizuje wariant -kalkusa, który rozciąga prostą abstrakcję nad zmienną na abstrakcję nad wzorem reprezentującym wzór rachunek różniczkowy. Jest to fenomenalnie ekspresyjne, a w szczególności pozwala dekonstruować samą aplikację: jeśli się nie mylę, termin: $\lambda$

(λ (x y) . x) ((λ x . x x) (λ y . y))

$(\lambda (x\ y). x)((\lambda x.x\ x)\ (\lambda y.y))$

redukuje do . Znowu, ja wierzę, że to jest więcej niż wystarczająco, aby wdrożyć cytat i eval operatorów. $\lambda x.x\ x$

— cody
źródło

Chciałbym głosować za tą z pozoru rozsądną odpowiedzią, ale nie mam pojęcia, czy w ogóle zaczyna ona odpowiadać na pytanie.

— Raphael

@Raphael czyta artykuły i dowiaduje się :) W rzeczywistości jest to tylko częściowa odpowiedź: artykuły rzeczywiście formalizują ważną cechę seplenia, której nie znaleziono w rachunku lambda: mianowicie operator QUOTE. Nie ma jednak obszernych badań metaoretycznych, po prostu wprowadzają je jako sposób wyrażenia pewnego rodzaju dziwnego nieprzejrzystego obliczenia w celu realizacji skomplikowanych aksjomatów teorii mnogości.

— cody

1

O ile dobrze pamiętam, w PPC nie można dopasowywać wzorców na powtórkach, dlatego podali je ze względu na zbieżność. Również w PPC dopasowanie wzorca jest ściśle dopasowane do dopasowanego, więc natychmiast zostanie znormalizowana do , wówczas próba dopasowania go do wzorca zakończy się niepowodzeniem.

(λ x . x x) (λ y . y)

$(\lambda x . x\ x)\ (\lambda y . y)$

λ y . y

$\lambda y . y$

(x y)

$(x\ y)$

— dzień

1

Jedyny cytat, jaki znam, to Lisp. Ale, jak pamiętam, zmienia to wszystko, co jest cytowane, w obiekt składniowy. „Funkcja” nie docenia wartości argumentu. Funkcja powinna pobrać wartość argumentu (ocenić go) i przekształcić z powrotem w jakieś wyrażenie składniowe, które ocenia (jak?) do tej wartości. Więc jeśli formalizm zajmuje się LISP , nie zbliżamy się do tego, co sugeruje pytanie.

q u o t e

$\mathtt{quote}$

r e f l e c t

$\mathtt{reflect}$

q u o t e

$\mathtt{quote}$

— babou

8

Jest to bardzo trudne, jeśli nie niemożliwe, bez rezygnacji z połączenia. Innymi słowy, podejrzewam, że masz rację co do owłosionej meta-teorii. Z drugiej strony możliwe jest zaprojektowanie rachunku kombinatora, który może wyrażać wszystkie funkcje obliczeniowe Turinga i który ma pełną zdolność do sprawdzania jego warunków: patrz Jay i Give-Wilson .

Uważam jednak, że posiadanie tej umiejętności ma negatywne skutki dla teorii równań. W szczególności będziesz w stanie udowodnić, że dwie wartości są równe, jeśli są równe do równoważności alfa.

Nie czytałem jeszcze związanej z nim papierowej kody, ale powinienem zauważyć, że w logice klasycznej zasadniczo masz tylko dwie rzeczy: prawdę i fałsz. Wszystko jest równoważne jednemu z nich. Oznacza to, że i tak masz tendencję do załamania się teorii równań.

— Philip JF
źródło

1

Zauważ, że rachunek Krivine'a nie jest rachunkiem zdań, ale raczej realizatorami tych, które mają wysoce nietrywialną teorię równań.

— cody

5

W teorii języków programowania funkcja, o której mówisz, jest zwykle określana jako „cytat”. Na przykład John Longley napisał o tym w niektórych swoich pracach, patrz ten artykuł .

Jeśli zastanawiasz się nad teoretycznymi rozważaniami (w przeciwieństwie do faktycznie użytecznej implementacji), możesz uprościć rzeczy, stwierdzając, że quote(lub reflectjak to nazywacie) mapuje się na typ liczb całkowitych nat, zwracając kod Gödel z jego argumentu. Następnie możesz rozłożyć liczbę, tak jak abstrakcyjne drzewo składniowe. Co więcej, nie potrzebujesz, evalponieważ można to zaimplementować w języku - jest to w zasadzie tłumacz języka.

$n \star m$ $\varphi_n(m)$ $\varphi_n$ $n$ $\lambda$ quote

Jeśli powiesz mi, czego szukasz, być może będę w stanie podać ci bardziej szczegółowe referencje.

Nawiasem mówiąc, oto otwarty problem:

$\lambda$ quote $\xi$

$\xi$

\frac{e_{1} \equiv e_{2}}{λ x . e_{1} \equiv λ x . e_{2}}

$\frac{e_1 \equiv e_2}{\lambda x \,.\, e_1 \equiv \lambda x \,.\, e_2}$

λ

$\lambda$

λ

$\lambda$ quotequote

\frac{e_{1} \equiv e_{2}}{q u o t e e_{1} \equiv q u o t e e_{2}},

$\frac{e_1 \equiv e_2}{\mathtt{quote}\,e_1 \equiv \mathtt{quote}\,e_2},$

q u o t e ((λ x . x) y) \equiv q u o t e y .

$\mathtt{quote}\,((\lambda x \,.\,x) y) \equiv \mathtt{quote}\, y.$ quote

λ

$\lambda$

— Andrej Bauer
źródło

β

$\beta$ quote

λ

$\lambda$

ξ

$\xi$

ξ

$\xi$

β

$\beta$

Poniższy artykuł pokazuje niektóre problemy z równaniem (ξ): Rachunek lambda jest algebraiczny, Peter Selinger. Ciekawe, coś nowego, o czym nie wiedziałem! Fajne.

— Transfinite Numbers

4

Oto alternatywna odpowiedź, zamiast korzystać z mojego nominalnego podejścia, które wciąż jest eksperymentalne, istnieje bardziej ugruntowane podejście, które wraca do artykułu:

LEAP: język z ewaluacją i polimorfizmem
Frank Pfenning i Peter Lee
https://www.cs.cmu.edu/~fp/papers/tapsoft89.pdf

Artykuł zaczyna się od:

Doprowadziło nas to do pytania, które po raz pierwszy postawił Reynolds, czy silnie pisane języki przyjmują tłumaczy metakrążonych. Konwencjonalna mądrość zdawała się wskazywać, że odpowiedź brzmiała „nie”. Nasza odpowiedź brzmi „prawie”.

Należy pamiętać, że LEAP jest znacznie silniejszy niż to, czego chce PO. Przede wszystkim jest napisane na maszynie. Po drugie, prosi o metakrążenie, co oznacza na przykład, że eval może wykonać własną definicję. W Prologu otrzymujesz metakołowość dla rozwiązania / 1:

solve(true).
solve((A,B)) :- solve(A), solve(B).
solve(H) :- clause(H,B), solve(B).

Jeśli dodasz następującą klauzulę, aby rozwiązać / 1:

solve(clause(H,B)) :- clause(H,B).

A jeśli zajmiesz się tym, ta klauzula / 2 zwróci również klauzule sol / 1. Następnie możesz wywołać polecenie Rozwiąż (rozwiązać (...)) i zobaczyć, jak wykonuje się ono sam.

Pytania o samo reprezentację wciąż pobudzają niektóre badania, patrz na przykład:

Autoprezentacja w systemie Girards U
Matt Brown, Jens Palsberg
http://compilers.cs.ucla.edu/popl15/popl15-full.pdf

— Liczby Transfinite
źródło

3

Problem został zidentyfikowany w pobliżu asystentów dowodowych, takich jak Coq i Isabelle / HOL. Pod nazwą akronim HOAS . Istnieją pewne twierdzenia na temat λ-Prolog, że dzięki nowemu kwantyfikatorowi things można tego dokonać. Ale nie mogłem jeszcze uchwycić tego twierdzenia. Wydaje mi się, że głównym spostrzeżeniem, jakie dotychczas uzyskałem, jest to, że nie ma określonego podejścia, istnieje kilka możliwych podejść.

Moje własne zdanie , jeszcze nie skończone , inspirowane jest niedawnym artykułem Paulsona na temat udowodnienia niekompletności Gödla. Używałbym obiektów wiążących na poziomie obiektu w połączeniu z pewną strukturą danych, która ma nazwy na poziomie meta. Zasadniczo podobna, ale odrębna struktura danych, jak ta z PO, oraz z kodowaniem Kościoła, ponieważ interesują mnie typy zależne:

datatype Expr = var Name                 /* written as n */
              | app Expr Expr            /* written as s t */
              | abs Name Expr Expr       /* written as λn:s.t */

Wyrażenia na poziomie meta można odróżnić od wyrażeń na poziomie obiektu, ponieważ używamy nazw zmiennych n, m, ... itd. Do oznaczenia nazw. Podczas gdy używamy nazw zmiennych x, y, .. itd. Na poziomie obiektu. Interpretacja meta terminu w logice obiektowej działałaby wówczas w następujący sposób. Napiszmy [t] σ do interpretacji terminu nominalnego t w kontekście nominalnym σ, który powinien dać termin obiektowy. Mielibyśmy wtedy:

 [n]σ = lookup σ n
 [s t]σ = [s]σ [t]σ
 [λn:s.t]σ = λx:[s]σ.[t]σ,n:x

Powyższe zdefiniowałoby, co OP nazywa funkcją EVAL. Mała różnica w stosunku do Paulsona, σ jest tylko skończoną listą, a nie funkcją. Moim zdaniem byłoby możliwe jedynie wprowadzenie funkcji EVAL, a nie funkcji REFLECT. Ponieważ na poziomie obiektu możesz mieć pewną równość, aby różne wyrażenia lambda były takie same. To, co musisz zrobić, to użyć ewaluacji do rozumowania, być może także do refleksji, jeśli czujesz taką potrzebę.

Musisz przejść do skrajności, takich jak Prolog, gdzie nic się nie rozszerza, jeśli chcesz zburzyć ścianę między wartością nominalną a wartością nominalną. Ale jak pokazuje przykład systemu λ-Prolog, w przypadku wyższego rzędu pojawiają się dodatkowe problemy, które można na przykład rozwiązać tylko logicznie, wprowadzając nowe środki, takie jak kwantyfikator ∇!

— Liczby Transfinite
źródło