Hacker News Reader

Comment by tekknolagi | Hacker News Reader

The author is the commenter :)

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.

Really? I had no idea! I thought FUNARG did get implemented (Moses implies on p. 13 that it was implemented by 1967, which is later than the Lisp 1.5 Manual (1962)), but maybe you're right that it only got implemented for the downward funarg problem, which is sort of the less interesting one — with dynamic binding, in the more common cases, you could solve the downward funarg problem by naming your variables things like CARBONATE-MAYONNAISE (thanks qq) instead of X, similar to the variable capture problem in Common Lisp ("unhygienic") macros.

Moses points out in his paper that none of this is particularly difficult if you use deep binding ("deep access", as he calls it) rather than shallow binding ("shallow access"): you "just" "abandon a stack and use a structure which is quite close to an alist", but of course that means that now all your variable lookups take O(ASSQ) time, as he sort of points out in footnote 4 on p. 12.

It's interesting that (though he cites Landin!) the idea of lexical scoping seems not to have entered his mind; he seems to be confusing it with what he calls "evaluating functions against the binding environment", which is similar but not quite the same.

https://openlibra.com/en/book/the-funarg-problem-explained is Weizenbaum's "unpublished" 1968 memo "The FUNARG problem explained" that Moses was working from. On skimming the memo, I think Weizenbaum did understand things in the modern sense and in particular solved it in a way that permitted proper garbage collection — but in SLIP-OPL, not LISP. Weizenbaum says (p. 55):

> Our solution to these problems is mainly that of providing a tree structured symbol table in place of the more usual stack structured symbol table. That solution is, of course, not original with us. It shows up, for example, in some versions of LISP and in Landin's SECD machine.

And at the opening of his memo he claims that "the original LISP implementation solved that problem," which I take to mean the problem as he understood it; in particular, he critique's Bobrow's 1967 paper on FUNARG with shallow binding: "Still, years after that implementation, the problem remains ill understood. Bobrow, for example, published a faulty solution for it only recently."

Of course, the fact that Weizenbaum thinks the original LISP "solved that problem" doesn't strongly imply that it solved it correctly, much less with TCE.

He doesn't seem to mention TCE, unless I missed it. I think the modern understanding of the importance of TCE dates from Scheme and the whole "ΛTU" series of AI memos — at the time I think it was considered merely an optimization. But you're certainly correct that if you want to loop indefinitely with Y you need precise TCE.

Interestingly the Bobrow paper seems to have been published a year earlier as a BBN Scientific Report: https://apps.dtic.mil/dtic/tr/fulltext/u2/647601.pdf but I haven't compared this version to the ACM version. On p.15 he describes in a footnote the degree to which his approach, which definitely will not work for upwards funargs, does work in BBN LISP:

> *With appropriate passing down of pushdown list [call stack] pointers we can even achieve the same effect as the standard FUNARG device on the 7094 for functional arguments. This FUNARG device preserves local context well enough to handle the Knuth's [sic] "Man and Boy" compiler problem (Algol Bulletin 18.1).

I admit I'm certainly no expert on late-1960s LISP code; my acquaintance is mostly limited to what appears in popular AI memos and HOPL papers.

Early LISP history is a bit blurry, and ancient implementations are full of surprises! Of course, the FUNARG problem was solved in theory in the LISP 1.5 manual, but, as you noted, at the cost of linear symbol lookup. This is probably the reason why this solution never made it into the actual implementation. Lexical scoping in combination with shallow binding did not even appear on the horizon before the LTU papers were published. Program performance was important on machines operating in the 200k instructions per second range and lexical scoping appeared to be expensive (it is, compared to dynamic scoping).

TCE was also a non-issue before the LTU papers, because it was (1) not necessary, you could just use a tag body, and (2) impossible to get right with dynamic scoping. Either you unbind after tail-calling and get no TCE, or you unbind before tail-calling and get a FUNARG problem.

If you want to experiment with LISP 1.5, there are 709 emulators out there, complete with original LISP tapes. E.g.: http://www.cozx.com/dpitts/ibm7090.html

Be prepared for some weirdness, though! Programs are entered as

    CONS (FOO BAR)

meaning (CONS (QUOTE FOO) (QUOTE BAR)), there are no comments, and in-situ lambda functions do not work. For instance,

    (LAMBDA (X) X) (FOO)

will evaluate, but

    DEFINE (( (TEST (LAMBDA (Q) ((LAMBDA (X) X) Q))) ))
    TEST (FOO)

will not. It is fun to explore, though.

Reply on news.ycombinator.com