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

[btanksley@hifn.com]

> From: iepos@tunes.org [mailto: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.

Good.

> > > 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".

Square a number, hopefully.  Possibly by multiplying it by itself, although
I didn't specify that.  What would you expect it to do?

Hmm, if you really wish to be literal, I would expect it to take a
representation of a number as input, and produce a representation of the
square of that number as output.

I'm not sure what blocks you from understanding the need for that, but
perhaps it'll help if I use a more complicated example: "Compute the DES
encryption of a 8-byte quantity."  The two procedures express the same basic
idea.

> 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.

Certainly you care.  Now, I'm not claiming that your _user's_ machine will
ever perform that action, but it's certain that somebody's machine will:
either your machine when it compiles the procedure, or the user's machine
when it runs the procedure.

> > 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.

Right.  Perhaps I should have said "a process taking place _through_ time"
rather than "in time".  A procedure consists of zero or more steps which
have a partial order to them with respect to time.

> > 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...

"Mapping" is a form of a verb, "to map".  In other words, a mapping may be
used as part of a procedure to map one thing to another.  A mapping is a
noun; a procedure is (essentially) a verb.

A procedure uses mappings (functions) to map values to other values.  If
this is impossible, then why on earth did you include both functions and
procedures in one language?

> > 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.

By making it take place as part of the procedure (as opposed to simply
denoting its existance).  You can't make it act like a procedure, of course;
but you can make it an atomic part of a procedure, and by doing so you make
it act "in time"; you make it capable of becoming an event.

> > 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.

In other words, the interpreter implicitly prepends the "&" operator when
appropriate.  There will be times when you will need to prepend it yourself.
(I don't care what the operator looks like, I'm just using a handy key.)

This is different from what would happen if the user typed "@@+ 4 5"; in
that case, I would expect the interpreter to cleverly realize that the user
probably wanted the system to perform the map thus indicated (even though
it's not a procedure and thus has no meaning in terms of being performed).

> 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):

W == [dup] dip i;

>   @@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.

Grin.  The problem is that I'm trying to think of your system as being
consistent and simple, when it's actually not.  It's got a very complex
interpreter, which tries its best to "do what you mean".  The thing is, this
actually makes sense for your language, since your language isn't about
_doing_ things; it's natural that your interpreter has to be smart in order
to _do_ things using it.

> Now, to explain "procedure completions" and why "B" can be used
> to concatenate 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...

What is a "large procedure"?  And isn't a procedure completion actually the
same thing as a "list of procedures"?

> 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".

Right.  In fact, it's essential to think of it this way, since otherwise it
doesn't work in your system.

>   @@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).

Isn't a procedure completion just a special type of procedure?  (Or is it
the other way around?)

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

Urf.  I'm certain I don't understand, because everything you've said makes
sense unless I try to assume that there's a distinction between procedures
and procedure completions.

> Now, procedures that "take parameters" (I would be reluctant to
> call them procedures at all)

Really.  Why?

> 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).

Really.  I was wondering about that.  Why not just make them procedures?

> 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.

Urk.  Now I'm getting confused.  Okay, so procedures with inputs are
emulated using functions.  This makes sense, since functions take inputs.
Cool.  But procedures with _outputs_...  Um...  Gee, that's _NASTY_.  Okay,
wait!  I see why you're doing this: procedures aren't functions, so they
don't 'return' values in the same manner as a function does.

Okay.  Sorry for the visible thinking process.  I think I understand the
reason for this; I'm missing one little thing, though, so I'm going to try
repeating what you said.

"@Input someFunction" means to get some input, apply someFunction to it
(resulting in a procedure completion), and then execute the resulting
procedure completion, right?  So in a sense @Input is a REALLY special
function, more like a combinator, right?

I don't know.  This whole thing is just mind-blowing.

Okay, so at this point it's pretty clear that "someFunction" has to be
_executed_ at runtime; unlike the other functions we've been using, it's
_forced_ to act like a procedure.  I don't like this: I think that your
model of input and output needs to be refined.  It just doesn't seem to work
with the rest of your ideas.  Perhaps one of the other applicative languages
might provide a useful theory?

Oh, and one more question.  Suppose I wanted to input a number and print the
number which is five more than it.  Let @Input handle numbers only (so that
we don't have to worry about errors).

@Input @Output @+ 5

Is that right?  We want to take two functions and one parameter, and produce
a single function which takes one parameter (which will be passed to the +).

If Joy were subject to the same restrictions, the program would look like
this:

[5 + Output] Input.

Do I get it?

Another possible example would be

[5 swap / Output] Input.

Or

@Input @Output @@C / 5

> 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

Hmm.  Yes, I think I see this.  And then if we write the result of Input as
"Input", we get:

@Output "Input" z

Thanks to the 'swap' action of @@C.  Right?

> 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.

Good call.  

> 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

Note that lambda actually does a poor job of modelling this action; the
problem is that lambda notation implies that the object being named remains
constant within a given lexical scope, and an object which is at one moment
'wet' and at the next 'dry' is not constant.

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

x\Dry Scrub Rinse x

> or alternatively, using "@",

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

Um...  Let me try...

Hmm.  I can't figure out how to have a function take a parameter which is
returned by another function, and then return something which is used by yet
another function.

Okay, after a weekend of relaxation it makes a little more sense.  It's
merely a matter of convention -- we have to choose which order the
parameters will go in.  I choose to put the parameter list before the return
function.

@@Rinse dish Dry

Hmm, it seems to me that multiple returns would be easy to perform (or at
least would be no harder than single returns).  Your opinion?

Finally, it's clear to me that you'd need a combinator to handle anything
more than two levels of that.  What combinator would that be?  How would you
Wash, Dry, then Rinse a dish using this design?

> 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

Ideally, it would be written (using my design) as

Rinse Scrub Dry.

However, using your design, your writing works; I would more commonly write
it as

dup Rinse dup Scrub Dry;

since we only duplicate before the use.  Makes sense to me.

Note that in my design, 'Dry' returns the dried plate, so the whole function
returns a clean and dry plate.  Your function doesn't return anything.  My
function can be modified to act like yours by rewriting it, intuitively
enough, as follows:

Rinse Scrub Dry drop.

Anyone who's every washed dishes and dropped at least one will see the
effects of this procedure/function.

> 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)...

How did I do?

> 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).

I don't really like it very much, honestly.  It may be pure, but I fail to
see any benefits this purity brings.  Joy is equally pure, but is _much_
easier to work with procedurally, mainly because Joy is theoretically based
on composition, and procedure execution has the same behavior as function
composition.

Whoops!  I was just checking my Python URLs for the week, and I read the
explanation of Continuations at
http://www.ps.uni-sb.de/~duchier/python/continuations.html; guess what?  It
turns out that your procedures match the formal version of the theory of
continuations.  Cool.  I've used continuations before, but I haven't seen
them explained that way.  Take a look.

> 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

Ah, yes.  This is much easier than my concept of having a list of
single-input functions.

> 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").

Start is a non-function.  That is, its only purpose is to do something, not
to 'return' something.

Right?

> 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).

Well, you _can_ check that the new theorem doesn't contradict the axioms,
can't you?

> 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).

Even simple Boolean logic is NP-hard.

> - "iepos" (Brent Kerby)

-Billy