A few speed bumps (Lisp blog series)
funcall.blogspot.com
funcall.blogspot.com
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; });
}
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));
}
}
} 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));
}
}
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;
}
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);
}
}