# A Zillion Ways to Compute the Inner Product of two Vectors in COMMON LISP

## + BIND : org-export-html-postamble-format org-export-html-postamble

The most common way to compute the inner product **s** of two vectors **a** and **b** of
size **n** is this:

s := 0 for i := 1 to n do s := s + a[i] * b[i]

## 1 Recursive

**trivial, eats your stack**

(defun IP (a b) (if (null a) 0 (+ (* (car a) (car b)) (IP (cdr a) (cdr b)))))

This is the genuine lisp way of of computation. But it is not properly tail-recursive. Though it generates a stackoverflow on large vectors.

## 2 Tail Recursive

**less trivial, fast, does not eat your stack**

(defun IP (a b &optional (acc 0)) (if (or a b) (IP (cdr a) (cdr b) (+ acc (* (car a) (car b)))) acc))

## 3 Applicative

**less trivial, concise, quite fast**

(defun IP(a b) (reduce #'+ (mapcar #'* a b)))

Most lispers would do it this way. It is concise and clean. `mapcar`

generates a list of products with the operator `*`

and `reduce`

folds
this list with the operator `+`

.

## 4 Iterative

**trivial**
Although not considered to be koscher Lisp by everyone, this one is
most simple to grasp for people coming from imperative Languages.

(defun IP (a b) (loop for p in a as q in b sum (* p q)))

## 5 Fortran-esk

**trivial, ugly, lightning fast**

(defun IP (a b) (prog ((c 0)) sum-up (setq c (+ c (* (car a) (car b))) ) (setq a (cdr a)) (setq b (cdr b)) (when (and a b) (go sum-up)) (return c)))

Long and verbose with a spoiled "GOTO".

## 6 Metalinguistic

**not trivial**

Here we generate an expression like `(+ (* 1 4) (* 2 5) (* 3 6))`

and
pass it to the `EVAL`

-Function.

(defun IP (a b) (eval (cons '+ (mapcar (lambda (p q) (list '* p q)) a b))))

## 7 Probably Wrong :-P

89

## 8 Function-Level

**very sophisticated, extravagant, not too fast**

This is derived from the Paper "Can Programming be Liberated from the
von Neumann Style?" of John Backus 1978. Please refer to this document
to fully understand this piece of Code. In essence, the function `IP`

is constructed by function composition of some 1-parameter-functions,
that are generated by function calls.

`insert`

and `alpha2`

are taken from backus' papers. The first one is
a function that generates closures, that act like `reduce`

and the
second generates closures that act like `mapcar`

-.

`transpose`

simply computes the transposed matrix of a matrix, given
in list representation, e.g. `((1 2) (a b)) --> ((1 a) (2 b))`

(use-package :alexandria) ; We need CURRY and COMPOSE (defun transpose (x) (apply #'mapcar (cons 'list x))) (defun insert (op) (curry #'apply op)) (defun alpha2 (op) (lambda (l) (mapcar (insert op) l))) (defparameter IP (compose (insert #'+) (alpha2 #'*) #'transpose)) (print (funcall IP '((1 2 3) (4 5 6))))

## 9 Via Composed Closures

**most sophisticated and therefore bullshit**

(defun IP (a b) (funcall (apply #'compose (mapcar (lambda (a b) (lambda (s) (+ s (* a b)))) a b )) 0))

This generates a list of closures, each computing one product and
adding some parameter eaten by them. After that, the 1-parameter
closures, that take the sum **s** computed so far are "composed"
together into a single function that is finally called with the value
**0** for **s**. This function finally performs the hole computation.

## 10 What Else?

This is my collection so far. Are there more ways to implement the inner product? Sure, there are. I'd be glad to hear from you of other possibilies. Pass me a mail or use the comment facility.

**I would like to grow this collection. Even bizarre solutions are welcome. Thanks in advance!**