How do I make the substitution ? Scheme

Question

How do I make the substitution? I tried to trace but I don't really get what is going on... the code:

(define (repeated f n)
  (if (zero? n)
    identity
    (lambda (x) ((repeated f (- n 1)) (f x)))))

f is a function and n is an integer that gives the number of times we should apply f. ....can someone help me to interpret it. I know it returns several procedures and i want to believe that it goes f(f(f(x)))

okey i will re-ask this question but in different manner, because i didn't really get an answer last time. consider this code

(define (repeated f n)
  (if (zero? n)
    identity
    (lambda (x) ((repeated f (- n 1)) (f x)))))

where n is a positive integer and f is an arbitrary function: how does scheme operate on this code lets say we give (repeated f 2). what will happen? this is what think:

(f 2)

(lambda (x) ((repeated f (- 2 1)) (f x))))


(f 1)

(lambda (x) ((lambda (x) ((repeated f (- 1 1)) (f x)))) (f x))))


(f 0)

(lambda (x) ((lambda (x) (identity (f x)))) (f x))))

> (lambda (x) ((lambda (x) (identity (f x)))) (f x))))

>  (lambda (x) ((lambda (x) ((f x)))) (f x))))

here is were i get stuck first i want it to go (f(f(x)) but now i will get (lambda x ((f x) (f x)) , the parentheses is certaintly wrong , but i think you understand what i mean. What is wrong with my arguments on how the interpreter works

Answer 1

You've got a function that takes a function f and an non-negative integer n and returns the function fⁿ, i.e., f(f(f(…f(n)…). Depending on how you think of your recursion, this could be implemented straightforwardly in either of two ways. In both cases, if n is 0, then you just need a function that returns its argument, and that function is the identity function. (This is sort of by convention, in the same way that x⁰ = 1. It does make sense when it's considered in more depth, but that's probably out of scope for this question.)

How you handle the recursive case is where you have some options. The first option is to think of fⁿ(x) as f(f^n-1(x)), where you call f with the result of calling f^n-1 with x:

(define (repeated f n)
  (if (zero? n)
      identity
      (lambda (x)
        (f ((repeated f (- n 1)) x)))))

The other option is to think of fⁿ(x) as f^n-1(f(x)) where _f^n-1 gets called with the result of f(x).

(define (repeated f n)
  (if (zero? n)
      identity
      (lambda (x)
        ((repeated f (- n 1)) (f x)))))

In either case, the important thing to note here is that in Scheme, a form like

(function-form arg-form-1 arg-form-2 ...)

is evaluated by evaluating function-form to produce a value function-value (which should be a function) and evaluating each arg-form-i to produce values arg-value-i, and then calling _function-value_ with the arg-values. Since (repeated ...) produces a function, it's suitable as a function-form:

 (f ((repeated f (- n 1)) x))
;    |--- f^{n-1} ------| 
;   |---- f^{n-1}(x) ------|
;|------f(f^{n-1}(x)) ------|

 ((repeated f (- n 1)) (f x))
; |--- f^{n-1} ------|
;|---- f^{n-1}(f(x))--------|

Based on Will Ness's comment, it's worth pointing out that while these are somewhat natural ways to decompose this problem (i.e., based on the equalities fⁿ(x) = f^n-1(f(x)) = f(f^n-1(x))), it's not necessarily the most efficient. These solutions both require computing some intermediate function objects to represent f^n-1 that require a fair amount of storage, and then some computation on top of that. Computing fⁿ(x) directly is pretty straightforward and efficient with, e.g., repeat:

(define (repeat f n x)
  (let rep ((n n) (x x))
    (if (<= n 0)
        x
        (rep (- n 1) (f x)))))

A more efficient version of repeated, then, simply curries the x argument of repeat:

(define (repeated f n)
  (lambda (x) 
    (repeat f n x)))

This should have better run time performance than either of the other implementations.

Answer 2

Equational reasoning would be very helpful here. Imagine lambda calculus-based language with Haskell-like syntax, practically a combinatory calculus.

Here, parentheses are used just for grouping of expressions (not for function calls, which have no syntax at all – just juxtaposition): f a b c is the same as ((f a) b) c, the same as Scheme's (((f a) b) c). Definitions like f a b = ... are equivalent to (define f (lambda (a) (lambda (b) ...))) (and shortcut for (lambda (a) ...) is (\a-> ...).

Scheme's syntax just obscures the picture here. I don't mean parentheses, but being forced to explicit lambdas instead of just equations and freely shifting the arguments around:

f a b = \c -> ....   ===   f a b c = ....      ; `\ ->` is for 'lambda'

Your code is then nearly equivalent to

repeated f n x                          ; (define (repeated f n)
  | n <= 0    = x                       ;  (if (zero? n)  identity
  | otherwise = repeated f (n-1) (f x)  ;    (lambda (x)
                                        ;      ((repeated f (- n 1)) (f x)))))

(read | as "when"). So

  repeated f 2 x =     ; ((repeated f 2) x) = ((\x-> ((repeated f 1) (f x))) x)
= repeated f 1 (f x)       ;      = ((repeated f 1) (f x))
= repeated f 0 (f (f x))   ;      = ((\y->((repeated f 0) (f y))) (f x))
= f (f x)                  ;      = ((\z-> z) (f (f x)))
                           ;      = (f (f x))

The above reduction sequence leaves out the particulars of environment frames creation and chaining in Scheme, but it all works out pretty much intuitively. f is the same f, n-1 where n=2 is 1 no matter when we perform the subtraction, etc..

Answer 3

Your implementation actually delays the further recursion and return a procedure whose body will create copies of itself to fulfill the task at runtime.

Eg. (repeated double 4) ==> (lambda (x) ((repeated double (- 4 1)) (double x))) So when calling it ((repeated double 4) 2) it runs ((repeated double (- 4 1)) (double 2))) where the operand part evaluates to (lambda (x) ((repeated double (- 3 1)) (double x))) and so on making the closures at run time so the evaluation becomes equal to this, but in stages during runtime..

((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) (identity x)) (double x))) (double x))) (double x))) (double x))) 2)

A different way of writing the same functionality would be like this:

(define (repeat fun n)
  (lambda (x)
    (let repeat-loop ((n n)
                      (x x))
      (if (<= n 0) 
          x
          (repeat-loop (- n 1) (fun x))))))

(define (double x) (+ x x))
((repeat double 4) 2) ; ==> 32

Answer 4

Danny. I think that if we work repeated with small values of n (0, 1 and 2) will be able to see how the function translates to f(f(f(...(x))). I assume that identity's implementation is (define (identity x) x) (i.e. returns its only parameter as is), and that the "then" part of the if should be (identity f).

(repeated f 0) ;should apply f only once, no repetition
-> (identity f)
-> f

(repeated f 1) ;expected result is f(f(x))
-> (lambda (x) ((repeated f 0) (f x)))
-> (lambda (x) (f (f x))) ;we already know that (repeated f 0) is f

(repeated f 2) ;expected result is f(f(f(x)))
-> (lambda (x) ((repeated f 1) (f x)))
-> (lambda (x) (f (f (f x)))) ; we already know that (repeated f 1) if f(f(x))

... and so on.