0x0f0f0f / gobba

A purely functional dynamically typed programming language.
https://0x0f0f0f.github.io/gobba-book/
MIT License
56 stars 2 forks source link

Recursion with lazy functions #1

Closed 0x0f0f0f closed 4 years ago

0x0f0f0f commented 4 years ago

There's a problem with laziness in recursion (with laziness in recursion (with laziness in recursion (with laziness ...))).

Non-recursive lazy functions work as expected, but as soon as a lazyfun is declared in a let rec statement, evaluation is stuck in an endless loop and stack overflows. After investigating a bit (trying factorial and fibonacci functions) I've found out that the problem occurs when arguments are passed to the recursive application. It seems that LazyExpressions passed as recursive application arguments never get evaluated.

https://github.com/0x0f0f0f/minicaml/blob/cfc0537dd8982b6696ba029181ebae956fdeb179/lib/eval.ml#L113-L134

Here's the example I've tried

let rec fib = lazyfun n -> if n < 2 then n else (fib (n - 1)) + (fib (n - 2)) in fib 5

Here's the factorial example

 let rec fact = lazyfun n -> if n < 2 then n else n * fact(n - 1) in fact 5
0x0f0f0f commented 4 years ago

Note that the fibonacci and factorial functions work correctly if they are not defined as lazy

0x0f0f0f commented 4 years ago

Temporarily removed lazyfun and lazylambda statements.

0x0f0f0f commented 4 years ago

The new single argument lambda abstraction fixes this issue.