Joy, Lambdas, Combinators, Procedures

[btanksley@hifn.com]

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

> > > Again, by "functional language" i meant "purely 
> > > applicative language".

> > What do you mean, then?  All modern functional languages, 
> > and most of the early ones as well, are applicative.  

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

Haskell is essentially applicative: the pattern-matching is important only
in a function-overloading sense.  This is proven most strongly by the fact
that Haskell is curried (currying is by definition a way of _applying_
parameters to functions).

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.

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

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

An applicative language any language which has application.  Application is
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());".

Joy is not applicative because although functions do have parameters, the
parameters are not given special place as belonging to the function; the
function is free to pick up any parameters it wishes.

Haskell is applicative because everything is curried; currying is, by
definition, assigning a language element its place in a function's parameter
list.

> > It's one of the most thoroughly
> > studied areas of computer science.  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.

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

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

A concatenative language, on the other hand, needs only three elements:
concatenation, function delimitation, and name definition.

Just for example, here's a fragment of a made-up applicative language:

define myNumber 3  -- see note below
define add [+]
define bump [add myNumber]

print add (bump 4) 5
>>> 12

And here's the same thing in a concatenative language:

define myNumber [3]
define add [+]
define bump [myNumber add]

5 4 bump add print
>>> 12

Note: the applicative listing is simpler in only one way: the '3' does not
need to be delimited, because the language knows that it's niladic, so
doesn't attempt to curry it.

Also note that my function definitions in the applicative language are
impossibly simple; I'm not defining parameters for them because they're both
essentially aliases of other functions.  This is ridiculously limited; in
real life I'd have to have named parameters as well.

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

> > > maybe so... I believe proofs about a purely applicative system
> > > may also be impressive. 

> > Impressive, yes -- but only in the sense of baroque 
> > complexity and limited
> > applicability.  Really; I've seen hundreds of them.

> I only suggested that there _exists_ (in an abstract sense) a
> purely applicative system that is easy to reason about;
> that you've seen hundreds of example bad systems does
> not eliminate that possibility that there is a good one.
> Anyway, can you give me one of those hundred examples?

Take a look in any book on programming languages which covers functional
languages.  They're almost all applicative.

> > > Hmm... I've never heard of "J" or "APL"...

> > Oh no!  APL's a great system, lots of fun.  I recommend you start by
> > learning J, since it uses ASCII characters (instead of 
> > APL's character set,
> > which requires not only extra characters, but even depends 
> > on being able to
> > overstrike them).  APL itself is a good language, but it's 
> > hard to learn without a special keyboard (IMO).

> I might have to check it out, then... is there a freely
> available system?

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

> > > anyway, I see no point in arguing further over which kind 
> > > of system
> > > is better (Joy-style or purely applicative); I haven't really
> > > claimed that either kind is generally better... but 
> > > purely applicative
> > > seems worth trying well, at least.

> > It's been tried thousands of times.  Look at _any_ 
> > functional language aside

> Can you give an example?

Haskell, Miranda, ML, C...

Every language which has function parameters is applicative.

> > from Joy.  Consider especially the ones with implicit 
> > currying; those have
> > implicit application, which makes them more comparable to 
> > Joy's implicit composition.

> (?)

Currying is the simplest way to apply parameters to functions.  This is
because it's implicit: you don't have to name the parameter.

Joy doesn't use application, but its main construct is implicit.  Therefore
it's kind of unfair to compare it to languages which don't have the capacity
to make their main construct implicit.

> - "iepos" (Brent Kerby)

-Billy