Help / JforC / Parsing and Execution II
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers
39. Parsing and Execution II
Now that you understand what an anonymous verb/adverb/conjunction is, you are ready to follow parsing and execution word by word. We will finally abandon all shortcuts and process sentences exactly as the interpreter does.
In any compiled language, a program is broken into words (tokens) and then parsed, and code is generated from the parsed result. Not so in J: a sentence is broken into words, but the sentence is not fully parsed; rather, parsing and execution proceed simultaneously, scanning the text from right to left. Parsing finds patterns in the sentence that are then executed. Execution includes the usual supplying of noun operands to verbs to obtain a result from the verb, but also other actions: supplying verb and noun operands to conjunctions and adverbs to produce derived entities, and recognition of other sequences that we will learn soon.
Execution of a bit of a sentence, which we will call a fragment, consists of replacing the fragment with an appropriate single word, namely the result of executing the fragment. In the simple case, where the fragment is the invocation of a verb (i. e. the fragment looks like verb noun or noun verb noun), the word that replaces it is the noun that is the result of the verb. If the fragment is the invocation of a modifier, the result of executing it will be a noun or a derived verb/adverb/conjunction. A noun is nothing but its value, but the derived verb/adverb/conjunction will itself eventually be executed: it is called an anonymous verb/adverb/conjunction and is saved by the interpreter in a private form, and the single word used to replace the fragment is a reference to this anonymous verb/adverb/conjunction (for the case of an anonymous verb, you may think of the single word as a pointer to a function that performs according to the definition of the anonymous verb).
In all cases the word replacing the fragment has a definite part of speech, and if it is a verb, a definite rank.
I want to repeat that 'execution' as used here is not synonymous with 'execution on noun operands'. Yes, verbs are executed that way. But the execution of a modifier produces an anonymous entity, and it may consume no nouns at all (as in the example of +&.>). Execution of a modifier is a step along the path to execution of the derived verb.
The Parsing Table
Execution of a sentence begins by breaking the sentence into words. The words (with a beginning-of-line marker, shown here as $, prepended) become the initial contents of the unprocessed word list. A push-down stack will also be used during execution; it is initially empty. Execution of the sentence is performed by repetition of the parsing step which comprises: (1) examining the top 4 elements of the stack to see if they match one of the 9 executable patterns; (2) if a match was found, executing the executable portion of the stack (what we called the executable fragment in the last chapter), resulting in a single word which replaces the fragment on the stack; (3) if no match was found, moving the rightmost word of the unprocessed word list into the leftmost position of the stack, pushing the rest of the stack to the right. Execution finishes when there are no unprocessed words and the stack does not contain an executable pattern. Note that execution of a fragment may leave the stack matching one of the executable patterns, so several sequential parsing steps may perform an execution without moving anything onto the stack. After all words have been processed, the stack should contain a beginning-of-line marker followed by a single word which becomes the result of the sentence.
To follow the parsing we need to know what patterns at the top of the stack contain an executable fragment. The parsing table below gives the complete list. More than one symbol in a box means that any one of them matches the box. name means any valid variable name, and C, A, V, and N stand for conjunction, adverb, verb, and noun respectively.
|
leftmost stack word |
other stack words |
action |
||
|
$ =. =: ( |
V |
N |
anything |
0 Monad |
|
$ =. =: ( A V N |
V |
V |
N |
1 Monad |
|
$ =. =: ( A V N |
N |
V |
N |
2 Dyad |
|
$ =. =: ( A V N |
V N |
A |
anything |
3 Adverb |
|
$ =. =: ( A V N |
V N |
C |
V N |
4 Conj |
|
$ =. =: ( A V N |
V N |
V |
V |
5 Fork |
|
$ =. =: ( |
C A V N |
C A V N |
anything |
6 Hook/Adverb |
|
name N |
=. =: |
C A V N |
anything |
7 Is |
|
( |
C A V N |
) |
anything |
8 Paren |
The lines in the parsing table are processed in order. If the leftmost 4 words on the stack match a line in the table, the fragment (those words on the stack which are in boldface in the parsing table) is executed and replaced on the stack by the single word returned. Because the fragment is always either two or three words long, it is officially known as a bident or trident. The last column of the parsing table gives a description of what execution of the fragment entails.
You will have an easier time following the parsing if you note that the leftmost word in the executable pattern is usually one of $ =. =: ( A V N . This means that you can scan from the right until you hit a word that matches one of those before you even start checking for an executable pattern. If you find one of $ =. =: ( A V N and it doesn't match an executable pattern, keep looking for the next occurrence.
Note that the leftmost stack word in the parsing table is never a conjunction. This is the ultimate source of our long-noted rule that conjunctions associate left-to-right: a conjunction can be executed only when it appears in the third stack position, but if another conjunction is in the leftmost position then, the stack will always be pushed down to examine that conjunction's left argument.
Line 6, defining hooks, is matched for any combination of CAVN CAVN except N A and V A which are matched in line 3. Only the combinations A A, C N, C V, N C, V C, and V V are valid; the rest result in syntax errors.
Examples Of Parsing And Execution
We will now follow a few sentences through parsing. We will represent anonymous entities by names in italics, with an indication of how the anonymous entity was created. Up till now in this book we have scarcely noticed that the term 'verb' was used both for an entity that can be applied to a noun to produce a noun result, and also for the name of that entity. This ambiguity will continue--being precise would be too cumbersome--but you should be aware of it. When we say 'the result is av, defined as +/', that means that an anonymous verb was created whose function is described as +/, and the nickname we are giving it--the word, that is, that goes on the execution stack to betoken this verb--is av.
Sentence: +/2*a where a is 1 2 3
|
unprocessed word list |
stack |
line |
|
$ + / 2 * a |
|
|
|
$ + / 2 * |
1 2 3 (not executable) |
|
|
$ + / 2 |
* 1 2 3 (not executable) |
|
|
$ + / |
2 * 1 2 3 (not executable) |
|
|
$ + |
/ 2 * 1 2 3 (result 2 4 6) |
2 |
|
|
$ + / 2 4 6 (result av, defined as +/) |
3 |
|
|
$ av 2 4 6 (result 12) |
0 |
|
|
$ 12 |
|
The column labeled 'line' indicates which line of the parsing table was matched by the stack. The fragment is marked in boldface and underlined. Note that when the noun a moved onto the stack, its value was moved; when a named verb, adverb, or conjunction is moved onto the stack, only the name is moved. Note also that the noun's value (1 2 3 here) is a single word.
From now on we will omit the lines that do not contain an executable fragment.
Sentence: mean =: +/ % #
|
unprocessed word list |
stack |
line |
|
$ mean =: + / % # |
|
|
|
$ mean |
=: + / % # (result av1, defined as +/) |
3 |
|
$ mean |
=: av1 % # (result av2, defined as av1 % #) |
5 |
|
|
$ mean =: av2 (result av2; mean is assigned av2) |
7 |
|
|
$ av2 |
|
I want to emphasize that what is assigned to mean is the result of parsing +/ % # . It is not the sequence +/ % #, but rather a single verb which performs the function described by the fork. Now you see why putting parentheses around the definition doesn't matter: av2 would be parsed the same either way.
|
unprocessed word list |
stack |
line |
|
$ mean 4 5 6 |
|
|
|
|
$ mean 4 5 6 (result 5) |
0 |
|
|
$ 5 |
|
Sentence: mean 4 5 6
Since mean is the result from parsing +/ % #, it is executed without further ado. As you can see, a single 'execution' step can trigger a cascade of processing as each verb referred to by an executing verb is executed in turn. Here, execution of mean does the entire processing of the fork, returning the result 5 . The verb to be executed can be quite complex, and can have a mixture of named and anonymous components, as in the next example.
Sentence: (mean - (+/ % #)&.(^."1)) 4 5 6 (find the difference between arithmetic and geometric mean)
|
unprocessed word list |
stack |
line |
|
$ ( mean - ( + / % # ) &. ( ^. " 1 ) ) 4 5 6 |
|
|
|
$ ( mean - ( + / % # ) &. |
( ^. " 1 ) ) 4 5 6 (result av1, defined as ^. " 1) |
4 |
|
$ ( mean - ( + / % # ) &. |
( av1 ) ) 4 5 6 (result av1) |
8 |
|
$ ( mean - |
( + / % # ) &. av1 ) 4 5 6 (result av2, defined as +/ |
3 |
|
$ ( mean - |
( av2 % # ) &. av1 ) 4 5 6 (result av3, defined as av2 % #) |
5 |
|
$ ( mean - |
( av3 ) &. av1 ) 4 5 6 (result av3) |
8 |
|
$ ( mean |
- av3 &. av1 ) 4 5 6 (result av4, defined as av3 &. av1) |
4 |
|
$ |
( mean - av4 ) 4 5 6 (result av5, defined as mean - av4) |
5 |
|
$ |
( av5 ) 4 5 6 (result av5) |
8 |
|
|
$ av5 4 5 6 (result 0.0675759) |
0 |
|
|
$ 0.0675759 |
|
Again, there was only one execution of a verb. It happened at the very end: after av5 was created, it was executed, and its execution included the execution of everything else. av5 executed to produce mean - av4; to do that it executed av4, then mean, then -, and so on up the line. Each executed entity produced a result in accordance with its definition.
Sentence: inc =: ({.a)&+ where a is 4 5 6
|
unprocessed word list |
stack |
line |
|
$ inc =: ( {. a ) & + |
|
|
|
$ inc =: |
( {. 4 5 6 ) & + (result 4) |
0 |
|
$ inc =: |
( 4 ) & + (result 4) |
8 |
|
$ inc |
=: 4 & + (result av, defined as 4&+) |
4 |
|
$ |
inc =: av (result av; inc is assigned av) |
7 |
|
|
$ av |
|
This illustrates an important point. Even in the middle of a complex definition, verbs are applied to nouns wherever possible. And, the value of a noun in a definition is the value at the time the definition was parsed. If a parsed definition refers to a verb, it does so by name, so the value of a verb is its value when it is executed.
The remaining examples are curiosities to show you that it's worth your trouble to learn the intricacies of parsing.
Sentence: a + a =. 5
|
unprocessed word list |
stack |
line |
|
$ a + a =. 5 |
|
|
|
$ a + |
a =. 5 (result is 5; a is assigned 5) |
0 |
|
|
$ 5 + 5 (result is 10) |
2 |
|
|
$ 10 |
|
a is assigned a value just before that value is pushed onto the stack.
Sentence: 2 +: (2 : '&') -: * 5
|
unprocessed word list |
stack |
line |
|
$ 2 +: ( 2 : '&' ) -: * 5 |
|
|
|
$ 2 +: |
( 2 : '&' ) -: * 5 (result is ac1, defined as 2 : '&') |
4 |
|
$ 2 +: |
( ac1 ) -: * 5 (result is ac1) |
8 |
|
$ |
2 +: ac1 -: * 5 (result is ac2, defined as &) |
4 |
|
|
$ 2 ac2 * 5 (result is av, defined as 2&*) |
4 |
|
|
$ av 5 (result is 10) |
0 |
|
|
$ 10 |
|
Look at what happens when we omit the parentheses:
Sentence: 2 +: 2 : '&' -: * 5
|
unprocessed word list |
stack |
line |
|
$ 2 +: 2 : '&' -: * 5 |
|
|
|
$ 2 +: 2 : |
'&' -: * 5 (result is 1) |
1 |
|
$ 2 |
+: 2 : '&' -: 1 (result is ac1, defined as 2 : '&') |
4 |
|
$ |
2 +: ac1 -: 1 (result is ac2, defined as &) |
4 |
|
|
$ 2 ac2 1 (domain error: 2&1 is illegal) |
4 |
The omission produces a subtle but fatal change in the parsing order. As the Dictionary says, "it may be necessary to parenthesize an adverbial or conjunctival phrase that produces anything other than a noun or verb". Now you see why.
Undefined Words
If you try to execute a nonexistent verb, you get an error:
z 5 |value error: z | z 5
However, that error occurs during execution of the name, not during its parsing. During parsing, an undefined name is assumed to be a verb of infinite rank. This allows you to write verbs that refer to each other, and relieves you from having to be scrupulous about the order in which you define verbs. For example:
a =: z
This produces a verb a which, when executed, will execute z.
z =: + a 5 5
With z defined, a executes correctly. Of course, it's OK to assign z to another verb too:
b =: z b 5 5
Now, can you tell me what +/@b 1 2 3 will do? Take a minute to figure it out (Hint: note that I used @ rather than @:).
+/@b 1 2 3 1 2 3
Because b has rank 0, +/@b also has rank zero, so the 'summing' is applied to atoms individually and we get a list result. Do you think +/@a 1 2 3 will have the same result?
+/@a 1 2 3 6
Even though a has the same value as b, its rank is different. a's rank was assigned when it was parsed, and at that time z was assumed to have infinite rank. b's rank was assigned when it was parsed too, but by that time z had been defined with rank 0. You can win a lot of bar bets with this one if you hang out with the right crowd.
Note
Avoid using the parameter names x, y, u, v, m, and n for your own public variables. Those names are reassigned whenever an explicitly-defined entity starts. Also, when an explicit definition is running, those names are always evaluated before they are put onto the stack (in other words, they are passed by value rather than by name, even if they are verbs). Therefore, they produce value error if they are undefined when used.
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers