Comment by kragen

5 years ago

Oh, so he is. I wonder if he'll explain I misunderstood him or correct the error.

In case you are still reading this: the book is about ancient LISP (LISP 1.0, 1.5, PDP-6 LISP), which was dynamically scoped. The Y combinator requires lexical scoping, though.

  • Hmm, that's a good point. The general-case solution they adopted for not having lexical scoping at the time was FUNARG, but of course that's just as much of a kludge as LABEL (which was, yes, in 1959 Lisp, before FUNARG). There are cheats like this, of course:

        (defun quasiquote-y (f)
          `(lambda (n)
             (funcall (function ,f) (function ,f) n)))
    

    Perhaps surprisingly, this does work in dynamically-scoped Lisp-2s like Elisp (which, unlike Lisp 1.5, doesn't have FUNARG), even for λ-expressions:

        (funcall
         (quasiquote-y '(lambda (f n)
                          (if (< n 2) 1
                            (* n (funcall f f (- n 1))))))
         4)
    

    Defining a version of QUASIQUOTE-Y that works for the following subtly different LAMBDA form has so far escaped me but seems like it ought to be feasible:

        (lambda (f n)
          (if (< n 2) 1
            (* n (funcall f (- n 1)))))
    

    Now, of course, in modern Lisps, we consider it a barbaric practice to treat a list beginning with the symbol LAMBDA as a function as such, as opposed to a piece of code which could be EVALed to produce a function. But this ancient abomination remains honored in the dark precincts of Elisp, and of course was entirely supported in Lisp 1.5 (though doing the equivalent of QUASIQUOTE would have been considerably more awkward; FUNARG was the favored design error of the day) and McCarthy 1959.

    ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-199.pdf ("The function of FUNCTION") relates the 1970 perspective on this problem.

    • The FUNARG device was defined in the LISP 1.5 manual, but never implemented. Later versions of MACLISP did a limited version of FUNARG (called FUNCTION*) that solved the downward, but not the upward FUNARG problem.

      Then dynamic scoping interferes badly with tail call elimination (TCE), because bindings do not have indefinite extent and need to be removed at some point. The exact point of removal leads to all kinds of interesting problems. The short version is, you can have TCE or correct bindings, but not both. So a dynamically scoped Y will kind of "work", but eventually either cause a FUNARG problem or overflow the stack.

      2 replies →