Search code examples
schemeracketcurryingsicp

In MIT Scheme/Racket, can a value be both the operator and operand? i.e. (lambda (y) (y y))

For the function foo6, give a Curried application of the procedure which evaluates to 3.

(define foo6
  (lambda (x)
    (x (lambda (y) (y y)))))

I've defined a foo7 to see how the last line works

(define foo7 (lambda (y) (y y)))

Is there some "y" that can both be the operator and the operand?

Edit: The question should read:

Is there some "y" that can both be the operator and the operand that will not cause an error or infinite loop?

Question taken from the Structure and Interpretation of Computer Program (SICP) Sample Programming assignments: https://mitpress.mit.edu/sicp/psets/index.html

From the "Introductory assignment," Exercise 11:

Solution

  • Yes. Scheme and Racket are both Lisp1s which means they only have one namespace and thus. the variable v can be any value including procedures.

    The second you see something like (lambda (y) (y y)) it obvious what type y is a procedure by the way it is being applied. For any other values than a procedure it would end with a application error:

    ((lambda (y) (y y)) 5)
; ERROR: application: 5 is not a procedure

    The procedure itself will probably expect itself as an argument so we can assume some sort of omega or z combinator.

    We have higher order procedures you pass functions as values in operand position and to use them just put then in operator position:

    (define (times n p)
  (lambda (arg)
    (let loop ((n n) (acc arg))
      (if (<= n 0)
          acc
          (loop (sub1 n) (p acc))))))

(define double (lambda (v) (+ v v)))
(define test (times 3 double))
(test 5) ; ==> 40

    Scheme is not alone on having this feature. The same code as above can be expressed just as easily in JavaScript as it also only have one namespace and parseInt(x) evaluates the variable parseInt to a value that gets applied with the argument you get from evaluating the variable x. They are just two variables, nothing special.

    EDIT

    Here is an example where (lambda (y) (y y)) is used in something usefull. 

    ;; the Z combinator 
(define Z
  (lambda (f)
    ((lambda (y)
       (y y))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

(define (fib n)
  ((Z (lambda (helper)
        (lambda (n a b)
          (if (zero? n)
              a
              (helper (- n 1) b (+ a b))))))
   n 0 1))

(fib 10) ; ==> 55

    The Z combinator is the Y combinator for eager languages. It makes it possibly for self reference without mutating the environment.