Joy, Lambdas, Combinators, Procedures
iepos@tunes.org
iepos@tunes.org
Fri, 28 Jan 2000 22:09:28 -0800 (PST)
> > 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)