Re:Function Inheritance Is Fun and Easy
by csense on Sunday September 27, 2015 @12:46AM
(#10285507)
I've read a couple recent articles about the Y combinator on HN, and it seems like an interesting theoretical concept for e.g. showing that lambda calculus is Turing-complete.
But while it might be useful in minimalist contexts like the lambda calculus without much built-in functionality, what problem is it solving in this context?
It seems like a much more straightforward way to accomplish the same thing, without needing the Y combinator, would be (in Python syntax):
Re:Function Inheritance Is Fun and Easy
by smosher_ on Sunday September 27, 2015 @02:30AM
(#10285678)
It's because the generator recurses with:
return fself(num - 1) + fself(num - 2);
instead of calling fib (or fib_gen) explicitly. fself is passed into the generator and it will need to be passed in again and again. That's what Y gets you. You could get tracing the way you suggest from something like:
let fib f n =
let n' = (* compute fib for n *) in
f n'
and supply some f that will log (and return) the computed values, but that won't work with the motivating example: memoization. This really should have been clearer in TFA.
It's worth noting the memoization in the linked gist isn't pure. memo() allocates a cache and returns a function that references it. The cache is updated by mutating in place. After all the hoops we've jumped thorugh it's a bit of a let-down to end up here. (It's doable though.)
Re:Function Inheritance Is Fun and Easy
by Lord_DeathMatch on Sunday September 27, 2015 @02:21AM
(#10285662)
As it is here, yeah, only once at the root level. But if you were to use it as a decorator on the original function, and reassign to the original name (as the decorator syntax does), it would print at every level, as the recursive call would bind to the decorated function.
Re:Function Inheritance Is Fun and Easy
by dwenzek on Monday September 28, 2015 @05:59AM
(#10289619)
Nice. But the implementation has some subtleties.
I use OCaml.
Fist, `fix f` must explicitly be defined as a function.
If we replace the expression `fun n -> f (fix f) n` by `f (fix f)`
then we got "Stack overflow during evaluation" of fix(f).
let rec fix f = fun n -> f (fix f) n
Then fix can be applied to some generator :
let fibgen(fib) =
fun n -> if n = 0 then 0
else if n = 1 then 1
else fib(n-1) + fib(n-2)
let fib = fix(fibgen)
assert (fib 6 = 8)
The compose and trace functions pose no issue.
let (>>) f g x = f(g(x))
let trace f_name f = fun n ->
Format.printf "%s(%d)\n%!" f_name n;
f n
let trace_fib = fix (trace "fib" >> fibgen)
But the memoize function cannot simply be defined as `memoize f = fun n -> ...`,
otherwise a fresh cache will be used for each call !
Indeed, `fix f` is called for each recursive call in the generator.
In the case of `fix (memoize >> fibgen)` memoize is recursively called
with a new function to be cached.
Hence, the use of an extra step to explicitly create once the cache.
let memoize size =
let cache = Hashtbl.create size in
fun f n ->
try Hashtbl.find cache n
with Not_found -> (
let r = f n in
Hashtbl.add cache n r;
r
)
let memoize_fib = fix (memoize 16 >> trace "fib" >> fibgen)
Last subtilty: the order of application of the misc transformers.
When we write `memoize 16 >> trace "fib" >> fibgen`,
the resulting function `f` adds
, in order, memoization, trace and fib recursive computation
to itself in disguise `fix f`.
The latter applied transformation takes the control. Here the fib computation
only calls the chain `fix f` if n is greater than 1.
So, a call to `trace_fib(0)` leads to no trace;
and a call to `memoize_fib(6)` caches the results for 4 and 5 but not for 6.
Hence, to memoize all calls and trace only actual call to fib,
we must reorder the transformations:
I find it interesting how category theory and higher-order functions are to functional programming what design-patterns are to OOP.
But while it might be useful in minimalist contexts like the lambda calculus without much built-in functionality, what problem is it solving in this context?
It seems like a much more straightforward way to accomplish the same thing, without needing the Y combinator, would be (in Python syntax):
Why is the Y combinator needed for this? I don't get it.It's worth noting the memoization in the linked gist isn't pure. memo() allocates a cache and returns a function that references it. The cache is updated by mutating in place. After all the hoops we've jumped thorugh it's a bit of a let-down to end up here. (It's doable though.)
(Edit: improve clarity.)
Fist, `fix f` must explicitly be defined as a function. If we replace the expression `fun n -> f (fix f) n` by `f (fix f)` then we got "Stack overflow during evaluation" of fix(f).
Then fix can be applied to some generator : The compose and trace functions pose no issue. But the memoize function cannot simply be defined as `memoize f = fun n -> ...`, otherwise a fresh cache will be used for each call ! Indeed, `fix f` is called for each recursive call in the generator. In the case of `fix (memoize >> fibgen)` memoize is recursively called with a new function to be cached.Hence, the use of an extra step to explicitly create once the cache.
Last subtilty: the order of application of the misc transformers. When we write `memoize 16 >> trace "fib" >> fibgen`, the resulting function `f` adds , in order, memoization, trace and fib recursive computation to itself in disguise `fix f`. The latter applied transformation takes the control. Here the fib computation only calls the chain `fix f` if n is greater than 1. So, a call to `trace_fib(0)` leads to no trace; and a call to `memoize_fib(6)` caches the results for 4 and 5 but not for 6.Hence, to memoize all calls and trace only actual call to fib, we must reorder the transformations: