Manually doing function body-substitution to see how a procedure works

Question

I'm stepping through a procedure that was provided in another answer (https://stackoverflow.com/a/68013528/651174), and I'm struggling trying to finish the substitutions in the procedure. Here is where I'm at now:

; main function
(define (curry num func)
  (cond ((= num 1) func)
        (else (lambda (x) (curry (- num 1)
                                 (lambda args (apply func (cons x args))))))))

And here is the call I'm doing:

(define (add-3 x y z) (+ x y z))
(add-3 100 200 300)
; 600
((((curry 3 add-3) 100) 200) 300)
; 600

Here is my attempt at substituting through the code to trace how the function works:

; Sub 1/3 (curry 3 add-3)
(lambda (x) (curry (- 3 1)
                   (lambda args (apply add-3 (cons x args)))))
; verify it works
((((lambda (x) (curry (- 3 1)
                   (lambda args (apply add-3 (cons x args))))) 100) 200) 300)
; 600 -- OK

; Sub 2/3 (curry 2 <func>)
; <func> = (lambda args (apply add-3 (cons x args)))
(lambda (x)
     (lambda (x) (curry (- 2 1)
                   (lambda args (apply (lambda args (apply add-3 (cons x args))) (cons x args))))))
; verify it works
((((lambda (x)
     (lambda (x) (curry (- 2 1)
                   (lambda args (apply (lambda args (apply add-3 (cons x args))) (cons x args)))))) 100) 200) 300)
; 700 -- Wrong output

I am guessing the 700 value has to do with me having two lambda (x)'s and not properly enclosing them or something. What would be the proper way to do the above substitution?

score 3 · Answer 1 · answered Jun 18 '21 at 02:42

Strictly speaking, you should not reduce a term under a lambda, since the language has the call-by-value reduction strategy. You will also find it less confusing that way (there are reduction strategies that allow you to reduce a term under a lambda, but you need to be careful to avoid unintentional variable capture).

Assuming that you follow the call-by-value reduction strategy properly:

(lambda (x) 
  (curry (- 3 1)
         (lambda args (apply add-3 (cons x args)))))

is the final answer. You don't need to reduce anything further.

On the other hand, you can reduce the following term further:

((lambda (x) 
   (curry (- 3 1)
          (lambda args (apply add-3 (cons x args))))) 100)
=>
(curry (- 3 1) (lambda args (apply add-3 (cons 100 args))))
=>
(curry 2 (lambda args (apply add-3 (cons 100 args))))
=>
(cond ((= 2 1) (lambda args (apply add-3 (cons 100 args))))
      (else (lambda (x) 
              (curry (- 2 1)
                     (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))))
=>
(cond (#f (lambda args (apply add-3 (cons 100 args))))
      (else (lambda (x) 
              (curry (- 2 1)
                     (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))))
=>
(cond (else (lambda (x) 
              (curry (- 2 1)
                     (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))))
=>
(lambda (x) 
  (curry (- 2 1)
         (lambda args (apply (lambda args (apply add-3 (cons 100 args))) (cons x args)))))

If you wish, you can check that it's correct:

(((lambda (x) 
    (curry (- 2 1)
           (lambda args
             (apply (lambda args (apply add-3 (cons 100 args)))
                    (cons x args)))))
  200)
 300)

;=> evaluates to 600

score 1 · Accepted Answer · answered Jun 18 '21 at 16:27

Once you have gotten to

((((lambda (x) (curry 2
                 (lambda args 
                   (apply add-3 (cons x args))))) 
   100) 200) 300)

you have two choices for how to proceed. You could try to substitute the inner curry, as you do in the question, but you have to be careful to avoid introducing another variable with the same name, by renaming new variables that would otherwise clash. So let's change what you have slightly, using x1 and arg1, in preparation for adding different numbers:

((((lambda (x1) (curry 2
                  (lambda args1 
                    (apply add-3 (cons x1 args1))))) 
   100) 200) 300)

Now when you expand the inner curry, there is no conflict:

((((lambda (x1) 
     (lambda (x2)
       (curry 1 (lambda args2
                  (apply (lambda args1 
                           (apply add-3 (cons x1 args1)))
                         (cons x2 args2)))))) 
100) 200) 300)

Observe that this still results in 600. You can trivially remove the (curry 1), of course. From here, you could start substituting the applications of these lambdas to the arguments 100, 200, and 300.

But I think it's simpler to take the other road. Once the expression you're trying to evaluate is ((lambda (x) ...) 100), don't dive deeper into the ... to make a more complicated lambda. Instead, substitute 100 for x in the body. This will keep things a little more concrete, and happens to coincide with how a Scheme interpreter would actually evaluate the expression.

So from

((((lambda (x) (curry 2
                 (lambda args 
                   (apply add-3 (cons x args))))) 
   100) 200) 300)

I would prefer to advance to

(((curry 2
         (lambda args 
           (apply add-3 (cons 100 args))))
    200) 300)

and now when we expand the inner curry there is no conflict. (I use names args1 and args2 for clarity, but they don't actually clash in scope - you could call them both args):

(((lambda (x)
    (curry 1
           (lambda args2
             (apply (lambda args1 
                      (apply add-3 (cons 100 args1)))
                    (cons x args2)))))
    200) 300)

Replace (curry 1 f) with f, and substitute 200 for x, leaving

((lambda args2
   (apply (lambda args1 
            (apply add-3 (cons 100 args1)))
          (cons 200 args2)))
   300)

Now all the currying is resolved, leaving just calls of apply on lambdas. As before let's resolve the outermost, with args2 as the list '(300):

(apply (lambda args1 
         (apply add-3 (cons 100 args1)))
       (cons 200 '(300)))
   
(apply (lambda args1 
         (apply add-3 (cons 100 args1)))
       '(200 300))

Next evaluate the apply on this lambda, substituting '(200 300) for args1:

(apply add-3 (cons 100 '(200 300)))

Simplify the cons, and the last apply, and we're left with what we hoped to find:

(add-3 100 200 300)

thank you so much, super super helpful (both approaches). One question: how did you get rid of the "double apply", that is, this part here -- `(apply (lambda args1 (apply add-3 (cons 100 args1))) '(200 300))` — David542, Jun 18 '21 at 22:14
That's simply the evaluation rule for `apply`. To apply arguments to a lambda, substitute the arguments for the formal parameter list in the body. It's not mentioned in SICP for quite a while, apparently first as a footnote on page 247. But you can find many discussions online about what `apply` does and why it's important. For example, https://stackoverflow.com/q/6722609/625403. — amalloy, Jun 19 '21 at 02:53

Will Ness · Answer 3 · 2021-06-19T17:44:57.113

In general, using the definition's known clauses to expand the definition by adding new explicit sub-clauses, for n = 2,3,..., and substituting accordingly, we get (brace yourself):

(define (curry n f)
  (cond 
    ((= n 1) f)
    (else   (lambda (x)
              (curry (- n 1)
                (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
               (curry 1
                 (lambda xs (apply f (cons x2 xs))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (curry 2
                 (lambda xs3 (apply f (cons x3 xs3))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply (lambda xs3 (apply f (cons x3 xs3))) 
                                   (cons x2 xs))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))

-------- (apply (lambda args B) L)  ==  (let ((args L)) B) -------------

==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (let ((xs3 (cons x2 xs)))
                               (apply f (cons x3 xs3)))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply f (cons x3 
                                       (cons x2 xs)))))))
    ((= n 4) (lambda (x4)
               (curry 3
                 (lambda xs4 (apply f (cons x4 xs4))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply f (cons x3 
                                       (cons x2 xs)))))))
    ((= n 4) (lambda (x4)
               (lambda (x3)
                 (lambda (x2)
                   (lambda xs (apply (lambda xs4 (apply f (cons x4 xs4)))
                                     (cons x3 
                                       (cons x2 xs))))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))
==
(define (curry n f)
  (cond 
    ((= n 1) f)
    ((= n 2) (lambda (x2)
                 (lambda xs (apply f (cons x2 xs)))))
    ((= n 3) (lambda (x3)
               (lambda (x2)
                 (lambda xs (apply f (cons x3 
                                        (cons x2 xs)))))))
    ((= n 4) (lambda (x4)
               (lambda (x3)
                 (lambda (x2)
                   (lambda xs (apply f (cons x4 
                                         (cons x3 
                                           (cons x2 xs))))))))))
    (else    (lambda (x)
               (curry (- n 1)
                 (lambda xs (apply f (cons x xs))))))))

etc.

So that, in pseudocode,

((curry 1 f) a ...) == (f a ...)
(((curry 2 f) a) b ...) == (f a b ...)
((((curry 3 f) a) b) c ...) == (f a b c ...)
....

etc. (where the notation c ... means "zero or more arguments").

Why is (apply (lambda args B) L) == (let ((args L)) B)? Consider

(apply (lambda args B) (list x y z))
=
((lambda args B)   x y z)
=
(let ((args (list x y z)))  B)

Thanks for such a detailed answer here. One question about this line: `(apply (lambda args B) L) == (let ((args L)) B)`. How exactly does that work? I tried it with something like: `(apply (lambda args (length args)) '(1 2 3 4))` with `L='(1 2 3 4)` and `B=(length args)`, which I think gives me: `(let ((args '(1 2 3 4))) (length args))`, but I don't really get that part (or even in my understanding of it, that it makes any sense.) — David542, Jun 21 '21 at 21:39
Oh, I think I see...It's just settings `args='(1 2 3 4)`...and within that environment it calls the function `B`. Sorry I thought the `B` was part of the `let` key/values and so wasn't understanding how `B` fit in there... So I end up getting `(let ((args '(1 2 3 4))) (length args))` --> `4` in Racket. — David542, Jun 21 '21 at 21:48
by the way, I wrote it up in the answer here which I've been trying to figure out for awhile, does that seem accurate? https://stackoverflow.com/questions/68042006/how-does-the-following-reduce/68075322#68075322 — David542, Jun 21 '21 at 22:14
will check your answer later... regarding A, B, etc., the big letters are meta-notation for "something that appears there", a piece of code, not a "function B". `L` is anything that produces some list-like datum, `B` is the "body" of that varargs lambda function, `(lambda args B)`. `args` here is actual variable, non-parenthesized. it can be called by any name, I use "args" as mnemonic. so whatever that L is evaluating to, it must be a list -- otherwise using `apply` will result in an error. so if it's some list, after two steps it will be _the same as if we wrote_ that `let` expression. — Will Ness, Jun 22 '21 at 07:18
so I use that, to simplify the applications inside each specific `n` clause, to get the simplified form which we are guaranteed to arrive at, if we actually perform the applications as written. so I get the other, simplified form of the code, which in every respect is the same as the original -- except it's simpler to understand, since those varargs lambdas are gone. — Will Ness, Jun 22 '21 at 07:19
@David542 "So I end up getting (let ((args '(1 2 3 4))) (length args)) --> 4 in Racket." **yes.** furthermore, before evaluating that, you could simplify it further, ***symbolically***, (like I do in the answer) to just `(length '(1 2 3 4))`. — Will Ness, Jun 22 '21 at 08:43

Manually doing function body-substitution to see how a procedure works

3 Answers3

Linked