Vocabulary/SpecialCombinations

From J Wiki
Jump to navigation Jump to search

Go straight to: the TABLES   Back to: Vocabulary

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

Information.png 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.


J typically executes verbs one by one, right-to-left, each verb not knowing what is coming next

   ? 1e6 $ 2   NB. 1 million random booleans
0 1 1 0 0 0 0 1...

Interpreted literally, J first makes a separate copy of the large noun (1e6 $ 2) in the form of a list. Then J creates random numbers from the list.

If J knew that we were only going to create the booleans, it could have done so directly without making the copy.

However, if we make a compound verb using modifiers, then J can (and does) tell what's coming next

   1e6 ?@$ 2   NB. 1 million random booleans
0 1 1 0 0 0 0 1...

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 '? 1e6 $ 2'
0.0045466 9.43808e6
   ts '1e6 ?@$ 2'
0.0003914 1.0495e6

The compound verb runs much faster and takes much less space, because no copy of the array is needed and the loops are tighter. 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

   1e6 ?@$ 2   NB. (?@$) is a single verb, having parts (?) and ($)

J first executes (?@$) which produces the SC.

Note: the noun 2 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

   randomof=: ?@$
   ts '1e6 randomof 2'
0.0003336 1.04989e6

This shows that randomof 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

   randomof
?@$

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 ($)

   '`random enshape' =: ?`$

In the following sentence, the SC is not recognized:

   ts '1e6 random@enshape 2'
0.0038908 9.43898e6

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 '1e6 random@enshape 2'     NB. the worst of times
0.0038466 9.43898e6
   ts '1e6 random@enshape f. 2'  NB. the best of times
0.0014436 1.0504e6

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, and it must be abandoned: no later execution will refer to the value.

For example, consider (i. 40) (+ * -) 5 when executed from a script. (40) and (5) are aliased, because the script holds a copy of them. (i. 40) is anonymous and unaliased. In the fork, - is executed first: at that point (i. 40) is not yet abandoned because it will be an argument to the later execution of +. When + is executed, (i. 40) is abandoned and the addition will be done in place. The results of both the addition and the subtraction are anonymous, unaliased, and abandoned, and thus the multiplication will be done in place.

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


Self-Effacing References

A name inflected with _:, as in name_:, is a self-effacing reference. A self-effacing reference is replaced by the value of the name, but then the name is immediately deleted. This can be used:

  • as an easy way to remove the name from the namespace
  • as a mechanism to extract the value of a verb in a sentence, without fully fixing it. Compare [:#names with [:#names f. and [:#(t_:=.names)
  • to make the value of a private name inplaceable. This will happen if there are no other extant references to the value and the reference is in the body of the definition (i. e. not inside ".).

Thus:

   decr =. {{ bigname =. 1e6 ?@$ 0  NB. big private name
>: bigname  NB. not inplace
y }}
   effacingdecr =. {{ bigname =. 1e6 ?@$ 0  NB. big private name
>: bigname_:  NB. inplace
y }}
   7!:2 'decr 0'
16778304
   7!:2 'effacingdecr 0'
8390048

NOTE: name_: must not be used in a sentence that has already used the value of name. Such use may crash the J session. Example: (# a::) , # a

Virtual Nouns

A virtual noun is a noun whose value is a reference to a contiguous part of another noun. They are produced automatically as sentences are executed and you are free to be oblivious to their existence. If you understand some details you might be able to write faster code in some cases.

Creation of Virtual Blocks

A virtual block is created when

  • a verb produces a result that is a contiguous part of one of its arguments, as in
    • ({. y)
    • (x {. y)
    • (}. y)
    • (x }. y)
    • (}. y)
    • (}: y)
    • (x $ y) when the result is no larger than y
    • (x ($,) y) when the result is no larger than y
    • (, y)
    • (,"n y)
    • (,. y)
    • (,."n y)
    • (x { y) when x is a numeric array in consecutive ascending order
    • (x , y) when there is spare room in the allocation for x, and x is a direct datatype
  • a partitioning modifier operates on a subarray of y . The partitioning modifiers are
    • ([x] u"n y)
    • (x u;.0 y)
    • ([x] u;.(_2 _1 1 2) y)
    • (x u;.(3 _3) y)
    • (u/ y)
    • (u\ y)
    • (u/\. y)
    • (u\. y)
    • (u/. y)
    • (x u\ y)

The partitioning modifiers pass virtual arguments into the verb u.

Realizing Virtual Nouns

Virtual nouns are passed around the interpreter like ordinary nouns and are deleted when they are no longer needed. Sometimes a virtual noun must be realized, that is, it must be replaced by a normal noun with a copy of the data. This happens in the following cases:

  • the virtual noun is assigned to a name
  • the virtual noun is made a part of another noun, by boxing it or binding it to a modifier
  • the noun containing the value referred to by the virtual noun is deleted
  • the virtual noun is passed into a DLL using the cd verb

Realizing a virtual noun takes time and space.

Special Forms

Unlike most special combinations, virtual blocks can work for you when primitives are separate. For example,

   +/ , array

will use a virtual array for the result of , and +/ will operate on that virtual array; the array is not copied.

Partitioning modifiers support some special forms:

BoxAtop

The forms

  • < y and <"n y
  • [x] <@f y
  • [x] <@(f"n) y
  • [x] <@:f;.0 y
  • [x] <@:f;.(_3 _2 _1 1 2 3) y
  • x <@:f/ y
  • <@:f/\. y

avoid generating individual boxing for the result-cells of f. The @: can be replaced by @ if f has infinite rank, and &:, &, and ([: < f) can also be used.

If u in a partitioning modifier is simply <, the result is created in such a way that its subsequent assignment to a name has less overhead than normal.

Note that according to these rules, <@:f@:g is not a BoxAtop verb, but <@:(f@:g) is. You should prefer the BoxAtop form.

Immediate Opening

Consider the execution of

   s =: 1e6 $ 'a very long string'
   ]subs =: 4 2 1?@$ 1e5   NB. (start,length) of 4 long substrings, each a 2x1 array
 1991
69444

 8355
11867

45741
14872

70027
92791
   #@> subs <;.0 s  NB. extract each substring, then take the length
69444 11867 14872 92791
   subs (#@>)@:(<;.0) s   NB. another way to do the same thing
69444 11867 14872 92791
   7!:2 '#@> subs <;.0 s'   NB. space required - each string is realized
297024
   7!:2 'subs (#@>)@:(<;.0) s'  NB. space required without realizing each string
2496

What makes (#@>)@:(<;.0) use so much less space is that the first verb executed (<;.0) knows that its result will be immediately opened by the next verb. Taking advantage of this fact, the first verb did not realize the virtual blocks before putting them into the boxed result. This can happen only when the two verbs are joined by a modifier - not when they are unconnected words as in (#@> subs <;.0 s).

This case is detected whenever an opening verb O is executed immediately after a BoxAtop verb B (see above) within a modifier (@ @: & &: &.&.: hook fork). Example: (O@:B). Note that there cannot be the possibility of an intermediate collection step between B and O. For example, O@(<@f;.1) is an immediate execution of O, but O@:(<@f;.1) is not because (<@f;.1) has finite left rank and its results might have to be assembled before being passed to O.

The opening verbs O are

  • ; y
  • > y
  • any modifier producing a verb that directly executes only opening verbs on its arguments

In addition, certain verbs inherit opening-verb status if the verb executed on their result is an opening verb:

  • |. y
  • |: y
  • , y
  • ] y
  • [ y
  • x ] y (inherits only for the y argument)
  • x [ y (inherits only for the x argument)
  • x ; y (inherits only for the y argument)


Supporting more verbs as opening verbs is a continuing project.

Sentences From Explicit Entities

Unless your sentences are very simple, the time spent parsing them is negligible. For sentences with small arguments, especially with complex verbs, parsing time may be comparable to the time to execute the verbs: if you execute such sentences repeatedly, either in a loop or in a repeated execution of an explicit entity, you may find the following techniques helpful:

Nameref Caching

Nameref caching causes the names of non-nouns in your explicit definition to be looked up just once and remembered. Subsequent executions of the same reference will use the result of the previous lookup. The technique is useful for most J programs, but is especially valuable if you have long search paths. See the full discussion here.

Pre-Parsed Parenthesized Primitives (PPPP)

When possible, JE will detect sequences that can be parsed before an explicit entity is executed, and parse them during the definition of the entity.
That is, it parses them when the : conjunction is executed.

A pre-parsable fragment must meet the following requirements:

  • the fragment must be enclosed in parentheses
  • the fragment must contain only primitives (i. e. no names)
  • the fragment must not contain =. or =:
  • the fragment must not contain !: or m : where m is a noun
  • the fragment must not execute a verb

Example: in an explicit definition, the sentence

a =. a +&.> b

will parse the +&.> every time the sentence is executed, but in

a =. a (+&.>) b

+&.> will be parsed only at the time the explicit entity is defined.

Preexecuting verbs with (( ))

Normally, PPPP will not pre-parse a fragment that contains the execution of a verb. This is because some such fragments consume a great deal of memory: (i. 1e8) for example.

If you enclose a fragment in double parentheses, it will be pre-parsed even if it executes verbs, provided it meets the other requirements for PPPP. An example:

a =. (('Name';'Value')) , table

The table header will be computed at definition time rather than at execution time.

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.

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.

If the search requires tolerant comparison, the tolerance is always the tolerance in effect when the search was created.

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

!.n to change comparison tolerance

Remove fixed list of items -.&n y

-.!.t to change comparison tolerance

When -.&n y is executed, The precomputed table is used only if the items of y and n have the same rank
Intersect with fixed list of items ([ -. -.)&n y

([ -. -.!.t) to change comparison tolerance

When -.&n y is executed, The precomputed table is used only if the items of y and n have the same rank;
The compound is implemented as ([ -.!.0 i.)
Which cells of y match m-items? e.&m y e.!.n to change comparison tolerance
Find index of first/last cell of y that does/does not match an m-item (e. i. 1:)&m y or
(i:&1@:e.)&m y
i: in place of i. for last cell

0 in place of 1 for mismatch
e.!.n to change comparison tolerance

Note: the combination must be applied with rank < 2
Count number of cells of y that match m-items ([: +/ e.) or
+/@e.&m y
e.!.n to change comparison tolerance
Do any cells of y match an m-item? ([: +/ e.) or
+./@e.&m y
e.!.n to change comparison tolerance
Do all cells of y match an m-item? ([: +/ e.) or
*./@e.&m y
e.!.n to change comparison tolerance
Get indexes of cells of y that match m-items ([: I. e.) or I.@e.&m y e.!.n to change comparison tolerance

Whole-Array Operations

What it does Type;

Precisions;
Ranks

Syntax Variants;

Restrictions

Benefits;

Bug Warnings

Calculate rank of a noun #@$ y
([: # $) y
@: in place of @
Calculate number of atoms in a noun #@, y
*/@$ y
([: # ,) y
([: */ $) y
@: in place of @
Is the noun empty? (0 e. $) y
Is the noun nonempty? *@#@, y
Does the noun have items? *@# y
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 creates a virtual noun
Combine axes (r) and (r+1) ,/"(-r) y creates a virtual noun
Combine axes (-r) and (-r)+1 ,/"r y creates a virtual noun
Combine axes 0 and 2 in place of axis 2 ,./ y creates a virtual noun
Combine axes r and r+2 in place of axis r+2 ,./"(-r) y creates a virtual noun
Box items of array (except the last one, if it is already boxed) ;/ y and ;/"r y linear time. <"_1 y (or <"r y) is preferable if y is not already boxed or you want the boxing to apply to all cells.
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
Intersection x ([ -. -.) y Supported as a primitive member of the i.-family

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 any x ];.0 y or [;.0 avoids creating indexes
Operations on subarrays any x u;.3 y

x u;.3 y

;._3 in place of ;.3 avoids building cell indexes. Fastest when x has 1 or 2 columns. Larger x is processed by recursion over pairs of columns

Selections

What it does Type;

Precisions;
Ranks

Syntax Variants;

Restrictions

Benefits;

Bug Warnings

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 \:

Principles Applying To Intervals/Subarrays/Partitions

Many of J's modifiers perform partitioning of an argument: they split the argument into possibly contiguous subarrays and execute a verb on each partition. The simplest partitioning modifier is rank ([x] f"r y). Others are f;.n f\ f\. . Further, any compound verb of less than infinite rank (such as +:@*) begins with an implicit step of partitioning by rank. This section gives information about the assembly of the partitioned results and how you can write the function f for greatest efficiency.

  • The results of executing f on each partition are stored one by one.
    • As long as the shapes and precisions of the results are the same, the results are stored as items of a single array
    • If the precision changes, old and new values are converted to the new common precision as required
    • If the shape changes, results with a different shape are stored separately in a boxed array
  • After all results have been received, they are collected into a single result array. If there was no change of shape, this step is trivial.
  • If f is of the form <@(g), the interpreter can be sure that there will be no change of precision or shape. In this case the final result will be created with recursive usecounts, which saves a little time.
  • If the compound <@(g) is used in a context in which it is known that the result of the compound will be immediately opened (examples: ;@:(<@(g)) or +:each@:(<@(g))), extra efficiencies are possible, including storing virtual blocks in the boxed result.
  • If the compound <@(g) is used in a context in which it is known that the result of the compound will be immediately razed (example: ;@:(<@(g))), part of the raze processing is performed during the assembly of the boxed result, to save a pass over the individual results.

Intervals

What it does Type;

Precisions;
Ranks

Syntax Variants;

Restrictions

Benefits;

Bug Warnings

Special functions [x] f;.n y

x f/. y

n e. _2 _1 1 2 and f is one of # $ {. {: avoids creating intervals
Reductions on intervals [x] f/;.n y

x f/. y

n e. _2 _1 1 2 and f is an atomic verb avoids creating intervals
Boxing intervals specified as start/length pairs x <;.0 y x has shape (n,2,1) streamlined processing
Boxing intervals specifies as start/end+1 pairs x (<;.0~ -~/"2)~ y x has shape (n,2,1) streamlined processing
Boxing result of function applied to intervals [x] <@f/;.n y

x <@f/. y
(f is any verb)

n e. _2 _1 1 2
Concatenated results on intervals ;@:(<@(u);.n) y

x ;@:(<@(u)/.) y

n e. _2 _1 1 2;

also [: ; (<@:(u);.n);
also [: ; (<@:(u)/.) dyad;
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 an atomic associative 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;
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 ]
Apply dyads to infixes (or entire axes) of length 2 2 f/\ y a good alternative is ({. f {:)

Partitions

Note: Partitions (x u/. y) are processed through the same code as (x u;.1 y) and inherit its special code as well.

What it does Type of y argument;

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 items per partition x #/. y

x $/. y

avoids building argument cells of y
First or last item in each partition x {./. y

x {:/. y

avoids building argument cells of y
Count number of items per partition, and first item numeric list; if x is boolean, any numeric x (#,{.)/. y also ({.,#) avoids building argument cells of y
Count number of items per partition, and index of first item x (#,{.)/. y also ({.,#) avoids building argument cells of y and avoids forming i.@# y
Boolean reductions on partitions Boolean x +//. y = <. >. in place of + avoids building argument cells
Sum on partitions Any numeric type except integer x +//. y <. >. in place of + avoids building argument cells
Min/max on partitions Any numeric type x <.//. y >. in place of <. avoids building argument cells
Find mean of each partition Any numeric type x (+/ % #)/. y avoids building argument cells
Box partitions Any x </. y avoids building argument cells
Group equal items by index Any (</. i.@#) y avoids building argument cells and i.@# y

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 extended integer 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, or of lower rank than y If x is a positive power of two, (-x) 17 b. y is better to get remainder
x #: y with x in the form (0,power of 2)
Integer quotient/remainder integer x #: y with x in the form (0,positive divisor) Fast when the leading atom of x is 0.
Find index lists of nonzeros in a multidimensional array any numeric ((0 (0}) $) #: I.@(0&~:)) y
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

Accurate Accumulation

What it does Type;

Precisions;
Ranks

Syntax

Restrictions

Benefits;

Bug Warnings

Compensated summation float of any rank +/!.0 y Gives extra precision if the (running sum plus one element) has more significance than a float. Details here
Accurate dot-product float of any rank x +/@:*"1!.0 y
Performs the calculation at twice the precision of floats. Details here

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
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
Array inner product x +/@:* y faster than +/ x * y
Vector inner product (dot product) x +/@:*"1 y Even if you have just one dot-product of two vectors, you should use this combination.
It has Integrated Rank Support, which means you should NOT assign +/@:*"1 to a name if you need to apply rank! If you do, x name"r y will be slower than x +/@:*"1"r y would be. Similarly, you should not assign +/@:* to a name, because x name"1 y would not be a special combination.
Gaussian function float; integer is converted to float x ^@:p. y less memory bandwidth
Convert near-0 values to exact 0 float; integer is converted to float x ((> |) * ]) y the comparison is intolerant and may be written with !.0; comparison of <: is treated as if <; any value near 0 is replaced with positive 0; also x (] * (> |)) y avoids intermediate result and can execute in place

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, the first being y. Each x-value is the place the next record would start, if a record starts at that x. (If the first value in each record is the length, x would be (list + i.#list) 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
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
Check boxing level x (< L.) y also <: > >: Stops processing y early if possible
i. on sorted lists integer cells of rank 1 x i.!.1 y supports IRS with i.!.1"n Faster; results unpredictable if atoms of argument-cells are not in nondescending order

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.