StandardML factorial evaluation enters infinite loop in Poly/ML REPL

110 views Asked by At

The following factorial function is well and good...

Poly/ML 5.8.3 Development (Git version v5.8.2-297-g8185978a)
> fun fact 0 = 1
# | fact n = n * fact(n-1);
val fact = fn: int -> int
> fact 2;
val it = 2: int
>

But the following takes the Poly REPL into infinite loop.

Poly/ML 5.8.3 Development (Git version v5.8.2-297-g8185978a)
> fun fact 0 = 1
# | fact n = n * fact n-1;
val fact = fn: int -> int
> fact 2;

Wondering what could be causing this??

2

There are 2 answers

0
sshine On BEST ANSWER

Since ForceBru already gave an adequate answer, for completion, here is an example of evaluating this by hand that should reveal the infinite recursion:

fact 2 ~> 2 * fact 2-1
       ~> 2 * (2 * fact 2-1)-1
       ~> 2 * (2 * (2 * fact 2-1)-1)-1
       ~> 2 * (2 * (2 * (2 * fact 2-1)-1)-1)-1
       ~> ...
3
ForceBru On

n * fact n-1 is the same as n * (fact n) - 1 - thus, n is never decreased, and your code ends up calling fact 2 over and over and over again.