Defining and using functions in variables in Common Lisp

Question

I stumbled upon this article explaining the Y Combinator. The code is in Scheme, but I'm trying to work through it using Common Lisp.

However, I'm having trouble doing the translation from Scheme to Common Lisp. Scheme uses a single namespace for both functions and (other) variables, but Common Lisp uses different namespaces for functions and variables. How can I resolve this difference, to get working Common Lisp code?

Scheme code

Here's some Scheme code from the tutorial.

In the beginning the author defines the factorial function:

(define (factorial n)
  if (= n 0)
    1
    (* n (factorial (- n 1)))))

and translates it into this:

(define factorial
  (lambda (n)
    (if (= n 0)
      1
      (* n (factorial (- n 1))))))

Because (according to the author) that's what Scheme does:

Scheme simply translates the first definition into the second one before evaluating it. So all functions in Scheme are really lambda expressions.

Common Lisp

I tried to rewrite both the above snippets in Common Lisp to imitate this transition from the first form to the second. But there is no define in CL, neither has it a single name space. So I tried to cheat my way around it.

Rewriting the first Scheme definition in Common Lisp was easy:

(defun factorial (n)
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

But (to me) translating this into the second definition was a bit trickier. I translated it like this:

(setf (symbol-function 'factorial)
  (lambda (n)
    (if (= n 0)
      1
      (* n (factorial (- n 1))))))

Is this a bad way to do this (or is there a better way)? It seems to work but the compiler gives me a style warning: undefined function: factorial.

Saldivar

Answer 1

In some ways it is more like this:

(setf (symbol-function 'factorial)
      (labels ((factorial (n)
                 (if (= n 0)
                     1
                   (* n (factorial (- n 1))))))
        #'factorial))

LABELS defines the local function factorial. Inside the definition of the local function factorial any calls to factorial are to that function. We then return this function from the labels expression. Thus you can define recursive functions, where the recursive call is not to an undefined function.

If you look at Common Lisp implementations you can see that DEFUN often expands into non-portable constructs like named lambda functions, instead. Additionally DEFUN also has compile-time side effects.

Megaron

Answer 2

If I understand correctly, the main thrust of your question deals with translating between a "Lisp-1" and a "Lisp-2".

Scheme is a "Lisp-1" -- it has a single namespace for both functions and variables. Common Lisp, on the other hand, is a "Lisp-2" -- it has separate namespaces for functions and variables.

In scheme, you can write

(define foo (lambda (...) ...))

and then call foo like:

(foo ...)

We can define foo in exactly the same way in Common Lisp as well, but if we try to call foo using that syntax, your program will crash. This is because foo is in the variable namespace, not the function namespace.

We can work around this by using funcall to invoke foo:

(funcall foo ...)

That's a brief introduction. The Common Lisp Cookbook's page on Functions provides additional details you might find useful.

Dupe

Yes, the different name space approach is the problem. I have to decide whether to store the function in the value cell (and calling it with funcall) or use Rainer's solution (which I think I'll try). The transition shown in the OP is only the first of a long series of transitions which will ultimately yield ` (define almost-factorial (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) (define Y (lambda (f) ((lambda (x) (x x)) (lambda (x) (f (x x)))))) (define factorial (Y almost-factorial))`. – Saldivar

@Frank, right. The Y-combinator involves passing a function as a parameter and applying that function. So I think you will need funcall no matter how you get there. – Dupe

Answer 3

The transformation makes no sense in Common List.

The CL defun usually does much more than mere (setf fdefinition).

You can see that by evaluating (macroexpand-1 '(defun foo (a b c) (bar c a b))).

The real question is -- why are you trying to do this?

Jura

I simply learn better typing the code myself instead of just reading it. Maybe in this case this isn't the best idea because of the differences between Scheme and Common Lisp. – Saldivar

I don't like rethorical questions like "why are you trying to do this" especially not because Frank starts with his motication, better understanding the Y-combinator. I bet you didn't go through the trouble to look up the article he is referring to. Regards, Albert – Consolatory