Tail-Recursive Calls with a Lambda-Calling Argument < Tell me, Schemer! < Viivi's Cell < Entrance

[Resolved] About the Scope in the Tail-Recursive Calls with a Lambda-Calling Argument

The problem of tail recursion with a Lambda call as an argument did not work as expected, which I had asked about on this page, has been resolved.
This correction will be reflected in Viivi version 00.22.00.

The correct evaluation did not take place because the binding of the argument had been registered in the binding environment of the closure own.
This is a basic mistake, and I am totally embarrassed about it.
The trace output of the three code runs with the corrected version is shown below.

Mathematically speaking, the correct terminating-condition in the recursion for the factorial calculation might be

0! = 1，

i.e.,

return 1, if (= n 0),

where the mathematical symbol '!' is the post-operator of the factorial calculation.
To make the explanation clearer, however, we adopt here a different terminating-condition

1! = 1，

i.e.,

return 1, if (= n 1).

If we use the mathematically-correct terminating-condition, the bound-values of the symbol 'result' become the same value 1 for different values 1 and 0 of 'n'.
This makes ambiguous the update of the binding-relationship of the symbol 'result'.

[1] In case of a (Non-TRC) Normal-Recursive Call

We begin with a factorial-calculation code of a (NON-TAIL-Recursive-Call) NORMAL-Recursive Call:

		
				
:::::::::::::::::::
:: factorial.scm ::
:::::::::::::::::::
   1:   (define !
   2:     (lambda (n)
   3:       (if (= n 1)
   4:         1
   5:         (* n (! (- n 1))))))
   6: 
   7:   (! 2)
   8:

Each Scheme source code is shown with its filename and the line-numbers like this.
Here we give the argument 2 at the top-level.

		
			
$ viivi -K factorial.scm
		...
        4: ┌─ (! 2)
        4: │┌─ !
        5: │└─ #<closure:[(n)] [(if (= n 1) 1 (* n (! (- n 1))))]>
        5: │┌─ 2
        6: │└─ 2
        6: │ * #<closure:[(n)] [(if (= n 1) 1 (* n (! (- n 1))))]>
        6: │ ○  n  →  2
        6: │┌─ (if (= n 1) 1 (* n (! (- n 1))))
        6: ││┌─ if
        7: ││└─ #<procedure:if>
        7: ││ * #<procedure:if>
        7: ││┌─ (= n 1)
        7: │││┌─ =
        8: │││└─ #<procedure:=>
        8: │││┌─ n
        9: │││└─ 2
        9: │││┌─ 1
       10: │││└─ 1
       10: │││ * #<procedure:=>
       11: ││└─ #f
       11: ││┌─ (* n (! (- n 1)))
       11: │││┌─ *
       12: │││└─ #<procedure:*>
       12: │││┌─ n
       13: │││└─ 2
       13: │││┌─ (! (- n 1))
       13: ││││┌─ !
       14: ││││└─ #<closure:[(n)] [(if (= n 1) 1 (* n (! (- n 1))))]>
       14: ││││┌─ (- n 1)
       14: │││││┌─ -
       15: │││││└─ #<procedure:->
       15: │││││┌─ n
       16: │││││└─ 2
       16: │││││┌─ 1
       17: │││││└─ 1
       17: │││││ * #<procedure:->
       18: ││││└─ 1
       18: ││││ * #<closure:[(n)] [(if (= n 1) 1 (* n (! (- n 1))))]>
       18: ││││ ●  n  →  1
       18: ││││┌─ (if (= n 1) 1 (* n (! (- n 1))))
       18: │││││┌─ if
       19: │││││└─ #<procedure:if>
       19: │││││ * #<procedure:if>
       19: │││││┌─ (= n 1)
       19: ││││││┌─ =
       20: ││││││└─ #<procedure:=>
       20: ││││││┌─ n
       21: ││││││└─ 1
       21: ││││││┌─ 1
       22: ││││││└─ 1
       22: ││││││ * #<procedure:=>
       23: │││││└─ #t
       23: │││││┌─ 1
       24: │││││└─ 1
       25: ││││└─ 1
       26: │││└─ 1
       26: │││ * #<procedure:*>
       27: ││└─ 2
       28: │└─ 2
       29: └─ 2

[2] In case of a Simple Tail-Recursive Call

Let's move to another version of a tail-recursive-call for the same factorial calculation:

		
			
::::::::::::::::::::::
:: factorialTRC.scm ::
::::::::::::::::::::::
   1:   (define !
   2:     (lambda (n result)
   3:       (if (= n 1)
   4:         result
   5:         (! (- n 1) (* n result)))))
   6: 
   7:   (! 2 1)
   8:

Viivi evaluates this code correctly again, to provide the same value 2 as expected.
The corresponding Viivi trace-output is as follows:

		
			
$ viivi -K factorialTRC.scm
		...
        4: ┌─ (! 2 1)
        4: │┌─ !
        5: │└─ #<closure:[(n result)] [(if (= n 1) result (! (- n 1) (* n result)))]>
        5: │┌─ 2
        6: │└─ 2
        6: │┌─ 1
        7: │└─ 1
        7: │ * #<closure:[(n result)] [(if (= n 1) result (! (- n 1) (* n result)))]>
        7: │ ○  n  →  2
        7: │ ○  result  →  1
        7: │┌─ (if (= n 1) result (! (- n 1) (* n result)))
        7: ││┌─ if
        8: ││└─ #<procedure:if>
        8: ││ * #<procedure:if>
        8: ││┌─ (= n 1)
        8: │││┌─ =
        9: │││└─ #<procedure:=>
        9: │││┌─ n
       10: │││└─ 2
       10: │││┌─ 1
       11: │││└─ 1
       11: │││ * #<procedure:=>
       12: ││└─ #f
       12: ││┌─ (! (- n 1) (* n result))
       12: │││┌─ !
       13: │││└─ #<closure:[(n result)] [(if (= n 1) result (! (- n 1) (* n result)))]>
       13: │││┌─ (- n 1)
       13: ││││┌─ -
       14: ││││└─ #<procedure:->
       14: ││││┌─ n
       15: ││││└─ 2
       15: ││││┌─ 1
       16: ││││└─ 1
       16: ││││ * #<procedure:->
       17: │││└─ 1
       17: │││┌─ (* n result)
       17: ││││┌─ *
       18: ││││└─ #<procedure:*>
       18: ││││┌─ n
       19: ││││└─ 2
       19: ││││┌─ result
       20: ││││└─ 1
       20: ││││ * #<procedure:*>
       21: │││└─ 2
       21: │ / #<closure:[(n result)] [(if (= n 1) result (! (- n 1) (* n result)))]>
       21: │ ●  n  →  1
       21: │ ●  result  →  2
       21: │┌─ (if (= n 1) result (! (- n 1) (* n result)))
       21: ││┌─ if
       22: ││└─ #<procedure:if>
       22: ││ * #<procedure:if>
       22: ││┌─ (= n 1)
       22: │││┌─ =
       23: │││└─ #<procedure:=>
       23: │││┌─ n
       24: │││└─ 1
       24: │││┌─ 1
       25: │││└─ 1
       25: │││ * #<procedure:=>
       26: ││└─ #t
       26: ││┌─ result
       27: ││└─ 2
       28: │└─ 2
       29: └─ 2

[3] In case of a Tail-Recursive Call with a Lambda-Calling Argument

[Apology]
The author found this code somewhere about ten-years ago, but he lost the origin.
I am very sorry if you are the author of this code.
Even though you are not the author, if you know the origin of the code, please tell it to the author and he will specify it here.

						
							
:::::::::::::::::::::::::
:: factorialLambda.scm ::
:::::::::::::::::::::::::
   1: (define _fact
   2:   (lambda (n k)
   3:     (if (= n 1)
   4:       (k 1)
   5:       (_fact (- n 1)
   6:         (lambda (u)
   7:           (k (* n u)))))))
   8: 
   9:   (_fact 2 (lambda (x) x))
  10:

Similar to the above examples, the expected result is 2.
Now Viivi is fixed and gives the correct value.

						
							
$ viivi -K factorialLambda.scm
		...
        0: ┌─ (define _fact (lambda (n k) (if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))))
        0: │┌─ define
        1: │└─ #<procedure:define>
        1: │ * #<procedure:define>
        1: │┌─ (lambda (n k) (if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u))))))
        1: ││┌─ lambda
        2: ││└─ #<procedure:lambda>
        2: ││ * #<procedure:lambda>
        3: │└─ #<closure:[(n k)] [(if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))]>
        3: │ ○  _fact  →  #<closure:[(n k)] [(if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))]>
        4: └─ #<unspecified>

        4: ┌─ (_fact 2 (lambda (x) x))
        4: │┌─ _fact
        5: │└─ #<closure:[(n k)] [(if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))]>
        5: │┌─ 2
        6: │└─ 2
        6: │┌─ (lambda (x) x)
        6: ││┌─ lambda
        7: ││└─ #<procedure:lambda>
        7: ││ * #<procedure:lambda>
        8: │└─ #<closure:[(x)] [x]>
        8: │ * #<closure:[(n k)] [(if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))]>
        8: │ ○  n  →  2
        8: │ ○  k  →  #<closure:[(x)] [x]>
        8: │┌─ (if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))
        8: ││┌─ if
        9: ││└─ #<procedure:if>
        9: ││ * #<procedure:if>
        9: ││┌─ (= n 1)
        9: │││┌─ =
       10: │││└─ #<procedure:=>
       10: │││┌─ n
       11: │││└─ 2
       11: │││┌─ 1
       12: │││└─ 1
       12: │││ * #<procedure:=>
       13: ││└─ #f
       13: ││┌─ (_fact (- n 1) (lambda (u) (k (* n u))))
       13: │││┌─ _fact
       14: │││└─ #<closure:[(n k)] [(if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))]>
       14: │││┌─ (- n 1)
       14: ││││┌─ -
       15: ││││└─ #<procedure:->
       15: ││││┌─ n
       16: ││││└─ 2
       16: ││││┌─ 1
       17: ││││└─ 1
       17: ││││ * #<procedure:->
       18: │││└─ 1
       18: │││┌─ (lambda (u) (k (* n u)))
       18: ││││┌─ lambda
       19: ││││└─ #<procedure:lambda>
       19: ││││ * #<procedure:lambda>
       20: │││└─ #<closure:[(u)] [(k (* n u))]>
       20: │ / #<closure:[(n k)] [(if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))]>
       20: │ ●  n  →  1
       20: │ ●  k  →  #<closure:[(u)] [(k (* n u))]>
       20: │┌─ (if (= n 1) (k 1) (_fact (- n 1) (lambda (u) (k (* n u)))))
       20: ││┌─ if
       21: ││└─ #<procedure:if>
       21: ││ * #<procedure:if>
       21: ││┌─ (= n 1)
       21: │││┌─ =
       22: │││└─ #<procedure:=>
       22: │││┌─ n
       23: │││└─ 1
       23: │││┌─ 1
       24: │││└─ 1
       24: │││ * #<procedure:=>
       25: ││└─ #t
       25: ││┌─ (k 1)
       25: │││┌─ k
       26: │││└─ #<closure:[(u)] [(k (* n u))]>
       26: │││┌─ 1
       27: │││└─ 1
       27: │││ * #<closure:[(u)] [(k (* n u))]>
       27: │││ ○  u  →  1
       27: │││┌─ (k (* n u))
       27: ││││┌─ k
       28: ││││└─ #<closure:[(x)] [x]>
       28: ││││┌─ (* n u)
       28: │││││┌─ *
       29: │││││└─ #<procedure:*>
       29: │││││┌─ n
       30: │││││└─ 2
       30: │││││┌─ u
       31: │││││└─ 1
       31: │││││ * #<procedure:*>
       32: ││││└─ 2
       32: ││││ * #<closure:[(x)] [x]>
       32: ││││ ○  x  →  2
       32: ││││┌─ x
       33: ││││└─ 2
       34: │││└─ 2
       35: ││└─ 2
       36: │└─ 2
       37: └─ 2

Tail-Recursive Calls with a Lambda-Calling Argument < Tell me, Schemer! < Viivi's Cell < Entrance

Contact