List function with Y combinator does no recursion, why?

Question

Note: This is kind of homework, kind of not -- the end goal is to have a function that produces a powerset of a set of numbers supplied to the function as a list of numbers. I have a recursive version of the function but I now need to find some ways of replacing each explicitly recursive function in the solution I have (append, mapm etc.) with an equivalent lambda-only expression.

As such, I am starting with smaller problems and hope to combine them all to write a full function. I've managed to come up with a non-recursive factorial function using pure-lambda (Y combinator) but I am now trying to come up with a nice function that squares every number in a list -- trying to solve smaller problems before jumping up to a multiply-recursive function:

(define (sqrlist numlist)
  (((lambda (f)
   ((lambda (x) (x x))
    (lambda (g)
     (f (lambda (x) ((g g) x))))))
  (lambda (f)
   (lambda (x)
    (cons (sqr (first x)) (rest x))))) numlist))

The code above doesn't recurse, despite the presence of the Y combinator before it -- I'm obviously having some issues passing the proper parameters to the functions within -- any ideas?

Answer 1

Here's a possible answer, I know that you solved it already, but it could be useful to have a second opinion :)

((lambda (X)
    ((lambda (proc)
       (proc proc))
     (lambda (proc)
       (X (lambda (arg)
            ((proc proc) arg))))))
  (lambda (sqrlist)
    (lambda (lst)
      (if (null? lst)
          '()
          (cons (* (car lst) (car lst))
                (sqrlist (cdr lst)))))))

It's "lambda-only" since it's written exclusively in terms of anonymous functions, it doesn't even use define. Here's how to call it:

(((lambda (X)
     ((lambda (proc)
        (proc proc))
      (lambda (proc)
        (X (lambda (arg)
             ((proc proc) arg))))))
   (lambda (sqrlist)
     (lambda (lst)
       (if (null? lst)
           '()
           (cons (* (car lst) (car lst))
                 (sqrlist (cdr lst)))))))
 '(1 2 3 4 5))

Answer 2

If you have a working procedure, converting to anonymous procedures is relatively straightforward and mechanical. Give each lambda an extra argument, which is "itself", and duplicate the procedure. So

(define (add-list list) 
  (if (empty? list) 
      0 
      (+ (first list) (add-list (rest list)))))

Becomes

(λ(list) (if (empty? list) 0 (+ (first list) (add-list (rest list)))))

This is of course a problem because add-list isn't defined. So we're going to have to ensure that we pass ourselves around every time.

(λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))

But where do we get ourselves in the first place? Well, we copy and paste (and give it an argument)

((λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 (λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 '(1 2 3 4))

Abstracting this "copy and paste" to the Y combinator is developed excellently in "The Why of Y" ^(PDF) and you should definitely check it out.

But remember the first step was "get it working." Do this before you abstract away defines.