Re: System deployment commands hoarding all RAM

[Juliana Sims]

Hi Sergio,

Continuing on from our out-of-band conversation about this topic, the 
most likely cause of your RAM issue is that you use recursion 
extensively, but not in tail position. This means that Guile cannot 
optimize this recursion to re-use stack frames and thus your memory 
usage is unbounded. I'll try to explain a bit more what that means in 
this email in the hopes that you'll be able to resolve it. Forgive me 
if I repeat things you already know; I want to make sure you have all 
the information you need to solve your problem.

You know what recursion is: calling a function from inside itself (or 
one of the functions it calls). You mentioned you've also heard of tail 
calls. I'll go ahead and describe tail calls a couple ways just in case 
these different descriptions help something click for you. I know I 
needed to hear several different explanations before I really 
understood them.

The common definition is that a tail call is a call made as the last 
thing a function does. I think of it as calling a function when there's 
no more work to do in the current function. Functions called in this 
way are said to be "in tail position." Tail recursion is simply making 
a recursive call in tail position. Here's a silly example defined first 
without tail recursion, then with:
```
(define (add-x n x)
 "Add @var{x} to @var{n} one at a time."
 (if (= x 0)
     n
     (+ 1 (add-x n (- x 1)))))

(define (add-x-tail n x)
 (if (= x 0)
     n
     (add-x-tail (+ n 1) (- x 1))))
```
An important note: while the recursive call is the last line of text in 
the tail-recursive function definition, this isn't necessarily 
required. That idea threw me off for quite some time. The following 
function is also tail recursive and produces the same output as the 
other two definitions:
```
(define (add-x-tail-2 n x)
 (if (not (= x 0))
     (add-x-tail-2 (+ n 1) (- x 1))
     n))
```

Let's return to the first definition for now. You may notice that the 
recursive call happens inside of a call to `+`. Because arguments have 
to be fully evaluated to values in order to be passed to functions, the 
`+` call cannot be fully evaluated without the result of the recursive 
call. We therefore have to keep around the outer `add-x` call so that 
we can fully evaluate `+` and return its value from `add-x`.

Let's walk through expanding a quick example, skipping some 
intermediary evaluation to save space and using ellipses to replace 
parts of the function we don't care about anymore but have to keep 
around anyway:

```
(add-x 3 2)
-> ;; replace add-x with its body, replacing variable names with values
(if (= 2 0)
   3
   (+ 1 (add-x 3 1)))
-> ;; repeat the above steps, replacing the inner call to add-x with 
its body and its variable names with their values
(... (+ 1 (if (= 1 0)
             3
             (+ 1 (add-x 3 0)))))
-> ;; and again
(... (+ 1 (... (+ 1 (if (= 0 0) 3))))) ;; we skip writing the second 
arm because we don't evaluate it
-> ;; now that everything is fully expanded, we can begin evaluating in 
ernest
(... (+ 1 (... (+ 1 3))))
->
(... (+ 1 4))
->
5
```

Compare that to the second function definition. In this definition, the 
`+` and `-` calls both happen inside the call to `add-x-tail`. These 
are operating on known values and can be fully evaluated before the 
call to `add-x-tail`. That is, there is no information in the first 
`add-x-tail` call that is required to use the result of the second (or 
third, fourth, etc) call to `add-x-tail`. This reveals another way to 
think of tail calls. Tail calls are calls for which all arguments are 
known and whose result is immediately returned by the calling function.

Here's where we introduce a new term: recursive tail call optimization. 
Tail calls and tail recursion just describe situations you find in 
code. In and of themselves, they only talk about what code does on a 
theoretical level. Tail call optimization is a way to take advantage of 
the theoretical aspects I've been discussing. I've been framing tail 
calls as calls which do not need any information from the function that 
calls them. Recursive tail call optimization allows the compiler to 
replace the arguments of the calling function with the new argument 
values and then simply re-evaluate that function in-place. If you're 
familiar with how computers operate at the level of machine code and 
the stack, recursive tail call optimization is usually implemented by 
moving the new arguments into the same argument registers as were used 
for the first call to a function, then jumping back to the beginning of 
the function's stack frame. Guile (and all Scheme implementations 
compliant with R5RS or later standards) does something very similar.

We'll step through evaluation of our tail recursive definition with 
this understanding in mind, as well as previous rules for making the 
steps shorter:
```
(add-x-tail 3 2)
-> ;; replace add-x-tail with its body and replace variable names with 
their values
(if (= 2 0)
   3
   (add-x-tail 4 1))
-> ;; we only need to replace variables this time
(if (= 1 0)
   4
   (add-x-tail 5 0))
-> ;; and now we can finish evaluation
(if (= 0 0) 5)
->
5
```

As you can see, we just replaced the arguments in-line and evaluated 
the function over. When deciding if you're using a recursive tail call, 
ask yourself: if I replace the arguments to the current call with the 
arguments to the next call and evaluate the function again with no 
other changes, will I get the result I want? If the answer is yes, then 
congratulations! That's a recursive tail call!

Now, that's all just to help you understand recursive tail calls, why 
they're useful, and how to recognize them. That doesn't actually help 
you write them. And even when you understand recursive tail calls well 
enough to write them reliably, it's often non-trivial to represent a 
particular computational task using only recursive tail calls. Still, 
hopefully this helps.

Here are some other explanations of tail calls and tail recursion which 
may also help:
* a brief description and demonstration from Computerphile on YouTube 
(I recommend a free software frontend): https://youtu.be/_JtPhF8MshA
* a more thorough treatment of the topic from "An Introduction to 
Scheme and Its Implementation": 
https://www.cs.utexas.edu/ftp/garbage/cs345/schintro-v14/schintro_127.html
* the entire sixth part of "How to Design Programs" talks about 
recursive tail calls and how to define functions using them (note that 
this section builds on the rest of the book so it may not be 
immediately obvious what it's saying without other context): 
https://htdp.org/2023-8-14/Book/part_six.html

I'm sure other seasoned Schemers on this list can help refine this 
explanation or point you to other resources, and they may even be able 
to point you towards tail-recursive solutions to your problem. I don't 
have the time to try my hand at it at the moment, unfortunately, but I 
wish you good luck and happy hacking!

-Juli

PS If you've never spent time with "How to Design Programs" (HtDP), I 
highly recommend it. It can be slow going if you're not new to 
programming, but the design recipe and the program design discipline it 
teaches are the most valuable education I've ever gotten in, well, 
designing programs (and the functions that compose them). HtDP is an 
incredibly good replacement for the program design parts of the 
legendary "Structure and Interpretation of Computer Programs" (SICP) 
because it is able to build upon and refine the lessons of SICP with 
further experience from decades more of teaching. Plus, its laser-focus 
on one specific subset of the many topics SICP covers allows it to 
progress more gently and explore concepts in more depth from more 
angles.