State Machines

One of the things you do when writing a game is to write little state machines for objects that have non-trivial behaviors. A game loop runs frequently (dozens to hundreds of times a second) and iterates over all the state machines and advances each of them by one state. The state machines will appear to run in parallel with each other. However, there is no guarantee of what order the state machines are advanced, so care must be taken if a machine reads or modifies another machine’s state.

CLOS provides a particularly elegant way to code up a state machine. The generic function step! takes a state machine and its current state as arguments. We represent the state as a keyword. An eql specialized method for each state is written.

(defclass my-state-machine ()
  ((state :initarg :initial-state :accessor state)))

(defgeneric step! (state-machine state))

(defmethod step! ((machine my-state-machine) (state (eql :idle)))  
  (when (key-pressed?)
    (setf (state machine) :keydown)))

(defmethod step! ((machine my-state-machine) (state (eql :keydown)))
  (unless (key-pressed?)
    (setf (state machine) :idle)))

The state variables of the state machine would be held in other slots in the CLOS instance.

One advantage we find here is that we can write an :after method on (setf state) that is eql specialized on the new state. For instance, in a game the :after method could start a new animation for an object.

(defmethod (setf state) :after ((new-state (eql :idle)) (machine my-state-machine))
  (begin-idle-animation! my-state-machine))

Now the code that does the state transition no longer has to worry about managing the animations as well. They’ll be taken care of when we assign the new state.

Because we’re using CLOS dispatch, the state can be a class instance instead of a keyword. This allows us to create parameterized states. For example, we could have a delay-until state that contained a timestamp. The step! method would compare the current time to the timestamp and go to the next state only if the time has expired.

(defclass delay-until ()
  ((timestamp :initarg :timestamp :reader timestamp)))

(defmethod step! ((machine my-state-machine) (state delay-until))
  (when (> (get-universal-time) (timestamp state))
    (setf (state machine) :active)))

Variations

Each step! method will typically have some sort of conditional followed by an assignment of the state slot. Rather that having our state methods work by side effect, we could make them purely functional by having them return the next state of the machine. The game loop would perform the assignment:

(defun game-loop (game)
  (loop
    (dolist (machine (all-state-machines game))
      (setf (state machine) (step machine (state machine))))))

(defmethod step ((machine my-state-machine) (state (eql :idle)))  
  (if (key-pressed?)
      :keydown
      :idle))

I suppose you could have state machines that inherit from other state machines and override some of the state transition methods from the superclass, but I would avoid writing such CLOS spaghetti. For any object you’ll usually want exactly one state transition method per state. With one state transition method per state, we could dispense with the keyword and use the state transition function itself to represent the state.

(defun game-loop (game)
  (loop
    (dolist (machine (all-state-machines game))
      (setf (state machine) (funcall (state machine) machine)))))

(defun my-machine/state-idle (machine)
  (if (key-pressed?)
      (progn
         (incf (kestroke-count machine))
         #'my-machine/state-keydown)
      #'my-machine/state-idle))

(defun my-machine/state-keydown (machine)
  (if (key-pressed?)
      #'my-machine/state-keydown
      #'my-machine/state-idle))

The disadvantage of this doing it this way is that states are no longer keywords. They don’t print nicely or compare easily. An advantage of doing it this way is that we no longer have to do a CLOS generic function dispatch on each state transition. We directly call the state transition function.

The game-loop function can be seen as a multiplexed trampoline. It sits in a loop and calls what was returned from last time around the loop. The state transition function, by returning the next state transition function, is instructing the trampoline to make the call. Essentially, each state transition function is tail calling the next state via this trampoline.

State machines without side effects

The state transition function can be a pure function, but we can remove the side effect in game-loop as well.

We keep parallel lists of machines and their states (represented as state transition functions).

(defun game-loop (machines states)
  (game-loop machines (map 'list #'funcall states machines)))

Now we have state machines and a driver loop that are pure functional.

Plaformer Game Tutorial

I was suprised by the interest in the code I wrote for learning the platformer game. It wasn’t the best Lisp code. I just uploaded what I had.

But enough people were interested that I decided to give it a once over. At https://github.com/jrm-code-project/PlatformerTutorial I have a rewrite where each chapter of the tutorial has been broken off into a separate git branch. The code is much cleaner and several kludges and idioticies were removed (and I hope none added).

You May Not Need That :around Method

I’ve seen this “anti-pattern” a few times in CLOS code. A superclass ’super will have a subclass ’sub and there will be a primary method specialized to the superclass.

(defmethod foo ((instance super) arg)
  (format t "~&Foo called on ~s." arg))

Then I’ll see an :around method defined on the subclass:

(defmethod foo :around ((instance sub) arg)
  (format t "~&Start foo...~%")
  (call-next-method)
  (format t "~&End foo.~%"))

The intent here is clearly that code in the method specialized on the subclass is invoked “around” the call to the method specialized on the superclass.

But the :around qualifier is not necessary and probably doesn’t do what is intended. If we remove the :around qualifier, then the most specific primary method will be the foo method specialized on ’sub. And the (call-next-method) invokation will chain up to the foo method specialized on ’super. It will work as was likely intended.

:around methods are useful when the superclass wants to run a method “around” the subclass. :around methods are combined from least specific to most specific — the opposite order of primary methods — so that the superclass can wrap the call to the subclass. An good example of where an :around method would be handy is when you need to sieze a lock around the call to the method. The superclass would sieze the lock in an :around method that would run before any of the subclass primary methods ran.

Ordinary chaining of methods doesn’t need the :around qualifier. Just chain the methods.

With- vs. call-with-

In Common Lisp, there are a lot of macros that begin with the word “with-”. These typically wrap a body of code, and establish a context around the execution of the code.

In Scheme, they instead have a lot of functions that begin with the words “call-with-”. They typically take a thunk or receiver as an argument, and establish a context around a call to the thunk or receiver.

Both of these forms accomplish the same sort of thing: running some user supplied code within a context. The Scheme way accomplishes this without a macro, but “call-with-” functions are rarely used as arguments to higher order functions. Writing one as a function is slightly easier than writing one as a macro because the compiler takes care of avoiding variable capture. Writing one as a macro leaves it up to the implementor to use appropriate gensyms. Writing one as a macro avoids a closure and a function call, but so does inlining the function. The macro form is slightly more concise because it doesn’t have a lambda at every call site. The function form will likely be easier to debug because it will probably involve a frame on the stack.

There’s no need to commit to either. Just write a “with-” macro that expands into a call to an inline “call-with-” function. This should equally please and irritate everyone.

Porting a Game from Java (update)

I didn’t expect anyone would be interested, so I just pushed the code that I had with little thought about anyone trying to use it. It turns out that some people actually wanted to run it, so I polished off some of the rough edges and made it easier to get working. Feel free to email me if you have questions or suggestions.

Porting a Game from Java

I decided to learn about games, so I followed along with a tutorial by Kaarin Gaming. His tutorial was written in Java, but of course I used Common Lisp. I made no attempt to faithfully replicate his design, but I followed it closely in some places, less so in others. The resulting program was more or less a port of the Java program to Common Lisp, so it not very remarkable in and of itself. Certainly I don’t expect many people to be interested in reading beyond this point.

It’s known that Java is wordy language and it shows in the end result. The tutorial had 3712 lines of Java code in 39 files and the equivalent Common Lisp was 2255 lines in 21 files. A typical Common Lisp file would contain more code than a typical Java file. It was often the case that a Common Lisp file would contain multiple classes.

Both versions used separate render and game mechanics threads. The render thread ran at about 60 frames per second where the game mechanics ran at 200 steps per second. The threads were mostly independent, but the game mechanics would occasionally have to query the render thread to find out whether an animation had completed or what frame the animation was on in order to synchronize attacks with reactions.

There were a couple of notable differences in the two implementations. The Java implementation would advance animation frames imperatively by incrementing the animation frame counter every few rendering cycles. The Common Lisp implementation would instead compute the animation frame functionally by subtracting the current time from the animation start time and dividing by the ticks per animation frame. In Common Lisp, different animation effects could be achieved by changing how the animation frame was computed. If you computed the frame number modulo the number of frames in the animation, you’d get an animation loop. If you clamped the frame number, you get a one-shot animation.

CLOS made some things easier. An :after method on the (setf get-state) of an entity would set the animation. The get-y method on some objects would (call-next-method) to get the actual y position and then add a time varying offset to make the object “float” in mid air. The get-x method on projectiles would would (call-next-method) to get the starting x position and then add a factor of the current ticks. This causes projectiles to travel uniformly horizontally across the screen. I often used the ability of CLOS to specialize on some argument other than the first one just to make the methods more readable.

The Common Lisp code is at http://github.com/jrm-code-project/Platformer, while the Java code is at https://github.com/KaarinGaming/PlatformerTutorial. Being a simple port of the Java code, the Common Lisp code is not exemplary, and since I didn’t know what I was doing, it is kludgy in places. The Common Lisp code would be improved by a rewrite, but I’m not going to. I was unable to find a sound library for Common Lisp that could play .wav files without a noticable delay, so adding sound effects to the game is sort of a non-starter. I think I’ve gotten what I can out of this exercise, so I’ll likely abandon it now.

Bilinear Fractional Transformations

A bilinear fractional transformation (BiLFT) is a two-argument function of the form

(lambda (x y)
  (/ (+ (* A x y) (* B x) (* C y) D)
     (+ (* E x y) (* F x) (* G y) H)))

William Gosper figured out how to use BiLFTs to perform linear fractional operations on infinite compositions of LFTs. It isn’t as hard as it might seem.

BiLFTs do not form a group under functional composition with LFTs, but they have this interesting property: if you hold either input to the BiLFT constant, the BiLFT becomes a LFT on the other input. So if we consider just one of the inputs at a time (or the output), we can apply some group-like operations.

You can compose LFTs with BiLFTs in three ways. First, you can run the output of a BiLFT into the input of a LFT. Second and third, you can run the output of a LFT into the either the x or y input of a BiLFT. Composing a LFT with a BiLFT in any of these ways produces another BiLFT, so there is some notion of closure under composition. Composing the identity LFT with a BiLFT in any of these ways does not change anything. For any composition of a LFT with a BiLFT, you can compose the inverse of the LFT to undo the composition.

BiLFTs can also form infinite compositions, but since there are two inputs, each input can be infinite. We cannot use a Scheme stream, but we can create a two-tailed stream-like object called a binary-expression. A binary-expression is a composition of two infinite compositions. We represent a binary-expression as an object with two delayed cdrs.

(defclass binary-expression ()
  ((generation :initarg :generation
               :initform 0)
   (bilft :initarg :bilft
          :initform (error "Required initarg :bilft was omitted."))
   (delayed-left :initarg :delayed-left
                 :initform (error "Required initarg :delayed-left was omitted."))
   (delayed-right :initarg :delayed-right
                  :initform (error "Required initarg :delayed-right was omitted."))))

Like a LFT, we use binary-expressions by trying to operate on the BiLFT, but forcing one of the tails and refining the binary-expression when necessary.

(defun refine-left (binary-expression)
  (let ((delayed-left (slot-value binary-expression 'delayed-left)))
    (if (null delayed-left)
        (error "Attempt to refine-left on empty stream.")
        (let ((left (force delayed-left)))
          (make-instance 'binary-expression
                         :generation (+ (slot-value binary-expression 'generation) 1)
                         :bilft (compose-bilft-lft-x
                                 (slot-value binary-expression 'bilft)
                                 (if (empty-stream? left)
                                     (make-lft 1 1
                                               0 0)
                                     (stream-car left)))
                         :delayed-left (if (empty-stream? left)
                                           nil
                                           (stream-delayed-cdr left))
                         :delayed-right (slot-value binary-expression 'delayed-right))))))

(defun refine-right (binary-expression)
  (let ((delayed-right (slot-value binary-expression 'delayed-right)))
    (if (null delayed-right)
        (error "Attempt to refine-right on empty stream.")
        (let ((right (force delayed-right)))
          (make-instance 'binary-expression
                         :generation (+ (slot-value binary-expression 'generation) 1)
                         :bilft (compose-bilft-lft-y
                                 (slot-value binary-expression 'bilft)
                                 (if (empty-stream? right)
                                     (make-lft 1 1
                                               0 0)
                                     (stream-car right)))
                         :delayed-left (slot-value binary-expression 'delayed-left)
                         :delayed-right (if (empty-stream? right)
                                            nil
                                            (stream-delayed-cdr right)))))))

refine-fairly alternates forcing the delayed-left or delayed-right tail while refine-disjoint looks at the overlap in the ranges of the BiLFT.

(defun refine-fairly (binary-expression)
  (if (zerop (mod (slot-value binary-expression 'generation) 2))
      (if (null (slot-value binary-expression 'delayed-left))
          (refine-right binary-expression)
          (refine-left binary-expression))
      (if (null (slot-value binary-expression 'delayed-right))
          (refine-left binary-expression)
          (refine-right binary-expression))))

(defun refine-disjoint (binary-expression)
  (if (bilft-disjoint? (slot-value binary-expression 'bilft))
      (refine-right binary-expression)
      (refine-left binary-expression)))

You can do arithmetic on infinite compositions by using the appropriate BiLFT:

(defparameter bilft-add 
  (make-bilft 0 1 1 0
              0 0 0 1))

(defparameter bilft-subtract 
  (make-bilft 0 1 -1 0
              0 0 0 1))

(defparameter bilft-multiply 
  (make-bilft 1 0 0 0
              0 0 0 1))

(defparameter bilft-divide 
  (make-bilft 0 1 0 0
              0 0 1 0))

Converting a binary-expression to a LFT stream

binary-expressions can be operated on in an analagous way to an infinite composition of LFTs, but in order to nest binary expressions, we need to be able to turn one into an infinite composition of LFTs so it can become the left or right input of the other. The way to do this is to generate a stream of LFTs and their inverses. The inverses are composed into the output of the binary-expression while the LFTs are composed downstream into one of the inputs of the next binary-expression.

The math works such that we can select any LFT that has an inverse, but we want our binary-expression to represent a narrowing transformation, so we try composing a few different LFTs and their inverses and see if we still have a narrowing transformation. If we find one, we proceed with the computation, but if we cannot find a LFT and its inverse that preserves the narrowing, we refine the binary-expression by forcing one of the two delayed inputs and composing it.

(defun decompose (left composed)
  (values left (funcall (inverse-lft left) composed)))

(defun decompose-range? (left composed if-success if-failure)
  (multiple-value-bind (left right) (decompose left composed)
    (if (range? right)  ;; does it still narrow?
        (funcall if-success left right)
        (funcall if-failure))))

(defun try-decompose-digit (lft if-success if-failure)
  (decompose-range?
   (make-lft 2 1 0 1) lft
   if-success
   (lambda ()
     (decompose-range?
      (make-lft 1 0 1 2) lft
      if-success
      (lambda ()
        (decompose-range?
         (make-lft 3 1 1 3) lft
         if-success
         if-failure))))))
    
(defun binary-expression-decompose-digit (binary-expression)
  (try-decompose-digit
   (slot-value binary-expression 'bilft)
   (lambda (digit bilft)
     (values digit (make-instance 'binary-expression
                                  :generation (slot-value binary-expression 'generation)
                                  :bilft bilft
                                  :delayed-left (slot-value binary-expression 'delayed-left)
                                  :delayed-right (slot-value binary-expression 'delayed-right))))
   (lambda ()
     (binary-expression-decompose-digit (refine-disjoint binary-expression)))))

(defun binary-expression->lft-stream (binary-expression)
  (multiple-value-bind (digit remainder) (binary-expression-decompose-digit binary-expression)
    (cons-lft-stream digit 
                     (binary-expression->lft-stream remainder))))

Now we have the machinery we need to do arithmetic on pairs of LFT streams.

Infinite Expression Trees

You can only go so far with a finite number of arithmetic operations, but you can go much further with an infinite number. For example, you can create converging infinite series. We can recursively generate an infinite tree of binary expressions. We unfold the tree and call a generating function at each recursive level.

(defun unfold-expression-tree-1 (left generate counter)
  (funcall (funcall generate counter)
           left
           (delay-lft-stream (unfold-expression-tree-1 left generate (+ counter 1)))))

Often the root of the tree is special, so the usual way we call this is

(defun unfold-expression-tree (root-bilft left generate)
  (funcall root-bilft
           left
           (delay-lft-stream (unfold-expression-tree-1 left generate 1))))

Square Root of Infinite Composition

To compute the square root of an infinite composition, we create an infinite tree. Each level of the tree refines the estimate of the square root of the estimate from the next level down in the tree.

(defun sqrt-lft-stream (lft-stream)
  (unfold-expression-tree-1
    lft-stream
    (constantly (make-bilft 1 2 1 0
                            0 1 2 1))
    0))

but we need not construct an infinite tree if each level is identical. We just re-use the level:

(defun sqrt-lft-stream (lft-stream)
  (let ((stream nil))
    (setq stream
          (funcall (make-bilft 1 2 1 0
                               0 1 2 1)
                   lft-stream
                   (delay-lft-stream stream)))
    stream))

This feeds back the square root into its own computation. (These ideas are from Peter Potts and Reinhold Heckmann.)

e^x and log(x)

Peter Potts gives these formulas for e^x and log(x) where x is an infinite composition of LFTs:

(defun %exp-lft-stream (lft-stream)
  (unfold-expression-tree-1
   (lambda (n)
       (make-bilft (+ (* 2 n) 2) (+ (* 2 n) 1) (* 2 n) (+ (* 2 n) 1)
                   (+ (* 2 n) 1) (* 2 n) (+ (* 2 n) 1) (+ (* 2 n) 2)))
   0
   (funcall (inverse-lft (make-lft 1 -1 1 1)) lft-stream)))

(defun %log-lft-stream (lft-stream)
  (unfold-expression-tree
   (make-bilft 1 1 -1 -1
               0 1  1  0)
   (lambda (n)
     (make-bilft n (+ (* n 2) 1)       (+ n 1) 0
                 0       (+ n 1) (+ (* n 2) 1) n))
   lft-stream))

These infinite expression trees converge only on a limited range, so we need to use identities on the arguments and results to extend the range to cover a wide set of inputs.

Infinite Composition

If you like functional composition, you’ll like linear fractional transformations (LFTs). They behave very nicely when you compose them (in fact, they are a group under functional composition). If you compose two LFTs, you get another LFT. You can keep composing as long as you wish. Let’s compose an infinite number of LFTs.

I suppose I should argue that composing an infinite number of LFTs will give you anything at all. Consider those LFTs with non-negative coefficients. When given an input in the range [0,∞], they will output a number in the range [A/C, B/D]. The output range is narrower than, and contained within, the input range. If we compose two such LFTs, the range of output of the outermost LFT will be even narrower. As we compose more and more of these narrowing LFTs, the range of output of the outermost LFT will become narrower and narrower. If we compose an infinite number of narrowing LFTs, the output range will narrow to a single point. Curiously, the limits on the range of output of a finite composition of LFTs are always rational numbers, yet the output from infinite composition of LFTs can be an irrational real number.

There are many ways to represent an infinite number of LFTs. A generator or a co-routine, for example, but I like the stream abstraction from Scheme. This is easily implemented in Common Lisp. A delay macro creates promises:

(defclass promise ()
  ((forced? :initform nil)
   (values-or-thunk :initarg :thunk
                    :initform (error "Required initarg :thunk omitted.")))
  (:documentation "A simple call-by-need thunk."))

(defmacro delay (expression)
  “Delays evaluation of an expression and returns a promise.”
  ‘(make-instance ’promise :thunk (lambda () ,expression)))

and the force function forces evaluation:

(defun force (promise)
  “Returns the values of a promise, forcing it if necessary.”
  (check-type promise promise)
  ;; Ensure the values have been memoized.
  (unless (slot-value promise ’forced?)
    (let ((values (multiple-value-list (funcall (slot-value promise ’values-or-thunk)))))
      ;; If this is not a recursive call, memoize the result.
      ;; If this is a recursive call, the result is discarded.
      (unless (slot-value promise ’forced?)
        (setf (slot-value promise ’values-or-thunk) values)
        (setf (slot-value promise ’forced?) t))))
   ;; Return the memoized values.
   (values-list (slot-value promise ’values-or-thunk)))

A stream is a cons of an element and a promise to produce the rest of the stream:

(defclass lft-stream ()
  ((car :initarg :car
        :initform (error "Required initarg :car omitted.")
        :reader stream-car)
   (delayed-cdr :initarg :delayed-cdr
                :initform (error "Required initarg :delayed-cdr omitted.")
                :reader stream-delayed-cdr)))

(defmacro cons-lft-stream (car cdr)
  ‘(make-instance ’stream :car ,car :delayed-cdr (delay ,cdr)))

(defun stream-cdr (stream)
  (force (stream-delayed-cdr stream)))

A stream of LFTs will represent an infinite composition. The first LFT is the outermost LFT in the composition. To incrementally compose the LFTs, we force the delayed cdr of the stream to get the second LFT. We compose the first LFT and the second LFT to get a new stream car, and the cdr of the delayed cdr is the new stream cdr. That is, we start with the stream {F …}, we force the tail, getting {F G …}, then we compose the first and second elements, getting {(F∘G) …}.

(defun refine-lft-stream (lft-stream)
  (let ((tail (stream-cdr lft-stream))) ;; forces cdr
    (make-instance ’stream
                   :car (compose (stream-car lft-stream) (stream-car tail))
                   :delayed-cdr (stream-delayed-cdr tail))))

so we can now write code that operates on what we have composed so far (in the car of the LFT stream), or, if we need to incrementally compose more LFTs, we repeatedly call refine-lft-stream until we have composed enough.

For example, we can compute the nearest float to an infinite composition as follows:

(defun nearest-single (lft-stream)
  (let ((f0 (funcall (stream-car lft-stream) 0))
        (finf (funcall (stream-car lft-stream) ’infinity)))
    (if (and (numberp f0)
             (numberp finf)
             (= (coerce f0 ’single-float)
                (coerce finf ’single-float)))
        (coerce f0 ’single-float)
        (nearest-single (refine-lft-stream lft-stream)))))

The problem with infinite compositions is that they may never narrow enough to proceed with a computation. For example, suppose an infinite composition converged to a number exactly in between two adjacent floating point numbers. The upper limit of the narrowing range will always round to the float that is above, while the lower limit will always round to the float that is below. The floats will never be equal no matter how many terms of the infinite composition are composed, so functions like nearest-single will never return a value. This is a tradeoff. We either continue computing, perhaps forever, with more and more precise values, or we stop at some point, perhaps giving an incorrect answer.

Operating on Infinite Compositions

You can compose a LFT with an infinite composition of LFTs. If we compose the LFT F with the infinite composition {G H …}, we can represent this one of two ways. Either we just tack the F on to the front, getting {F G H …}, or we continue further and eagerly compose the first two elements {(F∘G) H …}. If F is, for example, a LFT that adds 10 or multiplies by 7, the effect is to add 10 to or multiply by 7 the infinite composition. In this way, we can do arithmetic involving rational numbers and infinite compositions.

Sources of Infinite Compositions

It isn’t likely that you have a lot of ad hoc LFT streams you want to compose. Instead, we want some sources of infinite compositions. There are a few useful functions of finite arguments that return infinite compositions. I got these from Peter Potts's thesis. While most of these have limited ranges of arguments, you can use identity operations to divide down the input to an acceptable range and multiply up the output to the correct answer.

√(p/q)

Reinhold Heckmann came up with this one:

(defun %sqrt-rat (p q)
  (let ((diff (- p q)))
    (labels ((rollover (num den)
               (let ((d (+ (* 2 (- den num)) diff)))
                 (if (> d 0)
                     (cons-lft-stream (make-lft 1 0 1 2) (rollover (* num 4) d))
                     (cons-lft-stream (make-lft 2 1 0 1) (rollover (- d) (* den 4)))))))
       (rollover p q))))

The LFTs that this returns are curious in that when you compose them with a range, they divide the range in two and select one or other (high or low) segment. The outermost LFT in the infinite composition will represent a range that contains the square root, and the subsequent LFTs will narrow it down by repeatedly bifurcating it and selecting the top or bottom segment.

e^x, where x is rational and 1/2 < x ≤ 2

(defun %exp-rat (x)
  (check-type x (rational (1/2) 2))
  (cons-lft-stream
    (make-lft (+ 2 x) x
              (- 2 x) x)
    (lft-stream-map (lambda (n)
                      (make-lft (+ (* 4 n) 2) x
                                x             0))
                    (naturals))))

log(x), where x is rational and x > 1

(defun %log-rat (x)
  (check-type x (rational (1) *))
  (lft-stream-map
    (lambda (n)
      (funcall (make-lft 0             (- x 1)
                         (- x 1) (+ (* n 2) 1))
               (make-lft 0       (+ n 1)
                         (+ n 1)       2)))
    (integers)))

x^y, where x and y are rational and x > 1 and 0 < y < 1

(defun %rat-pow (x y)
  (check-type x (rational (1) *))
  (check-type y (rational (0) (1)))
  (cons-lft-stream
    (make-lft y 1
              0 1)
    (lft-stream-map
     (lambda (n)
       (funcall (make-lft 0             (- x 1)
                          (- x 1) (- (* n 2) 1))
                (make-lft 0       (- n y)
                          (+ n y)       2)))
     (naturals))))

tan(x), where x is rational and 0 < x ≤ 1

(defun %rat-tan (x)
  (check-type x (rational (0) 1))
  (lft-stream-map
   (lambda (n)
     (funcall (make-lft 0 x
                        x (+ (* n 4) 1))
              (make-lft 0 x
                        x (- (* n -4) 3))))
   (integers)))

tan^-1(x), where x is rational and 0 < x ≤ 1

(defun big-k-stream (numerators denominators)
  (cons-lft-stream (make-lft 0 (stream-car numerators)
                             1 (stream-car denominators))
                   (big-k-stream (stream-cdr numerators) (stream-cdr denominators))))

(defun %rat-atan (z)
  (check-type z (rational (0) 1))
  (let ((z-squared (square z)))
    (cons-lft-stream (make-lft 0 z
                               1 1)
                     (big-k-stream (stream-map (lambda (square)
                                                 (* z-squared square))
                                               (squares))
                                   (stream-cdr (odds))))))

These functions have limited applicability. In my next couple of posts, I’ll show some functions that transform LFT streams into other LFT streams, which can be used to increase the range of inputs and outputs of these primitive sources.

Exponentiating Functions

If we compose a function F(x) with itself, we get F(F(x)) or F∘F. If we compose it again, we get F(F(F(x))) or F∘F∘F. Rather than writing ‘F’ over and over again, we can abuse exponential notation and write (F∘F∘F) as F³, where the superscript indicates how many times we compose the function. F¹ is, naturally, just F. F⁰ would be zero applications of F, which would be the function that leaves its argument unchanged, i.e. the identity function.

The analogy with exponentiation goes deeper. We can quickly exponentiate a number with a divide and conquer algorithm:

(defun my-expt (base exponent)
  (cond ((zerop exponent) 1)
        ((evenp exponent) (my-expt (* base base) (/ exponent 2)))
        (t (* base (my-expt base (- exponent 1))))))

The analagous algorithm will exponentiate a function:

(defun fexpt (f exponent)
  (cond ((zerop exponent) #'identity)
        ((evenp exponent) (fexpt (compose f f) (/ exponent 2)))
        (t (compose f (fexpt f (- exponent 1))))))

The function (lambda (x) (+ 1 (/ 1 x))) takes the reciprocal of its input and adds one to it. What happens if you compose it with itself? We can rewrite it as a linear fractional transformation (LFT) (make-lft 1 1 1 0) and try it out:

> (make-lft 1 1 1 0)
#<LFT 1 + 1/x>

> (compose * (make-lft 1 1 1 0))
#<LFT (2x + 1)/(x + 1)>

> (compose * (make-lft 1 1 1 0))
#<LFT (3x + 2)/(2x + 1)>

> (compose * (make-lft 1 1 1 0))
#<LFT (5x + 3)/(3x + 2)>

> (compose * (make-lft 1 1 1 0))
#<LFT (8x + 5)/(5x + 3)>

> (compose * (make-lft 1 1 1 0))
#<LFT (13x + 8)/(8x + 5)>

> (compose * (make-lft 1 1 1 0))
#<LFT (21x + 13)/(13x + 8)>

Notice how the coefficients are Fibonacci numbers.

We can compute Fibonacci numbers efficiently by exponentiating the LFT 1 + 1/x.

> (fexpt (make-lft 1 1 1 0) 10)
#<LFT (89x + 55)/(55x + 34)>

> (fexpt (make-lft 1 1 1 0) 32)
#<LFT (3524578x + 2178309)/(2178309x + 1346269)>

Since we’re using a divide and conquer algorithm, raising to the 32^nd power involves only five matrix multiplies.

Fixed points

If an input x maps to itself under function f, we say that x is a fixed point of f. So suppose we have a function f with a fixed point x. We consider the function f’ which ignores its argument and outputs x. If we compose f with f’, it won’t make difference that we run the result through f again, so f’ = f∘f’ = f∞. You can find a fixed point of a function by composing the function with its fixed point. Unfortunately, that only works in a lazy language, so you have two options: either choose a finite number of compositions up front, or compose on demand.

You can approximate the fixed point of a function by exponentiating the function to a large number.

(defun approx-fixed-point (f) 
  (funcall (fexpt f 100) 1))

> (float (approx-fixed-point (make-lft 1 1 1 0)))
1.618034

> (float (funcall (make-lft 1 1 1 0) *))
1.618034

Alternatively, we could incrementally compose f with itself as needed. To tell if we are done, we need to determine if we have reached a function that ignores its input and outputs the fixed point. If the function is a LFT, we need only check that the limits of the LFT are equal (up to the desired precision).

(defun fixed-point (lft)
  (let ((f0   (funcall lft 0))
        (finf (funcall lft ’infinity)))  
    (if (and (numberp f0)
             (numberp finf)
             (= (coerce f0 ’single-float) 
                (coerce finf ’single-float)))
        (coerce f0 ’single-float)
        (fixed-point (compose lft lft)))))

> (fixed-point (make-lft 1 1 1 0))
1.618034    

Roll Your Own Linear Fractional Transformations

Looking for a fun weekend project? Allow me to suggest linear fractional transformations.

A linear fractional transformation (LFT), also known as a Möbius transformation or a homographic function, is a function of the form

(lambda (x)
  (/ (+ (* A x) B)
     (+ (* C x) D)))

You could just close over the coefficients,

(defun make-lft (A B C D)
  (lambda (x)
    (/ (+ (* A x) B)
       (+ (* C x) D))))

but you’ll want access to A, B, C, and D. If you implement LFTs as funcallable CLOS instances, you can read out the coefficients from slot values.

Constructor

The coefficients A, B, C, and D could in theory be any complex number, but we can restrict them to being integers and retain a lot of the functionality. If we multiply all the coefficients by the same factor, it doesn't change the output of the LFT. If you have a rational coefficient instead of an integer, you can multiply all the coefficients by the denominator of the rational. If there is a common divisor among the coefficients, you can divide it out to reduce to lowest form. (In practice, the common divisor will likely be 2 if anything, so if the coefficients are all even, divide them all by 2.) We can also canonicalize the sign of the coefficients by multiplying all the coefficients by -1 if necessary.

(defun canonicalize-lft-coefficients (a b
                                      c d receiver)
  (cond ((or (minusp c)
             (and (zerop c)
                  (minusp d)))
         ;; canonicalize sign
         (canonicalize-lft-coefficients (- a) (- b)
                                        (- c) (- d) receiver))
        ((and (evenp a)
              (evenp b)
              (evenp c)
              (evenp d))
         ;; reduce if possible
         (canonicalize-lft-coefficients (/ a 2) (/ b 2)
                                        (/ c 2) (/ d 2) receiver))
        (t (funcall receiver
                    a b
                    c d))))
  
(defun %make-lft (a b c d)
  ;; Constructor used when we know A, B, C, and D are integers.
  (canonicalize-lft-coefficients
   a b
   c d
   (lambda (a* b*
            c* d*)
     (make-instance 'lft
                    :a a* :b b*
                    :c c* :d d*))))

(defun make-lft (a b c d)
  (etypecase a
    (float (make-lft (rational a) b c d))
    (integer
     (etypecase b
       (float (make-lft a (rational b) c d))
       (integer
        (etypecase c
          (float (make-lft a b (rational c) d))
          (integer
           (etypecase d
             (float (make-lft a b c (rational d)))
             (integer (%make-lft a b
                                 c d))
             (rational (make-lft (* a (denominator d)) (* b (denominator d))
                                 (* c (denominator d)) (numerator d)))))
          (rational (make-lft (* a (denominator c)) (* b (denominator c))
                              (numerator c)         (* d (denominator c))))))
       (rational (make-lft (* a (denominator b)) (numerator b)
                           (* c (denominator b)) (* d (denominator b))))))
    (rational (make-lft (numerator a)         (* b (denominator a))
                        (* c (denominator a)) (* d (denominator a))))))

Printer

One advantage of making LFTs be funcallable CLOS objects is that you can define a print-object method on them. For my LFTs, I defined print-object to print the LFT in algabraic form. This will take a couple of hours to write because of all the edge cases, but it enhances the use of LFTs.

> (make-lft 3 2 4 -3)
#<LFT (3x + 2)/(4x - 3)>

Cases where some of the coefficients are 1 or 0.

> (make-lft 1 0 3 -2)
#<LFT x/(3x - 2)>

> (make-lft 2 7 0 1)
#<LFT 2x + 7>

> (make-lft 3 1 1 0)
#<LFT 3 + 1/x>

Application

The most mundane way to use a LFT is to apply it to a number.

> (defvar *my-lft* (make-lft 3 2 4 3))
*MY-LFT*
    
> (funcall *my-lft* 1/5)
13/19

Dividing by zero

In general, LFTs approach the limit A/C as the input x grows without bound. We can make our funcallable CLOS instance behave this way when called on the special symbol ’infinity.

> (funcall *my-lft* ’infinity)
3/4

In general, LFTs have a pole when the value of x is -D/C, which makes the denominator of the LFT zero. Rather than throwing an error, we’ll make the LFT return ’infinity

> (funcall *my-lft* -3/4))
INFINITY

Inverse LFTs

Another advantage of using a funcallable CLOS instance is that we can find the inverse of a LFT. You can compute the inverse of a LFT by swapping A and D and toggling the signs of B and C.

(defun inverse-lft (lft)
  (make-lft (slot-value lft ’d)
            (- (slot-value lft ’b))
            (- (slot-value lft ’c))
            (slot-value lft ’a)))

Composing LFTs

LFTs are closed under functional composition — if you pipe the output of one LFT into the input of another, the composite function is equivalent to another LFT. The coefficients of the composite LFT are the matrix multiply of the coefficients of the separate terms.

> (compose (make-lft 2 3 5 7) (make-lft 11 13 17 19))
#<LFT (73x + 83)/(174x + 198)>

Using LFTs as linear functions

A LFT can obviously be used as the simple linear function it is. For instance, the “multiply by 3” function is (make-lft 3 0 0 1) and the “subtract 7” function is (make-lft 1 -7 0 1). (make-lft 0 1 1 0) takes the reciprocal of its argument, and (make-lft 1 0 0 1) is just the identity function.

Using LFTs as ranges

LFTs are monotonic except for the pole. If the pole of the LFT is non-positive, and the input is non-negative, then the output of the LFT is somewhere in the range [A/C, B/D]. We can use those LFTs with a non-positive pole to represent ranges of rational numbers. The limits of the range are the LFT evaluated at zero and ’infinity.

We can apply simple linear functions to ranges by composing the LFT that represents the linear function with the LFT that represents the range. The output will be a LFT that represents the modified range. For example, the LFT (make-lft 3 2 4 3) represents the range [2/3, 3/4]. We add 7 to this range by composing the LFT (make-lft 1 7 0 1).

> (compose (make-lft 1 7 0 1) (make-lft 3 2 4 3))
#<LFT (31x + 23)/(4x + 3)>

Application (redux)

It makes sense to define what it means to funcall a LFT on another LFT as being the composition of the LFTs.

> (defvar *add-seven* (make-lft 1 7 0 1))
*ADD-SEVEN*

> (funcall *add-seven* 4)
11

> (funcall *add-seven* (make-lft 4 13 1 2))
#<LFT (11x + 27)/(x + 2)>

> (funcall * ’infinity)
11

Conclusion

This should be enough information for you to implement LFTs in a couple of hours. If you don’t want to implement them yourself, just crib my code from https://github.com/jrm-code-project/homographic/blob/main/lisp/lft.lisp