i hear that dan is working on an infix parser for factor.
here's a short introduction to the notation invented by
ken iverson, and used in APL, J, and K. it is independent
of the vector semantics of those languages.

a token has type noun (n), unary (n), verb (v), or adverb (a).

nouns are data, like

12
"foo"
a.b
[10 20 30]

verbs are operators which take two nouns and return a noun,
like

+

unaries are operators which take one noun and return one
noun. in K, a unary is written with a trailing ":", like

+: (+: is transpose)

except where adverbs are involved, the parser given below
can determine by context whether + is a verb or a unary.
you only really need to specify the unary form when passing
the operator to an adverb, since context may not be available
at parse-time.

adverbs are operators which take and return verbs and
unaries, like

+/ (/ takes + and returns summation)
+:' (' takes +: and returns transpose-each)

a tokenized expression is therefore a sequence of typed
tokens:

2+3 -> n:2 v:+ n:3

Infix expressions are parsed as:

(2+)3

that is, verb + is curried on noun 2 and the result --
a unary verb -- is applied to the noun 3. The derived
category of a curried verb is u (unary).

parsing an expression requires two tables: a binding-
strength table B, which gives the binding strengths of
category pairs, and a category-result table C, which
gives the category of the result of binding two objects.

except for the hierarchy implied by B, there is no
precedence relation defined for operators in an iverson
language. parentheses are used, infrequently, to redirect
order of execution.

the algorithm A -- developed by the IBM research scientists
Bunda and Gerth -- works this way:

(a b) is notation for binding a and b.

take an expression E. starting at the right, scan left.

if E is empty then return E.

if E consists of a single element then return E.

if E consists of two elements only:

E = a b

then return

E' = C(a,b):(a b).

else E is:

E = .. a b c d e f

scanning from the right, bind the first pair E[i] and E[i+1]
which satisfies the following condition:

E[i] is a noun and E[i+1] is a noun OR
B(E[i],E[i+1]) > B(E[i-1],E[i])

E' might now look like this:

.. a b C(c,d):(c d) e f

so apply A to E'.

For example:

2 + - 4 * foo 5
n v v n v n n

2 + - 4 * (foo 5) / because foo and 5 are nouns
n v v n v n

2 + - (4*) (foo 5)
n v v u n

2 + - ((4*)(foo 5))
n v v n

2 + (-((4*)(foo 5)))
n v n

(2+) (-((4*)(foo 5)))
u n

((2+)(-((4*)(foo 5))))
n

For K, the binding-strength table B is:

n v u a
- - - -
n 0 4 . 5
v 2 1 1 5
u 3 1 1 5
a . . . .

and the category-result table C is:

n v u a
- - - -
n n u . v
v n v v v
u n v v v
a . . . .

e.g. the parse tree for 2++/!3-4*5 is:

+-------+-------+
| |
+-+-+ +-----+------+
| | | |
v:+ n:2 +-+--+ +----+-----+
| | | |
a:/ v:+ u:!: +----+-----+
| |
+-+-+ +--+--+
| | | |
v:- n:3 +-+-+ n:5
| |
v:* n:4

other iverson-languages use different tables and
different sets of basic categories. for example,
in APL and J, there are conjunctions. a conjunction
take a pair of verbs/unaries and returns a verb/
unary. also, the noun-noun modification to the B-G
algorithm is needed to handle right-associativity
of function-application and indexing in K.

notice also that the K tables provide for expressions
like

2+
-+

the first expression evaluates to a unary, while the
second, which has the form v v, evaluates to a verb,
namely, the unary which applies unary - to the result
of adding two nouns.

although expressions in iverson notation are parsed
right-to-left, they are read left-to-right. In nearly
every instance, it is possible to directly transliterate
into english:

2++/!3-4*5

2 plus (the result of) sum over (the result of) 3 -
(the result) of 4 * 5.

infix syntax - iverson notation

stevan apter — 2005-06-26 14:09:58

ori_berger — 2005-06-26 22:43:08