|
|
Chapter 10: Tacit Verbs ContinuedThis chapter continues the theme of verbs tacitly defined introduced in Chapter 03. In Chapter 08 we looked at composition-operators and in Chapter 09 trains of verbs. The plan for this chapter is to look first at some general points which arise in writing expressions for tacit verbs. Then we go on to look at a selection of further operators for defining verbs by cases, for recursion and for iteration. 10.1 Expressions for Tacit VerbsHere is an example of a tacit verb. It multiplies its argument by 3:
Recall from Chapter 03 that the bonding operator & produces a monad from a dyad by fixing one of the arguments of the dyad. The scheme is that if N is a noun and V a dyad, then:
(N & V) y means N V y
(V & N) y means y V N
We take the bonding operator & as an example of a typical operator, where arguments may be nouns or verbs. In general, N can be an expression denoting an noun, and V an expression denoting a verb. We look now at how these expressions get evaluated. The general rules are set out formally in Chapter 31 but here we take an informal first look at a few of the main points. 10.1.1 If In Doubt, ParenthesizeHere is an example of a tacit verb. Its general form is V&N. It multiplies its argument by 9%5, that is, by 1.8
Are the parentheses around 9 % 5 necessary here? If we omit them, we see: SCALE =: * & 9 % 5 SCALE 1.8 so they evidently make a difference. SCALE is a number, not a verb. The result of 1.8 is produced by applying the verb *&9 to the argument % 5 (the reciprocal of 5)
We have a general rule: informally we can say that conjunctions get applied before adjacent verbs. Thus in the expression * & 9 % 5 the first step is to apply the & operator to its arguments * and 9. Why is the right argument of & just 9 and not 9%5? Because of another general rule: the right argument of a conjunction is as short as possible. We say that a conjunction has a "short right scope". (By contrast, we say that a verb has a "long right scope" to express what we earlier called the "rightmost first" rule for verbs.) What about the left argument of an operator? An adverb or conjunction is said to have "long left scope", that is, as much as possible. For example, here is a verb z which adds 3 to the square of its argument. 3 plus the square of 2 is 7.
We see that the left argument of @: is the whole of 3&+. If we are in doubt in any particular case we can always make our intention clear. We can write parentheses around a part of an expression, that is, around a function - verb or operator - together with its intended argument(s). For example, verb z can be written with parentheses as:
Sometimes parentheses are necessary (as the case of * & (9%5) shows) and sometimes not, but, let me emphasize, if in doubt, parenthesize. 10.1.2 Nouns Are EvaluatedIn an expression of the general form N&V or V&N, the noun-expression N gets evaluated right away. Here is an example of a function f to multiply by nine-over-five, the numerical value being given as a%b where a and b are nouns.
We see that function f contains the computed number 1.8 so that a%b has been evaluated. 10.1.3 Verb-Names Are Not EvaluatedIn N&V the verb-expression V is not necessarily fully evaluated. If expression V is the name of a verb, then the name is enough:
10.1.4 Unknowns are VerbsThirdly, when a new name is encountered, it is assumed to be a yet-to-be-defined verb if it possibly can be.
Any sequence of hitherto-unknown names is assumed to be a train of verbs: Ralph Waldo Emerson Ralph Waldo Emerson Consequently, a verb can be defined in "top-down" fashion, that is, with detail presented later. For example, here is a Celsius-to-Fahrenheit converter presented top-down.
ctof =: shift @ scale
shift =: + & 32
scale =: * & (9 % 5)
We can see that ctof is defined solely in terms of (the names) scale and shift. Hence if we now change scale or shift we will effectively change the definition of ctof. ctof 100 212 scale =: * & 2 ctof 100 232 scale =: * & (9 % 5) ctof 100 212 This possibility, changing the definition of a function simply by changing one of its subordinate functions, may or may not be regarded as desirable. It is useful, in so far as we can correct a definition just by changing a small part. However, it may be a source of error: we may introduce a new verb scale say forgetting that scale is already defined as subordinate in ctof. There are ways we can protect ctof against accidental redefinition of its subordinate functions. Firstly, we can put a wrapper of explicit definition around it, making scale and shift local, thus: CTOF =: 3 : 0 shift =. + & 32 scale =. * & (9 % 5) shift @ scale y. ) CTOF 100 212 A second method is to, so to speak, "freezing" or "fixing" the definition of ctof, with the "Fix" adverb f. (letter-f dot). Observe the difference between the values of the verbs ctof and (ctof f.)
We see that adverb f. applied to a tacit verb replaces names by definitions, giving an equivalent verb defined only in terms of built-in functions. Here is yet another definition of ctof. scale =: * & (9 % 5) shift =: + & 32 ctof =: (shift @ scale) f.
After this definition,, the names scale and shift are still defined, but are no longer important in the definition of ctof. 10.1.5 Parametric FunctionsThe following example shows the consequences of nouns being evaluated and verbs not in an expression for a tacit verb. A curve may be specified by an equation such as, for example:
y = 4 * lambda * x * (1 - x)
This equation describes a family of similar parabolic curves, and different members of the family are picked out by choosing different values for lambda. A function to correspond to this equation might be written explicitly as verb P: P =: 3 : '4 * lambda * y. * (1 - y.)' Here lambda is not an argument to function P, but a variable which makes a difference to the result. We say that lambda is a parameter, or that function P is parametric. Now, can we write a tacit version of P without fixing lambda in advance? Something like this perhaps?
P1 =: ((4 * lambda) & *) * (1 & -)]
This won't do: lambda is unknown, so is taken to be a verb, so 4 * lambda is a syntax error. How about this?
No good: lambda here is fixed in advance: it is now a constant rather than a parameter. In short, a fully tacit exact equivalent to P is not possible. We can come close by making the parameter lambda a (constant) function rather than a number. (Constant functions were covered in Chapter 09).
Now we can vary the parameter without redefining the function:
10.2 Cases and Recursion10.2.1 CasesThink of a number (some positive whole number). If it is odd, multiply by 3 and then add 1. Otherwise, halve the number you thought of. This procedure computes from 1 the new number 4, and from 4 the new number 2. To write a function to compute a new number according to this procedure, we start with three verbs, say halve to halve, mult to multiply-and-add, and odd to test for an odd number: halve =: -: mult =: 1: + (* 3:) odd =: 2 & |
Now our procedure for a new number can be written as an explicit verb: NEW =: 3 : 0 if. odd (y.) do. (mult y.) else. (halve y.) end. ) and equivalently as a tacit verb: new =: (halve ` mult) @. odd
In the definition of new , the symbol ` (backquote, called the "Tie" conjunction) ties together halve and mult to make a list of two verbs. Then, in evaluating (new y), the value of (odd y) is used to index the list (halve`mult). Then the selected verb is applied to y. That is, halve y or mult y is computed accordingly as odd y is 0 or 1. In this example, we have two cases to consider: the argument is odd or not. In general, there may be several cases. The general scheme is, if u0, u1 , ... un are verbs, and t is a verb computing an integer in the range 0 .. n, then the verb:
foo =: u0 ` u1 ` ...` un @. t
can be modelled by the explicit verb: FOO =: 3 : 0 if. (t y.) = 0 do. u0 y. elseif. (t y.) = 1 do. u1 y. NB. ... elseif. (t y.) = n do. un y. end. ) That is, verb t tests the argument y and then u0 or u1 or ... is applied to y according to whether (t y) is 0 or 1 or .... Here is another example, with three cases. Suppose that, each month, a bank pays or charges interest according to the balances of customers' accounts as follows. There are three cases:
pi =: * & 1.005 NB. pay interest ci =: * & 1.02 NB. charge interest dn =: * & 1 NB. do nothing
Now we want a verb to compute, from a given balance, 0 or 1 or 2 as the appropriate index into a list of three verbs containing pi , ci and dn. A somewhat heavy-handed but general method is to write verbs to recognise each of the three cases, tried in order: rpi =: >: & 100 NB. equal to or greater than 100 rci =: < & 0 NB. otherwise, less than 0 rdn =: 1: NB. otherwise and combine them into a case-recognising verb as follows: recognise =: (i. & 1 ) @: (rpi, rci, rdn) recognise " 0 (1000 _100 50) 0 1 2 Now we can put everything together: the processing of a balance can be represented by the verb PB say: PB =: pi ` ci ` dn @. recognise
The argument of PB is expected to fall under exactly one of the three possible cases, in order to select exactly one verb (pi or ci or dn) to apply to the whole argument. Hence, if the argument is a list such that different items fall under different cases, then the PB function must be applied separately to each item of its argument.
10.2.2 RecursionTo compute the sum of a list of numbers, we have seen the verb +/ but let us look at another way of defining a summing verb. The sum of an empty list of numbers is zero, and otherwise the sum is the first item plus the sum of the remaining items. If we define three verbs, to test for an empty list, to take the first item and to take the remaining items:
empty =: # = 0:
first =: {.
rest =: }.
then the two cases to consider are:
Sum =: (first + Sum @ rest) ` 0: @. empty Sum 1 1 2 4 Here we see that the verb "Sum" recurs in its own definition and so the definition is said to be recursive. In such a recursive definition, the name which recurs can be written as $: (dollar colon), meaning "this function". This enables us to write a recursive function as an expression, without assigning a name. Here is the "Sum" function as an expression: ((first + $: @ rest) ` 0: @. empty) 1 2 3 6 For another example, let us look at Ackermann's function, celebrated for being extremely recursive. Textbooks show it in a form something like this explicit definition of a dyad: Ack =: 4 : 0 if. x. = 0 do. y. + 1 elseif. y. = 0 do. (x. - 1) Ack 1 elseif. 1 do. (x. - 1) Ack (x. Ack y. -1) end. ) 2 Ack 3 9 A tacit version is due to Roger Hui (Vector, Vol 9 No 2, Oct 1992, page 142): ack =: c1 ` c1 ` c2 ` c3 @. (#. @(,&*)) c1 =: >:@] NB. 1 + y c2 =: <:@[ ack 1: NB. (x-1) ack 1 c3 =: <:@[ ack [ack <:@] NB. (x -1) ack x ack y -1 2 ack 3 9 Notice that in the line defining c2 the function is referred to as ack, not as $:, because here $: would mean c2. Here is yet another version. The tacit version can be made to look a little more conventional by first defining x and y as the verbs [ and ]. Also, we test for only one case on a line. x =: [ y =: ] ACK =: A1 ` (y + 1:) @. (x = 0:) A1 =: A2 ` ((x - 1:) ACK 1:) @. (y = 0:) A2 =: (x - 1:) ACK (x ACK y - 1:) 2 ACK 3 9 10.3 Iteration10.3.1 The Power ConjunctionThink of a number, double it, double that result, double again. The result of three doublings is eight times the original number. The built-in verb +: is "double", and the verb "three doublings" can be written using the "Power" conjunction (^:) as +: ^: 3
The general scheme is that for a verb f and an integer n
(f ^: n) y means f f f ... f f f f y
<--- n f's --->
Notice that f ^: 0 y is just y and then f ^: 1 y is f y . For example ,recall the new verb "halve or multiply-by-3-and-add-1 if odd".
With the Power conjunction we can generate a series by applying new 0 times, once , twice and so on, starting with 6 for example (new ^: 0 1 2 3 4 5 6 ) 6 6 3 10 5 16 8 4 10.3.2 Iterating Until No ChangeThe expression f ^: _, where the Power conjunction is given a right argument of infinity (_), is a verb where f is applied until a result is reached which is the same as the previous result. The scheme is:
f ^: _ y means
r such that r = f f ... f f y
and r = f r
Here is an example. Recall the P function defined above as:
P =: 3 : '4 * lambda * y. * (1 - y.)'
Suppose the parameter lambda is set to say, 0.7. Then if we repeatedly apply the function to an argument in the neighbourhood of 0.5, after 20 or so iterations the result will settle on a result of about 0.643 lambda =: 0.7 (P ^: 0 1 2 3 5 18 19 20 _) 0.5 0.5 0.7 0.588 0.678 0.666 0.642 0.644 0.642 0.643 and this value, r say, is called a fixed point of the P function because r = P r
10.3.3 Iterating WhileThe right argument of the "Power" conjunction can be a verb which computes the number of iterations to be performed. The scheme is:
(f ^: g) y means f ^: (g y) y
If g y computes 0 or 1, then f will be applied 0 times or 1 time: For example, here is a verb which halves an even number and leaves an odd number alone: halve =: -: even =: 0: = 2 & |
Now consider the function w =: (halve ^: even) ^: _ This means "halve if even, and keep doing this so long as the result keeps changing". In other words, while the argument is even, keep halving it. w (3 * 16) 3 The scheme is that a function written (f ^: g ^: _ ) can be modelled by an explicit definition: model =: 3 : 0 while. (g y.) do. y. =. f y. end. y. ) f =: halve g =: even
10.3.4 Iterating A Dyadic VerbAdding 3 to 0, twice, gives 6
The given left argument (3) is fixed at the outset, so the iterated verb is the monad 3&+. The general scheme is:
x (u ^: w) y means ((x&u) ^: w) y
where w is a noun or verb. This is the end of Chapter 10 |
Copyright © Roger Stokes 2001. This material may be freely reproduced, provided that this copyright notice is also reproduced.
last updated 09Jun01