Help / Learning / Ch 10: Conditional and Other Forms
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J
|
|
Chapter 10: Conditional and Other FormsTacit verbs, that is, verbs defined without the use of argument variables, were introduced in Chapter 03. Continuing this theme of tacit definition, in Chapter 08 we looked at the use of composition-operators and in Chapter 09 at trains of verbs. The plan for this chapter is to look at further ways of defining verbs tacitly:
10.1 Conditional FormsThink 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. A sequence of numbers generated by iterating the procedure is called a Collatz sequence, or sometimes a Hailstone sequence. For example: 17 52 26 13 40 To write a function for this procedure, we start with three verbs, say halve to halve, mult to multiply-and-add-one, 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: COLLATZ =: 3 : 'if. odd y do. mult y else. halve y end. ' and equivalently as a tacit verb: collatz =: halve ` mult @. odd
In the definition of collatz, the symbol ` (backquote) is called the "Tie" conjunction. It ties together halve and mult to make a list of two verbs. (Such a list is called a "gerund" and we look at more uses of gerunds in Chapter 14). The conjunction @. is called "Agenda". Its right argument is a verb, which selects another verb from the list of verbs which is the left argument. Thus in evaluating collatz 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 ... 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 .... 10.1.1 Example with 3 CasesSuppose that, each month, a bank pays or charges interest according to the balances of customers' accounts as follows. There are three cases:
Three verbs, one for each of the three cases, could be: pi =: * & 1.005 NB. pay interest ci =: * & 1.02 NB. charge interest uc =: * & 1 NB. unchanged
Now we want a verb to compute, from a given balance, 0 or 1 or 2, according to the case. We are free to choose how we number the cases. The following verb scores 1 for a balance of $0 or more plus another 1 for $100 or more. case =: (>: & 0) + (>: & 100) case _50 0 1 100 200 0 1 1 2 2 Now the processing of a balance can be represented by the verb PB say, being careful to write the three verbs in the correct case-number order.
PB =: ci ` uc ` pi @. case
The balance (the argument of PB) is expected to fall under exactly one of the three possible cases. Suppose the argument is a list of balances. The case verb delivers not just one but a list of case-numbers. This is an error. The remedy is to apply the PB function separately to each item of its argument.
10.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, called "Self-Reference"), 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 10.2.1 Ackermann's FunctionAckermann's function is 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 collatz verb "halve or multiply-by-3-and-add-1 if odd".
With the Power conjunction we can generate a series by applying collatz 0 times, once, twice and so on, starting with 6 for example (collatz ^: 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. Suppose function P is defined as: P =: 3 : '2.8 * y * (1 - y)' 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 value of about 0.643 (P ^: 0 1 2 3 19 20 _) 0.5 0.5 0.7 0.588 0.6783 0.6439 0.642 0.6429 and this value, r say, is called a fixed point of P 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". w (3 * 16) 3 The scheme is that if g returns 0 or 1 then 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, twice, to 0 gives 6 ((3&+) ^: 2) 0 6 This expression can be abbreviated as: 3 (+ ^: 2) 0 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. 10.4 Generating Tacit Verbs from ExplicitSuppose that e is a verb, defined explicitly as follows: e =: 3 : '(+/ y) % # y' The right argument of the colon conjunction we can call the "body". Then a tacit verb, t say, equivalent to e, can be produced by writing 13 : instead of 3 : with the same body. t =: 13 : '(+/ y) % # y'
Here now is an example of an explicit dyad. ed =: 4 : 'y % x' The equivalent tacit dyad can be generated by writing 13 : rather than 4 : with the same body. td =: 13 : 'y % x'
We can conclude that if we write 13 : body, and body contains y (but not x) then the result is a tacit verb of which the monadic case is equivalent to 3 : body. On the other hand, if body contains both x and y then the result is a tacit verb of which the dyadic case is equivalent to 4 : body. For the purpose of generating tacit functions, the body is restricted to being a single string or one line. Recall that with 3 : body, the body is not evaluated when the definition is entered. However, with 13 : body, then in effect the body is evaluated. For example:
We see that p is defined in terms of k while q is not. While p and q are at present equivalent, any subsequent change in the value of k will render them no longer equivalent.
A name with no assigned value is assumed to denote a verb. In the following example, note that f is unassigned, C is a predefined conjunction and g is a predefined verb. C =: @: g =: %:
This is the end of Chapter 10 |
The examples in this chapter
were executed using J version 701.
This chapter last updated 29 Jul 2012
Copyright © Roger Stokes 2012.
This material may be freely reproduced,
provided that this copyright notice is also reproduced.
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Learning J