Planet Lisp

Michael MalisLoops in Lisp Part 1: Goto

· 3 days ago

At its core, Common Lisp provides two primitives for performing iteration. The first of those primitives is recursion. Recursion is an amazing technique, but in this post I am going to focus on the other primitive – goto.

Goto is extremely powerful. It lets you manipulate the control flow of your program in anyway you can think of. This freedom to do whatever you want is also what makes goto so dangerous. In any given piece of code that uses goto, it is difficult to tell what the purpose of the goto is because it could be used for so many different reasons. Because of this, most languages provide various kinds of builtin loops instead of providing raw goto. Even though loops aren’t as general as goto, they express the intention of the code much more clearly.

As an example, let’s say you want to print all of the characters in a file. If your language provided while loops, you could do this by printing characters from the file one at a time while there are more characters left. If Common Lisp had while loops,1 the code for this procedure would look like this:

(while (peek-char file nil nil)
  (write-char (read-char file)))

If your language only had goto, it becomes much more difficult to implement the procedure. In the end, you have to, in some way, simulate a while loop. One way to code the procedure with just goto is the following. First check if there are any characters left in the file. If there aren’t any, goto the end. Otherwise print the next character and go back to the start. Here is Common Lisp code that implements this:2

  (if (not (peek-char file nil nil))
      (go end))
  (write-char (read-char file))
  (go start)

Not only is the version with goto much more verbose, it is also much harder to understand. The code lacks clarity because goto is so general. It gives you no context into how it is being used. The reader of the code will have to think about the positioning of all of the gotos before they can think about the overall flow of the program. On the other hand, in the version with the while loop, merely the fact that a while loop is being used gives whoever is reading the code a decent idea of the control flow.

In reality all loops are eventually compiled down to gotos. Whenever the compiler for a language that provides loops sees a loop, it generates code that simulates the loop through goto. You can do the same thing with Lisp macros!

If you don’t know, Lisp macros are compile time functions which take code as their input and return code as their output. When Lisp code is being compiled, all of the macros in the code are called and each one is replaced with its result. This means you can write a macro that looks like a while loop when you use it, but at compile time generates code to simulate a while loop through goto. You are in effect adding while loops to the Lisp compiler! Here is code that defines such a macro:

(defmacro while (test &body body)
  (let ((gtop (gensym))
        (gend (gensym)))
       (if (not ,test)
           (go ,gend))
       (go ,gtop)

With this macro, the first code example is now valid lisp code! The while macro takes as arguments a test and a body. It then generates code that uses the method used in the second example to simulate a while loop with goto. You can actually see what the first example looks like after expanding the macro by using the function macroexpand. Here is what the generated code looks like:

  (if (not (peek-char file nil nil))
      (go #:g730))
  (write-char (read-char file))
  (go #:g729)

The generated code is the exact same as the code in the second example except for the names of the labels. This means the two examples are the same functionally! The only real difference between them is that the first one is expressed in terms of loops, and the second one is expressed in terms of goto. Since it is so much easier to think in terms of loops than goto, there is no reason why you wouldn’t use the first example over the second.

Macros allow you to build any feature you want as long as it is possible to simulate that feature through lower level features. With respect to goto, this means you can build any kind of control flow construct you want by simulating it with goto and then putting a macro on top. In Common Lisp, all of the looping constructs (do, do*, dotimes, dolist, loop) are really just macros that expand into goto. This is what Alan Kay meant when he said “Lisp isn’t a language, it’s a building material”. It bears repeating. In Lisp, you can build any feature you want as long as it is possible to simulate that feature in terms of lower level features.

The post Loops in Lisp Part 1: Goto appeared first on Macrology.

drmeisterWhy Common Lisp for Scientific Programming?

· 4 days ago

What makes any language suitable for scientific computing?

The most important goal is translating ideas into fast code and building on other people’s work. We are working on improving Clasp’s ability to generate fast code based on the excellent LLVM library and Clasp can expose C++/C/Fortran libraries to build on the work of others. I’ve programmed in many languages and Common Lisp is the best at expressing ideas. Every language gets translated into an abstract syntax tree on its way to native code, Lisp code is an abstract syntax tree.  There is no programming concept that can’t be expressed compactly in Lisp, this is not true in other languages.  You cannot yet express multiple dispatch functions, dynamic variables or Common Lisp style macros (a few CL features) compactly in R, Fortran, C++, or Python.

Why are R, Fortran, C++, or Python considered suitable for scientific computing?

It is the wrong question – those languages are just the languages that people started using and so they keep using them.  It is not a choice most people make – it is inertia.

I choose Common Lisp.

drmeisterClasp 0.4 - Joining Common Lisp and C++

· 7 days ago

Announcing Clasp 0.4 – a new release that incorporates a brand new compiler – capable of generating 200x faster code than previously, many bug fixes, a more complete Common Lisp implementation, and C++ interoperation.

Get Clasp 0.4 here

New features:

  • Clasp has a completely new, optimizing/inlining compiler called cclasp!
  • Fixnum, character and single-float types are immediate values.
  • General object pointers and cons pointers are tagged for speed.
  • Clbind library allows programmers to expose external C++ libraries.
  • Lots of bug fixes and stability improvements.

What is Clasp?

Clasp is a new Common Lisp implementation that seamlessly interoperates with C++ libraries using LLVM for compilation to native code. This allows Clasp to take advantage of a vast array of preexisting libraries and programs, such as out of the scientific computing ecosystem. Embedding them in a Common Lisp environment allows you to make use of rapid prototyping, incremental development, and other capabilities that make Common Lisp such a powerful language.

Getting Clasp

Get Clasp 0.4 here

Precompiled and prepackaged versions of Clasp will be available for a limited number of distributions. Check the releases to see if there is something available for you.

At the moment, Clasp is supported on Linux and Mac OS X. On these systems, you should be able to build it from source if a pre-made package is not available or workable for you. In case you cannot get it to compile even with the instructions below, the quickest way to get help is to either file an issue, or to chat with us directly.

Building on most systems will take around 4GB of RAM and 2-4 hours with a relatively modern processor.

Acknowledgements (#clasp IRC channel nicknames)

Robert Strandh (beach) – the Cleavir compiler and guidance.

Shinmera – build testing and organization.

stassats – guidance, bug finding and speeding up the compiler.

flash- – feedback and debugging of the clbind library.

SAL9000 – designing list iterator and feedback on ASTMatcher library.

faheem – guidance in setting up the build system.

Common Lisp TipsMaking a directory from a pathname

· 13 days ago

Sometimes I want to create a directory pathname relative to some existing file pathname. For example, when I want to refer to files that are in the same directory as the currently loading file, I might work relative to *load-truename*.

I used to do it like this:

(make-pathname :directory (pathname-directory *load-truename*))

This worked fine for me, but after getting bug reports from Windows users, I’ve changed it to this:

(make-pathname :defaults *load-truename*
               :type nil
               :name nil
               :version nil)

That way all the properties of *load-truename* are carried over, except the name and type.

edit Added :version nil per Fare’s comment.

Michael MalisDefmemo

· 17 days ago

In my last post I talked about memoization i.e. caching the results of a function. Memoization is a fairly common technique for optimization. It is common enough to warrant writing a macro that makes it easy to define memoized functions. When demonstrating memoization, I had a memoized Fibonacci function that looked like this:1

(let ((table (make-hash-table)))
  (defun fib (n)
    (or (gethash n table)
        (setf (gethash n table)
              (if (<= 0 n 1)
                  (+ (fib (- n 1))
                     (fib (- n 2))))))))

There are a couple problems with the above code. One problem is the boilerplate. If you wanted ten different memoized functions, you would have to copy lines 1, 3, and 4 for every single memoized function. Some people like to call programmers who do this needless duplication, “human compilers”, since they are writing code that the compiler should be writing for them.

Another issue with the above code is the lack of abstraction. If you wanted to change the caching mechanism to say, only cache the last hundred values, you would have to change the definition of every single function! Ideally you would only need to modify the code in one place in order to change how the caching is implemented.

Defmemo is one way to solve both of these problems. Here is what the above code would look like if it were were to use defmemo:

(defmemo fib (n)
  (if (<= 0 n 1)
      (+ (fib (- n 1))
         (fib (- n 2)))))

Defmemo solves both of the problems extremely well. It removes all of the differences between the memoized version on the regular version except for having to use “defmemo” instead of “defun”. Defmemo also solves the abstraction problem by moving all of the code relevant to memoization into the body of defmemo. If you want to change how memoization works, all you have to do is change the code for defmemo.

Now for the implementation of defmemo. The implementation is made up of two separate parts. First, a higher order function, memo, which takes a function as an argument, and returns a memoized version of that function. The second part is the actual macro, defmemo. Instead of just defining the function like defun, defmemo first builds a lambda expression for the body. Then it generates code that calls memo on that lambda function. Finally defmemo uses the result of memo as the implementation of the function being defined.2

Here is the code for memo:34

(defun memo (f)
  (let ((cache (make-hash-table :test #'equalp)))
    (lambda (&rest args)
      (or (gethash args cache)
          (setf (gethash args cache)
                (apply f args))))))

Memo works by returning a function that has an internal hash-table. When that function is called, it first checks its hash-table to see if it has been called with the same arguments before. If so, it returns the value it had calculated the first time it was called.5 If it hasn’t been called with the same arguments before, the function will instead call the function that was passed in to memo, and then store the result of that inside the table. This way, if the memoized function is called with the same arguments a second time, it can just look up the result in the table.

Next, for defmemo itself, we need to generate code that takes the body as a lambda expression, passes that lambda function through memo, and uses that as the implementation of the function. One way to set the implementation of a function to be a lambda function is to use setf with symbol-function.6 For example, here is how you could set the implementation of square to be a lambda function that squares its argument:

(setf (symbol-function 'square) (lambda (x) (* x x)))

(square 5) => 25

Based on the paragraph above, here is the code for defmemo:

(defmacro defmemo (name args &body body)
 `(setf (symbol-function ',name) 
        (memo (lambda ,args ,@body))))

Now instead of defining a function with defun, we can define it with defmemo and it will automatically be memoized! Defmemo is a great example of how you can define your own ways to define functions. Many libraries provide similar features in which you use the same syntax as defun, only with a bit of magic thrown in.

The post Defmemo appeared first on Macrology.

Clozure CL BlogClozure CL 1.11 is available

· 21 days ago

Clozure CL 1.11 is now available. Please see for instructions on how to get it.

Didier VernaDeclt 2.0.1 "Benjamin Sisko" is out

· 24 days ago

Declt 2.0.1 "Benjamin Sisko" is out. This is a bugfix release with one internal change (a special variable was not following the earmuffs convention) and one actual bugfix (the same Texinfo anchor was generated for symbols with the same name but in different packages).

Find it at the usual place...

Didier VernaELS 2016 second invited speaker announced!

· 24 days ago

We're happy to announce our second invited speaker for the next European Lisp Symposium (May 9-10 2016, Krakow, Poland). Francis Sergeraert (Institut Fournier, Grenoble, France) will be speaking about lexical closures and complexity. All the details are already on the website...

Quicklisp newsOctober 2015 Quicklisp dist update now available

· 26 days ago
New projects:
  • cl-itertools — itertools Python lib ported to CL — MIT
  • cl-tesseract — CFFI bindings to the Tesseract OCR library. — MIT
  • fast-websocket — Optimized WebSocket protocol parser — BSD 2-Clause
  • lisp-critic — LISP-CRITIC - A Lisp code critiquing package. — MIT Licence
  • redirect-stream — Offers a stream that redirects all actions to an inner stream. — Artistic
  • trivial-ssh — An abstraction layer over cl-libssh2. — MIT
Updated projects: 3d-vectors, archive, binfix, buffalo, calispel, ceramic, chirp, city-hash, cl-ana, cl-async, cl-autowrap, cl-charms, cl-gists, cl-glfw3, cl-gobject-introspection, cl-hamt, cl-jpl-util, cl-launch, cl-liballegro, cl-libyaml, cl-locale, cl-marklogic, cl-messagepack, cl-openstack-client, cl-opsresearch, cl-permutation, cl-quickcheck, cl-readline, cl-redis, cl-riff, cl-scripting, cl-smtp, cl-yaml, clack, clavier, cletris, clfswm, climon, clml, closer-mop, clsql-orm, codata-recommended-values, colliflower,, commonqt, crane, croatoan, crypto-shortcuts, dexador, dissect, djula, docparser, drakma, drakma-async, eazy-gnuplot, eazy-project, esrap, external-program, fare-csv, fare-memoization, fast-http, frpc, gendl, hh-redblack, interface, introspect-environment, jonathan, json-responses, lack, lake, lift, lisp-gflags, lucerne, mathkit, mcclim, mgl-pax, montezuma, more-conditions, ningle, perlre, plump, postmodern, qt-libs, qtools, quri, rutils, s-http-client, scalpl, scriptl, serapeum, simple-tasks, snappy, staple, stumpwm, swank-crew, sxql, trivial-download, trivial-signal, uiop, unix-options, unix-opts, utm, varjo, websocket-driver, woo, xml-emitter.

Removed projects: teepeedee2. Removed because of the way it clobbers the ASDF configuration to load its own alexandria.

Incidentally, October marks the fifth anniversary of the initial release of Quicklisp. Enjoy!

Patrick SteinGrid-Generators v0.4.20151016 (and List-Types v0.4.20151029) Released

· 29 days ago

Two new Common Lisp libraries released: GRID-GENERATORS and LIST-TYPES.


I often find myself wanting to iterate over the points in a rectangular region of a grid in an arbitrary number of dimensions. If my grid is only one-dimensional or two-dimensional then I often just write nested loops to traverse the points of interest.

(loop :for y :from 0 :to 10 :by 1/2
    :do (loop :for x :from 0 :to 10 :by 1/2
             :do (something x y)))

However, when I want the code to be flexible in the number of dimensions, I always end up writing application-specific code to increment arbitrarily long lists of integers with given bounds. I finally got sick of repeating this code every time I needed it and created a library.

For the particular application that I have in mind though, I wanted more than just walking the points inside some rectangular hyper-prism. I wanted to traverse all of the points at a give taxicab distance from a starting point.

The GRID-GENERATORS package facilitates generating points in a rectangular hypergrid, generating points based on taxicab distance, and generating points based upon the number of steps in an arbitrary lattice (given the generators of the fundamental parallelpiped of the lattice). The GRID-ITERATE package provides ITERATE clauses for those generators.

For example, one could iterate over the same points in my nested example above like this:

(loop :with generator := (make-grid-generator '(10 10) :by '(1/2 1/2))
    :for (x y) := (funcall generator)
    :while x
    :do (something x y))

Or, with iterate:

  (iterate:for point on-grid-to '(10 10) by '(1/2 1/2))
  (destructuring-bind (x y) point
     (something x y)))

LIST-TYPES package

The LIST-TYPES package provides a way to generate `SATISFIES` type clauses that ensure that a list contains elements all of the given type. For example, if I wanted to ensure that my list was entirely rational numbers, I could use the declaration:

(check-type my-list (list-types:list-of rational))

Eugene ZaikonnikovSerious Software SpecLisp for Sinclair ZX Spectrum

· 29 days ago

The first computer I owned and learnt the basics of programming on was a Sinclair ZX Spectrum clone. Very modestly specced machine even for its heyday, it nonetheless could run a range of high level languages aside from built-in BASIC. I remember successfully porting backpropagating network code from German C't magazine to HiSoft Pascal, and fumbling around in HiSoft C.

Seirous Software SpecLisp, however, was a bit of enigma. Lisp tutorials were relatively hard to come by in pre-Internet age, and naive tinkering led nowhere.

Booting up

Fast forward to 2015, the days of information abundance, when things like SpecLsp user guide are floating around. The interpreter can be downloaded off the net as well, and ran under a number of free emulators. Let's finally have a look.

The origins of this dialect can be immediately traced to Lisp 1.5, down to the use of plist markers such as PNAME and APVAL, and rather specific (oblist) function, serving the original function of dumping the definitions in memory. As expected, it uses dynamic binding and FUNARG problem is not quite solved. And no QUOTE shortcuts: you have to spell it like you mean it.

Just like Lisp 1.5, it comes from the times predating bike helmets, mandatory seatbelts and interpreter sandboxes. Native function definitions are stored as call addresses via SUBR property of symbol plists. As such it perhaps makes the most concise FFI ever. Here's it issuing a system reset by jumping to 0x0000. I dare you to do that with a modern Lisp!


Being a true Lisp interpreter, it allows one to edit lambda definitions equally trivially:

Modify lambda

Now, it's easy to rationalize how self-modifying code is not really a feature and there's no need for it in the age of macros. But admit it, this is still kind of neat, in its own old school way. Feels just right. Besides, there's no other way to edit the definitions..

Remarkably, SpecLisp is case sensitive and lowercase by deafault, predating Franz bold introduction of that to the world of Common Lisp by 17 years.

Case sensitivity

But perhaps the most surprising part is SpecLisp's graphics extension. The interpreter was probably meant to serve educational purposes (even by 1983 standards, ZX Spectrum was an underwhelming Lisp machine), hence it featured a set of Logo-like turtle control commands.

Let's put it to good use by making a period true graphics demo.

The initialization routine to clear screen and center the pen:

(de prep (a)
  (progn nil
    (fwd 88) (right 90) (fwd 128) (right 270)

A function to render a square of specified size, and another to draw those squares in diminishing size while rotating:

(de square (n)
  (progn nil
    (fwd n) (right 90)
    (fwd n) (right 90)
    (fwd n) (right 90)
    (fwd n) (right 90)))

(de rotate (a n c)
  (while (greaterp n 0)
    (right a)
    (square n)
    (setq n (diff n c))))

In case you wondered, the opening nil in progn is the empty bindings list: the construct doubles as impromptu let.

Diminishing squares

Didier VernaELS 2016 first invited speaker announced!

· 39 days ago

We're happy to announce our first invited speaker for the next European Lisp Symposium (May 9-10 2016, Krakow, Poland). Pierre Castéran (University of Bordeaux, France) will be speaking about program proof and synthesis with Coq. All the details are already on the website...

Nick LevineCons Conflict Resolved

· 41 days ago

Didier VernaIn Cooperation with: ACM SIGPLAN for ELS

· 45 days ago

We're happy to announce that the European Lisp Symposium is now "In Cooperation with: ACM SIGPLAN". The proceedings will be published in the ACM Digital Library.

Michael MalisOr=

· 45 days ago

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

There are many cases where caching the results of a function (also called memoization), make a function much more efficient. For example a function that calculates the Fibonacci numbers:

(defun fib (n)
  (if (<= 0 n 1)
      (+ (fib (- n 1))
         (fib (- n 2)))))

If you try running fib on different values, you will notice that around 35 or so, it starts to take quite a long time to run. The problem is that fib calculates the smaller Fibonacci numbers many more times than it needs to. When calculating the 35th Fibonacci number, the second Fibonacci number is calculated a total of 5702887 times.1

This is where memoization comes in. If the above function were memoized, it would only need to calculate each Fibonacci number once. Then, whenever fib is asked to calculate a number it has already calculated, it can just look up the result in the table. Here is what the above code would look like if it were to take advantage of memoization:

(let ((table (make-hash-table)))
  (defun fib (n)
    (or (gethash n table)
        (setf (gethash n table)
              (if (<= 0 n 1)
                  (+ (fib (- n 1))
                     (fib (- n 2))))))))

With the memoized version, you will hit a stack overflow before you find a value that takes more than a moment to calculate. The problem with the above implementation is that it has some duplicate code. There are two calls made to gethash. The first call checks to see if the value has already been calculated. If not, fib calculates the value manually, and then uses the second call to store it into the table. The fact that the gethash call is repeated may not seem like a problem, but when the expression for the place is more complicated, it can become a much bigger deal.

Or= is a macro that fixes this problem. It does so by first checking whether its first argument, which should be a place, has a non-nil value.2 If it does, or= will just return that value. Otherwise it evaluates its remaining arguments until one of them evaluates to a non-nil value. Or= will then write the value of that expression into the place designated by the first argument. Here is the above code rewritten to use or=.

(let ((table (make-hash-table)))
  (defun fib (n)
    (or= (gethash n table)
         (if (<= 0 n 1)
             (+ (fib (- n 1))
                (fib (- n 2)))))))

The implementation of or= looks very similar to the incf ‘template’3 that is used when writing a macro that works with places. Here is the implementation of or=:

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

This time, the value being stored to the place is the or of the place and whatever other arguments are passed in. Since or evaluates its arguments lazily, we get the desired behavior of or= – evaluate the expression (and store the result) only if the place doesn’t have a value already. One problem with or= is that it determines if a value has already been stored in the place by testing if the value is non-nil. This can lead to a problem if the value stored in the place is actually nil! As an exercise, try writing a version of or= that takes advantage of the multiple values returned by gethash in order to properly handle nil.

In my next post, I am going to continue with the memoization example and demonstrate how to write a macro defmemo, which makes it easy to define memoized functions.

The post Or= appeared first on Macrology.

Didier VernaASDF-FLV 2.0

· 47 days ago

I've just released version 2.0 of ASDF-FLV, my ASDF extension for supporting file-local variables (ala *PACKAGE*). The code hasn't changed, but as for my other libraries, the system and package names are now prefixed with net.didierverna. ASDF-FLV is also available on GitHub now.

The reason I'm doing this now is that at least two of my other libraries are going to use it in a mandatory way, either directly or indirectly (and in turn, that's because no implementation has bothered to implement CDR #9 yet ;-).

Didier VernaELS 2016 Call for Papers

· 52 days 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
  François-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

· 53 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!

· 54 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

· 59 days ago

Michael MalisZap

· 59 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

· 63 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

· 65 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

· 66 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

· 69 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

· 70 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

· 70 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

· 72 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

· 73 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

· 75 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.

For older items, see the Planet Lisp Archives.

Last updated: 2015-11-24 16:00