Optymalizator kombinacji Y i ogona

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ć?

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.

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.