Planet Lisp

Patrick SteinThe Less You Know (An Unspoken Tenet of Clean Architecture)

· 6 hours ago

In response to my previous article, Holger Schauer asked why I implemented the use-cases with classes rather than having the book repository passed into the browse-books method or putting it into the abstract base-class browse-books-use-case rather than in the implementation.

(defstruct browse-books-request
  book-repository)

(defgeneric browse-books (request response))

;; -- or --

(defgeneric browse-books (book-repository request response)

;; -- or --

(defclass browse-books-use-case ()
  ((book-repository :initarg :book-repository :reader book-repository)))

I started to reply, but I found that I was having trouble keeping my response to a reasonable length. So, here, you are subjected to my unreasonably long response.

For reference, here is the repository from the previous post.

Java’s Influence

I chose to model the use-cases as classes to be faithful to all of the implementations that I’ve seen of Clean Architecture. Uncle Bob, in particular, does most of his videos and talks using Java or Ruby. When he uses Ruby, he still tends to use the same OO organization that he would use if he were writing Java.

One aspect of Java is that everything has to be a method on some class. If you want to declare a method somewhere but have its implementation somewhere else, you can do this with an abstract base class or an interface. You cannot, for example, declare an abstract static method as you can in CLOS (or even C).

Java’s single-inheritance makes it very awkward in general to use abstract base classes. If the book-repository slot were on the browse-books-use-case rather than on the implementation, this would have to be an abstract base-class and direct inheritance if it were in Java. If the book-repository slot is on the implementation rather than on the browse-books-use-case, then someone writing this in Java could use an interface and an implementation of that interface.

I wrote this blog post using Lisp/CLOS. However, for the actual project that I am working on, I have opted to use PHP. PHP shares Java’s inheritance restrictions. A class can only have one superclass but it can implement any number of interfaces.

The Stated Advantages of Clean Architecture

When Uncle Bob talks about why to use Clean Architecture, he tends to focus on these things:

  • Ability to defer decisions about the frontend and backend
  • Ability to test the core logic of the application easily
  • Ability to deploy your application in pieces

The adapters depend on interfaces defined in the application. The application does not depend on anything defined by the frontend or the backend. As such, deciding which frameworks to use on the frontend or which database to use on the backend can be deferred for a long time during the development process. Uncle Bob often describes how on FitNesse they developed using the filesystem as the database backend fully intending to plug in a relational database later in the project. In the end, they decided that the filesystem backend they had created served their purposes just fine. When they came upon a client who had requirements that all of the dynamic content be stored in their corporate database, they rewrote an adapter for that customer to use the database rather than the filesystem.

Clean Architecture applications are easy to test because the application code isn’t interwoven with the presentation code or the database code. One can create mocks (even test-specific mocks) for the repositories and front-ends that do whatever the test needs to have done. They can do it quickly, without temporary databases or network overhead.

In a Clean Architecture deployment of my application in Java, I might have one JAR file for the book repository implementation, one JAR file for the Console frontend, one JAR file for the application core logic, and one JAR file that wires all of those other pieces together on startup. If I need to incorporate a different database, then I only need to update the book repository implementation JAR and (maybe) the JAR file that wires the pieces together. I don’t have to redeploy my entire application every time the database changes. I don’t have to retest every bit of application logic. Everything is nicely contained.

An Unspoken Benefit of Clean Architecture

One of the ways that Clean Architecture keeps its dependencies in check is by making all of the interfaces going into or out of your application use primitive types or dumb structures for parameter passing. The unspoken benefit of this is that it encourages you to keep the interfaces as spartan as possible.

If the controller (the console in my sample application) that is invoking the use case doesn’t absolutely need to know there is a book repository involved, then it shouldn’t know about it. The book repository cannot be passed from the controller to the use case using primitive types and dumb structures.

The controller’s job is to take input from the user, turn it into a request, invoke the use case with that request, and present the response back to the user. There is no input that the controller can get from the user which will allow it to instantiate a book repository. It could, of course, pull it from global state as it pulled the use case. However, the less it needs to know, the better.

This separation has other benefits, as well. In Lisp, especially, one could imagine interacting with the application through the REPL. So, rather than implementing the simple REPL that I did with my console, I could have made a browse function that invokes the use-case and returns the results.

(defun browse ()
  (let ((request (make-browse-books-request))
        (response (make-browse-books-response)))
    (browse-books *browse-books-use-case* request response)
    (mapcar #'book-summary-to-plist
            (browse-books-response-list-of-book-summaries response))))

If everything is going to happen within my one Lisp image, then it would be fine to keep a *book-repository* global to pass into the use case. However, if I want to share the book repository between multiple users, each at their own REPL, then it no longer makes sense that each REPL would need a handle to the book repository.

Remote Proxy class-diagram

My browse function doesn’t need to know whether the use case it is interacting with is the actual implementation or just a proxy for the implementation. In the client-server case, it makes little sense for the client to have any idea that there is a book repository instance.

I suppose there are some classes of application where one might want to work on a remote repository but keep the application logic local. If that were the case, then one would want the book repository to be the interface which has the proxy and server. However, nothing in the architecture mentioned in the previous post precludes that use. If we had put the book repository into the interface for the use case rather than in its implementation, then we need to at least pretend there is a book repository on the local client even when everything is going to happen on the server.

Conclusion

An accidental benefit of Clean Architecture’s insistence on primitive or dumb-struct parameters to use-cases is that the parameters end up only reflecting the minimal amount of information that is specific to the current request. Any state that is common across requests is a part of the internal state of the use-case.

Because of this, code that is interacting with the use case only to know the little bit that makes them different from other people using the use case. This results in very simple interfaces to the use case and the a great deal of flexibility in implementation.

Patrick SteinExploring Clean Architecture

· 3 days ago

This is the first in what will likely be a series of blog posts about Clean Architecture. Uncle Bob Martin has written numerous blog posts and given lots of talks about it.

The goal of Clean Architecture is to have the directory structure of your application shout out what your application does rather than what framework was used to present your application or what database is nestled in the depths of your application. Your program is divided into Entities, Use Cases, and Interface Adapters.

Entities encapsulate “Enterprise-wide business rules.” Use Cases encapsulate “Application-specific business rules.” Interfaces and Adapters represent how your Use Cases want to interact with the outside world (e.g. databases, users, printers, etc.).

In Clean Architecture, the Entities cannot know that the Use Cases exist and the Use Cases cannot know anything about the Adapters except for the Interface to them which is defined by the Use Case rather than by the Adapter. The Use Case does not know whether the application is being used from the command-line or from the web or from a remote service calling into it. The Use Case does not know whether the data is being stored in the file system or in a relational database (or conjured from the ether as needed). Nothing in the Adapters can know anything about the Entities.

Simple Example

I have a project that I am just starting. I thought I would use this new project to see how Clean Architecture works for me.

There are large number of talks and videos about Clean Architecture. However, there are not many examples of it despite several years of Stack Overflow questions and blog posts asking for examples.

There are a few simple examples around the web. The most notable is Mark Paluch’s Clean Architecture Example. It is just big enough to get a sense of how things hang together. If you’re willing to put up with Java’s insane directory hierarchies, you can get a pretty good idea of what the application does just by poking around the Use Cases directory.

My First Use Case

My first Use Case is to let the User browse a list of Book Summaries. The User should be able to sort by Title, Author, Publication Date, or Date the Book was acquired. The User should be able to filter the list based upon Genre or Keyword. The Use Case should allow the caller to implement pagination, so the Use Case needs to support returning up to a given number of Book Summaries starting with a specific number.

Some might argue that that is multiple Use Cases glommed together. If that were the case, then I would need some way to pipeline together Use Cases if I’m going to make any sort of reasonably navigable app atop my Use Cases.

But, let’s start with baby steps.

The Simplified Version of my First Use Case

Let’s just say the User wishes to see a list of all of the Book Summaries. The User is fine with seeing all of them at once in whatever order my app sees fit.

This simple version of the Use Case is implemented in an accompanying repository under the tag the-dream.

Class Diagram (explained below)

The architecture consists of some simple structures with no “business logic” in them at all: book-summary and book.

(defstruct book-summary
  isbn
  title
  author
  cover-page-thumbnail)

(defstruct book
  isbn
  title
  author
  cover-page-thumbnail
  cover-page-fullsize
  list-of-thumbnails
  table-of-contents
  synopsis
  publication-date
  list-of-genres
  list-of-keywords)

There is one use case browse-books which defines the use-case interface browse-books-use-case along with its input structure browse-books-request and its output structure browse-books-response. The use case defines the method browse-books which must be called with a browse-books-use-case instance, a browse-books-request instance, and browse-books-response instance.

(defstruct browse-books-request)

(defstruct browse-books-response
  list-of-book-summaries)

(defclass browse-books-use-case ()
  ())

(defgeneric browse-books (use-case request response))

In my implementation, the browse-books-response is a simple data structure. One could easily imagine that the browse-books method would return one rather than filling one in that was passed to it. In some variants of Clean Architecture (like the Paluch example cited above), the response model is a class instance upon which a method is called to complete the interaction. But, it would have to be clear from the outset that anyone using this Use Case cannot depend on it being synchronous or asynchronous.

The use case also defines the book-repository interface that it needs.

(defclass book-repository ()
  ())

(defgeneric find-book-by-isbn (book-repository isbn))
(defgeneric all-books (book-repository))

In the Paluch example, all of the use cases share the same repository interfaces (though Paluch and others have separate repository interfaces for Users and Invoices and Items). In several of Uncle Bob’s videos, he makes the claim (or claims equivalent to the claim) that each use case should define an interface for just the methods it needs to use on a Book repository. In this use case, it would need only the ability to retrieve the list of Books and so I should not have defined find-book-by-isbn here at all, and I should have named this interface browse-books-book-repository.

I wrote browse-books-impl class which extends the browse-book-use-case. It takes an instance of book-repository on construction.

(defclass browse-books-impl (browse-books-use-case)
  ((book-repository :initarg :book-repository :reader book-repository)))

(defun make-browse-books-use-case (book-repository)
  (check-type book-repository book-repository)
  (make-instance 'browse-books-impl :book-repository book-repository))

It uses that to retrieve the list of Books. Then, it creates a book-summary from each book instance retrieved from the book-repository.

(defun summarize-book (book)
  (check-type book book)
  (make-book-summary :isbn (book-isbn book)
                     :title (book-title book)
                     :author (book-author book)
                     :cover-page-thumbnail (book-cover-page-thumbnail book)))

(defmethod browse-books ((use-case browse-books-impl)
                         (request browse-books-request)
                         (response browse-books-response))
  (let* ((books (all-books (book-repository use-case)))
         (summaries (mapcar #'summarize-book books)))
    (setf (browse-books-response-list-of-book-summaries response) summaries))
  response)

To test the design so far, I wrote in-memory-book-repository backend which implements the book-repository interface that was defined in the Use Case.

(defclass in-memory-book-repository (book-repository)
  ((books :initarg :books :reader books)))

(defun make-in-memory-book-repository (books)
  (check-type books list)
  (assert (every #'book-p books))
  (make-instance 'in-memory-book-repository :books books))

(defmethod all-books ((book-repository in-memory-book-repository))
  (mapcar #'copy-book (books book-repository)))

I also wrote a console frontend which invokes the browse-books-use-case.

(defun console-browse-books ()
  (let ((request (make-browse-books-request))
        (response (make-browse-books-response)))
    (browse-books *browse-books-use-case* request response)
    (mapcar #'console-print-summary
            (browse-books-response-list-of-book-summaries response))
    (values)))

...

(defun console-main-loop ()
  (catch 'console-quit
    (with-standard-io-syntax
      (loop
         :do (mapc #'console-print
                   (multiple-value-list
                      (console-eval (console-read))))))))

To tie it all together, I wrote app-context which holds the current browse-books instance.

(defvar *browse-books-use-case*)

And, I wrote the app which creates an instance of the in-memory-book-repository and creates the browse-books-impl for the app-context. Then, it runs the main loop of the console frontend.

(defun run-console-app-with-memory-db (&optional (books *book-list*))
  (let* ((book-repo (make-in-memory-book-repository books))
         (*browse-books-use-case* (make-browse-books-use-case book-repo)))
    (console-main-loop)))

Trouble In Paradise

Already, in this simple interface, I am torn. For this Use Case, I do not need the repository to return me the list of Books. I could, instead, ask the repository to return me the list of Book Summaries. If I do that, my application is just a fig-leaf over the repository.

(defgeneric all-book-summaries (book-repository))

Well, the argument against asking the repository for Book Summaries is that it should not be up to the database to decide how I would like to have my Books summarized. That certainly seems like it should be “business logic” and probably “application specific” business logic at that.

So, fine. I will have the repository return Books and the Use Case will summarize them.

Now, let me extend the Use Case the next little bit forward. What if I want to support pagination? My choices are to push the pagination down to the repository so that I can ask it to give me up to 20 Books starting with the 40th Book. Or, I can let the repository give me all of the books and do the pagination in the Use Case.

(defstruct browse-books-request
   start max-results)

Here, I can find no guidance in any of the Clean Architecture videos that I have watched nor in the examples that I have found online. Everyone seems happy with the repositories being able to return one item given that item’s unique identifier or return all of the items.

If the repository is going to return all of the Books, then why wouldn’t my Use Case just return them all and leave the caller to do any pagination that is needed?

This works fine when there are a few dozen books and they are small. It does not scale, and I don’t know how it is supposed to scale without pushing most of the responsibility onto the repository.

(defgeneric all-books-in-range (book-repository start max-results))

Sure, I can push the responsibility onto the repository. But, one of the reasons that Clean Architecture is so structured is to allow easy testing of all of the application logic. The more that I push into the repository, the less that I actually exercise when I run my unit tests with my mock repository (and the more complex my mock repository should probably be).

One possible approach would be to have the all-books method instead be all-isbns. Then, I can retrieve all of the ISBNs and use find-book-by-isbn to get all of the books.

Now, if I want to sort by Author then by Title, I need to:

  • fetch all of the ISBNs all-isbns,
  • fetch each ISBN’s title,
  • sort my ISBNs by title,
  • fetch each ISBN’s author,
  • stable-sort my ISBNs by author,
  • clip to my range,
  • fetch each book in my range,
  • summarize each fetched book

Or, I have to write an SQL query, that can do all of that in one database call instead of 2N + R + 1 calls (where N is the number of books in the database and R is the number of books in my range), making my Use Case a fig-leaf again.

Zach BeaneLisp and WebAssembly

· 3 days ago

Douglas Crosher, who did lots of work on CMUCL and created the commercial Scieneer Common Lisp, has been trying to make WebAssembly friendlier to Lisp. It hasn’t been easy. Even minor changes are getting pushed back. See his email to SBCL-devel for some of the details, and how to help.

Luís Oliveiraslime-macrostep

· 5 days ago
SLIME's just got a new contrib called slime-macrostep, courtesy of Jon Oddie who also wrote the underlying macrostep package.

And what is slime-macrostep? It's an interactive inline macro-expander. Have a look:


In this quick demo, using a CFFI example, I start by expanding the top-level WITH-FOREIGN-OBJECT form, then I expand the WITH-ALIEN form, but regret it and collapse it back. Then I proceed to expand everything else, including compiler macros!

A nice feature of slime-macrostep is that the expansions are annotated to show which forms are further expandable and macrostep-expand will jump automatically to the next expandable form. That's what makes it a stepper: pressing e repeadly will step through the macroexpansion. Plus, it expands macrolets!

If you'd like to try it out, please grab SLIME's bleeding edge (via MELPA or Git). It's enabled by default if you use the slime-fancy meta contrib. Feedback is most welcome.

Joe MarshallRace results are in

· 8 days ago
Some people wanted to compare machines, so here is the exact code I used and some sample values I got from running it on my laptop. I'm curious what values other people get.
;;; -*- Mode: scheme; coding:us-ascii -*-

;;; This is code for MIT/GNU Scheme.  We attempt to measure the speed of ASSQ.
;;; The code avoids obvious abstractions because we don't want to
;;; measure the speed of function calling.

;; Inline the standard scheme primitives.
(declare (usual-integrations))

;; We change the size and alignment of the heap by consing a small
;; data structure to this list.
(define *change-heap-size-and-alignment* '())

;;; Creates a test alist that looks like this:
;;; ((13 . "13")
;;;  (23 . "23")
;;;  (25 . "25")
;;;  (18 . "18")
;;;  (0 . "0")
;;;  (19 . "19")
;;;  (5 . "5")
;;;  (4 . "4")
;;;  (6 . "6")
;;;    ...
;;; 
(define (make-test-alist n-elements)
  (let ((alist 
         (fold-left (lambda (alist number)
                      (alist-cons number (number->string number)
                                  alist))
                    '()
                    ;; shuffle the numbers from 1 to n
                    (map car
                         (sort   
                          (map (lambda (n)
                                 (cons n (random 1.0)))
                               (iota n-elements))
                          (lambda (l r) (< (cdr l) (cdr r))))))))
    (gc-flip)
    (set! *change-heap-size-and-alignment* 
          (cons (vector #f) *change-heap-size-and-alignment*))
    alist))

;;; Creates an alist of <size> entries and then measures the time to
;;; perform n-lookups on it.  Specialized to fixnum-only arithmetic.

(define (time-alist size n-lookups)
  (let ((test-alist (make-test-alist size)))
    (show-time
     (lambda ()
       (do ((i   0 (fix:+ i 1))
            (idx 0 (if (fix:> idx size)
                       0
                       (fix:+ idx 1)))
            (answer '() (assq idx test-alist)))
           ((fix:>= i n-lookups) answer))))))
Here's a sample run on my laptop. We make an alist with 10 elements and call ASSQ 100,000,000 times on it, fetching each entry about the same number of times.
1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-alist 10 100000000))

;process time: 2260 (2260 RUN + 0 GC); real time: 2259
;process time: 2260 (2260 RUN + 0 GC); real time: 2265
;process time: 2290 (2290 RUN + 0 GC); real time: 2291
;process time: 2250 (2250 RUN + 0 GC); real time: 2247
;process time: 2260 (2260 RUN + 0 GC); real time: 2259
;process time: 2240 (2240 RUN + 0 GC); real time: 2240
;process time: 2240 (2240 RUN + 0 GC); real time: 2243
;process time: 2250 (2250 RUN + 0 GC); real time: 2258
;process time: 2240 (2240 RUN + 0 GC); real time: 2247
;process time: 2250 (2250 RUN + 0 GC); real time: 2250
Process time is reported in milliseconds, so it took about 2.26 seconds to do 100,000,000 million lookups. This divides out to .0000000225 seconds = 22.5 nanoseconds per lookup.

It should be about linear with the size of the list, so we'd expect a 100 element list to take somewhere around 225 nanoseconds.

1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-alist 100 100000000))

;process time: 20720 (20720 RUN + 0 GC); real time: 20753
;process time: 20700 (20700 RUN + 0 GC); real time: 20733
;process time: 20640 (20640 RUN + 0 GC); real time: 20671
;process time: 20690 (20690 RUN + 0 GC); real time: 20695
;process time: 20670 (20670 RUN + 0 GC); real time: 20690
;process time: 21010 (21010 RUN + 0 GC); real time: 21026
;process time: 20800 (20800 RUN + 0 GC); real time: 20832
;process time: 20760 (20760 RUN + 0 GC); real time: 20747
;process time: 20710 (20710 RUN + 0 GC); real time: 20702
;process time: 20690 (20690 RUN + 0 GC); real time: 20700
;Value: #t
Testing a hash table:
(define (make-test-hash-table n-entries)
  (alist->hash-table (make-test-alist n-entries)))

;;; Creates a hash-table of <size> entries and then measures the time to
;;; perform n-lookups on it.  Specialized to fixnum-only arithmetic.

(define (time-hash-table size n-lookups)
  (let ((test-hash-table (make-test-hash-table size)))
    (show-time
     (lambda ()
       (do ((i   0 (fix:+ i 1))
            (idx 0 (if (fix:> idx size)
                       0
                       (fix:+ idx 1)))
            (answer '() (hash-table/get test-hash-table idx #f)))
           ((fix:>= i n-lookups) answer))))))
Put 10 elements or a thousand in a hash table, it takes a constant amount of time to look things up:
1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-hash-table 10 100000000))

;process time: 8320 (8320 RUN + 0 GC); real time: 8321
;process time: 8300 (8300 RUN + 0 GC); real time: 8304
;process time: 8420 (8420 RUN + 0 GC); real time: 8419
;process time: 8280 (8280 RUN + 0 GC); real time: 8304
;process time: 8380 (8380 RUN + 0 GC); real time: 8387
;process time: 8280 (8280 RUN + 0 GC); real time: 8288
;process time: 8320 (8320 RUN + 0 GC); real time: 8311
;process time: 8330 (8330 RUN + 0 GC); real time: 8327
;process time: 8290 (8290 RUN + 0 GC); real time: 8290
;process time: 8310 (8310 RUN + 0 GC); real time: 8307
;Value: #t

1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-hash-table 1000 100000000))

;process time: 8400 (8400 RUN + 0 GC); real time: 8403
;process time: 8550 (8550 RUN + 0 GC); real time: 8553
;process time: 8620 (8620 RUN + 0 GC); real time: 8639
;process time: 8420 (8420 RUN + 0 GC); real time: 8435
;process time: 8400 (8400 RUN + 0 GC); real time: 8425
;process time: 8460 (8460 RUN + 0 GC); real time: 8455
;process time: 8460 (8460 RUN + 0 GC); real time: 8459
;process time: 8480 (8480 RUN + 0 GC); real time: 8486
;process time: 8500 (8500 RUN + 0 GC); real time: 8502
;process time: 8520 (8520 RUN + 0 GC); real time: 8518
;Value: #t

Testing an rb-tree:
(define (make-test-rb-tree n-entries)
  (alist->rb-tree (make-test-alist n-entries) fix:= fix:<))

;;; Creates a rb-tree of <size> entries and then measures the time to
;;; perform n-lookups on it.  Specialized to fixnum-only arithmetic.

(define (time-rb-tree size n-lookups)
  (let ((test-rb-tree (make-test-rb-tree size)))
    (show-time
     (lambda ()
       (do ((i   0 (fix:+ i 1))
            (idx 0 (if (fix:> idx size)
                       0
                       (fix:+ idx 1)))
            (answer '() (rb-tree/lookup test-rb-tree idx #f)))
           ((fix:>= i n-lookups) answer))))))

1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-rb-tree 10 100000000))

;process time: 3910 (3910 RUN + 0 GC); real time: 3908
;process time: 3810 (3810 RUN + 0 GC); real time: 3805
;process time: 4090 (4090 RUN + 0 GC); real time: 4090
;process time: 3970 (3970 RUN + 0 GC); real time: 3967
;process time: 4060 (4060 RUN + 0 GC); real time: 4051
;process time: 3980 (3980 RUN + 0 GC); real time: 3979
;process time: 4040 (4040 RUN + 0 GC); real time: 4040
;process time: 4090 (4090 RUN + 0 GC); real time: 4094
;process time: 3810 (3810 RUN + 0 GC); real time: 3810
;process time: 4090 (4090 RUN + 0 GC); real time: 4092
;Value: #t

1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-rb-tree 100 100000000))

;process time: 7700 (7700 RUN + 0 GC); real time: 7720
;process time: 7760 (7760 RUN + 0 GC); real time: 7767
;process time: 7700 (7700 RUN + 0 GC); real time: 7710
;process time: 7890 (7890 RUN + 0 GC); real time: 7893
;process time: 7920 (7920 RUN + 0 GC); real time: 7914
;process time: 7650 (7650 RUN + 0 GC); real time: 7646
;process time: 7740 (7740 RUN + 0 GC); real time: 7738
;process time: 7760 (7760 RUN + 0 GC); real time: 7761
;process time: 7670 (7670 RUN + 0 GC); real time: 7671
;process time: 8140 (8140 RUN + 0 GC); real time: 8136
;Value: #t

1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-rb-tree 1000 100000000))

;process time: 13130 (13130 RUN + 0 GC); real time: 13124
;process time: 13160 (13160 RUN + 0 GC); real time: 13153
;process time: 13150 (13150 RUN + 0 GC); real time: 13149
;process time: 13140 (13140 RUN + 0 GC); real time: 13140
;process time: 13310 (13310 RUN + 0 GC); real time: 13304
;process time: 13170 (13170 RUN + 0 GC); real time: 13172
;process time: 13140 (13140 RUN + 0 GC); real time: 13167
;process time: 13250 (13250 RUN + 0 GC); real time: 13238
;process time: 13300 (13300 RUN + 0 GC); real time: 13318
;process time: 13420 (13420 RUN + 0 GC); real time: 13416
;Value: #t
And wt-trees while we're at it:
(define (make-test-wt-tree n-elements)
  (alist->wt-tree number-wt-type (make-test-alist n-elements)))

(define (time-wt-tree size n-lookups)
  (let ((test-wt-tree (make-test-wt-tree size)))
    (show-time
     (lambda ()
       (do ((i   0 (fix:+ i 1))
            (idx 0 (if (fix:> idx size)
                       0
                       (fix:+ idx 1)))
            (answer '() (wt-tree/lookup test-wt-tree idx #f)))
           ((fix:>= i n-lookups) answer))))))
1 ]=> (do ((i 0 (+ i 1))) ((not (< i 10))) (time-wt-tree 100 100000000))

;process time: 6400 (6400 RUN + 0 GC); real time: 6397
;process time: 6740 (6740 RUN + 0 GC); real time: 6736
;process time: 6760 (6760 RUN + 0 GC); real time: 6763
;process time: 6070 (6070 RUN + 0 GC); real time: 6068
;process time: 6450 (6450 RUN + 0 GC); real time: 6461
;process time: 6800 (6800 RUN + 0 GC); real time: 6812
;process time: 6330 (6330 RUN + 0 GC); real time: 6346
;process time: 6060 (6060 RUN + 0 GC); real time: 6066
;process time: 6050 (6050 RUN + 0 GC); real time: 6039
;process time: 6300 (6300 RUN + 0 GC); real time: 6303
;Value: #t

Joe MarshallAlist vs. hash-table

· 9 days ago
An alist is a simple data structure that holds key-value pairs in a linked list. When a key is looked up, the list is searched to find it. The time it takes is proportional to the length of the list, or the number of entries.

A hash-table is a more complex data structure that holds key-value pairs in a set of "hash buckets". When a key is looked up, it is first "hashed" to find the correct bucket, then that bucket is searched for the entry. The time it takes depends on a number of things, the hash algorithm, the number of buckets, the number of entries in the bucket, etc. A hash-table can be faster than an alist because the hashing step is quick and the subsequent search step will have very few entries to search.

In theory, an alist takes time proportional to the number of entries, but a hash-table takes constant time independent of the number of entries. Let's find out if this is true for MIT/GNU Scheme.

I wrote a little program that measures how long it takes to look things up in an alist vs. a hash table. Here's what I measured:
It does indeed seem that alists are linear and hash tables are constant in lookup time. But the hashing step of a hash table does take time, so short alists end up being faster that hash tables. The breakeven point looks like a tad over 25 elements. So if you expect 25 or fewer entries, an alist will perform better than a hash table. (Of course different implementations will have different break even points.)

A tree data structure is slightly more complex than an alist, but simpler than a hash table. Looking up an entry in a tree takes time proportional to the logarithm of the number of entries. The logarithm function grows quite slowly, so a tree performs pretty well over a very large range of entries. A tree is slower than an alist until you have about 15 entries. At this point, the linear search of an alist cannot compete with the logarithmic search of a tree. The time it takes to search a tree grows, but quite slowly. It takes more than 100 entries before a tree becomes as slow as a hash table.
With a big enough tree, the growth is so slow that you can pretend it is constant.

drmeisterImproving the Clasp programming experience

· 9 days ago

I’ve been working quietly to improve the Clasp programming experience by implementing a C++ scraper for Clasp that extracts all information from the C++ code required to expose that code to Common Lisp.

This means functions, classes, methods, symbols, enums and initialization functions are identified by the scraper and code is automatically generated to expose these entities to the Common Lisp programming environment.  This replaces thousands of calls that were hand coded by me and were called at startup to expose C++ functionality to Common Lisp with automatically generated code.  To expose a C++ function now all you do is some variation on this:

namespace ext {
CL_LAMBDA(x y &optional (z 0));
CL_DOCSTRING(R”doc(* Arguments
– x :: A fixnum
– y :: A fixnum
– z :: A fixnum
* Description
Add up to three fixnums together as long as they fit into an int.
If they don’t, an error will be signaled.)doc”);
CL_DEFUN int add_numbers(int x, int y, int z) {
return x + y;
}

The CL_LAMBDA(…), CL_DOCSTRING(…), and CL_DEFUN tags are read from the C++ source code by the scraper and code is generated to enable things like (ext:add-numbers 4 5) to be called from Common Lisp.  Above is a complicated example using the optional CL_LAMBDA(…) and CL_DOCSTRING(…) macros – something as simple as below is all that is necessary to bind the C++ function to the ext:add-two-numbers symbol:

CL_DEFUN int ext__add_two_numbers(int x, int y) {return x+y;}

The C-preprocessor is run on all of the source code with macros defined for tags like CL_DEFUN, CL_DEFMETHOD, CL_DOCSTRING(…), LISP_CLASS(…) etc. prior to the scraper searching for the tags. The scraper then generates code that is run at startup to expose everything. The scraper is run every time Clasp is built but it’s smart about only rebuilding generated code that needs to be rebuilt.

There are several benefits to this: (1) adding functions, classes, methods etc. to Clasp Common Lisp is easier now because you just add the entity and there are no more worries about where to add the call at startup to expose the entity. (2) The scraper builds a database of source location for all of these entities. So now, from Slime you can hit M-. on a Clasp symbol and emacs will jump to the source in the C++ source or Common Lisp source – wherever it is defined.

At the same time I’ve added code to extract and generate lambda-lists and docstrings for C++ functions and methods and they are also available now within the Common Lisp environment.

The scraper is written in standard Common Lisp and sbcl has been added as a build dependency for Clasp. The python scrapers Clasp used up to this point have all been retired and python is no longer a dependency for Clasp.


Joe MarshallLatest amusement

· 11 days ago
Here's a procedure that CDRs down a list until it hits the end:
(define (last-cdr list)
  (let loop ((tail list))
    (if (pair? tail)
        (loop (cdr tail))
        tail)))
The inner loop of the procedure compiles to this:
loop-3:
 (cmp q (r 7) (@r 6))         ;; Interrupt check
 (jge (@pcr interrupt-12))

 (mov q (r 0) (@r 4))         ;; Fetch 'tail'

 (mov q (r 1) (r 0))          ;; Extract the tag
 (shr q (r 1) (&u; #x3a))

 (cmp b (r 1) (&u; 1))         ;; Check for pair?, jump if not
 (jne (@pcr label-14))

 (and q (r 0) (r 5))          ;; Mask the tag

 (mov q (r 1) (@ro 0 8))      ;; Fetch the CDR

 (mov q (@r 4) (r 1))         ;; Assign 'tail'

 (jmp (@pcr loop-3))          ;; Do it again.
On my laptop, each iteration of this loop takes a few nanoseconds.

I noticed that there seems to be a lot more going on than CDRing down a list. The interrupt check is responsible for a lot of the overhead. MIT/GNU Scheme polls for interrupts. The compiler inserts an interrupt check at every procedure entry and backwards branch. This ensures that only a small, bounded number of instructions can run between interrupt polls. The interrupt poll and the heap check are simultaneous because of a hack. To interrupt Scheme, you save the "Top of Heap" pointer and set it to zero. This causes the heap check to fail as if there were an out of memory condition. The out of memory handler first checks to see if this was actually an interrupt masquerading as an out of memory, and restores the heap pointer if so.

The two instructions,

(cmp q (r 7) (@r 6))         ;; Interrupt check
 (jge (@pcr interrupt-12))
perform the check. The first compares register 7 with the contents of memory that register 6 points at. The convention for the compiler is that register 7 contains the free pointer and register 6 holds the address of MEMTOP. The interrupt check does a memory cycle.

The reason you poll for interrupts is that you need the virtual machine to be in a coherent state because the interrupt could attempt to run arbitrary code. The garbage collector in particular has to be able to parse the machine state
at an interrupt. Interrupts are polled at apply time. Before application, the interrupts are checked. If an interrupt is to be processed, a continuation is pushed that will do the original application, and an interrupt handler is applied instead.

In MIT-Scheme, the virtual machine is a stack machine, and at apply time the entire state of the virtual machine is pointed to by the stack pointer. This is a good state to be in when you handle interrupts or garbage collect. But this means that arguments are passed on the stack. This instruction:

(mov q (r 0) (@r 4))
loads register 0 with the contents of memory at register 4. (The compiler convention is that register 4 is the stack pointer.) In other words, it is fetching the value of the argument tail from the stack. This is the second memory cycle.

Between interrupt polls, the compiled code can freely manipulate Scheme objects without worrying about being embarrassed by the garbage collector. But at apply time, when a possible interrupt poll could happen, the compiled code must put the virtual machine back into a coherent state. In particular, modified values are stored back on the stack.I This instruction just before the jump puts the value of tail back on the stack before jumping to the top of the loop.

(mov q (@r 4) (r 1)) 
That's three memory cycles in addition to the actual fetching of the CDR in this instruction:
(mov q (r 1) (@ro 0 8))
Of course these are quite inexpensive memory cycles because the top of stack is cached, but there is at least the time time it takes to validate the cache entry.

The interrupt poll occurs every time around the loop, so we copy the arguments back and forth between the stack and registers on each iteration. If we unroll the loop we can avoid some of the copying:

(define (last-cdr list)
  (let loop ((tail list))
    (if (pair? tail)
        (loop (cdr tail))
        tail)))

(define (last-cdr2 list)
  (let loop ((tail list))
    (if (not (pair? tail))
        tail
        (let ((tail (cdr tail)))
          (if (not (pair? tail))
              tail
              (loop (cdr tail)))))))
The loop in last-cdr2 compiles to this:
loop-6:
 (cmp q (r 7) (@r 6))           ;; Interrupt check
 (jge (@pcr interrupt-15))  

 (mov q (r 0) (@r 4))           ;; Fetch 'tail'

 (mov q (r 1) (r 0))            ;; Extract the tag
 (shr q (r 1) (&u; #x3a))

 (cmp b (r 1) (&u; 1))           ;; Check for pair?
 (jne (@pcr label-17))

 (and q (r 0) (r 5))            ;; Mask the tag

 (mov q (r 1) (@ro 0 8))        ;; Fetch the CDR

 (mov q (@r 4) (r 1))           ;; Assign 'tail'

 (mov q (r 0) (r 1))
 (shr q (r 0) (&u; #x3a))        ;; Extract the tag

 (cmp b (r 0) (&u; 1))           ;; Check for pair?
 (jne (@pcr label-19))

 (and q (r 1) (r 5))            ;; Mask the tag

 (mov q (r 0) (@ro 1 8))        ;; Fetch the CDR

 (mov q (@r 4) (r 0))           ;; Assign 'tail'

 (jmp (@pcr loop-6))            ;; Do it again
If I count correctly, there are six memory cycles per iteration, two of which are CDRs. We also avoid a single jmp instruction per iteration.

Here's the timing on my machine:

(test-last-cdr)
3.643 nanoseconds per cdr
3.643 nanoseconds per cdr
3.711 nanoseconds per cdr
3.643 nanoseconds per cdr
3.576 nanoseconds per cdr

(test-last-cdr2)
2.766 nanoseconds per cdr
2.699 nanoseconds per cdr
2.834 nanoseconds per cdr
2.699 nanoseconds per cdr


Michael ForsterHunchentools

· 12 days ago

I’ve published Hunchentools, my utility library for Hunchentoot. Hunchentools is not yet available for download via quicklisp.

Hunchentools includes functions to streamline aborting of request handling in common situations, functions to create dispatchers contingent upon request methods, functions for escaping strings, and various functions related to session security and authentication.

External documentation and examples are lacking at this point, but all exported symbols have associated documentation strings.

Joe MarshallLocality and GC

· 14 days ago

I was curious about how long it took to CDR down a list. I wrote a little program that adds up the elements in a list
and tried it out.

(define test-list (iota (expt 10 6)))

(define (sum-list list)
  (let loop ((total 0)
	     (tail  list))
    (if (pair? tail)
	(loop (+ total (car tail)) (cdr tail))
	(begin (if (not (null? tail))
		   (error:not-list list 'sum-list))
	       total))))

(define (test-sum-list n)
   (do ((i 0 (+ i 1))
        (answer '() (sum-list test-list)))
       ((not (< i n)) answer)))

1 ]=> (show-time (lambda () (test-sum-list 1000)))

;process time: 4280 (4280 RUN + 0 GC); real time: 4281
;Value: 499999500000
But after garbage collection, the performance dropped a bit.
1 ]=> (gc-flip)

;GC #18 15:18:59: took:   0.13   (0%) CPU,   0.13   (0%) real; free: 246114893
;Value: 246114893

1 ]=> (show-time (lambda () (test-sum-list 1000)))

;process time: 4490 (4490 RUN + 0 GC); real time: 4483
;Value: 499999500000
Now it's taking 4.49 ms.

The garbage collector in MIT Scheme is a very simple, stop the world, copying collector. The GC algorithm traverses the heap in breadth-first order. An undesired effect of this is data structures being spread about the heap. When I first built the test-list, the cons cells were close together. Here are the first few addresses:
1 ]=> (do ((tail test-list (cdr tail))
                (i 0 (+ i 1)))
               ((not (< i 10)) #f)
             (display (object-datum tail))
             (newline))
253936080
253936064
253936048
253936032
253936016
253936000
253935984
253935968
253935952
253935936
;Value: #f
But after garbage collection...
1 ]=> (gc-flip)

;GC #19 15:33:28: took:   0.15   (1%) CPU,   0.16   (0%) real; free: 246114593
;Value: 246114593

1 ]=> (do ((tail test-list (cdr tail))
              (i 0 (+ i 1)))
             ((not (< i 10)) #f)
           (display (object-datum tail))
           (newline))
194190168
194326376
194416512
194499936
194555336
194584992
194609544
194631760
194652360
194669208
;Value: #f
All the cons cells are on different pages.

This is annoying, so I hacked the GC so that it transports chains of cons-cells eagerly. If we do the same experiment, before the flip,

1 ]=> (show-time (lambda () (test-sum-list 1000)))

;process time: 4280 (4280 RUN + 0 GC); real time: 4280
;Value: 499999500000
And after.
1 ]=> (gc-flip)

;GC #5 15:38:53: took:   0.23   (2%) CPU,   0.24   (0%) real; free: 249429521
;Value: 249429521

1 ]=> (show-time (lambda () (test-sum-list 1000)))

;process time: 4100 (4100 RUN + 0 GC); real time: 4100
;Value: 499999500000
Now we see a performance increase. If we look at the test list,
1 ]=> (do ((tail test-list (cdr tail))
           (i 0 (+ i 1)))
          ((not (< i 10)) #f)
        (display (object-datum tail))
        (newline))
193516792
193516808
193516824
193516840
193516856
193516872
193516888
193516904
193516920
193516936
;Value: #f

You can see that the cons-cells addresses are next to each other.

Quicklisp newsNew Quicklisp client available

· 17 days ago
I've updated the Quicklisp client to version 2016-01-21. There are a few new things:

  • Fix for issue #116, so"asdf" is now ignored as a system to be bundled instead of signaling an error. Thanks to Dimitri Fontaine for inspiration and some code for fixing this.
  • Merged pull request #127, which has some small fixes courtesy of Attila Lendvai
  • Merged pull request #124, which adds recognition of URL schemes to fetching, and a special variable to control what function is used for what scheme. This feature moves Quicklisp closer to out-of-beta; many thanks to SANO Masatoshi for contributing it.
To get this update, use (ql:update-client) and restart your session. 

Patrick SteinPopulation in Politics, Simple Frequency Counts

· 25 days ago

The first coding assignment of the Data Management and Visualization class that I am doing on Coursera is just to do some frequency analysis on some of the variables that will be involved in the research you want to do.

I am using the 2012 U.S. Presidential Election data broken down by county.

Frequency Counts

The assignment was to do frequency counts. If I did tables of raw frequency counts, the tables would be huge. There are 4588 counties in the data set. There are 4075 different values for the total number of votes cast in a county. As such, I bucketed the counts based upon the power of ten of the value. Here is the output for the total number of votes cast:

CL-USER> (print-log-buckets "Total" #'vote-distribution-votes-cast)
+----------------+--------------------+
|    Votes Total | Number of counties |
+----------------+--------------------+
|            1's | 3                  |
|           10's | 72                 |
|          100's | 646                |
|        1,000's | 2102               |
|       10,000's | 1513               |
|      100,000's | 247                |
|    1,000,000's | 5                  |
+----------------+--------------------+
NIL

Here is the output for the total number of votes for Democratic candidates and for the Republican candidates:

CL-USER> (print-log-buckets "Dem" #'vote-distribution-dem)
+----------------+--------------------+
|      Votes Dem | Number of counties |
+----------------+--------------------+
|            1's | 15                 |
|           10's | 166                |
|          100's | 1171               |
|        1,000's | 2380               |
|       10,000's | 730                |
|      100,000's | 124                |
|    1,000,000's | 2                  |
+----------------+--------------------+
NIL
CL-USER> (print-log-buckets "GOP" #'vote-distribution-gop)
+----------------+--------------------+
|      Votes GOP | Number of counties |
+----------------+--------------------+
|            1's | 12                 |
|           10's | 171                |
|          100's | 937                |
|        1,000's | 2349               |
|       10,000's | 1009               |
|      100,000's | 110                |
+----------------+--------------------+
NIL

With the above frequency count, we can see that of the five counties with over a million votes cast, the Democrats got more than a million votes in two of them whilst the Republicans did not get a million votes in any county.

The numbers are pretty close the whole way through, but that still doesn’t mean a great deal. It could be that the fifteen counties where Democrats got fewer than ten votes were counties with ten thousand votes cast. So, I put together a small function then to get the worst counties for a given party:

(defun get-worst-counties (key &optional (how-many 10))
  (subseq (stable-sort (copy-seq *by-county*)
                       #'<
                       :key (lambda (dist)
                              (/ (funcall key dist)
                                 (max 1
                                      (vote-distribution-votes-cast dist)))))
          0
          how-many))

The worst counties for Democrats and Republicans?

CL-USER> (get-worst-counties #'vote-distribution-dem)
(#S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "HANCOCK CTY TOWNSHIPS" :DEM 0 :GOP 0 :VOTES-CAST 0)
 #S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "UPTON" :DEM 0 :GOP 0 :VOTES-CAST 0)
 #S(VOTE-DISTRIBUTION :STATE "TX" :COUNTY "KING" :DEM 5 :GOP 139 :VOTES-CAST 145)
 #S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "MORO PLT." :DEM 1 :GOP 21 :VOTES-CAST 23)
 #S(VOTE-DISTRIBUTION :STATE "MT" :COUNTY "WIBAUX" :DEM 25 :GOP 421 :VOTES-CAST 544)
 #S(VOTE-DISTRIBUTION :STATE "TX" :COUNTY "ROBERTS" :DEM 25 :GOP 408 :VOTES-CAST 439)
 #S(VOTE-DISTRIBUTION :STATE "ID" :COUNTY "MADISON" :DEM 832 :GOP 13445 :VOTES-CAST 14412)
 #S(VOTE-DISTRIBUTION :STATE "ID" :COUNTY "FRANKLIN" :DEM 325 :GOP 5195 :VOTES-CAST 5600)
 #S(VOTE-DISTRIBUTION :STATE "TX" :COUNTY "STERLING" :DEM 31 :GOP 459 :VOTES-CAST 494)
 #S(VOTE-DISTRIBUTION :STATE "TX" :COUNTY "GLASSCOCK" :DEM 44 :GOP 526 :VOTES-CAST 578))
CL-USER> (get-worst-counties #'vote-distribution-gop)
(#S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "HANCOCK CTY TOWNSHIPS" :DEM 0 :GOP 0 :VOTES-CAST 0)
 #S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "UPTON" :DEM 0 :GOP 0 :VOTES-CAST 0)
 #S(VOTE-DISTRIBUTION :STATE "SD" :COUNTY "SHANNON" :DEM 2922 :GOP 188 :VOTES-CAST 3130)
 #S(VOTE-DISTRIBUTION :STATE "CT" :COUNTY "HARTFORD" :DEM 31735 :GOP 2138 :VOTES-CAST 34037)
 #S(VOTE-DISTRIBUTION :STATE "DC" :COUNTY "DISTRICT OF COLUMBIA" :DEM 222332 :GOP 17337 :VOTES-CAST 243348)
 #S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "PENOBSCOT NATION VOT DST" :DEM 253 :GOP 23 :VOTES-CAST 281)
 #S(VOTE-DISTRIBUTION :STATE "NY" :COUNTY "BRONX" :DEM 288378 :GOP 26304 :VOTES-CAST 316047)
 #S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "ISLE AU HAUT" :DEM 48 :GOP 5 :VOTES-CAST 57)
 #S(VOTE-DISTRIBUTION :STATE "MA" :COUNTY "PROVINCETOWN" :DEM 2121 :GOP 210 :VOTES-CAST 2380)
 #S(VOTE-DISTRIBUTION :STATE "ME" :COUNTY "MONHEGAN PLT." :DEM 49 :GOP 5 :VOTES-CAST 55))

As you can see from this, there are two counties which show no votes cast. In both of those cases, there are no precincts reporting in the data set. The data set tells the number of precincts in the county along with the number of precincts reporting. These counties with none of the precincts reporting are significant glitches in the data. On the other hand, some counties in the data have hundreds of precincts where all but one reported. I could remove a county from the data if not all of its precincts reported. However, I believe that within a county, single precincts will not differ very much from other precincts which were counted in the data. Further, as I do not have any hope of determining the population density down to the precinct level, I am just going to roll with what I have.

Implementation

I put together some simple utilities around Fare-CSV to retrieve particular columns of a CSV file formatted in particular ways. Here is the source code for those utilities.

One of the things that immediately became apparent is that there are two separate columns in the database labelled "TOTAL VOTES CAST". I wanted to make sure there were no confusion, so I wrote a quick function then to check that both of those columns agree everywhere.

(defun both-total-votes-columns-agree-everywhere ()
  (let ((columns (find-columns-with-label "TOTAL VOTES CAST")))
    (flet ((votes-cast-agrees (*row*)
             (apply #'= (get-columns-as #'parse-integer-allowing-junk
                                        columns))))
      (every #'votes-cast-agrees (data-rows)))))

(assert (both-total-votes-columns-agree-everywhere))

Spoiler: They do. Whew!

The data here has one row per county. I might have preferred there be one row per county/candidate pair. Regardless, I wrote a short function that takes a party name and all of the columns identifying parties along with the columns identifying how many votes a given party received.

(defun count-votes (party parties votes)
  (loop :for p :in parties
     :for v :in votes
     :when (string= p party)
     :sum v))

For example, this might get arguments party = "DEM", parties = ("DEM" "GOP" "LIB" "GRN" "" "" "" "" "" "" "" "" "" "" "" ""), and votes = (91696 121234 5539 2127 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL). This function sums up all of the numbers in the votes list where the corresponding entry in the parties list matches the given party.

I made a little data structure to hold the data that I am interested in for each county.

(defstruct vote-distribution
  (state "" :type string)
  (county "" :type string)
  (dem 0 :type integer)
  (gop 0 :type integer)
  (votes-cast 0 :type integer))

I then created a function which returns a function. The returned function returns an instance of my data structure for the row passed into it. Note: the data set contains rows which roll-up the results for a whole state. For those rows, the FIPS code for the county is zero.

(defun make-votes-by-county-data-collector ()
  (let ((state-column  (find-column-with-label "State Postal"))
        (county-column (find-column-with-label "County Name"))
        (fips-column   (find-column-with-label "FIPS Code"))
        (total-column  (find-column-with-label "TOTAL VOTES CAST"))
        (party-columns (find-columns-with-label "Party"))
        (votes-columns (find-columns-with-label "Votes")))

    (lambda (*row*)
      (when (plusp (get-column-as #'parse-integer-allowing-junk fips-column))
        (let* ((state (get-column-as #'string-upcase state-column))
               (county (get-column-as #'string-upcase county-column))
               (total (get-column-as #'parse-integer-allowing-junk
                                     total-column))
               (parties (get-columns-as #'string-upcase party-columns))
               (votes (get-columns-as #'parse-integer-allowing-junk
                                      votes-columns)))
          (make-vote-distribution :state state
                                  :county county
                                  :dem (count-votes "DEM" parties votes)
                                  :gop (count-votes "GOP" parties votes)
                                  :votes-cast total))))))

I did that because I originally had all of that functionality in the function which loops over each of the rows in the data set. Now, the function that collects all of these is simpler, but I’m not sure the overall simplicity is much improved.

(defun get-votes-by-county ()
  (loop :with collector := (make-votes-by-county-data-collector)
     :for row :in (data-rows)
     :for dist := (funcall collector row)
     :when dist
     :collect dist))

(defparameter *by-county*
  (stable-sort (get-votes-by-county)
               #'<
               :key #'vote-distribution-votes-cast))

I created a function to bucket them based on their base-10 logarithm. Of course, this immediately freaked out on the couple of counties for which there is no data in the data set, so I had to take care not to take the logarithm of zero.

(defun log-buckets (&optional (key #'vote-distribution-votes-cast))
  (let ((buckets (make-hash-table :test #'equal))
        (max-bucket 0))
    (labels ((bucket-number (dist)
               (floor (log (max (funcall key dist) 1)
                           10)))
             (incorporate (dist)
               (let ((n (bucket-number dist)))
                 (setf max-bucket (max n max-bucket)
                       (gethash n buckets) (1+ (gethash n buckets 0))))))
      (mapc #'incorporate *by-county*)
      (loop :for n :to max-bucket
         :collect (gethash n buckets 0)))))

I made a wrapper function for that which pretty-prints the results as a table.

(defun print-log-buckets (label &optional (key #'vote-distribution-votes-cast))
  (let ((buckets (loop :for pow :from 0
                    :for buck :in (log-buckets key)
                    :appending (list (expt 10 pow) buck))))
    (format t "+~16,,,'-<~>+~20,,,'-<~>+~%")
    (format t "|~16< Votes ~A ~>| Number of counties |~%" label)
    (format t "+~16,,,'-<~>+~20,,,'-<~>+~%")
    (format t "~{| ~12:D's | ~D ~38T|~%~}" buckets)
    (format t "+~16,,,'-<~>+~20,,,'-<~>+~%")))

Here is the source code for all of the above snippets.

Michael MalisLoops in Lisp Part 3: Iterate

· 26 days ago

This is part 3 of Loops in Lisp. For part 1 on how you can build any kind of looping construct you want out of just goto and macros, click here. For part 2 on Loop, click here.

The Iterate library is pretty awesome. It provides a macro iterate (and an alias for it, iter) that is basically a Lispy version of loop. The most obvious consequence of this is that iterate uses a lot more parens than loop does:

;; Loop code
(loop for i from 1 to 10
      collect i)

;; Iterate code
(iter (for i from 1 to 10)
      (collect i))

Even though all of the extra parens make iterate much uglier than loop, they give iterate all of the advantages of Lisp syntax. One such advantage is the ability to embed iterate clauses within Lisp code and vice versa. While you can’t do this with loop, you can do it with iterate because the syntax of iterate is so similar to the syntax of ordinary Lisp code. Here is what happens when you try to embed a collect clause within Lisp code with loop and with iterate:1

;; Not valid loop code.
(loop for i from 1 to 10
      do (when (evenp i)
           (collect i)))

;; Valid iterate code
(iter (for i from 1 to 10)
      (when (evenp i)
        (collect i)))

Although the ability to seamlessly go between Lisp code and iterate is pretty awesome, the greatest feature provided by iterate is also the entire reason why Lisp syntax has so many parens in the first place. Lisp syntax (and by extension iterate) makes it easy to write macros! Because of this, you can add pretty much any feature you want to iterate. As a simple example, here’s how you could define an iterate clause specifically for looping over the digits of a number:2

(defun digits (n)
  "Returns a list of the digits of N."
  (map 'list #'digit-char-p (princ-to-string n)))

(defmacro-clause (for var in-digits-of n)
  `(for ,var in (digits ,n)))

And here is how you would use it:

(iter (for i in-digits-of 123)
      (sum i))
=> 6

I cannot express how awesome this is. If you want an iterate clause for iterating over SQL queries, you can add it. If you want an iterate clause for looping over your own custom data structure, you can add it. You can add any feature you want all because iterate allows for the use of macros!

Personally, I prefer to use iterate over loop. Even though it is uglier, it is much more extensible than loop because it decides to use a Lisp like syntax.

The post Loops in Lisp Part 3: Iterate appeared first on Macrology.

Patrick SteinBuilding Supplies

· 30 days ago

I have a couple of nascent projects on my plate which require custom, server-side software. I’ve been trying to use these projects to explore the Clean Architecture concepts using Test-Driven Development (TDD).

I can’t even begin.

According to Clean Architecture, I should start with my application logic independent of whether it will be a command-line tool, a series of tools, a web-application, or what-have-you. So, let me start on the application code.

This is TDD though. So, I need to start with a test. How do I do that?

(ql:quickload :nst)

(nst:def-test-group querying-data () ...)

Wait a minute? I just committed myself to Lisp. I just made a huge business decision, a huge implementation decision, a decision that will shape my life for the next n years, and neither TDD or Clean Architecture had anything to say.

I need building supplies. I can’t go anywhere with my architecture or my development without a programming language.

I want to write my apps in Lisp. One of them, I already have mostly done in Lisp. I am still trepidatious about deploying Lisp.

Why am I trepidatious about deploying Lisp? Is it because there is inadequate support for web programming in Lisp? Absolutely not. Is it because I have some doubt in Lisp’s staying power? Absolutely not.

It’s email. Email is holding me back.

I use my current web hosting provider to give me a LAMP stack upon which I run WordPress for this blog and some git repositories and a bug-tracking database (that I can’t remember how to log into). All of that, I could move with confidence in a few hours.

What I dread is having to collect the several hundred mail-forwards that I currently have along with the half-dozen IMAP accounts and move them anywhere, let alone to somewhere that I have to manage them myself and deal with SPAM and mail queues and crap.

It seems that for only a few bucks more per month than I’m paying now, I can get Plesk on a VPS that should be big enough for my purposes. Does anyone have any experience with Plesk? Is it going to make email painless for me on Ubuntu? Or, am I going to hate my life? Does someone have a VPS provider they strongly recommend?

Do I really have to write my application in PHP on the chance that I’ll want to deploy it on the web just because email is scary?

Luís OliveiraCommon Lisp Recipes: A Problem-Solution Approach

· 34 days ago
Edi Weitz, author of things like CL-PPCRE and Hunchentoot (amongst many other pieces of ediware), has just published a new book, "Common Lisp Recipes: A Problem-Solution Approach". I've ordered mine. Get yours from Apress or a European Amazon store.


Common Lisp Recipes is a collection of solutions to problems and answers to questions you are likely to encounter when writing real-world applications in Common Lisp. Written by an author who has used Common Lisp in many successful commercial projects over more than a decade, this book is the first Common Lisp book which covers areas as diverse as web programming, databases, graphical user interfaces, communication with other programming languages, multi-processing, and mobile devices as well as debugging techniques and optimization, to name just a few. It is organized around specific problems or questions each followed by ready-to-use example solutions and clear explanations of the concepts involved, plus pointers to alternatives and more information. Each recipe can be read independently of the others and thus the book will hopefully earn a special place on your bookshelf as a reference work you always want to have within reach.

Common Lisp Recipes is aimed at programmers who are already familiar with Common Lisp to a certain extent but do not yet have the experience you typically only get from years of hacking in a specific computer language. It is written in a style that mixes hands-on no-frills pragmatism with precise information and prudent mentorship.

If you feel attracted to Common Lisp's mix of breathtaking features and down-to-earth utilitarianism, you'll also like this book.

Patrick SteinPopulation Density in Politics

· 35 days ago

I am taking a Coursera course by Wesleyan University titled Data Management and Visualization.

During Bush v. Gore, there was a ton of freely available data about that election. I did a quick-and-dirty graph showing that Gore won the most populous counties by wide margins and Bush won most of the rest of the counties by wide margins.

For this course, I am going to revisit that analysis with the 2012 election data and maybe the 2008 election data.

The Hypothesis

In the United States, there is a strong correlation between population density and voting for the Democratic candidate for president.

The Data

The 2012, by-county results are available through The Guardian newspaper website. The 2008 election data is available for purchase through Dave Leip’s Election Data Store. The US Census Data website has information available about the population and land area of each U.S. county.

Related Work

My first web search for related data was: correlation population density political party.

This search turns up several articles about a scatterplot by Conor Sen relating the Cook Partisan Voting Index (PVI) plotted against population density based on 2012 data. There are related heat-maps by others from the same data.

That search also turns up a paper by Jowei Chen of the University of Michigan and Jonathan Rodden of Stanford University about why compact voting districts are bad for Democrats. That paper focuses mostly on the shapes of voting districts in Florida and how they have be gerrymandered to make those in population-dense areas very compact while those in less populated areas are tentacled and sprawling and how this results in a higher number of Republican representatives than is warranted by overall population numbers.

A related aspect that shows up in this search is that on specific issues, like transit infrastructure, the congressional voting record is strongly correlated with the population density of the congressperson’s district. This effect is a second-order effect, however. The vote of a congressperson will likely be entwined with what the party as a whole wants as much as (or even more than) their constituents want.

ArcGIS contains a map correlating political affiliation of congresspersons with the population density of their districts.

The Tools

I will, of course, being me, use Common Lisp for all of this. I suspect that I will use Fare-CSV for ingesting CSV data. If I have to parse TIGRE data, I will likely rely on some blend of esrap and CL-EWKB or custom geometry code. For plotting, I will likely rely on Vecto but may also try out some of the other libraries like adw-charting or finally get around to making my own multi-backend charting library.

CL Test Gridquicklisp 2015-12-18

· 41 days ago
Almost every month cl-test-grid detects various regressions in CL ecosystem.

Like this month:
https://common-lisp.net/project/cl-test-grid/ql/quicklisp-2015-12-18-diff2.html

And in general: https://common-lisp.net/project/cl-test-grid/ql/

I have problem reporting all these regressions to interested parties. Studying why something fails, searching for right person to report, formulating and submitting bug reports - all that easily takes more than a full working day.

Also, sometimes it's not necessary a bug from the library maintainer point of view, for example if his library fails on CLISP because CLISP ships with old ASDF, maybe this maintainer doesn't care. But maybe those who depends on this library care. So, it's not always obvious whether the situation requires to disturb people.

That's why I created this blog. I mean it as a low volume notification channel - mostly a notice with reports once a month when the tests are finished, and a summary of what I understand about the failures. Then, if people are interested in particular failures, they can ask and I will help to investigate and explain why exactly something fails.

I hope this will help to effectively fix important failures and keep the community aware about the factors causing fluctuations of quality in CL ecosystem.

Now about this month regressions.

First of all, I usually build two diff reports.

One is grouped by lisp implementation first and then by library:
https://common-lisp.net/project/cl-test-grid/ql/quicklisp-2015-12-18-diff.html

Another one is grouped by library first and then by lisp impl:
https://common-lisp.net/project/cl-test-grid/ql/quicklisp-2015-12-18-diff2.html

Both reports show the same data, just arranged differently.

The most noticeable regressions in quicklisp 2015-12-18 comparing to the previous
release:
  • bordeaux-threads uses UIOP without specifying :depends-on :uiop in the .asd file; in result on lisp implementations where ASDF doesn't include UIOP, bordeaux-threads (and libraries depending on it) fail to load
  • iolib rejects ASDF < 3.1, so fails to load (and prevents libraries using it from loading) on lisps with elder ASDF
  • cl+ssl declares FFI binding for function SSL_CTX_set_default_verify_dir which is absent in the latest stable OpenSSL release, and only present in OpenSSL master. c+ssl doesn't use this function, the ffi declaration was added just to allow others to invoke it. Still, cl+ssl fails to load on CMUCL because CMUCL actually checks for foreign symbol to be present when FFI declaration is processed. Other lisps we tested are unaffected. This problem is fixed already in cl+ssl git.
  • As usually, more and more libraries start to use new ASDF features, for example keywords :home, :at. These libraries and their dependencies fail to load on elder ASDF.
  • croatoan library starts using sb-ext:posix-getenv thus fails on non-sbcl lisps (hint: use uiop:getenv instead)
  • rutils (and depending libs) fail on ABCL and ECL with "No such method for PRINT-OBJECT"
  • several libraries fail on ECL with "* is not a valid type specifier"
  • com.informatimago.common-lisp.telnet fails on CMUCL with "The value of the :SLOT-NAME initarg, US, is a constant and so cannot be bound."
... and other failures.

If you're interested in some specific failure or need help investigating something, just ask in the comments or on the mailing list.

LispjobsClojure developer, Glamify, remote

· 42 days ago

https://remoteok.io/remote-jobs/14166-remote-clojure-developer-glamify

We need an experienced Clojure developer to work full time or part time. Ideally you’d be familiar with some of the following:

Datomic Ring Reagent DataScript Prismatic Schema Server-side React Nashorn Figwheel

Bonus points for being in a timezone close to eastern Australia.

The project is only two months old, and so far there’s only one developer.


Quicklisp newsDecember 2015 Quicklisp dist update now available

· 51 days ago
New projects:
  • asdf-viz — visualize the library dependency of an asdf/quicklisp system — LLGPL
  • ax.tga — A fork of cl-tga with some new features. — MIT
  • cl-amqp — AMQP 0.9.1 with RabbitMQ extensions in Common Lisp — MIT
  • cl-cut — Macros for partial application of expressions in the spirit of SRFI 26. — MIT
  • cl-textmagic — Common lisp implementation of TextMagic API to send SMS — MIT
  • eventfd — IOLib based eventfd bindings — MIT
  • ia-hash-table — Main purpose is to be able to use strings as real keys but do gethash with symbols and vice versa. Can be useful for things like http headers parsing (no more intern leaks), json apis with/without https://github.com/AccelerationNet/access. Only tested on SBCL. Expected to work on Allegro, CCL and LW. — MIT
  • qtools-ui — A collection of components and utilities for use in Qt applications. — Artistic
  • read-csv — A library for reading CSV data from streams. — lgpl2
  • simple-inferiors — A very simple library to use inferior processes. — Artistic
  • smart-buffer — Smart octets buffer — BSD 3-Clause
  • teepeedee2 — Multiprotocol fast networking framework 
  • trivial-build — Compile a system into an executable. — MIT
  • trivial-exe — Tools for working with executables — MIT

Updated projects: access, antik, binfix, birch, bordeaux-threads, buffalo, buildapp, caveman, ceramic, cl+ssl, cl-ana, cl-ansi-term, cl-autowrap, cl-cairo2, cl-charms, cl-cli, cl-colors, cl-coveralls, cl-decimals, cl-enchant, cl-enumeration, cl-gambol, cl-general-accumulator, cl-geometry, cl-groupby, cl-hash-util, cl-interpol, cl-l10n, cl-libyaml, cl-opsresearch, cl-pass, cl-permutation, cl-project, cl-protobufs, cl-rabbit, cl-readline, cl-sdl2, cl-sendmail, cl-xul, cl-yaml, clack, clack-errors, clazy, clinch, clip, clods-export, closer-mop, clsql, clsql-orm, codex, coleslaw, colleen, colliflower, com.informatimago, command-line-arguments, common-doc, common-html, common-lisp-actors, commonqt, crane, croatoan, data-table, declt, defenum, defmacro-enhance, djula, eazy-process, eazy-project, esrap, external-program, fare-csv, fare-mop, fare-utils, fast-http, fast-io, find-port, gendl, geneva, glkit, gsll, helambdap, hl7-parser, hu.dwim.asdf, hu.dwim.computed-class, hu.dwim.def, hu.dwim.delico, hu.dwim.logger, hu.dwim.partial-eval, hu.dwim.perec, hu.dwim.presentation, hu.dwim.quasi-quote, hu.dwim.rdbms, hu.dwim.reiterate, hu.dwim.serializer, hu.dwim.syntax-sugar, hu.dwim.util, hu.dwim.walker, hu.dwim.web-server, inferior-shell, iolib, jonathan, kenzo, lack, lime, lisp-namespace, lispbuilder, local-time, lparallel, lucerne, macro-html, mcclim, mgl-pax, mixalot, mk-string-metrics, mpc, napa-fft3, new-op, perlre, policy-cond, pounds, projectured, prove, qlot, qt-libs, qtools, ratify, rcl, rfc2109, rfc2388-binary, rpm, rutils, s-protobuf, scalpl, scriba, sdl2kit, serapeum, simple-tasks, staple, string-case, stumpwm, swank-protocol, swap-bytes, sxql, texp, trivia, trivial-benchmark, trivial-download, trivial-open-browser, trivial-update, trivialib.type-unify, unix-opts, utilities.binary-dump, utilities.print-tree, varjo, vom, woo, xecto, yason.

Michael ForsterDon't Panic! React with Common Lisp

· 51 days ago

I’ve written Panic, a small library for generating React components with Common Lisp and Parenscript. The current version of Panic is compatible with React 0.11.2, but I’m working on support for React 0.14, in particular, for the changes introduced in React 0.12. Panic is not yet available for download via quicklisp.

API

The Panic API consists of two Parenscript macros, DEFCOMPONENT and JSL.

[Macro] defcomponent name lambda-list [documentation] form*

Defines a Parenscript special variable as if by PS:DEFVAR, assigning it the value created by a call to React.createClass(…).

name is a symbol.

lambda-list is a list the elements of which are a list matching the destructuring lambda list

(&key display-name
      get-initial-state
      get-default-props
      prop-types
      mixins
      statics
      component-will-mount
      component-did-mount
      component-will-receive-props
      should-component-update
      component-will-update
      component-did-update
      component-will-unmount)

If display-name is not provided, it will default to the symbol name of name.

The remaining elements must be expressions yielding functions–the lifecycle methods of the React component class.

forms is an implicit PROGN and constitutes the body of the mandatory render method of the React component class.

[Macro] jsl form* => result*

JSL is a Lispy take on JSX, the React Javascript syntax extension. JSL transforms its body, expanding JSL forms into Parenscript function forms to call React DOM operations.

A JSL form is a list with the first element being a keyword naming a React element type. All but the last of the remaining elements constitute a possibly empty list of alternating React property names and values. The last element is a possibly empty list of the children of the React element.

Example: A Simple Component

(ps:ps
  (panic:defcomponent hello-message
      ()
    (panic:jsl
     (:div "Hello " (ps:@ this props name))))

  (ps:chain
   -react
   (render-component (hello-message (ps:create :name "John"))
                     (ps:chain
                      document
                      (get-element-by-id "mount-node")))))

Example: A Stateful Component

(ps:ps
  (panic:defcomponent timer
      (:get-initial-state
       #'(lambda () (ps:create 'seconds-elapsed 0))
       :tick
       #'(lambda ()
           (ps:chain
            this
            (set-state (ps:create
                        'seconds-elapsed
                        (1+ (ps:@ this state seconds-elapsed))))))
       :component-did-mount
       #'(lambda ()
           (setf (ps:@ this interval)
                 (set-interval (ps:@ this tick) 1000)))
       :component-will-unmount
       #'(lambda () (clear-interval (ps:@ this interval))))
    (panic:jsl
     (:div "Seconds Elapsed: " (ps:@ this state seconds-elapsed))))

  (ps:chain
   -react
   (render-component (timer)
                     (ps:chain
                      document
                      (get-element-by-id "mount-node")))))

Example: An Application

(ps:ps
  (panic:defcomponent todo-list ()
    (flet ((create-item (item-text) (panic:jsl (:li item-text))))
      (panic:jsl
       (:ul (ps:chain this props items (map #'create-item))))))

  (panic:defcomponent todo-app
      (:get-initial-state
       #'(lambda () (ps:create :items (array) :text ""))
       :on-change
       #'(lambda (e)
           (ps:chain
            this
            (set-state (ps:create :text (ps:@ e target value)))))
       :handle-submit
       #'(lambda (e)
           (ps:chain e (prevent-default))
           (let ((next-items
                  (ps:chain
                   this
                   state
                   items
                   (concat (array (ps:@ this state text)))))
                 (next-text ""))
             (ps:chain
              this
              (set-state (ps:create :items next-items
                                    :text next-text))))))
    (panic:jsl
     (:div
      (:h3 "TODO")
      (todo-list (ps:create :items (ps:@ this state items)))
      (:form :on-submit (ps:@ this handle-submit)
             (:input :on-change (ps:@ this on-change)
                     :value (ps:@ this state text))
             (:button (+ "Add #"
                          (1+ (ps:@ this state items length))))))))

  (ps:chain
   -react
   (render-component (todo-app nil)
                     (ps:chain
                      document
                      (get-element-by-id "mount-node")))))

Michael MalisLoops in Lisp Part 2: Loop

· 54 days ago

This is part 2 of Loops in Lisp. Click here to view the previous post on how you can build any iteration abstraction you want out of just goto and macros.

The loop macro is probably the most well known of all macros. It provides a DSL for performing any kind of iteration imaginable. To give you an idea of just how powerful loop is, here are the first two Project Euler problems, solved using just loop:

;; Solution for problem #1.
(loop for i from 1 below 1000
      if (or (= 0 (mod i 3))
             (= 0 (mod i 5)))
        sum i)

;; Solution for problem #2.
(loop for a = 1 then (+ a b)
      and b = 0 then a
      while (< a 4000000)
      if (evenp a)
        sum a)

The coolest part of loop is that it is just a macro! That means it would be possible to build loop in Common Lisp, even if it wasn’t provided as a builtin (here is one such implementation). That also means any loop code is eventually compiled down to goto! For example, here is the expansion of the solution to the first Project Euler problem:

(block nil
  (let ((i 1))
    (declare (type (and real number) i))
    (let ((#:loop-sum-2482 0))
      (declare (type number #:loop-sum-2482))
      (tagbody
       sb-loop::next-loop
        (if (>= i '1000)
            (progn (go sb-loop::end-loop))
            nil)
        (if (let ((#:g2483 (= 0 (mod i 3))))
              (if #:g2483
                  #:g2483
                  (the t (= 0 (mod i 5)))))
            (setq #:loop-sum-2482 (+ #:loop-sum-2482 i)))
        (setq i (1+ i))
        (go sb-loop::next-loop)
       sb-loop::end-loop
        (return-from nil #:loop-sum-2482)))))

If you look carefully, the expansion is nothing more than a mix of a few gotos and conditionals. Also, even though the generated code is a complete mess, you are able to work with it through interface provided by loop. Even though loop is fairly complex, it is still much simpler than raw gotos. If you think about it, loop is really just a convenient way of specifying a combination of patterns of gotos and conditionals.

I don’t have much to add about loop that others haven’t already said. If you are looking for a basic introduction to loop you should read Peter Seibel’s guide which can be found here. If you are looking for a more complete reference, check out the loop chapter in Common Lisp the Language which can be found here.

While all of the features of loop compose well with each other, they do not compose well with the rest of Common Lisp. You cannot embed a loop clause (e.g. collect) within ordinary lisp code. That brings us to what will be next week’s topic, iterateIterate is basically a more lispy version of loop. It allows you to seamlessly go between iterate clauses and regular Lisp code. More importantly, iterate allows you to define macros that then become part of the iterate DSL!

The post Loops in Lisp Part 2: Loop appeared first on Macrology.

Marco AntoniottiRevamped CL-ENUMERATIONS

· 64 days ago

I just revamped the CL-ENUMERATIONS library and API.

This was simply a nice cleanup of the previous library. The new documentation pages are, of course, generated with a little HEΛP, which also got some fine tuning to be able to generate doc pages from quite a variety of relatively "plain" doc-strings.


(Cheers)

Nick LevinePortable walker?

· 64 days ago
Does anyone know of a portable code walker that works across all the popular implementations? (I know more or less all of them have a walker buried inside their CLOS, but the interfaces to these aren't all the same. I looked at ql's hu.dwim.walker but it's not in theory available on very many implementations, and when I tried it on LW it just Didn't Work.)

Marco AntoniottiThere's a pulse

· 70 days ago

Hello there,

After a long time I finally had a few hours (sic!) to get back to actual hacking.

The main thing I did was to get myself re-accustomed with the new common-lisp.net infrastructure based on GitLab. This took some time to "realign" my repositories and getting my head wrapped around the way things work.

The result is that I went back to HEΛP to fix some tricky package issues, which are the result of wanting to be too cocky. Next I want to rework the web page layout in order to use the new HTML5 "semantic" tags.

After that, I will rework the documentation of my libraries and go on to "finish" a couple of other ones I have on the back burner.

Do I have too much on my lisping plate? :) :)

Cheers


MA

Paul KhuongRetrospective on Binary Search and Comp{ress,ilat}ion

· 71 days ago

I never know whether to prefer closure or fresh questions, in research. I got a little of both lately. First, closure on searching in permutations of sorted arrays, and second, more avenues on the compilation as compression angle.

Array Layouts for Comparison-Based Searching

In July 2012, I started really looking into searching in static sorted sets, and found the literature disturbingly useless. I reviewed a lot of code, and it turned out that most binary searches out there are not only unsafe for overflow, but also happen to be badly micro-optimised for small arrays with simple comparators. That lead to Binary Search eliminates Branch Mispredictions, a reaction to popular assertions that binary search has bad constant factors (compared to linear search or a breadth first layout) on modern microarchitecture, mostly due to branch mispredictions. That post has code for really riced up searches on fixed array sizes, so here’s the size generic inner loop I currently use.

1
2
3
4
5
6
7
8
9
10
const uint32_t x = ...;
const uint32_t *base = ...;
size_t n = ...;
size_t half;

while ((half = n / 2) > 0) {
    const uint32_t *mid = &base[half];
    base = (*mid < x) ? mid : base;
    n -= half;
}

The snippet above implements a binary search, instead of dividing by three to avoid aliasing issues. That issue only shows up with array sizes that are (near) powers of two. I know of two situations where that happens a lot:

  1. bad benchmarks;
  2. data structures built around powers of two (e.g., Saxe & Bentley dynamisation).

The fix for the first case is to do proper benchmarking on a wide range of input sizes. Ternary or offset binary search are only really useful in the second case. There’s actually a third case: when I’m about to repeatedly search in the same array, I dispatch to unrolled ternary searches, with one routine for each power of two. I can reduce any size to a power of two with one initial iteration on an off-center “midpoint.” Ternary search has a high overhead for small arrays, unless we can precompute offsets by unrolling the whole thing.

My work on binary search taught me how to implement binary search not stupidly–unlike real implementations–and that most experiments on searching in array permutations seem broken in their very design (they focus on full binary trees).

I don’t think I ever make that explicit, but the reason I even started looking into binary search is that I wanted to have a fast implementation of searching in a van Emde Boas layout! However, none of the benchmarks (or analyses) I found were convincing, and I kind of lost steam as I improved sorted arrays: sortedness tends to be useful for operations other than predecessor/successor search.

Some time in May this year, I found Pat Morin’s fresh effort on the exact question I had abandoned over the years: how do popular permutations work in terms of raw CPU time? The code was open, and even good by research standards! Pat had written the annoying part (building the permutations), generated a bunch of tests I could use to check correctness, and avoided obvious microbenchmarking pitfalls. He also found a really nice way to find the return value for BFS searches from the location where the search ends with fast bit operations (j = (i + 1) >> __builtin_ffs(~(i + 1));, which he explains in the paper).

I took that opportunity to improve constant factors for all the implementations, and to really try and explain in detail the performance of each layout with respect to each other, as well as how they respond to the size of the array. That sparked a very interesting back and forth with Pat from May until September (!). Pat eventually took the time to turn our informal exchange into a coherent paper. More than 3 years after I started spending time on the question of array layouts for implicit search trees, I found the research I was looking for… all it took was a bit of collaboration (:

Bonus: the results were unexpected! Neither usual suspects (B-tree or van Emde Boas) came out on top, even for very large arrays. I was also surprised to see the breadth-first layout perform much better than straight binary search: none of the usual explanations made sense to me. It turns out that the improved performance (when people weren’t testing on round, power of two, array sizes) was probably an unintended consequence of bad code! Breadth-first is fast, faster than layouts with better cache efficiency, because it prefetches well enough to hide latency even when it extracts only one bit of information from each cache line; its performance has nothing to do with cachability. Our code prefetches explicitly, but slower branchy implementations in the wild get implicit prefetching, thanks to speculative execution.

Conclusion: if you need to do a lot of comparison-based searches in > L2-sized arrays, use a breadth-first order and prefetch. If you need sorted arrays, consider sticking some prefetches in a decent binary search loop. If only I’d known that in 2012!

Comp{ress,ilat}ion

A couple months ago, I found LZ77-like Compression with Fast Random Access by Kreft and Navarro. They describe a Lempel-Ziv approach that is similar to LZ77, but better suited to decompressing arbitrary substrings. The hard part about applying LZ77 compression to (byte)code is that parses may reuse any substring that happens to appear earlier in the original text. That’s why I had to use Jez’s algorithm to convert the LZ77 parse into a (one word) grammar.

LZ-End fixes that.

Kreft and Navarro improve random access decompression by restricting the format of “backreferences” in the LZ parse. The parse decomposes the original string into a sequence of phrases; concatenating the phrases yields the string back, and phrases have a compact representation. In LZ77, phrases are compressed because they refer back to substrings in prior phrases. LZ-End adds another constraint: the backreferences cannot end in the middle of phrases.

For example, LZ77 might have a backreference like

[abc][def][ghi]
   ---------

to represent “cdefg.” LZ-End would be forced to end the new phrase at “f”

[abc][def][ghi]
   -------

and only represent “cdef.” The paper shows that this additional restriction has a marginal impact on compression rate, and uses the structure to speed up operations on compressed data. (The formal definition also forbids the cute/annoying self-reference-as-loop idiom of LZ77, without losing too much compression power!)

We can apply the same idea to compress code. Each phrase is now a subroutine with a return at the end. A backreference is a series of calls to subroutines; the first call might begin in the middle, but matches always end on return, exactly like normal code does! A phrase might begin in the middle of a phrase that itself consists of calls. That’s still implementable: the referrer can see through the indirection and call in the middle of the callee’s callee (etc.), and then go back to the callee for a suitably aligned submatch.

That last step looks like it causes a space blowup, and I can’t bound it (yet).

But that’s OK, because I was only looking into compressing traces as a last resort. I’m much more interested in expression trees, but couldn’t find a way to canonicalize sets (e.g., arguments to integer +) and sequences (e.g., floating point *) so that similar collections have similar subtrees… until I read Hammer et al’s work on Nominal Adapton, which solves a similar problem in a different context.

They want a tree representation for lists and tries (sets/maps) such that a small change in the list/trie causes a small change in the tree that mostly preserves identical subtrees. They also want the representation to be a deterministic function of the list/trie. That way, they can efficiently reuse computations after incremental changes to inputs.

That’s exactly my sequence/set problem! I want a tree-based representation for sequences (lists) and sets (tries) such that similar sequences and sets have mostly identical subtrees for which I can reuse pre-generated code.

Nominal Adapton uses a hash-based construction described by Pugh and Teitelbaum in 1989 (Incremental computation via function caching) to represent lists, and extends the idea for tries. I can “just” use the same trick to canonicalise lists and sets into binary trees, and (probabilistically) get common subexpressions for free, even across expressions trees! It’s not perfect, but it should scale pretty well.

That’s what I’m currently exploring when it comes to using compression to reduce cache footprint while doing aggressive specialisation. Instead of finding redundancy in linearised bytecode after the fact, induce identical subtrees for similar expressions, and directly reuse code fragments for subexpressions.

More to come

I thought I’d post a snippet on the effect of alignment and virtual memory tricks on TLBs, but couldn’t find time for that. Perhaps later this week. In the meantime, I have to prepare a short talk on the software transactional memory system we built at AppNexus. Swing by 23rd Street on December 15 if you’re in New York!

Michael MalisLoops in Lisp Part 1: Goto

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

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

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)))
    `(tagbody
       ,gtop
       (if (not ,test)
           (go ,gend))
       ,@body
       (go ,gtop)
       ,gend)))

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:

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

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?

· 77 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++

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

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

· 89 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)
                  n
                  (+ (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)
      n
      (+ (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.


For older items, see the Planet Lisp Archives.


Last updated: 2016-02-08 02:16