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