Sun Jun 29 10:25:11 CEST 2008

lambda: why names?


Lambda names are a user interface: lexical locality works well for
human brains. However, manipulating lambda expressions is
tedious. (DeBruijn indices fix this problem, but are not so
readable.. Maybe it's best to regard names as syntactic sugar?).

What I don't understand in a lot of texts about Joy is the emphasis on
composition instead of application. I understand that the _structure_
of a program is better seen in terms of composition alone, but the
eventual use of a program is really application. Let uppercase denote
data items and lowercase denote functions:

           S a b

The first space between S and a is an application, while the second
one is a composition. Eventually, you're interested in the
value. Maybe the nuance is to really get rid of the value altogether
and see the semantics of [a b] as the 'output' of a program? Feels

    syntax:     concatenation
    semantics:  composition of functions
    execution:  application

The only real down-to-earth use i see is syntactic manipulation
leaving semantics invariant: optizing compilation.

Really, Joy in its 'composition only' lore is really about
compilation, about 'relative semantics' which stops at the actual
application. Maybe my intuition is too much attracted by operational
semantics (the 'real' world?).

After all, there is something to say for "Application has not a single
property. Function composition is associative and has an identity
element" -Meertens. In S a b, dragging the S on the left along is
rather pointless, even if the 'real' thing that happens is ((S a) b),
semantically all that matters is the composition of a and b, because
the application can be associated out: (S (a b))

Anyways.. Onward: Backus' FP: all functions are unary, but functional
forms can take multiple parameters. Embedded in Purrr this means that
at runtime there is a single 'token' going around, but at compile
time, there might be a stack of functions and forms combining
them. Actually, this seems like an interesting embedding! Purrr as a
metalanguage for a non-stack language, based on the observation that
both languages are concatenative, but having a different threaded
state: stack vs. list of lists.

Then about Category Theory and CAM. Too much for now..