Joy, Lambdas, Combinators, Procedures

[iepos@tunes.org]

This is the third part of my reply to that message you sent
a while back... I have your two more recent messages and
will reply to them too, sometime...

this message is still way too long, so i'll skip through some things
(I read them of course, but just do not have time to reply to them),
but I'll at least try to address your direct questions.

> > I still do not quite get exactly what you mean by "parameter counts".
> 
> A function can't be 'executed' in any way I know of until all of its
> parameters are filled (otherwise its value is undefined).  Thus you have to
> keep count of parameters.  This is more complicated than it might seem; you
> can't simply trace through the code and keep a type stack, as you can with
> Joy; you have to parse the entire source and consider a potentially huge
> tree of parameters.
> 
> For example, in your language, is this an error?
> 
> @@@ackermann 4 5 6
> 
> (Ackermann is a two-parameter function.)

That would be an expression that would probably have no denotation
under the language (although it is "well-formed", in a certain sense).
Any expression involving this expression would also have no denotation.
I guess you could say that it is an error. If you fed this expression (or an
expression involving this expression) to an interpreter,
it would probably complain that the expression does not denote
a procedure (the interpreter can only execute expressions
that denote procedures).

> > Not sure what you mean by "select" combinator or "runtime" 
> > combinators.
> 
> A 'select' combinator is an example of a runtime combinator.  Think of the
> Forth word 'PICK', which takes an integer "n" and pushes onto the stack the
> n-th item.  Joy has no such combinator, although it would be easy enough to
> build one by using a loop and 'dip'.  The point is that sometimes you don't
> know which item to take until runtime.

Ahh... this is interesting. If I understand what you mean by "select",
then in my system an analogous "select" would have these properties
(these are just examples):

  select 2 f x y z  ==  f z x y z
  select 1 f x y z  ==  f y x y z
  select 0 f x y z  ==  f x x y z

The last two properties could be written more simply as:

  select 1 f x y    ==  f y x y
  select 0 f x      ==  f x x

Essentially, applying a "select n" to a function of so-many parameters
yield a similar function but with a copy of its "nth" parameter 
inserted at the front.

It might be wondered whether such a "select" could be constructed
in my system... it is certain at least that each specific "select n" can
be constructed (since they are all combinators). For instance,
"select 0" is simply "W" (this is analogous to a "0 select" of
Joy being the same as just "dup"). Also, it turns out that
"select 1" is the same as "BW . C" or in other words "B(BW)C".

Now, the question of whether a fully general "select" (i.e.,
a function that takes a natural number and yields the corresponding
"select" combinator) could be constructed is a bit more difficult...
the answer depends on what primitives are available for
number-manipulation. After a bit of study, I see that in general,
"select n" can be constructed as

  B (iterate n B W) (foldl n C)

This depends on two other series, "iterate" and "foldl", as
I've called them. These two series would probably be easy enough
to construct in any decent number system. They have the
generating rules:

  iterate 0     == KI
  iterate (n+1) == SB (iterate n)

  foldl 0       == KI
  foldl (n+1)   == (S(CB) . BB) (foldl n)

I suspect that there might be a simpler way of generating "foldl"...
Anyway, then, using a "primrec" one could directly form these series as

  iterate  ==  primrec (K(SB)) (KI)
  foldl    ==  primrec (K(S(CB) . BB)) (KI)

By the way, the series "n\ foldl n C" (which was used in forming
the series for "select" in my definition) is itself interesting;
it is quite similar to select, except that it _moves_ the
parameter (so to speak) instead of copying it. The way in
which I've formed "select" works essentially by duplicating
the parameter and then moving the copy (so to speak).

> > I don't
> > see how it would be such a headache to add a new combinator in
> > my type of system... all combinators can be constructed from just
> > a few (for instance, "B", "C", "W", and "K"), so if the system could
> > handle procedures written using those few combinators, then it could
> > handle procedures written using other ones, by just replacing
> > occurences of the new ones by their definitions in terms of 
> > the old ones. 
> 
> Look up K-complexity on the web -- it's the theory of reducing functions to
> just a few combinators.  (Your compiler could theoretically work that way.)
> The problem is that it's a very hard task; 

Hmm... I'm not familiar with "K-complexity", but this is incorrect,
I think. It is really quite an easy task to rewrite any combinator
(expressed using lambdas) as a combination of, say, the
"I", "B", "C", "S", and "K" combinators. There is a straightforward
algorithm for doing it; I'm not sure what its order is, but in
practice (at least for relatively simple combinators that people might
want to deal with), it takes practically no time at all to
carry it out... I won't take the time here to detail
how exactly the algorithm works (this is done on my web site,
though, under the section, "Lambda Construct and Completeness"),
but I will just give an example of how the combinator

  f\g\h\x\ f(gx(hx))

can be written with "I", "B", "C", and "S", using the algorithm...

  f\g\h\x\ f(gx(hx))
  f\g\h\ Bf(Sgh)
  f\g\ B(Bf)(Sg)
  f\ B(B(Bf))S
  C(BB(BBB))S

You can verify that this combinator, "C(BB(BBB))S" is the same as
the original by checking to see that when applied to the four
parameters to get the right answer:

  C(BB(BBB))Sfghx
  BB(BBB)fSghx          by C's rewrite rule
  B(BBBf)Sghx           by B's rewrite rule
  B(B(Bf))Sghx          by B's rewrite rule
  B(Bf)(Sg)hx           by B's rewrite rule
  Bf(Sgh)x              by B's rewrite rule
  f(Sghx)               by B's rewrite rule
  f(gx(hx))             by S's rewrite rule

Anyway, this just shows that it is a fairly easy mechanical task
to rewrite lambda-expressions using the combinators
"I", "B", "C", and "S" (and occasionally "K", when dealing with
functions that ignore some of their parameters).

> > > An applicative system only makes sense as a declarative system.  A
> > > concatenative system also makes sense as an imperative one.
> 
> > I'm not sure what precisely you mean by "declarative" and 
> > "imperative",
> 
> I've never heard anyone express misunderstanding of that particular
> distinction before; it's one of the most common and deep-running
> distinctions in computer languages.  Could you clarify?

Well, I guess usually "imperative" is used to describe systems
in which the "command" or "procedure" play a fundamental role,
whereas "declarative" is used to describe systems where the
"statement" (expression of information) plays a fundamental role.

If this is what you meant, then I guess I would say that
my system is either both "imperative" and "declarative" or
neither one; procedures will play an important role in the system,
and statements will also (when I begin working on the logic
part of the system), but neither the "procedure" or "statement"
has extra-special status in the system.

Actually, it has been a thought in my head that the distinction
between "statements" and "commands" is somewhat artificial...
Commands can be re-expressed as statements, and vice versa.
For instance, the English command,

  "Go get me something to drink."

could be re-expressed as a statement (with little or no change
in meaning) as

  "I want you to get me something to drink."

Similarly, the statement,

  "Two plus two equals four."

could be expressed as a command as

  "Note that two plus two equals four."

> > However, even though the language does
> > not have special constructs for dealing with them [combinators], they might
> > be treated quite specially by the execution system; in this
> > sense, as you have said, they are not so "ordinary".
> 
> How can the language _avoid_ having special constructs for combinators?  I
> don't have a clue how this can be done.  You have to *at least* rewrite all
> combinators down to the basis set (the combinators from which everything
> else is constructed in your theory), and then you have to have special
> parsing support for each of the basis combinators.

I have indeed gotten away without having special parsing support for
combinators (although this doesn't seem like an amazing feat
to me). Here is an excerpt from the parser of my system:

  expr *toexpr(){
    if(str[siz]=='@'){
      expr *x,*y;

      siz++;
      x=toexpr();
      y=toexpr();
      if(x==NULL || y==NULL) return NULL;
      else return (expr *)App(x,y);
    }else return name_toexpr(toprim());
  }

Basically, it checks to see if the string starts with a '@';
if so, it skips over it and then descends into recursion;
otherwise, if it doesn't start with '@', then the expression
must be a word, in which case "toprim()" is used to parse it:

  char *toprim(){
    char *s=NULL;
    int i=0;
    int max=0;

    for(;;){
      char c=str[siz];

      if(i>=max){
        s=mem_reget(max,max*2+1,s);
        max=max*2+1;
      }

      if(c=='.'){
        s[i]=0;
        siz++;
        return s;
      }else if(c==0 || c==EOF){
        return NULL;
      }else{
        s[i]=c;
        i++;
        siz++;
      }
    }
  }

[sudden realization that I could have just used strchr()]...
This is a messy way of reading the word; words are terminated
by "." in the system. Anyway, my point is that the parser
does not specially mention any combinators; combinators are
expressed using just ordinary words. Of course, certain
combinators are mentioned specially in other parts of the system.

By the way... here is an example expression that the parser
recognizes:

  @@def."Y".@@B.M.@@C.B.M.

The string literal "Y" is treated as if it was a word by the parser,
although it is handled a bit specially by "name_toexpr"
(which usually does a dictionary-lookup). If I were to rewrite
the system, I would probably make this kind of syntax sugar
be handled by the parser instead, but it doesn't really matter
I guess.

By the way, there is an actual system...
it can be found at http://www.tunes.org/~iepos/clip/clip-0.3.6.tar.gz

It is kind of weird and doesn't do very much right now.
When it starts, it runs the list of procedures in the "boot" file
(each line is parsed and executed before the next is parsed;
this is so that if one line defines a new word, then the next lines
can make use of the new word). Currently, all that "boot" does
print a little column of "o"s down the screen (using recursion),
and installs a hook so that when you press a key, the representation
of the key appears on a certain place on the screen.

There are several things about the system that I'm not really
satisfied with (aside from the fact that it is incomplete and slow)...
but I won't go into that now...

> Let's suppose that your system uses functions and three combinators: K, D,
> and C (I don't expect that these are the ones actually needed, I don't
> remember that).  Your system will require:
> 
>  - atomic functions and types (assuming that you don't go "whole horse" and
> just define everything in terms of the basic combinators, which is certainly
> possible but VERY expensive)

types... types are interesting things that I've been thinking about
lately... my current system is rather untyped. The main ability
that one would associate with "typed systems", I suppose, is the
ability to arbitrarily construct restricted functions, i.e.
functions that only meaningful when applied to a certain class
of parameters.

For instance, in my system, one might want to construct a
"procedure-concatenation" function; currently, there is no way
to do this exactly in my system. One could use the B combinator,
which acts as concatenation when applied to two procedures; but,
the B combinator is also meaningful when applied to things other
than procedures, so it does not really cut it as a 
"procedure-concatenation" function.

The primitive this ability boils down to is, I think, a primitive
which i'll call "restrict", with this property:

  "restrict f x" is the same as "x", as long as "f x" is true;
  otherwise, "restrict f x" is meaningless.

For example, "restrict number 2" is analagous to the English
expression "the number 2"; it is the same as just "2", since
"2" is a number. However, "restrict number Output" would be
a meaningless expression, analagous to the English "the number Output",
which is meaningless because Output is not a number.

Using "restrict" (and certain combinators), it would be possible
(using some combinators) to form functions with arbitrarily restricted
domains and ranges. This could be useful.

By the way, I suspect that a "restrict" could actually be formed
in various ways from other primitives... but I won't go into that...

> >   1) In a purely-applicative system of the kind I've described,
> >      it is always possible to replace a sub-expression with
> >      one of equivalent meaning, while this is not the case
> >      in the Joy system, because of Joy's heavy dependence on
> >      a quotation construct. To illustrate, suppose in Joy one
> >      had a program
> 
> Not true -- as you admit below, the quotation construct has little to do
> with it.  The problem is caused by being able to treat quotations as lists.
> If that were not possible, or if it were restricted in certain ways, there
> would be no problem even in this circumstance.

Right, it looks like you're not denying that there is this problem
with Joy... you're just denying that it stems from the quotation
construct... the solution you propose (restricting the ability
to treat quotations as lists) is one that the author of Joy has
considered; it has the disadvantage that you would then need
to have separate constructs for lists (if you still want them).
But, as far as I can see, it does look like a remedy that could work.

> >        foo (plus 0)
> >      could be freely rewritten as
> >        foo I
> 
> >      regardless of the structure of "foo", if the system had
> >      realized that the expression "plus 0" means the same 
> > thing as "I".
> 
> And the exactly analogous expression "0 plus foo" could be freely rewritten
> as "foo" in Joy.

Hmm... no, my "foo (plus 0)" is not well analagous with Joy's
"0 plus foo". The Joy analogue would be "[0 plus] foo".

Let me explain why I think this way... Suppose instead that
we have "WB (plus 1)"... "WB" is a higher-order function that
takes a function, in this case "plus 1" (the add-one function),
and yields the function's composition of itself; in this case,
that will be "plus 2".

Now, could you see that a Joy analogue of "WB (plus 1)" would
be "[1 plus] dotwice", where "dotwice" is a combinator that
takes a quoted program and does that program twice
(such a "dotwice" could be formed as "dup [i] dip i", I think).
In contrast, I cannot think of any "foo" such that "WB (plus 1)"
would be analagous to "1 plus foo" of Joy.

Back to the original example... the Joy "0 plus foo" is a program
that adds zero and then does "foo" to the result. It would be
analagous to "B foo (plus 0)", the composition of "foo" with add-zero...
By the way, "B foo (plus 0)" could probably be rewritten in my
system as "B foo I" and then just "foo".

> Note that there wasn't even a need for an 'id' placeholder.

In the truely analagous example in a applicative system (just given),
there is no need for an "I" there either.

> Entirely correct.  It _does_ cause an impediment; the interesting thing is
> that it itself (treating programs as lists) is a form of automated reasoning
> about programs.  This suggests that the problem it causes _might_ be
> fundamental, one of the classic Godel incompleteness problems (as phrased
> for concatenative languages, of course).  In other words, reasoning about
> programs may be easy; but reasoning about programs which are themselves
> rasoning about programs is not easy.

This is an interesting thought... But, I'm not sure that this
(the problem of not being able to substitute equivalent expressions
within quotations) is really a fundamental problem; my purely
applicative system does not seem to have it, and you've given
a remedy that could possibly rid a Joy-style system of it.

> >   2) Many fundamental equivalences of Joy programs that one
> >      might like to show require restrictions, while
> >      similar equivalences of purely-applicative expressions
> >      can be taken unrestrained. Specifically, one might
> >      like to think upon seeing a Joy program of the form
> 
> This is _really_ heavily unfair.  Those things aren't "fundamental
> equivalences"; they're rewriting rules.  Rewriting rules of that nature are
> a thing used by syntax-based languages, and you honestly can't expect them
> to apply to a non-syntax based one.  The fact that some of them do anyhow is
> almost amazing.

Hmm... I'm not sure what you mean by a "non-syntax based" langauge.
All languages (including Joy) have a syntax, do they not?
>From this comment, I guess I can see that you just do not
value too highly the ability to do "textual reasoning" in
a language (i.e., reasoning which is achieved by changing expressions
around mechanically, but without paying special attention
to their meaning).

Yet, textual reasoning (or "formal reasoning" as it is usually
called) is something that I find quite interesting; it seems to me
to be a very good quality of a language if it can be easily
textually-reasoned upon. 
 
> The actual rewriting rules Joy has are very simple; they state things like:
> 
> if "t == a b c" and "d e a b c f g == z y x" then "d t f g == z y x".  In
> other words, direct text replacement is reasonable.

Hmm... I'm guessing that that "e" was not supposed to be in the
second one, or something, but I get what you are saying...
There is some textual reasoning that can be done with Joy,
and one of the principles (which you've just illustrated) is that if

   x

is replacable by

   y

then it also holds that

   a x b

is replacable by

   a y b

(this holds for all well-formed Joy expressions "x", "y", "a", and "b",
and by "x is replacable by y" I mean "x can be textually replaced by 
y in any program and the resulting program will make the system do
the same thing as before").

> >      The analagous equivalence in a purely-applicative system
> >      is that
> 
> >        @@@C f x y
> >      can be rewritten as
> >        @@f y x
> >      This can be accepted without restraint for all expressions
> >      "f", "x", and "y" of the system.
> 
> That's because combinators in your system have syntactic effect.  In order
> to do that, I'd have to define:
> 
>  C == dip [swap] i;
> 
>  [y] [x] [f] C == [x] [y] f

Hmm... I suppose you meant "C == [swap] dip i"...
but, yes I suppose you could then accept "[y] [x] [f] C == [x] [y] f"
unrestrained. But, I don't think this principle is analagous
to the "C f x y = f y x", because the former would almost never
be used at all in a Joy system at all, while the latter would be
very commonly used in my system. On the other hand, a reasoning
system in Joy would probably commonly find itself reasoning
that "x y swap" is the same as "y x", but it could only realize
this once it verified that "x" and "y" were simple programs that
just pushed a thing onto the stack with no other effect;
this might not be such an awful problem, since a reasoning system
would probably want for other purposes information on how many
items a program might push onto the stack.

> > But, if you can see any awful problems with the approach
> > I'd still like to hear, of course.
> 
> The nastiest one I've seen is the lack of ability to *do* things in the
> language.  You have to add another language on top.

That's sort of right. In my system, one would not
"do things in the language". Rather, one would use the language
to express things that one wants done. This is just a matter
of interpretation though, and doesn't really matter at all...
You could use my system to get computers to do things, just
as you could in other systems. And, it is not necessary
to "add another language on top" (this reflects a misunderstanding
of my procedure system which I think may have been cleared up
now).

> I also suspect that even the strength of your functional language,
> functions, will be very hard to read and maintain without automated help.
> APL functions don't use many combinators, but APL programmers recommend
> deleting the program and rewriting it based on the comments rather than
> trying to understand the program.  Forth programmers don't do that.

confession... in working in my CLIP system, on several occasions I've
found myself deleting lines and rewriting them after they didn't
work on the first try, rather than trying to understand them :-)
but, i think this reflects my own unfamiliarity with the system
and also the inconvenience of the system's current syntax.

> -Billy

- iepos ("Brent Kerby")