Chapter 14: Chapter 14: Gerunds

In this chapter we consider 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.

14.1 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. The definitions are repeated here:

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

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 is 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) 

Example to be supplied

The scheme above can also be written equivalently as a fork:

	 u ^: (U`V`W)   means   U (u ^: V) W 

For example:

   U =: [
   V =: 2:
   W =: ]
   

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. i = first of x
   k =: {: @ [    NB. k = last of x
   r =: i { ]     NB. i'th row
   
   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, (reference ...), 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.

14.5 Gerunds in Train-Making

In this section we look at how gerunds can play a role in tacit operators, in particular in operators which build trains.

What we will see (eventually!) is how a tacit operator can work by building a gerund from its arguments and then doing something with the gerund.

14.5.1 Review

We begin with a simple example (not involving gerunds), just to remind ourselves how the bidents or tridents of Chapter 13 can be used to define tacit operators. Suppose we aim to define an adverb, B say, to generate a hook according to the scheme :

       x B   =    (x A) V

where x is the argument-verb, A is a given adverb and V a given verb. From Chapter 13 we recall the bident AV with the scheme:

            x (A V)   =   (x A) V

and thus B is straightforwardly written as a bident of the form (A V). To illustrate, if for A we take ~, and for V we take the built-in verb >: (increment) then we have:

   B =: ~ >:   NB. adverb verb

Suppose for the schematic argument x we take the verb (,) then we see that (, B) is a hook:

B hook =: , B hook 2 2 (,~) >: 2
~ >:
,~ >:
3 2
3 2

14.5.2 Problem

In the last example it was straightforward to arrive at the definition of B because in Chapter 13 we found a bident (AV) with a right-hand side (x A) V which was just right for our purpose. Now, how can we define a hook-generating conjunction, T say, as a bident or trident according to the scheme

      x T y     =   (x C y) V

where C is a given conjunction and V is a given verb? The problem is that there is no bident or trident in Chapter 13 with a scheme which looks like this:

         x (???) y   = (x C y)  V

Here is a scheme which will in fact do the job:

            x (C (`V) EV) y   =  (x C y) V

(where EV we defined above as `: 6, "Evoke Gerund"). Two questions arise immediately: how did we arrive at this, and how does it work? We will come back to these questions, but first let us make sure it does work.

For conjunction C and verb V suppose we take:

   C =: "
   V =: >: 

Now we write our conjunction T as a trident, matching the pattern of the left-hand side of the scheme,

   T =: C (`V) EV  

If we take for the schematic arguments x and y the verb , and the noun 1 then we see that (, T 1) is a hook of the required form (x C y) V.

h =: , T 1 h 2 2 ,"1 >: 2
,"1 V
2 3
2 3

14.5.3 How did we arrive at this scheme?

There is an easy way to find a scheme like this. The J system itself can automatically generate a tacit form by translating an explicit definition. (See Chapter 15 ).

Recall the scheme we wanted for T, which was:

       x T  y   =  (x C y)  V

We want to find a tacit expression for T, that is, we want to find a tacit equivalent to the explicit definition

   E =: 2 : '(x. C y.) V'

where we intend C and V to be:

   C =: "
   V =: >:

we find the tacit equivalent of E by writing 12 : rather than 2 : and otherwise the same as E

   T =: 12 : '(x. C y.) V'
   

T , T 1 (, C 1) V , E 1
C (`V) (`:6)
,"1 V
,"1 V
,"1 V

Notice that the automatically-generated form of T has `: 6 where we earlier wrote EV (but of course we defined EV to be `: 6)

These automatically-generated expressions may sometimes appear unfamiliar. Hence our purpose in this section has been, in part, to become acquainted with expressions of this kind before we come to the next chapter.

14.5.4 How does this scheme work?

Recall that the scheme was:

          x (C (`V) EV) y   =  (x C y) V

On the left-hand side, ` and EV are tell-tale signs of introducing and using a gerund.

To see in more detail how the scheme works we can start from the left-hand side and, step by step, derive the right-hand side, at each step showing an expression equivalent to the previous. The derivation is more convincing if we evaluate each expression to show that it computes the same result as the previous.

To make the expressions evaluatable, schematic variables x y and V can appear as themselves if we erase the names beforehand, so they are treated as unknown verbs. However, for C we must have a definite evaluatable conjunction. For this we choose @ since x@y always evaluates to x@y for unknown x and y. Hence the preparations we need are:

   erase 'x';'y';'V'    
1 1 1
   C =: @               

Here now is a derivation.

   x (C (`V) EV) y        
x@y V

This is the left-hand side. We see that it is of the form x (conjunction adverb adverb) y
   ((x C y) (`V)) EV 
x@y V

Obtained from previous by applying trident CAA, for which the scheme is x (C A A) y = ((x C y) A) A. Now we see that (`V) is of the form conjunction adverb
   ((x C y) ` V) EV      
x@y V

Obtained from previous by applying by bident CV, for which the scheme is x (C V) = (x C V). Now we see that ((x C y) ` V) is a gerund.
   (x C y) V
x@y V

Obtained from previous by applying adverb EV to the gerund, according to the scheme u`v`w... EV = (u v w... ). Now we have the right-hand side.

14.5.5 Another Example

Suppose we aim to define tacitly an adverb, Q say, which generates a hook according to the scheme:

      x Q    =   V (x A)

where V is a given verb and A a given adverb. In the absence of a directly suitable bident or trident in Chapter 13, we say Q is to be a tacit equivalent of the explicitly-defined E:

   E =: 1 : 'V (x. A)'

We get the tacit equivalent by taking A to be / and V to be %, then defining Q as the same as E but writing 11 : rather than 1 :

   A =: /
   V =: %
   
   Q =: 11 : 'V (x. A)'

We see that + Q is a hook

Q + Q + Q 1 2 1 + E 1 2 1
A (V`) (`:6)
V +/
0.25 0.5 0.25
0.25 0.5 0.25

and that this scheme is valid:

          x (A (V`) EV)  =  V (x  A)

This scheme can be derived as follows. By way of preparations, A must be a definite adverb (it is) and x must be an unknown name (it is). Our derivation is:

   x (A (V`) EV)       
V x/

Beginning with the left-hand side, which is of the form x (adverb adverb adverb)
   ((x A) (V`)) EV    
V x/

Obtained by applying trident AAA, for which the scheme is x (A A A) = ((x A) A) A. Now we notice that V` is of the form verb conjunction.
   (V ` (x A)) EV 
V x/

Obtained by applying bident VC for which the scheme is x (V C) = V C x. Now we notice that V ` (x A) is of the form verb`verb, that is a gerund.
   V (x A) 
V x/

Obtained by applying adverb EV for which the scheme is u`v`w...EV = (u v w ...). We get the right-hand side.

This is the end of chapter 14.


NEXT
Table of Contents


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

last updated 14 Mar 2002