Skip to content

6.8 Inspiration from APL

Claude Roux edited this page Jan 30, 2022 · 1 revision

APL

Version française

APL is certainly one of the most cryptic and surprising languages ever created. Born from the mathematical notations of Kenneth Iverson at Harvard, to manipulate arrays and lists, this language allows to write a code of a rare sobriety. APL often manages to implement complex matrix manipulations in a few symbols where established languages require lines and lines of code.

The following example shows how to implement the multiplication of two matrices in three symbols:

 M +.× N   

The '.' is called: internal product. At each iteration, it multiplies a row of M by a column of N, and then sums each element of the resulting vector.

APL alone defines a paradigm of its own, where the efficiency of the formulation makes most other languages horribly wordy and cumbersome by comparison. But, even if we don't pretend to build a APL interpreter here, it seemed to us that a language like LispE which manipulates lists for a living, could only benefit from the power and richness of some of these instructions.

Infuse, in a way, the magic of APL in LispE.

Adaptations

But before we get into how we drew inspiration from APL, let's describe some of the concepts we integrated into LispE to make this enrichment possible.

New containers: numbers, matrix and tensor

We have added three new types of containers to make the use of these new instructions as transparent and simple as possible.

  • numbers: this is a list that contains only double float values: (0.1 1.2 1.4)
  • matrix: this is an NxM matrix where each row is a numbers list: ( (numbers) (numbers)... (numbers))
  • tensor: it is a matrix N1xN2x..xNn, the deepest lines are also numbers lists

Note that tensors and matrices are by default list objects to which we have added dimensions. Note also that numbers, matrix and tensor are also instructions that can transform a list into the corresponding object:

(range 0 1 0.1) ; creates a list of type numbers: (0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1)
(numbers '(1 2 3 4)) ; transforms this list into a list of doubles
(numbers 1 2 3 4) ; generate directly a list of doubles
(matrix '((1 2 3) (4 5 6)) ) ; creates the corresponding matrix
(tensor '( ( (1 2 3) (3 4 5) ) ( (6 7 8) (9 10 11) )

The set of instructions we are going to present applies to these containers.

Extending the domain of numerical operators

By default, numerical operators such as + - * / % ~ & &~| % apply to scalars as well as to lists or even lists of lists.

(+ 1 2 3); gives 6
(+ '(1 2 3)); gives 6
(+ '(1 2 3) 10) ; gives (11 12 13)
(+ '(1 2 3) '(1 2 3)) ; gives (2 4 6)
(+ '((1 2 3) (4 5 6)) 10); gives ((11 12 13) (14 15 16))
(+ '((1 2 3) (4 5 6) (6 7 8)) '(10 20 30)); gives ((11 12 13) (24 25 26) (36 37 38))

The APL philosophy

APL provides a list of operators whose main purpose is to manipulate vectors, matrices or tensors. Most of these operators have a dual interpretation depending on whether they are used with one argument (monadic) or two arguments (dyadic). For example, the operator rho:⍴ renders the dimensions of a matrix in monadic mode or constructs a matrix when the number of arguments is greater.

We have implemented only a very small part of all the operators of the language, so we do not pretend here to offer a complete interpreter of the language. It is possible that we will add new operators in the future, but for the moment the list is limited to the instructions that we found most interesting, and this is purely subjective.

⍳: iota, iota0

The first of these instructions is iota which can be said to be at the heart of most examples in APL. iota is a monadic function that returns a list of integers bounded by the value provided. The version iota0 starts this list at 0, while iota starts it from 1.

(iota 10); gives (1 2 3 4 5 6 7 8 9 10)
(iota0 10); gives (0 1 2 3 4 5 6 7 8 9)

We implemented this function to keep some consistency with APL, but admittedly it duplicates range.

⍴: rho

rho is by far the most powerful method in the language. Used with a container, it renders its dimensions. Used with dimensions and a flat list of values, it builds the corresponding matrix or tensor by drawing from the list for its initialization. Note that when the list contains less values than the container to build, we re-start from the beginning of the list to continue the initialization.

(rho '((1 2) (3 4))) ; gives (2 2)
(rho 2 2 (iota 4)) ; gives ((1 2) (3 4))
(rho 2 2 2 (iota 4)); gives (((1 2) (3 4)) ((1 2) (3 4))
(rho 3 3 3 (gamma_distribution 30 1 0.4))
; gives (((0.432632 0.0582416 0.133275) (0.201316 0.251462 0.325018) (0.0110476 0.853308 1.30962)) ((0.152873 0.588721 0.898728) (0.0208302 0. 142427 0.350234) (0.123387 0.582459 0.243948)) ((0.233026 0.829267 0.161644) (0.151935 0.286315 0.00731607) (0.0511841 0.273263 0.509721)))

// : Reduce operator

Note that the APL version contains only one /, which in our case would have been ambiguous with the division operator. It is for the same reason that we have also called the scan operator \\ (see below).

Note that this operator also has an alphabetical name: reduce which can be used instead of //.

  • This operator allows you to apply an operation between all the elements of a list.
  • It also allows you to eliminate or reduce the number of elements in a list by providing a list of integers.
(// + '(1 2 3)); gives 6
(reduce + '(1 2 3)); gives 6
(// '(1 0 2) '(1 2 3)); gives (1 3 3)

or -// : back-reduce

This operator applies operations from the end of the list.

Note that this operator also has an alphabetical name: backreduce which can be used instead of -//.

You can see the difference immediately in the following example:

(// '- '(1 2 3)); gives -4
(-// '- '(1 2 3)) ; gives 0
(⌿ - '(1 2 3)); also gives 0

\\: scan operator

  • This operator is used to scan a list and apply between each element a given operator. Each intermediate result is kept in a list.
  • It can also be used in conjunction with a list of numeric values to extend a list.

Note that this operator also has an alphabetical name: scan which can be used instead of \\.

(\\'+ '(1 2 3)); yields (1 3 6) [1 (1+2) ((1+2)+3)
(\\ '(1 0 2) '(4 6)); yields (4 0 6 6)

or -\\: back-scan

This operator works in the same way as \\, except that it applies the operators from the end of the list.

Note that this operator also has an alphabetical name: backscan which can be used instead of -\\.

If we compare the two following lines, we can immediately see the difference:

(\\ - '(1 2 3)); gives (1 -1 -4)
(⍀ '- '(1 2 3)); gives (3 1 0)

External product: (° L1 operator L2)

This operator applies an operation between each element of L1 and each element of L2.

'(2 3 4) * '(1 2 3 4)); gives ((2 4 6 8) (3 6 9 12) (4 8 12 16))

Inner product : (. M1 reduce_operator row_column_operator M2)

The inner product first applies the row column operator between a row of M1 and a column of M2, then applies a reduction using the reduce operator on the resulting vector.

For example, one can perform a multiplication of two matrices in this way:

(. '((1 2) (5 4) (3 0)) + * '((6 2 3 4) (7 0 1 8)))

; which gives us:

((20 2 5 20) (58 10 19 52) (18 6 9 12))

In other words:

  TABLE1           TABLE2            TABLE
  1    2         6  2  3  4       20  2  5 20 
  5    4         7  0  1  8       58 10 19 52
  3    0                          18  6  9 12

More Operators

We have also implemented other operators such as:

  • transpose: transpose a row/column matrix
  • rank: extraction of a submatrix from a tensor according to rows and columns
  • invert: inversion of a matrix
  • solve: solve a set of equations with several unknown variables
  • reverse: transpose a matrix or a tensor along a given axis

Here are some examples:

(setq m (rho 3 2 (iota 6))); m is now ((1 2) (3 4) (5 6))
(reverse m); gives ((2 1) (4 3) (6 5)). the default axis is 1
(reverse m 0) ; gives ((5 6) (3 4) (1 2))

(setq m (rho 3 4 5 (iota 60)))
;(((1 2 3 4 5) (6 7 8 9 10) (11 12 13 14 15) (16 17 18 19 20)) 
;((21 22 23 24 25) (26 27 28 29 30) (31 32 33 34 35) (36 37 38 39 40)) 
;((41 42 43 44 45) (46 47 48 49 50) (51 52 53 54 55) (56 57 58 59 60)))

(rank m 1); gives ((21 22 23 24 25) (26 27 28 29 30) (31 32 33 34 35) (36 37 38 39 40))
(rank m 1 1); gives (26 27 28 29 30)
(rank m -1 1); gives ((6 7 8 9 10) (26 27 28 29 30) (46 47 48 49 50))
(rank m -1 -1 1); gives ((2 7 12 17) (22 27 32 37) (42 47 52 57))

(invert (rho 2 2 (iota 4))); gives ((-2 1) (1.5 -0.5))

A slightly richer example

Someone forecasts investments in a foreign country for the next 5 years:

(setq Inv (numbers 2000 5000 6000 4000 2000))

But the country in question suffers from inflation, and the inflation rates are forecast as follows:

(setq Inf (numbers 2.6 2.9 3.4 3.1 2.7))

We can easily normalize these values:

(+ 1 (/ Inf 100))

; which gives
  1.026 1.029 1.034 1.031 1.027

The cumulative consequence of these inflation rates can be calculated by multiplying them all with a "Multiply-Scan":

(\\ * (+ 1 (/ Inf 100)))

; which gives:
  1.026 1.056 1.092 1.125 1.156

Now, the investments expressed in "future values" would be :

(* Inv (\\ * (+ 1 (/ Inf 100))))

; which gives
  2052.00 5278.77 6549.90 4501.96 2311.76

Finally, the year after year cumulated investment may be obtained by an "Add-Scan":

(\\ + (* Inv (\\ * (+ 1 (/ Inf 100)))))

; which gives
  2052.00 7330.77 13880.67 18382.63 20694.39

As you can see, we employed two Scans in the same expression.

Conclusion

It is clear that we are far from reaching the sobriety and efficiency of the real APL language. On the other hand, some of the operators we have borrowed from this language bring a real plus to LispE, allowing it to handle lists and matrices in a simple and concise way.

Clone this wiki locally