Joy, Lambdas, Combinators, Procedures

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

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

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

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

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

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

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

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

> [made-up applicative language...]

I think maybe another example may help...
In a Joy test library, I saw this definition of "factorial":

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

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.

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

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

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

I'll check it out...

> > - "iepos" (Brent Kerby)
> 
> -Billy
> 

I hope this has cleared things up...

- "iepos" (Brent Kerby)