>>  <<  Ndx  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  wd  Help  Learning J

Chapter 14: Gerunds

What is a gerund, and what is it good for? Briefly, a gerund represents a list of verbs. It is useful mainly 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. This noun can be a single number or a list of numbers. A single number is taken as an index selecting a verb from the gerund. For example.

G =: + ` - ` % f =: G @. 0 1 f 1
+-+-+-+
|+|-|%|
+-+-+-+
+ 2

A list of numbers is taken as a list of indices selecting verbs from the gerund to form a train. In the following example the selected two verbs form a hook.

G h =: G @. 0 2 h 4
+-+-+-+
|+|-|%|
+-+-+-+
+ % 4.25

The scheme is, for a gerund G and indices I :

           G @. I   means   (I { G) EV

For example:

G (G @. 0 2) 4 ((0 2 { G)) EV 4
+-+-+-+
|+|-|%|
+-+-+-+
4.25 4.25

This scheme gives us an abbreviation for the unpacking by indexing we saw above.

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
(, sumlast2)^:(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.

The main consideration with an operator is how to recover individual verbs from the gerund argument. Useful here is the agenda conjunction @. which we looked at above. Recall that it can select one or more verbs from a gerund.

G G @. 0 G @. 0 2
+-+-+-+
|+|-|%|
+-+-+-+
+ + %

Now for the operator. Let us define an adverb A, say, to produce a fork-like verb, so that

      x (f `g ` h  A)  y   is to mean   (f x) g (h y)  
     
   
   A =: 1 : 0
f =. u @. 0
g =. u @. 1
h =. u @. 2
((f @ [) g (h @ ]))  f.
)
   

To demonstrate 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").

H =: {. ` , ` {: zip =: H 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 =. u @. 0
map =. u @. 1
fil =. u @. 2
((com /)  @:  map  @:  (#~ fil))  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
   

This is the end of chapter 14.


NEXT
Table of Contents
Index


The examples in this chapter were executed using J version 601 beta. This chapter last updated 12 Jun 2006 .
Copyright © Roger Stokes 2006. This material may be freely reproduced, provided that this copyright notice is also reproduced.


>>  <<  Ndx  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  wd  Help  Learning J