Ch 10: Conditional and Other Forms

| # Chapter 10: Conditional and Other Forms Tacit 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: Conditional forms Recursive forms Iterative forms Generating tacit definitions from explicit definitions ## 10.1 Conditional Forms Think 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 & |
`halve 6` | `mult 6` | `odd 6`
    3
    19
    0
Now our procedure for a new number can be written as an explicit verb:
       NEW =: 3 : 'if. odd y. do. mult y. else.  halve y. end. '
and equivalently as a tacit verb:
       new =: (halve ` mult) @. odd
`NEW 1` | `new 1`
    4
    4
In the definition of `new`, 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 `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.
      ...
    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 Cases Suppose that, each month, a bank pays or charges interest according to the balances of customers' accounts as follows. There are three cases: If the balance is $100 or more, the bank pays interest of 0.5% If the balance is negative, the bank charges interest at 2%. Otherwise the balance is unchanged. 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
`pi 1000` | `ci _100` | `uc 50`
    1005
    _102
    50
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
`PB _50` | `PB 0` | `PB 1` | `PB 100` | `PB 200`
    _51
    0
    1
    100.5
    201
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.
`PB 99 100` | `(PB "0) 99 100`
    error
    99 100.5
## 10.2 Recursion To 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: an empty list, in which case we apply the `0:` function to return zero a non-empty list, in which case we want the first plus the sum of the rest:
       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 Function Ackermann'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 Iteration ### 10.3.1 The Power Conjunction Think 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`
`+: +: +: 1` | `(+: ^: 3 ) 1`
    8
    8
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".
`(new ^: 0) 6` | `(new ^: 1) 6` | `new 6`
    6
    3
    3
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 Change The 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`
`r =: (P ^: _) 0.5` | `P r`
    0.6429
    0.6429
### 10.3.3 Iterating While The 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 & |
`foo =: halve ^: even` | `(foo " 0) 1 2 3 4`
    halve^:even
    1 1 3 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
`(f ^: g ^: _) 3 * 16` | `model 3*16`
    3
    3
### 10.3.4 Iterating A Dyadic Verb Adding `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 Explicit Suppose 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.'
`e` | `t` | `e 1 2 3` | `t 1 2 3`
    3 : '(+/ y.) % # y.'
    +/ % #
    2
    2
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.'
`ed` | `td` | `2 ed 6` | `2 td 6`
    4 : 'y. % x.'
    ] % [
    3
    3
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:
`k =: 99` | `p =: 3 : 'y.+k'` | `q =: 13 : 'y.+k'` | `p 6` | `q 6`
    99
    3 : 'y.+k'
    ] + 99"_
    105
    105
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.
`k =: 0` | `p 6` | `q 6`
    0
    6
    105
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 =: %:
`foo =: 13 : '(f C f y.) , g y.'` | `f =: *:` | `foo 4`
    f@:f , [: g ]
    *:
    256 2
This is the end of Chapter 10

NEXT
Table of Contents
Index

Copyright © Roger Stokes 2004. This material may be freely reproduced, provided that this copyright notice is also reproduced.

last updated 15 Oct 2004