02 Sep 2015

feedPlanet 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

feedPlanet 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

feedPlanet 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 <argA> <argB>) = Id, then we say that <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:

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 address4 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.56

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

feedPlanet 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

feedPlanet 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:

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

feedPlanet 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

  1. 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.
  2. Associative, i.e. (binop a (binop b c)) = (binop (binop a b) c)
  3. 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.
  4. 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