Joy, Lambdas, Combinators, Procedures

[iepos@tunes.org]

As you say, this has turned into quite a fun discussion...

I'm going to do a bit of clipping in my reply...

> > a system might like to formalize as primitive expressions
> > the number literals 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 
> > strictly, this is not allowed in a purely applicative system since
> > it would require an infinite number of primitives. Instead, one
> > could take as primitives only the numbers 0 through 9 (and maybe
> > "ten"), and then refer to the other numbers using multiplication and
> > addition. 
> 
> Sorry, but as much as I like the theory you're bringing to the
> table, I really, really hate messing up a good language with theory.

I was a bit unclear on this: it is not my intent to apply such strict
restrictions to external programming languages of the system.
The purpose of that comment was to clarify my definition of
"purely applicative" which I've been using a lot throughout
this discussion. A practical system will probably use languages
that are not entirely purely applicative in this strict sense.

> Don't forget that the purpose of a programming language is to allow
> people to express things to the computer.  

Another thing I was not clear about: when I've said that I wanted
my system to be based on a purely applicative language, I meant
that _internally_ it would use a (nearly) purely applicative language.
When I've been talking about languages of the system, I think maybe
you've misunderstood me to be talking about external languages
that the user uses (there may have been some cases where this is
what I meant though)... But, incidentally, if I was a user wanting
to use my system, I would probably wouldn't mind the external language
being nearly purely applicative, also.

> Having a finite number of "primitives" is
> not required by any theory you've stated; it's simply an arbitrary
> restriction you've placed upon yourself.

This statement reveals a misunderstanding by what I mean by "primitives".
By a "primitive" of a language, I mean an expression of the language
which has a precise meaning that is not determined by the meaning
of its parts. If a language has a scheme of expressions with
similar meaning, then those expressions are not primitives
(by the definition of what I mean by "primitive").

With this definition of "primitive" in mind, the idea of a language
having an infinite number of primitives is quite bizarre. In general,
it would be impossible to understand sentences in such a language,
since the language would essentially have an infinitely large
vocabulary, which you could probably never grasp.

When I mean "primitive" in this sense, I'll try to say "word" from
now on, since I may use "primitive" in other ways sometimes.

> > Well, your "stack(--)" construct would then be much like a 
> > lambda construct of applicative systems (note that it requires the
> > use of variables like "a", "b", and "c"). This would probably cause 
> > complications in proof systems.
> 
> Not at all, because the pseudovariables would not intermingle at all with
> functionality.  It's nothing more than a new naming convention for a subset
> of the combinators, really.  The 'C' combinator under this system has the
> name 'ba' or 'stack:(ab--ba)'.  (In my original design and implementation
> under Pygmy Forth I accepted input of the simple form 'abc--cba' rather than
> requiring the 'stack:()' notation.)

I can see that you like to think of "ab--ba" as a word, just another
way of writing "swap", rather than as a complex expression formed
from "--".

If you only used this abbreviation for a few stack-operators
(i.e., if you renamed "dup" to "a--aa", "pop" to "a--", and a few
others), then it really would make little difference to the system.

On other hand (and this is the original point I was trying to get
across), if in general you accepted all expressions of the form "...--..."
in the system, then this would be quite a change to the system.
The system could no longer be implemented in the "switch-case"
way that I suspect it is, since there would be an infinite number
of primitives of the form "...--...". 

In other words, whereas now Joy has specific support for just a few
stack-operators like "swap" and "dup", if this new "--" notation were
adopted in general, then it would not be enough for Joy to support
just a few of the expressions of the form "...--..."; it would have
to support them all. This would likely be done in one of these two ways:

  1) by adding special support in the interpreter loop to handle
     execution of expressions of the form "...--...".
  2) by preprocessing the program, replacing expressions of the
     form "...--..." by equivalent expressions formed from
     just "dip", "swap", "dup", and "pop" (and possibly a few
     others).

I'm guessing you'd prefer the second approach (a textual preprocess
may not really be necessary; the replacement could happen as
part of the parse, if the system parses its text before
executing it; or, it could do the replacement at the last
second, when interpreting the expression); either way would
require significant modification to the system. But still,
it would not necessarily be bad.

I'm still quite interested in knowing of an "abstraction algorithm"
that could be used to rewrite "...--..." expressions using
just "dip", "swap", and such. You've hinted that "dip" will
be important, although surely other operators will also be needed.

Abstraction algorithms are quite interesting things to me...
There are probably several different algorithms that might
be used... For instance, "abc--cba" might be written either as

  swap [swap] dip swap

or as

  [swap] dip swap [swap] dip

Incidentally, that these two are the same corresponds to a fairly
fundamental Combinatory Axiom that

  C.BC.C = BC.C.BC

or in other words that

  BC(B(BC)C) = B(BC)(BC(BC))

> The reason I'm calling your grouping into question is complexity; I believe
> that your system has very important categories which you're ignoring.  
> For example, your primitive functions bear little resemblance in behavior to
> your primitive combinators.  Your functions simply use their parameters;
> your combinators have to select and choose parameters.

I'm not sure what you mean by "primitive functions" (combinators are
a kind of function); perhaps you are talking about my procedure
primitives like "get" and "put" (i.e., analogues of "scanf" and "printf").
These primitives are of a different sort than combinators, and probably
would be grouped together when presenting the system (actually,
they are not so different from combinators as I think you've
perceived; you've misunderstood how I plan to go about doing procedures;
in a separate post, I'll try again to explain how I plan on doing them).

> > The precise meaning of "combinator" may vary a bit among uses, but
> > calling all functions "combinators" is getting a bit nonstandard.
> 
> This is practically true for applicative languages, but breaks down almost
> completely for concatenative ones.  In such languages, ALL words (including
> so-called combinators and special forms) are actually functions from a stack
> to a stack.  

This is true (except for informal primitives like "put" and "get",
which can't really be modelled as just functions from stacks to stacks);
but, usually by a "combinator" in Joy, I am just referring to
things like "swap", "dup", "pop", and maybe "dip" and "concat"
and some others, but not "+", "-", "1", "2", and such.

This use of "combinator" with respect to Joy is a little vague;
but, in case it is not clear, in an applicative system, by
"combinator", I mean a function that takes some parameters
(through currying), and results in some application
of those parameters to each other (i.e., a "combination" of the
parameters). A few examples of combinators:

  - "f\f f": a function that takes a parameter "f" and results in "f f",
    the application of "f" to itself. (This is sometimes called
    the mockingbird combinator).
  - "x\y\x": a function that takes two parameters "x" and "y" (through
    currying) and results in "x". In other words, this combinator
    takes a parameter of "x", and results in a function that
    always returns "x". This is sometimes called the K combinator.
  - "x\y\z\ xz(yyy)(zx)". This is a weird combinator with no common
    name and seemingly little significance.

There are also of course lots of other interesting combinators
like B, C, W, and S...

> In addition, according to the foundational axioms of
> K-complexity theory, all functions can be built from a small set of specific
> combinators (I seem to recall S and K) combinators, 

It is true that the S and K combinators can be used alone to form all
other combinators, and even a bit larger class functions which I call
"pure functions", but to say that S and K alone can be used
to form _all_ functions is getting a bit silly. For instance,
S and K cannot be used to form the function of "fatherhood",
which given a person, yields his father. They also cannot be
used to form numeric functions like "+", "-", "*", and "/"
in the ordinary sense (although they can be used to form similar
functions that operate on Church Numerals or representations of
numbers).

> so all functions can therefore be regarded as combinators in any
> system (including yours).

Not so. But, this is true in a certain sense... there are interesting
ways in which pure functions can be used to emulate numbers,
propositions, and lists. It is conceivable that pure functions could be used to
represent even other things like people, pictures, sounds, and programs,
but this would be a bit weird, and I don't plan to do it in my
system.

> > But anyhow, that definitions and system dictionary were "not 
> > special" was not my main point; my main point (which you have
> > not contradicted) was that a special language construct is not
> > needed for definitions.
> 
> I have contradicted that; although it's true that no special syntax is
> needed (an obvious point proven many times over)

It is obvious that you have misunderstood what I meant by
"special language construct". By this, I meant a special
syntax, like Joy's "==". Surely you would not contradict me and
then immediately acknowledge that what I said was true.

> The fact that all of your combinators can be expressed in terms of a
> few simple combinators doesn't change the fact that all combinators --
> especially including those few ones -- require special parsing from
> the compiler.

I have admitted several times that I don't know of any techniques
for efficiently compiling programs expressed in the style I've
suggested (although I have hope that efficient techinques do
exist and that I will discover them at some point). I do know
of some inefficient techniques of interpreting them, anyway.

There's one thing somewhat relevant to this that I may not have made
clear yet... whereas many programming languages only provide
ways of representing programs, languages of the type I've described
will cleanly be able to represent other concepts, such as numbers,
propositions, lists, functions, as well as programs. I think
some enlightenment may result from comparing my language(s) to
human languages like English, rather than to programming langauges.

Of course, languages in my system will probably not really
have the expressiveness of English (at least, not initially), nor will
they have the vagueness or syntactic complexity of English. But, as it
is possible in English to refer to, say, the number "two", so will it
be possible to refer to the number two in a language in my system. 
A purely applicative language could conceivably be used for purposes other
than programming; it could be used for human communication
(this would be unusual), or it could be used as a device
for a formal logic system, without involving automatic computers.

> > > Speaking of immediate execution, how would your system 
> > > handle Forth-like
> > > metaprogramming?  Does the code have full access to all of 
> > > the unparsed
> > > source?
> 
> > Probably yes... As an example, if a user has been working on writing
> > a complicated program, he would probably have given a name to
> > a field for the program's text. Conceivably, this name could
> > occur within the text itself, so that the program could refer
> > to its own text cleanly. 
> 
> This is not Forth-like; in fact, it's a superset of Forth's capabilities
> which will force you to re-parse the file every time it's used.  That's
> pretty brutal. 

I do not see how it requires me to re-parse the file every time
it is used. Perhaps you mean "every time it changes"; I don't 
know...

> interpreter hasn't touched yet.  I don't believe that this is even possible
> with your system; all text has to be parsed before anything can be
> evaluated.

I don't have a system. Neither do I have my mind set on any particular
technique for interpreting text that user's type in. Anyway, it
doesn't really take very long to parse text, so this doesn't
really seem to matter too much to me (well, perhaps there might one
time be a huge specification file; I suppose if a user changed
one bit in such a huge file, it might be worth it if the system
can find a way to reparse just a part of it without reparsing the
whole thing; this is something I have not ruled out).

> Your system doesn't currently have any
> obvious ways to reach inside a completely applied function and modify it,
> but you can play with the variables about to be passed to a function.  (In
> this respect, Joy is clearly _much_ more expressive, since manipulating a
> quoted program as a list allows arbitrary modification.)

This is an interesting comment. I've thought using adding a
"reification" primitive (as Fare calls it) which is a function
that given a thing, yields a data-structure that represents that thing;
this would allow "arbitrary manipulation". I'm not sure that I would
really need to use this though. (by the way, since there may be several
ways of expressing things in a language, one might make such a
"reification" primitive as yielding a set of expressions, rather
than a particular one; if one did this, one would probably also need
a "pick" procedure that one could use to get the system to
arbitrarily pick a member of a set; but... I need to clarify
on how procedures will be dealt with)

> > On the other side of metaprogramming, languages in the system will
> > probably provide ways of referring to the systems own
> > low-level structures, including, for instance, procedures for
> > peeking and poking at the system's raw memory, or doing raw
> > I/O. Using these procedures, the system could change the
> > way it works (it could even change itself so that it did not
> > work at all).
> 
> Until the theory is worked out, it can be nice to have the
> raw capability, even if we know that someday it'll go away.

I always want to have raw capability. I want full power over my system.
But, of course it might be nice if the system asked for confirmation
(involving authentication to make sure it is really me and not the
imposter who stole my keyboard) before doing something it thought
might be dangerous. But this would be quite nice feature that I
don't expect to implement anytime soon; it would naturally be the
job of the shell more than anything else.

> I have to agree with you that definitions don't _have_ to be included in
> either of our systems, though.  It would be a bear to work with, but it
> would be *possible*.

Yeah, as an example, one could look at Unlambda. It doesn't have
definitions, and it is a bear to work with, as you say, probably
due to the fact that it doesn't allow definitions.

The next issue brought up, how my system will deal with
procedures, I'll reply to in a separate post...

By the way, if anybody else reads these posts and has something
interesting to say, feel free to chime in.

- "iepos" (Brent Kerby)