## 02 Sep 2015

### Planet Lisp

#### Joe Marshall: Linear fractional transforms and permutations

So what does group theory have to do with linear fractional transforms? I'm glad you asked. The answer is pretty complicated, though.

There's no good place to start here, so let's just dive in. This function computes the `cross-ratio`

of four numbers:

(define (cross-ratio A B C D) (/ (* (- a b) (- c d)) (* (- a d) (- c b)))) 1 ]=> (cross-ratio 1 9 5 13) ;Value: 4/3

There's a geometric interpretation of the cross ratio, but for the moment, just think of it as a function that takes any four numbers and produces a value.

1 ]=> (cross-ratio 3 2 1 9) ;Value: -4/3 1 ]=> (cross-ratio 5 1 8 4) ;Value: 16/7

The cross ratio is preserved under linear fractional transforms:

1 ]=> (define lft2 (make-linear-fractional-transform 3 -1 2 7)) ;Value: lft2 1 ]=> (cross-ratio (lft2 3) (lft2 2) (lft2 1) (lft2 9)) ;Value: -4/3 1 ]=> (cross-ratio (lft 3) (lft 2) (lft 1) (lft 9)) ;Value: -4/3 1 ]=> (cross-ratio 3 2 1 9) ;Value: -4/3

The cross ratio is also preserved under *some* permutations of its arguments.

1 ]=> (cross-ratio 3 2 1 9) ;Value: -4/3 1 ]=> (cross-ratio 1 9 3 2) ;Value: -4/3 1 ]=> (cross-ratio 2 3 9 1) ;Value: -4/3

but not all

1 ]=> (cross-ratio 3 2 9 1) ;Value: 4/7 1 ]=> (cross-ratio 2 9 3 1) ;Value: 7/3

Now here's the interesting part. There's a linear fractional transform that will "undo" the permutation of the arguments to cross-ration.

1 ]=> ((make-linear-fractional-transform -1 1 0 1) 7/3) ;Value: -4/3 1 ]=> ((make-linear-fractional-transform 1 0 1 -1) 4/7) ;Value: -4/3

There are 24 permutations of the argument list to `cross-ratio`

, and here are the equivalence classes:

((-4/3 (1 9 3 2) (2 3 9 1) (3 2 1 9) (9 1 2 3)) (-3/4 (1 2 3 9) (2 1 9 3) (3 9 1 2) (9 3 2 1)) (3/7 (1 2 9 3) (2 1 3 9) (3 9 2 1) (9 3 1 2)) (4/7 (1 9 2 3) (2 3 1 9) (3 2 9 1) (9 1 3 2)) (7/4 (1 3 2 9) (2 9 1 3) (3 1 9 2) (9 2 3 1)) (7/3 (1 3 9 2) (2 9 3 1) (3 1 2 9) (9 2 1 3)))

And these are the linear fractional transforms that permute among these:

(#[linear-fractional-transform 89333 x] #[linear-fractional-transform 89334 1/x] #[linear-fractional-transform 89335 (1 - x)] #[linear-fractional-transform 89403 1/(1 - x)] #[linear-fractional-transform 89370 x/(x - 1)] #[linear-fractional-transform 89393 (x - 1)/x])

This is cool. Instead of thinking of a linear fractional transform as a continuous function that traces out a hyperbola, or as an interval on the real number line, we can think of a linear fractional transform as a function that computes a permutation.

Here is a function called `d3`

that is defined on the symbols `a`

, `b`

, `c`

, `d`

, `e`

, and `f`

.

1 ]=> (d3 'a 'b) ;Value: d

With six symbols, there's only 36 possible outcomes, so we can enumerate them:

a b c d e f a ((e d f b a c) b (f e d c b a) c (d f e a c b) d (c a b f d e) e (a b c d e f) f (b c a e f d))

Here's a hack. The identity element can be seen to be `'e`

, so list that row and column first:

e a b c d f e ((e a b c d f) a (a e d f b c) b (b f e d c a) c (c d f e a b) d (d c a b f e) f (f b c a e d))

Now the table headers are exactly the same as the first entries in the respective rows or columns, so you can do without them.

((e a b c d f) (a e d f b c) (b f e d c a) (c d f e a b) (d c a b f e) (f b c a e d))

Another weird thing is that you can permute any rows but the first, or permute any columns but the first, and still have an equivalent table.

Anyway, d3 is the "symmetry group" of a triangle. Here the operations are

e = leave it alone f = rotate clockwise 120 degrees d = rotate counter-clockwise 120 degrees a = hold vertex A in place, and flip the triangle over swapping vertex B and C b = hold vertex B in place, and flip the triangle over swapping vertex A and C c = hold vertex C in place, and flip the triangle over swapping vertex A and B

Now consider this,

e = #[linear-fractional-transform 89333 x] f = #[linear-fractional-transform 89393 (x - 1)/x] d = #[linear-fractional-transform 89403 1/(1 - x)] a = #[linear-fractional-transform 89370 x/(x - 1)] b = #[linear-fractional-transform 89335 (1 - x)] c = #[linear-fractional-transform 89334 1/x]

Just as d3 permutes a triangle, these linear fractional transforms permute among the equivalence classes of cross ratios.

02 Sep 2015 4:20am GMT

## 28 Aug 2015

### Planet Lisp

#### ECL News: ECL 16.0.0 release

Hello! Since we don't have proper rss feed yet (I'll work on it in upcoming weeks and post here, when done), I'm writing here, that new ECL release is available. Enjoy!

https://common-lisp.net/project/ecl

Regards,

Daniel

PS This is the last (except pointer to new rss feed) on this channel, since we've moved from SF to above-mentioned address.

28 Aug 2015 11:06am GMT

## 27 Aug 2015

### Planet Lisp

#### Joe Marshall: n-ary functions and argument lists

Suppose we have a binary operation `Op2 = (lambda (left right) ...)`

. If it is closed over some type, you can make expression trees.

(Op2 (Op2<arg1><arg2>) (Op2 (Op2<arg3><arg4>)<arg5>))

If `Op2`

is associative as well, these are equal:

(Op2 (Op2<arg1><arg2>) (Op2<arg3>(Op2<arg4><arg5>))) (Op2<arg1>(Op2 (Op2<arg2><arg3>) (Op2<arg4><arg5>)))

This makes the tree structure irrelevant so long as the fringe of the tree stays in order, so we can flatten the tree by making an N-ary version of the binary operation:

(define (binary->nary Op2) (lambda (a1 a2 . an) (fold-left Op2 (Op2 a1 a2) an))) ((binary->n-ary Op2)<arg1><arg2><arg3><arg4><arg5><arg6>etc.)

The value of this expression naturally depends upon the values of the arguments. Changing the argument list is highly likely to change the value of the entire expression. However, we can make certain changes to the argument list without changing the value of the entire expression. If we know what those changes are, we can manipulate the argument list before invoking the operator, and still get the same answer. Naturally, most of the changes we can make to the argument list depend on the specifics of `Op2`

, but it turns out that some interesting changes are possible without knowing any specifics, only knowing a few high-level properties of `Op2`

.

Obviously, the first thing we can do is reduce the argument list through evaluation. Simply replace the first two arguments with the value of `(Op2 `

*<arg1>* *<arg2>*)

((binary->n-ary Op2)<arg1><arg2><arg3><arg4><arg5><arg6>etc.) = ((binary->n-ary Op2) (Op2<arg1><arg2>)<arg3><arg4><arg5><arg6>etc.) = ((binary->n-ary Op2)<result><arg3><arg4><arg5><arg6>etc.)

Since `Op2`

is associative, we can replace any 2 adjacent arguments with their combination.

Now suppose there is an identity element among the arguments we can give to Op2.

(Op2<arg>id) =<arg>and(Op2 id<arg>) =<arg>

We can do this:

(define (binary->nary Op2) (lambda an (fold-left Op2 id an))) (define Op (binary->nary Op2))

Which is cleaner than the original. We also get a new way to manipulate the argument list to `Op`

. We can add the identity element anywhere we wish, or we can delete the identity element wherever we find one.

(Op<arg1><arg2><arg3>Id<arg4><arg5><arg6>etc.) = (Op<arg1><arg2><arg3><arg4><arg5><arg6>etc.) = (Op<arg1>Id<arg2><arg3><arg4><arg5>Id<arg6>etc.)

One more restriction. We want `Op2`

to be invertible. Suppose `(Op2 `

. *<arg1>* *<arg2>*) = *<result>*`Op2`

is invertible if, given any two of *<arg1>*, *<arg2>*, and *<result>*, the third can be uniquely determined. If you have one *<arg>* and a *<result>*, you can run things backwards and get the other *<arg>*.

Requiring `Op2`

to be invertible has many consequences, some of them quite non-obvious. An obvious consequence, though, is that we can define inverse elements. If `(Op2 `

, then we say that *<argA>* *<argB>*) = Id*<argB>* is the inverse of *<argA>* (and vice versa). We find the inverse of an argument by fixing the output as the identity element and running `Op2`

backwards to find the other argument.

This gives us the final way to manipulate the argument list. If an element appears next to its inverse, both can be removed:

(Op<arg1><arg2><arg3>(inverse<arg3>)<arg5><arg6>etc.) = (Op<arg1><arg2>(Op2<arg3>(inverse<arg3>))<arg5><arg6>etc.) = (Op<arg1><arg2>Id<arg5><arg6>etc.) = (Op<arg1><arg2><arg5><arg6>etc.)

So here are all the restrictions on Op2:

- Closed over an set of arguments
- Associative
- Has an identity argument
- Invertible

If `Op2`

has these properties (and a lot of binary operations do), then we can define an n-ary `Op`

and play with its argument list. If you do this, you might notice that it looks kind of familiar:

(op f g (inverse g) j id h) = (op f j id h) = (op f j h)

The argument list sort of looks like a function pipeline. The allowed manipulations of the argument list are compatible with a function pipeline, too. In fact, it could *be* a function pipeline if `Op`

is the `compose`

operator, and `f`

, `g`

, and `h`

are appropriate invertible unary functions. But whatever it is, the point is that it looks enough like a function pipeline that we can pretend that it is.

27 Aug 2015 7:18pm GMT

#### CL Test Grid: Regressions and improvements in quicklisp 2015-08-04

The difference between quicklisp 2015-07-10 and quicklisp 2015-08-04 is shown in these reports:

https://common-lisp.net/project/cl-test-grid/ql/quicklisp-2015-08-04-diff.html

grouped by lisp implementation

https://common-lisp.net/project/cl-test-grid/ql/quicklisp-2015-08-04-diff2.html

grouped by library

(Both reports show the same data, just arranged differently)

As we see, most of the new failures are caused by drakma failing to load on CCL 1.8, CLISP and SBCL 1.0.58, because drakma.asd now specifies test-op, but in a way supported only by new ASDF, and not supported by the ASDF shipped with these old lisp implementations. Maybe the drakma-caused failures are not critical for everyone, on the other hand it is trivial to fix.

There are other regressions as well as some improvements. If you care about some of the results, but don't understand the cause of particular failure, or how to read the report, just ask in the comments or on the mailing list, we will be glad to help, investigate and reproduce the problem.

BTW, you can click test result links in the reports to open the corresponding log.

A little bit more about the cl-test-grid project. We regularly collect test results of all the Quicklisp libraries on various lisp implementations, and compute difference between Quicklisp versions to detect changes (regressions or improvements). That way we can monitor the CL ecosystem as a whole.

27 Aug 2015 11:11am GMT

#### Michael Malis: Defaddress

*This post is the first part of a two part series exploring the emulator cl-6502. This post will cover how addressing modes are implemented in cl-6502. The second part will go over the implementation of the opcodes.*

cl-6502 is an emulator for the MOS 6502 processor, used in devices such as the Apple II and the NES. As an emulator, cl-6502 has three distinct roles. It needs to be able to convert assembly code into machine code (assembly), it needs to be able to convert machine code back into assembly (disassembly), and it needs to be able to actually interpret the machine code (execution). By using macros in clever ways, cl-6502 is able to create multiple DSLs for defining different components of the emulator. One of those macros is **defaddress**, which makes it easy to add addressing modes to the emulator. First some background.

Assembly language has what are known as "addressing modes". Depending on which addressing mode is being used, the argument to the instruction will be calculated in a different manner. The programmer is able to specify different addressing modes by using slightly different syntaxes. As an example here is the same jump instruction just with two different addressing modes:

JMP $0 JMP ($0)

From here on out, I'm going to use the term "operand" to refer to the value given to the instruction before the addressing mode has been taken into account and the term "argument" to refer to the value after the addressing mode has been considered. As you should be able to tell, both instructions above are passed the same operand of zero, but because they are using different addressing modes, they will calculate their arguments in two different ways.

Since the first instruction doesn't use any extra syntax (except the dollar sign which just means base 16), it uses "absolute" addressing. With absolute addressing the argument is the same as the operand.^{1} The first instruction can be read as, continue execution at the instruction at address zero.

Since the second instruction has parens around the operand, it uses what is known as "indirect" addressing. For indirect addressing, the operand is actually the memory location of the argument.^{2} The second instruction can be read as, get the address that is stored at address zero, and continue execution at the instruction at that location in memory. Assuming the value 123 was stored at address zero, the operand would be zero, the argument would be 123, and the instruction would cause execution to be resumed at the instruction at location 123.

In total there are 13 different addressing modes for the 6502. In order to make it easy to define all of these different addressing modes, cl-6502 creates a macro **defaddress**. **Defaddress** is a DSL for the sole purpose of defining addressing modes. Each one of the main arguments to **defaddress** handles one of the jobs (assembly/disassembly/execution) that an emulator has to perform with respect to the addressing mode. As to what the **defaddress** DSL looks like, here is the code that defines the absolute addressing mode.

(defaddress absolute (:reader "^_$" :writer "$~{~2,'0x~}") (get-word (cpu-pc cpu)))

The code above has three distinct parts. The first piece is the reader, which is used to parse the assembly code:

"^_$"

The reader argument is a regular expression that recognizes the syntax of the addressing mode being defined, in this case aboslute addressing. The regex is a normal perl compatible regex except it may use an underscore to match (and capture) an operand. The regex above matches a lone operand, which is exactly the syntax for absolute addressing. After the reader is the writer:

"$~{2,'0x~}"

The writer is a format string that is able to reproduce the original assembly (with the proper syntax for the addressing mode) from the machine code. The writer for absolute addressing says to print the operand as a zero padded, two digit, hexadecimal number. Basically, it just prints the lone operand in assembly language without any additional syntax. Since there is no extra syntax, that means the generated code is using absolute addressing.

The last part is the body. The body is a block of code that calculates the argument from the operands.^{3} For absolute addressing the body is:

(get-word (cpu-pc cpu))

When this code is ran, the variable *cpu* will be bound to an object representing the current state of the cpu. The pc of the cpu normally points to the current instruction being executed, but cl-6502 uses a slight trick. By incrementing the pc, it will now point to the first operand of the instruction! All the body does is take the value of the pc (which is the address of the argument/operand), and looks up the value at that address^{4} to get the actual argument.

As a second example of **defaddress**, here is the code for indirect addressing:

(defaddress indirect (:reader "^\\(_\\)$" :writer "($~{~2,'0x~})") (get-word (get-word (cpu-pc cpu)) t))

There are only a few differences between the code for indirect and absolute addressing. In the reader and writer, there are now an extra pair of parens around the operand. This is because the syntax for indirect addressing is an operand surrounded by parens. Another difference is with the body. Since there is an extra layer of indirection with indirect addressing, there is an additional call to **get-word**. For indirect addressing, the body says to calculate the argument, get the value of the pc (the address of the operand or the address of the address of the argument), get the value at that address (the operand or the address of the argument), and then get the value at that address (the actual argument).

Since I have already shown you some examples of how to use **defaddress**, I am now going to explain how **defaddress** works. Here is the complete definition of **defaddress**:

(defmacro defaddress (name (&key reader writer cpu-reg) &body body) `(progn (defmethod reader ((mode (eql ',name))) ,(cl-ppcre:regex-replace-all "_" reader "([^,()#&]+)")) (defmethod writer ((mode (eql ',name))) ,writer) (push ',name *address-modes*) (defun ,name (cpu) ,@body) (defun (setf ,name) (value cpu) ,(if cpu-reg `(setf ,@body value) `(setf (get-byte ,@body) value)))))

I'm going to break down the code for **defaddress** one part at a time. After explaining a piece does, I will show you what the expansion of that piece looks like when defining absolute addressing. The first part of **defaddress** handles the reader:

(defmethod reader ((mode (eql ',name))) ,(cl-ppcre:regex-replace-all "_" reader "([^,()#&]+)"))

This part generates code which will define a method on the generic (virtual) function **reader**. **Reader** takes in the name of the mode as an argument and is supposed to return a regex (a true perl compatible regex, i.e. no underscores) that will recognize the mode and extract the operands:

(reader 'absolute) => "^([^,()#&]+)$"

To produce the method, **defaddress** just takes the reader argument, substitutes the underscore with a regex that can be used to recognize operands, and uses that as the value **reader** should return for the mode being defined. Here is what the piece of code expands into for absolute addressing:

(defmethod reader ((mode (eql 'absolute))) "^([^,()#&]+)$")

The next part does pretty much the exact same thing, only for the writer:

(defmethod writer ((mode (eql ',name))) ,writer)

It generates the code for a method for the generic function **writer**. Since the format string is used unmodified, **defaddress** just inserts the string into the body of the function. There result winds up being:

(defmethod writer ((mode (eql 'absolute))) "$~{~2,'0x~}")

Next up is the piece:

(push ',name *address-modes*)

This piece of code adds the mode being defined to a list of all of the addressing modes. The list is used to find all of the addressing modes that match the syntax of a given instruction. The snippet simply expands into:

(push 'absolute *address-modes*)

Now for the most important part of **defaddress **- the code that handles the body:

(defun ,name (cpu) ,@body)

It just puts the body inside of a function named by the addressing mode. The function is supposed to take the in the current state of the cpu as an object and return the argument used for the current instruction. Note that the variable *cpu* is available to the body. This is how the body of **defaddress** is able to access the cpu object. The expansion winds up looking like:

(defun absolute (cpu) (get-word (cpu-pc cpu)))

There is just one more part, a **setf** function for the addressing mode:

(defun (setf ,name) (value cpu) ,(if cpu-reg `(setf ,@body value) `(setf (get-byte ,@body) value)))

This code generates a **setf** function, basically a way to modify the argument of the instruction. Many instructions not only use the argument, but they store a new value to the memory location of the argument. The **setf** function defined by **defaddress** is just a way to do that. I'm not going to go in depth about it, but this is the only piece of code that uses the *cpu-reg* argument. The *cpu-reg* argument is just used to smooth out some differences between different addressing modes. The code generated by the above code winds up looking like:

(defun (setf absolute) (value cpu) (setf (get-byte (get-word (cpu-pc cpu))) value))

As I just said, the **setf** function defined can be used to set the value of the argument. To do it for absolute addressing, get the operand and set the value at that memory location.^{5}^{6}

And that is pretty much everything there is to know about **defaddress**. In the next post I am going to talk a bout **defasm, **a macro that makes it easy to define different instructions for the emulator. It piggybacks off of the information provided by **defaddress** in order to handle all of the instructions in all of the different possible addressing modes.

The post Defaddress appeared first on Macrology.

27 Aug 2015 5:53am GMT

## 26 Aug 2015

### Planet Lisp

#### Zach Beane: Jean-Philippe Paradis really, really, really wants you to know about his stuff

In the past few years, I haven't had as much time to write about Common Lisp stuff as much as I did before.

For a while, I used a bookmarking tool to collect links to interesting stuff and periodically post them, a la Christian Neukirchen's Trivium. But I fell behind at that, and stopped. These days, I often find neat Lisp stuff and think "I should write about that on my blog!" However, the link often ends up as a tweet, a reddit link, or disappears into the bottom half of my todo list.

I talked about the general slowdown in Planet Lisp blogging at ELS in London. Compared to ten years ago, the usual people just aren't writing as much, for various reasons. It wasn't only doom and gloom, though. ELS was also an energizing experience, with a lot of excitement, positivity, and enthusiasm for Common Lisp. It gave me renewed energy for writing about CL stuff and linking to new CL things.

Then yesterday, out of left field, someone asked me what I thought about the recent @HexstreamSoft twitter rants.

Take a minute to browse through @HexstreamSoft. I'll wait. (NSFW language and images.)

There are two resources he created that seem to have set off the latest rants. First, there is a format reference. Second, there is a Common Lisp symbol reference. The former looks fairly complete, and presents information in an interesting way. The latter looks mostly incomplete.

There is no conspiracy on my part to suppress these links. I'm not sure I saw them before yesterday, though it's possible I saw them and forgot about them. But while I'd like to post more links and share more cool Lisp stuff, it's *not* my personal responsibility to plug everything that comes along. The world's lack of interest in a resource cannot be laid solely at my feet.

Unfortunately, conspiracy theories and rants sap my energy; fortunately, this seems like a fairly uncommon thing. (Madhu is the only other person I know of who sees a nefarious conspiracy in my work.)

If you'd like to see *your* work featured on Planet Lisp, one of the best ways is to start your own blog full of useful Common Lisp articles, add an RSS or Atom feed, and tell me about it. (If you have lots of energy and want to start a blog linking to every cool new CL thing, that would be great too!)

Another way to get featured on Planet Lisp, one I do not especially prefer, is to take to twitter and rant about the Common Lisp mafia. It worked this time, but I'm not inclined to respond to that type of thing again.

26 Aug 2015 12:00am GMT

## 25 Aug 2015

### Planet Lisp

#### Eugene Zaikonnov: CL-JPEG has been updated

A long due update to Common Lisp JPEG Library has now been merged into sharplispers/cl-jpeg.

The summary of changes:

- The various global state tables and counters were moved into special variables of decoder/encoder functions. This should address the concerns of thread safety.
- The monolithic source file was broken up into several according with modern way of structuring the projects.
- Metadata for :author and :description was added to the project's .asd.
- The contributors are now listed. Do let me know if I forgot to add someone.

Revisiting own 16 year old code was an interesting experience. Thanks to everyone who kept the project alive over the years.

25 Aug 2015 3:00pm GMT

#### Common Lisp Tips: When a synonym-stream is useful

Imagine your project has a special variable whose value is a stream to which some output is directed, e.g. `my-project:*log-output*`

. You can change where the output goes by setting the value of the special variable, but by default, output should go to `*standard-output*`

.

The naive way to do this is a direct reference:

```
(defvar *log-output* *standard-output*)
```

However, this can run into trouble if `*standard-output*`

is bound to something unexpected when that form is evaluated. For example, if file loading output is temporarily suppressed by binding `*standard-output*`

to `(make-broadcast-stream)`

, output to `*log-output*`

is then also discarded.

One way to work around it is with make-synonym-stream:

```
(defvar *log-output* (make-synonym-stream '*standard-output*))
```

With that setup, any output sent to `*log-output*`

is sent to the stream that is the *dynamic* value of the symbol `'*standard-output*`

. And since the dynamic value is looked up for each output, the output to `*log-output*`

will go to `*standard-output*`

even if `*standard-output*`

is assigned some other stream value later on.

25 Aug 2015 2:24am GMT

## 23 Aug 2015

### Planet Lisp

#### Joe Marshall: Playing with linear fractional transforms

I wanted to play with continued fractions and linear fractional transforms, so I wrote some code to make it easier. A linear fractional transform (also called a homographic function or Mobius transform) is a function like this:

In MIT/GNU Scheme:

;; x => (3x + 1)/(x + 4) 1 ]=> (define foo (make-linear-fractional-transform 3 1 1 4)) ;Value: foo 1 ]=> (foo 2) ;Value: 7/6

I used an *entity* object so, in addition to invoking it on a number, there are two more ways to manipulate a linear fractional transform:

;; A predicate 1 ]=> (linear-fractional-transform? foo) ;Value: #t ;; And a CPS accessor 1 ]=> (lft/spread-coefficients foo (lambda (A B C D) (list A B C D))) ;Value 307: (3 1 1 4)

I also added a print method:

1 ]=> foo ;Value 308: #[linear-fractional-transform 308 (3x + 1)/(x + 4)]

As I mentioned in a prior post, you can partly apply a linear fractional transform:

1 ]=> foo ;Value 308: #[linear-fractional-transform 308 (3x + 1)/(x + 4)] 1 ]=> (lft/partly-apply foo 2) ;Value 315: #[linear-fractional-transform 315 (7x + 3)/(6x + 1)]

Since I want to reason about applying a linear fractional transform to an argument, I wrote an abstraction for that:

;; Apply LFT foo to continued fraction phi. 1 ]=> (make-lft-application foo phi) ;Value 311: #[lft-application 311 (3x + 1)/(x + 4) {1 ...}]

So now we can write a procedure that takes an application, peels off the first term in the continued fraction, feeds it to the linear fractional transform, and creates a new application:

(define (application/step lft-application) (let ((lft (application-function lft-application)) (cf (application-continued-fraction lft-application))) (make-lft-application (lft/partly-apply lft (head cf)) (tail cf)))) 1 ]=> (define appl (make-lft-application lft/identity sqrt-two)) ;Value: appl 1 ]=> appl ;Value 317: #[lft-application 317 x {1 2 2 2 ...}] 1 ]=> (application/step appl) ;Value 318: #[lft-application 318 (x + 1)/x {2 2 2 ...}] 1 ]=> (application/step (application/step appl)) ;Value 319: #[lft-application 319 (3x + 1)/(2x + 1) {2 2 ...}] 1 ]=> (application/step (application/step (application/step appl))) ;Value 320: #[lft-application 320 (7x + 3)/(5x + 2) {2 ...}]

All these `lft-application`

objects should be (numerically) equal.

In an earlier post I showed how a linear fractional transform can be partly evaluated by determining the `integer-part`

of the transform. The `integer-part`

of an application is the `integer-part`

of the application-function. You can get the fractional part by subtracting the integer-part.

### A digression

If you apply a linear fractional transform to zero, it's obvious the answer is `B/D`

. On the other hand, if you apply a transform to a sufficiently large x, you'll get as close as you want to `A/C`

.

If the denominator of a linear fractional transform is zero for some value of x, there should be a vertical asymptote at that point. That's the *pole* of the transform. The pole is at `(- D)/C`

. The pole will be at zero if `D`

is zero. It will be at a negative number if D and C are the same sign and at a positive number if D and C differ in sign.

If you take a linear fractional transform with a pole at a negative number, and you sweep the input from 0 up on to infinity, the output will vary smoothly and monotonically from `B/D`

approaching `A/C`

and staying between both values at all times.

1 ]=> lft1 ;Value 675: #[linear-fractional-transform 675 (3x + 1)/(4x + 2)] 1 ]=> (lft1 0) ;Value: 1/2 1 ]=> (lft1 1000000) ;Value: 3000001/4000002 1 ]=> (exact->inexact 3000001/4000002) ;Value: .7499998750000625

(On the other hand, if the pole is at a positive number, as you sweep the input from 0 up to infinity, the output starts at `B/D`

, but flees away from `A/C`

until the input gets to the pole. Then the output approaches `A/C`

, but from the opposite direction. In any case, if the pole is positive, then the output will vary from `B/D`

and eventually approach `A/C`

, but *never* being between them.)

We can represent intervals as linear fractional transforms. The endpoints of the interval are `A/C`

and `B/D`

.

To get the width of the interval, just subtract the endpoints: `A/C - B/D = (A*D - B*C)/(C * D)`

Imagine you are performing some calculation with continued fractions. Since there may be an infinite number of terms, the calculation will proceed incrementally, using up terms as needed and generating other terms. So you can think of a more complex calculation as a tree, where a node in the tree is a linear fractional transform and the continued fraction terms flow between the nodes.

When we do an `application/step`

, we move a term from the continued fraction into the linear fractional transform. Now consider a term as an element of information. We've moved this information out of the continued fraction and into the linear fractional transform. The information is apparently "stored" in the linear fractional transform until it is extracted as an output term for the next stage in the computation. But if you think about it, the "format" of the information is different depending upon whether it is flowing between nodes, where it is a series of continued fraction terms, or if it is stored in a linear fractional transform, where it is encoded somehow in the values of the coefficients. The act of partly-evaluating a linear fractional transform is in effect "encoding" some information as a continued fraction term. Partly applying a linear fractional transform is in effect "decoding" the continued fraction term (presumably generated by an earlier computation). Why not change to a more efficient communication channel?

When a node sends information to another node, instead of converting the information to several continued fraction terms to be assembled at the other end, we'll send the information as a single linear fractional transform. It contains the desired information already in the right "format". (See Peter Potts's work.)

### A digression

What happens if we compose two linear fractional transforms?

(compose (lambda (x) (/ (+ (* A x) B) (+ (* C x) D))) (lambda (y) (/ (+ (* p y) q) (+ (* r y) s))))

We get

(lambda (x) (/ (+ (* A (/ (+ (* p x) q) (+ (* r x) s))) B) (+ (* C (/ (+ (* p x) q) (+ (* r x) s))) D)))

Which, after some algebra, turns into this:

(lambda (x) (/ (+ (* (+ (* A p) (* B r)) x) (+ (* A q) (* B s))) (+ (* (+ (* C p) (* D r)) x) (+ (* C q) (* D s)))))

Which is equivalent to this:

(lambda (x) (let ((E (+ (* A p) (* B r))) (F (+ (* A q) (* B s))) (G (+ (* C p) (* D r))) (H (+ (* C q) (* D s)))) (/ (+ (* E x) F) (+ (* G x) H))))

Which you can see is another linear fractional transform.

If we have a linear fractional transform

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

It's inverse (if it has one) is:

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

Which is yet another linear fractional transform. These things are everywhere.

Let's see, if we have a binary operation `binop`

that is

- Closed over some set,
*i.e.*given any two elements of the set, the operation applied to the elements produces another element of the set. In other words,`binop`

takes two arguments, returns one value, and the type of both arguments and return value are the same. - Associative,
*i.e.*`(binop a (binop b c)) = (binop (binop a b) c)`

- Has an identity argument. A "left identity" is an argument such that
`(binop left-identity x) = x`

. A "right identity" is an argument such that`(binop x right-identity) = x`

. An "identity" argument works as a left or right identity. - Is invertible,
*i.e.*for any objects a and b, there is a unique object x such that`(binop a x) = b`

and a unique object y such that`(binop y b) = a`

then we have a *group*.

The `compose`

function is a binary operation. When you compose a linear fractional transform with another, you get a third linear fractional transform.

1 ]=> (define lft1 (make-linear-fractional-transform 3 1 4 2)) ;Value: lft1 1 ]=> (define lft2 (make-linear-fractional-transform 5 1 1 0)) ;Value: lft2 1 ]=> (lft/compose lft1 lft2) ;Value 662: #[linear-fractional-transform 662 (16x + 3)/(22x + 4)]

Linear fractional transforms are associative.

1 ]=> (define lft3 (make-linear-fractional-transform 7 2 1 3)) ;Value: lft3 1 ]=> (lft/compose lft1 (lft/compose lft2 lft3)) ;Value 663: #[linear-fractional-transform 663 (115x + 41)/(158x + 56)] 1 ]=> (lft/compose (lft/compose lft1 lft2) lft3) ;Value 664: #[linear-fractional-transform 664 (115x + 41)/(158x + 56)]

The linear fractional transform `(make-linear-fractional-transform 1 0 0 1)`

is both a left and right identity when composed with another linear fractional transform.

1 ]=> (define lft/identity (make-linear-fractional-transform 1 0 0 1)) ;Value: lft/identity 1 ]=> (lft/compose lft/identity lft1) ;Value 665: #[linear-fractional-transform 665 (3x + 1)/(4x + 2)] 1 ]=> (lft/compose lft1 lft/identity) ;Value 666: #[linear-fractional-transform 666 (3x + 1)/(4x + 2)]

Given lft1 and lft2, there is a unique linear fractional transform x such that `(compose lft1 x) = lft2`

, and a unique linear fractional transform y such that `(compose y lft1) = lft2`

. x should be `(compose (inverse lft1) lft2)`

, and y should be `(compose lft2 (inverse lft1))`

1 ]=> lft1 ;Value 675: #[linear-fractional-transform 675 (3x + 1)/(4x + 2)] 1 ]=> lft2 ;Value 687: #[linear-fractional-transform 687 (5x + 1)/x] 1 ]=> (define x (lft/compose (lft/inverse lft1) lft2))) ;Value: x 1 ]=> (lft/compose lft1 x) ;Value 690: #[linear-fractional-transform 690 (5x + 1)/x] 1 ]=> (define y (lft/compose lft2 (lft/inverse lft1))) ;Value: y 1 ]=> (lft/compose y lft1) ;Value 691: #[linear-fractional-transform 691 (5x + 1)/x]

It sure looks like linear fractional transforms form a group under function composition.

I guess it's time to learn a little group theory.

23 Aug 2015 8:23pm GMT

#### Quicklisp news: July 2015 download stats

Here are the top 100 downloads for July, 2015:

13137 alexandria

8723 trivial-features

8303 babel

7185 cffi

7095 bordeaux-threads

6398 trivial-gray-streams

6269 flexi-streams

5246 trivial-garbage

5126 usocket

5072 closer-mop

4989 cl-fad

4772 cl-ppcre

4725 split-sequence

4659 anaphora

4599 cl+ssl

4317 cl-base64

4159 chunga

4097 puri

4022 drakma

3916 iterate

3842 nibbles

3773 chipz

3256 named-readtables

3183 ironclad

2816 md5

2816 local-time

2783 let-plus

2741 slime

2702 uiop

2595 trivial-backtrace

2507 cl-colors

2375 hunchentoot

2313 cl-ansi-text

2263 prove

1924 cl-unicode

1900 rfc2388

1900 metabang-bind

1863 trivial-types

1860 cl-utilities

1821 cl-annot

1806 optima

1777 fiveam

1717 cl-interpol

1700 cl-syntax

1629 static-vectors

1583 trivial-utf-8

1580 quri

1466 parse-number

1450 fast-io

1418 salza2

1322 clack

1313 quicklisp-slime-helper

1296 cl-json

1226 proc-parse

1137 xsubseq

1092 jonathan

1068 fast-http

1036 ieee-floats

1025 osicat

1019 closure-common

1018 lack

959 cxml

957 asdf-system-connections

937 zpb-ttf

935 http-body

914 uuid

897 postmodern

893 hu.dwim.asdf

876 trivial-indent

860 zpng

835 plump

833 cl-dbi

827 esrap

818 fare-utils

813 jsown

812 array-utils

806 cl-who

776 cl-yacc

754 metatilities-base

746 symbol-munger

720 swap-bytes

719 yason

718 cl-containers

711 trivial-mimes

695 fare-quasiquote

687 lisp-unit

686 clss

662 lquery

648 cl-vectors

636 iolib

626 myway

626 map-set

625 parenscript

608 lparallel

607 arnesi

605 log4cl

592 hu.dwim.stefil

588 cl-marshal

585 vom

578 external-program

23 Aug 2015 6:52pm GMT