[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