Talk:Y combinator: Difference between revisions
Added comment on the Task...
GordonBGood (talk | contribs) (Added comment on the Task...) |
|||
Line 191:
[[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]]) 03:18, 26 May 2015 (UTC)
==Comment on the overall task==
For most languages it seems that this task is a joke, as the real use of the Y combinator is to apply recursion to a non-recursive function (often with recursion '''on variables''' otherwise not possible in that particular language) in order to get an output. In order to implement it, one requires recursion on either functions or lambda functions, as the expression of the Y conbinator requires it in all cases. By not allowing recursive state, this means that the definition of "Y (or fix) = x where x = f x" (in Haskell syntax) is not allowed as x is a variable state; indeed, for most strict languages this is not directly possible as it causes an infinite race and even with the addition of a lazy as in "let fix f = let rec x = lazy (f x) in x.force()" (F# syntax), this is still not possible in many more imperative type languages.
These languages may require something such as follows (C# syntax):
<lang csharp> T rv = default(T); // (or other initial condition of the recursion)
rv = new Lazy(() => rv) // note: gets the '''future value''' (by reference) of rv
rv = new Lazy(f(rv)); // note: f must be a function from a Lazy<T> to produce T
return rv.force(); // to get the non-lazy final value.</lang>
Note that the above code requires mutability of the 'rv' variable and also that it requires that the lambda retrieve the '''future version''' of rv. Most imperative type languages (and also functional languages other than Haskell) do have mutable variables '''but''' many (such as Rust) do not have the ability to refer to captured free variables future state (captured by value and not by reference as in C#). This would be the problem that this task would seek to address.
So, to break the infinite recursion, most of these implementations introduce a "Mu" type as in Haskell as follows:
<lang haskell>newtype Mu a = Roll { unroll :: Mu a -> a }
fix :: (a -> a) -> a
fix = \f -> (\x -> f (unroll x x)) $ Roll (\x -> f (unroll x x))
fac :: Integer -> Integer
fac = fix $ \f n -> if (n <= 0) then 1 else n * f (n - 1)</lang>
Note that the above starts the joke, as all we have done is move the recursive state from the outside at the "fix" function to the inside in the recursive function as 'n' in this case.
Part of the joke is that the above is useless: fix fac should produce Integer and an infinite race but it doesn't because the Haskell compiler knows category theory and the Lambda Calculus and can recognize (correctly) that this is an identity that just produces the 'f' function. In other words, it knows that we may as well have just written it as follows:
<lang haskell>fac n = if (n <= 0) then 1 else n * fac (n - 1)</lang>
which is '''the way one would normally write this recursively''' so that is what is effectively generated. In other word, using fix had absolutely no purpose, although it is possible to do it in this case as it doesn't require closures!
Now other compilers (even most functional language ones) aren't so smart and either produce an infinite race or are smart enough to recognize that it would be one and error out, but aren't smart enough to recognize the identity. In the case of dynamically typed languages, this can work by use of the delay/lazy functionality as in the Scheme example above, but this doesn't work for statically typed languages.
So other versions of combinator (Z combinator, etc.) are used such as F# and Ocaml (perhaps among others) as follows (using Haskell signature syntax):
<lang haskell>Y :: (('a -> 'b) -> 'a -> 'b) -> 'b</lang>
or as used in C# and Rust (perhaps among others) as follows (again in Haskell signature syntax):
<lang haskell>Y :: (('a -> 'b) - ('a -> 'b)) -> ('a -> 'b)</lang>
However, the joke continues as these are just as useless when applied to a function that is already recursive.
The real purpose of the fixed point Y combinator is to implement recursion on functions that are not recursive, as in the fibs definition in the Haskell section as follows:
<lang haskell>fibs_ a = 0:1:(fix zipP a (tail a))
where
zipP f (x:xs) (y:ys) = x+y : f xs ys
fibs() = fix fibs_ -- a function so that the head of the lazy list is not held in memory</lang>
Now this (lazy) list based implementation actually has a purpose as the lambda function is not easy to write in many languages and often depends on being able to write using recursive state and often versions of fix cause recursion in evaluation or runtime over the function.
'''So I propose some changes/additions to this task as follows''':
1. clarifying that the form "fix f = f (fix f)" does not have recursive state as discussed above but that "fix f = let x = f x in x" does have recursive state, which is not allowed.
2. Adding an objective to the task to use the 'fix'/'Y' function to generate a lazy list such as the above 'fibs' example.
Most languages have a built in "lazy" capability although it may be optional, but if not a non-thread safe version can easily be generated as follows (for Go language):
<lang golang>type Lazy struct {
value *whatever_type_is_to_be_included // go doesn't have generics
genf func() *whatever_type_is_to_be_included // might use interface{} for a poor man's generics
}
func (lzy *Lazy) force() *whatever_type_is_to_be_included {
if lzy.genf != nil { // not thread-safe
lzy.value = oll.genf()
lzy.genf = nil
}
return lzy.value
}</lang>
Given Lazy above, it is generally just as easy to build a LazyList, as follows (again in Go):
<lang golang>type LazyList struct {
head *big.Int
tail *Lazy // Lazy of LazyList; should not be accessed directly only through method
}
func (oll *LazyList ) rest() *LazyList {
return oll.tail.force()
}</lang>
or optionally combine the Lazy and the LazyList
<lang golang>type LazyList struct {
head *big.Int
tail *LazyList // should not be accessed directly only through method
contf func() *LazyList
}
func (oll *LazyList ) Rest() *LazyList {
if oll.contf != nil { // not thread-safe
oll.tail = oll.contf()
oll.contf = nil
}
return oll.tail
}</lang>
Examples for languages capable of generating 'fibs' as per this algorithm would be truly useful and not a joke.
| |||