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

[btanksley@hifn.com]

> > > But, what action does "Square a number" express? 
> > > What would the system do if you told it, "Square a number".

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

> Ahh... This example did help. Thanks. Such a program could be
> represented in my system... Reverting back to the simpler example of
> squaring, a program to compute the square of 129 could be written as
> something like:

>   put (stringify (square 129))

Well...  Yes.  That's a procedure which _prints_ the square of 129.

A procedure which simply _computed_ the square of 129 would likely look a
lot like a function which did the same thing -- but on the other hand, it
might compute the square by doing a series of additions (just to suggest one
possible silliness).  OTOH, a procedure to compute the DES encryption of a
bytestream would be quite logical: there might be two different procedures,
one for software and one for hardware.  Both would enact the same function.

> This seems to me like a natural way to express the procedure,
> since what you really want the system to do is print onto the
> screen a string representing (in some normal form that the user
> can understand) the square of 129. If you told the system just,

>   square 129

> it would respond with an error, complaining that this was not a
> procedure and that it could not execute it.

You're assuming that 'square' isn't a procedure -- why do you assume that?
"square stop 129" is a perfectly valid way to ask the computer to perform a
squaring (assuming that 'square' is a procedure).  It would run, consuming
some CPU cycles, and then stop, returning the result to 'stop' (perhaps
'stop' doesn't like results, but that's a different question).

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

> Hmm... certainly functions could be used to construct procedures...
> Actually, every function has an associated procedure, a procedure
> which takes a single parameter, has no effect, but then results
> in the function of that parameter (procedures like these, that have no
> effect, in general I will call "pure procedures"). There is
> a precise connection between functions and their associated
> procedures; however, functions would be distinct from their associated
> procedures in my system ...

That's not what it looks like in your system.  How do you mean 'distinct',
when a function returning a procedure is treated as though it WAS the
procedure, and a procedure can allegedly return a function, and a procedure
can accept a function as a parameter (and all continuations are actually
functions yielding a procedure)?

> There is probably a little bit of confusion now associated with the
> word "procedure", since I have used it in several distinct ways...
> I originally used "procedure" to refer only to specific
> things-to-do. A specific thing-to-do I will now call a "command"
> (this use of "command" is similar to what I called "procedure 
> completions")
> while a "procedure" I will use to refer to things that are
> like commands, except that they take parameters and yield results.

Okay.  So a command is simply something to do; it takes no parameters of any
kind.

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

> And who is the one to apply the FORCE?

The definition of your procedures.  A real function has parameters which are
known at compile-time; a function given to a procedure does not know its
parameters.

> I do not see the problem
> that apparently you see. Note that it is not "someFunction" itself
> that is executed (it would not make sense to execute a function).
> Rather it is the application of "someFunction" to the "foo" input;

Exactly.  Application happens implicitly and at runtime; everywhere else in
your system, application is obvious, explicit, and compile-time.  Do you
still not see the asymmetry?

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

> 8-(

> Really I see no problem with this model of Output and Input...

I'm glad you found the problem and figured out a fix for it -- the system
you describe below makes a LOT more sense.

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

> > [5 + Output] Input.

> > Do I get it?

> Yes, I think this is right, although this would be a weird thing to
> do in Joy, of course... One would probably really use

>   Input 5 + Output

Oh, of course.  Grouping isn't needed to cause composition to occur in Joy.

> > Another possible example would be

> > [5 swap / Output] Input.

> I'm not sure what is meant by "/" here...

Division.  What would you have used?

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

> Uh oh... I can see that using a physical example was a bad idea.
> I had thought of Rinse, Scrub, and Dry as simple procedures with
> no results. I had thought of the "piece of dishware" as the
> abstract "identity" of the dish, not the state or the physical
> structure of the dish, which changes over time.

Calling these "simple procedures" may be useful -- but then we have to note
that "simple procedures" are not as simple as "pure procedures".

> Another example
> may help clarify this; consider this command here written in English:

>   Send Bill the letter.
>   Then, wait until Bill sends back a response.
>   Then, throw the response in the trash.

> Does it seem unnatural that the command makes several references
> to "Bill"; would it have been clearer if the author had written
> "the new Bill" in the second occurence to make clear that
> Bill may no longer be the same? It seems to me that it would
> not make it clearer; the two references to "Bill" refer to
> the same person... My multiple references to a piece of dishware
> are similar to the multiple references to Bill in this silly command.

Actually, in English every explicit mention of a name implies a change of
meaning -- every time you name Bill above you imply vaguely that you could
be talking about any person or thing named "Bill".  If you wanted to be
certain that your (literal-minded and stupid) reader knew what you were
saying, you'd have to use pronouns, like so:

  Send Bill the letter.
  Then, wait until he sends back a response.
  Then, throw it in the trash.

But either way, this is not in the least declarative; the use of 'he' or
'Bill' simply serves as a handle to an object of unknown state.  Not a very
good comparison to a functional mathematical model.

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

> It sounds like you have three functions, and want to yield their
> composite. If your three functions are called "f", "g", and "h",
> then the composite could be called either "B f (B g h)" or 
> "B (B f g) h", since "B" is associative; or you could just
> write it as "f . g . h", using sugar...

No, I have three *procedures*, and want their composite.  But you answered
that below -- it's pretty simple, when you think about it right.

> If I understand, you want your "Rinse" procedure to take a dish,
> and then result in the new dish (the new "rinsed" dish, as if
> it were distinct from the original; I guess we are now talking
> about the states of the dishes, so to speak, rather than the
> "abstract identity" of the dishes).

Correct.  This is neccessary in order to model the behavior of the procedure
in a functional manner.

> The "Rinse" primitive itself
> would then be a function of the type
>   Dish -> (Dish -> Command) -> Command

> Essentially, "Rinse" takes a Dish and a continuation that uses the
> new Dish.

Right -- or the modified old dish, however you wish to put it.

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

> Yes... I see that, if "drop" is a synonym for "pop" (is it?).

Yes, it is.  I've programmed a LOT more in Forth than in Joy.  In ANSI
Forth, POP isn't defined, but in Chuck Moore's Forth it refers to popping
the TOS and placing it onto the return stack.

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

> 8-(

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

> I suspect that my kind of system may lend itself better to textual
> reasoning, the primary fault of Joy being the "opaqueness" of
> the quotation construct; but, as you've said, this problem of Joy
> could be remedied...

We fundamentally disagree here.  Joy's quotation construct needs to be
opaque only in the presence of either broken functions (functions which
don't handle recursion endcases correctly) and functions which expect a data
structure rather than a quotation (in which cases a raw quotation is a poor
design).

If I were to decide that the opaqueness was a serious problem, I could
completely remove quotation introspection from Joy, at which point it would
have the same feature set that your language has.  However, unlike you, I
consider quotation introspection to be a *feature*, not a bug, and its
removal would destroy a lot of expressive power, and in fact make our
languages functionally equivalent.

> > mainly because Joy is theoretically based
> > on composition, and procedure execution has the same 
> > behavior as function composition.

> My approach is also theoretically based on composition (although
> composition does not play quite so fundamental a role as it
> does in Joy).

No, your approach is based on application.  You can certainly *do*
composition, but then I can also imitate application (I have to use
quotation to do that).

> Now I'll share with you my some new (untested) enlightenment...
> All this time with primitives like "Output" and "Putc" I have
> been having them take the continuation as their final parameter
> (after the string in the case of Output, or after the coordinates
> and the character, in the case of Putc). I now realize that the
> correct way is for the continuation to come First in the parameter
> list (I know this sounds like a terrible, doctrinaire statement,
> but bear with this and you will see that it really is Better 
> this way).

No, no!  It sounds like a terrific insight.  I wish I had thought of that
;-)!  It unifies your procedures with your combinators.  Very cool.

> I will now redefine what I mean by "procedure" (this is not consistent
> with my prior usage, but who cares):

>   a "procedure" is a function that takes a continuation parameter
>   and possibly several other parameters afterwards, and 
>   yields a command
>   that that does something and then goes on to do either the
>   continuation, or else an application of the continuation to
>   something else, or else an application of such an application
>   to something else, or else ... (what we're trying to say here
>   is that the continuation may be applied through currying to
>   as many things as the procedure wants to apply it to, although
>   the number of such things must be the same each time).

Okay.  I'm dizzy. ;-)

A procedure is a function which takes a continuation parameter, and returns
a function (if it can take more parameters) or a command (if that's all the
parameters it can take).

The function it returns is like the original procedure-function, except that
it _doesn't_ take a continuation.  Shall we borrow from your (now obsolete)
terminology to call the type of this function a "procedure completion"?

So, we start out with a function, which represents a procedure.  Every
procedure requires at least one parameter to be bound to it: its
continuation parameter.  The function takes as an argument a continuation,
and returns a completion.

A completion is a command if and only if every one of its parameters is
filled.

A continuation is a completion with exactly one parameter unfilled.  (This
restriction is subject to change -- perhaps multiple-value-return will bind
to multiple parameters.)

> You can see that the rewrite rules for these combinators are
> quite similar to the rules that Joy uses for "swap", "dup", and "pop",
> except that these seem to have an extra parameter "f" at the
> front that was not present in the Joy analogues; this parameter
> is essentially the continuation parameter...

Yes, this makes complete sense.

> The "C" combinator, for instance, can be thought of as a procedure
> which takes a continuation parameter "f" and then two other
> parameters "x" and "y"; it goes on to do just "f y x". Essentially,
> the "C" combinator, if you think of it as a procedure, takes
> two parameters and has two results, the two results being the
> exact same as the two parameters except that they are swapped.

Conceptually, this is true.  Textually, it's not -- because 'x' or 'y' may
have multiple returns in Joy.  If you wish for this to apply textually as
well, you need to explicitly group x and y (the use of variables provides
grouping in your notation which is not actually present in either of our
languages -- for example, suppose you were to replace "x" textually with "3
4").

@plus x y
->
@plus 3 4 y

(Oops!)

> Note that the order of the parameters has been reversed; the
> "T" combinator naturally has a reversing effect... Note that
> this program written as "T 'x . T 5 . T 4 . putc" is quite
> analagous to how one would write it in Joy, as:

>   'x 5 4 putc

Wow.  That's really clean.  One could almost name "T" as "Literal" or
"Leaf", and pretend that it is the equivalent of Forth's (LIT) primitive.

Question: how would multi-parameter functions be called?  Suppose we have
'putxy', which takes two screen addresses and does something with them.

  T 3 . T 4 . putxy

Hmm...  this looks right.  I'm not too familiar with the derivation process,
but it seems to work.

Also, formally your language doesn't support multiple returns from
functions; but by using T, we see that:

USING getxy == T x . T y
IN
   getxy . putxy == T x . T y . putxy;
END IN;

is valid.  So we "imitate" other aspects of the stack.

Right?

> In contrast to my other example program that did the same thing,
> it is now not necessary to use "C" (it was only necessary before
> because the "Output" was Backwards).

Eminently logical, and it should have been obvious to both of us.

> This function takes a continuation "f" and yields the application
> of that continuation to "3", "4", and "5". There are ways to write
> this function without using a lambda; one way is

>   T 5 . T 4 . T 3

Um...  This isn't a list (or quotation) in the Joy sense, though.  It's just
a bare set of stack parameters.  You need to group those in order to emulate
lists, and even there you haven't emulated the list operators.

> I think I can almost see a direct way now that Joy procedures can
> be translated into procedures of my system. I think I'll give
> it a try...

> First I'll start with a simple example: the Joy program "3 2 + put",
> which outputs "5". That program would be written in my system as:

>   T 3 . T 2 . T + . B . B . put

Where did those 'B's come from?  And why is there a 'T' in front of + but
not in front of 'put'?

> This is the program that puts "5" and then goes on to do "f"...
> If one were really going to write this kind of program in my
> system, one would probably use something like

>   T (+ 2 3) . put

> In the first version, the "+" operator of Joy was translated into
> the "T + . B . B" of my system, since the "+" of Joy sort of has two
> applications built into it. 

Hmm.  Confusing.  So a procedure with a single application doesn't require
any 'B's to follow it, but procedures with two applications require two
'B's.  How about three parameters?

Oh, wait!  I figured it out -- the extra B is for the return value (or
continuation) binding.  I think I get it now.

> Now for the matter of quoted programs... A quoted program in Joy
> is a simple program that does nothing except push a single
> result onto the stack. The way I'll translate quoted programs in
> my system will reflect this... A quoted program like "[3 2 + put]"
> will be translated as just "T (T 3 . T 2 . T + . B . B . put)";
> basically it is translated the same way as the program within
> the []s, but with "T" applied to the whole thing.

Yes.  That works very well -- except, of course, for the ability to treat
that program as a list of operations.

> Isn't this weird... ?

Absolutely.  And very cool.  Modulo a few translation problems, which you
mention in another letter, this provides some additional ways to reason
about both of our systems.

> Also, I think I might have some trouble constructing certain
> operators on lists... for instance, the "length" operator which,
> given a lists, gives its size... I'm not sure how I would 
> construct it...
> It would be possible, though, if I had a "reification" 
> primitive or such...
> But, the solution I usually use is to make the first element of
> a list contain its length in some cases... I'm not sure if
> this is good or not, though... Another option would be to construct
> lists as chains of pairs, with a terminator; this is the approach
> that is usually used, I guess, but it would make the other list
> operators (for instance, concatenation) much more complex.

List concatenation is fairly complex in Joy.  consing is relatively simple.

> - "iepos" (Brent Kerby)

-Billy