Re: [stack] Joy's relationship to FP + a Joy variant with combining forms

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" <[email protected]>
To: "concatenative" <[email protected]>
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
>