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.
ex, 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)))
xy, 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.
