# Common Lisp Series package

Tags:

# Common Lisp Series package

## Introduction

Richard C. Water’s SERIES package for Common Lisp introduces the **Series** data type representing lazy sequences and a set of operations on them. The interesting thing about this package is that it allows to substitute many typical loop constructions with more functional approach but without losing on performance.

## Restrictions

The idea is to use CL macrosystem to process the composition of expressions into the call graph and then effectively generate plain loops. Of course this could only be done for a subset of expressions which satisfy the set of limitations on *optimizable expressions*:

- Expressions must be statically analyzable
- Expressions must be straight-line computations
- Procedures called by expressions must be preorder
- Intermediate values in computations must be sequences
- Every non-directed data-flow in expression must be on-line

The good thing about these restrictions is that the **SERIES** package during the code walking phase explicitely checks them and issue a warning if some expression could not be optimized. In this case a developer have an opportunity to manually optimize it or restructure to create optimizable expression.

## How to install and use

Just use

```
(ql:quickload "series")
```

to install.

In order to use one could either call the functions directly from the series package or use the function setup all necessary redefinitions for **defun**, **let** etc to try to automatically analyze the code and to setup helper reader macros:

```
(eval-when (:compile-toplevel :execute :load-toplevel)
(series::install))
```

## Performance

In order to test it I decided to compare with a pure functional implementation of some extremely simple function. All comparisons were made with LispWorks 7.0 32bit for Mac OSX. In all cases I compare performance of pure-functional implementation of the algorithm vs implementation with **SERIES**, and providing comparison with the simple *loop* implementation.

### Sum of the list

First trivial task is to calculate the sum of the squares of numbers in a list. Pure functional implementation:

```
(defun sum-squares-cl (lst)
(declare (optimize (safety 0) (speed 3)))
(reduce #'+ (mapcar (lambda (x) (expt x 2)) lst)))
```

The pure functional implementation is a reduce over mapped list with applied square function. Pure *loop*-based implementation looks like this:

```
(defun sum-squares-loop2 (lst)
(declare (optimize (safety 0) (speed 3)))
(loop for x in lst
summing (expt x 2)))
```

Here we use **summing** facility of the *loop* macro, avoiding introducing accumulator variable.

The implementation using **SERIES** package:

```
(defun sum-squares-series2 (lst)
(declare (optimize (safety 0) (speed 3)))
(collect-sum (mapping ((x (scan lst))) (expt x 2))))
```

Here the conversion of the list `lst`

into the series happens with function `scan`

.
Series `mapping`

macro defines a list of `let`

like bindings as a first argument and a body of the function as a second.
`collect-sum`

allows to collect resuls. More generic implementation below:

```
(defun sum-squares-series1 (lst)
(declare (optimize (safety 0) (speed 3)))
(collect-fn 'integer (lambda () 0) #'+
(mapping ((x (scan lst)))
(expt x 2))))
```

More generic version uses the `collect-fn`

function - the building block for accumulation functions using *series* expressions.

Lets generate a test data using using alexandria’s `iota`

function which generates a list of integers up to its argument (thanks to Steve Losh for suggestion)

```
(defparameter *data* (loop :for i :below 4000 :collect (iota i)))
```

Simple comparison (gives the following results:

```
SERIES-TEST 4 > (time (loop for d in *data* do (sum-squares-cl d)))
Timing the evaluation of (LOOP FOR D IN *DATA* DO (SUM-SQUARES-CL D))
User time = 1.870
System time = 0.002
Elapsed time = 1.858
Allocation = 155486812 bytes
0 Page faults
Calls to %EVAL 76022
NIL
SERIES-TEST 5 > (time (loop for d in *data* do (sum-squares-loop2 d)))
Timing the evaluation of (LOOP FOR D IN *DATA* DO (SUM-SQUARES-LOOP2 D))
User time = 0.928
System time = 0.001
Elapsed time = 0.908
Allocation = 59525512 bytes
1 Page faults
Calls to %EVAL 76022
NIL
SERIES-TEST 6 > (time (loop for d in *data* do (sum-squares-series1 d)))
Timing the evaluation of (LOOP FOR D IN *DATA* DO (SUM-SQUARES-SERIES1 D))
User time = 0.861
System time = 0.001
Elapsed time = 0.843
Allocation = 59521180 bytes
0 Page faults
Calls to %EVAL 76022
NIL
SERIES-TEST 7 > (time (loop for d in *data* do (sum-squares-series2 d)))
Timing the evaluation of (LOOP FOR D IN *DATA* DO (SUM-SQUARES-SERIES2 D))
User time = 0.943
System time = 0.002
Elapsed time = 0.927
Allocation = 59518424 bytes
0 Page faults
Calls to %EVAL 76022
NIL
```

From this results one can see that the pure functional implementation is slowest, while using both versions of the *series* function gives the same performance as the version with `loop`

macro.

Let’s try to macroexpand the *series* implementation of this function:

```
SERIES-TEST 8 > (pprint (macroexpand '(collect-sum (mapping ((x (scan lst))) (expt x 2)))))
(COMMON-LISP:LET* ((#7=#:OUT-86150 LST))
(COMMON-LISP:LET (#8=#:ELEMENTS-86142
#1=#:LISTPTR-86144
#6=#:TEMP-86145
(#2=#:LIMIT-86146 0)
(#3=#:INDEX-86147 -1)
#4=#:LSTP-86148
#9=#:ITEMS-86152
(#5=#:SUM-86139 0))
(DECLARE (TYPE LIST #1#)
(TYPE SERIES::VECTOR-INDEX+ #2#)
(TYPE SERIES::-VECTOR-INDEX #3#)
(TYPE BOOLEAN #4#)
(TYPE NUMBER #5#))
(LOCALLY
(DECLARE (TYPE ARRAY #6#))
(IF (SETQ #4# (LISTP #7#))
(SETQ #1# #7# #6# #())
(LOCALLY
(DECLARE (TYPE ARRAY #7#))
(SETQ #6# #7#)
(SETQ #2# (SERIES::ARRAY-FILL-POINTER-OR-TOTAL-SIZE #7#))))
(TAGBODY
#10=#:LL-86153 (IF #4#
(PROGN
(IF (ENDP #1#) (GO SERIES::END))
(SETQ #8# (CAR #1#))
(SETQ #1# (CDR #1#)))
(PROGN
(INCF #3#)
(LOCALLY
(DECLARE (TYPE ARRAY #7#) (TYPE SERIES::VECTOR-INDEX #3#))
(IF (>= #3# #2#) (GO SERIES::END))
(SETQ #8# (THE SERIES::*TYPE* (ROW-MAJOR-AREF #7# #3#))))))
(SETQ #9# ((LAMBDA (X) (EXPT X 2)) #8#))
(SETQ #5# (+ #5# #9#))
(GO #10#)
SERIES::END)
#5#)))
```

Up to the `TAGBOBY`

intstruction follows declarations. As one can see, the actual algorithm implementation starts with `TAGBODY`

, with the iteration label `#10`

and end of loop `SERIES::END`

.

### Sum of the list with conditions.

Now lets evolve this example. The task is to calculate the sum of first 5 numbers, which squares are above 50. For pure functional implementation we need to add the `take-first-n`

function, which will take first N element of the list (basically a wrapper around `subseq`

:

```
(defun take-first-n (lst n)
(declare (optimize (safety 0) (speed 3)))
(let ((l (length lst)))
(subseq lst 0 (min n l))))
```

Now the implementation is trivial:

```
(defun sum-squares-of-5-above-50-cl (lst)
(declare (optimize (safety 0) (speed 3)))
(reduce #'+
(take-first-n
(remove-if (lambda (x) (< x 50))
(mapcar (lambda (x) (expt x 2)) lst))
5)))
```

Obivious problem of this implementation is that we create a 3 intermediate lists: first with `mapcar`

, next with `remove-if`

and last with the `take-first-n`

.

The implementation with **SERIES** will look similar but will not need the wrapper function:

```
(defun sum-squares-of-5-above-50-series (lst)
(declare (optimize (safety 0) (speed 3)))
(collect-sum
(subseries
(choose-if (lambda (x) (>= x 50))
(mapping ((x (scan lst)))
(expt x 2)))
0 5)))
```

The *loop*-based implementation not as easily readable:

```
(defun sum-squares-of-5-above-50-naive (lst)
(declare (optimize (safety 0) (speed 3)))
(let ((sum 0))
(loop for x in lst
for counter = 0
for y = (expt x 2)
thereis (< counter 5)
if (> y 50)
do
(incf counter)
(incf sum y))
sum))
```

Here we need intermediate variable - counter - to be able to break the loop. Let’s measure the performance:

```
SERIES-TEST 9 > (time (loop for d in *data* do (sum-squares-of-5-above-50-cl d)))
Timing the evaluation of (LOOP FOR D IN *DATA* DO (SUM-SQUARES-OF-5-ABOVE-50-CL D))
User time = 1.233
System time = 0.187
Elapsed time = 1.856
Allocation = 194243052 bytes
3006 Page faults
Calls to %EVAL 76022
NIL
SERIES-TEST 10 > (time (loop for d in *data* do (sum-squares-of-5-above-50-series d)))
Timing the evaluation of (LOOP FOR D IN *DATA* DO (SUM-SQUARES-OF-5-ABOVE-50-SERIES D))
User time = 0.107
System time = 0.003
Elapsed time = 0.088
Allocation = 2419888 bytes
37 Page faults
Calls to %EVAL 76022
NIL
SERIES-TEST 11 > (time (loop for d in *data* do (sum-squares-of-5-above-50-naive d)))
Timing the evaluation of (LOOP FOR D IN *DATA* DO (SUM-SQUARES-OF-5-ABOVE-50-NAIVE D))
User time = 0.036
System time = 0.000
Elapsed time = 0.019
Allocation = 2399620 bytes
0 Page faults
Calls to %EVAL 76022
NIL
```

As it can be seen the the performance difference more than 10 times between functional and series/loop based implementation.

## Conclusion

It is preferrable to use **SERIES** package instead of pure functional approach then possible since it will keep the code as readable/maintainable without giving up on performance. Obiviously not all algorithms could be implemented with **SERIES**; the authors of **SERIES** package claim however that analyzed 80% of loops could be implemented with **SERIES**.

## Update

Updated test results after Steve Losh’s suggestion.