Vocabulary/SpecialCombinations
Go straight to: the TABLES Back to: Vocabulary
Special Combinations (SCs) Of Primitives: Why and How?
If you are a J learner, you can get by without knowing anything at all about the contents of this page.
Like many language processors, J performs optimizations. It has speed-ups and takes short cuts. In the vast majority of cases, these optimizations are transparent to you, the J programmer.
But occasionally it is possible to trick J into revealing that it has taken a short cut. Then, as part of your general debugging regime, this page is here to consult to assist in analysing your bug.
There's another reason why it's good to know, in a broad sense, what J is capable of doing at runtime. A prime feature of J is the many subtle ways it affords of combining primitives (and also user-defined verbs) to build more complex verbs. This is all the more remarkable when you consider that the verbs being combined are array-savvy: they aren't confined to working just with atoms, but can work with lists of practically unlimited complexity.
This opens up a whole new world of programming, vastly simplifying traditional algorithms such as matrix inversion and finite-state machines. But it may look as if it forbids you to take advantage of what you know about your own data to achieve more efficient code.
If you've been trained on a scalar language like C++, in which you work with an array by looping through its entries one-by-one, you can terminate a loop early at your own discretion, whereas whole-list verbs seem on the face of it to demand that all (notional) loops must run to completion.
This is far from being the case. There are decades of experience behind the J interpreter, plus its forerunner APL, during which the scope for many efficiencies with certain combinations of primitives have been recognised. The combinations themselves can be detected in your code and special algorithms brought into play as a result. These are the special combinations (SCs) we're talking about here. The backlog of practical experience is weighty enough that, in the vast majority of situations you're likely to encounter, some scope for underlying efficiency has already been recognised and exploited to make your code run faster than you might expect, going just on the primitives being combined.
You are free to ignore this hidden aspect of J when coding a verb. And it may be wise to do so when writing a first draft of your script. But knowing which combinations of primitives give this sort of benefit might change the way you code your verb. At any stage you can use J's built-in timer with your own sample data to check your conjectures and "count your winnings", so to speak.
Contents
- 1 Special Combinations (SCs) Of Primitives: Why and How?
- 1.1 At what stage are Special Combinations (SCs) recognized?
- 1.2 Naming a Special Combination (SC)
- 1.3 Using a Cover Name for a Primitive stops J from recognizing a Special Combination (SC)
- 1.4 Using a Special Combination (SC) in a Compound Verb
- 1.5 Execution In Place (EIP)
- 1.6 TABLES of Special Combinations (SCs) by Category
- 1.6.1 Searching and Matching Items: Fast List Operations (FLOs)
- 1.6.2 Searching and Matching Items: Precomputed searches
- 1.6.3 Whole-Array Operations
- 1.6.4 Subarrays and Substrings
- 1.6.5 Selections
- 1.6.6 Sorting and Ordering
- 1.6.7 Intervals
- 1.6.8 Infixes
- 1.6.9 Partitions
- 1.6.10 Diagonals and Polynomials
- 1.6.11 Assignments In Place (AIP)
- 1.6.12 Integer Operations
- 1.6.13 Mathematical Operations
- 1.6.14 Miscellaneous Functions
J typically executes verbs one by one, right-to-left, each verb not knowing what is coming next
a =: 1000 1000 ?@$ 0 NB. 1 million random values in a 1000 by 1000 table +/ , a NB. Add them up 500024
Interpreted literally, J first makes a separate copy of the large noun (a) in the form of a list. Then J sums the list.
If J knew that we were only going to take the total of the list, it could just have added up the values as it visited them, and not bothered with making the copy.
However, if we make a compound verb using modifiers, then J can (and does) tell what's coming next
+/@, a NB. (+/@,) is a single verb with parts 500024
How can we tell if J is making good use of that information? It shows up as an improvement in time and/or space.
Here's a tool: ts, to find the time and space used by a given sentence
ts =: 6!:2 , 7!:2@]
Let's use ts to compare the performance of two alternative sentences in which
- J must execute verbs (+/) and (,) in turn, not knowing what comes next
- J is given a compound verb to execute, which J can recognize as a whole
ts '+/ , a' 0.00509779 8.3897e6 ts '+/@, a' 0.00150066 1280
The compound verb runs about 3 times faster and takes much less space, because no copy of the array is needed. It's an example of a special combination (SC) -- a phrase that get special support in the J interpreter itself.
Such phrases are listed in each primitive-page under: "Use These Combinations". They are also described in tables below and in the J Dictionary: Appendix B: Special Code.
At what stage are Special Combinations (SCs) recognized?
J recognizes a special combination (SC) as soon as the modifier that creates it is executed.
A modifier is executed as soon as it gets its left [and right] operand[s].
Executing a modifier creates a derived verb. This derived verb can be executed later, but J recognizes a SC before the verb is executed, at the moment the verb is created.
In the example
+/@, a NB. (+/@,) is a single verb, having parts (+/) and (,) 500024
the template for the SC is (f/@,) -- where f is any verb -- and the modifier that produces the SC is (@).
J first interprets +/ and then executes (+/@,) which produces the SC.
Note: the noun a has not entered the picture yet.
A hook or a fork is a "modifier" for this purpose, and J can recognize a SC within it.
Naming a Special Combination (SC)
If you assign a special combination (SC) to a name, J can still recognize it as a SC
addall=: +/@, ts 'addall a' 0.00158736 1024
This shows that addall performs just as well as the SC: (+/@,).
Observation: there is no way to tell from the displayed value of a verb that it is a SC
addall +/@,
Using a Cover Name for a Primitive stops J from recognizing a Special Combination (SC)
J can only match primitives, not verb names, to its internal SC template.
Example: give names to the two verbs (+) and (,)
'`plus enfile' =: +`,
In the following sentence, some sort of SC is recognized
ts 'plus/@, a' 0.318667 1664
We can tell because the space required was low. But it is slow because the named verb: plus needed to be executed for each additional atom of (a).
In this sentence, a different SC is recognized
ts '+/@enfile a' 0.00545077 8.39021e6
We can tell because the space required is high: it is needed for the list: (,a), but it is much faster because (+/) does not need to execute a named verb repeatedly.
Remember: Giving cover names to primitive verbs interferes with code optimization.
But it doesn't matter if you give cover names to modifiers such as each and every .
If you simply must give cover names to primitive verbs in a tacit definition, use f. to permit J to recognize underlying SCs.
f. replaces all names with their definitions and forces J to re-scan for SCs.
ts 'plus/@enfile a' NB. the worst of times 0.322007 8.39059e6 ts 'plus/@enfile f. a' NB. the best of times 0.00179939 4736
Using a Special Combination (SC) in a Compound Verb
J recognizes a special combination (SC) even if embedded in a larger phrase.
See above for an instance of this: J recognizes the SC: +/ even inside the phrase (+/@,).
Execution In Place (EIP)
A J verb typically accepts an array y as an argument and returns a whole new array. But this is grossly inefficient if the new array is
- large
- nearly identical to the old array
- replaces it.
J recognizes situations in which the argument is no longer needed after the verb has been executed, and performs those operations in place, creating the result in the same area occupied by the argument.
In-place execution requires a supporting verb and a suitable argument.
The verbs that support in-place execution are:
- x , y can append to x in place, provided its precision does not have to be changed
- x m} y and x u} y can modify y in place, provided its precision does not have to be changed
- x v0`v1`v2} y can modify the result of v2 in place
- Any atomic verb whose arguments are all singletons - atoms or arrays containing only one atom - can put its result in place of such an argument.
- x + y, x - y, and x * y when the precisions are identical, provided the precision does not have to be changed
- noun forks (N0 V1 V2) allow inplacing if V1 or V2 support it
- verb forks (V0 V1 V2) allow inplacing if V0 or V1 support it
- verb forks (V0@[ V1 V2) and (V0@[ V1 V2) allow inplacing if V0, V1, or V2 support it (only one argument to V2 can be inplaced)
- ] and [
The list of verbs that support in-place execution is continually growing.
An argument can be rewritten in place in two cases:
- it is anonymous: an unnamed result of a previous execution in the sentence;
- it is a zombie: a name that will be reassigned with the result of the execution of the verb.
In addition, the argument must be unaliased: its value must not be referred to by any name other than a zombie name.
Examples
a =: 10000#'a' b =: a , 'b' NB. NOT in-place a =: a , 'b' NB. In-place because a is zombie a =: i. 3 b =: 1;a a =: a , 6 NB. NOT in-place because a is referred to by b b =: ('b' ,~ {.) a NB. , is in-place because the result of {. is anonymous a =: (] , {.) a NB. , is not in-place because by default zombies are not rewritten until the final assignment 9!:53 (1) NB. Allow early assignment to zombies (see below) a =: (] , {.) a NB. Now , is executed in-place
Early Assignment To Zombies
Consider the sequence:
]a =: 'abcdefghijkl' abcdefghijkl a =: ('z' ,~ 'y' ,~ ]) a a abcdefghijklyz
(a) is modified in place twice: because the value of (a) is going to be replaced, it is fair game for reassignment.
It follows that a zombie name may be modified even if the assignment is never executed.
]a =: i. 10 0 1 2 3 4 5 6 7 8 9 a =: ('b' ,~ 100 ,~ ]) a |domain error | a=: ('b',~100,~])a a 0 1 2 3 4 5 6 7 8 9 100
Note that the value of a has been modified with the intermediate result.
The change to the value of the argument is not guaranteed: if the verb cannot be executed in place, the value of the zombie name will not be modified until the assignment is executed.
You may prevent modification of zombie names before the final assignment with (9!:53 (0)).
Oddities
Verbs that may modify the current locale or path, or refer to names that are not arguments, are considered unsafe for assignment-in-place and are executed as if (9!:53 (0)) were in effect. Unsafe verbs include:
- explicit definitions
- ". y
- 6!:2, 7!:2, and all 18!:xx
- Any combination containing an unsafe verb
Normally this is all handled automatically. But if a name is redefined with an unsafe value, previously-defined names that refer to the redefined name will not be notified of the unsafe value:
9!:53 (2) NB. allow intermediate assignment to zombies recip =: % NB. A safe name appendsum =: [: recip ] , + NB. append (x+y) to the end of y, then take reciprocal: safe recip =: 3 : 0 y , value ) NB. The redefined recip is now unsafe, but appendsum is still believed safe value =: 0 1 value =: 5 appendsum value NB. Surprise! value was modified before recip was called
The error occurs only when a name is redefined. You can avoid such problems by any of the following means:
- Order your definitions so that names refer only to already-defined names
- If necessary redefine a name after its referents have been defined
- Set 9!:53 (0)
Other In-Place Sentences
Certain special sentence-templates are recognized and perform assignment in place (AIP).
TABLES of Special Combinations (SCs) by Category
Searching and Matching Items: Fast List Operations (FLOs)
Fast List Operations (FLOs) are a large and important family of SCs. They are summarized below in a highly condensed table, which repays close study.
Why are FLOs needed? Consider the following phrase
(x < y) i. 1
This finds the first position where x is less than y. But in the process it computes the entire Boolean list (x < y) before starting to look (i.) for the first 1.
On the other hand, the following phrase uses a FLO
x i.&1@:< y
which happens to be the first FLO in the table below, (i.&1@:f), with f replaced by < This terminates as soon as it finds a position where x is less than y. Potentially this is a huge performance improvement.
What It Does Type;
Precisions;
RanksSyntax Primitives permitted in place of f Variants;
Restrictions
Benefits;
Warnings
Find first place where x f y is true Permitted: Boolean, integer, floating point, byte, symbol (not unicode).
x and y need not be the same precision.x (f i. 1:) y x i.&1@:f y = ~: < <: > >: e. E. Permitted: (f!.0) (parentheses obligatory!) to force exact comparison.
J recognizes FLO only if f returns an atom or list.Avoids computing entire x f y
Note: if f is e. the combination must have rank < 2Find first place where x f y is false x (f i. 0:) y x i.&0@:f y = ~: < <: > >: e. Find last place where x f y is true x (f i: 1:) y x i:&1@:f y = ~: < <: > >: e. Find last place where x f y is false x (f i: 0:) y x i:&0@:f y = ~: < <: > >: e. Count number of places where x f y is true x ([: +/ f) y x +/@:f y = ~: < <: > >: e. E. Is x f y true anywhere? x ([: +./ f) y x +./@:f y = ~: < <: > >: e. E. Is x f y true everywhere? x ([: *./ f) y x *./@:f y = ~: < <: > >: e. For what indices is x f y true? x ([: I. f) y x I.@:f y = ~: < <: > >: e. E.
Searching and Matching Items: Precomputed searches
The search m&i. y gives the same result as m i. y, but it has two stages: first m&i. is executed, then m&i. y does the search.
The i.-family of verbs do a lot of preprocessing of the arguments before performing a search: building hash tables, trees, etc. This preprocessing can be done for the m operand at the time m&i. is executed. So, if the same table is going to be searched often, you can save a lot of time by creating a verb v =: m&i. which will do all the indexing for m at the time of its definition; when you apply that verb to an argument y, only y will need to be preprocessed: a big savings if the search space m is bigger than y.
An m-item is an item of the m operand. All these combinations have the bug that if y does not have cells whose shape is the shape of an m-item, an error is signaled rather than quietly indicating no match. Some of the combinations have other bugs noted below.
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Warnings
Find first/last match m&i. y i: in place of i. for last match
!.0 for exact comparison
Which cells of y match m-items? e.&m y e.!.0 for exact comparison Find index of first/last cell of y that does/does not match an m-item (e. i. 1:)&m y i: in place of i. for last cell
0: for mismatch
Note: the combination must be applied with rank < 2 Count number of cells of y that match m-items +/@e.&m y Do any cells of y match an m-item? +./@e.&m y Do all cells of y match an m-item? *./@e.&m y Get indexes of cells of y that match m-items I.@e.&m y
Whole-Array Operations
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Operations on a flattened array x ({ ,) y
x ({. ,) y
x (}. ,) y
x (e. ,) y
f/@, y
(f is any verb)or @: & &: in place of @ Avoids copying the array to compute (,y) Combine first 2 axes (axes 0 and 1) ,/ y linear time Combine axes 1 and 2 ,./ y linear time Box items of list ;/ y linear time (like <"_1 y) Join contents of boxed items along first axis ,&.>/ y Bug warning: Atomic replication is inaccurate. OK if contents of same rank. Better to use <@; y Join contents of boxed items along axis 1 ,.&.>/ y Applying f/ after g
(f and g are any atomic verbs)
x f/@:g y
x ([: f/ g) y
avoids recopying arguments Reshape to exactly x x ($ ,) y Supported as a primitive by ($ ,)"n
Subarrays and Substrings
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Extract multiple substrings into a list Boolean list, byte list x ;@:(<;.0) y or [: ; <;.0 avoids boxing, avoids creating subarrays Extract substring/subarray table or list x ];.0 y or [;.0 avoids creating indexes Operations on subarrays list or table u;.3 y
x u;.3 y
;._3 in place of ;.3 avoids building cell indexes. Apply ;.3 _3 at rank 2 or lower
Selections
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Razed selections x (;@{) y also x ([: ; {) y Fetch from multiple index lists (each row of x is one index list into y) x (<"1@[ { ]) y avoids boxing x Translate characters from q to p byte (p {~ q i. ]) y also ((q i.]) { p"_) y and (q&i. { p"_) y Composite item the x arrays are the same precision and not boxed, extended integer, or rational name =: i} x0,x1,...,xm,:xn =. in place of =:
If there are 2 x's, i may be Boolean or integer, but if more than 2 x's, i must be integer.
No parentheses allowedavoids catenation and lamination
Sorting and Ordering
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Find ordinal numbers of y (the relative rank of each item of y in the sort order /:@/: y
/:@:/: y
not
([: /: /:) y;
\: is not specialbetter than /:^:2 y Find index of first/last occurrence of largest/smallest value integer or floating-point list (i. <./) y
(i. >./) y
or i: it actually does (i. >.!.0/) etc.; is faster than 0 ({ /:~) y Find xth-largest value of y x is a Boolean or integer atom, y is an integer or floating-point list x ({ /:~) y not \: Partitions y using a randomly-selected
pivot: time and space results
are variableFind the index of the xth-largest value of y x is a Boolean or integer atom, y is an integer or floating-point list x ({ /:) y not \:
Intervals
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Reductions on intervals f/;.n y
x f/;.n y
n e. _2 _1 1 2 and f is an atomic verb avoids creating intervals Boxing intervals <@f/;.n y
x <@f/;.n y
(f is any verb)n e. _2 _1 1 2 Concatenated results on intervals ;@:(<@(u);.n) y n e. _2 _1 1 2;
also [: ; (<@:(u);.n);
also (<@(u);.n) provided u has infinite monadic rank
Parentheses required around u unless <@u is a single word x is a Boolean list (not an atom or an integer list with values 0 or 1) x ;@:(<@:(u);.n) y Concatenated running totals on intervals (running total, but total is reset at start of each interval) ;@:(<@(f/\);.n) y
x ;@:(<@(f/\);.n) y
(f is any verb)n e. _2 _1 1 2;
also [: ; (<@(f/\);.n);
also <@:(f/\)Feature: If x is all 0, produces a 0-length table rather than an empty list
Infixes
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Reductions on infixes Boolean, integer, floating-point x +/\ y <. >. in place of + much faster than alternatives Integer reductions on infixes integer x (17 b.)/\ y also (22 b.) (23 b.) (25 b.) in place of (17 b.) much faster than alternatives Boolean reductions on infixes Boolean x +./\ y x positive
*. = ~: in place of +.
much faster than alternatives Mean on infixes integer and floating-point x (+/%#)\ y x positive
*. = ~: in place of +
much faster than alternatives Reshape infixes x ]\ y [ , in place of ] Apply dyads to infixes (or entire axes) of length 2 2 f/\ y fastest way to apply f when there are 2 items (faster than ({. f {:))
Partitions
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Reductions on prefixes/suffixes f/\ y and f/\. y very fast when f is atomic and associative Reductions on prefixes f/\.&.|. y faster than f/\ y unless f is atomic and associative Count number of equal items per partition x #/. y avoids building argument cells of y Count number of equal items per partition, and one copy of the item list x (#,{.)/. y also ({.,#) avoids building argument cells of y Boolean reductions on partitions Boolean x +//. y = <. >. +. * *. ~: in place of + avoids building argument cells Reductions on partitions integer, floating-point x +//. y <. >. in place of + avoids building argument cells Integer reductions on partitions integer x (17 b.)//. y (22 b.) (23 b.) (25 b.) in place of (17 b.) avoids building argument cells Find mean of each partition x (+/ % #)/. y avoids building argument cells
Diagonals and Polynomials
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Polynomial Multiplication x +//.@(*/) y avoids building argument cells Polynomial Multiplication (Boolean) Boolean x ~://.@(*./) y
x ~://.@(+./) y
x +//.@(*./) y
x +//.@(+./) yavoids building argument cells Polynomial Multiplication (bitwise) integer x (22 b.)//.@(17 b./) y avoids building argument cells Sum along diagonals +//. y avoids building argument cells Max/min along diagonals non-complex numeric >.//. y <. in place of >. avoids building argument cells Boolean reductions along diagonals Boolean +.//. y *. = ~: < <: > >: in place of +. avoids building argument cells Bitwise reductions along diagonals integer (17 b.)//. y (22 b.) (23 b.) in place of (17 b.) avoids building argument cells
Assignments In Place (AIP)
Certain sentences are calculated in place (without copying the array being modified). The sentence must match the template below exactly, with parentheses added only where noted, and with no other computation to the left or right of the template shown.
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Composite item in place b is Boolean; x and name are the same precision and shape and not boxed, extended integer, or rational name =: b} x,:name
name =: b} name,: x
=: in place of =.
Must be same name either side.
No parentheses allowedavoids making a new copy of name
Integer Operations
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Integer-result operations extended integer <.@f y
x <.@f y
(f is any verb)>. in place of <. Avoids non-integer intermediate results Integer divide integer x <.@% y
x >.@% y
@: in place of @ uses integer division Integer powers non-complex x, integer y x ^ y Uses repeated multiplication (avoids log) Powers mod(m) integer, extended integer x m&|@^ y
m&|@(n&^) y
Avoids the large result of exponentiation Integer [quotient/]remainder of power of 2 integer x | y with x a power of 2 If x is positive, (-x) 17 b. y is better to get remainder x #: y with x in the form (0,power of 2) Bitwise reduction and scan integer x (m b.)/ y
16 ≤ m ≤ 31
/\ /\. in place of / much faster than alternatives Convert an integer to a numeric list of digits Boolean, integer, extended integer "."0@": y @: & &: in place of @ fastest way, especially for extended integers
Mathematical Operations
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Mean with rank (+/ % #) y Supported as a primitive by (+/ % #)"n Arrays of random numbers x ?@$ y
x([: ? $)y
?. in place of ?
@: in place of @
# in place of $does not create x $ y e^{πy} ^@o. y handles large values of y Matrix product float or complex; integer is converted to float x +/ . * y heavily optimized, to the point of using external libraries devoted to matrix multiplication Vector inner product (dot product) x +/@:* y faster than +/ x * y
Miscellaneous Functions
What it does Type;
Precisions;
RanksSyntax Variants;
Restrictions
Benefits;
Bug Warnings
Follow a chain of variable-length records integer x and y {&x^:a: y
x {~^:a: y
<_ in place of a: Produces list of starting positions. Limit all values of x to at most #x, then append _1 to the end of x. Discard the final starting position of _1. Monadic power whose power depends on x x f@]^:g y
(f is any verb)
Applies f rather than x&(f@]) (very small improvement) Odometer function (y gives the size of each wheel; result is all readings from 0 0 0 0 to <: y) integer (#: i.@(*/)) y @: in place of @ CRC calculation x&(128!:3) Calculates the CRC lookup table when executed; x 128!:3 y computes it every time the verb is executed Box the indexes of identical items (</. i.@#) y
y </. i. # y
(</. i.@#) y uses less space Create list of integers from 1 to # y, or the reverse #\ y also #\. which is the reverse faster than >:@i.@# y Not-match x -.@-: y @: in place of @ Use this form for not-match. Supported as a primitive by (-.@-:)"n Fast agenda f0...fn@.v"0 y All f's must be atomic.
If v has rank 0 then "0 can be omitted
Bitwise operations on bytes byte u&.(a.&i.) y (u y) -: u"0 y avoids conversion to integer (m b.)/&.(a.&i.) y
x (m b.)&.(a.&i.) y
16 ≤ m ≤ 31
Notes
1. Syntax shows both the form taken by the Special Combination (SC) and whether it is valid for a monad (f y) or a dyad (x f y).
2. A verb f is said to be an atomic verb if
- f = f"0
- the shape of the value returned by f is either empty or the same as one of its arguments x or y
Most arithmetic verbs are atomic verbs, as are combinations of arithmetic verbs. Some combinations of atomic verbs are special combinations.