Hacker News new | past | comments | ask | show | jobs | submit login
A few speed bumps (Lisp blog series) (funcall.blogspot.com)
24 points by chris11 on March 9, 2009 | hide | past | favorite | 4 comments



Just yesterday I felt the same confusion. I'm working on a JavaScript web application that communicates with a Common Lisp backend using S-expressions one way and JSON the other way (for good enough reasons).

I devised a neat scheme with nested alists and wrote a poorly-specified, bug-ridden implementation of half of Common Lisp in JavaScript to make sense of it all. Then I got really confused for a couple of weeks until I finally figured out why it was so hard to get right.

JavaScript doesn't have a cons or pair type. There's just no way to get cdr and cons to work sanely without being able to juggle Arrays' individual conses. Adding a class for such a fundamental unit and implementing my own linked lists with that would bog everything down just a bit too much. So the house of cards collapsed.

In hindsight it's obvious, but I spent a lot of time wondering why the whole thing was so confusing.


  function cons(x, y) {
      return function(m) {
          return m(x, y);
      }
  }
  
  function car(x) {
      return x(function(a, d) { return a; });
  }
  
  function cdr(x) {
      return x(function(a, d) { return d; });
  }
or

  function cons(x, y) {
      return function (m) {
          return m(x, y, function (n) { x = n }, function (n) { y = n });
      }
  }
  
  function car(x) {
      return x(function (a, d, sa, sd) { return a; });
  }
  
  function cdr(x) {
      return x(function (a, d, sa, sd) { return d; });
  }
  
  function setcar(x, y) {
      return x(function (a, d, sa, sd) { sa(y); });
  }
  
  function setcdr(x, y) {
      return x(function (a, d, sa, sd) { sd(y); });
  }
  
  function list() {
      arguments.shift = Array.prototype.shift;
      if (arguments.length == 0) {
          return null;
      } else {
          return cons(arguments.shift(), list.apply(this, arguments));
      }
  }
  
  function mapcar(fun, lst) {
      if (null == lst) {
          return null;
      } else {
          return cons(fun(car(lst)), mapcar(fun, cdr(lst)));
      }
  }

  function reduce(fun, init, lst) {
      if (null == lst) {
          return init;
      } else {
          return fun(car(lst), reduce(fun, init, cdr(lst)));
      }
  }
  
  function filter(fun, lst) {
      if (null == lst) {
          return null;
      } else {
          if (fun(car(lst))) {
              return cons(car(lst), filter(fun, cdr(lst)));
          } else {
              return filter(fun, cdr(lst));
          }
      }
  }


That's interesting... I've been thinking about this for a while now and at first I thought it would be incredibly bloated, but now I'm not so sure. Definitely interesting.


just for fun:

  function copylist(lst) {
      return mapcar(function (x) { return x; }, lst);
  }
  
  function last(lst) {
      if (null == lst) {
          return null;
      } else if (null == cdr(lst)) {
          return lst;
      } else {
          return last(cdr(lst));
      }
  }
ugly append:

  function append() {
      var lst = null;
      var i = 0;
      for (; i < arguments.length && null == lst; i++) {
          if (null != arguments[i]) {
              lst = copylist(arguments[i]);
          }
      }
      for (; i < arguments.length; i++) {
          if (null != arguments[i]) {
              setcdr(last(lst), copylist(arguments[i]));
          }
      }
      return lst;
  }
the fun:

  function qsort(lst) {
      if (null == lst) {
          return null;
      } else {
          var pivot = car(lst);
          var nlst = cdr(lst);
          return append(qsort(filter(function (x) { return x < pivot; }, nlst)),
                        list(pivot),
                        qsort(filter(function (x) { return x >= pivot; }, nlst)));
      }
  }
  
  function powerset(lst) {
      if (null == lst) {
          return null;
      } else {
          var first = car(lst);
          var rest  = powerset(cdr(lst));
          return append(list(list(first)),
                        mapcar(function (x) { return append(list(first), x); }, rest),
                        rest);
      }
  }




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: