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

[iepos@tunes.org]

It took a while to reply, but I'm still here...

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

Ahh... I'm not sure that my system has an analogue of a procedure that
simply "computes" the square of 129... Perhaps you could use
"T (square 129)", which would push the square of 129 onto "the stack";
however, it is not guaranteed to be kept in the system's evaluated form...
it could be kept on the stack as just "square 129"... In general,
the system would decide for itself when and how completely to evaluate
its expressions.

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

Yes, you could do it that way, if you had a procedure version of
"square", which took a continuation parameter in addition to the number.
Such a procedurized "square" actually can be constructed from the
ordinary "square", specifically, as "CB square"; if you told
the system to do "(CB square) stop 129", the command would reduce to:

  C B square stop 129
  B stop square 129     [C]
  stop (square 129)     [B]

This is how I would expect your procedurized square to work;
it goes on to do the continuation "stop" but with the result of
the squaring passed as a parameter.

The reverse of this is also possible; that is, if one had "CB square",
as a primitive, it would be possible to retrieve the ordinary squaring
function, specifically, as "(CB square) I"... you just give the
continuation to be the identity. This reduces by "C" to
"B I square", and thus just "square" (in general, "B I foo", the
composition of the identity with "foo", is the same as just "foo",
at least if "foo" is a function).

By the way, after some thought, I've come to like Joy-styled systems
more than before... there is one odd thing about my system that
bothers me: I'd planned on frequently using functions like "square"
(that do not take continuation parameters); however, the question
arises of how to deal with similar (non-procedural) functions that
have multiple results... for instance, how might I formalize a
"divmod" function, that takes a couple numbers and yields both 
the result of their division and the remainder? 

The best way I can think of to formalize it is as a function
that takes three parameters: a "continuation" function (which the
two results will be applied to), and the two numbers. That is,
for example, "divmod foo 3 13" would yield "foo 4 1" (since
"3" goes into "13" four times with one leftover). Note that
"foo" does not need to be a procedure; it just has to be some
binary function... for example, "divmod add" (where "add" is not
a procedure, but just a binary function that takes two numbers
and yields their sum) would be a function that takes two numbers
and yields the sum of their quotient and remainder.

The problem with this approach is that there is now a dissimilarity
between functions that have multiple results and functions that
have a single result. Functions that have multiple results take
a continuation parameter, while functions with single results do
not. Of course, it is possible to formalize single-resulting
functions using a continuation parameter, as was done above with
"square"; this seems to me to be an interesting approach.
If all functions took a continuation parameter, then the system
would be brought even closer to Joy.

Functions that take a continuation parameter as their first parameter
I will call "regular" (this is a generalization of the usual terminology
of "regular combinators"). If one wanted all functions in my system
to be regular, there is a problem one would encounter: it is
possible to form irregular functions out of regular ones...
For instance, "(CB square)I" is an irregular function (the numerical
function of squaring), even though both "CB square" and "I" are
regular.

Hmm, but, if you take two regular functions and compose them,
guess what? the result is always a regular function. And, if
you take "T" and apply to something, the result is always a
regular function. So... how about we give up unrestrained
application, and take composition and application of "T" as
primitive operations. If this is done, then we'd end up with
something very much like Joy. Actually, quotation (application of "T")
would not behave quite the same way as in the original Joy system;
it would behave in a much better way, I think, a way which would
allow unrestained substitution of equivalent expressions even
within quotation; yet, this comes with some pitfalls,
which I'll mention later...

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

Ahh... I should have explained this... I meant the distinction
between "square" and "CB square" of my system... "CB square" is the
associated procedure of "square" in my system, yet it is certainly
distinct from "square". By the way, "CB square" could also be written
"T square . B"... As I mentioned above, there is some interest
in a system where something like "CB square" is expressible but
"square" is not...

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

Maybe, but it does not seem to be a problem to me.
It seems analagous to what happens when one uses a Joy primitive
like "get", which pushes a string onto the stack; usually,
things are pushed onto the stack explicitly; does it seem
odd that "get" pushes something onto the stack "implicitly"?

When a user uses "get" he knows it is going to push something
on the stack (as it is specified to do), so I don't really see how
the push is implicit at all. Likewise, if someone uses an
"Input" primitive in my system, he knows that the continuation
is going to be applied to the result of the input...

> > > Another possible example would be
> > >
> > > [5 swap / Output] Input.
> >
> > I'm not sure what is meant by "/" here...
> 
> Division.  What would you have used?

Oh... I see... I was reading "/" as an infix operator.
I get it now...

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

Right... I meant "simple" in quite an untechnical sense... 
by the way, the purity of procedures would be something
quite important for a system to keep track of, I suspect; if the system
knows that a procedure is pure and knows what will be on the stack
when it is executed, then it may be able to execute it ahead of time
(or behind time, in Lazy style, perhaps) without being explicitly
told to.

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

I see your point... This is mostly just a funny feature of English,
though, of course; in a formal language, there would be no confusion
in mentioning "Bill" twice. I think my later example with the 
keyboard lights may have better illustrated my original point
(that there is use in talking about abstract physical things
rather than specific states of such things, as in the num-lock light
on my keyboard). 

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

Ahh... I see... It is possible to view your "Rinse" procedure as
a pure procedure, which has no effect (except on the stack, of course),
while the same is not true of mine.

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

Types... this reminds me of the interesting type system that the
author of Joy (Manfred von Thun) developed... In his system your
"Rinse" would be said to be of type

  Dish -> Dish

while mine would just be

  Dish ->

This type system doesn't give a way to express the purity of
the procedures, but it could be easily extended to do so, I think...
As another example, the type of "+" would be

  Int Int -> Int

In general, there are primitive types like "Dish" and "Int"; then,
other types are constructed using type concatenation, type quotation,
in addition to "->". 

There is an alternative to "->"... "->" could be eliminated, I think,
if one had instead a unary type constructor, which I'll call "-", which
takes a type, and yields the "opposite" type (if a type pushes
something onto the stack, then the opposite type will pop something
off the stack, and vice-versa)... Then, the type of "+" could be
written

  -Int -Int Int

or perhaps

  -(Int Int) Int

Anyway, this is tentative... I haven't really thought too much
about using "-", or about type systems at all...

It would be possible to make types first-class... a type could
be thought of as a pure procedure which takes a thing off the
stack, and pushes a proposition (True or False) indicating
whether the popped thing was a member or not. But, maybe this would
not be a good idea... I'm not sure... Type systems are usually
kept separate from the rest of the system.

And, mentioning "-" reminded me of something else... One interesting
primitive one could add to the system is an "undo" primitive...
Such a primitive would take a quoted program off the stack, and
would "undo" the quoted program. This probably seems like a
wild idea; "undo" is usually thought of as a fancy feature often added
to text editors and things... to treat it as a fundamental primitive
of a system is getting weird... it would probably make the system
impossible to fully implement.

But, there are interesting things about "undo"... It seems to be
the analogue of the "inverter" primitive that I wanted in my
applicative system. Using it in conjunction with the Church Numbers
(those "doonce", "dotwice", "dothrice", and such, that I mentioned
earlier), it would be possible to form all kinds of interesting
Church numbers (including negative, fractional, irrational, imaginary,
etc.). Actually, "undo" might itself be considered the Church Number
for negative one.

Then, as an example, one could form a "dohalf" primitive, that
takes a quoted program and executes it a "half" a time:

  [[dotwice] cons] undo

I think that is right... and, the "dotwice", "dothrice", and such
I used earlier took a quotation and resulted in a quotation;
as I use them now, they do not result in a quotation, but rather
just execute the quotation they are given so many times...
this means I would need to reform the primitives I'd given
for addition, multiplication, and exponentiation...

Anyway, using "undo", it would be possible to form primitives
for subtraction and division ... for instance,

  [5 add] undo
  
would be a function that subtracts 5... I guess then that
 
  [add] cons undo

would be a subtraction program... Division could be formed
using "undo" from multiplication in a similar way... and
then roots and logarithms from exponentiation...

Church numbers are fun, fun, fun...
Unfortunately, I'm not sure how any of this would actually be implemented.
And, of course, some programs do not make sense to be run a negative
number of times, or a fractional or imaginary number of times
(although some do), or some might make sense in multiple ways...
Not sure how a system would deal with this... 
  
> > 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.

Now seems like a good time to share the idea I had about altering
the quotation construct of Joy to make it better correspond to
application of "T"... (I don't claim that this enhancement
would make Joy better; in fact, looking back, I think it would make
it worse, although it does inspire a few other thoughts)

The basic idea is to make "[foo]" denote the program of pushing
the program "foo" onto the stack; then, for instance, "[add]" and
"[swap add]" are equivalent programs, since each pushes the "adding"
program onto the stack. And... if you told the mythical system to
do "[add] [swap add] =", it would push "True" onto the stack
(although it might not realize it, if it is acting in a lazy style).

To emphasize, in my mythical modified Joy system, "[add]" and "[swap add]"
mean the same thing to the system and can be replaced by each other.
A consequence of doing it this way is that programs cannot directly
be introspected; however, this could be fixed by adding a "reify"
primitive. 

Now, there is the issue of lists... how will lists be represented,
now that quoted programs no longer have introspection? My answer
is that you do not need lists; just push all the elements directly
onto the stack (perhaps with an additional integer, indicating
how many there are). Then, make all the "list" operators
(such as "reverse", "concat", and "cons") operate on the bare
stack. By the way, if for some reason you really needed to manipulate
all the elements as a single beast, then you could use a quoted program
that pushes the elements onto the stack.

By the way, this talk of pushing lots of stuff onto the stack reminded
me of Henry Baker's "The Forth Shall be First", which I was reading
again a bit ago... he really seems to advocate "linear" implementations,
which do not use pointers and garbage collecting, but instead
stuff all their data directly on the stack, which is popped off
after it is used (in the most extreme case, there is a
stack with the processor's pending instructions on it, and even the
instructions are popped away after they are executed)... this is an
interesting idea, which I'd never considered before... it
neccessitates a more careful programming style, though... one must
be careful not to pass huge data structures to programs when they only need
a small piece (the penalty being an big expensive memcpy, assuming
that the rest of the data structure was needed elsewhere, and
was copied with "dup"). 

Of course, a general "linear" system would still need some heap
management (although it looks as though one really could do without
garbage collection); a good system will probably need to support
(pseudo-)concurrent execution of threads, each thread having its
own stack, and thus someone would need to decide which thread uses
which memory for its stack... and, which space a thread uses may
need to move around from time to time, to prevent trampling on some other
thread's stack space...

Also, there would need to be some way of threads coordinating with
each other... in my system, I had thought of using Fields...
new fields could be constructed with a "new" primitive, and then
they coulded be fetched or stored using "get" and "set" primitives
(like the "@" and "!" of FORTH)... multiple threads could use
the same fields... however, I'm not convinced that this is the
best way; it actually seems to be not a very good way at all,
considering the synchronization issues. In a linear system, it may
also tend to cause wasteful moving around of data structures 
(from a thread's stack, to a field, and then to another thread's stack).

Another option is to have some direct primitives by which one
can transfer items from one thread's stack to another... one
would need to have been explicitly set to read and the other 
explicitly set to write (so that items would never get pushed
onto a thread's stack by another while it was in the middle of doing
something else)... Anyway, this is just another tentative idea...
By the way, in a nice system, I would probably still like to
have fields... they just don't seem to be good low-level primitives
for an implementation... fields could probably be constructed
using this stack-transfering primitive, by making a thread for
each field, a thread that has the field's value on its stack,
and which waits for some signal (to fetch or store), at which
point it would either read in a replacement value for the
stack or else write a copy to some other thread...

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

Exactly. Ahh... we're talking again about my applicative system...
I'm still interested in it, although I'm now more interested
in implementing a refinement of the Joy system than in implementing
that purely applicative system... In a bit I'll mention some
refinements I have in mind...

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

Sounds like a good idea; before, I used "procedure completion" to
name what I now call a "command", but now we have "command",
so we might as well use "procedure completion" for this...

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

The continuation taken may sometimes be a command (if the procedure
has no results), or it may be a function onto a command (if
the procedure has some results). In our new terminology,
a function (possibly of many arguments, through currying) onto a command
is a "completion"; so, "continuation" is synonymous with "completion"
and a procedure is just a function from a completion to a completion. 

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

Right.

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

For procedures with exactly one result, this is right: the continuation
must be a completion with exactly one parameter unfilled (i.e.,
the continuation must be a function onto a command). In general,
the continuation taken by a procedure is just a completion,
with the of parameters unfilled reflecting the number of results
of the procedure.

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

I'm a bit confused. What I said was not really a textual rule, and
I was talking about my system, not 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!)

The "@" indicates that you are talking about my system, I think...
Yet neither "@plus x y" nor "3 4" are well-formed expressions
of my system... 

There is one thing that I think may be relevant to this though...
It is not a general rule that "x . y . C" can be replaced by
"y . x", although this does hold if "x" and "y" are pure procedures
that only push a single value onto the stack.

For instance, it is correct to rewrite 

  T 2 . T 3 . C

as

  T 3 . T 2

But, it is incorrect to rewrite

  T 2 . (T 3 . T 4) . C

as

  (T 3 . T 4) . T 2 . C

because "T 3 . T 4" is not a pure procedure that pushes just one
value onto "the stack" (instead, it pushes two values).

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

Yes... this is right; this is a procedure which takes a continuation
"f" and does "putxy f 4 3".

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

Right... in my system there one does not make functions with multiple
returns, but one can make procedures (including pure procedures)
with multiple returns... This is what you have done; "T x . T y"
is a pure procedure that returns "x" and "y". More literally,
it is a function that takes a continuation "f" and yields
"f y x".

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

Ahh... how about this: a program as a bunch of opcodes on the stack,
followed by an integer telling how many there are. Of course, this
would mean that when you deal with quoted programs, it is not
enough to juggle one stack item; you have to juggle lots of them
(except in the case of the empty program)... that's okay though;

I'm not sure about this ... dumping lots of things onto the stack
instead of dumping just a "list" of such things. I'm pretty sure
that if I implemented a program to push a "list" of things
onto the stack, I would implement it by having it just dump all
of its elements... but maybe there should be a distinction at a
high level (between a program that pushes a "list" of things and 
a program that just pushes all the things)...

What do you think... ?

> > - "iepos" (Brent Kerby)
> 
> -Billy

- "iepos" (Brent Kerby)