Sunday, February 27, 2011

Almost Literate Syntax Trees

Suppose you're translating a lambda calculus expression like:
λxyz.xyz
into a Lisp-like syntax tree:
  (fun 'x
(fun 'y
(fun 'z
(apply
(apply (sym 'x) (sym 'y))
(sym 'z)
)
)
)
)
where sym expresses a reference to a symbol that is (or should be) bound in the current context.

If you replace fun with givenA and sym with the, the result looks like:
  (givenA 'x
(givenA 'y
(givenA 'z
(apply
(apply (the 'x) (the 'y))
(the 'z)
)
)
)
)
This exploits an English speaker's understanding that “a” introduces a term, and “the” refers to an occurrence of that term in the same context.

The second example reads better to me, but I haven't been able to come up with an everyday-English equivalent for apply. Maybe it's just not an everyday concept.

No comments:

Post a Comment