Just for fun. The 'Y combinator' Nim code on rosettacode does not seem to be a true Y combinator. The following is the call-by-value Y combinator.
type M[T] = object
m: proc(a:M[T]):T
proc O[T](f:M[T]):proc(a:M[T]):T = f.m
proc I[T](f:proc(a:M[T]):T):M[T] = M[T](m: f)
# call by name, requires lazyness
# proc y[T](f:proc(a:T):T):T =
# (proc(x:M[T]):T = f(O(x)(x)))(I(proc(x:M[T]):T = f(O(x)(x))))
# call by value, works strictly
proc y[T](f:proc(a:proc(t:T):T):proc(t:T):T):proc(t:T):T =
(proc(x:M[proc(t:T):T]):proc(t:T):T = f(proc(v:T):T = O(x)(x)(v)))(
I(proc(x:M[proc(t:T):T]):proc(t:T):T = f(proc(v:T):T = O(x)(x)(v))))
let
fac = proc(f:proc(x:int):int):proc(x:int):int =
(proc(n:int):int = (if n==0: 1 else: n*f(n-1)))
fib = proc(f:proc(x:int):int):proc(x:int):int =
(proc(n:int):int = (if n==0: 0 elif n==1: 1 else: f(n-1)+f(n-2)))
echo y(fac)(10)
echo y(fib)(20)
We could probably use something similar to get recursive (closure) iterators, perhaps with less nice syntax than ideal. I was just discussing such an approach with @sschwarzer in private communications, but ran into "type trouble". The essence of the Y/Z combinator is, of course, to build "body recursion" from "self-application at the parameter list level".
type # illegal recursion in type
RecItr = iterator(x: openArray[int], rest: RecItr): seq[int]
iterator rec(x: seq[int], rest: RecItr): seq[int] {.closure.} =
if x.len > 0:
let here: seq[int] = x[0..0]
yield here
let itr = rest(x[1..^1], rest)
for it in itr():
yield it
let y: seq[int] = @[6, 3, 9, 1]
for k in rec(y, rec):
echo k
type
RecProc1 = proc(x: openArray[int], rest: RecProc2): seq[int]
RecProc2 = proc(x: openArray[int], rest: RecProc1): seq[int]
It's disappointing that Nim doesn't allow cyclic procedural types, like the one you wanted to write, but not too surprising. OCaml requires a special flag to compile types like this
# type cont = int -> cont -> int list;;
Error: The type abbreviation cont is cyclic
# type cont = Cont of (int -> cont -> int list);;
type cont = Cont of (int -> cont -> int list)
type
RecProc[T] = object
call: proc(x: T, c: RecProc[T]): seq[T]
Any reason why Nim doesn't support this directly? I'm reminded of a fun article about continuations where the thing preventing the implementation of a slick treemerge in pascal was the inability to define a function of a certain cyclic type.
That is a fun article. I did not really need/want a recursive proc type..That was just a side trip. @Araq would have to answer as to project priorities.
What I did want to write was a recursive iterator to use in the context of multiway trees. As mentioned by the OP, alluded to by me earlier, and reiterated by @bpr, the wrapper object trick does work for that:
type
Itr = object
itr: iterator(x:openArray[int], rest:Itr): seq[int]
iterator rec(x:openArray[int], rest:Itr): seq[int]{.closure.} =
if x.len > 0:
yield x[0..0]
for e in rest.itr(x[1..^1], rest):
yield e
let y: seq[int] = @[6, 3, 9, 1]
let itr = Itr(itr: rec)
for k in rec(y, itr): echo k
Maybe I have a bug or there's a codegen bug. Anyway, it seems by Z combinator construction that Nim has (or almost has) had recursive iterators all along.. :-)
@rockcavera - I think I was wrong about my last example. While the object wrapper fixes the type recursion issue, the fact that closure iterators "resume" and so want/need a factory proc to establish their parameters prevents recursion on the argument list working the way I was trying. But this works fine (on versions of nim back to at least 0.19):
proc makeItr(n: int): iterator(): int =
result = iterator(): int =
if n > 0:
yield n
let it = makeItr(n - 1)
for e in it(): yield e
var it = makeItr(6)
for i in it(): echo i # Output: 6 5 4 3 2 1
It's honestly close enough to the way one would ordinarily use closure iterators that I might suggest updating the manual with this example saying Nim doesn't have recursive iterators exactly, but the above works (whatever that should be called), and I don't think it super unfair to say Nim had "a kind" of recursive closure iterators all along.
Also, if you want to make the code look more recursive (maybe subjective...), you can add a for-loop macro to some thatDef.nim module:
import macros # This needs {.experimental: "forLoopMacros".}
macro toItr*(x: ForLoopStmt): untyped =
## Convert factory proc call for inline-iterator-like usage.
## E.g.: ``for e in toItr(myFactory(parm)): echo e``.
let expr = x[0]
let call = x[1][1] # Get foo out of toItr(foo)
let body = x[2]
result = quote do:
block:
let itr = `call`
for `expr` in itr():
`body`
import thatDef
{.experimental: "forLoopMacros".}
proc makeItr(n: int): iterator(): int =
result = iterator(): int =
if n > 0:
yield n
for e in toItr(makeItr(n - 1)): yield e
for i in toItr(makeItr(6)): echo i # Output: 6 5 4 3 2 1
The 'Y combinator' Nim code on rosettacode does not seem to be a true Y combinator. The following is the call-by-value Y combinator...
I am the contributor of the Nim RosettaCode Y-Combinator, and noticed your post here but just got around to replying and commenting:
I think what you are seeing is just a difference in terminology and implementation details, as your "call-by-value Y combinator" is called the Z combinator by some as it differs from what is usually called the Y combinator (as you call the "call-by-name Y combinator) by one beta transformation. In fact, your implementation of your "call-by-value Y combinator" is identical to my RosettaCode Z combinator other than my use of the "sugar" library to make the code more readable (or at least more resembling forms as used in a functional language), my code allowing for the function input type T being different from the output type TResult instead of both being the same as your T generic type, and the formulation which simplifies by embedding the effect of your O[T] and I[T] functions into the calculation of my g function by simple transformations. There are other contributions in other languages that follow either of the forms, yours or mine; my g implementation is like the Haskell contribution but with the transformation that turns it into a "call-by-value Y combinator" equals the Z combinator.
While mathematically correct, use of these methods of implementing recursion is really just a "toy" application as the common examples of their use build stack for every recursion, even for languages that guaranty Tail-Call-Optimization (TCO) when the recursive call is in tail call position (Nim cannot make that guaranty as it uses other languages as the back-end compiler which don't make that guaranty) as the examples (for instance fibonacci) don't put the recursive calls into tail call position.
That is why at the end of my Nim RosettaCode contribution I implement the "call-by-name Y combinator" including laziness as it requires (in two different ways) and then show a better application of this in generating an infinite lazy Fibonacci sequence that does not build stack and which might actually be useful, although with Nim we don't actually require the Y combinator to do this. As noted there, using the Y combinator in this way is related to Continuation Passing Style (CPS) and how it can be used to implement recursive algorithm programs which can prevent building stack by deferring computations using laziness.
This is what Haskell has built into the language and the Haskell RosettaCode Y combinator contribution discusses this to some extent.