# 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`
... where X and Y represent left and right arguments to the combinators.

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.)