Recurse from within let binding - Scheme

Question

I know Scheme is tail-recursive, but if a function calls itself from within a let binding, will the bound values stay in memory even if they are not needed? I have code similar to this:

(define (some-function)
  (let ((c (read-char)))
    (some-function)))

The actual function is a bit more complicated, but it shouldn't matter since the flow and such is the same. Will the value of 'c' be kept since the function is called from the inside of the let block? I don't want to use up tons of extra memory if this function keeps going for a while.

Answer 1

If a function is tail recursive, that is if the recursive function call is the last thing evaluated as part of the function, which is the case in your code, the recursion does not keep any local variables in memory, so the stack space consumption remains constant.

If it weren't tail recursive, that is if there still remained something to be done after the recursion, c would have to be kept in memory making the function consume O(n) stack space where n is the number of recursion. An example would be this:

(define (some-function)
  (let ((c (read-char)))
  (+ c (some-function))))

Here the addition will be executed after the recursion, so c has to be kept in memory while the recursive call executes.

Answer 2

Consider your example:

(define (some-function)
  (let ((c (read-char)))
    ; <HERE>
    (some-function)))
(some-function)

Suppose we run this program. The program will loop invoking some-function over and over. At some point the garbage collector is activated. Suppose for the sake of argument, that the process (the running program) is interrupted at the point marked <here>.

The job of the garbage collector is to reclaim memory that is no longer in use. What does "in use" mean?

A piece of memory is in use, if it (or values occupying the memory) might be used when the program continues. The name c is bound to a character, so that character can not be reclaimed. However since the call to some-function is tail recursive only one invocation of some-function is active at a time. This means that all old values of c can be reclaimed.

For a named loop where the loop function is tail called only the most recent values are in use. (The values stay in memory until the garbage collector is activated though).

A little experiment, try:

(let loop ((v 0))
  (loop (make-vector 100000 42))

This program loops and loops. For each round a vector of length 100000 is allocated. If you run out of memory, you know that the values of v aren't garbage collected. If the program runs uninterrupted, then the garbage collector has made it possible to recycle the memory.

Answer 3

In tail position, the bound variable doesn't need to exist. Only the variables available when the procedure is created is available at the call time.

(define (some-function)
  ;; only global variables exist at this point
  (let ((c (read-char)))
    ;; c exists for a brief time 
    (some-function)))

After the variable some-function is evaluated inside the procedure, then c is removed before applying whatever some-function was evaluated to. There exists only one c at a time.`

Imagine this slightly altered version:

(define (some-function previous)
  (let ((c (read-char)))
    (some-function c)))

Here we have the same except some-function and c is evaluated before c and previous are removed and the apply is started.

It is a requirement that the procedures and variables are handled in this way. It's called tail call optimization.

When a procedure gets created, the variables that is used in them needs to exist for the duration of the procedures existence:

(define (some-function2)
  (let ((c (read-char)))
    (lambda () c)))

(define test (some-function2))
(define test2 (some-function2))

Now. The variable is moved to be something connected to the procedure and still not a part of the environment when the some-function2 call is finished. The procedures are called closures and the c in each are closure variables that live on even after the binding procedure is done. If you are used to other languages you can think of these variables that live on to be on the heap. These "free variables" are what made Scheme special when it was created in the 70s and every programming language since is more or less based on this principle.