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

John Nowak <[email protected]>
Newsgroups gmane.comp.lang.concatenative
Message-ID <[email protected]>
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
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.