Essays/Combinators
This essay is a work in progress. (It's based largely on wikipedia page which also appears to be a work in progress, as that page had changed significantly after the second draft of this essay was written.)
Intro
Sometimes it's interesting to think about combinators. In one sense, J supports all of the classic combinators -- but in another sense, it does not. If we focus purely on the specification of classic combinators, without reference to the examples, we can achieve a rather simple implementation:
First draft effort
In terms of the argument *patterns*, they look like this:
| I | ] X
|
| K | X [ Y
|
| KI | X ] Y
|
| S | (F G) X
|
| B | F@:G X
|
| C | X F~ Y
|
| W | F~ X
|
| D | X (F G) Y
|
| B1 | X F@:G Y
|
| Φ | X F&:G Y
|
| Ψ | (F G H) X
|
There's a trick, though, which is that combinators are typically discussed with an assumption that they can take combinators as arguments. To emulate this aspect of combinators in J we could have some kind of "combinator execution environment which emulates the typical assumptions about syntactic treatment for combinators.
To achieve that in J, it's perhaps easiest to represent combinators as boxed gerunds with a boxed argument list.
Second draft effort
Here's an effort in that direction:
1APPLY=: {{ (E=:,<(,'@');<x,<'0';<y)`:6 '' }}
2I=: 0&{`''
3K=: 1&{`''
4KI=: 0&{`''
5VERB=: {{ (m{n)`:6 }}
6S=: {{ (((0 VERB y) (1 VERB y)))`'' }}`''
7B=: {{ ((0 VERB y) @: (1 VERB y))`'' }}`''
8C=: {{ (((0 VERB y) @: |.))`'' }}`''
9W=: {{ (((0 VERB y) @: ,~))`'' }}`''
10D=: {{ (((0 VERB y) @:(0&{, (1 VERB y) @:(1&{))`'' }}`''
11B1=: {{ (((0 VERB y) @:((1 VERB y)"0))`'' }}`''
12PSI=: {{ (((0 VERB y) @:(,&(1 VERB y)/))`'' }}`''
13PHI=: {{ (((0 VERB y) (1 VERB y) (2 VERB y)))`'' }}`''
Here, APPLY takes a gerund left argument and a right argument which will be passed to the gerund. The combinators are all expressed as gerund, and the combinators which expect "function arguments" look for gerunds, convert them to verbs, build a new verb and then convert that back to a gerund. This should approximate the typical expectations for combinators (but note that every application of a combinator or a function created using combinators needs APPLY, or something analogous.
Another combinator is the Y combinator:
Y=: {{ (0 VERB y (I APPLY y), K APPLY y)`'' }}`''
The Y combinator allows "anonymous recursion" by passing to the "recursive" function its definition as an argument.
(Caution: observe the distinction between lower case y (the right argument to a J verb) and upper case Y (the Y combinator), in contrast to the opening presentation of combinators at the top of this page.)
Some examples:
fac=: {{'a b'=. y if. 0>:b do. 1 else. b*Y APPLY a;b-1 end. }}`''
fib=: {{'a b'=. y if. 2>:b do. b else. (Y APPLY a;b-1)+(Y APPLY a;b-2) end. }}`''
With these definitions:
Y APPLY fib;7 21 Y APPLY fac;7 5040
Also, at least in the context of these definitions, we can use an abbreviated version of the Y combinator:
Y=: {{ (0 VERB y) y }}`''
This works with a variety of examples of the classic uses of combinators, but it's still a bit awkward.
SKI Combinator implementation
Instead, to implement combinators in J, we declare that a combinator is a monadic verb which takes a gerund as an argument and produces a gerund as a result. This closely matches the design and usage pattern of all classic combinator examples. Also, combinators are classically executed left to right, and we can achieve that with J verbs using parenthesis.
But this approach means we need modifiers to convert back and forth between the verb form of a combinator and the gerund form of a combinator. Borrowing from english (for example: walk -> walking), we'll represent the modifier which converts a verb to a gerund as ing. And to convert a gerund (which is a noun) back to a verb, we'll use ize (for example: crystal -> crystalize). Also, for convenience, we'll use a capital name for the verb form of combinators and a corresponding lower case name for the gerund form of combinators.
ing=: `''
ize=: `:6
NB. Ix = x
NB. Iy = y
I=: ]
i=: I ing
NB. Kxy = x
NB. Kmy = y
K=: {{ y"_ ing }}
k=: K ing
NB. Sxyz = (xz)yz
NB. Smny = (my)ny
S=: {{
y {{
m {{ ((m ize y)ize n)ize y }}y ing
}}ing
}}
s=: S ing
NB. Smny = myny
NB. combinators implicitly evaluate left to right, so parenthesis were only for emphasis
Thus, a J expression representing the SKSK phrase of combinator calculus would be ((S K ing) ize S ing) ize K ing or ((S k)ize s)ize k and the verb form of this phrase would be (((S k) ize s) ize k) ize or, pre-evaluating the expression, equivalent to K k.
(By now you should be able to recognize that the absence of a trailing ize on a multi-word combinator expression means that the expression produces its result in gerund form.)
But these expressions are still a bit long-winded. Typically, in combinator calculus, we have a sequence of combinators, we just want to evaluate that sequence. Or:
res=: resolve=: resultof=: {{ x ize y }}~/@|.
For example:
k`k -:&resultof s`k`s`k
1
Caution: In the above implementation, the values produced by resultof may be subtly different from the values produced by direct evaluation.
(K k) -: resultof k`k
0
(K k) =L:1 resultof k`k
┌───────────────┐
│┌─┬───────────┐│
││1│┌─────┬───┐││
││ ││┌─┬─┐│1 1│││
││ │││1│1││ │││
││ ││└─┴─┘│ │││
││ │└─────┴───┘││
│└─┴───────────┘│
└───────────────┘
(K k) =L:2 resultof k`k
┌─────────────┐
│┌─┬─────────┐│
││1│┌───┬───┐││
││ ││1 0│1 1│││
││ │└───┴───┘││
│└─┴─────────┘│
└─────────────┘
$L:1 K k
┌─────────────┐
│┌─┬─────────┐│
││1│┌─────┬─┐││
││ ││┌─┬─┐│2│││
││ │││1│1││ │││
││ ││└─┴─┘│ │││
││ │└─────┴─┘││
│└─┴─────────┘│
└─────────────┘
$L:1 resultof k`k
┌────────────┐
│┌─┬────────┐│
││1│┌────┬─┐││
││ ││┌─┬┐│2│││
││ │││1│││ │││
││ ││└─┴┘│ │││
││ │└────┴─┘││
│└─┴────────┘│
└────────────┘
To correct this problem, the definition of ing should be changed to
ing=: {{ {.u`''}}
BKW Combinator implementation
With this in mind, we can implement the B, C and W combinators. Multiple approaches exist. We can express these combinators in terms of the S, K and I combinators:
NB. caution: these were transcribed from wikipedia expressions and may not be accurate
b=: resultof s`(res k`s)`k
c=: resultof s`(res s`(res k`(res s`(res k`s)`k))`s)`(res k`k)
w=: resultof s`s`(res s`k)
Or, we can express them algorithmically, in much the way we specified the other set of combinators:
NB. Bxyz = x(yz)
NB. Bmny = m(ny)
B=: {{
y {{
m {{ m ize n ize z }} y ing
}}ing
}}
NB. Cxyz = xzy
NB. Cmny = myn
C=: {{
y {{
m {{
((m ize y)ize n
}}ing
}}ing
}}
NB. Wxy = xyy
NB. Wmy = myy
W=: {{
y {{
(m ize y) ize y
}}ing
}}
Y Combinator implementation and examples
The famous (or infamous) Y (or "fixed point") combinator may be implemented to these specifications as:
Y=: {{
{{y ize y}} y {{
m ize y {{
(m ize m)ize y
}}ing
}}ing
}}
This combinator lets us implement "recursion without a stack" (in the sense that pending executions are represented in the passed data structure instead of as contexts to be resumed). However, we have a minor difficulty with J's type system which needs to be resolved before we can implement classics like factorial or fibonacci. We defined combinators as taking an argument which is a gerund and which return a gerund. But for a function like factorial we want to work with numbers, and not gerunds. So, we need a mechanism to represent a numeric argument as a gerund.
arg=: {{<(,'0');y}}
(We can recover the numeric argument from this gerundial form using ize.)
With this approach we can define factorial as:
fac=: Y {{y {{'`f val'=. m`y
if. 1>:val do. 1 else. val*f arg val-1 end.
}}ing}}ing
This is, of course a gerund, we need to convert it to verb form (and package its argument) to use it:
fac ize arg 5
120
Or, for convenience:
factorial=: fac ize@arg"0
For example:
factorial i.7
1 1 2 6 24 120 720
(Of course, J's ! is much more efficient, but that's not the point here.)
We can also implement a fibonacci function (with even less efficiency, since it's doubly recursive):
fib=: Y {{y {{'`f val'=. m`y
if. 2>:val do. val else. (f arg val-1)+f arg val-2 end.
}}ing}}ing
fibonacci=: fib ize@arg"0
fibonacci i.9
0 1 2 3 5 8 13 21 34
(Finally, note that in our definitions of fib and fac we could have used u instead of m and the implementations would have worked just as well. However, m emphasizes that we're expecting a gerund here.)