Ch 14: Gerunds

| # Chapter 14: Gerunds What is a gerund, and what is it good for? Briefly, a gerund represents a list of verbs. It is useful, in the main, for supplying a list of verbs as a single argument to an operator. The plan for this chapter is: to introduce gerunds to look at some built-in operators which can take gerunds as arguments to look at user-defined operators taking gerund arguments ## 14.1 Making Gerunds: The Tie Conjunction Recall from Chapter 10 how we defined a verb with several cases. Here is a small example as a reminder. To find the absolute value of a number `x` we compute `(+x)`, or `(-x)` if the number is negative, thus:
`abs =: + ` - @. (< & 0)` | `abs _3`
    +`-@.(<&0)
    3
The expression `(+`-)` looks like a list of verbs. Here the two verbs `+` and `-` are tied together with the "Tie" conjunction (```, backquote, different from `'`) to produce a gerund.
       + ` -
    +-+-+
    |+|-|
    +-+-+
We see that the gerund `(+ ` -)` is a list of two boxes, each of which contains a representation of a verb. A gerund is a noun - a list of boxes. Here is another gerund which represents three verbs:
       G =: + ` - ` abs
       G
    +-+-+---+
    |+|-|abs|
    +-+-+---+
Inside each box there is a data structure which represents, or encodes, a verb. Here we will not be concerned with the details of this representation, which will be covered in Chapter 27. ## 14.2 Recovering the Verbs from a Gerund The verbs packed into a gerund can be unpacked again with the built-in adverb "Evoke Gerund" which is denoted by the expression `(`: 6)`. Let us call this `EV`.
       EV =: `: 6
Adverb `EV` applied to a gerund yields a train of all the verbs in the gerund. In the next example, the result `foo` is a 3-train, that is a fork.
       f =: 'f' & ,
       g =: 'g' & ,
`H=: f ` , ` g` | `foo =: H EV` | `foo 'o'`
    +-+-+-+
    |f|,|g|
    +-+-+-+
    f , g
    fogo
Individual verbs can be unpacked by indexing the boxed list `H` and then applying `EV`.
`H` | `2{H` | `vb =: (2{H) EV` | `vb 'o'`
    +-+-+-+
    |f|,|g|
    +-+-+-+
    +-+
    |g|
    +-+
    g
    go
Shorter trains can be unpacked from a gerund, again by indexing.
`H` | `1 2 { H` | `tr =: (1 2 { H) EV` | `tr 'a'`
    +-+-+-+
    |f|,|g|
    +-+-+-+
    +-+-+
    |,|g|
    +-+-+
    , g
    aga
Now we come to the uses of gerunds. ## 14.3 Gerunds As Arguments to Built-In Operators A major use of gerunds is that they can be supplied to operators as a single argument containing multiple verbs. We look first at further built-in operators taking gerund arguments, and then at examples of home-made operators. ### 14.3.1 Gerund as Argument to APPEND Adverb There is a built-in adverb called "APPEND", denoted by the expression `(`: 0)`. It applies a list of verbs to a single argument to give a list of results. For example:
       APPEND =: `: 0
       sum    =: +/
       count  =: #
       mean   =: sum % count
       G1     =: count ` sum ` mean
`G1` | `foo =: G1 APPEND` | `foo 1 2 3`
    +-----+---+----+
    |count|sum|mean|
    +-----+---+----+
    count`sum`mean`:0
    3 6 2
The adverb is called `APPEND` because the results of the individual verbs in the gerund are appended, that is formed into a list. The general scheme is that for verbs `u`, `v`, `w` , ... then
          (u`v`w...) APPEND y  means  (u y), (v y), (w y) , ...
Here is another example, showing that a gerund can be, not just a one-dimensional list, but an array of verbs. The list of verbs `G1` formed by "Tie" can be reshaped into an array, a table say, and the shape of the result is the same.
`G2 =: 2 2 $ G1` | `G2 APPEND 4 5`
    +-----+-----+
    |count|sum  |
    +-----+-----+
    |mean |count|
    +-----+-----+
      2 9
    4.5 2
### 14.3.2 Gerund as Argument to Agenda Conjunction Recall the `abs` verb defined above. Here is a reminder:
`abs =: + ` - @. (< & 0)` | `abs 6` | `abs _6`
    +`-@.(<&0)
    6
    6
Here, the "Agenda" conjunction `(@.)` takes a verb on the right. As a variation, `(@.)` can also take a noun on the right. The noun consists of a list of numbers, which are indices selecting verbs from the gerund. The selected verbs form a train. This scheme gives us an abbreviation for the unpacking by indexing we saw above. The scheme is, for a gerund `G` and a list of indices `I` :
               G @. I   means   (I { G) EV
For example:
`G =: +`-`%` | `tr =: G @. 0 2` | `tr 4` | `(0 2 { G) EV 4`
    +-+-+-+
    |+|-|%|
    +-+-+-+
    + %
    4.25
    4.25
Next, we look at how to build trains with more structure. Consider the train `T`:
`T =: * (- 1:)` | `T 3` | `T 4`
    * (- 1:)
    6
    12
which computes `(T x) = x * (x -1)` . The parentheses mean that `T` is a hook where the second item is also a hook. Trains structured with parentheses in this way can be built with Agenda, by indexing items from a gerund, using boxed indices to indicate the parenthesisation.
       foo =: (* ` - ` 1:) @. (0 ; 1 2)
`T` | `foo` | `foo 3`
    * (- 1:)
    * (- 1:)
    6
### 14.3.3 Gerund as Argument to Insert We have previously encountered the insert adverb applied to a single verb: the verb is inserted between successive items of a list. More generally, when insert is applied to a gerund it inserts successive verbs from the gerund between successive items from the list. That is, if `G` is the gerund `(f`g`h`...)` and and `X` is the list `(x0, x1, x2, x3, ...)` then
          G/X    means   x0 f x1 g x2 h x3 ...
`ger =: + ` %` | `ger / 1 2 3` | `1 + 2 % 3`
    +-+-+
    |+|%|
    +-+-+
    1.66667
    1.66667
If the gerund is too short, it is re-used cyclically to make up the needed number of verbs. This means that a one-verb gerund, when inserted, behaves the same as a single inserted verb. ### 14.3.4 Gerund as argument to POWER conjunction Recall from Chapter 10 that the POWER conjunction `(^:)` can take, as right argument, a number which specifies the number of iterations of the verb given as left argument. As a brief reminder, 3 doublings of 1 is 8:
       double =: +:
       (double ^: 3) 1
    8
As a variation, the number of iterations can be computed by a verb right-argument. The scheme is, for verbs `u` and `v`:
          (u ^: v) y   means   u ^: (v y) y
For example:
       decr =: <:
`double ^: (decr 3) 3` | `(double ^: decr) 3`
    12
    12
More generally, the right argument can be given as a gerund, and the verbs in it do some computations at the outset of the iteration process. The scheme is:
          u ^: (v1 ` v2) y   means    u ^: (v1 y) (v2 y)
To illustrate, we define a verb to compute a Fibonacci sequence. Here each term is the sum of the preceding two terms. The verb will take an argument to specify the number of terms, so for example we want `FIB 6` to give `0 1 1 2 3 5` The verb to be iterated, `u` say, generates the next sequence from the previous sequence by appending the sum of the last two. If we define:
       u        =: , sumlast2
       sumlast2 =: +/ @ last2
       last2    =: _2 & {.
then the iteration scheme beginning with the sequence 0 1 is shown by
`u 0 1` | `u u 0 1` | `u u u 0 1`
    0 1 1
    0 1 1 2
    0 1 1 2 3
Now we define the two verbs of the gerund. We see that to produce a sequence with `n` terms the verb `u` must be applied `(n-2)` times, so the verb `v1`, which computes the number of iterations from the argument `y` is:
             v1 =: -&2
The verb `v2`, which computes the starting value from the argument `y`, we want to be the constant function which computes `0 1` whatever the value of `y`.
             v2 =: 3 : '0 1'
Now we can put everything together:
`FIB =: u ^: (v1 `v2)` | `FIB 6`
    u^:(v1`v2)
    0 1 1 2 3 5
This example showed a monadic verb `(u)` with the two verbs in the gerund (`v1` and `v2`) performing some computations at the outset of the iteration. What about dyadic verbs? Firstly, recall that with an iterated dyadic verb the left argument is bound at the outset to give a monad which is what is actually iterated, so that the scheme is:
      x  u ^: k  y    means    (x&u) ^: k y
Rather than constant `k`, we can perform pre-computations with three verbs `U` `V` and `W` presented as a gerund. The scheme is:
          x u ^: (U`V`W) y  means  (((x U y)&u) ^: (x V y))  (x W y)
or equivalently as a fork:
          u ^: (U`V`W)   means   U (u ^: V) W
For example, suppose we define::
       U =: [
       V =: 2:
       W =: ]
Then we see that `p` and `q` below are equivalent. 3 added twice to 4 gives 10.
`p =: + ^: (U`V`W)` | `3 p 4` | `q =: U (+ ^: V) W` | `3 q 4`
    +^:(U`V`W)
    10
    U +^:V W
    10
### 14.3.5 Gerund as Argument to Amend Recall the "Amend" adverb from Chapter 06 . The expression `(new index } old)` produces an amended version of `old`, having `new` as items at `index`. For example:
          'o'  1 } 'baron'
    boron
More generally, the "Amend" adverb can take an argument which is a gerund of three verbs, say `U`V`W`. The scheme is:
    x (U`V`W) } y  means (x U y) (x V y) } (x W y)
That is, the new items, the index(es) and the "old" array are all to be computed from the given `x` and `y`. Here is an example (adapted from the Dictionary). Let us define a verb, `R` say, to amend a matrix by multiplying its `i`'th row by a constant `k`. The left argument of `R` is to be the list `i k` and the right argument is to be the original matrix. `R` is defined as the "Amend" adverb applied to a gerund of 3 verbs.
       i =: {. @ [    NB. x i y  is  first of x
       k =: {: @ [    NB. x k y  is  last of x
       r =: i { ]     NB. x r y  is  (x i y)'th  row of y

       R =: ((k * r) ` i ` ]) }
For example:
       M =: 3 2 $ 2 3 4 5 6 7
       z =: 1 10      NB. row 1 times 10
`z` | `M` | `z i M` | `z k M` | `z r M` | `z R M`
    1 10
    2 3
    4 5
    6 7
    1
    10
    4 5
     2  3
    40 50
     6  7
## 14.4 Gerunds as Arguments to User-Defined Operators Previous sections showed supplying gerunds to the built-in operators (adverbs or conjunctions). Now we look at defining our own operators taking gerunds as arguments. We begin with explicit operators and then go on to tacit operators. The main consideration with an explicit operator is how to recover individual verbs from the gerund argument. We saw several possibilities above. Here is a simple one. Let `g Untie i` give the `i`'th verb in gerund `g`. We index `g` to get the `i`'th representation, and then apply adverb `EV` to turn the representation into a verb:
       Untie =: 2 : '(y. { x.) EV'
`plus =: (*`-` +) Untie 2` | `2 plus 3`
    +
    5
Now for the operator. Let us define an adverb `A`, say, to produce a fork-like verb, so that `x (u`v`w A) y` is to mean `(u x) v (w y)`.
       A =: 1 : 0
    u =. x. Untie 0
    v =. x. Untie 1
    w =. x. Untie 2
    ((u @ [) v (w @ ])) f.
    )
To illustrate `A`, here is a verb to join the first item of `x` to the last of `y`. The first and last items are yielded by the built-in verbs `{.` (left-brace dot, called "Head") and `{:` (left-brace colon, called "Tail").
`g =: {. ` , ` {:` | `zip =: g A` | `'abc' zip 'xyz'`
    +--+-+--+
    |{.|,|{:|
    +--+-+--+
    {.@[ , {:@]
    az
### 14.4.1 The Abelson and Sussman Accumulator Here is another example of a user-defined explicit operator with a gerund argument. Abelson and Sussman ("Structure and Interpretation of Computer Programs", MIT Press 1985) describe how a variety of computations all conform to the following general plan, called the "accumulator": Items from the argument (a list) are selected with a "filtering" function. For each selected item, a value is computed from it with a "mapping" function. The results of the separate mappings are combined into the overall result with a "combining" function. This plan can readily be implemented in J as an adverb, `ACC` say, as follows.
          ACC =: 1 : 0
    'com map fil' =. <"0 x.
    ((com EV /)  @:  (map EV)  @:  (#~ fil EV))  f.
    )
`ACC` takes as argument a gerund of three verbs, in order, the combiner, the map and the filter. For an example, we compute the sum of the squares of the odd numbers in a given list. Here the filter, to test for an odd number, is `(2&|)`
          (+ ` *: ` (2&|)) ACC 1 2 3 4
    10
The first line of `ACC` splits up the gerund argument into three 1-item gerunds, `com` `map` and `fil`. The boxing `(<"0)` is needed because the multiple assignment automatically strips off one layer of boxing. In the second line, `EV` is applied to each 1-item gerund to yield its verb. This is the end of chapter 14.

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 21 Oct 2004