>>>>> "Hans" == Hans Aberg <[EMAIL PROTECTED]> writes:
> In real life though, it is very difficult to translate an arbitrarily given
> lambda expression into a combination of the given primitive set.
I cannot resist illustrating Hans's point. This is the sort of thing
that comes up...
(((V "^" :*: V "0" :^: V "*" :+: (V "^" :*: V "0" :^: V "*") :^: V "+"
:*: V "*") :+: (V "Junk" :^: V "^") :^: V "^") :+: V "*") :+: (V
"Junk" :^: V "^") :^: V "^"
> So for
> practical purposes, there is no real gain in attempting to use a primitive
> set as a replacement for lambda expressions.
Maybe it isn't entirely futile to think about it though.
Reduction to combinators is the sort of thing that compilers
do. I sometimes wonder if there is any interest for compilers in the fact
that the only non-affine combinator (i.e. duplicating an argument) is
+. Maybe there is a garbage-collection angle.
By the way, I'm not wild about Hans's term "constant variables". In
Church's lambda-I calculus, you aren't allowed abstractions where the
bound variable doesn't occur in the body. It would be better to
distinguish linear (exactly once), affine (at most once), and general
abstraction. All 0, 1, * and ^ are affine, but + is not. All 1, *
and ^ are linear, but 0 is not. Reduction of affine combinators
needs essentially no new space, I think.
It is amusing to think of an arithmetic machine (a bit like the
G-machine maybe) that spends most of its time collecting the garbage
generated by an occassional addition.
-- Peter
