Joy's relationship to FP + a Joy variant with combining forms

[John Nowak]

On the Joy site, there exists a comparison between Joy and FP:
http://www.latrobe.edu.au/philosophy/phimvt/joy/j08cnt.html

 From what I gather, there are two main differences between Joy and  
FP. The first is that Joy is based on function composition whereas FP  
is based on function application. The second is that functions in Joy  
can be higher order whereas all functions in FP are first order.

Instead of higher order functions, FP has combining forms (aka  
functionals). Combining forms are used to form new functions. The main  
difference between combining forms and HOFs is that combining forms  
take their functions as arguments "directly". In other words, they  
cannot be passed at runtime and there are no first class functions.  
Accordingly, programs in FP cannot compute programs. It would seem  
that Joy also has two combining forms, namely composition and quotation.

In short, Joy is higher order and based on composition, and FP is  
first order and based on application. What I'm wondering is what a  
first order language based on composition would look like.

My reason for this interest is due to the difficulty inherent in  
reasoning about concatenative programs in which functions can access  
indeterminate portions of the stack. If higher order functions are  
eliminated and replaced with combining forms that yield functions,  
this problem goes away, and it does so without the need for a suite of  
fixed arity combinators and other ugliness. I have other reasoning for  
being interested that I won't discuss for now.

Briefly, I'll lay out how I think such a language might work.

In order to get rid of higher order functions, things like 'dip' and  
'if' need to become combining forms. The syntax for using a combining  
form is '<form_name>(<arg1>, <arg2>, ... <argN>)'. For example, here's  
an implementation of factorial:

     Higher order version:
     fact = dup zero? [succ] [pred dup pred fact *] if

     Combining form version:
     fact = dup zero? if(succ, pred dup pred fact *)

One thing to note is that a combining form for quotation is no longer  
needed since it is impossible to create objects that represent  
functions.

While FP does not allow the definition of new combining forms, such a  
facility is undoubtedly necessary for real programming. The syntax for  
this mimics use. Note that all variables are in uppercase so as to not  
clash with function names. Here is an example of how we can define a  
'reverse-map' combining form in terms of the 'fold' combining form:

     Higher order version:
     reverse-map = null swap [cons] compose fold

     Combining form version:
     reverse-map(F) = null fold(F cons)

To be clear, these are not general lambda expressions. Combining forms  
yield normal point-free functions. For example, 'reverse-map(negate)'  
expands to 'null fold(negate cons)'. Also note that it is impossible  
to assign a variable to an object passed on the stack; they only deal  
with expressions given directly.

If anyone has any thoughts on such a language, either in terms of nice  
theoretical properties or feasibility, it would be much appreciated. I  
have some thoughts on the topic but I'll hold them for the time being.

- John

[stevan apter]

APL is a first-order applicative language with combining forms (called
"operators".)  for example

    +/x

/ is an operator taking + as its operand and yielding a function which
applies + over x.  / is not first-class, cannot be assigned or passed
or returned as a value.  my memory is that backus specifically
credits iverson's work and APL as the inspiration for FP's combining
forms in his original paper, although i could be mistaken.

in later generation APLs, it was possible to define operators as second-
order functions in the same way that one could define first-order functions.

i hope this is useful, or at least fills in a little history.

----- Original Message -----
From: "John Nowak" <john@...>
To: "concatenative" <concatenative@...>
Sent: Saturday, May 31, 2008 10:15 AM
Subject: [stack] Joy's relationship to FP + a Joy variant with combining forms

> On the Joy site, there exists a comparison between Joy and FP:
> http://www.latrobe.edu.au/philosophy/phimvt/joy/j08cnt.html
>
> From what I gather, there are two main differences between Joy and  
> FP. The first is that Joy is based on function composition whereas FP  
> is based on function application. The second is that functions in Joy  
> can be higher order whereas all functions in FP are first order.
>
> Instead of higher order functions, FP has combining forms (aka  
> functionals). Combining forms are used to form new functions. The main  
> difference between combining forms and HOFs is that combining forms  
> take their functions as arguments "directly". In other words, they  
> cannot be passed at runtime and there are no first class functions.  
> Accordingly, programs in FP cannot compute programs. It would seem  
> that Joy also has two combining forms, namely composition and quotation.
>
> In short, Joy is higher order and based on composition, and FP is  
> first order and based on application. What I'm wondering is what a  
> first order language based on composition would look like.
>
> My reason for this interest is due to the difficulty inherent in  
> reasoning about concatenative programs in which functions can access  
> indeterminate portions of the stack. If higher order functions are  
> eliminated and replaced with combining forms that yield functions,  
> this problem goes away, and it does so without the need for a suite of  
> fixed arity combinators and other ugliness. I have other reasoning for  
> being interested that I won't discuss for now.
>
> Briefly, I'll lay out how I think such a language might work.
>
> In order to get rid of higher order functions, things like 'dip' and  
> 'if' need to become combining forms. The syntax for using a combining  
> form is '<form_name>(<arg1>, <arg2>, ... <argN>)'. For example, here's  
> an implementation of factorial:
>
>     Higher order version:
>     fact = dup zero? [succ] [pred dup pred fact *] if
>
>     Combining form version:
>     fact = dup zero? if(succ, pred dup pred fact *)
>
> One thing to note is that a combining form for quotation is no longer  
> needed since it is impossible to create objects that represent  
> functions.
>
> While FP does not allow the definition of new combining forms, such a  
> facility is undoubtedly necessary for real programming. The syntax for  
> this mimics use. Note that all variables are in uppercase so as to not  
> clash with function names. Here is an example of how we can define a  
> 'reverse-map' combining form in terms of the 'fold' combining form:
>
>     Higher order version:
>     reverse-map = null swap [cons] compose fold
>
>     Combining form version:
>     reverse-map(F) = null fold(F cons)
>
> To be clear, these are not general lambda expressions. Combining forms  
> yield normal point-free functions. For example, 'reverse-map(negate)'  
> expands to 'null fold(negate cons)'. Also note that it is impossible  
> to assign a variable to an object passed on the stack; they only deal  
> with expressions given directly.
>
> If anyone has any thoughts on such a language, either in terms of nice  
> theoretical properties or feasibility, it would be much appreciated. I  
> have some thoughts on the topic but I'll hold them for the time being.
>
> - John
>

[John Nowak]

On May 31, 2008, at 1:31 PM, Stevan Apter wrote:

> my memory is that backus specifically
> credits iverson's work and APL as the inspiration for FP's combining
> forms in his original paper, although i could be mistaken.

Indeed he did:

"We owe a great debt to Kenneth Iverson for showing us that there are  
programs that are neither word-at-a-time nor dependent on lambda  
expressions, and for introducing us to the use of new functional  
forms." - John Backus, 'Can Programming Be Liberated from the von  
Neumann Style?'

> in later generation APLs, it was possible to define operators as  
> second-
> order functions in the same way that one could define first-order  
> functions.

I believe this is equivalent to what I'm suggesting. In other words,  
you can make new second order operators, but there is still no way to  
represent functions as objects (i.e. no first class functions).

What I'm desperately curious about is why certain languages like FP,  
APL, J, etc, avoid first class functions. Obviously there are  
advantages to only having first order functions, and I see a few ways  
this is useful (termination proofs are much easier, etc), but I'm  
admittedly less informed on this subject than I'd like to be. If  
anyone would be willing to point me in the direction of something that  
discusses the advantages of the FP/APJ/J approach in contrast to the  
ML/Haskell approach, I'd be very grateful. Unfortunately, most papers  
on FP seem to be locked away on sites I don't have access to, which is  
doubly bad as there are so few to begin with.

- John

[John Cowan]

John Nowak scripsit:

> What I'm desperately curious about is why certain languages like FP,  
> APL, J, etc, avoid first class functions. Obviously there are  
> advantages to only having first order functions, and I see a few ways  
> this is useful (termination proofs are much easier, etc), but I'm  
> admittedly less informed on this subject than I'd like to be. If  
> anyone would be willing to point me in the direction of something that  
> discusses the advantages of the FP/APJ/J approach in contrast to the  
> ML/Haskell approach, I'd be very grateful. Unfortunately, most papers  
> on FP seem to be locked away on sites I don't have access to, which is  
> doubly bad as there are so few to begin with.

I don't really know either, but one thing that comes to mind is that these
languages are classically implemented using dynamic-binding interpreters,
which don't mix very well with first-class functions (the Lisp "funarg
problem").  Although as long ago as 1977, HP implemented APL using a
JIT compiler, with as far as I know no effects on the language except
the loss of "eval".

The paper describing it, (Eric J. Van Dyke, A Dynamic Incremental Compiler
for an Interpretative Language, HP Journal, pp. 17-24, July 1977), is
not online as far as I can tell, but in brief: Each line of APL code
was compiled into machine code as it was encountered, specializing the
code to assume that the rank, shape, and type of the variables mentioned
in it were fixed.  A prologue, also JIT-compiled, assured that this was
still true when the line was next executed.  If the assumption failed,
the line was recompiled using a different strategy which assumed that
rank and type were fixed but not shape; further failures caused this
second strategy to be repeated.  This technique squeezed almost all the
polymorphism out of actual APL programs.

--
Income tax, if I may be pardoned for saying so,         John Cowan
is a tax on income.  --Lord Macnaghten (1901)           cowan@...

[stevan apter]

----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@...>
Sent: Saturday, May 31, 2008 11:58 AM
Subject: Re: [stack] Joy's relationship to FP + a Joy variant with combining forms

>
> On May 31, 2008, at 1:31 PM, Stevan Apter wrote:
>
>> my memory is that backus specifically
>> credits iverson's work and APL as the inspiration for FP's combining
>> forms in his original paper, although i could be mistaken.
>
> Indeed he did:
>
> "We owe a great debt to Kenneth Iverson for showing us that there are  
> programs that are neither word-at-a-time nor dependent on lambda  
> expressions, and for introducing us to the use of new functional  
> forms." - John Backus, 'Can Programming Be Liberated from the von  
> Neumann Style?'
>
>> in later generation APLs, it was possible to define operators as  
>> second-
>> order functions in the same way that one could define first-order  
>> functions.
>
> I believe this is equivalent to what I'm suggesting. In other words,  
> you can make new second order operators, but there is still no way to  
> represent functions as objects (i.e. no first class functions).

right.

>
> What I'm desperately curious about is why certain languages like FP,  
> APL, J, etc, avoid first class functions. Obviously there are  
> advantages to only having first order functions, and I see a few ways  
> this is useful (termination proofs are much easier, etc), but I'm  
> admittedly less informed on this subject than I'd like to be. If  
> anyone would be willing to point me in the direction of something that  
> discusses the advantages of the FP/APJ/J approach in contrast to the  
> ML/Haskell approach, I'd be very grateful. Unfortunately, most papers  
> on FP seem to be locked away on sites I don't have access to, which is  
> doubly bad as there are so few to begin with.

i don't recall any specific discussions.  based on conversations with
APL implementation teams over the years, i'm guessing that they never
saw the point of having first-class functions, much less first-class
operators.  (K is the exception here - everything is first-class.)

classical APL operators like / take functions of fixed and well-known
arity:  +/, but not first/.  moreover, functions of any kind have zero,
one, or two arguments, and operators have one or two arguments.  the
reasons, i gather, are partly syntactic, partly semantic.  (in APL it's
often difficult to disentangle these concerns.)

i think you can trace these ideas (and limitations) to two sources:
(i) early APL implementations had to be squeezed into tiny memory, and
(ii) the implementors were mathematicians, and the generating ideas
behind APL were based on iverson's program for the reform and regimentation
of mathematical notation (see his book "A Programming Language".)  APL
represented a series of compromises dictated by the existing technology
and the uses envisioned by the implementors.

to get a good feel for how people were thinking about these things, you
might want to get hold of an early edition of gilman & rose's "APL: an
interactive approach."  this is an introductory textbook, but i think
this makes it easy to see what was *not* on the horizon at that time.
in particular, the fundamental (ontological?) distinction between *data*
(which varies) and *functions* (which did not.)  i recall one of these
early implementors -- i think it might have been jim brown of ibm --
remarking that defined operators might not be too useful, since the
handful of primitive operators seemed to cover all the useful cases.
and no one could think of any useful examples of third- or fourth-order
functions.

i think it would be fairly easy to gin up a model of concatenative APL,
with or without array primitives (but definitely without the symbolic
character set!)

fixed forms instead of HOFs is an interesting idea.  as always with me,
the question is what loss of expressiveness (if any) will result.

>
> - John
>

[John Nowak]

On May 31, 2008, at 1:34 PM, John Cowan wrote:

> This technique squeezed almost all the polymorphism out of actual  
> APL programs.

Part of my interest in using combining forms is for exactly this  
reason. Certain combinators like 'each', which takes a list and a  
quotation and calls the quotation for each value of the list as it is  
pushed onto the stack, are difficult to handle efficiently. The reason  
is that the quotation can use any amount of the stack as any  
combinator with an effect of type 'A b -> A' can be passed in. This  
means the programmer can write things like like 'random-boolean [pop]  
[+] if each', where the actual arity of the quotation passed to 'each'  
is indeterminable up until the moment it gets there. Obviously more  
grotesque examples can be constructed. As such, combinators like  
'each', while very useful, seem to require the implementation to use a  
stack. This issue evaporates if we know the function that is to be  
used with 'each' at compile time.

- John

[John Nowak]

On May 31, 2008, at 2:33 PM, Stevan Apter wrote:

> i think you can trace these ideas (and limitations) to two sources:
> (i) early APL implementations had to be squeezed into tiny memory, and
> (ii) the implementors were mathematicians, and the generating ideas
> behind APL were based on iverson's program for the reform and  
> regimentation
> of mathematical notation (see his book "A Programming Language".)  APL
> represented a series of compromises dictated by the existing  
> technology
> and the uses envisioned by the implementors.

While I'm sure this holds true for APL, what about FP? It seems no  
real concern was given to FP's efficiency, and at least with FL, the  
intended use case seems more general than that of APL's.  
Unfortunately, I've not been able to find anything by Backus  
indicating why he chose to not have first class functions. I'm sure  
the purpose is to make it easier to prove program properties, but more  
detail would be nice.

> fixed forms instead of HOFs is an interesting idea.  as always with  
> me,
> the question is what loss of expressiveness (if any) will result.

The immediately obvious consequence is that you lose 'compose' and  
'curry' as both exist to return functions as objects. This is less  
detrimental than it may seem at first. As I showed in the email that  
began this thread, implementing 'map' in terms of 'fold' makes use of  
'compose' in the Joy-like version, but gets on fine without it in the  
combining form version.

Here's another example. In Factor, 'map' requires a quotation with a  
stack effect of ( old -- new ). Sometimes though, it is nice to have a  
function 'map-with' that makes repeated use of a value on the stack  
and keeps it around after 'map-with' is finished. For example:

    -- yields '8 { 5 6 7 }'
    8 { 3 2 1 } [ - ] map-with

We can define 'map-with' in Factor as such:

    : map-with [ dupd ] swap compose map ;

In the language I'm proposing, we'd do this instead:

    map-with(F) = map(dupd F)

One last example. Let's say we want a function 'make-hash-table' that  
takes a function to use for equality. It would have the type 'A [b b -
 > Bool] -> A (Hashtable b)'. To get this to work without first class  
functions, we simply make 'make-hash-table' into a combining form.  
Since the function is hidden in the Hashtable object and cannot be  
accessed in any way, there's no problem.

To be clear, there absolutely would be a loss in expressiveness, and I  
don't mean to gloss over it. It's something you'd be certain to  
eventually bump into. I do think, however, that it is perhaps not as  
severe as it may initially seem.

- John

[stevan apter]

----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@...>
Sent: Saturday, May 31, 2008 2:09 PM
Subject: Re: [stack] Joy's relationship to FP + a Joy variant with combining forms

> On May 31, 2008, at 2:33 PM, Stevan Apter wrote:
>
>> i think you can trace these ideas (and limitations) to two sources:
>> (i) early APL implementations had to be squeezed into tiny memory, and
>> (ii) the implementors were mathematicians, and the generating ideas
>> behind APL were based on iverson's program for the reform and
>> regimentation
>> of mathematical notation (see his book "A Programming Language".)  APL
>> represented a series of compromises dictated by the existing
>> technology
>> and the uses envisioned by the implementors.
>
> While I'm sure this holds true for APL, what about FP? It seems no
> real concern was given to FP's efficiency, and at least with FL, the
> intended use case seems more general than that of APL's.
> Unfortunately, I've not been able to find anything by Backus
> indicating why he chose to not have first class functions. I'm sure
> the purpose is to make it easier to prove program properties, but more
> detail would be nice.

you might want to pick up a copy of this:

http://www.abebooks.com/servlet/SearchResults?an=iverson&sts=t&tn=algebra+algorithmic&x=0&y=0


>
>> fixed forms instead of HOFs is an interesting idea.  as always with
>> me,
>> the question is what loss of expressiveness (if any) will result.

it's the *net* effect i'd be interested in.  my experience is that
this cannot be predicted based on small examples.  how does expressiveness
scale as applications grow?  such measures are invariably subjective, and
consist of comparisons such as "in X i could do Y this way; in Z i have to
do ...".  over time, these comparisons accumulate, and indicate where *useful* expressiveness has been lost.  so i suppose i use
"expressiveness" to cover
more than just how easy it is translate an algorithm into code.  without
invoking the full power of the strong sapir-whorf hypothesis i think it's
safe to say that properties of the pl contribute to the trajectory we
take through the mental search space of algorithms.  do i need to give
examples to make the case for this claim?

i know, this is a hobbyhorse of mine -- add up all the factors that make up
a real-world programming environment (and yes, there are many kinds) and then
ask:  over time, how does this language perform?  only to the extent that
formal properties of the language impinge on overall performance are my
interests engaged.  (i am repeatedly appalled by how much code java
programmers have to read and write to accomplish the simplest tasks.)

>
> The immediately obvious consequence is that you lose 'compose' and
> 'curry' as both exist to return functions as objects. This is less
> detrimental than it may seem at first. As I showed in the email that
> began this thread, implementing 'map' in terms of 'fold' makes use of
> 'compose' in the Joy-like version, but gets on fine without it in the
> combining form version.
>
> Here's another example. In Factor, 'map' requires a quotation with a
> stack effect of ( old -- new ). Sometimes though, it is nice to have a
> function 'map-with' that makes repeated use of a value on the stack
> and keeps it around after 'map-with' is finished. For example:
>
>    -- yields '8 { 5 6 7 }'
>    8 { 3 2 1 } [ - ] map-with
>
> We can define 'map-with' in Factor as such:
>
>    : map-with [ dupd ] swap compose map ;
>
> In the language I'm proposing, we'd do this instead:
>
>    map-with(F) = map(dupd F)
>
> One last example. Let's say we want a function 'make-hash-table' that
> takes a function to use for equality. It would have the type 'A [b b -
> > Bool] -> A (Hashtable b)'. To get this to work without first class
> functions, we simply make 'make-hash-table' into a combining form.
> Since the function is hidden in the Hashtable object and cannot be
> accessed in any way, there's no problem.
>
> To be clear, there absolutely would be a loss in expressiveness, and I
> don't mean to gloss over it. It's something you'd be certain to
> eventually bump into. I do think, however, that it is perhaps not as
> severe as it may initially seem.

i have the same hunch.


>
> - John
>

[John Nowak]

On Jun 1, 2008, at 11:30 AM, Stevan Apter wrote:

> you might want to pick up a copy of this:
>
> http://www.abebooks.com/servlet/SearchResults?an=iverson&sts=t&tn=algebra+algorithmic&x=0&y=0

Done! Thanks.

> without invoking the full power of the strong sapir-whorf hypothesis
> i think it's safe to say that properties of the pl contribute to the
> trajectory we take through the mental search space of algorithms.
> do i need to give examples to make the case for this claim?

Not for my sake at least; I agree completely.

- John

[William Tanksley, Jr]

John Nowak <john@...> wrote:
> In short, Joy is higher order and based on composition, and FP is
> first order and based on application. What I'm wondering is what a
> first order language based on composition would look like.

> One thing to note is that a combining form for quotation is no longer
> needed since it is impossible to create objects that represent
> functions.

Hmm. So is Forth a first-order language based on composition? Seems
that way. Mind you, Forth wasn't designed with that in mind, so its
syntax is a hodge-podge, but it does seem like its semantics are
comparable.

I'm tempted to muck about with defining a suite of words in Forth that
would give it the syntax you describe. Maybe after I get my current
project into releasable form.

> While FP does not allow the definition of new combining forms, such a
> facility is undoubtedly necessary for real programming. The syntax for
> this mimics use. Note that all variables are in uppercase so as to not
> clash with function names. Here is an example of how we can define a
> 'reverse-map' combining form in terms of the 'fold' combining form:

>     Combining form version:
>     reverse-map(F) = null fold(F cons)

I'm thinking that this works using pure textual replacement. Is this
right? If so, this is a perfect match for Forth (and more regular than
the current Forth conventions).

In short, I this looks like a nice model to give a concatenative stack
language disciplined access to its own source code.

> - John

-Wm

[John Nowak]

On Jun 12, 2008, at 10:53 AM, William Tanksley, Jr wrote:

> John Nowak <john@...> wrote:
>
>> In short, Joy is higher order and based on composition, and FP is
>> first order and based on application. What I'm wondering is what a
>> first order language based on composition would look like.
>>
>> One thing to note is that a combining form for quotation is no longer
>> needed since it is impossible to create objects that represent
>> functions.
>
> Hmm. So is Forth a first-order language based on composition?

Roughly speaking, yes. Forth's words aren't pure in the same sense as  
functions are in Joy and FP, but if you ignore that, I'd say it  
qualifies. Forth also does have second-order combining forms such as  
IF and LOOP. Of course, they're not nearly as rich as they could be.

> Seems that way. Mind you, Forth wasn't designed with that in mind,  
> so its
> syntax is a hodge-podge, but it does seem like its semantics are
> comparable.

Ignoring side effects, I'd agree.

>> Combining form version:
>> reverse-map(F) = null fold(F cons)
>
> I'm thinking that this works using pure textual replacement. Is this
> right? If so, this is a perfect match for Forth (and more regular than
> the current Forth conventions).

Yes and no. In 5th, reverse-map has its own type, and the expression  
given to it is type checked independently of reverse-map's definition.  
In other words, no expansion is necessary, and hence type inference  
remains local. In an untyped language like Forth, textual replacement  
would be a sufficient way of explaining things, although you may wish  
to share the code generated for the expression passed if it is used in  
multiple places (e.g. twice(F) = F F).

> In short, I this looks like a nice model to give a concatenative stack
> language disciplined access to its own source code.

Or, in the 5th view, a disciplined way of manipulating its own  
functions. This is in contrast to Joy's "undisciplined" way of  
manipulation where you can write combinators that seem to be more than  
the sum of their parts. For example, it becomes possible to write  
things like '[dup i] dup i' that fail to terminate even though no  
recursive combinator was employed. Of course, "undisciplined" is a  
horribly loaded way of saying this.

- John

[William Tanksley, Jr]

John Nowak <john@...> wrote:
> William Tanksley, Jr wrote:
>> In short, I this looks like a nice model to give a concatenative stack
>> language disciplined access to its own source code.

> Or, in the 5th view, a disciplined way of manipulating its own
> functions.

You're right; the access this provides to the source code is extremely limited.

> This is in contrast to Joy's "undisciplined" way of
> manipulation where you can write combinators that seem to be more than
> the sum of their parts. For example, it becomes possible to write
> things like '[dup i] dup i' that fail to terminate even though no
> recursive combinator was employed. Of course, "undisciplined" is a
> horribly loaded way of saying this.

Some programmers prefer not to receive punishment from compilers...
They seem to believe that compilers dish out enough punishment without
the compiler author adding more. :-)

So I don't think "undisciplined" is so horrible.

> - John

-Wm

[pml060912]

--- In concatenative@..., "William Tanksley, Jr"
<wtanksleyjr@...> wrote:

>
> John Nowak <john@...> wrote:
> > In short, Joy is higher order and based on composition, and FP is
> > first order and based on application. What I'm wondering is what a
> > first order language based on composition would look like.
>
> > One thing to note is that a combining form for quotation is no longer
> > needed since it is impossible to create objects that represent
> > functions.
>
> Hmm. So is Forth a first-order language based on composition? Seems
> that way. Mind you, Forth wasn't designed with that in mind, so its
> syntax is a hodge-podge, but it does seem like its semantics are
> comparable.
>
> I'm tempted to muck about with defining a suite of words in Forth that
> would give it the syntax you describe. Maybe after I get my current
> project into releasable form.

Just as a reminder, my occasional work on Furphy is about that:
http://users.beagle.com.au/peterl/furphy.html - PML.