\( \newcommand\D{\mathrm{d}} \newcommand\E{\mathrm{e}} \newcommand\I{\mathrm{i}} \newcommand\bigOh{\mathcal{O}} \newcommand{\cat}[1]{\mathbf{#1}} \newcommand\curl{\vec{\nabla}\times} \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ZZ}{\mathbb{Z}} \)
UP | HOME

Generic Arithmetic

Table of Contents

1. Introduction

We have a notion of generic arithmetic where we can add symbols ("variables") to numbers. For example \((3+x)^{2}\) is completely sensible in modern mathematics. We would like to similarly perform generic arithmetic in Lisp.

Examples to bear in mind: operating on polynomials (taking their quotient results in a rational function), operating on matrices, and operating on numbers.

This seems to require "shadowing" the original functions from the cl namespace. At first I hoped there was a way around this, but it now seems inevitable.

2. Generic Arithmetic

2.1. Acting on two operands alone

We begin with making generic operations which act on two operands. Extending to an arbitrary number of operands is straightforward afterwards. We define generic functions on two operands, with default for numbers.

2.1.1. Addition

(defgeneric add (x y))

(defmethod add ((x number) (y number))
  (cl:+ x y))

2.1.2. Subtraction

(defgeneric sub (x y)
  (:documentation "Computes X - Y."))

(defmethod sub ((x number) (y number))
  (cl:- x y))

2.1.3. Multiplication

(defgeneric times (x y))

(defmethod times ((x number) (y number))
  (cl:* x y))

2.1.4. Division

(defgeneric div (x y))

(defmethod div ((x number) (y number))
  (cl:/ x y))

2.2. Generic Unary Operations

There are two special cases we need to consider when dealing with generic arithmetic, namely: negation and inversion. These are for the case when subtraction and division are given a single argument (respectively).

2.2.1. Negation

(defgeneric negate (x))

(defmethod negate ((x number))
  (cl:- x))

2.2.2. Invert

Of particular concern, in the future, will be having an invert for matrix classes. 

(defgeneric invert (x))

(defmethod invert ((x number))
  (cl:/ x))

2.3. Generic n-ary Operations

We adhere to the signatures of arithmetic operators specified in Common Lisp: The Language, chapter 12, section 2.

2.3.1. Addition

Our first attempt at adding quantities should adhere to the function signature for + in Common Lisp the Language (section 12.2). We may naively expect: 

(defun + (&rest quantities)
  (reduce add quantities))

But this will throw errors on (+) or (+ 3). We revise our definition to be: 

(defun + (&rest quantities)
  (cond
    ((null quantities) 0)
    ((singleton? quantities) (car quantities))
    (t (reduce add quantities))))

2.3.2. Subtraction

(defun - (minuend & subtrahends)
  (if (null subtrahends)
      (negate minuend)
      (reduce sub subtrahends :initial-value minuend)))

2.3.3. Multiplication

(defun * (&rest quantities)
  (cond
    ((null quantities) 1)
    ((singleton? quantities) (car quantities))
    (t (reduce times quantities))))

2.3.4. Division

(defun / (numerator &rest denominators)
  (if (null denominators)
      (invert numerator)
      (reduce div denominators :initial-value numerator)))

2.4. Derived Operations

We have operations derived from these basic ones. For example, exponentiation. 

(defgeneric expt (x m))

(defmethod expt ((x number) (m number))
  (cl:expt x m))

Following Knuth, in his "Two Notes on Notation" (arXiv:math/9205211), we will have (expt 0 0) evaluate to 1.

3. SCMUTILS

It seems SCMUTILS has a make-generic-operator <arity> <name> <default-operation> method to declare a generic operator.

Then assign-operation will take a generic-operator, the appropriate handler, and some number of argument predicates. As SCMUTILS uses Predicate Dispatching the predicates control method selection.

4. References

Last Updated 2022-05-03 Tue 09:51.