Planet Lisp

Didier VernaELS 2016 Call for Papers

· 44 hours ago
		 ELS'16 - 9th European Lisp Symposium
	       AGH University of Science and Technology
			    Kraków, Poland

			    May 9-10, 2016

		Sponsored by EPITA and AGH University

The purpose of the European Lisp Symposium is to provide a forum for
the discussion and dissemination of all aspects of design,
implementation and application of any of the Lisp and Lisp-inspired
dialects, including Common Lisp, Scheme, Emacs Lisp, AutoLisp, ISLISP,
Dylan, Clojure, ACL2, ECMAScript, Racket, SKILL, Hop and so on. We
encourage everyone interested in Lisp to participate.

The 9th European Lisp Symposium invites high quality papers about
novel research results, insights and lessons learned from practical
applications and educational perspectives. We also encourage
submissions about known ideas as long as they are presented in a new
setting and/or in a highly elegant way.

Topics include but are not limited to:

- Context-, aspect-, domain-oriented and generative programming
- Macro-, reflective-, meta- and/or rule-based development approaches
- Language design and implementation
- Language integration, inter-operation and deployment
- Development methodologies, support and environments
- Educational approaches and perspectives
- Experience reports and case studies

We invite submissions in the following forms:

  Papers: Technical papers of up to 8 pages that describe original
    results or explain known ideas in new and elegant ways.

  Demonstrations: Abstracts of up to 2 pages for demonstrations of
    tools, libraries, and applications.

  Tutorials: Abstracts of up to 4 pages for in-depth presentations
    about topics of special interest for at least 90 minutes and up to
    180 minutes.

  The symposium will also provide slots for lightning talks, to be
  registered on-site every day.

All submissions should be formatted following the ACM SIGS guidelines
and include ACM classification categories and terms. For more
information on the submission guidelines and the ACM keywords, see: and

Important dates:

 -   19 Feb 2016 Submission deadline
 -   25 Mar 2016 Notification of acceptance
 -   15 Apr 2016 Early registration deadline
 -   22 Apr 2016 Final papers due
 - 9-10 May 2016 Symposium

Programme chair:
  Irène Durand, LaBRI, University of Bordeaux, France

Local chair:
  Michał Psota, Emergent Network Defense, Kraków, Poland

Programme committee:
  Antonio Leitao — INESC-ID / Instituto Superior Técnico, Universidade
    de Lisboa, Portugal
  Charlotte Heerzel — IMEC, Leuven, Belgium
  Christian Queinnec — University Pierre et Marie Curie, Paris 6, France
  Christophe Rhodes — Goldsmiths, University of London, United Kingdom
  Didier Verna  — EPITA Research and Development Laboratory, France
  Erick Gallesio — University of Nice-Sophia Antipolis, France
  Francois-René Rideau, Google, USA
  Giuseppe Attardi — University of Pisa, Italy
  Henry Lieberman — MIT, USA
  Kent Pitman, HyperMeta Inc., USA
  Leonie Dreschler-Fischer — University of Hamburg, Germany
  Pascal Costanza — Intel Corporation, Belgium
  Robert Strandh — University of Bordeaux, France

Search Keywords:

#els2016, ELS 2016, ELS '16, European Lisp Symposium 2016,
European Lisp Symposium '16, 9th ELS, 9th European Lisp Symposium,
European Lisp Conference 2016, European Lisp Conference '16

Zach BeaneMeta: the Lisp Meetings calendar

· 3 days ago

The Lisp Meetings calendar has been busted as a sidebar on Planet Lisp for a while.

The code to make the sidebar was originally set up with Google’s data-loaded XML feed of calendar events. Sometime in the past year, Google stopped publishing that feed, instead offering a simplified, pre-rendered feed of events.

To fix it, I have to update my software to either scrape the simplified feed or use some lower-level data API. Until then, the sidebar will continue to say “No upcoming meetings” even when that’s not true.

To stay fully up-to-date on all the interesting meetings, check the Lisp Meetings calendar directly, until the sidebar is fixed.

And if you’re in the Boston area, we’re getting together for a dinner on the 15th. See the boston-lisp archives for details.

Didier VernaELS 2016 coming in hot!

· 3 days ago

We're happy to announce that the next European Lisp Symposium will be held at the AGH University of Science and Technology in Kraków, Poland, on May 9-10. Stay tuned for updates, upcoming CfP, invited speakers and lots of good stuff!

Zach BeaneFrom Baggers: Tamei categorizes CL forms by purity

· 8 days ago

Michael MalisZap

· 9 days ago

This post makes use of places. If you are unfamiliar with how places work, see my post Getting Places.

Many languages provide syntactic sugar for evaluating an expression involving a variable and assigning the result of that expression to the variable at the same time. In these languages you can do something such as the following:

x += 5

The above expression both adds five to the value of x and writes that new value back to x. In this post, I’m going to show you how you can write a macro zap that is a generalized version of this technique. With zap the above example would look like the following:

(zap #'+ x 5)

There are a couple things that make zap really cool. First of all, it can be used with any function. For example, if you wanted to cube the value in x, you could use the following:

(zap #'expt x 3)

The other thing that makes zap so awesome is that it can be used on any place. If you want to use zap on the value stored in a hash table with key 5, you can do that:

(zap #'+ (gethash 5 table) 5)

Now that you’ve seen how zap is used, here is how it can be implemented:

(defmacro zap (fn place &rest args)
        (temps exprs stores store-expr access-expr) 
      (get-setf-expansion place)
    `(let* (,@(mapcar #'list temps exprs)
            (,(car stores) 
              (funcall ,fn ,access-expr ,@args)))

You should be able to see that the code for zap is eerily similar to that of incf (from Getting Places). They are the exact same except instead of binding the gensym that will hold the new value to one plus the value already in the place:

(,(car stores) (+ 1 ,access-expr))

The gensym is bound to the result of calling the function with the value in the place and all of the other arguments passed to zap:

(,(car stores) (funcall ,fn ,access-expr ,@args))

Although zap is just a nice syntactic shortcut, it is a great example of the crazy things you can do with places.

The post Zap appeared first on Macrology.

Quicklisp newsSeptember 2015 Quicklisp dist update now available

· 13 days ago
New projects:
  • 3d-vectors — A small utility library implementing basic 3d vector functionality. — Artistic
  • cl-annot-prove — Annotation Syntax Test Library. — MIT
  • cl-arxiv-api — Bindings for API of — MIT
  • cl-diceware — Diceware in Lisp — MIT
  • cl-disque — A Disque client for Common Lisp — MIT
  • cl-hamt — Dictionary & set data structure using hash array-mapped tries — BSD
  • cl-scram — Common lisp library to implement SCRAM-SHA1 SASL mechanism. — Revised BSD License (see LICENSE)
  • clim-pkg-doc — clim-package-documentation — BSD Simplified
  • codex — A documentation system for Common Lisp. — MIT
  • colliflower — Generic interfaces for collections and iterators. — MIT
  • elb-log — ELB log manager for Common Lisp — MIT
  • file-types — Simple scheme to classify file types in a hierarchical fashion. — GNU AGPL
  • geneva — Core of the Geneva document preparation system. Provides data structures and syntax sugar. — GNU AGPL
  • inquisitor — Encoding/end-of-line detecter and of external-format wrapper for Common Lisp — MIT
  • lake — Lake is a GNU make like build utility in Common Lisp. — MIT
  • macro-html — HTML generation library. Aims to be fast, modular, cachable and concise. It does so by defining each tag as a macro which expands to code printing the respective HTML source. Also employs a DSL for element attributes. — GNU AGPL
  • macrodynamics — A language extension for creating bindings scoped to the entire expansion process of a region of code. — LLGPL
  • mini-cas
  • pandocl — A universal document converter. — MIT
  • parenml — S-expression markup language. — MIT
  • snooze — A framework for building REST services using CLOS. — LLGPL
  • texp — DSL for outputting TeX expressions using S-expressions. — GNU Affero General Public License
  • translate — Abstraction layer for translations — LLGPLv2
  • trivial-documentation — Extract documentation and definitions for symbols and packages. — GNU AGPL
  • trivial-open-browser — Open the browser to a URL, on any system. — MIT
  • ubiquitous — A library providing a universal application configuration mechanism. — Artistic
  • ufo — Roswell Script Manager — MIT
  • zenekindarl — A fast precompiling template engine —
Updated projects: access, array-utils, asdf-linguist, binfix, birch, bit-smasher, bknr-datastore, buffalo, carrier, caveman, ceramic, cffi, cl-6502, cl-ana, cl-async, cl-base64, cl-bson, cl-ca, cl-containers, cl-coveralls, cl-curlex, cl-emb, cl-ev, cl-fuse, cl-gearman, cl-geocode, cl-gists, cl-glfw3, cl-grace, cl-hash-util, cl-html5-parser, cl-influxdb, cl-intbytes, cl-irc, cl-jpeg, cl-ledger, cl-liballegro, cl-marklogic, cl-messagepack, cl-mlep, cl-modlisp, cl-mustache, cl-opengl, cl-opsresearch, cl-pdf, cl-photo, cl-ppcre, cl-project, cl-pslib, cl-rabbit, cl-read-macro-tokens, cl-rethinkdb, cl-rss, cl-shellwords, cl-string-match, clack, clavier, cletris, clfswm, climc, climon, clipper, clml, closer-mop, clsql, clss, coleslaw, com.informatimago, common-doc, common-doc-plump, common-html, commonqt, crane, croatoan, dartsclhashtree, defpackage-plus, delta-debug, dexador, djula, docparser, eazy-gnuplot, eazy-project, esrap-liquid, fast-http, fast-io, fiasco, fred, frpc, gbbopen, gendl, getopt, hu.dwim.web-server, hunchensocket, inferior-shell, integral-rest, irc-logger, jonathan, jsown, kenzo, kmrcl, lack, let-over-lambda, lml, lml2, lparallel, lquery, lucerne, mk-string-metrics, named-readtables, opticl, osc, parse-js, pgloader, pipes, plump, portableaserve, postmodern, pounds, prove, ptester, puri, purl, qlot, qt-libs, qtools, quri, racer, reversi, rlc, rutils, scalpl, scriptl, serapeum, spinneret, stumpwm, sxql, tagger, trivial-benchmark, trivial-features, uffi, umlisp, umlisp-orf, websocket-driver, woo, wookie, xlunit, xptest.

Removed projects: hinge, py-configvalidator, read-csv.

Hinge was removed because I can't check it out from git any more. py-configvalidator and read-csv no longer build with SBCL, and the authors have not responded to github issues.

To get this update, use: (ql:update-dist "quicklisp")

LispjobsClojure developer, EMBL-EBI Hinxton, nr Cambridge, UK

· 15 days ago

The European Bioinformatics Institute is looking for a Clojure developer:

We are seeking an experienced software developer to develop a new system for the capture of complex experimental data from model organism genetics research. You will join the Non-vertebrate Genomics team at the European Bioinformatics Institute (EMBL-EBI), located on the Wellcome Genome Campus near Cambridge in the UK, working on the WormBase project.

Here is the complete job description:

Although the job description doesn’t mention Clojure, I have been assured that Clojure will be the main development language.

Michael MalisGetting Places

· 15 days ago

This post will serve as an introduction to writing macros that work with places. I will refer back to it whenever I examine a macro which deals with places.

Places are an incredible part of Common Lisp. In short, a “place” is any location that can hold a value. The obvious example of a place is a variable. Less obvious examples include the elements of an array, or the slots of an object. What makes the concept of places special is that Common Lisp provides a standard interface for reading and writing to them. You can write macros on top of this interface that work for every kind of place. As an example, look at the macro incf. It takes a place as an argument, adds one to its value, and stores the new value back into the place. If you want to increment a variable x, you would use:

(incf x)

And if you wanted to increment the element at index x of a sequence, you would use:

(incf (elt seq x))

They use the exact same syntax even though a variable is very different from an element of a sequence. Because it takes advantage of the interface for places, incf will work on any place, be it a variable, the slot of an object, or a user defined place.

So at this point you are probably wondering how does incf work and more generally, how do you write macros that use places? To write such a macro, you need to use the function get-setf-expansion.1 Get-setf-expansion takes an expression representing a place and returns a total of five values (if you are unfamiliar with multiple values, see my post on multiple-value-bind). Altogether, these five values tell you everything you need to know about the place in order to read and write to it.

To show you how you are supposed to use get-setf-expansion, I’m first going to demonstrate how you could use it to write the expansion of incf by hand. After that, I will show code that will automate this, which winds up being an implementation of incf. Let’s start by writing the expansion of the example above. The one where the element of a sequence is being incremented. To write the expansion of that by hand, you would first call get-setf-expansion to obtain all of the information:2

(get-setf-expansion '(elt seq x))

In SBCL this call will return the following values:

;; (1) temps
(#:seq1017 #:x1016)

;; (2) exprs
(seq x) 

;; (3) stores

;; (4) store-expr
(sb-kernel:%setelt #:seq1017 #:x1016 #:new1015) 

;; (5) access-expr
(elt #:seq1017 #:x1016))

From now on, I will refer to each value returned by get-setf-expansion by the name in the comment before it (e.g. temps refers to the first value).

In order to uniquely identify the element of a sequence (the place we are working with in this example), you need two things. You need the sequence itself and the index into the sequence. That is exactly what the two expressions in exprs evaluate to! Since incf needs to use these values multiple times, the two values have to be bound to gensyms in order to prevent multiple evaluation (see my post on once-only for why multiple evaluation is a problem). You are supposed to bind the values of the expressions to the gensyms in temps so that the other expressions returned by get-setf-expansion can use those gensyms to easily determine the place being worked with. The bindings need to be made with let* because it is possible for an expression in exprs to refer to the value of a previous expression in exprs. So the first part of the expansion will bind all of the symbols in temps to values of the expressions in exprs with let*:

(let* ((#:seq1017 seq) (#:x1016 x))

Now the gensyms in temps can be used to uniquely identify the place. As I mentioned previously, the other expressions can now easily determine the place through the gensyms. For example, access-expr can be used to retrieve the value currently in the place. Since the place we are dealing with is the element of a sequence,  access-expr is just a call to elt using the gensyms in temps as the arguments. We are going to use access-expr in a moment, but first I have to talk about how to write to the place.

In order to write to the place, you need to use stores and store-exprStores is a list of gensyms that need to be bound to the values that are to be stored in the place (it is possible for a single place to hold multiple values).  In this case we want to bind the gensym in stores to one plus the value already in the place. We can easily obtain the value in the place through access-expr. Once the gensyms have been bound, you can use store-expr to actually write the values in stores to the place. Notice how store-expr is a call to an internal SBCL function sb-kernel:setelt% that uses the gensyms in temps and stores as arguments. Presumably sb-kernel:setelt% sets the element of a sequence. After adding the binding for the gensym in stores and store-expr, we wind up with the final expansion which looks like:3

(let* ((#:seq1017 seq) 
       (#:x1016 x) 
       (#:new1015 (+ 1 (elt #:seq1017 #:x1016))))
  (sb-kernel:%setelt #:seq1017 #:x1016 #:new1015))

To review, the above code first binds the gensyms in temps to the values of the expressions in exprs. This allows access-expr and store-expr to use the gensyms in temps in order to determine the place being worked with. Then the code uses access-expr to retrieve the value, adds one to that, and binds that value to the gensym in stores. This is because the value of the gensym in stores is ultimately going to be the one written to the place. Finally the code evaluates store-expr in order to actually store the value in the gensym into the place.

Now here is one possible implementation of incf,4 which is code for everything we just did by hand. I called it incf% so that it doesn’t have the same name as the builtin version.

(defmacro incf% (place)
        (temps exprs stores store-expr access-expr)
      (get-setf-expansion place)
    `(let* (,@(mapcar #'list temps exprs)
            (,(car stores) (+ 1 ,access-expr)))

The above code first binds the five values returned by get-setf-expansion to variables. It then generates a let* binding which binds the symbols in temps to the expressions in exprs and also binds the gensym in stores to one plus the result of evaluating access-expr. Finally the above code splices in store-expr to actually write the value. And that is everything there is to incf.

Incf is but a single example of what can be done with places. In the next couple of posts, I plan to cover some really cool macros that encapsulate a bunch of common patterns related to places.

The post Getting Places appeared first on Macrology.

Patrick SteinSay What You Mean

· 19 days ago

There is a scene in the movie The Birdcage where the son tells his father that he (the son) has met a girl and is going to get married. The father begins gulping down the glass of wine that he has in hand. The son asks, Are you upset? The father finishes the glass of wine and says, Let me tell you why.

Here is a function that I wrote several years ago.

(sheeple:defreply mouse-move ((item =draggable=) xx yy)
  (let ((dragging (dragging item)))
    (when dragging
      (let ((dx (- xx (car dragging)))
            (dy (- yy (cdr dragging))))
        (incf (offset-x item) dx)
        (incf (offset-y item) dy))
      (let ((pp (parent item)))
        (when pp
          (when (< (width pp) (+ (offset-x item) (width item)))
            (setf (offset-x item) (- (width pp) (width item))))
          (when (< (height pp) (+ (offset-y item) (height item)))
            (setf (offset-y item) (- (height pp) (height item))))))
      (when (< (offset-x item) 0) (setf (offset-x item) 0))
      (when (< (offset-y item) 0) (setf (offset-y item) 0))

This is awful! Am I upset? Let me tell you why.

Is it the Single Responsibility Principle (SRP)? No.

Is it Don’t Repeat Yourself (DRY)? No.

Is it Mixing Levels of Abstraction? Closer, but not quite.

Those are all clearly violated by this code. But, that’s not really the problem. The problem is Why. Nothing about this code tells you why it is here or what is doing.

There is no way to glance at that function and have any idea what’s going on. You have to read it carefully. You have to understand things that aren’t even in this source file to make head nor tail of it. Once you understand the second LET block, you will have nine more lines of code without the least inkling of why there should be nine more lines of code. Anyone care to hazard a guess as to why this function returns T (only) when we’re dragging?


Two years ago, a colleague and I were tasked with providing docstrings for every function in all of the code we’d written in the last year. We’d done well on providing docstrings to the outward-facing functions, but now we had to do the rest. He started at one end of the directory (in alphabetical order), and I started at the other end. This gave me a good opportunity to look closely at a boat-load of code he’d written that I’d never really delved into before.

He was absolutely religious about encapsulating containers. If he had a hash-table or a p-list or a flat list in a DEFVAR, there was one and only one function that retrieved items from it and at most one function that added items to it. Those functions were one or two lines each (two if they needed a mutex). Those functions were named after what the collection was storing not what mechanism was used to store them.

A lot of times when people talk about the value of encapsulating, they talk about shielding the rest of the code from the implementation details so that if you need to replace how it’s actually implemented on the back end you can do it without breaking any existing code. You are protecting your precious implementation from how people will use it so that you can someday replace the implementation with an even more precious implementation next year (when your language finally gets first-class functions).

I’ve been coding for a good long time now. I’m going to let you in on a little secret. Code almost never gets replaced. When code does get replaced, it almost never continues to adhere to the old API (there was always a semantic leak). If there is a business justification strong enough to let you replace the code, it’s because the old code has become an unmaintainable mess of people subverting the interface or the code as it is didn’t scale and now synchronous things need to happen asynchronously or local things have to happen remotely and hiding that under your old API isn’t going to relieve the bottlenecks.

Trying to insulate your code so that it’s easy to replace is looking down the wrong end of the telescope. The real benefit of encapsulation is that the people who read your code later can be half-asleep and still get everything—your code will scream its meaning. The real benefit of encapsulation is that the person debugging your code can set a break-point in a place that means something—not in the seventeen places the state might have changed but in the only place it could change.

Making It Better

Any ideas what the body in this function does?

(sheeple:defreply mouse-move ((item =draggable=) xx yy)
  (if (being-dragged-p item)
      (handle-event ()
         (let ((dx (- xx (drag-starting-x item)))
               (dy (- yy (drag-starting-y item))))
           (translate-widget item dx dy)
           (keep-widget-inside-parent item)))
      (ignore-event ())))

The new functions BEING-DRAGGED-P, DRAG-STARTING-X, and DRAG-STARTING-Y are just wrappers around what had been explicitly treated as an (OR NULL (CONS INTEGER INTEGER)).

(defun being-dragged-p (item)
  (dragging item))

(defun drag-starting-x (item)
  (car (dragging item)))
(defun drag-starting-y (item)
  (cdr (dragging item)))

It is still an (OR NULL (CONS INTEGER INTEGER)) but nobody ever has to care. Nobody ever has to try to remember what the integers mean. Sure, you could replace it with a structure or a complex number, but why would you ever bother? Why would you ever look at it again?

The new macros HANDLE-EVENT and IGNORE-EVENT encapsulate the return value of this function into something with meaning.

(defmacro handle-event (() &body body)
       (values t)

(defmacro ignore-event (() &body body)
       (values nil)

It might still be too easy to write an event-handler with a path which doesn’t end in one of these two macros, but it is way better than that dangling T was. It looks like it’s really supposed to be there, and it looks like what it means rather than what it is.

The TRANSLATE-WIDGET and KEEP-WIDGET-INSIDE-PARENT functions can benefit greatly with some further helper functions (and analogous functions for top and bottom):

(defun left (item)
  (offset-x item))
(defun (setf left) (x item)
  (setf (offset-x item) x))
(defun right (item)
  (+ (left item) (width item)))
(defun (setf right) (x item)
  (setf (offset-x item) (- x (width item))))

Some Rules of Thumb

If you find that when you want to check (PRED1 ...) you instead have to check:

(and (PRED0 ...)
     (PRED1 ...))

Then you should consider making a function that does them both. Consider the difference between these two blocks of code:

(when (and (connectedp (player1 g))
           (connectedp (player2 g))
           (not (pausedp g)))

(when (game-active-p g)

If you find that you are depending on the NULL-ness or positiveness or some other property of some number of state variables to decide which course of action to take, then you should consider making predicates named after your state. In many OO scenarios, you may even want to explicitly track (or calculate) which state you are in at all times.

(defmacro state-case (g &body clauses)
  `(ecase (calculate-or-fetch-state-of g)

(state-case g

In more imperative languages, it may even be beneficial to keep a STATE member variable in your class. When doing that, make sure that there is one and only one function which actually mutates the value of that STATE member. This will let you:

  1. Log all state transitions without having to hunt for all of them.
  2. Quickly hunt for all of them if you want to do that
  3. Set a break point on all state changes.
  4. Enforce the validity of transitions (or at least scream loudly when something transitions from STOPPED to PAUSED without having passed through PLAYING first).

If you have to check whether some resource is being used by some instance, don’t ask it which resource it is using, ask it whether it is using the one you want.

;;; Common: Reader is forced to know each player has one socket and
;;;    that sockets are comparable with #'=
(loop :for player :in all-networked-players
      :until (= socket-with-something-happening
                (player-socket player))
      :finally (return player))

;;; Better: All I wanted to know is, "Is this yours?"
(loop :for player :in all-networked-players
      :until (player-using-socket-p player
      :finally (return player))

Encapsulation is about protecting the person who has to read your code. It’s not about protecting your code.

ABCL Devabcl-1.3.3 released

· 19 days ago
In anticipation of the coming season, we have released abcl-1.3.3

Version 1.3.3


*  [r14802,r14813] Add character name for non-breaking space

   Use a human readable name for character 160, #\No-break_space,
   following sbcl, ccl and clisp. This permits the Quicklisp system
   spinneret to load.  The #\No-break_space name is a valid
   CHAR-NAME/NAME-CHAR pair, but is emitted directly as a glyph wrt. the
   current output encoding under the CL:FORMAT "~:c" directive as
   these implementations do by default.

   Thanks to Javier Olaechea.


* [r14808] CL:FILE-WRITE-DATE fixed for logical pathnames


** Update references to new git repository

** ABCL now runs the git master consolidated ANSI-TEST suite which
   features subdirectories and distinquished value for

** ABCL.TEST.ANSI:CLEAN-TESTS now acts recursively via appropiate
   Pathname wildcards to match new directory structure.


  Fix COMPILE-SYSTEM to offer full ANSI environment for ASDF and


** Use of Maven has been robustified.

*** [r14803] Fix usage with all known versions through maven-3.3.3


*** [r14806] Fix usage with specifying local Maven repository

** More complete attempt at re-initialization via

        (ABCL-ASDF:INIT :force t)

Victor AnyakinIntroducing scanf in Common Lisp

· 20 days ago

There are many ways to extract data from strings or files. The scanf family of function offers one of them.

These functions scan input according to a provided format string. The format string might contain conversion specifiers or conversion directives to extract integers, floating-point numbers, characters, strings, etc. from the input and store it in the arguments.

For example, a format string for parsing components of an IP address might look like: “%3d.%3d.%3d.%3d” — the scanf function will parse 4 integers (maximum 3 digits each) that are delimited with dots and return them to the caller.

There are basically two ways to implement scanf:

  1. as an interpreter, that scans format string and executes commands as they are retrieved.
  2. as a translator to an intermediate language that, in turn, is compiled into machine code.

The trivial-scanf package (that comes as the part of the CL-STRING-MATCH library) takes the first approach. The trivial-scanf implementation reads one character at a time, and depending on the read character performs the designated operation. Underneath, it uses PROC-PARSE library to deal with the input. Outline of the function’s main loop looks as follows:

 (while (< fmt-pos fmt-len))
 (for c = (char fmt fmt-pos))
 (case c
    ;; process conversion directive
   ((#\Space #\Tab #\Return #\Newline #\Page)
    ;; process white space characters
    ;; process ordinary characters

Conversion directives might have optional flags and parameters that must be taken into account. Simple directives, like %d, are handled in a straightforward way: input matching to the designated data type (digits) are bound to a string that is then parsed using corresponding function (parse-integer in this case).

However, the standard scanf also specifies a directive to match a set of designated characters. For example, directive ‘%[a-z0-9-]’ would scan input and return a string composed of letters, digits, and a dash from the current position, until first mismatch. In case, if we dealt with an octet-string (a string where every character is guaranteed to be a single byte in size), it would be feasible to interpret this directive using a table to mark characters that belong to the set. The trivial-scanf takes another approach: characters set directive is converted into a list of closures that serve as predicates for the input string binding operation. In our example, the list of closures would contain predicates for: (range #\a...#\z), (range #\0...#\9) (character #\).

trivial-scanf will be accessible through Quicklisp after the next packages update. At the moment you can clone the repository and install it locally.

Some usage examples:

(ql:quickload :trivial-scanf)
(snf:scanf "%3d.%3d.%3d.%3d" "") => (127 0 0 1)
(snf:scanf "%d %[A-C] %d" "1  ABBA  2") => (1 "ABBA" 2)

This the first (almost alpha) release of the code, so some bugs are expected. Feel free to comment or submit them.

trivial-scanf is the part of the CL-STRING-MATCH library.

Zach BeaneMy new favorite slime/sbcl/ccl trick

· 22 days ago

Thanks to _death on #lisp, I just updated ~/.swank.lisp with this:

(push (lambda (&rest args)
        (apply #'swank:ed-in-emacs args)

Update: Matt Emerson clued me in to this:

(setq ccl:*resident-editor-hook* #'swank:ed-in-emacs)

Now I can (ed “foo.lisp”) in the repl and it pops open in a new buffer. Fantastic!

Joe MarshallIntegers and rationals

· 23 days ago
In an earlier post, I asked readers to implement the bijection rational->integer and integer->rational. John Cowan suggested the Calkin-Wilf tree as a starting point. The Calkin-Wilf tree is a rooted binary tree where the nodes (or vertices, if you like) are labeled with positive rational numbers. It is infinite and complete: every node has two children. The Calkin-Wilf tree is constructed so that every rational number is assigned a unique node. Every positive rational number appears once and exactly once in the tree. The path from the root node to any selected rational is unique and can be encoded (in binary) as an integer.
1 ]=> (rational->integer 355/113)

;Value: 67107847

1 ]=> (integer->rational 67107847)

;Value: 355/113

1 ]=> (cwt/value *the-calkin-wilf-tree*)

;Value: 1

1 ]=> (cwt/value (cwt/left *the-calkin-wilf-tree*))

;Value: 1/2

1 ]=> (cwt/value (cwt/right *the-calkin-wilf-tree*))

;Value: 2

1 ]=> (cwt/value (cwt/left (cwt/right (cwt/left (cwt/left *the-calkin-wilf-tree*)))))

;Value: 4/7
Ho hum. We've all seen this sort of thing before.

Here's the unusual part:
1 ]=> cwt/left

;Value 1236: #[linear-fractional-transform 1236 x/(x + 1)]

1 ]=> cwt/right

;Value 1237: #[linear-fractional-transform 1237 (x + 1)]
So I can write
1 ]=> (cwt/value ((compose cwt/left cwt/right cwt/left cwt/left) *the-calkin-wilf-tree*))

;Value: 4/7

1 ]=> (lft/compose cwt/left cwt/right cwt/left cwt/left)

;Value 1260: #[linear-fractional-transform 1260 (3x + 1)/(5x + 2)]
(See "Playing with Linear Fractional Transforms")

The dyadic fractions are those rational numbers whose denominator is a power of 2. Numbers like 1/4, 3/8, or 11/32. These are the divisions you'd find on a ruler (in the US). Floating point numbers are usually implemented as dyadic fractions.
You can put the dyadic fractions into a binary tree as follows:

(define *the-dyadic-fraction-tree* 1)

(define (dft/left node)
  (/ (- (* (numerator node) 2) 1)
     (* (denominator node) 2)))

(define (dft/right node)
  (/ (+ (* (numerator node) 2) 1)
     (* (denominator node) 2)))

1 ]=> *the-dyadic-fraction-tree*

;Value: 1

1 ]=> (dft/left *the-dyadic-fraction-tree*)

;Value: 1/2

1 ]=> (dft/right *the-dyadic-fraction-tree*)

;Value: 3/2

1 ]=> (dft/left (dft/left (dft/right (dft/left *the-dyadic-fraction-tree*))))

;Value: 9/16
The next question is, what happens if I use a path derived from the Calkin-Wilf tree and use it on the dyadic fraction tree? Yes, this is a fairly random thing to try, but the trees are the same (that is, have the same structure) even if the values at the nodes are not. Either set of fractions is in a one-to-one mapping with the tree, so there is a one-to-one mapping between rational numbers and dyadic fractions.
This is Minkowski's ? (question mark) function. It maps the rational numbers on the X axis to the dyadic fraction on the Y axis. It has a number of weird properties. For example, it is strictly increasing and continuous, but it is not absolutely continuous. The function does not have a derivative in the usual sense.

Joe MarshallA textbook case

· 24 days ago
This is priceless. The url is It says
This is in a high school math textbook in Texas.
 Example 2 : Is there a one-to-one and onto correspondence between integers and rational numbers?

... -4 -3 -2 -1 0 1 2 3 4 ...
... -1/4 -1/3 -1/2 -1/1 -2/4 -2/3 -2/2 -2/1 -3/4 -3/3 -3/2 -3/1

No matter how you arrange the sets, there is never one unique integer for each rational number. There is not a one-to-one and onto correspondence.

The challenge: implement rational->integer that returns "one unique integer for each rational number", and its inverse, integer->rational.

Joe MarshallCurrying and confusion

· 26 days ago
A friend of mine recently said to me "Don't know anything about currying except for food". I'm sure that nearly everyone who reads this blog is familiar with currying functions (and has probably curried a function within the last few hours), but it makes a good blog topic anyway.

"Currying" a function (as opposed to an entrée) is named after Haskell Curry, but he was inspired by a paper by Moses Schönfinkel, and it appears that Gottlob Frege came up with idea. So much for the name.

Pick your favorite binary function. I like "multiply", but any binary function will do. It need not be associative or commutative. As an example, imagine a print-to function that takes a document and a device.

Now consider these unary functions:
(define (multiply-by-five n) (* 5 n))
(define (multiply-by-negative-one n) (* -1 n))
(define (multiply-by-thirty-seven n) (* 37 n))
There is an obvious pattern here that we can abstract out:
(define (make-multiply-by x) (lambda (n) (* x n))

(define multiply-by-five (make-multiply-by 5))
(define multiply-by-negative-one (make-multiply-by -1))
(define multiply-by-thirty-seven (make-multiply-by 37))
Or, if we use print-to
(define (make-print-to-device device) (lambda (doc) (print-to doc device)))

(define print-to-inkjet (make-print-to-device the-inkjet-printer))
(define print-to-daisywheel (make-print-to-device the-daisy-wheel-printer))
Note the similarity between make-multiply-by and make-print-to-device.
(define (make-multiply-by x) (lambda (n) (* x n))
(define (make-print-to-device device) (lambda (doc) (print-to doc device)))

(define (make-<unary> an-argument)
  (lambda (another-argument) (<binary> an-argument another-argument)))
We can abstract this operation:
(define (make-unary-maker binary-operation)
  (define (make-unary-operation an-argument)
    (lambda (other-argument)
      (binary-operation an-argument other-argument)))
We have a pile of functions, all similar because they were created with the make- function. And the make- functions are all similar because they were created with make-unary-maker.

This is the meta-operation we call "currying". We take a function of several arguments, decide on some fixed values for some subset of arguments, and return a new function of the remaining, unfixed arguments.

Captain Obvious has a few things to say about functions.

A function won't return a value unless you call it.

The cardinality of the set of return values cannot be larger than the cardinality of the set of valid arguments. Functions don't make up values. There can be fewer possible return values than possible valid arguments, but never more.

If two sets are different sizes, then if you try to pair up elements from each set, you'll have some left over.

If we compose two functions and the set of possible output from the first is different in size from the set of possible valid input to the second, then there will either be output from the first that the second cannot accept, or possible inputs to the second that the first cannot produce. The latter case isn't a problem, but in the former case, you'll get an error.

If you "invert" a function, its output becomes input and vice versa.

Since inverse functions (when they exist, that is) are functions, The same constraints on the cardinality of input and output apply, but in the other direction. If you invert a composition, then the valid arguments and results swap roles. If the cardinalities match, we're cool, but if there is a mismatch, we're in the opposite situation of the non-inverse, and what was not an error (i.e. accepting an input that can never be produced) becomes one (i.e. producing a value that cannot be accepted).

If the appropriate cardinalities never increase, you can compose two functions. If the appropriate cardinalities match, you can invert the composition.

What does this have to do with currying?

I'm reading a bit about group theory and I chanced upon some exposition that was thick with comments and arguments surrounding the cardinality of various sets and subsets within the group. Once the exposition introduced a number of sets with equal cardinalities, the author pointed out that you can define an invertible function between any two sets with the same cardinality. Since the set of integers and the set of multiply-by- functions have the same cardinality, you could define a function that maps integers to multiply-by- functions. This isn't much of a revelation because that's what we did to get those functions in the first place. After slogging through this, I finally worked out what they were trying to say: "You can curry the binary operation." But they completely avoided the word "curry", and made arguments about set cardinality.

The next paragraph in the exposition was worse. You can curry the other argument to the binary operation. This leads to a completely different set of curried functions over a different set of arguments. Now it ultimately doesn't matter which argument you curry, when all is said and done, both arguments show up and are passed to the binary function. But all the intermediate values are drawn from different sets than if you curried the other way. It takes a very complicated argument about cardinalities to derive that either way of currying will work.

Eugene ZaikonnikovVisualizing larger graphs with Tulip

· 27 days ago

Simple algorithms handling large-ish data sets tend to be pretty. However, the results aren't necessarily intuitive for sifting through with REPL and Lisp inspector, and dedicated visualization tools come handy.

For sizable graphs I settled with Tulip, a powerful and comprehensive tool for juggling around massive (hundreds of thousands nodes) data sets. One can conveniently pan, rotate and zoom the graph, limit the visibility to specific clusters. It is possible to run a wide range of ordering, manipulating and testing algorithms as well.

I came up with cl-tulip-graph (formerly Bouquet) for quickly blueprinting a .tlp graph of a Lisp data structure. The README explains its use, but here's a real-life sample of generation. It generates a graph for the internal state of a computationalist pattern matcher; the particular structural details are unimportant here.

 1 (defun render-graph (&optional (filename *standard-output*))
 2     (bouquet:new-graph)
 3   (loop for entry in (append '(zero one two three four five six seven eight nine
 4           *mnist-id* *row* *image* *blob*
 5           dark light)
 6            *universum*) do
 7        (bouquet:register-node entry)
 8        (bouquet:label (bouquet:node entry) entry))
 9   (loop for entry in '(*mnist-id* *row* *image* *blob*)
10      do
11        (bouquet:make-cluster (symbol-name entry))
12        (loop for rec = (symbol-plist entry) then (cddr rec)
13    for ctxt = (first rec)
14    for links = (second rec)
15    while rec do
16      (bouquet:add-to-cluster
17       (bouquet:cluster (symbol-name entry))
18       (bouquet:node ctxt))
19      (loop for r in links do
20      (bouquet:register-edge
21        (bouquet:node ctxt)
22        (bouquet:node r)))))
23   (with-open-file (f filename :direction :output
24           :if-exists :overwrite
25           :if-does-not-exist :create)
26           (bouquet:render-graph f)))

After the graph initialziation, the loop on line 3 through 8 sets up all the nodes with labels. The next loop sets up a bunch of clusters and adding the edges between the nodes. The graph is rendered into file stream on the last line.

Unordered graph

This trihobeozar of a graph rendered nicely via Cone Tree layout:

Cone layout

Joe MarshallSomething less abstract

· 29 days ago

pre { border:1px dashed #aaaaaa; background:#eeeeee; white-space:pre; font-family:monospace; font-size:9pt; line-height: 10pt; height:auto; width:auto; padding:5px; margin-top: .75em; margin-left:10px; margin-bottom: .75em; overflow:auto; }

To recap, a linear fractional transform (lft) is a function of this form:

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

Using an object-oriented extension to Scheme, I've given these functions a special print method so they look pretty. (I'm using MIT/Gnu Scheme with SOS, a CLOS-like object system. I haven't included all the code in my posts, but it should be easy for an intermediate programmer to replicate this.)

1 ]=> (make-linear-fractional-transform 1 2 3 4)

;Value 13: #[linear-fractional-transform 13 (x + 2)/(3x + 4)]
But otherwise they are normal one argument functions. Since they take and return objects of the same type, you can chain them together with function composition.
(define foo (make-linear-fractional-transform 1 2 3 4))
(define bar (make-linear-fractional-transform 1 4 0 2))

1 ]=> (compose foo bar)

;Value 14: #[compiled-closure 14 (lambda "global" #x35) #x84 #x25de16c #x3a5ea78]

1 ]=> ((compose foo bar) 1/10)

;Value: 81/203
lft/compose knows to explicitly construct an lft rather than a generic closure,
1 ]=> (lft/compose foo bar)

;Value 15: #[linear-fractional-transform 15 (x + 8)/(3x + 20)]

1 ]=> ((lft/compose foo bar) 1/10)

;Value: 81/203
but there is no difference when you apply the composed function.

I've been distracted by group theory, so let's do something less abstract. Here is an infinite stream of linear fractional transforms.

(define lft-stream
   (make-linear-fractional-transform 0 4 1 0)
    (lambda (n d)
      (make-linear-fractional-transform n 1 d 0))
    (cons-stream 1 (stream-map square (naturals))))))

1 ]=> (pp (stream-head lft-stream 10))
(#[linear-fractional-transform 17 4/x]
 #[linear-fractional-transform 26 (x + 1)/x]
 #[linear-fractional-transform 25 (3x + 1)/x]
 #[linear-fractional-transform 34 (5x + 1)/4x]
 #[linear-fractional-transform 33 (7x + 1)/9x]
 #[linear-fractional-transform 32 (9x + 1)/16x]
 #[linear-fractional-transform 31 (11x + 1)/25x]
 #[linear-fractional-transform 30 (13x + 1)/36x]
 #[linear-fractional-transform 29 (15x + 1)/49x]
 #[linear-fractional-transform 28 (17x + 1)/64x])

This is a stream of functions, so let's compose them. Imagine our function stream is (f g h ...). We want to generate the stream (f (compose f g) (compose f g h) ...)

1 ]=> (fold-stream lft/compose lft:identity lft-stream)

;Value 36: {#[linear-fractional-transform 37 x] ...}

1 ]=> (pp (stream-head (fold-stream lft/compose lft:identity lft-stream) 10))
(#[linear-fractional-transform 37 x]
 #[linear-fractional-transform 17 4/x]
 #[linear-fractional-transform 45 4x/(x + 1)]
 #[linear-fractional-transform 44 (12x + 4)/(4x + 1)]
 #[linear-fractional-transform 43 (19x + 3)/(6x + 1)]
 #[linear-fractional-transform 42 (160x + 19)/(51x + 6)]
 #[linear-fractional-transform 41 (1744x + 160)/(555x + 51)]
 #[linear-fractional-transform 40 (23184x + 1744)/(7380x + 555)]
 #[linear-fractional-transform 39 (10116x + 644)/(3220x + 205)]
 #[linear-fractional-transform 38 (183296x + 10116)/(58345x + 3220)])

Let's apply these transforms to a number. 42 is random enough.

1 ]=> (pp (stream-head 
      (lambda (transform) (transform 42.0)) 
      (fold-stream lft/compose lft:identity lft-stream))
That looks familiar. We'll pick a point further on in the stream.
1 ]=> (stream-ref (fold-stream lft/compose lft:identity lft-stream) 20)

;Value 48: #[linear-fractional-transform 48 (2166457145737216x + 48501417558016)/(689604727481670x + 15438480702645)]

1 ]=> ((stream-ref (fold-stream lft/compose lft:identity lft-stream) 20) 1.0)

;Value: 3.1415926535898056
This stream of functions are functions that approximate π. Each element in the stream is a function that is a better approximation of π than the last.
1 ]=> (stream-ref (fold-stream lft/compose lft:identity lft-stream) 10)

;Value 51: #[linear-fractional-transform 51 (3763456x + 183296)/(1197945x + 58345)]

1 ]=> (define foo (stream-ref (fold-stream lft/compose lft:identity lft-stream) 10))

1 ]=> (foo 0.0)

;Value: 3.1415888250921244

1 ]=> (foo 1.0)

;Value: 3.141593103503172

1 ]=> (exact->inexact (foo 'infinity))

;Value: 3.1415933118799275
Ok, let's subtract off that three.
(define (make-lft-subtract n)
  (make-linear-fractional-transform 1 (- n) 0 1))

1 ]=> (lft/compose (make-lft-subtract 3) foo)

;Value 54: #[linear-fractional-transform 54 (169621x + 8261)/(1197945x + 58345)]

1 ]=> ((lft/compose (make-lft-subtract 3) foo) 42.)

;Value: .14159330668296408
And multiply by ten
(define (make-lft-multiply n)
  (make-linear-fractional-transform n 0 0 1))

1 ]=> (lft/compose (make-lft-multiply 10) (make-lft-subtract 3) foo)

;Value 55: #[linear-fractional-transform 55 (339242x + 16522)/(239589x + 11669)]

1 ]=> ((lft/compose (make-lft-multiply 10) (make-lft-subtract 3) foo) 42.)

;Value: 1.4159330668296406
and now the next decimal digit is in the ones place. If we repeat this process, we'll generate the decimal digits of our approximation to π one at a time.
1 ]=> ((lft/compose (make-lft-multiply 10) (make-lft-subtract 3) foo) 42.)

;Value: 1.4159330668296406

1 ]=> ((lft/compose (make-lft-multiply 10)
                    (make-lft-subtract 1)
                    (make-lft-multiply 10)
                    (make-lft-subtract 3) foo) 42.)

;Value: 4.159330668296407

1 ]=> ((lft/compose (make-lft-multiply 10)
                    (make-lft-subtract 4)
                    (make-lft-multiply 10)
                    (make-lft-subtract 1)
                    (make-lft-multiply 10)
                    (make-lft-subtract 3) foo) 42.)

;Value: 1.5933066829640692
We'll define a composition as a data structure with an lft and a promise (delayed evaluation) to provide more lfts to compose. Operations on a composition will work on the lft and try to avoid forcing the promise if possible. If the lft isn't a good enough approximation, we force the promise, get a new lft, and create a new composition.
(define-class (<lft-composition>
        (constructor make-lft-composition 
                            (linear-fractional-transform promise)))
  (linear-fractional-transform define accessor accessor composition-transform)
  (promise                     define accessor accessor composition-promise))

(define (composition/refine lft-composition)
  (let ((lft (composition-transform lft-composition))
        (lft-stream (force (composition-promise lft-composition))))
    (make-lft-composition (lft/compose lft (head lft-stream)) (cdr lft-stream))))
Getting the integer part of a composition involves getting the integer part of the transform, if possible, and if not, refining the composition until it is possible. composition/integer-and-fraction returns two values: the integer extracted, and the final composition remaining after any refinement steps and after subtracting off the integer.

(define (composition/%integer-part lft-composition)
  (lft/integer-part (composition-transform lft-composition)))

(define (composition/integer-and-fraction lft-composition)
  (let ((integer (composition/%integer-part lft-composition)))
    (if (not integer)
        (composition/integer-and-fraction (composition/refine lft-composition))
        (values integer (make-lft-composition
                            (make-linear-fractional-transform 1 (- integer) 0 1)
                            (composition-transform lft-composition))
                         (composition-promise lft-composition))))))
We'll create a stream of digits by peeling off the integer parts and multiplying the fraction by 10.
(define (composition->digit-stream c radix)
  (receive (ipart fpart) (composition/integer-and-fraction c)
       (lft/compose (make-linear-fractional-transform radix 0 0 1)
      (composition-transform (force fpart)))
       (composition-promise (force fpart)))

(define foocomp (make-lft-composition (head lft-stream) (cdr lft-stream)))

1 ]=> (stream-head (composition->digit-stream foocomp 10) 50)

;Value 204: (3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1)

Clozure CL BlogClozure CL 1.11 pre-release available for testing

· 30 days ago

A pre-release version of Clozure CL 1.11 is now available for testing.

Please use Subversion to get a copy. For example, to get the 1.11 pre-release for Linux/x86, you would type (where the $ is the shell prompt)

$ svn co

To get a version for a different platform, change the linuxx86 to one of darwinx86, freebsdx86, solarisx86, windows, or linuxarm.

They hardly merit a mention, but draft release notes are available for your perusal.

If you find problems, the best way to report them is to use After you register and sign in, click on “New Ticket” in the top navigator bar. If you don’t want to register, you can send mail to openmcl-devel or to me ( privately.

Thank you for any testing that you are willing to do. After a short period of testing and bug fixing, I will build updated binaries and make the 1.11 release official.

Michael MalisDefasm

· 30 days ago

This post is the second part of a two part series exploring the emulator cl-6502. If you haven’t read the first part exploring the implementation of addressing modes in cl-6502, you can find it here.

This post is going to go over how cl-6502 implements the instruction set of the 6502. Most of the work in defining the instruction set is done by a single macro, defasm. But before I can go into the details of defasm, I have to explain how cl-6502 represents instructions.

cl-6502 represents each instruction as a function inside an array called *array-funs*. The function for a specific instruction is indexed by that instruction’s opcode.1 To execute an instruction, cl-6502 looks up the opcode of the current instruction and calls the function at that location inside of *array-funs*. There is also a second array, *opcode-metadata*, which keeps track of some metadata about each instruction such as the number of bytes each one takes up. All defasm does is make it easy to generate all of the functions and metadata that wind up inside of those two arrays.

To show you just how easy it is to implement instructions with defasm, here is the implementation of the adc (add with carry) instruction:

(defasm adc (:docs "Add to Accumulator with Carry")
    ((#x61 6 2 indirect-x)
     (#x65 3 2 zero-page)
     (#x69 2 2 immediate)
     (#x6d 4 3 absolute)
     (#x71 5 2 indirect-y)
     (#x75 4 2 zero-page-x)
     (#x79 4 3 absolute-y)
     (#x7d 4 3 absolute-x))

  (let ((result (+ (cpu-ar cpu) 
                   (status-bit :carry))))
      :carry (&gt; result #xff)
      :overflow (overflow-p result (cpu-ar cpu) (getter))
      :negative (logbitp 7 result)
      :zero (zerop (wrap-byte result)))
    (setf (cpu-ar cpu) (wrap-byte result))))

There are two main parts to the above code. The first part specifies all of the addressing modes the instruction is compatible with along with the metadata for each variant of the instruction (there is a different version of the instruction for every possible addressing mode the instruction can be used with).

After that is the body – the code that actually implements the instruction being defined. The body is responsible for setting all of the appropriate flags and memory locations to the values they should have after executing the instruction. Make sure you note that just like in defaddress, the variable cpu can be used in the body to reference an object that represents the current state of the cpu.

Defasm takes these two pieces, and generates one lambda expression for each variant of the instruction. All of the generated lambda expressions use the same body, except defasm generates some additional code that allows the body to work across all of the different addressing modes.

Now to get into the specifics of the DSL. In the addressing mode part of the DSL, there are four pieces of metadata that need to be associated with each version of the instruction. The first part is the opcode, the machine code representation of the instruction. Next up is the number of cycles it takes for the instruction to execute. After that is the size of the instruction, the number of bytes it takes up in memory. Last is the name of the addressing mode used for that specific variant of the instruction. As an example, here is the metadata for the adc instruction in the indirect-x addressing mode:

(#x61 6 2 indirect-x)

What it is saying is that this version of the instruction has the opcode #x61, takes six cycles to run, takes two bytes in memory, and uses the indirect-x addressing mode. The fact that when an instruction is used in different addressing modes, it uses a different number of clock cycles and takes up a different amount of space is one reason why different addressing modes are provided in assembly language.

For the body, defasm does something very clever to have the body work for every possible addressing modes. Within the body, the functions getter and setter are bound to local functions that can be used to obtain and modify the argument to the instruction. For each variant of the instruction, defasm generates the definition of these two functions differently so that they will always calculate the correct argument for the given addressing mode.

For example, in the version of adc that uses immediate addressing, getter will just return the value of the operand, but in the version that uses absolute addressing, getter will use the operand as an address and look up the value at that location in memory. In the definition of the adc instruction above, the body uses getter to obtain the argument, adds that to the value in the accumulator, adds in the carry, and then sets all of the appropriate flags and registers depending on the final value it winds up with. Since getter and setter work across all of the different addressing modes, so does the body!

Now let’s look at the actual implementation of defasm:

(defmacro defasm (name (&key (docs "") raw-p (track-pc t))
                  modes &body body)

     ,@(loop for (op cycles bytes mode) in modes collect
         `(setf (aref *opcode-meta* ,op) 
                ',(list name docs cycles bytes mode)))

     ,@(loop for (op cycles bytes mode) in modes collect
         `(setf (aref *opcode-funs* ,op)
                (lambda (cpu)
                  (incf (cpu-pc cpu))
                  (flet ((getter ()
                           ,(make-getter name mode raw-p))
                         (setter (x)
                           (setf (,mode cpu) x)))
                  ,@(when track-pc
                     `((incf (cpu-pc cpu) ,(1- bytes))))
                  (incf (cpu-cc cpu) ,cycles))))))

As usual, I’m going to show a snippet of the implementation of defasm and then show what the macroexpansion of that piece looks like. The first part of the implementation handles the addressing modes and metadata:

(loop for (op cycles bytes mode) in modes collect
  `(setf (aref *opcode-meta* ,op) 
         ',(list name docs cycles bytes mode)))

For each addressing mode, this generates code which will store a list containing the metadata into the proper place in the *opcode-meta* array. In other words it takes each part that looks like:

(#x61 6 2 indirect-x)
and generates code that looks like:
(setf (aref *opcode-meta* #x61)
     '(adc "Add to accumulator with carry" 6 2 indirect-x))

After that we have the part that will generate the actual lambda expressions for the functions that will be stored in *array-funs*:

(loop for (op cycles bytes mode) in modes collect
  `(setf (aref *opcode-funs* ,op)
         (lambda (cpu)
           (incf (cpu-pc cpu))
           (flet ((getter ()
                   ,(make-getter name mode raw-p))
                 (setter (x)
                   (setf (,mode cpu) x)))
          ,@(when track-pc
              `((incf (cpu-pc cpu) ,(1- bytes))))
          (incf (cpu-cc cpu) ,cycles))))

This code loops over all of the metadata for the different addressing modes and uses this information to generate the expression for each variant of the instruction. As mentioned previously, the function will be stored by the variant’s opcode. As for the actual function itself, it does something along these lines. First, it advances the pc. This is done so that the pc now points to the operand of the instruction. By doing this, the job of defaddress becomes much easier since it can use the pc as a pointer to the operand. Next, the function evaluates the body in an environment with getter and setter bound to functions that can be used to read and write to the argument. After that it will advance the pc forward to the next instruction (unless track-pc was false, which happens for instructions that modify the pc themselves such as jumps). Finally, the function will increment the cycle count by the number of cycles it takes the instruction to execute.

The definitions of getter and setter are really just calls to the function with the same name as the addressing mode associated with the variant of the instruction.2 If you look back at the last post, you will see that defaddress automatically generates these “mode” functions. All they do is calculate the effective argument for the given addressing mode! Exactly what getter does. As an example of what the expansion looks like, here is the lambda expression generated for the adc instruction in the indirect-x addressing mode.

(setf (aref *opcode-funs* #x61)
      (lambda (cpu)
        (incf (cpu-pc cpu))
        (flet ((getter ()
                 (get-byte (indirect-x cpu)))
               (setter (x)
                 (setf (indirect-x cpu) x)))
         (let ((result (+ (cpu-ar cpu) 
                          (status-bit :carry))))
          (set-flags-if :carry (&gt; result 255) 
                        :overflow (overflow-p result 
                                              (cpu-ar cpu)
                        :negative (logbitp 7 result) 
                        :zero (zerop (wrap-byte result)))
          (setf (cpu-ar cpu) (wrap-byte result))))
        (incf (cpu-pc cpu) 1)
        (incf (cpu-cc cpu) 6)))

And that’s all there is to defasm! There are a couple really cool things you should note about cl-6502. First off, the macros expand into a lot of code. The definition of adc at the beginning of this post expands into roughly 500 lines of code. Here is a link to a gist of it if you want to see it. More incredibly, cl-6502 implements an entire emulator in under 1000 lines of code. cl-6502 is a fantastic example of how effective macros are at creating concise DSLs.

The post Defasm appeared first on Macrology.

Joe MarshallFlipping the number line

· 31 days ago

Here is a number line. It looks funny because I did two things: first, I stretched and compressed different parts so I could fit all the numbers in. Second, I rolled it into a circle.

All the numbers are in there. Most of them are really crammed near the top.

What happens to the number line if you apply a linear fractional transform? Here I apply 1/x:

1/x flips the entire diagram vertically. (What happens if you apply -x?)

In this example, I apply x + 1:

The numbers in the circle rotate clockwise, but not exactly linearly. The negative numbers are compressed and the positive numbers expanded.

There are, of course, an unlimited number of linear fractional transformations I can apply to my number line, but they all act by flipping or rotating the number line in some manner. We can derive every transform by a sequence of flips and rotates. Can we find a basic set of operations from which we can construct all the rest?

We can enumerate all the linear fractional transforms the same way we enumerate all rational numbers. We conceptually make a table of all of them, but we walk the table diagonally. There are four integers per linear fractional transform, rather than the two in a rational number, but that makes only a minor difference. It seems likely that our basic set of operations will be found in the set of linear fractional transforms with small integers for coefficients. If we use the positive and negative integers with absolute value of four or less, we'll have a good sized set to start with. Just from the combinatorics, we'd expect (expt 9 4) possible ways to list them, but many of these are duplicates. Nonetheless, there are still 2736 unique linear fractional transforms with coefficients that have an absolute value of four or less.

(I'm tired of typing "linear fractional transform". I'm going to abbreviate it lft.)

What happens if you compose an lft with itself? Obviously constants and identity remain unchanged, but the other ones are more interesting. These lfts are self inverses. If you compose them with themselves, you get the identity:

#[linear-fractional-transform 20 -x]
#[linear-fractional-transform 14 1/x]
#[linear-fractional-transform 13 -1/x]
#[linear-fractional-transform 227 x/(x - 1)]
#[linear-fractional-transform 226 -x/(x + 1)]
#[linear-fractional-transform 225 -(x + 1)]
#[linear-fractional-transform 224 (1 - x)]
#[linear-fractional-transform 223 (x + 1)/(x - 1)]
#[linear-fractional-transform 222 (1 - x)/(x + 1)]
These ones are not identities when you compose them twice (lft/compose x x), but they are identities if you compose them three times (lft/compose x x x)
#[linear-fractional-transform 522 1/(1 - x)]
#[linear-fractional-transform 521 -1/(x + 1)]
#[linear-fractional-transform 397 -(x + 1)/x]
#[linear-fractional-transform 396 (x - 1)/x]
These two are examples that require four composes
#[linear-fractional-transform 528 (x + 1)/(1 - x)]
#[linear-fractional-transform 527 (x - 1)/(x + 1)]

And these examples require six:

#[linear-fractional-transform 59 (x + 1)/(2 - x)]
#[linear-fractional-transform 58 (x - 1)/(x + 2)]
#[linear-fractional-transform 57 (2x + 1)/(1 - x)]
#[linear-fractional-transform 56 (2x - 1)/(x + 1)]
#[linear-fractional-transform 55 1/(3 - 3x)]

I have not seen an lft that gives the identity when composed with itself five times, nor seven, or eight.

Some lfts never self compose to identities. Obviously repeated self composition of x+1 will never equal the identity.

Joe MarshallLinear fractional transforms and permutations

· 36 days ago

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.

ECL NewsECL 16.0.0 release

· 41 days ago

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!


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

Joe Marshalln-ary functions and argument lists

· 42 days ago
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 <arg3> <arg4>)
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:
  • 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.

CL Test GridRegressions and improvements in quicklisp 2015-08-04

· 42 days ago
The difference between quicklisp 2015-07-10 and quicklisp 2015-08-04 is shown in these reports:
grouped by lisp implementation
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.

Michael MalisDefaddress

· 42 days ago

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:


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)
    (defmethod reader ((mode (eql ',name)))
         "_" 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.

Zach BeaneJean-Philippe Paradis really, really, really wants you to know about his stuff

· 43 days ago

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.

Eugene ZaikonnikovCL-JPEG has been updated

· 44 days ago

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.

Common Lisp TipsWhen a synonym-stream is useful

· 44 days ago

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.

Fernando BorrettiState of the Common Lisp Ecosystem, 2015

· 44 days ago

This is a description of the Common Lisp ecosystem, as of August 2015, from the perspective of a user and contributor.

The purpose of this article is both to give an overview of the ecosystem, and to help drive consolidation in each domain.

Each application domain has recommendations for consolidating that part of the ecosystem, and pointers for interesting future work.

Application Domains

Web Development


Clack, the equivalent of WSGI/Rack has existed since 2009, and is throughly tested and battle-tested. Three web frameworks - Caveman2, Ningle, and Lucerne - are built on top of it.

Clack is an HTTP server abstraction, that allows the user to write web applications (or, more reasonably, web application frameworks) without depending on a particular server.

The importance of using Clack cannot be understated: If you build an application directly on, say, Hunchentoot, you're tied to Hunchentoot, and if a new, faster server - like Woo - comes out, you have to rewrite the entire application to use it. If you write a plugin for Clack - like clack-errors - it is automatically usable by all applications, regardless of framework, that are built on Clack, reducing useless duplication of code.

With Clack, switching from Hunchentoot to Woo, and enjoying the incredible speedup, is a simple matter of installing libev and changing a keyword argument.


Stop using Hunchentoot directly. Use Clack, or even better, one of the frameworks built on it.

Future Work:

The foundation is finished, now it's time to write higher-level layers. An extensible administration framework for Clack applications, like Django's Admin, would be a good example.


This is bound by Common Lisp's ability to compile to JavaScript. Common Lisp being rather a sizeable language, the options are rather limited:

  • Parenscript: A DSL that compiles a subset of Common Lisp to idiomatic JavaScript.

  • JSCL: A CL-to-JS compiler designed to be self-hosting from day one. Lacks CLOS, format and loop.


The best way to help consolidation is to drive one of the existing CL-to-JS implementations forward.

Future Work:

Something like CFFI, but for CL-to-JavaScript implementations, so bindings to JavaScript libraries don't have to be rewritten if a new implementation comes out.

A tool for compiling Common Lisp to JavaScript files, independent of the actual implementation, to make it easier to go from Parenscript to JSCL or to some other implementation.

Command Line

Over the years some tools have cropped up in this area, the latest, and the one that sees to have gained most momentum, is Roswell, an implementation manager/installer and script runner. One neat feature is support for very easily compiling tiny scripts into executables, e.g., for building documentation.

It has recently also been used to install implementations in Travis, thus circumventing some of the problems of cl-travis.


Kill cl-launch, use Roswell.

Future Work:

More Roswell scripts.


For quite a while, a major concern was the lack of a complete GUI solution. Well, now we have it: CommonQt plus Qtools. The former has years of use in real-life applications, and the latter is a layer to make everything simpler.

The biggest problem when using CommonQt is it requires Smoke to run, and getting the libraries can be difficult, especially on systems other than Linux. This is solved by Qtools, which depends on the qt-libs library. It downloads the Smoke libraries for whatever platform you're on, and this makes setting it up and deploying applications easier.


Focus on CommonQt, and help improve cl-cffi-gtk, but other libraries should be considered deprecated.

CLIM is interesting and was the last attempt to do any kind of research on how user interfaces should be built, but is not a viable option in 2015.

Future Work:

More tutorials and examples of using CommonQt and Qtools.

Machine Learning

CLML is a fairly extensive solution. It was developed by Mathematical Systems Inc., a Japanese company. Mike Maul then took it to GitHub and cleaned it up a little. A tutorial on time series is available.

Another candidate in this area is mgl, used by its author to win the Higgs Boson Machine Learning Challenge.

In the area of numerical code, a library I've always though was interesting in this domain is Antik, but sadly it depends on the GNU Scientific Library, making it GPL. There's also mgl-mat and LLA.


A merge of the numerical parts of LLA and mgl-mat, and the machine learning parts of CLML and mgl would solve most consolidation problems in this area.

Future Work:

CLML probably has a lot of numerical code that can be excised and released as a separate library, along the lines of SciPy and NumPy.


cl-dbi provides a uniform interface to the various database server-specific libraries (cl-postgres, cl-mysql, etc.). SxQL provides a DSL for building safe, automatically parameterized SQL queries.

There are two fairly complete ORMs: Crane, by yours truly, and Integral, by the author of cl-dbi.


Discourage using anything other than cl-dbi.

Future Work:

Bindings for other database systems, e.g. Oracle, exist. Writing drivers for cl-dbi would be the best course of action and help consolidation.


I've never done any graphics programming, so my knowledge of this area is lacking. There's CEPL, and its sister project, Varjo, which have a nice collection of video tutorials. Of course, there are lower level libraries, like cl-opengl and cl-sdl2.


Promote the use of CEPL, because it's fairly complete.

Future Work:

A high-level OpenGL library, like pg, would be great.

More libraries in this area, especially for manipulating different mesh or other 3D formats.


cl-async is probably the most complete solution to anything concurrency related. And it's built on libuv, the library that powers Node.js.

Other libraries of interest in this area are,

  • STMX: Provides support for software transactional memory, which is pretty impressive.

  • lparallel: A very complete framework for parallel programming.

Libraries like legion simplify concurrency for specific use cases.


Future Work:

There's plenty of room for new ideas in this area.

File Formats

There exist Common Lisp libraries for all the major file formats:

A new player in the field of JSON libraries is Jonathan, a very fast JSON encoder and decoder.


There are too many XML and JSON libraries, this leads to choice paralysis.

Future Work:

A YAML parser so that cl-yaml doesn't depend on the libyaml library would make distribution far simpler.


UIOP, ASDF's portable compatibility layer, contains a large set of tools for portably doing everything from querying the hostname to running external programs to manipulating environment variables.


Use UIOP for everything. Don't use cl-fad. Don't use OSICAT.

Future Work:

An interesting project to develop in this area would be a DSL for building LLVM IR, either as a string or using the LLVM API bindings. This would allow you to use Common Lisp as an assembly language with a very powerful macro system. A use case: JIT-compiling highly-optimized, SIMD-vectorized numerical code.


Building a framework like Haskell's Criterion would be a good step forward.
My go-to library in this area is esrap, which generates parsers from Lispy grammar definitions. More diversity in this area would be welcome. Recently, proc-parse, a fast vector parsing library, was released.
There is not much to say about this, except that Common Lisp has good tools in this area, like log4cl and vom.


Type System

There's not much to say here, except that Common Lisp has a pretty great type system that is not exploited nearly enough.


Not applicable. CLOS has no competition, e.g. from revived versions of Flavors, and is basically the only OOP system there is in Common Lisp.

Future Work:

I often reach for trivial-types, a library that contains a bunch of simple type specifiers. A larger library, e.g. including this CDR, would be good.


There are many existing test frameworks, the main ones being FiveAM and the much newer Prove.

Of the existing libraries, Prove is a good candidate for the one to settle on. Extensible test reporters are a great idea, and the general approach to extensibility makes it a good solution to the problem of test frameworks.

Other, older libraries depend on test frameworks like rt or lisp-unit, but these aren't relevant anymore.


Discourage using testing frameworks other than FiveAM and Prove.

Future Work:

Writing any new test frameworks will be counter-productive at this point. Work should focus on consolidating the existing ones.

Testing on the Cloud

Common Lisp has good support for using services like Travis and Coveralls, for testing code and tracking code coverage in the cloud, respectively. The two main libraries for this are cl-travis and cl-coveralls, and they are both very easy to use. Testing and tracking the coverage of a Common Lisp project is certainly easier than doing the same with a Python project, in my experience.


cl-travis has some problems, namely, it requires sudo to install implementations, which means it can't use Travis' new Docker-based infrastructure.

Roswell solves this problem, so using Roswell should be encouraged over cl-travis. A tutorial on using Roswell with Travis is here.

Future Work:

Supporting more services, like Circle CI, is always useful. Tutorials are always a good addition.


For online, automatically updated documentation, in the style of Read the Docs, we have Quickdocs, which extracts project API references using docparser.

There aren't many documentation generators, surprisingly. I use Codex to generate my documentation. It's written on CommonDoc, a library that provides a format-agnostic internal representation for documents. Codex is designed along the lines of Sphinx: documentation is written in prose, and you insert automatically-extracted API documentation (functions, macros, classes, etc.) into the text using macros.


Promote the use of Quickdocs by linking to it in library READMEs, to new users, etc.

Future Work:

I'll continue working on Codex and CommonDoc, and any improvements to CommonDoc (mainly, more output formats and more macros) will be reflected in Codex.


This is essentially a solved problem in most implementations. Sometimes you can get tripped up if an implementation's encoding format is set to something like Latin-1 instead of UTF-8, but those are easily fixed, e.g. in SBCL:

(setf sb-impl::*default-external-format* :utf-8)

Other than that, I've never run into any Unicode problems, even when interfacing with C libraries.


Some implementations lag behind others in Unicode support, e.g. ABCL.

Future Work:

There is some work to be done, in the form of missing features of cl-unicode.

Package Management

Quicklisp is the de-facto package manager for Common Lisp. And that's pretty much it. Don't disrupt what works.


Not applicable.

Future Work:

Tools built on Quicklisp, like Quickdocs and qlot.

Build System

ASDF is the de-facto build system of Common Lisp. Everyone uses it.

Every project has an .asd file, called a system definition file, which defines project metadata (author, maintainer, homepage, etc.) and the components.

This, to me, is one of the major selling points of Common Lisp. With languages like Python, every file imports whatever it needs, and your project becomes a massive graph of interdependent files. In ASDF, you basically list the files in your project in the order in which they are defined. Or, you can specify the dependencies between the files, and let ASDF figure out a linear ordering. The point is that dependencies are explicit, and clearly spelled out.

But, enough proselytizing. The point is that there is no competition to ASDF, not because nobody has bothered to create a competitor, but because ASDF out-competed all the other alternatives years ago. And that's a good thing.


Not applicable.

Future Work:

More ASDF components, e.g. for building C/C++ files. A platform-independent package manager for downloading the external C libraries required by a Lisp library would be amazingly useful.


SLIME is a Common Lisp IDE built on Emacs, and the most widely-used CL IDE. The fact that it's built on Emacs is a problem, as telling a new user they have to learn Emacs before using SLIME (which is not strictly true) is a significant artificial barrier to entry.


Reduce the barrier to entry to using SLIME.

Future Work:

Non-Emacs IDEs can't hurt. An Atom plugin that interfaces with a Swank server, for instance, would be pretty great.


Specific Problems


The number of people building web applications in Common Lisp who don't know about Clack is too high. Obviously, there's a problem in reaching potential users with good library choices.

Choice Paralysis

When someone asks what library to use to write code in a given domain, only the best library in that domain should be recommended. Saying "you also have X, Y and Z" only worsens the paradox of choice.

If someone asks what GUI toolkit to use, answer "CommonQt with Qtools", don't add "but you can also use cl-cffi-gtk or LTK..."

If someone asks what to use to build web applications, link them to one of the frameworks built on Clack. Don't talk about Hunchentoot or Wookie or Woo or some other server.

If someone asks what IDE to use, point them to SLIME. Don't tell them about some obscure abandoned project from 2005 that only runs CLISP.

And, most importantly: when someone asks which implementation to use, just say SBCL or CCL. Don't tell them, "well, you can use ECL to embed Lisp or ABCL to run on the JVM". Those are for more niche users, not new users asking how to get started.


Quicklisp Downloads

Below is the total number of downloads, of the top 100 most popular projects on Quicklisp, between January and July:


I am subscribed to this feed of new Common Lisp repos on GitHub. I wrote some code to query my Newsbeuter database:

(ql:quickload (list :dbi :yason :local-time :group-by))

(defvar *connection*
  (dbi:connect :sqlite3
               :database-name (merge-pathnames #p".newsbeuter/cache.db"

(let* ((output (merge-pathnames #p"lisp-github.json"
       (query (dbi:prepare *connection*
                           "SELECT pubDate FROM rss_item WHERE feedurl = ?"))
       (results (mapcar #'(lambda (result)
                             (getf result :|pubDate|)))
                         (dbi:execute query "")))))
  (with-open-file (stream output
                          :direction :output
                          :if-exists :supersede
                          :if-does-not-exist :create)
     (mapcar #'(lambda (group)
                  (local-time:format-timestring nil
                                                (first group)
                                                :format (list :year #\- :month #\- :day))
                  (1- (length group))))
             (group-by:group-by-repeated results
                                         :keys (list #'identity)
                                         :tests (list #'(lambda (a b)
                                                          (= (local-time:day-of a)
                                                             (local-time:day-of b))))))

From to , a total of repos were created


Thanks to Javier Olaechea for his comments on Unicode support, Eitaro Fukamachi and François-René Rideau, and Gabriel Gonzalez for the original State of the Haskell Ecosystem article.

Joe MarshallPlaying with linear fractional transforms

· 45 days ago
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)))
     (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.

For older items, see the Planet Lisp Archives.

Last updated: 2015-10-07 00:00