Recursive Multiplication in Scheme (positive numbers)-CodePudding

I am new to scheme and am trying to gain an understanding of how the following piece of code is able to recursively multiply two numbers provided (how is the function stack occurring here):

;Recursive Arithmetic
(define increment
  (lambda (x)
    (  x 1)))

(define decrement
  (lambda (x)
    (- x 1)))

(define recursive-add
  (lambda (x y)
    (if (zero? y)
        x
        (recursive-add (increment x) (decrement y)))))

"Define Multiplication Recursively"
(define recursive-mult
  (lambda (x y)
    (if (zero? y)
        0
        (recursive-add x (recursive-mult x (decrement y)))))) ;else

(recursive-mult 9 5)

My first doubt is what part of the else section is executed first?

In the else section, if (decrement y) is executed first, then y is first decremented by 1, then the(recursive-mult x section runs next by which function calls itself, so the section (recursive-add x never gets called in this same line of code.

Now, if in the else section, the recursive-add x is executed first, x gets added first, then the recursive-mult x runs which runs the the whole function again and the (decrement y) is never reached.

Now I know either of my two assumptions above, or maybe both are wrong. Would someone be able to point me in the right direction please? I apologize if my question displays a high level of inadequacy in this subject but I really want to learn scheme properly. Thank you.

CodePudding user response：

This is an answer in Common Lisp, in which I am more familiar, but the approach is the same. Here is a translation of your code:

(defpackage :so (:use :cl))
(in-package :so)

(defun add (x y)
  (if (zerop y)
      x
      (add (1  x) (1- y))))

(defun mul (x y)
  (if (zerop y)
      0
      (add x (mul x (1- y)))))

The increment and decrement functions are not defined, I'm using 1 and 1- which are equivalent.

In the else section, if (decrement y) is executed first, then y is first decremented by 1, then the(recursive-mult x section runs next by which function calls itself, so the section (recursive-add x never gets called in this same line of code.

You can use the substitution model to evaluate recursive functions.

(add (add 1 3) 1)

Let's evaluate first the first argument of the top-most and:

(add (add 2 2) 1)
(add (add 3 1) 1)
(add (add 4 0) 1)
(add 4 1)

Here the call eventually returned and the first argument is 4. Once the execution is resumed, the rest of the code for (add (add 1 3) 1) is executed, which is equivalent to:

(add 5 0)

And finally:

Each time you invoke the function a new frame is pushed on the call stack, which is what is shown in a trace:

(trace mul add)

The macro above in Common Lisp makes it so the mul and add functions are traced. Now when I run a program, a trace is printed when they are entered and exited: Let's try with small values:

(mul 2 3)

The trace is printed as follows (don't mind the SO:: prefix, this is part of the fully-qualified name of symbols):

  0: (SO::MUL 2 3)
    1: (SO::MUL 2 2)
      2: (SO::MUL 2 1)
        3: (SO::MUL 2 0)
        3: MUL returned 0
        3: (SO::ADD 2 0)
        3: ADD returned 2
      2: MUL returned 2
      2: (SO::ADD 2 2)
        3: (SO::ADD 3 1)
          4: (SO::ADD 4 0)
          4: ADD returned 4
        3: ADD returned 4
      2: ADD returned 4
    1: MUL returned 4
    1: (SO::ADD 2 4)
      2: (SO::ADD 3 3)
        3: (SO::ADD 4 2)
          4: (SO::ADD 5 1)
            5: (SO::ADD 6 0)
            5: ADD returned 6
          4: ADD returned 6
        3: ADD returned 6
      2: ADD returned 6
    1: ADD returned 6
  0: MUL returned 6

The difference with Scheme is that Scheme does not define the order by which function arguments are evaluated (it is left unspecified), so maybe your code would not exactly behave as above, but it should still compute the same answer (because there are no side effects).

CodePudding user response：

Scheme has eager evaluation so if you have

(op1 expr1 (op2 1 (op3 expr2 expr3)))

Then op1 form will depend on expr1 and the form with op2 to be complete before op1 can be applied. If we have an implementation that does left to right evaluation it will do it like this:

(let ((vexpr1 expr1)
      (vexpr2 expr2)
      (vexpr3 expr3))
  (let ((vop3 (op3 vexpr2 vexpr3)))
    (let ((vop2 (op2 1 vop3)))
      (op1 vexpr1 vop2))))

So to answer your question the order in the same left to right Scheme will be:

(let ((vdy (decrement y)))
  (let ((vrm (recursive-mult x vdy)))
    (recursive-add x vrm)))

Same in CPS:

(decrement& y 
            (lambda (vdy)
              (recursive-mult& x 
                               vy 
                               (lambda (vrm)
                                 (recursive-add& x vrm continuation)))))

So in practice the application for the first round doesn't happen before the whole recursive-mult for the smaller expression happens first. Thus (recursive-mult 3 3) turns into

(recursive-add 3 (recursive-add 3 (recursive-add 3 0)))

And as you can see the last one is being done first, then the second one and the last addition to be performed is the one of the first round before recursion.