Joy, Lambdas, Combinators, Procedures

[iepos@tunes.org]

It's been awhile since I've made any comments to this list,
so now I'm posting some of my thoughts...

A while back, some TUNES-sters expressed admiration for
the Joy programming system. Although the current implementation
seems inadequate for serious practical use, it does have some
interesting features.

In particular, Joy is nice in that it does not require one to
use variables or anything like them. Instead, one uses
primitive programs which they call "combinators" (which are
similar to combinators in the ordinary sense).

One thing about Joy which bothers me is that it gives no way
to formally express, for example, the number "2". Although it
is possible to express the _program_ that "pushes the number 2
onto the stack" (such a program is expressed simply as "2"), the
number 2 itself cannot be represented. 

This is a defect that seems fairly serious to me, although I suspect
that it may be possible to fix the defect by reformalizing
the interpretation of the system (perhaps eliminating the "stack")
without changing how the system actually works.



Anyhow, enough about Joy... now I'll describe some ideas I've had
for a programming system, if anyone is interested...

In the system I'm thinking of, things would be expressed using
purely applicative expressions (with mild syntactic sugar).
That is, the system would supply some primitives (mostly functions),
and then other things could be expressed in terms of these
primitives using function application. Composition can be
expressed using the "B" combinator, which will probably be
taken as a primitive.

Only a single-parametered function application is necessary,
of course, since multiple-parametered functions can be emulated
using single-parametered curried ones (i.e., functions that return
functions).

In a programming system, one important question to ask is
"How will the system deal with procedures?", since procedures
are quite important in programming systems. The system will
likely have some primitives for forming procedures; for instance,
there would likely be, say, a "put" which is a function that
given a string, yields a procedure that outputs that string.
So, using this, a hello-world "program" could be expressed:

  put "hello"

Which would be syntactic sugar for something like

  put (makelist 5 'h' 'e' 'l' 'l' 'o')

A question that arises is: "How will it be possible to chain
procedures together?". For example, how could a procedure
that prints "hello", waits for one second, and then prints
"world" be expressed? 

One way would be to add a "chaining" function as a primitive,
a function that, given two procedures, yields a procedure that
does the first procedure and then the second. Using such
a "chain" primitive, the procedure mentioned above might
be expressed:

  chain (put "hello") (chain (wait 1) (put "world"))

However, there is a more elegant approach: build the "chaining"
into the procedure primitives; that is, make "put" (and other
primitives) take an additional parameter, a procedure that
tells what to do after the output has been written... with
this technique, the above procedure might be expressed like:

  put "hello" (wait 1 (put "world" stop))

This seems to require a "stop" primitive. Anyhow, this is probably not
really a new idea. In a system that uses this technique, it would be
important to distinguish between procedures, like
  
  put "hello"

and procedure completions, as one might call them, like
  
  put "hello" stop

Also, the function "put", by itself, is neither a procedure nor
a procedure completion, but a function onto procedures
(in this system, functional abstraction will certainly not
be welded in with constructs for forming procedures; this
would be in contrast with languages like C and Scheme
(but not Joy)).

As it turns out, in this kind of system, chaining of procedures
can be expressed using composition; for instance, the
procedure that puts "hello", waits a second, and then puts "world"
could be expressed:

  put "hello" . wait 1 . put "world"

where "." is composition. This seems to be quite an interesting
coincidence, that composition works as a program-sequencer in
both this system and the Joy-style system, even though Joy used
an entirely different model of procedures (a procedure in Joy
was considered a function from an input state to output state,
while a procedure here is considered a function that takes
another procedure, yielding a "procedure completion").

Likely, a simple interpreter might like to read in an expression
denoting a procedure, rather than a procedure completion. The
interpreter could supply its own completion, as it naturally
would if it wanted to do something in particular (such as take
in the next input) after it was through executing the procedure.
So, a "stop" primitive is not really necessary (although in a
real system it would probably be needed for other purposes).

Some fairly fundamental procedure primitives a system might want
to have ... 

  - a "wait" primitive, that executes a procedure after some specified
    amount of time.
  - a "do-all-these" primitive, that given a set of procedure 
    completions, yields a procedure completion that does them all
    (possibly simultaneously).
  - a "do-one-of-these" primitive, that given a set of procedure
    completions, yields a procedure completion that does one of
    them (the system's choice).
  - some primitives for setting and getting the states of fields
    (i.e., devices like global variables). Many procedures could
    be expressed in ways that do not involve fields; but, in
    a complex systems, fields will probably be essential, particularly
    for coordination between multiple procedures that may be executing
    at once. Anyhow, I don't see fields, in their pure form,
    as "unclean".

In addition to setting and getting procedures for fields,
there will probably need to be a procedure that waits for a field
to enter a certain class of states.

There will likely also need to be several other primitives which
I have not thought of, such as a procedure to prematurely terminate
another executing procedure (such a procedure would take as a parameter,
not a procedure or procedure completion, but an "execution"; i.e.,
a specific running procedure completion); this, of course, would
be an awful primitive to use without some sort of way to formalize
cleanup, so that an execution may finish cleaning up instead
of abruptly stopping.

Anyway, there are probably a myriad of ways of doing procedures
in a system; when designing this basic part of system, it might
be a good idea to keep in mind the question, "How might one describe
these procedures in a natural language like English?". A good
system might want to provide constructs for expressing procedures
that are at least as powerful as those one might usually use
to express procedures in English.

Anyway, I've gone off on a bit of a tangent. Before forgetting
about procedures, there is one other interesting thing to
think about: procedures that yield results. It will probably
not be necessary to use too many result-yielding procedures in a
functional-style system, but we might like, for instance, a
primitive like "get", that reads a line of input from the user
in some way. Such a procedure would need to yield a result.
This is really quite simple to do in the kind of system I've
described; rather than having "get" take another procedure as
a parameter, telling what to do next, have "get" take a
_function over_ a procedure. For instance,

  get (x\ put x stop)

is a procedure completion that gets an input and then puts it;
the "x\" is supposed to be a lambda, the expression could
be written with the C combinator as:

  get (C put stop)

A procedure similar to this procedure completion could be written:

  get . C put

Anyway, I have no excuse for not actually implementing a system
like this ...

Except that I've gotten sort of hung up on how to deal with
numbers in the system (and numbers must immediately be dealt with,
because I need them to represent the coordinates for characters
on the screen; this could be avoided if i used something like "put"
as a primitive rather than a raw interface to ncurses as I was,
but it needs to be dealt with at some point anyway).

I was planning on using Church-style functional numbers (i.e., "iterators"),
rather than taking numbers as primitives. However, ultimately
I need to get the numbers into a base 2 form, so they can be
used as indices for the screen. And this has brought up an
important question of how the system should internally represent
things; in my toy system, I had planned to represent everything
using binary (function application) trees, with primitives at the nodes.
However, this will not be practical for numbers; at least it won't
be practical to keep them in beta-reduced form (the size of the
beta-reduced form of a Church number is proportional to the size
of the number, which is not too good).

Usually, putting expressions in beta-reduced form seems like the thing to do
when getting ready to interpret them. When two Church numbers are in
beta-reduced form, it is easy to see if they are equal, or to see which
one is bigger. However, this is not practical, even in a toy system.
The obvious approach is to represent numbers in the standard
base 2 form, as a sum of powers of two; this is the form I ultimately
need to get them in at some point anyway; plus, in this form,
it is easy to calculate many operations like addition, subtraction,
multiplication, and division (i.e., given two expressions "x" and "y"
in base 2 form, it is easy to get "x + y" and such into base 2 form also).

Still, at a high level, I do not want to give up Church numbers.
Also, base 2 form only works for integers (or perhaps, using "fixed point",
certain fractions); and, base 2 form also becomes inadequate for
very large numbers. For instance, the number "9 9 9" (nine raised
to the "9<sup>9</sup>" power) we can easily represent using just five
characters, but in base 2 form, it would take over a billion bits
to represent.

Anyway, in my toy system, I'll probably end up keeping everything in
a binary tree form, but not necessarily beta-reduced. When I need
to get an expression into a base 2 form, I'll put it in it,
which will involve looking at the expression and seeing if
it represents a number primitive "0" or "1" or maybe "2" or "3" (or ...),
in which case it is quite easy to put it in base 2 form;
otherwise, if its of the form "x.y" then we have composition
which is multiplication for Church numerals, so "x" and "y"
will each be put in base 2 form, and then a (relatively) efficient
shifting algorithm will be used to multiply them; otherwise
if it is of the form "NB x y" (addition) or "x y" (exponentiation)
then some other algorithm will be used... If, unfortunately,
it is in none of those forms, then it will be necessary to
resort to Strong Reduction to get the expression into base 2 form
(since the user must be using some fancy way of forming
numbers, other than small primitives and addition, multiplication, etc.).
If it turns out that the expression does not even represent a
Church numeral, then the user will be chewed out.

Actually, I do not know of any good ways of doing strong reduction
(i.e., the kind of reduction in which "BCC" is reduced to "I"
and "B(Bfg)h" is reduced to "Bf(Bgh)") with combinators. In fact,
the only ways I know of involve using Variables (the simplest
way being to rewrite the expression using lambdas; in this form,
strong reduction is quite easy; then, when done, one would
rewrite it back using combinators). In "Combinatory Logic", Curry
says that no finite axiom scheme will do for strong reduction;
he gives an "infinite recursive" scheme, but does not offer
any evaluation strategies. Anyway, that was old stuff. I don't
know if anyone has come up with anything since then. Can anyone
enlighten me?



Anyway, enough rambling... As usual there is my recently updated
site on TUNES at

  http://www.tunes.org/~iepos

which I humbly proclaim as the Best source of introductory
information on combinators (that I know of).


- "iepos" (Brent Kerby)