Rozwiązywanie równań funkcyjnych dla nieznanych funkcji w rachunku lambda

14

Czy są jakieś techniki rozwiązywania równań funkcyjnych dla nieznanych funkcji w rachunku lambda?

Załóżmy, że mam funkcję tożsamości zdefiniowaną jako taką:

jax=x

(czyli przez spisanie równanie dla oczekiwanego zachowania tej funkcji), a teraz chcę go rozwiązać za wykonując jakąś transformację algebraicznym uzyskać intensional formułę dla tej funkcji:ja

ja=λx.x

mówi, jak dokładnie funkcja wykonuje to, czego oczekiwano (to znaczy, jak zaimplementować ją w rachunku lambda).

Oczywiście funkcja tożsamości jest używana tylko jako przykład. Interesują mnie bardziej ogólne metody rozwiązywania takich równań. W szczególności chciałbym znaleźć funkcję która spełnia następujące wymagania:b

bfa(λx.M.)=(λx.faM.)

to znaczy „wstrzykuje” daną funkcję do podanej funkcji lambda przed jej „ciałem” (co jest pewnym arbitralnym wyrażeniem lambda), być może przez rozebranie jej i skonstruowanie nowej, tak aby stała się parametr, do którego stosowana jest funkcja .fa(λx.M.)M.fa

BarbaraKwarc
źródło

Odpowiedzi:

13

Jest to znany problem, znany jako unifikacja wyższego rzędu .

Niestety ten problem jest ogólnie nierozstrzygalny. Jest rozstrzygalny fragment, znany jako Fragment Wzoru Millera. Jest szeroko stosowany, między innymi, do sprawdzania typów programów zależnie wpisywanych z metawetami lub dopasowywaniem wzorców. W tym fragmencie zmienne unifikacyjne są stosowane tylko do wyraźnie powiązanych zmiennych programu.

Ten papier stanowi świetny samouczek na temat tego, jak działa ujednolicenie wyższego rzędu, i przedstawia (stosunkowo) jego prostą implementację.

Niestety nie wygląda na to, aby twoja funkcja mieściła się w tym fragmencie wzorca. To powiedziawszy, to, co widzę, jest bardzo podobne do składu funkcji. Czy poniższa funkcja spełnia twoje wymagania?

b=λfa sol x .fa (sol x)

Mamy:

  • b fa (λx.M.)
  • przezrównoważność α=b fa (λy.[y/x]M.)α
  • =λx.fa ((λy.[y/x]M.)x)
  • =λx.fa ([x/y][y/x]M.)
  • =λx.fa M.
jmite
źródło
1
Tak, wygląda na to :) Zabawne jest to, że prawie mam to rozwiązanie, ale z jakiegoś powodu pomyślałem, że wywołanie na czymś „wykonałoby to”, zepsując wyrażenie: q To, co przeoczyłem, to że możemy zastąpić zmienną inną zmienną związaną na zewnątrz. (λx.M.)
BarbaraKwarc,
1
Dzięki za link do artykułu, sprawdzę go i za kilka dni zaakceptuję twoją odpowiedź, aby dać innym szansę.
BarbaraKwarc,
3
Czy to zjednoczenie wyższego rzędu? Wydaje się, że pytanie dotyczy raczej niepisanego rachunku lambda, a nie zwykłego rachunku lambda.
Peter Taylor
2

Myślę, że mam częściową odpowiedź dotyczącą równania z funkcją tożsamości:

Ix=x

Chcemy go rozwiązać, znajdując wzór na , który będzie miał postać ( λ p . M ) z pewnym nieznanym jeszcze wyrażeniem M jako jego ciałem. Zastąpmy to ja w pierwotnym równaniu:I(λp.M)MI

(λp.M)x=x

następnie zastosuj funkcję do po lewej stronie:x

M[p/x]=x

Ale co tu mamy? :> To równanie jest wzorem dla wyrażenia , którego szukamy, po podstawieniu każdego wystąpienia p w nim x , i mówi, że powinno ono wyglądać jak prawa strona :) Innymi słowy, funkcja szukaliśmy to:Mpx

I=(λx.x)

która oczywiście jest poprawną odpowiedzią :)


Wypróbujmy to samo podejście, aby znaleźć wzór na kombinator . Chcemy, aby działał w taki sposób, aby po nałożeniu na siebie wytworzył się przyłożony do siebie:ω

ωω=ωω

Teraz znaleźliśmy formułę , który ma postać ( λ x . M ) z jakiegoś nieznanego jeszcze ekspresji M . Podstawiając to do równania otrzymujemy:ω(λx.M)M

(λx.M)ω=ωω

Zastosowanie go do parametru po lewej stronie daje wzór na :M

M[x/ω]=ωω

Oznacza to, że po podstawieniu każdego wystąpienia w M przez ω wytworzyło sięxMω , więc możemy wywnioskować, że oryginalne wyrażenie M przed podstawieniem powinno być xωωMxx

ω=(λx.xx)

co jest w rzeczywistości :)


Mam jednak wrażenie, że może być tak łatwo tylko dlatego, że prawa strona była już w takiej formie, jakiej szukamy.

BarbaraKwarc
źródło
M[x/ω]=ωωω=(λx.xx)
W tych dwóch prostych przypadkach - tak, istnieje: po prostu odwróć podstawienie. Ale jak powiedziałem, te przypadki mogą działać na zasadzie „szczęścia”: że prawa strona jest już w wymaganej formie. Kiedy spróbowałem z bardziej złożonymi przykładami, to nie zadziałało. Tego właśnie szukam: algorytmicznie.
BarbaraKwarc
1
ωω=ωωωω