Vocabulary/SpecialCombinations

From J Wiki
Jump to: navigation, search

Go straight to: the TABLES   Back to: Vocabulary

Special Combinations (SCs) Of Primitives: Why and How?

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.

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

Syntax 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 < 2

Find 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;
Ranks

Syntax 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;
Ranks

Syntax 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;
Ranks

Syntax 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;
Ranks

Syntax 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 allowed

avoids catenation and lamination

Sorting and Ordering

What it does Type;

Precisions;
Ranks

Syntax 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 special
better 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 variable
Find 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;
Ranks

Syntax 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/\)

Infixes

What it does Type;

Precisions;
Ranks

Syntax 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 ] If x is an atom, the result is a table with shape 0,x; should be an empty list
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;
Ranks

Syntax 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;
Ranks

Syntax Variants;

Restrictions

Benefits;

Bug Warnings

Polynomial Multiplication x +//.@(*/) y avoids building argument cells
Polynomial Multiplication (Boolean) Boolean x ~://.@(*./) y

x ~://.@(+./) y
x +//.@(*./) y
x +//.@(+./) y

avoids 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;
Ranks

Syntax 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 allowed

avoids making a new copy of name

Integer Operations

What it does Type;

Precisions;
Ranks

Syntax 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;
Ranks

Syntax 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

Miscellaneous Functions

What it does Type;

Precisions;
Ranks

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