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ć?
f#
recursion
tail-call
continuation
Nicolas
źródło
źródło
f
. Widzimy, że toy
może zadzwonićf
z trzaskiem(y f)
, ale, jak mówisz,f
moż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?Odpowiedzi:
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.
źródło
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.
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 nief
. TOC w leniwym kontekście jest bardziej skomplikowany, a ponadto wynikiem(y f)
jest powtarzanie kompozycji funkcji bez zastosowania zx
. 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#)Jeśli jeszcze tego nie wiesz, różnica między Haskellem
foldl
afoldl'
Haskellem może nieco wyjaśnić sytuację.foldl
jest napisane tak, jak by to było w chętnym języku. Ale zamiast być TOC, jest tak naprawdę gorzej niżfoldr
dlatego, ż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.źródło