Joy, Lambdas, Combinators, Procedures

[btanksley@hifn.com]

From: iepos@tunes.org [mailto:iepos@tunes.org]

> > It is interesting, though, that your language can express 
> > "overbound"
> > functions.  I don't understand what that could mean to the 
> > function -- do
> > you have any ideas?  If we can come up with a theoretical functional
> > meaning, perhaps we can make sense of them procedurally as well.

> > In general, currying takes a function of n variables and a 
> > parameter, and
> > returns a function of n-1 variables.  I don't see how you 
> > can get away with
> > disregarding the terminating condition: when n=0, currying 
> > is impossible.

> In general, this is true (by "currying", I suppose you mean just
> "application")...

No, I mean precisely "currying" -- unless you're aware of some definition
I'm not.  "Application" is a very general term; "currying" specifically
refers to applying one parameter at a time.  Even C is applicative.

> But, this does not really hold in all cases,
> when higher-order functions are involved. For instance, the "B"
> combinator may be thought of as a three-parameter function;
> thus, you'd suppose that when you applied it to a parameter, you'd
> get a two-parameter function. But, if you apply "B" to, say, 
> "B" itself,
> you'll end up with a four-parameter function (although it could also
> be thought of as a two-parameter function that yields a two-parameter
> function, or a one-parameter one that yields a three-parameter one):

> In general, when you apply "B" to a function of order "n" (meaning
> a function that takes "n" parameters), you end up with a function of
> order "n + 1".

I'm confused now.  This seems to violate the definition of currying.  I
suppose that something magic is happening inside of 'B'; it's very easy to
describe (and makes complete sense), but I don't see how it works formally.

It's quite simple -- 'B' applies its third parameter to its second, which is
applied to its first.  In this case, the first parameter is expecting more
than one parameter, so when it's applied it's still hungry.

This is very interesting, in a sense.  Functions which are applied inside of
combinators (instead of explicitly with an @ sign) have to look for their
parameters elsewhere on the tree: their parameters are applied to the
combinator, not to them.  This adds a very complex twist to executing your
parse tree.

> > I'd like to hear a method, though;

> This reminds me of an odd hole that I realized recently that my
> system has. In my more recent post, I described a technique 
> that I thought
> could be used to translate Joy programs into procedures of my
> system; I realize now that there is a flaw in the technique
> so that it would not work in certain cases (actually, I consider
> more a flaw of my system than the technique):

Well, let's see how to 'fix' it.  Or make your system better by taking
advantage of it, naturally.

> In Joy, when a program is executed and there are "too many" items
> on the stack, there is no problem; the procedure just doesn't use
> the extra items; it saves them on the stack for future programs.
> Now...  if we shift into my system, which uses continuations 
> instead of
> a stack, there is something similar... The "C" combinator could be
> thought of as a function that takes a continuation function "f" plus
> two more parameters "x" and "y", yielding "f y x". In "procedure"
> terminology, we might call "C" a procedure that takes two parameters
> and has two results...

Odd.  I see your point, though.

> Now, if "C" is applied to "too many" things, you may still end up
> with something meaningful... For instance, let "foo" be some
> procedure that takes 4 parameters (plus a continuation parameter,
> which comes first). In my system, "foo stop a b c d" might be 
> a meaningful
> command to the system. Now, what I'm getting to is that
> "C (foo stop) a b c d" would then also be meaningful, even though
> "C" is applied to more than three parameters; it is the same as
> "foo stop b a c d".

Ah hah.  Yes, good point.

The problem is that C only takes three parameters; after that you're NOT
applying parameters to C, but rather to the result of the expression
containing C.  Put in explicit form, this is legal:

@@(@@@C @foo stop b a) c d

but this isn't:

@@@@@C @foo stop b a c d

(Does this make sense?  Formally those two expressions mean the same thing,
but I hope you can see the informal difference.)

Let me sketch a tree:

+ C - foo - stop
| + - b
| + - a
|
+ - c
+ - d

See what I mean?  So the function (C (foo stop) b a) has to computed, then c
and d have to be computed, and only then can c and d be applied to the
function denoted by (C (foo stop) b a).

> In general, a combinatory reduction in the system can take place
> in any part of an expression. For example, "(C f x y) a b c" reduces
> to "(f y x) a b c" or just "f y x a b c". Similarly,
> "f (C g x y)" can be reduced to "f (g y x)". This idea can be
> summarized by the so-called "u" and "v" rules:

>   u: If "x -> y", then "f x -> f y"
>   v: If "x -> y", then "x f -> y f"

Now, I have to grant that this is true.  The problem is parsing and
interpreting it.

> Hmm... I feel like I've gone off on a tangent, although that seemed
> relevant... Back to what I was originally going to describe, the
> analogue of what happens when there are "too many things on 
> the stack"...

> I had considered, for example, "Output" to be a function that
> takes two parameters, a continuation, and a string to be outputted,
> and yielding another continuation. Thus, I might say that
> "Output stop 'hello'" is a continuation of the system, and that the
> system might be able to execute it. However, what would we say
> about "Output stop 'hello' 'there'"? In this case, we have applied
> the continuation "Output stop 'hello'" to yet another parameter
> "'hello'"... I had originally considered that this expression would
> just be jibberish, since continuations were not functions, and
> did not make sense when applied to parameters.

By the syntactic rules of currying, that _is_ nonsense.

> But, I think that would be a bad quality of my system. To make my
> system analagous to Joy, "Output" would need to forward any extra
> parameters it has to the next continuation... Thus,
> "Output foo 'hello' 'there'" would be a program that outputted "hello"
> and then went on to do "foo 'there'", the extra parameter "'there'"
> having been forwarded to the continuation "foo". Thus, a program
> to output "hello" and then "there" could be written as:

Um.  Interesting.  So to use the terms I used, a "command" _can_ accept
parameters, and its action in so doing is simply to pass those parameters to
its continuation.  Interesting.

Taking this another step further, suppose that we say that a niladic
function can also accept parameters?  That would solve the problem of the C
combinator you mention above.  It would also provide a basis (or an excuse)
for not having to count the parameters of a function.

>   Output (Output stop) 'hello' 'there'
> Or, in a more Joy-like way...
>   T 'there' . T 'hello' . Output . Output

> Actually, this second is a bit different from the first one... The
> first is a continuation that outputs 'hello' and then 'there' and
> then "stop"s. The second is a bit more abstract; it is a function...
> if you applied it to "stop" you would get the first one... But,
> you could apply to some other continuation... Normally in my system
> one would not make explicit references to "stop", so the second
> is more like what one might actually use.

Yes.  Looks good.

> > Perhaps it's reasonable to simply ignore those extra variables.
> > That _does_ make sense, pragmatically.  
> > It's an irritation when coding,
> > though, since you couldn't tag a large class of simple errors. 

> Hmm... Well it wouldn't make much sense to me if the system
> treated "ackermann 4 5 6" as if it was just the same as
> "ackermann 4 5"... (not sure if this is what you meant).

Exactly what I meant.  Do you have a better idea?

> > [expressing all combinators from a few primitives]

> > It's not a trivial task, and it expands rapidly;
> > but in its naive form it's linear.  Optimization is where 
> > it gets hard

> Yes, optimization is usually a hard thing... Actually, in some cases,
> it might be hard to say which expression of a combinator is more
> "optimal" than another. I guess you could go by the size of the
> expression; if so, then "optimization" is quite a hard problem,
> as far as I know... There are often clever ways of writing
> combinators using shorter expressions than what that simple
> algorithm gives. 

If you can't even guess what "optimization" means, then your system truly
_is_ far inferior to Joy.

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

> > Hmm.  Not really, although that's a possible expression of it.

> > A better way to express the difference is to point out that 
> > imperative
> > languages express sequences of commands, each of which has 
> > some kind of
> > effect on its environment.  Declarative languages express 
> > -- or pretend to
> > express -- unchanging facts about reality.

> > Joy contains a declarative language: its definitions are an 
> > imitation of the
> > notation the author uses for expressing rules, and contain 
> > restrictions
> > which allow the compiler to check them for inconsistencies. 
> > Your language
> > tries to be declarative throughout, but it turns out that 
> > it can't express
> > any action without procedures.

> Neither being "declarative" or "imperative" is one of my goals for
> the system, at least not now... Being "declarative" may have been
> a goal, before, but I don't really care now.

That's wise.

> If I had to summarize
> what my goals for the system are, I might say that I want the
> system to be

>   1) flexible
>   2) highly-performant
>   3) simple

Forth.

> These are rather broad goals, of course. I also have some other, more
> specific, goals that are means to achieve these (although
> "highly-performant" is way on the back-burner)... For instance,
> the goal of making the system more-or-less purely applicative
> and based on combinators...

If you can't decide what "optimize" means, how can you make a
"highly-performant" system?

> Of course, I don't claim that making the system purely applicative
> is the only way to achieve great flexibility... Joy's 
> concatenative approach
> may also be adequate; on the other hand, there are some things one
> can do in my system that I'm not sure one can do directly in Joy

The trick here is the word "directly".

> (for instance, the use of "M" to get the current continuation).

Continuations are not natural to me, so I have trouble answering that claim.
I didn't understand your original claim, either.  In general, in order to
get the continuation of the current state, one has to preserve all
parameters and all future function calls.  In Joy, the best way to do that
is to save the data stack and return stack, push the current IP onto the
saved return stack, and return the two stacks.  M doesn't even see any of
the parameters; it only affects the 'return stack'.  Thus, a call to a
"continuation" has to provide all-new parameters.

In other words, I don't think M is really returning a continuation, but
rather a list of future function calls (up to, but not including, the return
from the current procedure).  Joy can do that same thing at least as well
simply by providing a word which returns the current IP (instruction
pointer), since execution will proceed straightforward from there.  Forth
can do it that way as well (and that's how it builds all of its control
structures), but it can also reach into the continuation and modify it by
text processing.

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

> > This distinction you're making seems to be valid, but it 
> > seems to me to
> > contradict everything you've said in the past about your 
> > system versus mine.
> > For example, you state that your language can actually 
> > represent the number
> > 3, while my system can only imitate 3 by means of a procedure.  

> That statement I said was silly, and I would not repeat it
> (although it was true, in a sense). 

You just repeated it; you can't have it both ways.  I still don't understand
how it can be true in ANY WAY.

> > "Actual representation" is the goal of a declarative language; in
> > such a language you want to make it seem like the author of 
> > a program
> > is merely expressing immortal and immutable truths to the 
> > computer to
> > help it understand the problem (the problem is also treated as an
> > immortal truth).

> It seems clear that you do not like "declarative" languages.

I had not intended to be clear.  ;-)  <J/K>  Seriously, though, I didn't
intend to express any dislike.

I have no dislike of any kind for declarative languages.  On the contrary, I
think they're immensely powerful.  I'm simply expressing a passionless,
precise description.  Re-read my statement with that in mind -- I was not
exaggerating, and I stand by my words.

One of the reasons I like Joy is that it taught me why I liked Forth:
because it was both declarative and imperative at the same time.

> I do not really value the approach, although I do not dislike
> it either. Of course, there might be some specific "declarative"
> systems that I value more than some specific "imperative" systems
> or vice versa, but I'd really probably need to look at specific
> systems to pass judgement.

Your functional sublanguage is powerful because it's declarative.  You've
explained that repeatedly.  Your procedural system is powerful because it's
imperative.

Joy is powerful because it's both at the same time -- and it's also simple.

> > To help carry out this illusion, declarative languages usually do
> > consistency checks to make sure that the author doesn't attempt to
> > "contradict" himself, 

> Ahh ... consistency checks... I'm guessing that a consistency check
> is something that is truely valuable; a powerful imperative 
> system will have its analogue.

No it won't, because imperative systems are all about _changing_ things.
You can't tell whether the author is being accidentally inconsistent or
deliberately ordering the computer to change something.

Of course, nothing is _perfectly_ imperative or declarative, so in reality
you really can do _some_ consistency checks.

> > and usually disallow redeclaration or changing of data.

> Ahh ... Yes, I suppose many declarative systems have little or no
> support for Fields ("field" is my name for an abstract storage spot,
> which can hold one value at a time, but may hold different
> values at different times); this would be unfortunate, because fields
> are really quite useful... On the other hand, many 
> "imperative" systems
> place very heavy emphasis on fields, which is also unfortunate;
> the heavy emphasis on fields (even when they are not needed) is
> probably what creates the problems of provability with "imperative"
> systems.

Many languages have attempted to meld mutable values with declarative
programs.  I'm not aware of a single one which has suceeded.  The only way
to do it -- let me look this up...  Darn, I can't find it.

There's one language which models changing state by an infinite sequence of
values.  When you 'assign' a value to an expression, you're really switching
its position in the sequence.  It's a very interesting language, lot of fun
to play with -- and I can't find _any_ mention of it anywhere (nor can I
remember its name).

> Anyway, I plan on having support in my system for fields
> (in fact, I already do; there is a "new" which yields a new
> field filled with a specified value, and a "get" and a "set"
> which can be used to get and set it; fields do not need to be
> assigned names). Interestingly, Joy does not seem to have support
> for fields, except for the stack, which could be considered a
> sort of field. If Joy were going to be used as a practical system,
> I think it would need to be extended with fields...

Hard to say.  "Practicial" isn't something one can achieve just by
developing a laundry list of features.

> > x = 1
> > x = 2

> > This is a contradiction to a declarative language.  To make 
> > this valid, you
> > have to use lexical scopes:

> > x = 1
> > in:
> >   x = 2

> > Now the inner x is different from the outer x.

> Hmm... That did not make sense to me. If "x" is a name the 
> user uses for
> a particular number, then the original verdict (that "x = 1" and
> then "x = 2" causes a contradiction) seems natural to me;
> if I had told that system both that "x = 1" and "x = 2" I would
> want it to complain about a contradiction.

Right.

> On the other hand, looking at the example, I'm guessing that the
> user intended to use "x" more as a field for a number than as
> just a number; if so, then the user could have correctly said
> (this is Joy-style code):

>   newfield "x" define
>   1 x set
>   2 x set

That's Forth-style, not Joy-style.  But anyhow...

> Where "newfield" is a program that pushes a new field onto the stack,
> and "define" is a program that takes a string literal and a thing
> to bind it to off the stack... Then, "set" would be program that takes
> a value and a field to set with that value.

> On the other hand, perhaps the user did intend to have "x" represent
> a number rather than a field for a number. Perhaps after he typed
> "x = 1" he realized that he defined "x" to the wrong number,
> and wanted to correct it so that "x" was defined to be "2". In
> the system I'm thinking of, he could have correctly expressed
> this as (again, Joy-style):

>   1 "x" define
>   2 "x" redefine

> or equivalently:

>   1 "x" define
>   "x" undefine 
>   2 "x" define

All this stuff does an almost incredible amount towards destroying all of
the benefits functional languages are supposed to have.

I'm starting to be puzzled.  You started out explaining this really clean,
simple functional language to me, and you told me that it was better than
Joy because it expressed the same things in a clearer way.  As time goes on,
though, it's looking as though your language is almost completely incapable
-- you're having to tack on elements from every other domain, ranging from
procedural through object-oriented to logical.  You're doing all of this
stuff without a word of explanation as to how it fits together; you seem to
believe that all of the people who have tried this before just got it wrong
by accident, and you'll get it right equally by accident.

This is especially odd since you're extremely knowledgable about theory, and
I'd expect you to have developed your own theory to a high art.

> > This is why I argued with your implementation, preferring 
> > instead my own:

> >  x\dry (rinse (wash x))
> > or
> >  @dry @rinse @wash

> By the way, "@dry @rinse @wash" is not quite right... It is not
> a well-formed expression... What you want, I think, is
>   dry . rinse . wash

You're absolutely right -- I was treating them as functions.  In Joy, they
are.

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

> > Certainly.

> > [example with "augment"]

> I'm not sure I quite followed that...

> It looks like maybe you're classifying expressions that involve
> list-breaking-down programs (such as 'uncons') as "broken".
> But, I'm not sure I see how this is connected with substitution 
> (of equivalent programs) and how it needs to be restricted within
> quotations...

Not really.  List-breaking-down is fine -- but breaking down a list has to
account for the fact that the list may be empty or of length one, thanks to
functionally equivalent substitutions inside the list.

In other words, the program which is taking apart the lists _has_ to be able
to handle arbitrary programs.  If it's unable to handle them, than it's not
truly parsing programs: it's actually parsing lists in a specific format.

Any program which can handle arbitrary programs as input will also respond
correctly to behavior-preserving modifications to those programs.

> > Your applicative system does not manifest this
> > difficulty because _it is impossible to use your system to 
> > reason about
> > programs_.  

> In a certain sense, my system cannot reason about programs, or
> about anything at all, as I have not yet constructed a reasoning
> system; in this sense, Joy is not really capable of reasoning
> about programs either, in that it does not come with a reasoning
> system either.

Joy IS capable of reasoning about its own programs.  The fact that it
doesn't come with a reasoning system (whatever you might mean by that) means
only that you, the programmer, have to write your own system.

In Joy, every program which manipulates a quoted program in some sense is
reasoning about it.

> Yet, in a different sense, both my system and Joy _can_ reason about
> programs. The framework is there; in both systems, programs can
> be manipulated in a first-class way... A reasoning system just needs
> to be constructed on top of them.

No, this is simply false.

> But actually, I don't think one could construct a good reasoning
> system on top of my current system. Rather, I need to enhance my
> system with a Reification primitive. So, what you said was right...

Yes, this is true.  Once you add reification your system will be equivalent
to Joy -- although more complex.

> > As soon as you add reasoning capability your program will have
> > to face the exact same problem -- 

> I still have to think a bit about how I might make the reification
> primitive work. Perhaps when I add it, there will be problems,
> as you suspect...  

Okay, we'll have to see.

> The reification primitive will probably take the form of a procedure
> which takes an arbitrary thing of the system as a parameter,
> and which results in a data-structure representing that thing.
> In the data-structure, I might use, say, numbers to represent
> the primitives, and pairs (by "pair", meaning a procedure that
> pushes two things onto the stack, i.e., to the continuation)
> to represent applications.

> Anyhow, a reification primitive would really be quite a low-level
> primitive; in a finished system, users would probably not need
> to refer to it explicitly (drawing instead upon the many bounties
> offered by the logic system that was constructed using it);

There's no reason for the logic system to be constructed using reification;
however, I would expect that the logic system would be very useful for
analyzing reified data.

> > and the same solution I outlined will work
> > for you, and any solution you come up with will also work for me.

> I guess Joy already sort of uses the solution of having reification...
> The quotation construct is sort of a reification construct.

The really interesting thing is that the reified language is
organizationally identical to the language the programmer types in.  Once
you learn how to write in Joy, you automatically know how its reified
programs are stored.  In addition, functions are passed around in reified
form at all times.

This is not true for your language.

> > Your language, OTOH, takes existing theory -- which is of 
> > dubious use, and
> > is only around because it loosely models existing 
> > programming languages --
> > and attempts to build a programming language on it.

> This is a strange statement...

Yes, it is.  I don't know why I wrote it -- I was wrong.

> > Of course, if I were to say that Joy was any better than 
> > your language I'd
> > be wrong.  It's also a wild speculation, and odds are just 
> > about certain
> > that it'll never be of any real use.  The real value I'm 
> > looking at is the
> > possibility of building a child of Forth which is just as 
> > useful as Forth,
> > and just as easy to formally reason about as Joy.

> Ahh... So you are also looking at constructing your own system...

Yes.  Joy is cool, but it's clearly not a useful language, nor is it
intended to be.  Forth, on the other hand, was not designed to be cool, but
instead useful; however, almost accidentally, it is cool.  I think that I
can merge the deliberate coolness of Joy with the deliberate usefulness of
Forth to gain a language which is more useful and more cool than either.

Pardon my use of the non-technical term 'cool' above.  ;-)

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

> > APL experience indicates that it may be a fundamental fact 
> > rather than a temporary inconvenience.

> I doubt it... I guess I'll have to see, though...

I suppose so -- although I would tend to be less flippant in dismissing
prior experience.

> > That way you can borrow the slogan used by at least
> > one APLer: "APL: if you can say it, it's done." 

> I suspect that instead I'll adopt this slogan:
> "CLIP: You can say it, but can the system do it?"

Eek.  I see your point.

> It might be considered a problem of my system that it is possible
> to refer (in a valid way) to a procedure that the system is
> capable of doing, but yet the system not be able to do it.
> That is, for instance, one might tell the system to do
> (this is pseudo-code)

>   ifte (C.BC.C = BC.C.BC) (Output 'yes') (Output 'no')

> This expression denotes the procedure of outputting 'yes'
> (which the system is perfectly capable of doing), but
> the system might not be able to figure that out, because to
> do so it would probably have to figure out that "C.BC.C = BC.C.BC"
> denotes the truth proposition; it may or may not be able to do this
> (I would hope that in a finished system, it could) ...

> This problem could become somewhat serious when one wants to
> distribute programs; a program might work on one person's machine
> but not on another... A possible solution would be to formalize
> a subset of the language which all decent systems could decipher;
> then, before distributing a program, one would "compile" it into
> this restricted langauge; this compilation would basically involve 
> the insertion of (a piece of) the system's logic system into
> the generated program...

Um...  But the recieving system would have to be able to execute that logic
system.  It would be trivially easy to construct a malicious false logic
system.

> - iepos ("Brent Kerby")

-Billy