Joe Ganley

Reader Bennet Yee pointed out that my Lisp in JavaScript interpreter failed on his Y-combinator code, as follows:


((lambda (x y) (x x y))

   (lambda (me n)

      (cond ((< n 1) 1)

             (t (* n (me me (- n 1))))))

   4)

Naturally, I suspected a bug in the lambda machinery, but it turned out to be much simpler: The symbol-table lookup code had a conditional that depended on the value of the variable being looked up, and JavaScript (as in C/C++) equates 0 to false. Thus, it failed to find the variable when its value was 0. I hadn't caught this before because I habitually write that terminating condition as the slightly more efficient "< n 2", and thus it terminates before n reaches 0.

This task also led me to revisit the Y combinator, which is really beautiful. For those who don't want to wade through the details, it's a clever mechanism for implementing a recursive call to a lambda (i.e. nameless) function.

Labels: lisp, programming

Comments (0)

Joe Ganley	I make software and sometimes other things.

Due to Blogger's termination of support for FTP, this blog is no longer active. It is possible that some links from here, particularly those within the site, are now broken. If you encounter one of those, your best bet is to go to the new front page and hunt for it from there. Most, but not all, of the blog's posts are on this page; the archives are here.
I worked on Chrome
Well, not really. But I did just discover that my Lisp in JavaScript interpreter is part of Google Chrome's test suite. Labels: chrome, google, javascript, lisp, testing Comments (0)
Lisp in JavaScript bug fix
Reader Bennet Yee pointed out that my Lisp in JavaScript interpreter failed on his Y-combinator code, as follows: `((lambda (x y) (x x y)) (lambda (me n) (cond ((< n 1) 1) (t (* n (me me (- n 1)))))) 4)` Naturally, I suspected a bug in the lambda machinery, but it turned out to be much simpler: The symbol-table lookup code had a conditional that depended on the value of the variable being looked up, and JavaScript (as in C/C++) equates 0 to false. Thus, it failed to find the variable when its value was 0. I hadn't caught this before because I habitually write that terminating condition as the slightly more efficient "`< n 2`", and thus it terminates before `n` reaches 0. This task also led me to revisit the Y combinator, which is really beautiful. For those who don't want to wade through the details, it's a clever mechanism for implementing a recursive call to a lambda (i.e. nameless) function. Labels: lisp, programming Comments (0)