Lambda calculus ponderings
Yeah, I've been posting a lot. Don't worry, this probably doesn't interest you - I just wanted to muse out loud.

So, Arc's out. Arc (for those of you keeping score at home) is Paul Graham's "new" Lisp he's been working on for the past 6 years or so. If this is at all the kind of thing that interests you, check it out - if not, you can probably stop reading now, because the rest assumes some (though not much) familiarity with Lisp and the Lambda calculus.

Arc's mostly some nice syntactic sugar and conventions. For instance, you write (fn (x) x) instead of (lambda (x) x) for an anonymous function, which seems small, but when you consider how often you have to write lambda, it adds up. And fn is a much better choice than do (as in Nu - another new language that has Lisp syntax, a Ruby heart, and an Objective-C foundation). I also like the concision of single-value lambda expressions, so that (fn (x) (+ x 1)) can be written as [+ _ 1] (the underscore is the single argument, though support for multiple positional parameters would be nice, as square brackets would simply be anonymous functions of any type. Another somewhat more questionable decision is to use = as the assignment operator, since it breaks Lisp convention pretty badly, though it's much more pleasant to say (= foo (list 1 2 3)) than (setf foo (list 1 2 3)) or (setq foo (list 1 2 3)) - and the way you can use = to set inside other data structures is nice, too. If we have set foo as in the previous example, we can say (= (car foo) 0) and the value of foo becomes (0 2 3). Very nice indeed.

But the single development I liked most was the following: in Arc, every data structure is an accessor function to an indexed binding. For instance (again using the example foo) (foo 1) would evaluate to 2, because the list foo acts as a function that, given an index, returns that binding - in this case, the list contains 2 at the second position. But going further, we can set on this as well: (= (foo 1) 5) would result in foo being the list (0 5 3). And going further still, this works with hashes - no more (gethash myhash "keyname") - just (myhash "keyname"). If you're used to traditional array[key] notation, this is actually a mapping from M-expressions - fn[arg1, arg2, ...] - to S-expressions - (fn arg1 arg2 ...) - which McCarthy described in his original paper on Lisp. They're isomorphic, and in fact S-expressions contain less characters than M-expressions, but of course if you're used to one the other looks weird for a while (of course, I'm quite sneakily leaving the question of infix operators out).

So, this brings us to my lambda calculus question - how would we define basic operations like cons, car and cdr in order to use something like Church numerals and get this behaviour? Typically, we use the following definitions (using L for the Greek letter lambda):

cons = L h. L t. L f. f h t
T = L a. L b. a
F = L a. L b. b
car = L l. l T
cdr = L l. l F
0 = L f. L x. x
1 = L f. L x. f x
2 = L f. L x. f (f x)
+1 = L n. L f. L x. f (n f x)

However, as you can see the application of these definitions doesn't give us the behaviour that the numbers can be used as indices for a list by applying the list to the number. I'd rather redefine cons et al. than the Church numerals, simply because the Church numerals have a very elegant definition: the Nth Church numeral is a function that takes a function and returns its N-fold composition.

So, any ideas?

• Mini Sitemap:

• Post to Journal
• Downloads

• LJ Gift Shop
• Safety Tips

• Support & FAQs
• Be a Support Volunteer

• Feedback & Contact Us
• Report Abuse

• Site News
• More... (Full Sitemap)