Optymalizator kombinacji Y i ogona

20

Definicja kombinatora Y w F # to

let rec y f x = f (y f) x

f oczekuje, że jako pierwszy argument będzie miała kontynuację rekurencyjnych podproblemów. Używając yf jako kontynuacji, widzimy, że f będzie stosowane do kolejnych wywołań w miarę rozwoju

let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...

Problem polega na tym, że z góry ten schemat wyklucza stosowanie jakiejkolwiek optymalizacji wywołania ogona: w rzeczy samej, może być pewna operacja oczekująca na f, w którym to przypadku nie możemy po prostu mutować lokalnej ramki stosu powiązanej z f.

Więc :

  • z jednej strony użycie kombinatora Y wymaga wyraźnej innej kontynuacji niż sama funkcja.
  • w innych przypadkach, aby zastosować TCO, chcielibyśmy, aby żadna operacja nie oczekiwała na f, a jedynie wywołanie samej f.

Czy znasz jakiś sposób na pogodzenie tych dwóch rzeczy? Jak Y z akumulatorem, czy Y z sztuczką CPS? A może argument dowodzący, że nie da się tego zrobić?

Nicolas
źródło
Czy dodałeś klucz rec do swojej implementacji? Powinienem pomyśleć, że potrzebuje tego po przeczytaniu ...
Jimmy Hoffa,
Czy masz dowód, że nie optymalizuje ogona? Powinienem pomyśleć, że możesz przeczytać IL dla tej funkcji i przekonać się, nie zdziwiłbym się, gdyby kompilator był wystarczająco inteligentny, aby coś wymyślić.
Jimmy Hoffa,
w przypadku prostej niepowiązanej rekurencji nie: jednak można ją przepisać, aby pozwolić na takie rzeczy, z zastrzeżeniem faktu, że ramka stosu jest ponownie wykorzystywana przez wywołanie y. tak, może trzeba zobaczyć IL, bez doświadczenia w tym.
nicolas
5
Założyłem konto i otrzymałem 50 punktów za komentarz. To pytanie jest naprawdę interesujące. Myślę, że to zależy całkowicie f. Widzimy, że to ymoże zadzwonić fz trzaskiem (y f), ale, jak mówisz, fmoże mieć trochę oczekującej operacji. Myślę, że byłoby interesujące wiedzieć, czy istnieje oddzielny kombinator, który jest bardziej przyjazny dla ogona. Zastanawiam się, czy to pytanie zwróciłoby większą uwagę na stronie CS Stackexchange?
John Cartwright,

Odpowiedzi:

4

Czy znasz jakiś sposób na pogodzenie tych dwóch rzeczy?

Nie, i nie bez powodu, IMHO.

Kombinator Y jest teoretyczną konstrukcją i jest potrzebny tylko do ukończenia rachunku lambda (pamiętaj, że w rachunku lambda nie ma pętli, ani lambda nie mają nazw, których moglibyśmy użyć do rekurencji).

Jako taki, kombinator Y jest naprawdę fascynujący.

Ale : Nikt tak naprawdę nie używa kombinatora Y do faktycznej rekurencji! (Z wyjątkiem może dla zabawy, aby pokazać, że to naprawdę działa.)

Optymalizacja połączeń ogonowych, OTOH, jest, jak sama nazwa wskazuje, optymalizacją. Nie wnosi nic do ekspresji języka, zależy nam tylko na względach praktycznych, takich jak przestrzeń stosu i wydajność kodu rekurencyjnego.

Twoje pytanie brzmi zatem: czy istnieje sprzętowa obsługa redukcji wersji beta? (Wiesz, redukcja beta to sposób, w jaki wyrażenia lambda są redukowane.) Ale żaden funkcjonalny język (o ile mi wiadomo) nie kompiluje swojego kodu źródłowego do reprezentacji wyrażeń lambda, które zostaną zmniejszone w czasie wykonywania.

Ingo
źródło
2
Kombinator Y przypomina ponowne wpisywanie węzła, który po każdym użyciu staje się rozwiązany. Większość systemów skraca to i wiąże węzeł na poziomie meta, tak że nigdy nie trzeba go ponownie próbować.
Dan D.,
1
Co do ostatniego akapitu, należy rozważyć Haskell, które w jego sercu wykorzystuje obniżenie wykres zrobić oceny leniwy. Ale moim ulubionym jest optymalna redukcja, która zawsze podąża ścieżką w sieci Church-Rosser z najmniejszymi redukcjami do pełnej normalnej formy. Tak jak w Asperti i Guerrini's The Optimal Implementation of Functional Programming Languages . Zobacz także BOHM 1.1 .
Dan D.,
@DanD. Dzięki za linki, wypróbuję je później w przeglądarce obsługującej PostScript. Pewnie jest dla mnie coś do nauczenia. Ale czy jesteś pewien, że skompilowany haskell redukuje wykresy? Wątpię w to.
Ingo
1
W rzeczywistości wykorzystuje redukcję wykresów: „GHC kompiluje się do bezgotówkowej maszyny tagless G (STG). Jest to hipotetyczna maszyna do redukcji wykresów (tj. Maszyna wirtualna, która wykonuje redukcje wykresów, jak opisano powyżej)”. Od ... Więcej informacji na temat urządzenia STG patrz Simon Peyton Jones wykonawczych leniwe języków funkcyjnych na sprzęcie Stock: Spineless Tagless G-maszyna .
Dan D.
@DanD. w tym samym artykule, który podłączyłeś, czytamy dalej, że GHC „dokonuje szeregu optymalizacji tej reprezentacji, zanim ostatecznie skompiluje ją w prawdziwy kod maszynowy (prawdopodobnie za pomocą C przy użyciu GCC)”.
Ingo
0

Nie jestem całkowicie pewien tej odpowiedzi, ale jest to najlepsze, co mogłem wymyślić.

Kombinator y jest z natury leniwy, w ścisłych językach lenistwo należy dodać ręcznie poprzez dodatkowe lambdas.

let rec y f x = f (y f) x

Twoja definicja wygląda tak, jakby wymagała lenistwa w celu jej zakończenia, w przeciwnym razie (y f)argument nigdy nie zakończyłby oceny i musiałby ocenić, czy go użyjesz, czy nie f. TOC w leniwym kontekście jest bardziej skomplikowany, a ponadto wynikiem (y f)jest powtarzanie kompozycji funkcji bez zastosowania z x. Nie jestem pewien, czy potrzeba wziąć pamięć O (n), gdzie n jest głębokością rekurencji, ale wątpię, czy można osiągnąć taki sam rodzaj spisu treści, jak to możliwe przy czymś takim (przejście na Haskell, ponieważ tak naprawdę nie wiem FA#)

length acc []    = acc
length acc (a:b) = length (acc+1) b 

Jeśli jeszcze tego nie wiesz, różnica między Haskellem foldla foldl'Haskellem może nieco wyjaśnić sytuację. foldljest napisane tak, jak by to było w chętnym języku. Ale zamiast być TOC, jest tak naprawdę gorzej niż foldrdlatego, że akcelerator przechowuje potencjalnie ogromny kawał, którego nie można częściowo ocenić. (Jest to związane z tym, dlaczego zarówno foldl, jak i foldl 'nie działają na nieskończonych listach.) Tak więc w nowszych wersjach Haskell, foldl'dodano, która wymusza ocenę akumulatora za każdym razem, gdy funkcja się powtarza, aby zapewnić, że nie powstanie ogromne uderzenie. Jestem pewien, że http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 może to wyjaśnić lepiej niż ja.

Ericson2314
źródło