Re: Understanding the difference betwee `subproblem level` and `reduction number`

[Matt Birkholz]

On Mon, 2022-10-17 at 13:07 +0200, Francesco Ariis wrote:
> Hello schemers,
> [...]
>     (- n 1)                       is subproblem level 0
>     (factorial (- n 1)))))        is subproblem level 1
>     (* n (factorial …)            is subproblem level 2
> 
> Everything is clear here.
> 
> But then it goes on to say that if we go further up , the `if` expression
> is not at subproblem level 3 (as I would have guessed), but at
> “reduction number” 1.
> 
> Indeed if I `(debug)` and then `B` to the `if` expression, I get:
> 
>     Subproblem level: 2  Reduction number: 1
> 
> It is not clear to me what the difference is between “levels” and
> “reduction numbers” is or if that matters debugging-wise.
> 

"levels" are sub-problems: stack frames.  (Actually sub-problems cause
the caller to save its state, push a frame.  Sub-problems are the
causes; stack frames are the consequences.)

"reduction numbers" are per sub-problem.  Reduction 0 is the sub-
problem itself, wanting to reduce a call to a value(s), i.e. invoke its
continuation, i.e. pop its stack frame.

Reductions >= 1 are artificial stack frames inserted to help us mere
mortals see how a frame-per-call stack would have wound/unwound. 
Without it, Scheme's stack can seem bizarre, with the top continuation
*way* up the call chain, in this case perhaps the REPL, *not* the if
expression, *not* even the factorial procedure.

This is the price of tail-call optimization, and why the wise man
starts his debugging before his compiling.  (Compiled code does not
generate these artificial stack frames).

-Matt