A Little J Horner
Vector 9:3, page 89
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 89
Horner’s method for evaluating a polynomial (see Spunde’s Technical Correspondence, Vector 8.3 (Jan 1992) pp 138-9) can be expressed in J as follows, for (ascending) coefficients CS and a single value V:
A defined verb
can be used (albeit inefficiently) with a list of values VS:
Alternatively, a little verb which adds its left argument to VS times its right argument can be inserted in list CS all at once:
By way of explanation, a taste of J follows:
In the first expression, ,. is Append (an extension of APL’s Catenate-along-the-last-dimension) which joins V to each item in CS. The resulting 2-column matrix is Ravelled (,) then Beheaded (}. does 1 Drop) producing a vector of coefficients interspersed with copies of V. (Note that J notation employs some two-character symbols, here, for example, ,. and }. with period suffixes.) Then Insert / (same as APL’s Reduction operator with a vector) applies two verbs (functions) to that vector. Plus + and Times * (× in APL) are Tied (`) together as a gerund (akin to a function array) — forming boxed noun equivalents of the verbs (see Bernecky’s "Gerunds and Representations", APL91 ACM).
The J definition of Horner is similar to direct definition in that it uses only one line but uses the copula =. (like APL’s ←) instead of a colon and is "tacit", that is, uses verbs without showing their arguments explicitly. Here the Tied verb +`* is the argument for Insert (an adverb); the resulting derived verb is the left argument of the Atop conjunction (@) and Behead (}.) is its right argument. That verb composition is the argument of another Atop @ with Ravel (,) on its right. That, in turn, is finally composed Atop the result of Append (,.) applied to the two arguments given to Horner. It might be noted that this definition is equivalent to — but not procedurally identical to — the algorithm above, which executes verb composition in the reverse order. This can be seen by typing the name of the verb (here, Horner) by itself on a J system, which produces a boxed representation showing the nesting of verbs (and adverbs and conjunctions).
Once defined, Horner can, of course, be executed: V Horner CS. It can also be executed, as is, with a list of values VS by applying the Rank conjunction (") shown here with a right argument of 0 1 indicating each scalar in the left argument to be used with the vector right argument (and the result assembled accordingly). Note that if a noun were given as the right argument (instead of pronoun CS here), either it or the right argument to " must be parenthesized.
Lastly, consider the alternative of composing a verb which adds its left argument to VS times its right argument and inserting that verb between each item of CS. (+ VS&*) is a "hook" composed of two verbs: Plus (+) and a monadic verb composed of VS With (&) Times (*). In general, a dyadic hook x (f g) y is x f g y and the conjunction & bonds its noun argument with its verb argument to derive a monadic verb.
The plum — defining a verb for the last expression of Horner’s method — is left for you, Jack, to pull out.
University of Massachusetts
Amhurst, MA 01003 USA