Czy kombinacyjne terminy logiczne są zawsze większe?

9

Istnieje więc algorytm konwertujący warunki rachunku lambda na logikę kombinatoryczną za pomocą kombinatorów SK. Produkuje rzeczy, które eksplodują wielkością. Chciałbym dowiedzieć się więcej o tej eksplozji w rozmiarze. Nie mogę jednak wymyślić lepszego algorytmu. Słyszałem, że języki funkcjonalne są praktycznie kompilowane z kombinatorami, więc wydaje się, że musi istnieć lepszy algorytm. Przejrzałem artykuł Davida Turnera na ten temat, a on po prostu mówi, aby zastosować kilka optymalizacji i że powodują one „znaczną poprawę”.

Czy „znaczna poprawa” oznacza, że ​​rozmiar spada tylko do wielomianu? Czy istnieje znany sposób na przekształcenie terminów lambda w logikę kombinatoryczną przy jedynie zwiększeniu wielkości wielomianu (lub mniej?)? Jeśli taki algorytm istnieje, to czy jest on praktyczny?

Jake
źródło
artykuł pochodzi z 1979 r. Istnieje znacznie bardziej nowoczesne / najnowsze myślenie / technologia, w jaki sposób tłumaczyć kod na logikę, np. z układami FPGA i GPU, i ogólnie nie byłyby oparte na językach funkcjonalnych ....
dniu
Czy możesz wskazać mi je?
Jake,
badania, które przytaczasz, są bardziej teoretycznym „dowodem zasady” ... lepiej byłoby zacytować koncepcję / sekcję dotyczącą „wielomianowego wzrostu wielkości”, która wydaje się być przedmiotem twojego pytania ... czy jesteś zainteresowany ogólna teoria przekształcania kodu w logikę / obwody, po stronie teoretycznej lub stosowanej, czy teoria robienia tego efektywnie, czy obie? pytanie jest bardzo przekrojowe w różnych aspektach ... może uda się dowiedzieć więcej na czacie informatyki
vzn
1) Czy istnieje sposób na zaimportowanie tego do czatu? Nie mogę tego rozgryźć. 2) Nie ma sekcji o zwiększaniu wielkości wielomianu i to jest mój problem. W rzeczywistości nie mówi nic znaczącego (ani nie mogę znaleźć takich odniesień) na temat tego, jak duży jest wzrost wielkości.
Jake,
komentarze można zaimportować na czat po kilku osobnych opublikowanych komentarzach. to nie jest konieczne, aby rozpocząć czat. W przypadku wzrostu wielomianowego może to być koncepcja „plotek” lub „folkloru” na temat tej linii badań, co nie jest pewne. ale gdzie słyszałeś takie rzeczy, jak „produkuje rzeczy, które eksplodują rozmiarem”; pomocna byłaby bardziej szczegółowa itd.
dniu

Odpowiedzi:

4

nie jest ekspertem w tej dziedzinie, ale oto dwie prace historyczne, które wydają się być ściśle związane z pytaniem i jest to prawdopodobnie półaktywny obszar badań. Turner zaproponował zestaw kombinatorów, które można sprowadzić do kombinatorów SK. ten następny artykuł dowodzi, że kombinatory Turnera nawet nie zredukowane do kombinatorów SK prowadzą do wykładniczego wybuchu (i przypuszczalnie redukcja do SK byłaby jeszcze większa). ale drugi artykuł mówi, że istnieje wydajny algorytm kosmiczny O (n log n) oparty na kombinatorach Turnera. (wygląda na to, że poczyniono twierdzenia dotyczące wydajności wielomianowej, które są uważane za nie w pełni wykazane / niesprawdzone, a zatem są uważane za domniemania ...

  • Co to jest skuteczne wdrożenie rachunku λ? / Frandsen, Sturtivant (1991) (patrz str. 18)

    Ponadto pokazujemy, że implementacje oparte na kombinatorach Turnera lub super-kombinatorach Hughesa mają złożoność , tj. Wykładniczą dolną granicę. Otwarte jest, czy istnieje jakakolwiek implementacja złożoności wielomianowej , chociaż domniemano, że niektóre implementacje mają tę złożoność.2Ω(ν)νO(1)

  • Tłumaczenie Turner Combinators w przestrzeni O (n log n) / Noshita (1985)

    Przedstawiono praktyczną metodę reprezentacji kombinatorów Turnera, która w najgorszym przypadku potrzebuje tylko przestrzeni O (n log n) do tłumaczenia wyrażeń lambda długości n.

vzn
źródło
1
doskonały! Znalazłem ten artykuł także po wyszukaniu tych dwóch artykułów. sciencedirect.com/science/article/pii/002001908790161X Dzięki!
Jake