# Lambdas, Definitions

## iepos@tunes.org — 2000-05-03 22:34:57

    > >Anyhow, I didn't suggest

    > >saving all of the data stack.

    >

    > Eh?  I thought you did.  In that case, forget what I said.  I was arguing

    > against that.  I don't see a reason to argue against a concept which has no

    > defenders :-).

     A strange confusion... I'm not sure how this happened :-)

    Anyway, now for a topic I've been wanting to discuss for a little while:

    "lambdas" and their relationship to definitions, in concatenative languages.

    Some of this was discussed earlier on the TUNES list, but my thoughts

    on the subject have cleared up a bit since then, so I don't mind

    restating a bit of it.

    In case some are not familar with terminology relating to lambdas,

    I'll give a little background. A lambda is a language device that

    allows one to construct a function using a formal parameter; for instance,

    if you name the squaring function as

      the function that takes a number 'x' and yields 'x' times 'x'

    then you're using a lambda, and we call "x" the formal parameter

    (as opposed to an "actual" or "concrete" parameter like "3" that we

    could pass to this function).

    Nearly all programming language feature a lambda-like construct

    (but Joy is an exception). For instance, in Haskell, one could write

    the squaring function as

      x -> x*x

    C also has a lambda-like construct; you could write the squaring

    function as "sqr" provided you had defined it as:

      int sqr(int x){ return x*x; }

    But, this requires that one make up the name "sqr", as C does not have

    an "anonymous" lambda construct, whereas Haskell does.

    Anyway, now back to concatenative languages. In Joy, one can construct

    a squaring program as:

      dup *

    What I'm going to suggest now is that it might be interesting if Joy

    was extended so that one could also construct in a way like this:

      x\ [x] [x] *

    Here's the meaning of this program, word by word:

      "x\"  Pop the top item off the stack and call it "x".

      "[x]" Push x onto the stack.

      "[x]" Push x onto the stack.

      "*"   Multiply the top two things on the stack.

    The first word, "x\", is the one that uses a lambda...

    One interesting about having such a lambda construct is that it is

    possible to construct many of the Joy combinators using it, for instance:

      dup    == x\ [x] [x]

      pop    == x\

      swap   == x\ y\ [x] [y]

      i      == x\ x

      dip    == x\ y\ x [y]

      cons   == x\ y\ [[y] x]

      concat == x\ y\ y x

    Moreover, such a lambda construct makes Joy's "==" syntax unnesessary,

    in principle, and probably also in practice. For instance, suppose

    one made these definitions:

      sqr    == dup *

      dot    == [*] cons dip [*] cons dip +

    One could get the same effect using a couple lambdas instead of "==":

      [dup *] sqr\

      [[*] cons dip [*] cons dip +] dot\

    Anyway, that was just some food for thought...

    One other thing... it would probably be good to have some way of ending

    the scope of a variable; for this it seems natural to write "\x".

    Thus, for the squaring program we might write:

      x\ [x] [x] * \x

    By the way, it is not my view that Joy is broken and needs to

    be fixed by adding a lambda construct. Joy was deliberately designed

    to avoid the formal parameters associated with lambdas, and it

    does quite a nice job. In fact, adding a lambda construct as I suggest

    would not add any power to the language, as far as what programs

    can be constructed in it. There even exist systematic ways that one

    can use to eliminate these lambdas, replacing them with combinators

    like "dup", "dip", and "cons". Here is a simple but lame algorithm

    to do just that thing (it uses "i", "dip", "cons", "dup", and "pop"):

    Rule 1: x\ x   (if there are no future uses of "x") -> i

    Rule 2: x\ x   (if there are future uses of "x")    -> dup dip x\

    Rule 3: x\ A   (if there are no future uses of "x") -> pop A

    Rule 4: x\ A   (if there are future uses of "x")    -> [A] dip x\

    Rule 5: x\ [x] (if there are no future uses of "x") ->

    Rule 6: x\ [x] (if there are future uses of "x")    -> dup x\

    Rule 7: x\ [Z] (if there are no future uses of "x") -> [x\ Z] cons

    Rule 8: x\ [Z] (if there are future uses of "x")    -> dup [[x\ Z] cons] dip x\

    When we apply the example to this program,

      x\ [x] [x] * [x] -

    we get:

      dup x\ [x] * [x] -           (by rule 6)

      dup dup x\ * [x] -           (by rule 6)

      dup dup [*] dip x\ [x] -     (by rule 4)

      dup dup [*] dip -            (by rule 5)

    The algorithm happened to generate something fairly compact this time.

    Usually we are not so lucky. Of course, there are better algorithms...

    Anyway... that's enough for now...

    - Brent Kerby ("iepos")