-
Notifications
You must be signed in to change notification settings - Fork 8
6.8 Inspiration from APL
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.
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.
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.
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))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.
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 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)))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)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- 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)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)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))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
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))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.027The 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.156Now, the investments expressed in "future values" would be :
(* Inv (\\ * (+ 1 (/ Inf 100))))
; which gives
2052.00 5278.77 6549.90 4501.96 2311.76Finally, 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.39As you can see, we employed two Scans in the same expression.
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.