-- The $: cheatsheet --
-- ischtche%uwaterloo.ca --
-- See also --
The $: primitive in J can be confusing to J beginners. The Vocab entry is at
best terse and at worst cryptic and mysterious: "$: denotes the longest verb
that contains it." It seems to produce counterintuitive results:
fibo =: 3 : 'if. 1 < y do. ($: y-1) + ($: y-2) else. y end.'
fibo 5
|stack error: fibo
| ($:y-1)+( $:y-2)
"But I gave it a proper base case!" you might think. "Where's the stack error?"
If only the vocab page was structured in a pedagogical way! Curse thee, Roger!
You and your infernal line-noise language!
-- Here's the deal --
Before you start using $:, familiarize yourself with the ^: (Power) and @.
(Agenda) conjunctions. (Ctrl+F for 'I KNOW THOSE' if you know those already.)
In its simplest form, u^:n y will apply u to y, n times. The dyadic version
x u^:n y simply translates to x&u^:n y , meaning that the x is kept constant.
But ^: can also accept a verb as its right operand. u^:v y translates to
u^:(v y) y and x u^:v y becomes x u^:(x v y) y . That is, the verb v uses
the values of x and y to decide how many times to iterate u on a per-use basis.
In particular, if v only ever gives a boolean result, then ^:v acts kind of
like an if-then statement: when v gives 1, you run u once, and when it gives 0
you do nothing. (It is, however, more powerful, as v can give 2 to run twice,
or _1 to try to do the inverse of u, or _ to run to a fixed point, and so on.)
NB. halve only if even
-:^:(0 = 2&|) 18
9
-:^:(0 = 2&|) 19
19
-:^:(0 = 2&|) 20
10
If ^: is an if-statement, then @. is a switch- or case-statement. If you have a
gerund f`g`h , then f`g`h@.0 will act like f, and f`g`h@.1 will act like
g, and so on. But again, the great power comes from the @.v form. You can pick
which of f or g or h to use on the fly: f`g`h@.v y is f`g`h@.(v y) y , and
likewise for the dyadic usage.
NB. do nothing if 0 mod 3
NB. double if 1 mod 3
NB. set to _ if 2 mod 3
]`+:`_: @. (3&|) " 0 i. 10
0 2 _ 3 8 _ 6 14 _ 9
So now you're thinking, ALRIGHT, I KNOW THOSE NOW. Great. I'll explain one
example using $: and then give you a bunch more to investigate yourself.
If you have a recursively defined function F where B is a base-case not
referencing F, R is a recursive case that does reference F, and C is a
boolean verb that is 1 when you recurse and 0 when you don't, then
F =: B ` R @. C
and you can use $: to refer to F in R.
For a totally original example I definitely in no way stole from the vocab,
let's try a factorial function. The definition in pseudocode:
fac is a verb
if y=0, then fac y is 1
if y>0, then fac y is y * fac y-1
Our test C is >&0 , the base case is 1: and the recursion is (] * fac@<:) .
So by the rule above,
fac =: 1: ` (] * $:@<:) @. (<&1)
fac 5
120
1: ` (] * $:@<:) @. (<&1) 7 NB. even use it inline!
5040
q: 1: ` (] * $:@<:) @. (<&1) 7 NB. and do things after!
2 2 2 2 3 3 5 7
What is happening in that last sentence is that the longest verb expression
containing $: is 1:`(]*$:@<:)@.(<&1) even though it's found in a sentence
with other verbs like q: . Here's a couple of actual working Fibonaccis:
] ` ($:@-&1 + $:@-&2) @. (1&<) " 0 i.10
0 1 1 2 3 5 8 13 21 34
(-&1 +&$: -&2)^:(1&<) " 0 i.10
0 1 1 2 3 5 8 13 21 34
To speak more generally, $: can be used within a tacit verb expression as
exactly what it claims to be: self-reference. It's notorious for being finnicky
(and rightfully so; recursion is not to be taken lightly) but if you understand
tacit J and recursion, it's not all that scary.
-- Exercises --
Exercise 1: Why does 3 : 'if. 1 < y do. ($: y-1) + ($: y-2) else. y end.' fail?
Hint: What is the longest verb containing $: in ($:y-1)+($:y-2) ?
Exercise 2: Implement the verb C using $: and tacit style. It satisfies the
recurrence (n C k) = (n % k) * (n-1) C (k-1) for all n and k>0, and
(n C 0) = 1 for all n. What is n C k?
Exercise 3: Implement the Ackermann function from the pseudocode below. Use $:
and tacit style.
ack is a verb
if m=0 then m ack n is n+1
if m>0 and n=0 then m ack n is (m-1) ack 1
if m>0 and n>0 then m ack n is (m-1) ack (m ack n-1)
test case: 3 ack 3 should be 61
Hint: Write it in the form f`g`h@.v .
Exercise 4 (HARD): Implement the Ackermann function from the pseudocode below.
Use $: and tacit style. You do not have to explicitly implement Iter.
Iter is an adverb
if y=0 then (f Iter) y is f 1
if y>0 then (f Iter) y is f (f Iter) y-1
ack2 is a verb
if m=0 then m ack2 n is n+1
if m>0 then m ack2 n is ((m-1)&ack2 Iter) n
Done correctly, ack2 will be more time/space efficient than ack from Exer. 3.
-- Answers --
1. In the statement ($: y-1) + ($: y-2) , $: refers to itself, not 3 : '...'.
2. C =: 1:`(% * $:&<:)@.(0 < ]) NB. these are the binomial coefficients k!n
3. ack =: >:@]`(<:@[ $: ])`(<:@[ $: [ $: <:@]) @. (, i. 0:) NB. many solutions
4. Do it yourself ;)