Joy, Lambdas, Combinators, Procedures

[btanksley@hifn.com]

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

> > > Eh? Hmm, Haskell, for example, is not purely applicative. It has
> > > a lambda construct, and also a strange (pattern-matching) 
> > > definition
> > > construct. This is along with its strange constructs that involve
> > > types. These constructs, it seems, are not syntactic sugar, but
> > > essential constructs to the system.

> > Oh, and BTW, the very existence of a lambda construct goes 
> > a long way to
> > proving that Haskell is applicative.  A lambda expression 
> > is only meaningful when it can be applied.

> I believe this reply is based on a misunderstanding of what I meant
> by "purely applicative". By a "purely applicative" language I mean
> a language which has _only_ an application construct, and no other
> constructs (other than primitives). So, since Haskell has a 
> lambda construct (a construct other than application), it is
> not purely applicative. Purely applicative languages (in the sense
> that I mean) do not have lambdas or named variables of any kind.

Oh!  So indeed we _were_ talking past each other.  Thanks for the
clarification -- I was talking about "applicative" languages versus
"concatenative" languages, and you were talking about "purely applicative"
languages versus "everything else".

Now that we both know what each is trying to communicate, perhaps we can
resolve these issues.

Let me make clear my bias against a purely applicative language with a
single disgusting analogy: I would no more consider using a purely
applicative language for the sake of simplicity than I would consider using
castration for the sake of moral purity.  I consider both goals to be noble
(in their place), but I consider the means to be misguided.

All those features are in there for a reason: the reason is generally to
make real programs simpler.

> > > In case this was not clear, by "purely applicative 
> > > language", I mean
> > > a language in which all expressions are built from a finite set
> > > of primitives using a binary construct ("function application").
> > > An expression in such a language is most naturally written
> > > using a binary tree, with primitives as leafs.

> > This is a definition which fails to define.  Joy fits that 
> > definition
> > exactly, as does every language which uses finite-length 
> > identifiers.

> No, Joy has an odd construct for quotation, with those "[]"s.
> This is a construct other than application.

You didn't say that it couldn't have other constructs.  But never mind.

Your purely applicative language has MANY other constructs, ranging from
combinators to parenthesis to definitions.  So your language doesn't fit
your reading of that definition either.

> > Unless you're implying that infix isn't allowed, in which case most
> > languages are excluded (but not Joy).

> Strictly, infix constructs other than application are not allowed
> in a purely applicative language; however, a language that has
> an infix construct can usually be reformalized without it, using
> a new function primitive.

Agreed.

> > An applicative language any language which has application. 
> > Application is

> I'll take that as a definition here...  But remember that that is not 
> what I mean by a "purely applicative" language.

It's an inclusive definition -- your purely applicative language will fit
it.

> > the action of assigning a language element as being 
> > exclusively the property
> > of a function invocation.  For example, in the C function call
> > "unlink(filename+1);" the function 'unlink' is being applied to the
> > syntactic element 'filename+1'.  No other function is being 
> > given that
> > particular element; in fact, it may be impossible to 
> > reproduce, as for
> > example the C call "unlink(filename+rand());".

> I'm not sure what you mean by this... This seems to be part of
> an extended definition of "application", I guess...

Exactly.  It's a vital thing to realize about applicative languages:
"application" is when you syntactically "apply" a paramater to a function.

> > > > > [purely applicative systems]
> > > > The benefits are very 
> > > > well-known -- but the drawbacks are as well.

> > > Hmm, what drawbacks are you speaking of?

> > First of all, the names.  Because parameters are 
> > syntactically tied to the
> > function to which they're applied, if you're going to use 
> > them more than
> > once you need to give them a name.  The presence of this 
> > name forces you to
> > apply certain rules to the language's semantics beyond 
> > those which are
> > strictly required by the mathematics.

> Once again, a purely applicative system (in the sense that I meant)
> does not use names for its parameters. Purely applicative
> systems instead tend to use combinators (primitive functions such 
> as "B", which composes a function, and "C", which swaps its parameter 
> order, and others) to form functions. With a handful of
> such primitive functions, it is possible to form any function
> that could have been formed with a lambda (named variable) construct.

This is true.  If you'd played with J or APL you'd realize that it quickly
becomes FAR to complicated to track parameters that way -- but it's still
possible.

> > In addition, because function invocation is complicated by function
> > application, proofs written in the language have to deal 
> > with the double action.

> The system you're describing (C, I believe) is nothing like a
> purely applicative system. 

It's precisely and exactly (in this quote at least) purely applicative.
Note that I said nothing about names above -- the simple fact is that in an
applicative language, function invocation is always accompanied by function
application; in other words, the language can't emit code to run the
function until it has the paramaters which will be passed to the function.

(Named variables actually don't eliminate applicative purity; they eliminate
combinatoral purity, though, and I'm quite willing to agree that your
language design can eliminate named variables.)

> > > Anyway, one clear benefit of using a purely applicative language
> > > is that it has such an amazingly simple syntax.

> > I strongly suspect that you don't have a referent for 
> > "simple syntax".
> > Currying (the simplest known way to define an applicative 
> > language) is
> > indeed simpler than some of the complex parsing tricks some 
> > languages have
> > to do; however, currying is not enough by itself.  You also 
> > have to have
> > four other syntactic elements: one to delimit functions, 
> > one to define
> > names, one to count how many parameters a function has (and 
> > identify each
> > one), and one to change the curry order.  That's a total of 
> > five elements.

> Again, this is based on a misunderstanding... A purely applicative
> system does not use named parameters, and does have a truely
> simple syntax.

Read what I wrote -- I didn't mention named parameters.  I listed five
essential elements of application; with all five of those you don't have a
language, instead you have a spreadsheet macro (or something).

A concatenative language only needs some of those; it doesn't need curry
order changes, and it doesn't need parameter counts.  In place of currying,
of course, it uses composition.

Your language, by the way, adds another element which isn't listed in my
"must have"s: combinators.  Combinators seem to be special to your language,
like IMMEDIATE words are to Forth.  That definitely adds another element to
your language -- an element which Joy does not have.  (Joy includes
functions which act as combinators, but they do so without any special
language support.)

> I think maybe another example may help...

Thank you.

> In a Joy test library, I saw this definition of "factorial":

>   [ [pop 0 =] [pop succ] [[dup pred] dip i *] ifte ] y

Good choice.  (That's an ugly way to do it and I wouldn't dream of writing
real code that way, but it uses the primitives so it's easy to translate and
is somewhat non-trivial.)  Note that a harder challenge might have been
appropriate for you: in Joy it's trivial to define new combinators; in fact,
there's no distinction between a user-defined combinator and a user-defined
function.  Is it equally easy in your language?

The definition of 'y' in Joy is:

 y == [dup cons] swap concat dup cons i;

> In a purely applicative language, a factorial function might 
> be written as:

>   Y (S3 (ifte =0) (K 1) . S times . CB (minus 1))

> Or, without the sugar for composition ("."),

>   Y (B (S3 (ifte =0) (K 1)) (B (S times) (CB (minus 1))))

> where Y, B, S, S3, K, and C are certain primitive functions, 
> with these
> rewrite rules:

>   Yf = f(Yf)
>   Bfgx = f(gx)
>   Sfgx = fx(gx)
>   S3 f g h x = fx(gx)(hx)
>   Cfxy = fyx

> Hopefully you do not see a purely applicative approach as all
> so bad now, seeing how similar in spirit it is to Joy.

Well, I'm not sure that a single example can show that much.  Can you refute
my claim that Joy is simpler than even a truly pure applicative approach
(and your language isn't pure, but rather adds the notion of combinators to
an otherwise applicative base)?

Furthermore, having looked at the proofs written in the Joy manuals, can you
duplicate any of them as simply?

> > > In fact, the
> > > syntax of a purely applicative language is simpler than the syntax
> > > of a Joy-style expression. The essential construct of Joy is
> > > the list ("quoted program"); the other constructs (such as the
> > > finite-set construct and number-literal construct) could be 
> > > eliminated. 
> > > So, the format of a Joy expression is a tree (with primitives 
> > > at the leafs),

> > Something happened to the rest of this paragraph.  I'm not 
> > sure what you
> > were trying to say, so I'd better not try to reply :-).

> Let me clarify...
> It should be clear that the list construct (written using "[" and "]")
> is the most fundamental construct of Joy.

> If the extras of Joy were 
> omitted, the syntax of a Joy program would be basically a list
> of expressions (programs to execute), where each individual
> expression is either a primitive program (like "pop" or "dup")
> or itself a list (using "[]"s) of expressions. 

Okay, I think I see your point (although I wouldn't call that foundational;
it's only an essential side-effect of the concatenative nature of Joy).  So
you've now described Joy's syntax.

> Anyhow, the whole point of this was to show that Joy's syntax is
> a bit more complicated than a purely applicative one.

Again, why?  You've explained the syntax of Joy, but you haven't even made a
reference to the syntax of your language, much less that of a purely
applicative language.

I've recited already the five syntactic elements that every applicative
language needs in order to produce code; I've also recited the three
elements that a concatenative language needs.  I've also made the claim that
your language needs one additional element (combinators) which is distinct
from any of the other five needed by a truly pure applicative language.

Can you make any counterclaims?

> > Yes.  It's an obsolete variant of a now-commercial system, 
> > but it still
> > works.  It's at ftp://archive.uwaterloo.ca/languages/j.  
> > (There may be other
> > implementations there by now; however, it's a sophisticated 
> > language even though it has a simple syntax.)

> I'll check it out...

The interesting thing about APL is that it, like LISP, is an accidental
pioneer; the inventor of APL didn't really intend for it to explore
combinators any more than the inventor of LISP intended it to explore
lambda-calculus.

> - "iepos" (Brent Kerby)

-Billy