Programming language J. Amateur look. Part 4. Boxes and cycles. Conclusion
Previous article in the Cycle Programming Language J. Amateur Look. Part 3. Arrays
We have already encountered the fact that the noun in J is an array. Even over single constant values, vector operations are allowed. In aggregate, all this constitutes a convenient vector homogeneous programming environment.
')
However, it is obvious that arrays have their limitations. Due to the fact that in J the default is only rectangular arrays, it is not possible to create so-called standard means. jagged arrays In addition, for lists consisting of disparate elements, arrays are also not suitable.
To solve these problems, J provides the means to create and use heterogeneous sequences - boxes. A box is a kind of container that can hold an arbitrary element. An array of boxes is, respectively, 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 must call the monad verb "<" to extract ("open") the elements out of the box - the monad verb ">":
The box itself is drawn in ASCII graphics. Now we extract the value of the box:
In order to add several elements to the box, the verb “;” is intended, which links the elements into a sequence of boxes:
To enumerate the elements of such a boxed sequence, we can use parts of speech already known to us. For example, the adverb "between":
Or composition of verbs:
Next, we use the verb "{" to extract the second element of the box:
In this example, you should pay attention to the following point: the index reference returns the boxed element of the array, without automatically unpacking it.
From the previous expression, we can conclude that if we want to apply a verb to each element of the box, each time the verb will take an operand wrapped in a noun box. In order to “pull out” an element from the array at each request, and after the action “thrust” the result back into the box, you can use the “&.” Union already known to us.
The conjunction "&." Applies the right verb to the operand, and the left verb is applied to the result. Then, the verb opposite 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 box item.
Due to the fact that the expression &.> Is used quite often, it is by default associated with the symbol each:
Note that in the data processing speed of the box, they are significantly (up to 3 orders of magnitude!) Behind the numerical arrays.
It is not always possible to represent the verb in a tacit form. For this, there are special constructions in J, which we will call imperative. First of all, these are the operations “3:” and “4:” (do not confuse with constant verbs “3:” and “4:”). The default right operand is called “y”, the left “x”. For example:
If you feel that your imperative definition can be written in tacit form as well, but you don’t know how, then you can use the remarkable standard verb transformation:
For the construction of multi-line verbs similar constructions are used. And, as in most functional languages, the last calculated value is returned and therefore no analogue of the return operator is required. In multiline verbs, you can also use local variables — they are defined using the “=.” Operation. The symbol of the end of the definition of the verb is the symbol ")"
J also has special constructions for checking conditions (.if), cycles (.while) and some others. For more information, please refer to the documentation.
The recursive quick sort function was shown 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 is no built-in such function.
In order to write in J a recursive function of calculating the length of a vector, we will have to introduce an additional verb-predicate to determine whether a noun is a sequence with at least one element. Let's call this predicate isa from the phrase “is array”. Let's 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 extraction from the element vector at a certain position. This is the verb "{"
Thus, if the expression "1 & {" works correctly, then we assume that the operand is an array with a length greater than 1. Otherwise, we return false (zero). We also added to the definition a ban on the dyadic call of a verb.
In order to simulate a condition check, we use the union @., Which calls the verb out of the box at the position defined by the right operand. Those.
We need to return length = 1 if the right operand is a vector of length = 1, i.e. if the predicate isa on this noun returns 0.
At the place of the ellipsis, we must implement a recursive call to calculate the length for the tail of the transmitted sequence. We use the fact that the recursive call in J is implemented by the verb "$:". So will 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 dyadny:
Definition of the verb looks quite 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 written by us. To do this, we use the verb “6!: 2”, which executes its right operand as many times as it is indicated in the left operand and returns the average operation time of each run in seconds.
As you can see, in this case, the use of built-in J tools is 3 orders of magnitude faster than our independent implementations. In addition, J has a limit on the depth of recursion and there is no tail recursion optimization.
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. If we are interested, we 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 tools.
The beginning of a new namespace should begin with the expression:
Where in quotes you need to write the name of the namespace, which will become current. The default namespace is '
When referring to encapsulated members of the namespace, you must add the suffix _name_ to each element, where “name” is the name of the namespace. It is recommended to name the namespace in uppercase. Let's give a clear example:
In the conclusion of the section we give one textbook example - the verb quick sort. Sorting Hoare by J can be written as follows:
Consider the definition line by line:
As we have shown earlier, quick sorting can be written in one line:
Recall that "$:" means a recursive call of a verb, and the expression "@" defines a sequential calculation of verbs.
It should be noted here that the code of guru programmers in J often violates all the above recommendations.
1. Boxes
We have already encountered the fact that the noun in J is an array. Even over single constant values, vector operations are allowed. In aggregate, all this constitutes a convenient vector homogeneous programming environment.
')
However, it is obvious that arrays have their limitations. Due to the fact that in J the default is only rectangular arrays, it is not possible to create so-called standard means. jagged arrays In addition, for lists consisting of disparate elements, arrays are also not suitable.
To solve these problems, J provides the means to create and use heterogeneous sequences - boxes. A box is a kind of container that can hold an arbitrary element. An array of boxes is, respectively, 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 must call the monad verb "<" to extract ("open") the elements out of the box - the monad 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 the 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 enumerate the elements of such a boxed sequence, we can use parts of speech 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, we use the verb "{" to extract the second element of the box:
1 { ;/i.3 +-+ |1| +-+ In this example, you should pay attention to the following point: the index reference returns the boxed element of the array, without automatically unpacking it.
From the previous expression, we can conclude that if we want to apply a verb to each element of the box, each time the verb will take an operand wrapped in a noun box. In order to “pull out” an element from the array at each request, and after the action “thrust” the result back into the box, you can use the “&.” Union already known to us.
The conjunction "&." Applies the right verb to the operand, and the left verb is applied to the result. Then, the verb opposite 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 box item.
(+: &. >) ;/ 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 the data processing speed of the box, they are significantly (up to 3 orders of magnitude!) Behind the numerical arrays.
2. Definition of multi-line verbs
“What do you need 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 represent the verb in a tacit form. For this, there are special constructions in J, which we will call imperative. First of all, these are the operations “3:” and “4:” (do not confuse with constant verbs “3:” and “4:”). The default right operand is called “y”, the left “x”. For example:
v1 =: 3 : '- y' NB. v2 =: 4 : 'x + y' NB. If you feel that your imperative definition can be written in tacit form as well, but you don’t know how, then you can use the remarkable standard verb transformation:
13 : 'x + y' + 13 : 'x - (y + 1)' [ - 1 + ] For the construction of multi-line verbs similar constructions are used. And, as in most functional languages, the last calculated value is returned and therefore no analogue of the return operator is required. In multiline verbs, you can also use local variables — they are defined using the “=.” Operation. The symbol of the end of 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 constructions for checking conditions (.if), cycles (.while) and some others. For more information, please refer to the documentation.
3. Recursion
The recursive quick sort function was shown 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 is no built-in such function.
def len(xs): """>>> len([1,2,3]) 3""" if xs == []: return 0 return 1+len(xs[1:]) In order to write in J a recursive function of calculating the length of a vector, we will have to introduce an additional verb-predicate to determine whether a noun is a sequence with at least one element. Let's call this predicate isa from the phrase “is array”. Let's 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 extraction from the element vector at a certain position. This is the verb "{"
isa =: ((1: 1&{) :: 0:) : [: Thus, if the expression "1 & {" works correctly, then we assume that the operand is an array with a length greater than 1. Otherwise, we return false (zero). We also added to the definition a ban on the dyadic call of a verb.
In order to simulate a condition check, we use the union @., Which calls the verb out of the box at the position defined by the right operand. Those.
3:`4: @. 1 4: 3:`4: @. 0 3: We need to return 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 At the place of the ellipsis, we must implement a recursive call to calculate the length for the tail of the transmitted sequence. We use the fact that the recursive call in J is implemented by the verb "$:". So will 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 dyadny:
len2 =: [`((>:@[) $: (}.@])) @. (isa@]) 1 len2 i.7 7 Definition of the verb looks quite 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 written by us. To do this, we use the verb “6!: 2”, which executes its right operand as many times as it is indicated in the left operand and returns the average operation 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, the use of built-in J tools is 3 orders of magnitude faster than our independent implementations. In addition, J has a limit on the depth of recursion and there is no tail recursion optimization.
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. If we are interested, we 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 tools.
The beginning of a new namespace should begin with the expression:
cocurrent 'name' Where in quotes you need to write the name of the namespace, which will become current. The default namespace is '
base '. Therefore, as soon as the code block in the namespace is complete, you must return to the default scope using the expression: cocurrent 'base' When referring to encapsulated members of the namespace, you must add the suffix _name_ to each element, where “name” is the name of the namespace. It is recommended to name the namespace in uppercase. Let's give a clear example:
cocurrent 'INNER' rate =: 10 v =: 3 : 'rate + y' cocurrent 'base' v_INNER_ 1 11 rate_INNER_ =: 1 v_INNER_ 1 2 5. Example
In the conclusion of the section we give one textbook example - the verb quick sort. Sorting Hoare by J can be written as follows:
sel=: 1 : 'x # [' quicksort=: 3 : 0 if. 1 >: #y do. y else. (quicksort y <sel e),(y =sel e),quicksort y >sel e=.y{~?#y end. ) Consider the definition line by line:
- 1 line. We first dwell on the auxiliary sel expression defined on the first line of our example. First, we note that type expressions
1 : ''
indicate that the expression in quotes is an adverb. Recall that by adverb we mean a special construction that modifies the behavior of the verb, with which this adverb is used. In this case, sel adverb copies (verb “#”) from the left operand (verb “[”) those elements that are specified in “x”. - 2 line. The very definition of a quick sort verb begins with a 3: 0 expression, which means that this verb has only one argument.
- 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 no sorting required.
- 4-6 line. Otherwise, the results (of the verb “,”) of the 3 quicksort recursive calls in the array are combined. Moreover, the first are those elements that are smaller than the randomly chosen element “e”, then there are elements equal to “e”, then elements that are larger “e”. At the end of the expression is determined by the value of "e". Moreover, “{” means the choice of an element at a random (“?”) Position in the segment 0 ... length of the operand (“#y”).
- 7 line. Completion of the definition of the verb.
As we have shown earlier, quick sorting can be written in one line:
quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?@#)) ^: (1<#) Recall that "$:" means a recursive call of a verb, and the expression "@" defines a sequential calculation of verbs.
6. Tips
Want to know the secret of how to write good articles? Write 500 articles.
Roger Hui, "Remembering Ken Iverson", 2004
- Remember that the source code is read much more often than they write. For J this is especially true.
- Let's take meaningful verbs. 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 tacit verbs even where they are optional. The expressions “+ /: + *: ~ 1:” and “+ /: (+ *: ~ 1 :)” are calculated in the same way, but the latter is easier to read.
It should be noted here that the code of guru programmers in J often violates all the above recommendations.
- Keep in mind that the verb may not be called the way you intended it: provide for both monadic and dyadic call. J error messages are not very informative.
- Make compact definitions of verbs. Two verbs with a length of 20 characters are easier to read by a person than a single verb with a length of 40 characters.
- If the 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 indication of the operands.
- Use cyclic imperative and recursive constructions only when necessary. Although they sometimes make it easier to read the program, they are very slow. Use 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 special attention to the chapters called "Loopless code".
7. What to read next
Never give more than one explanation to what is happening - the latter will always be correct.
Kenneth Iverson.
- http://vector.org.uk is a very solid magazine from the British APL Association. The articles are mainly about the APL language, but there are many articles on the languages J, Q, K. Everything can be downloaded in electronic form. Highly recommended.
- http://nsl.com - site name stands for “no stinking loops”. The site has many examples of varying degrees of complexity. Mainly in K. There is, for example, the implementation of the lazy subset of the language K on K. itself.
- http://www.jsoftware.com/jwiki/Links - a collection of links to useful resources on the language J.
- http://jsoftware.com/forums.htm - a list of J. mailing lists (activity is quite high - for example, in the main section of "Programming" an average of 8-12 messages per day).
- http://www.jsoftware.com/jwiki/Essays - do not forget about this “inexhaustible source of wisdom” - a collection of articles and examples with comments. Among the essays can be found, for example, 30-line sudoku solver.
Instead of conclusion
I once told Ken, "You know, Ken, you are my favorite designer of programming languages, and Don Knuth is my favorite programmer." Ken immediately asked, “What's wrong with my programming?”
- Joey Tuttle, A Celebration of Kenneth Iverson, 2004-11-30
Source: https://habr.com/ru/post/198230/
All Articles