October 20, 2013 at 01:38Programming language J. Look amateur. Part 4. Boxes and cycles. Conclusion
- Tutorial
Previous article in the programming language J. Look of an amateur. Part 3. Arrays
We are already faced with the fact that the noun in J is an array. Even on single constant values, vector operations are permissible. Together, all this makes up a convenient vectorial homogeneous programming environment.
However, it is obvious that arrays have their own limitations. Due to the fact that in J, by default there are only rectangular arrays, there is no way to create the so-called standard means jagged arrays. In addition, for lists consisting of heterogeneous elements, arrays are also not suitable.
To solve these problems, J provides tools for creating and using heterogeneous sequences - boxes. A box is a kind of container that can store an arbitrary element. An array of boxes is, accordingly, a kind of array of elements of type (void *). Therefore, for example, the first element of a boxed sequence can be a one-dimensional array, the second is a number, and the third is a matrix of integers.
In order to create a box, you need to call the monadic verb "<" to extract ("open") the elements from the box - the monadic verb ">":
The box itself is drawn in ASCII graphics. Now we extract the value of the box:
In order to add several elements to a box, the verb “;” is intended, which links the elements into a sequence of boxes:
To list the elements of such a boxed sequence, we can use the parts of speech that are already known to us. For example, the adverb “between”:
Or composition of verbs:
Next, use the verb "{" to extract the second element of the box:
In this example, one should pay attention to the following moment: the index call returns the boxed element of the array without unpacking it automatically.
From the previous expression, we can conclude that if we want to apply a certain verb to each element of the box, then each time the verb will take an operand wrapped in a box noun. In order to “pull out” an element from the array at each call, and after the action “shove” the result back into the box, you can use the already known union “&.”.
The union “&.” Applies the right verb to the operand, and the left verb applies to the result. Then the verb inverse to the right verb is applied to the result. Thus, we actually repeated the algorithm described in the paragraph above. We use this scheme to double each element of the box.
Due to the fact that the expression &.> Is used quite often, it is by default associated with the symbol each:
Note that in data processing speed, boxes are significantly (up to 3 orders of magnitude!) Lagging behind numerical arrays.
It is not always possible to present the verb in tacit form. For this, there are special constructions in J, which we will call imperative. First of all, these are operations “3:” and “4:” (do not confuse with the constant verbs “3:” and “4:”). The default operand is called “y”, the left is “x”. For instance:
If you feel that your imperative definition can be written in tacitic form, but you do not know how, then you can use the wonderful standard verb conversion:
To write multi-line verbs, similar constructions are used. Moreover, as in most functional languages, the last calculated value is returned, and therefore no analogue of the return statement is required. In multiline verbs, local variables can also be used - they are determined using the “=.” Operation. The symbol for ending the definition of the verb is the symbol ")"
J also has special constructs for checking conditions (.if), loops (.while), and some others. For more information, we recommend that you consult the documentation.
The recursive quicksort function was shown back in the introduction. Let's look at another example. We write in Python a simple function for determining the length of a sequence as if there was no such function built-in.
In order to write a recursive function for calculating the length of a vector in J, we will have to introduce an additional predicate verb to determine whether a noun is a sequence with at least one element. Call this predicate isa from the phrase "is array". We will write at the beginning an example of using this verb:
We will determine whether the operand is a vector of length more than 1, through the verb of extracting an element from the vector at a certain position. This is the verb "{"
Thus, if the expression “1 & {” fulfills correctly, then we consider that the operand is an array with a length greater than 1. Otherwise, return false (zero). We also added a ban on the dyadic call of the verb to the definition.
In order to simulate a condition check, we use the @. Union, which calls the verb from the box in that position, which is determined by the right operand. Those.
We need to return the length = 1 if the right operand is a vector of length = 1, i.e. if the predicate isa on this noun returns 0.
In place of the ellipsis, we must implement a recursive call to calculate the length for the tail of the transmitted sequence. We take advantage of the fact that the recursive call in J is implemented by the verb "$:". T.O. we get
The next step is to rewrite our verb so that the recursive call becomes tail. To do this, we will store the accumulated value in the left operand, and the verb, therefore, becomes dyadic:
The definition of a verb looks rather unappetizing, and in fact it is. We illustrate the algorithm of the verb len2 with an example in Python:
It is interesting to compare the speed of the code we wrote. To do this, use the verb “6!: 2”, which executes its right operand as many times as indicated in the left operand and returns the average run time of each run in seconds.
As you can see, in this case, using the built-in J tools is 3 orders of magnitude faster than our independent implementations. In addition, in J there is a restriction on the depth of recursion and there is no optimization of tail recursion.
It should be noted that the use of such recursive expressions is recommended only for training and in case of emergency.
We will not dwell on the use of the object-oriented approach to programming in J. For those interested, let’s say that there is support for OOP in J. Read more, for example, in Learning J.
Note, however, that J has special constructs for using namespaces that have syntax similar to OOP toolkit.
The beginning of a new namespace should begin with the expression:
Where in quotation marks you need to write the namespace name, which becomes the current one. The default namespace is '
When accessing the encapsulated namespace members, you must add the suffix _name_ to each element, where "name" is the namespace name. Uppercase namespaces are recommended. Here is a good example:
At the end of the section, we give one textbook example - the quick sort verb. The Hoar sort on J can be written as follows:
Let's analyze the definition line by line:
As we showed earlier, quick sorting can be written in one line:
Recall that “$:” means a recursive call of a verb, and the expression “@” defines sequential computation of verbs.
It should be noted here that the code of guru programmers in J often violates all of the above recommendations.
1. Boxes
We are already faced with the fact that the noun in J is an array. Even on single constant values, vector operations are permissible. Together, all this makes up a convenient vectorial homogeneous programming environment.
However, it is obvious that arrays have their own limitations. Due to the fact that in J, by default there are only rectangular arrays, there is no way to create the so-called standard means jagged arrays. In addition, for lists consisting of heterogeneous elements, arrays are also not suitable.
To solve these problems, J provides tools for creating and using heterogeneous sequences - boxes. A box is a kind of container that can store an arbitrary element. An array of boxes is, accordingly, a kind of array of elements of type (void *). Therefore, for example, the first element of a boxed sequence can be a one-dimensional array, the second is a number, and the third is a matrix of integers.
In order to create a box, you need to call the monadic verb "<" to extract ("open") the elements from the box - the monadic verb ">":
]x =. <1 2 3
+-----+
|1 2 3|
+-----+
The box itself is drawn in ASCII graphics. Now we extract the value of the box:
>x
1 2 3
In order to add several elements to a box, the verb “;” is intended, which links the elements into a sequence of boxes:
1;2;2
+-+-+-+
|1|2|2|
+-+-+-+
(i.10) ; 42 ; (i. 2 3)
+-------------------+--+-----+
|0 1 2 3 4 5 6 7 8 9|42|0 1 2|
| | |3 4 5|
+-------------------+--+-----+
To list the elements of such a boxed sequence, we can use the parts of speech that are already known to us. For example, the adverb “between”:
;/ i.3
+-+-+-+
|0|1|2|
+-+-+-+
Or composition of verbs:
(#@>)"0 (1 2 3; 2; 3 4) NB. узнаем длину содержимого каждой (ранг = 0) коробки из последовательности
3 1 2
Next, use the verb "{" to extract the second element of the box:
1 { ;/i.3
+-+
|1|
+-+
In this example, one should pay attention to the following moment: the index call returns the boxed element of the array without unpacking it automatically.
From the previous expression, we can conclude that if we want to apply a certain verb to each element of the box, then each time the verb will take an operand wrapped in a box noun. In order to “pull out” an element from the array at each call, and after the action “shove” the result back into the box, you can use the already known union “&.”.
The union “&.” Applies the right verb to the operand, and the left verb applies to the result. Then the verb inverse to the right verb is applied to the result. Thus, we actually repeated the algorithm described in the paragraph above. We use this scheme to double each element of the box.
(+: &. >) ;/ i.3
+-+-+-+
|0|2|4|
+-+-+-+
Due to the fact that the expression &.> Is used quite often, it is by default associated with the symbol each:
each
&.>
(+: each) ;/ i.3
+-+-+-+
|0|2|4|
+-+-+-+
Note that in data processing speed, boxes are significantly (up to 3 orders of magnitude!) Lagging behind numerical arrays.
2. Definition of multiline verbs
“What does it take to create an elegant programming language?”
Iverson: “The secret is to do what you expect from him.”
Fred Brooks, A Celebration of Kenneth Iverson, 2004-11-30
It is not always possible to present the verb in tacit form. For this, there are special constructions in J, which we will call imperative. First of all, these are operations “3:” and “4:” (do not confuse with the constant verbs “3:” and “4:”). The default operand is called “y”, the left is “x”. For instance:
v1 =: 3 : '- y' NB. монада
v2 =: 4 : 'x + y' NB. диада
If you feel that your imperative definition can be written in tacitic form, but you do not know how, then you can use the wonderful standard verb conversion:
13 : 'x + y'
+
13 : 'x - (y + 1)'
[ - 1 + ]
To write multi-line verbs, similar constructions are used. Moreover, as in most functional languages, the last calculated value is returned, and therefore no analogue of the return statement is required. In multiline verbs, local variables can also be used - they are determined using the “=.” Operation. The symbol for ending the definition of the verb is the symbol ")"
v =: 4 : 0 NB. диада
z =. y + 1 NB. выражение "z =: ..." создало бы глобальную переменную z
x - z
) NB. Именно так, с непарной закрывающей скобкой.
3 4 v 1 2
1 1
J also has special constructs for checking conditions (.if), loops (.while), and some others. For more information, we recommend that you consult the documentation.
3. Recursion
The recursive quicksort function was shown back in the introduction. Let's look at another example. We write in Python a simple function for determining the length of a sequence as if there was no such function built-in.
def len(xs):
""">>> len([1,2,3])
3"""
if xs == []:
return 0
return 1+len(xs[1:])
In order to write a recursive function for calculating the length of a vector in J, we will have to introduce an additional predicate verb to determine whether a noun is a sequence with at least one element. Call this predicate isa from the phrase "is array". We will write at the beginning an example of using this verb:
isa 1 NB. ожидаем 0
isa i.0 NB. ожидаем 0
isa 1 2 3 NB. ожидаем 3
We will determine whether the operand is a vector of length more than 1, through the verb of extracting an element from the vector at a certain position. This is the verb "{"
isa =: ((1: 1&{) :: 0:) : [:
Thus, if the expression “1 & {” fulfills correctly, then we consider that the operand is an array with a length greater than 1. Otherwise, return false (zero). We also added a ban on the dyadic call of the verb to the definition.
In order to simulate a condition check, we use the @. Union, which calls the verb from the box in that position, which is determined by the right operand. Those.
3:`4: @. 1
4:
3:`4: @. 0
3:
We need to return the length = 1 if the right operand is a vector of length = 1, i.e. if the predicate isa on this noun returns 0.
len =: 1:`(.....) @. isa
In place of the ellipsis, we must implement a recursive call to calculate the length for the tail of the transmitted sequence. We take advantage of the fact that the recursive call in J is implemented by the verb "$:". T.O. we get
len =: 1:`(>:@$:@}.) @. isa
len 1 2 3
3
len 17
1
The next step is to rewrite our verb so that the recursive call becomes tail. To do this, we will store the accumulated value in the left operand, and the verb, therefore, becomes dyadic:
len2 =: [`((>:@[) $: (}.@])) @. (isa@])
1 len2 i.7
7
The definition of a verb looks rather unappetizing, and in fact it is. We illustrate the algorithm of the verb len2 with an example in Python:
def len2(acc,xs):
if xs == []:
return acc
else:
return len2(acc+1, xs[1:])
It is interesting to compare the speed of the code we wrote. To do this, use the verb “6!: 2”, which executes its right operand as many times as indicated in the left operand and returns the average run time of each run in seconds.
time =: 6!:2
x =: i.1000
10 time 'len x' NB. рекурсивный глагол
0.00614873
10 time '1 len2 x' NB. глагол с хвостовой рекурсией
0.00553225
10 time '# x' NB. встроенный глагол вычисления длины массива
1.67641e_6
As you can see, in this case, using the built-in J tools is 3 orders of magnitude faster than our independent implementations. In addition, in J there is a restriction on the depth of recursion and there is no optimization of tail recursion.
It should be noted that the use of such recursive expressions is recommended only for training and in case of emergency.
4. Namespaces
We will not dwell on the use of the object-oriented approach to programming in J. For those interested, let’s say that there is support for OOP in J. Read more, for example, in Learning J.
Note, however, that J has special constructs for using namespaces that have syntax similar to OOP toolkit.
The beginning of a new namespace should begin with the expression:
cocurrent 'name'
Where in quotation marks you need to write the namespace name, which becomes the current one. The default namespace is '
base'. Therefore, as soon as the code block in the namespace is finished, you need to return to the default scope using the expression: cocurrent 'base'
When accessing the encapsulated namespace members, you must add the suffix _name_ to each element, where "name" is the namespace name. Uppercase namespaces are recommended. Here is a good example:
cocurrent 'INNER'
rate =: 10
v =: 3 : 'rate + y'
cocurrent 'base'
v_INNER_ 1
11
rate_INNER_ =: 1
v_INNER_ 1
2
5. Example
At the end of the section, we give one textbook example - the quick sort verb. The Hoar sort on J can be written as follows:
sel=: 1 : 'x # ['
quicksort=: 3 : 0
if. 1 >: #y do. y
else.
(quicksort y sel e=.y{~?#y
end.
)
Let's analyze the definition line by line:
- 1 line. Let us first dwell on the auxiliary expression sel defined on the first line of our example. First, note that expressions like
1 : 'выражение'
indicate that the expression in quotation marks is an adverb. Recall that by an adverb we mean a special construction that modifies the behavior of a verb, with which this adverb is applied. In this case, the adverb sel copies (verb "#") from the left operand (verb "[") those elements that are indicated in "x". - 2 line. The very definition of the quick sort verb begins with the expression 3: 0, which means that only one argument is allowed for this verb.
- 3 line. The next line checks if 1 is greater than or equal (">:") to the length ("#") of the operand, then the value of this operand is returned, because sorting is not required.
- 4-6 line. Otherwise, the verb “,” combines the results of 3 recursive quicksort calls in an array. Moreover, the first are those elements that are smaller than the randomly selected element "e", then there are elements equal to "e", then the elements are large "e". At the end of the expression, the value “e” is defined. Moreover, "{" means the choice of an element at a random ("?") Position on the segment 0 ... operand_length ("#y").
- 7 line. Completion of the definition of the verb.
As we showed earlier, quick sorting can be written in one line:
quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?@#)) ^: (1<#)
Recall that “$:” means a recursive call of a verb, and the expression “@” defines sequential computation of verbs.
6. Tips
Want to know the secret to writing articles well? Write 500 articles.
Roger Hui, Remembering Ken Iverson, 2004
- Remember that source code is read much more often than it is written. For J, this is especially true.
- Give verbs meaningful names. Do not use names like v1, v2, etc.
- Be sure to write comments for each verb with an example of a verb call.
- Be sure to write unit tests.
- Put spaces and brackets in tacitic verbs, even where they are optional. The expressions “+ /: + *: ~ 1:” and “+ /: (+ *: ~ 1 :)” are calculated the same, but the latter is easier to read.
It should be noted here that the code of guru programmers in J often violates all of the above recommendations.
- Keep in mind that a verb may not be called in the way you intended it to: include both a monad and dyad call. J's error messages are not very informative.
- Make compact verb definitions. Two verbs with a length of 20 characters each are easier to read than a single verb with a length of 40 characters.
- If a verb calculates a “book” mathematical formula, then write it in tacit form only if it significantly increases the efficiency of calculations. In other cases, write with explicit operands.
- Use cyclic imperative and recursive constructs only when necessary. Although they sometimes make reading a program easier, they are very slow. Use the adverbs "/", "\" and the like.
- Consider defining all files as OOP modules.
- If possible, do not use global variables.
- Read the book "J for C programmers". Pay particular attention to chapters titled "Loopless code."
7. What to read further
Never give more than one explanation of what is happening - the latter will always be correct
Kenneth Iverson.
- http://vector.org.uk — очень солидный журнал от Британской ассоциации APLщиков. Статьи в основном про язык APL, но много статей и по языкам J, Q, K. Все можно скачать в электронном виде. Крайне рекомендуется.
- http://nsl.com — название сайта расшифровывается как «no stinking loops». На сайте много примеров разной степени сложности. В основном на языке K. Есть, к примеру, реализация ленивого подмножества языка К на самом К.
- http://www.jsoftware.com/jwiki/Links — сборник ссылок на полезные ресурсы по языку J.
- http://jsoftware.com/forums.htm — список почтовых рассылок J. (активность достаточно высокая — например, в основном разделе «Programming»в среднем по 8-12 сообщений в день).
- http://www.jsoftware.com/jwiki/Essays - don't forget about this “inexhaustible source of wisdom” - a collection of articles and examples with comments. Among the essays you can find, for example, a sudoku solver in 30 lines.
Instead of a conclusion
I once told Ken, “You know, Ken, you are my favorite designer of programming languages, and Don Knut is my favorite programmer.” Ken immediately asked, “What's wrong with my programming?”
- Joey Tuttle, A Celebration of Kenneth Iverson, 2004-11-30