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)


ABOUT \| BLOG \| RESUME \| PROJECTS \| EMAIL

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)