Wed Aug 13 12:56:04 CEST 2008

The role of names in concatenative languages

Lambda calculus is based on the two complementary operations of
abstraction and applications.  Combinatory logic is a variant of the
lambda calculus expressed in terms of just application and a couple of
primitive lambda terms called combinators[1].  Further simplification is
possible: the combinators can be made ``flat'' by using only left
associative application[2].

In Scheme, a practical programming language based on the lambda
calculus, some forms are allowed to be abbreviated using names.  This
abbreviation mechanism is not essential to computation: it is merely a
notational device.

  * A set of primivite abstractions and values.
  * function application
  * abstractions through LAMBDA
  * abbreviation of values thorugh DEFINE

In Scheme there are 2 mechanisms that introduce names.  DEFINE
introduces abbreviations for expressions on the toplevel, while LAMBDA
uses names to create parameterized code, which are later filled in
using (explicit) applications.

Eliminating abstraction (LAMBDA) from Scheme can be done in a similar
way as for the lambda calculus -> flat combinators conversion.
Replacing application with only left associative application creates a
language which has a mechanism to define names (DEFINE) that is
completely independent of its primary abstraction mechanism
(concatenation of terms).

This is quite remarkable.  In Scheme it is possible to unify these two
name mechanisms by interpreting DEFINE as the introduction of lexical
variable by wrapping a Scheme expression in a LAMBDA.  However, in a
concatenative language we are now free to take another route: to take
names _out of the language_ completely, making it part of some meta

This is what happens in Coma.  All the metaprogramming machinery can
be concentrated in a very simple combinatory ``algebra'' instead of
having to deal with scoping of names.

[1] http://en.wikipedia.org/wiki/Combinators
[2] http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03