Procedures in CLIP (was: Joy, Lambdas, ...)

[iepos@tunes.org]

I'm going to go back over how procedures might work in my system
("CLIP") since I wasn't too clear before... This will describe how
the system internally models procedures, as well as how
programmers would probably refer to them.

> > By "procedure", I mean a specific command
> > that something should be done, or the idea of that specific thing
> > getting done. In this sense, here are some examples of some procedures
> > (written in English):
> >
> >   - Go home.
> >   - Reboot yourself.
> >   - Output "Hello World" to the user.
> 
> "Square a number."  Okay, I'm with you.  

Wait... I don't think you are. Each of the above three examples
expresses an action ("going home", "rebooting oneself",
"outputting 'hello world'"). But, what action does "Square a number"
express? What would the system do if you told it, "Square a number".

Suppose we supply a specific number; for instance, does
"Square the number 3" then express an action? This may be getting
close to representing a real action, the action of visually changing
the number "3" into the number "9" inside one's mind. But, this is
quite a useless action that I don't really care if my system can perform.

> So 'procedure' connotes a process taking place in time, 

I guess this is correct... But, procedures like "go home" and
"reboot yourself" should be distinguished from events (as I'll
call them) like

  - the event of Joe going home (on January 5, 2000 at 5:00PM)
  - the event of Robo rebooting himself (at such-and-such time)

A "procedure", as I use the word, is about the same as a "command"
or an "instruction". One procedure could be executed several
different times by several different systems.

> whereas a function could denote a step of that
> process, but doesn't state anything about time.

No... A function, as I use the word, is just an abstract mapping from
keys to values... not a step of a process...

> So to make a function act procedurally, you need to transform it into a
> "completion" by attaching a next-thing-to-do to it, correct?

No... I'm not sure what you mean by "make a function act procedurally".
There is really nothing procedure-like about, say, the function
of squaring; I'm not sure how you would make it act like a procedure.

> > And, in this sense, the idea of "Output" (like the "printf" of "C")
> > is not itself a procedure, but a function that takes a string
> > and then yields a procedure.
> 
> Okay, so it's possible to have computed procedures.  This only makes sense.

This is correct. Another way of saying it is this: one can refer to a
procedure using an expression other than a single word.

> Let me try to write a brief program:
>
> &
>   !  @exec @Output @stringify @@+ 4 5
>      stop

This is not correct. "&", "!", and "exec" are all strange things that
you do not need. Also, "stop" is not needed in this example. If I
understand what you want the program to do, it should be written:

  @Output @stringify @@+ 4 5

This is a procedure that outputs the string "9". There is no need
to wrap it with "exec" or "&". When you type in an expression
representing a procedure, the interpreter will probably respond
by executing the procedure, and then giving you another prompt.

Now, suppose you wanted the system to do the procedure twice,
then you would compose the two procedures together using "B", as in:

  @@B @Output @stringify @@+ 4 5 @Output @stringify @@+ 4 5

(in a moment, I will clarify on why composition is used,
and what I meant by "procedure completions" and when "stop" might
be used). Since we are composing the same thing with itself we
could use "WB" (the self-composition combinator; in general,
"W" takes a binary function and yields a similar unary one
with a duplicated parameter, so to speak):

  @@WB @Output @stringify @@+ 4 5

This would be a procedure that outputs the string "9" two times.
 
> Okay, that makes a little more sense.  (I'm not allowing myself to think
> about the logic involved in a function which executes a procedure -- that
> doesn't even begin to make sense -- but it's the first thing I thought of.)

I agree... a "function which executes a procedure" doesn't even
begin to make sense.

Now, to explain "procedure completions" and why "B" can be used
to concatenate procedures...

Often, actions that the system might execute have a certain time of
completion. For instance, if the user typed in

  @Output "hello"

into a shell, after a while the system would be finished executing
it, and it would be time for the shell to give another prompt
(well, depending on the nature of the shell, this is probably
what it would do). 

By the way, the technique of procedure completions that I'm about
to describe is not the only way that one could do procedures in
an applicative system of the style I'm considering, but it is one that
I find quite natural... Using it, it is not necessary to have extra
primitives for concatenating procedures or returning results from
procedures.

Basically, a "procedure completion" is a string of things to do,
although it is distinct from a large procedure or a list of
procedures. It may seem odd that we make up a new notion
"procedure completion", when seemingly we could emulate it
using just a large procedure or list of procedures. But,
doing it this way will be fruitful, I think, so bear with
this explanation...

Using procedure completions, it is possible to think of a procedure "p"
as a function that takes a procedure completion "x" (the thing to do
after the procedure terminates) as a parameter, and yields another
procedure completion, the procedure completion of doing "p" and then
going on to do "x".

Stated again (this is important), a procedure is a function that 
  takes a procedure completion and
  yields a procedure completion.

For instance, the procedure

  @Output "hello"

can be thought of as a function that takes a procedure completion
and yields a procedure completion. Essentially, the procedure completion
that results is the same as the one that is taken except that the action
of outputting "hello" is prepended. For instance,

  @@Output "hello" other-things-to-do

is a procedure completion to output "hello" and then go on to
do "other-things-to-do". Remember that a shell in the system
will probably not actually want to be given a procedure completion,
but instead a procedure (a shell could possibly be constructed
which took a procedure completion rather than a procedure,
but I would prefer that it take a procedure). But still, it
is useful to talk about procedure completions (there are also
some times when one may explicitly want to refer to a procedure
completion in the system; this will be described later).

Now, since "@@Output 'hello' other-things-to-do" is a procedure
completion that outputs "hello" and then does those other things,
it follows that

  @@Output "hello" @@Output "world" other-things-to-do

would be a procedure completion that outputs "hello" and then
outputs "world". What I'm leading up to is that

  @@B @Output "hello" @Output "world"

is a procedure that outputs "hello" and then outputs "world"
because, by the definition of "B", applying this procedure
to a procedure completion "z" results in

  @@Output "hello" @@Output "world" z

As a reminder, the rewrite rule of "B" could be expressed

  @@@B x y z   ==   @x @y z

Hopefully this is starting to make sense now.

Be sure to keep in mind the distinction between procedures
and procedure completions... 

Now, procedures that "take parameters" (I would be reluctant to
call them procedures at all) are emulated using functions onto
procedures. For instance, "Output" is a function that takes a
string and yields a procedure (this has been mentioned before).

Procedures that yield results are emulated in a similar way.
Recall that most procedures (that don't yield results) take as
a parameter just a completion, a thing to do after the
procedure is done executing; in contrast, a procedure with
a result (for instance, an "Input", which reads a line from
the keyboard, and results in a string) takes not a procedure
completion, but a function onto a procedure completion.

As an example, a procedure that takes an input using "Input" and
then spits the resulting string back out with "Output" could be written:

  @@B Input @C Output

That might not have made sense... Maybe it will make sense if
you note that when this procedure is applied to a completion "z",
you get (by definition of "B"):

  @Input @@C Output z

Remember that "Input" is a function that takes as a parameter
another function (a function that, given the resulting string of
Input, tells what procedure completion to do next). Here,
we have applied "Input" to the function "@@C Output z".
Essentially, this function "@@C Output z" is a function that
takes the resulting string "s" and yields "@@Output s z",
a procedure completion that outputs the string "s" and then
goes on to do "z".

I'm guessing this may still seem a bit foggy, as it is not
entirely familiar even to me, who has made up this system.
The best thing to do now, then, seems to be to give a few
more examples... For a bit, I'll stay away from procedures that give
results, since these are probably the most confusing. One simple
example...

  @@B Rinse-it @@B Scrub-it Dry-it

is a procedure that Rinses, Scrubs, and then Dries it (where
"Rinse-it", "Scrub-it", and "Dry-it" are simple procedures). This
is just a reminder that composition can be used to concatenate
simple procedures. Using syntactic sugar "." for composition, this
might be written as:

  Rinse-it . Scrub-it . Dry-it

This procedure, when applied to a completion "z", gives

  Rinse-it (Scrub-it (Dry-it z))

This is a procedure completion that does Rinse-it, Scrub-it,
and Dry-it, and then goes on to do "z". It could have been
written in that "@" syntax as

  @Rinse-it @Scrub-it @Dry-it z

Now for another example... Now suppose we have more general
primitives "Rinse", "Scrub", and "Dry", which are functions
(taking a piece of dishware or something) that yield procedures;
these procedures would be kind of like the "Output" mentioned
earlier, which is also a function that yields a procedure.
Now, with these three primitives, we want to form a function
that takes a piece of dishware and yields a procedure that does
all three things to it; using a lambda, we could express this
procedure as

  x\ (Rinse x . Scrub x . Dry x)

or alternatively, using "@",

  x\ @@B @Rinse x @@B @Scrub x @Dry x

This procedure could be expressed without a lambda, using the
"N" combinator, as

  N B Rinse (N B Scrub Dry)

or alternatively,

  @@@N B Rinse @@@N B Scrub Dry

What exactly the "N" combinator is I won't go into (unless you ask),
except that it can be constructed from other combinators as "B(BS)B"
and that its rewrite rule is:

  Nfghx = f(gx)(hx)

The "N B" combinator (or just "NB") turns out to be quite
interesting; it is associative in that "NB (NB x y) z" is the same in
all cases as "NB x (NB y z)". This "NB" combinator turns out to
act as an addition function among the Church Numerals, and so
we might write that last procedure with syntactic sugar "+" for
"NB" as

  Rinse + Scrub + Dry

This is quite a clean result (I wouldn't expect it to always be
quite this pretty). Remember that this whole thing is a function
that takes a piece of dishware "d" and yields the procedure

  Rinse d . Scrub d . Dry d

This procedure is a function that takes a procedure completion "z"
and yields

  Rinse d (Scrub d (Dry d z))

or in other words,

  @@Rinse d @@Scrub d @@Dry d z

For curiosity, a program analagous to "Rinse + Scrub + Dry"
I think would be written in Joy as

  dup dup Rinse Scrub Dry

Anyway, do you understand now the way of doing procedures that
I've described? (If you do, you might try to give me another
example program)... It seems to be quite a nice, pure approach
that, as far as I know, has never been attempted (of course, it
may have been attempted and I not know).

Now, I'll restate again how procedures that yield results work...
Whereas "Rinse-it" is a function that takes simply a procedure
completion (telling what to do next, after "it" is done
being rinsed), a result-yielding procedure takes not a procedure
completion, but a function onto a procedure completion.

For instance, we'll take "Pick-favorite-dish" as a simple result-yielding
procedure. We can think of it as a function that takes a
function (a function that tells what to do next, when applied to
the favorite dish). For example, suppose the system wants to
execute the procedure completion

  Pick-favorite-dish foo

The system would execute this by deciding what its favorite dish
was (call it "d"), and then going on to execute the procedure
completion "foo d".

Procedures that yield multiple results might be emulated as
a single-result-yielding ones that yield a list; but, more
likely one would use a procedure that took a multiple-parametered
function (multiple-parametered through currying). For instance,
let "Pick-two-things" be some procedure that yields two results
in this way. Then, when the system executes the completion

  Pick-two-things foo

It will do the action associated with "Pick-two-things", and
then do "foo x y", or in other words, "@@foo x y", where "x" and "y" are 
the two results that the procedure yielded.

One other interesting thing... 

  Y (Output "hello")

is a procedure completion that outputs "hello" over and over again
(forever), if "Y" is the recursion combinator. For, by the rewrite
rule of "Y", it is the same as

  Output "hello" (Y (Output "hello"))

That was a procedure completion that did "Output 'hello'" over
and over again. If one wanted a procedure instead, one could use

  K (Y (Output "hello"))

This procedure ignores its parameter, the "next thing to do".

By the way, the above discussion may have made it seem that
all procedures in my system will be functions that take a
procedure completion (or else a function onto one) as a parameter,
telling what to do after the procedure terminates. This may
not exactly be the case; some procedures, for example, might take two
procedure completions as parameters, the first telling what
to do next if the procedure "succeeds", and the other telling
what to do if it has some sort of failure. I'm not really sure in
general how I'll handle failures with procedures in my system;
there are probably several different ways to go about it...

The system will probably need lots of primitives involving
procedures, like "Output", "Input" and such (actually, the
initial system will probably use lower-level primitives
for writing to the screen, and will construct its own
"Output" and "Input"). As I've remarked before, several
primitives involving concurrency and fields will probably
be needed...

One random thought... I mentioned earlier that I'd give 
an example use of "stop", which is what I'll do now
(well, I'll get to it in a second)... Sometime in the system
I'll probably use a "meanwhile, start working on this" primitive,
a procedure primitive (actually a function onto a procedure,
like "Output") which initiates another task. Suppose we
call this primitive "start", then here would be an example program
involving it:

  start (Output "hello" stop) . Output "world"

This would be a program that outputs "hello" and "world" but in
an order undetermined. The "start (Output 'hello' stop)" part is
a procedure that executes very quickly probably; it tells
the system to start working on "Output 'hello' stop", but
the system only has to _start_ working on it before proceeding;
it might not be _finished_ doing "Output 'hello' stop" before
going on to do "Output 'world'". If an interpreter executes
this program, it might even give the next prompt before
outputting "hello", although "world" will definitely be
outputed.

Note that "start", as I've used it, takes a procedure completion,
like "Output 'hello' stop" as a parameter, but not a procedure,
like "Output 'hello'". One could conceivably construct a
"start" that takes a procedure rather than a completion
(in fact, such a thing could be constructed from the original
"start" as "B start stop"), but the one that takes a completion
is better to me. Anyway, they are both interdefinable
(the ordinary "start" can be defined from the other start
as "B otherstart K").

Hopefully this explanation was helpful... There are still many issues
relating to the system that I haven't decided on. One of the
biggest questions, and this was mentioned in the last post,
is "How will the system be implemented?".

Actually, I've already started implementing a system. I have
something that works but that is not usable. Within a few
weeks it should be ready for toy purposes (for instance,
outputting the first 100 prime numbers, or a number guessing
game, or finding a solution to the Towers of Hanoi).
Currently, numbers are implemented using "int"s. This does
not really satisfy me; I plan on going back and reimplement
the system to use Church Numerals, but this will probably take time
and I do not want to wait any longer to get a system that
can at least do something interesting.

One other question about the system that I haven't really decided on is:
"Will there be a logic system integrated into the system?
If so, how would such a system work (internally and externally)?"...
Such a logic system would probably store Theorems in some way,
sometimes deriving new ones and tossing out old ones; such
a system would probably assist in normalizing expressions...
For instance, if a user had told the system that "foo" is
an integer and that "foo*2 + 1 = 9", then the logic system
might help the normalize "foo" to "4", if "foo" needed
to be normalized at some point.

Such a logic system would be a very nice thing to have in a system,
but there are a few pitfalls I suppose... Logic systems tend
to be of a very fragile nature (I guess almost all computing systems
are of a fragile nature, but logic systems are the worst, I think).
For instance, suppose a user told the system that "K = CK" (or "0 = 1"
or something of this sort)... This could tend to result in a system crash,
since if the system really accepted it, then by some simple reasoning
it could replace any expression for any other expression; the system
might decide to recompile itself to be more "efficient" (but
accidentally incorrect, although provably correct, since
anything at that point would be easily provable by the system).

One solution to this "fragileness" problem is for the system
to be careful when applying newly obtained information in
certain ways; it may wish to restrict itself only to highly
trusted axioms when verifying the correctness of a new compilation
of itself, for instance. Also, the system might do common-sense
consistency checks before accepting new information at all, to make
sure it is not absurd; but, a full consistency check (meaning a
proof that the added information will not cause everything to
be provable) in general would not be possible, I think, according to
"Godel's theorem", unless the system is already blown
(in which case everything would be provable, including
that the system is consistent).

Another problem with having a logic system is that logic
problems are indefinitely difficult. In general, 
not even a brute-force algorithm exists for testing
theorems, much less an efficient one (at least, this is true if
the system contains the so-called "first order predicate logic" 
which is undecidable). If programs were distributed,
one would probably not want to include logic problems in
the program; rather one would "compile" in an ordinary
procedure to find a solution (this would require some indefinitely
difficult work on the original machine, but the program could then be
straightforwardly executed on the other machines)... but then,
the program might want to be provided in its original form
too, in case a target system is smart enough to find a better
solution.

Anyway, that was quite a vague thought (sometime I'll have
to think of some specific problems to illustrate what I'm saying)...
I don't think I'm going to build in a logic system into the
prototype system, although I might try to make one on top of it
at some point, storing the theorems using fields. A nice
logic system is something that I think I'm going to need
before a nice efficient compiler (with provable correctness)
can be implemented; also, a logic system is a valuable tool
by itself, from a user's perspective.

And ... the rest of your comments I'll reply to in another post...

- "iepos" (Brent Kerby)