Planet Lisp

drmeisterRelease 0.2 of clasp is available

· 56 minutes ago

I uploaded a new release of Clasp today (January 25th, 2015) that brings a lot of stability improvements, improved performance, improved compatibility with the Common Lisp standard and ASDF, SLIME and Quicklisp support.

It requires a reinstallation of externals-clasp.  We are working on eliminating the need for externals-clasp.

Features include:

  1. ASDF support has been added – it can be accessed using (require :asdf)
  2. SLIME support has been added and the changes to SLIME have been uploaded to the standard SLIME repository (https://github.com/slime/slime).  You should be able to access it the standard way you install and upgrade slime.
  3. Quicklisp support has been added.  I’ve submitted the changes to quicklisp to Zach Bean (the developer of quicklisp) and they should be available soon.
  4. Improvements in performance of the compiled code (Linux code is at least 2x faster).
  5. Improvements in stability.
  6. Almost all Common Lisp symbols have been implemented (18 left, you can see them using (core:calculate-missing-common-lisp-symbols).
  7. Example code for Clasp/C++ interoperation is available at https://github.com/drmeister/demo-clasp-cxx
  8. Weak-key-hash-tables, weak-pointer, weak-key-mapping types have been implemented in both garbage collectors.

This release focused on getting SLIME working because I want to incorporate a new compiler front end for Clasp and I want to do it in this extremely powerful programming environment.


Patrick SteinCons-Air (a.k.a. Lispers On A Plane)

· 3 days ago

Before bed last night, I was trying to sort out in my head the lineage and historical inter-relations between BKNR, TBNL, HTML-TEMPLATES, CL-WHO, and Hunchentoot. When my alarm went off this morning, I was having a dream about the Lisp community.

In my dream, there were about 50 Lispers on a prison plane. It was pretty much a commercial 737, but all of the passengers were wearing prison jumpsuits and the plane would never land. We were all just on the plane. We refueled in flight. (The dream had nothing to say about how we restocked with food or emptied the septic tanks. *shrug*)

There was a cage around/over the last three rows of the left side of the plane. The door to the cage was not locked, but everyone knew that you were only allowed to go into the cage if Edi let you. Edi Weitz was the top dog in this prison. The only reason the rest of us were still alive is because Edi hadn’t seen a reason to have us taken care of yet.

Didier Verna was the only person who was allowed to approach the cage if Edi were in it.

There wasn’t much turbulence, but we were flying through a thunderstorm. This had Nick Levine sitting at a window seat, looking out over the wing, nervously bobbing back and forth, and sipping whiskey with ice from a plastic cup.

The storm had Zach Beane pacing back and forth in the aisle.

Cyrus Harmon was sitting doing a crossword puzzle from the in-flight magazines, giggling to himself about Faré.

Faré was standing near the front of the plane throwing little packets of peanuts at everyone. He wasn’t trying to hurt people with them, but he was delighting in watching them bounce of the heads of people who weren’t expecting them (especially the back of Zach’s head when he was fifteen or twenty rows away).

Robert Goldman was trying to get some sleep, but was unable to do so because of the lack of leg-room, the bright cabin lights, and all of the packets of peanuts careening past.

There were a number of other Lisp-folk in this dream. For some of them, I don’t recall exactly what they were up to. For a few, it would probably be impolitic of me to say. :)

Dimitri FontaineMy First Slashdot Effect

· 3 days ago

Thanks to the Postgres Weekly issue #89 and a post to Hacker News front page (see Pgloader: A High-speed PostgreSQL Swiss Army Knife, Written in Lisp it well seems that I just had my first Slashdot effect...

Well actually you know what? I don't...

So please consider using the new mirror http://dimitri.github.io/pgloader/ and maybe voting on Hacker News for either tooling around your favorite database system, PostgreSQL or your favorite programming language, Common Lisp...

It all happens at https://news.ycombinator.com/item?id=8924270.

Coming to FOSDEM?

If you want to know more about pgloader and are visiting FOSDEM PGDAY or plain FOSDEM I'll be there talking about Migrating to PostgreSQL, the new story (that's pgloader) and about some more reasons why You'd better have tested backups...

If you're not there on the Friday but still want to talk about pgloader, join us at the PostgreSQL devroom and booth!

LispjobsTwo Clojure positions, AppsFlyer, Herzliya, Israel

· 5 days ago

Server-side Developer: Herzliya, Israel

We are coding commandos with strong product sense. Most of the code we write is operative in hours to days. We insist that you write something operational in your first two days. We decide and move fast, and iterate faster. If you are ready to write production code in Clojure, If you are ready to write the most exciting code of your life - If you are ready to jump on stage and let your code play - come and join us.

Responsibilities:

Write good, robust, simple, fast and meaningful code that can handle billions of hits
Qualifications:

Strong web experience (at least 5 years)
Strong coding ability and architecture familiarity combined with product sense
Experience with Linux (Ubuntu), AWS / EC2, Continuous Deployment (SaltStack, Chef, Puppet)
Experience with Python, Redis, ZeroMQ, CouchDB, MongoDB
Experience with distributed systems
Experience with monitoring tools (Nagios, Graphite)
Product management understanding
Experience working with clients - an advantage
Mobile experience (iOS, Android) - an advantage
Digital advertising experience - an advantage

Contact: Adi Shacham-Shavit <adi@appsflyer.com>

Dev Team Leader: Herzliya, Israel

We are looking for a technologies in hart, with passionate to distributed production systems and excellent development abilities to join our team.

Responsibilities:
Lead a small development team to write good, robust, simple, fast and meaningful code that can handle billions of hits
Qualifications:

Strong web experience (at least 5 years)
Strong coding ability and architecture familiarity combined with product sense
Experience with Linux (Ubuntu), AWS / EC2, Continuous Deployment (Chef etc.)
Experience with NoSQL databases, like Redis, Couchbase, MongoDB
Manage team of 2-3 developers (at least 1 year)
Exceptionally self-motivated, have a “get things done” mentality
Experience working with clients - an advantage
Mobile experience (iOS, Android) - an advantage
Digital advertising experience - an advantage

Contact: Adi Shacham-Shavit <adi@appsflyer.com>


LispjobsSoftware Engineer - Functional (Clojure), ROKT, North Sydney, NSW, Australia

· 5 days ago

Exceptional opportunity to join one of the fastest growing Australian technology start-ups
— Well-funded
— High growth phase

The Positions
ROKT is seeking a number of functional programmers (ideally with experience in Clojure) at all levels of seniority. The positions involve the continued development and maintenance of established production Clojure code (principally related to data transformation, analysis and predictive optimisation) as well as the development of new products and services.

Successful candidates will join a growing team of ~10 engineers, predominantly developing on a Microsoft/AWS stack at present – we're looking at considerable expansion of our engineering capability this year, a significant part of which includes broadening and accelerating our adoption of the Clojure ecosystem.

The Company
ROKT is a rapidly growing innovative technology company. At ROKT you will have the opportunity to work in a fast paced environment with very smart and talented people.

Recognised as one of the hottest companies in our field, ROKT is in a unique position to continue to lead the market with data driven technology solutions that deliver innovation to publishers, ecommerce platforms and advertisers. With a proven technology platform, an established and growing partner portfolio, and outstanding growth, this is a unique opportunity to join a fast paced Australian technology start-up.

Benefits
— Competitive packages based on qualifications and experience
— Employee share scheme
— Health and wellness initiatives
— Staff awards program; generous staff referral program
— Office snacks & fruit
— Global company gathering and celebration 3 times a year
— Get paid to write Clojure!

Skills, Experience and Education
— A bachelor's degree in Computer Science or similar discipline
— Previous experience (commercial or demonstrable personal experience) with functional programming in Clojure, or Common Lisp.
— A level of experience that demonstrates competency in a spectrum of development skills, from our chosen development methodology (Agile XP/Scrum) through to discipline in testing, documentation etc.
— Strong SQL skills, "big data" experience, and familiarity with AWS is considered highly desirable
— Excellent verbal and written communication skills

Location
North Sydney, NSW, Australia

Join us
Interested candidates should submit CVs to Claudio Natoli – claudio@rokt.com


Didier VernaELS 2015 programme committee members announced

· 6 days ago

The programme committee members for this year's European Lisp Symposium has just been announced. Ladies and gentlemen, please welcome, on the keyboards...

Gábor MelisRecurrent Nets

· 6 days ago

I've been cleaning up and documenting MGL for quite some time now and while it's nowhere near done, a good portion of the code has been overhauled in the process. There are new additions such as the Adam optimizer and Recurrent Neural Nets. My efforts were mainly only the backprop stuff and I think the definition of feed-forward:

 (build-fnn (:class 'digit-fnn)
   (input (->input :size *n-inputs*))
   (hidden-activation (->activation :inputs (list input)
                                    :size n-hiddens))
   (hidden (->rectified :x hidden-activation))
   (output-activation (->activation :inputs (list hidden)
                                    :size *n-outputs*))
   (output (->softmax-xe-loss :x output-activation)))

and recurrent nets:

 (build-rnn ()
   (build-fnn (:class 'sum-sign-fnn)
     (input (->input :size 1))
     (h (->lstm :name 'h :inputs (list input) :n-cells n-hiddens))
     (prediction (->softmax-xe-loss
                  :x (->activation :name 'prediction
                                   :size *n-outputs*
                                   :inputs (list h))))))

is fairly straight-forward already. There is still much code that needs to accompany such a network definition, mostly having to do with how to give inputs and prediction targets to the network and also with monitoring training. See the full examples for feed-forward and recurrent nets in the documentation.

Dimitri FontaineNew release: pgloader 3.2

· 9 days ago

PostgreSQL comes with an awesome bulk copy protocol and tooling best known as the COPY and \copy commands. Being a transactional system, PostgreSQL COPY implementation will ROLLBACK any work done if a single error is found in the data set you're importing. That's the reason why pgloader got started: it provides with error handling for the COPY protocol.

That's basically what pgloader used to be all about

As soon as we have the capability to load data from unreliable sources, another use case appears on the horizon, and soon enough pgloader grew the capacity to load data from other databases, some having a more liberal notion of what is sane data type input.

To be able to adapt to advanced use cases in database data migration support, pgloader has grown an advanced command language wherein you can define your own load-time data projection and transformations, and your own type casting rules too.

New in version 3.2 is that in simple cases, you don't need that command file any more. Check out the pgloader quick start page to see some examples where you can use pgloader all from your command line!

Here's one such example, migrating a whole MySQL database data set over to PostgreSQL, including automated schema discovery, automated type casting and on-the-fly data cleanup (think about zero dates or booleans in tinyint(1) disguise), support for indexes, primary keys, foreign keys and comments. It's as simple as:

$ createdb sakila
$ pgloader mysql://root@localhost/sakila pgsql:///sakila
2015-01-16T09:49:36.068000+01:00 LOG Main logs in '/private/tmp/pgloader/pgloader.log'
2015-01-16T09:49:36.074000+01:00 LOG Data errors in '/private/tmp/pgloader/'
                    table name       read   imported     errors            time
------------------------------  ---------  ---------  ---------  --------------
               fetch meta data         43         43          0          0.222s
                  create, drop          0         36          0          0.130s
------------------------------  ---------  ---------  ---------  --------------
                         actor        200        200          0          0.133s
                       address        603        603          0          0.035s
                      category         16         16          0          0.027s
                          city        600        600          0          0.018s
                       country        109        109          0          0.017s
                      customer        599        599          0          0.035s
                          film       1000       1000          0          0.075s
                    film_actor       5462       5462          0          0.147s
                 film_category       1000       1000          0          0.035s
                     film_text       1000       1000          0          0.053s
                     inventory       4581       4581          0          0.086s
                      language          6          6          0          0.041s
                       payment      16049      16049          0          0.436s
                        rental      16044      16044          0          0.474s
                         staff          2          2          0          0.170s
                         store          2          2          0          0.010s
        Index Build Completion          0          0          0          0.000s
------------------------------  ---------  ---------  ---------  --------------
                Create Indexes         40         40          0          0.343s
               Reset Sequences          0         13          0          0.026s
                  Primary Keys         16         14          2          0.013s
                  Foreign Keys         22         22          0          0.078s
                      Comments          0          0          0          0.000s
------------------------------  ---------  ---------  ---------  --------------
             Total import time      47273      47273          0          2.261s

Other options are available to support a variety of input file formats, including compressed csv files found on a remote location, as in:

curl http://pgsql.tapoueh.org/temp/2013_Gaz_113CDs_national.txt.gz \
    | gunzip -c                                                        \
    | pgloader --type csv                                              \
               --field "usps,geoid,aland,awater,aland_sqmi,awater_sqmi,intptlat,intptlong" \
               --with "skip header = 1"                                \
               --with "fields terminated by '\t'"                      \
               -                                                       \
               postgresql:///pgloader?districts_longlat

2015-01-16T10:09:06.027000+01:00 LOG Main logs in '/private/tmp/pgloader/pgloader.log'
2015-01-16T10:09:06.032000+01:00 LOG Data errors in '/private/tmp/pgloader/'
                    table name       read   imported     errors            time
------------------------------  ---------  ---------  ---------  --------------
                         fetch          0          0          0          0.010s
------------------------------  ---------  ---------  ---------  --------------
             districts_longlat        440        440          0          0.087s
------------------------------  ---------  ---------  ---------  --------------
             Total import time        440        440          0          0.097s

As usual in unix commands, the - input filename stands for standard input and allows streaming data from a remote compressed file down to PostgreSQL.

So if you have any data loading job, including data migrations from SQLite, MySQL or MS SQL server: have a look at pgloader!

LispjobsAmazon still hiring Clojure software developers (Seattle, Washington)

· 10 days ago

I received an email from the Amazon recruiter, and they say they are looking for more Clojure candidates. Please refer to the previous post if you’re interested:

https://lispjobs.wordpress.com/2014/11/25/clojure-software-development-engineers-amazon-com/


Didier VernaInsider Threat Detection at Haystax

· 11 days ago

Reported to me by Craig Norvell: Haystax appears to have some interesting Lisp projects in the works. Combining Lisp, Prolog, RDF (AllegroGraph), and a BBN for insider threat detection solutions.

From their website:

Haystax's predictive models are continuously updated based on the prevailing threat environment making it highly suitable for both detection and continuous evaluation of threats. These unique models go beyond traditional web and business intelligence to enable organizations to achieve contextual real-time situational awareness by fusing all operationally relevant information - private, public, video and live feeds - into consolidated views to show patterns and identify threats that are usually buried in too much noise or not placed in proper context.

Here is a Technical paper, and the STIDS Conference website. If you are interested, it looks like you can also attend a webcast on January 21st.

Quicklisp newsJanuary 2015 Quicklisp dist update now available

· 11 days ago
New projects:
Updated projects: arc-compat, avatar-api, blackbird, buildnode, caveman, cl-acronyms, cl-ana, cl-ansi-text, cl-async, cl-autowrap, cl-base58, cl-creditcard, cl-dbi, cl-gss, cl-inflector, cl-libuv, cl-marshal, cl-mock, cl-mustache, cl-opengl, cl-pass, cl-rabbit, cl-randist, cl-random, cl-sdl2, cl-virtualbox, cl-webkit, clack, clack-errors, clos-fixtures, closer-mop, clss, clx, colleen, com.informatimago, commonqt, corona, crane, css-selectors, datafly, eco, esrap, exponential-backoff, fast-http, fset, gbbopen, gendl, hdf5-cffi, hermetic, http-body, hu.dwim.stefil, integral, introspect-environment, iolib, jsown, lambda-fiddle, lisp-unit2, local-time, lol-re, ltk, mk-string-metrics, modularize, modularize-hooks, modularize-interfaces, new-op, osicat, plump, plump-tex, pp-toml, prove, pzmq, quri, rock, rutils, scalpl, sdl2kit, serapeum, sheeple, slime, spinneret, stumpwm, sxql, template, trivial-arguments, trivial-download, trivial-extract, trivial-features, trivial-garbage, weblocks, weblocks-utils, websocket-driver, woo, wookie, wuwei, xsubseq.

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

To install exactly this update, use (ql-dist:install-dist "http://beta.quicklisp.org/dist/quicklisp/2015-01-13/distinfo.txt" :replace t).

This Quicklisp update is supported by my employer, Clozure Associates. If you need commercial support for Quicklisp, or any other Common Lisp programming needs, it's available via Clozure Associates.

LispjobsCommon Lisp Developer, RavenPack, Marbella, Spain

· 12 days ago

See: http://www.ravenpack.com/company/careers/#lisp

Position immediately available for an experienced software professional. You will work with an international team of developers skilled in Common Lisp, PL/SQL, Java and Python.

The ideal candidate will have excellent skills as a software engineer, with a strong computer science background and professional experience delivering quality software.  You must be fluent in modern software development practices, including multi-threading, distributed systems, and cloud computing.  If you are not already an expert in Common Lisp, you aspire to become one. Innovative problem solving and engaging human interaction drive you. With high degree of independence, you will design and implement maintainable software in Common Lisp based on loose and changing specifications.

Familiarity with SQL including query optimization and PL/SQL is very much a plus.  Comfort in a growing, fast-paced environment with a premium on problem solving is required.  Must be adaptable and willing to learn new technologies. You work successfully in a small team environment, with a willingness to teach and to learn. Lead reviews of your code and participate in the reviews of others.

The ability to communicate effectively in English, both in writing and verbally is a must. Knowledge of Spanish is not a business requirement. European Union legal working status is strongly preferred.


Paul KhuongLock-free Sequence Locks

· 12 days ago

Specialised locking schemes and lock-free data structures are a big part of my work these days. I think the main reason the situation is tenable is that, very early on, smart people decided to focus on an SPMC architecture: single writer (producer), multiple readers (consumers).

As programmers, we have a tendency to try and maximise generality: if we can support multiple writers, why would one bother with measly SPMC systems? The thing is SPMC is harder than SPSC, and MPMC is even more complex. Usually, more concurrency means programs are harder to get right, harder to scale and harder to maintain. Worse: it also makes it more difficult to provide theoretical progress guarantees.

Apart from architecting around simple cases, there’s a few ways to deal with this reality. We can define new, weaker, classes of program, like obstruction-freedom: a system is obstruction-free when one thread is guaranteed to make progress if every other thread is suspended. We can also weaken the guarantees of our data structure. For example, rather than exposing a single FIFO, we could distribute load and contention across multiple queues; we lose strict FIFO order, but we also eliminate a system bottleneck. Another option is to try and identify how real computers are more powerful than our abstract models: some argue that, realistically, many lock-free schemes are wait-free, and others exploit the fact that x86-TSO machines have finite store buffers.

Last week, I got lost doodling with x86-specific cross-modifying code, but still stumbled on a cute example of a simple lock-free protocol: lock-free sequence locks. This sounds like an oxymoron, but I promise it makes sense.

Lock-free sequence locks

It helps to define the terms better. Lock-freedom means that the overall system will always make progress, even if some (but not all) threads are suspended. Classical sequence locks are an optimistic form of write-biased reader/writer locks: concurrent writes are forbidden (e.g., with a spinlock), read transactions abort whenever they observe that writes are in progress, and a generation counter avoids ABA problems (when a read transaction would observe that no write is in progress before and after a quick write).

In Transactional Mutex Locks (PDF), sequence locks proved to have enviable performance on small systems and scaled decently well for read-heavy workloads. They even allowed lazy upgrades from reader to writer by atomically checking that the generation has the expected value when acquiring the sequence lock for writes. However, we lose nearly all progress guarantees: one suspended writer can freeze the whole system.

The central trick of lock-freedom is cooperation: it doesn’t matter if a thread is suspended in the middle of a critical section, as long as any other thread that would block can instead complete the work that remains. In general, this is pretty hard, but we can come up with restricted use cases that are idempotent. For lock-free sequence locks, the critical section is a precomputed set of writes: a series of assignments that must appear to execute atomically. It’s fine if writes happen multiple times, as long as they stop before we move on to another set of writes.

There’s a primitive based on compare-and-swap that can easily achieve such conditional writes: restricted double compare and single swap (RDCSS, introduced in A Practical Multi-Word Compare-and-Swap (PDF)). RDCSS atomically checks if both a control word (e.g., a generation counter) and a data word (a mutable cell) have the expected values and, if so, writes a new value in the data word. The pseudocode for regular writes looks like

if (CAS(self.data, self.old, self) == fail) {
    return fail;
}

if (*self.control != self.expected) {
    CAS(self.data, self, self.old);
    return fail;
}

CAS(self.data, self, self.new);
return success;

The trick is that, if the first CAS succeeds, we always know how to undo it (data’s old value must be self.old), and that information is stored in self so any thread that observes the first CAS has enough information to complete or rollback the RDCSS. The only annoying part is that we need a two-phase commit: reserve data, confirm that control is as expected, and only then write to data.

For the cost of two compare-and-swap per write – plus one to acquire the sequence lock – writers don’t lock out other writers (writers help each other make progress instead). Threads (especially readers) can still suffer from starvation, but at least the set of writes can be published ahead of time, so readers can even lookup in that set rather than waiting for/helping writes to complete. The generation counter remains a bottleneck, but, as long as writes are short and happen rarely, that seems like an acceptable trade to avoid the 3n CAS in multi-word compare and swap.

Real code

Here’s what the scheme looks like in SBCL.

First, a mutable box because we don’t have raw pointers (I could also have tried to revive my sb-locative hack) in CL.

1
2
3
(defstruct (box
            (:constructor make-box (%value)))
  %value)

Next, the type for write records: we have the the value for the next generation (once the write is complete) and a hash table of box to pairs of old and new values. There’s a key difference with the way RDCSS is used to implement multiple compare and swap: we don’t check for mismatches in the old value and simply assume that it is correct.

1
2
3
4
5
6
7
(defstruct (record
             (:constructor %make-record (generation ops)))
  (generation (error "Missing arg") :type fixnum :read-only t)
  ;; map of box -> (cons old new).  I use a hash table for
  ;; convenience but I doubt it's the right choice.
  (ops (error "Missing arg") :type hash-table :read-only t))
(declaim (freeze-type record))

The central bottleneck is the sequence lock, which each (read) transaction must snapshot before attempting to read consistent values.

1
2
3
4
5
6
7
8
9
10
(declaim (type (or (and unsigned-byte fixnum) record) **current-record**))
(defglobal **current-record** 0)

(defvar *initial-record*)

(defun snapshot-generation ()
  (let ((initial *initial-record*))
    (if (record-p initial)
        (record-generation initial)
        initial)))

The generation associated with a snapshot is the snapshot if it is a positive fixnum, otherwise it is the write record’s generation.

Before using any read, we make sure that the generation counter hasn’t changed.

1
2
3
4
5
6
7
8
(defun check ()
  #-(or x86 x86-64) (sb-thread:barrier (:read)) ; x86 don't reorder reads
  (let ((initial *initial-record*)
        (current **current-record**))
    (unless (or (eql initial current)
                (and (record-p initial)
                     (eql (record-generation initial) current)))
      (throw 'fail t))))

I see two ways to deal with starting a read transaction while a write is in progress: we can help the write complete, or we can overlay the write on top of the current heap in software. I chose the latter: reads can already be started by writers. If a write is in progress when we start a transaction, we stash the write set in *current-map* and lookup there first:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defvar *current-map* nil)

(defun box-value (box)
  (prog1 (let* ((map *current-map*)
                (value (if map
                           (cdr (gethash box map (box-%value box)))
                           (box-%value box))))
           (if (record-p value)
               ;; if we observe a record, either a new write is in
               ;; progress and (check) is about to fail, or this is
               ;; for an old (already completed) write that succeeded
               ;; partially by accident.  In the second case, we want
               ;; the *old* value.
               (car (gethash box (record-ops value)))
               value))
    (check)))

We’re now ready to start read transactions. We take a snapshot of the generation counter, update *current-map*, and try to execute a function that uses box-value. Again, we don’t need a read-read barrier on x86oids (nor on SPARC, but SBCL doesn’t have threads on that platform).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun call-with-transaction (function &rest; arguments)
  (catch 'fail
    (let* ((*initial-record* **current-record**)
           (*current-map* (and (record-p *initial-record*)
                               (record-ops *initial-record*))))
      #-(or x86 x86-64) (sb-thread:barrier (:read))
      (return-from call-with-transaction
        (values (apply function arguments) t))))
  (values nil nil))

(defmacro with-transaction ((&rest; bindings) &body; body)
  `(call-with-transaction (lambda ,(mapcar #'first bindings)
                            ,@body)
                          ,@(mapcar #'second bindings)))

The next function is the keystone: helping a write record go through exactly once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(defun help (record)
  (flet ((write-one (box old new)
           ;; if record isn't the current generation anymore,
           ;; it has already been completed
           (unless (eq **current-record** record)
               (return-from help nil))
             (let ((actual (sb-ext:cas (box-%value box) old record)))
               (when (eql actual new) ;; already done? next!
                 (return-from write-one))
               
               ;; definite failure -> no write went though; leave.
               (unless (or (eql actual old)
                           (eql actual record))
                 (return-from help nil))

               ;; check for activity before the final write
               (unless (eq **current-record** record)
                 (sb-ext:cas (box-%value box) record old)
                 (return-from help nil))

               ;; Really perform write (this can only fail if
               ;; another thread already succeeded).
               (sb-ext:cas (box-%value box) record new))))
    (maphash (lambda (box op)
               (write-one box (car op) (cdr op)))
             (record-ops record)))
  ;; Success! move the generation counter forward.
  (eql record (sb-ext:cas (symbol-value '**current-record**)
                          record
                          (record-generation record))))

Now we can commit with a small wrapper around help. Transactional mutex lock has the idea of transaction that are directly created as write transactions. We assume that we always know how to undo writes, so transactions can only be upgraded from reader to writer. Committing a write will thus check that the generation counter is still consistent with the (read) transaction before publishing the new write set and helping it forward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defun commit (record)
  (check-type record record)
  (let ((initial
          (loop
           (let ((value **current-record**))
             (check)
             (if (record-p value)
                 (help value)
                 (return value))))))
    (unless (and (eql (sb-ext:cas (symbol-value '**current-record**)
                                  initial record)
                      initial)
                 (help record))
      (throw 'fail t))
    t))

And now some syntactic sugar to schedule writes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(defvar *write-record*)

(defun call-with-write-record (function)
  (let ((*write-record* (%make-record (mod (1+ (snapshot-generation))
                                           (1+ most-positive-fixnum))
                                      (make-hash-table))))
    (multiple-value-prog1 (funcall function)
      (commit *write-record*))))

(defun (setf box-value) (value box)
  (setf (gethash box (record-ops *write-record*))
        (cons (box-value box) value))
  value)

(defmacro with-write (() &body; body)
  `(call-with-write-record (lambda ()
                             ,@body)))

That’s enough for a smoke test on my dual core laptop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(defvar *a* (make-box 0))
(defvar *b* (make-box 0))
(defvar *semaphore* (sb-thread:make-semaphore))

(defun test-reads (n)
  (let ((a *a*)
        (b *b*))
    (sb-thread:wait-on-semaphore *semaphore*)
    (loop repeat n
          count (with-transaction ()
                  (assert (eql (box-value a) (box-value b)))
                  t))))

(defun test-writes (n)
  (let ((a *a*)
        (b *b*))
    (sb-thread:wait-on-semaphore *semaphore*)
    (loop repeat n
          count (with-transaction ()
                  (with-write ()
                    (incf (box-value a))
                    (incf (box-value b)))
                  t))))

The function test-reads counts the number of successful read transactions and checks that (box-value a) and (box-value b) are always equal. That consistency is preserved by test-writes, which counts the number of times it succeeds in incrementing both (box-value a) and (box-value b).

The baseline case should probably be serial execution, while the ideal case for transactional mutex lock is when there is at most one writer. Hopefully, lock-free sequence locks also does well when there are multiple writers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
(defun test-serial (n)
  (setf *a* (make-box 0)
        *b* (make-box 0)
        *semaphore* (sb-thread:make-semaphore :count 4))
  (list (test-reads (* 10 n))
        (test-reads (* 10 n))
        (test-writes n)
        (test-writes n)))

(defun test-single-writer (n)
  (setf *a* (make-box 0)
        *b* (make-box 0)
        *semaphore* (sb-thread:make-semaphore))
  (let ((threads
          (list (sb-thread:make-thread #'test-reads :arguments (* 10 n))
                (sb-thread:make-thread #'test-reads :arguments (* 10 n))
                (sb-thread:make-thread #'test-writes
                                       :arguments (ceiling (* 1.45 n))))))
    (sb-thread:signal-semaphore *semaphore* 3)
    (mapcar (lambda (x)
              (ignore-errors (sb-thread:join-thread x)))
            threads)))

(defun test-multiple-writers (n)
  (setf *a* (make-box 0)
        *b* (make-box 0)
        *semaphore* (sb-thread:make-semaphore))
  (let ((threads
          (list (sb-thread:make-thread #'test-reads :arguments (* 10 n))
                (sb-thread:make-thread #'test-reads :arguments (* 10 n))
                (sb-thread:make-thread #'test-writes :arguments n)
                (sb-thread:make-thread #'test-writes :arguments n))))
    (sb-thread:signal-semaphore *semaphore* 4)
    (mapcar (lambda (x)
              (ignore-errors (sb-thread:join-thread x)))
            threads)))

Let’s try this!

First, the serial case. As expected, all the transactions succeed, in 6.929 seconds total (6.628 without GC time). With one writer and two readers, all the writes succeed (as expected), and 98.5% of reads do as well; all that in 4.186 non-GC seconds, a 65% speed up. Finally, with two writers and two readers, 76% of writes and 98.5% of reads complete in 4.481 non-GC seconds. That 7% slowdown compared to the single-writer case is pretty good: my laptop only has two cores, so I would expect more aborts on reads and a lot more contention with, e.g., a spinlock.

CL-USER> (gc :full t) (time (test-serial 1000000))
Evaluation took:
  6.929 seconds of real time
  6.944531 seconds of total run time (6.750770 user, 0.193761 system)
  [ Run times consist of 0.301 seconds GC time, and 6.644 seconds non-GC time. ]
  100.23% CPU
  11,063,956,432 processor cycles
  3,104,014,784 bytes consed

(10000000 10000000 1000000 1000000)
CL-USER> (gc :full t) (time (test-single-writer 1000000))
Evaluation took:
  4.429 seconds of real time
  6.465016 seconds of total run time (5.873936 user, 0.591080 system)
  [ Run times consist of 0.243 seconds GC time, and 6.223 seconds non-GC time. ]
  145.97% CPU
  6,938,703,856 processor cycles
  2,426,404,384 bytes consed

(9863611 9867095 1450000)
CL-USER> (gc :full t) (time (test-multiple-writers 1000000))
Evaluation took:
  4.782 seconds of real time
  8.573603 seconds of total run time (7.644405 user, 0.929198 system)
  [ Run times consist of 0.301 seconds GC time, and 8.273 seconds non-GC time. ]
  179.30% CPU
  7,349,757,592 processor cycles
  3,094,950,400 bytes consed

(9850173 9853102 737722 730614)

How does a straight mutex do with four threads?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(defun test-mutex (n)
  (let ((mutex (sb-thread:make-mutex))
        (semaphore (sb-thread:make-semaphore))
        (a 0)
        (b 0))
    (flet ((reader (n)
             (sb-thread:wait-on-semaphore semaphore)
             (loop repeat n do
               (sb-thread:with-mutex (mutex)
                 (assert (eql a b)))))
           (writer (n)
             (sb-thread:wait-on-semaphore semaphore)
             (loop repeat n do
               (sb-thread:with-mutex (mutex)
                 (incf a)
                 (incf b)))))
      (let ((threads
              (list (sb-thread:make-thread #'reader
                                           :arguments (* 10 n))
                    (sb-thread:make-thread #'reader
                                           :arguments (* 10 n))
                    (sb-thread:make-thread #'writer
                                           :arguments (ceiling (* .75 n)))
                    (sb-thread:make-thread #'writer
                                           :arguments (ceiling (* .75 n))))))
        (sb-thread:signal-semaphore semaphore 4)
        (mapc #'sb-thread:join-thread threads)))))
CL-USER> (gc :full t) (time (test-mutex 1000000))
Evaluation took:
  5.814 seconds of real time
  11.226734 seconds of total run time (11.169670 user, 0.057064 system)
  193.10% CPU
  9,248,370,000 processor cycles
  1,216 bytes consed

(#<SB-THREAD:THREAD FINISHED values: NIL {1003A6E1F3}>
 #<SB-THREAD:THREAD FINISHED values: NIL {1003A6E383}>
 #<SB-THREAD:THREAD FINISHED values: NIL {1003A6E513}>
 #<SB-THREAD:THREAD FINISHED values: NIL {1003A6E6A3}>)

There’s almost no allocation (there’s no write record), but the lack of read parallelism makes locks about 20% slower than the lock-free sequence lock. A reader-writer lock would probably close that gap. The difference is that the lock-free sequence lock has stronger guarantees in the worst case: no unlucky preemption (or crash, with shared memory IPC) can cause the whole system to stutter or even halt.

The results above correspond to my general experience. Lock-free algorithms aren’t always (or even regularly) more efficient than well thought out locking schemes; however, they are more robust and easier to reason about. When throughput is more than adequate, it makes sense to eliminate locks, not to improve the best or even the average case, but rather to eliminate a class of worst cases – including deadlocks.

P.S., here’s a sketch of the horrible cross-modifying code hack. It turns out that the instruction cache is fully coherent on (post-586) x86oids; the prefetch queue will even reset itself based on the linear (virtual) address of writes. With a single atomic byte write, we can turn a xchg (%rax), %rcx into xchg (%rbx), %rcx, where %rbx points to a location that’s safe to mutate arbitrarily. That’s an atomic store predicated on the value of a control word elsewhere (hidden in the instruction stream itself, in this case). We can then dedicate one sequence of machine to each transaction and reuse them via some Safe Memory Reclamation mechanism (PDF).

There’s one issue: even without preemption (if a writer is pre-empted, it should see the modified instruction upon rescheduling), stores can take pretty long to execute: in the worst case, the CPU has to translate to a physical address and wait for the bus lock. I’m pretty sure there’s a bound on how long a xchg m, r64 can take, but I couldn’t find any documentation on hard figure. If we knew that xchg m, r64 never lasts more than, e.g., 10k cycles, a program could wait that many cycles before enqueueing a new write. That wait is bounded and, as long as writes are disabled very rarely, should improve the worst-case behaviour without affecting the average throughput.

Colin LuptonLearn Lisp The Hard Way, now brought to you by LispTO

· 17 days ago

It is with great pleasure that I announce that Learn Lisp The Hard Way is now an official, collaborative project of the Toronto Lisp User Group; and we are now accepting donations specifically for this project through PayPal. I will still be participating in the exact same capacity, but hopefully this change will help LLTHW become the definitive introduction to Common Lisp significantly faster. In particular I would like to welcome Leo “Inaimathi” Zovic as a co-author—the author of cl-notebook, cl-css, formlets, and many other excellent Lisp libraries—although other members of LispTO have expressed interest as well.

I would also like to ask the Lisp Community at large to consider contributing original text and source code examples, for the book itself, the interactive tutorial powered by David Vázquez Púa’s JSCL, and the drop-down CL language reference. Ideally, for the language reference, I would like to partner up with Robert Strandh’s project, CL-reference, to create a definitive, public domain reference to the Common Lisp standard. You can visit the new repository at: http://github.com/LispTO/llthw and submit a pull request if you would like to contribute.

Please be advised, that it is our intention to bring this title to print in addition to providing the complete book text online for free in perpetuity, so all contributors to the book text should be prepared to sign a contract and royalty schedule when the first edition is complete—towards this end I have updated the license of the book text to a Creative Commons Attribution-NoDerivatives 4.0 International License. However, there are a lot of other ways to contribute to the site and project in general, so if you don’t want to sign anything and still want to participate, you have a lot of options—the rest of the project remains MIT Licensed.

For those of you in the Lisp community that have already shown support for this project and contributed as peer reviewers and editors, be sure to create an issue on the repo and say if you would like to be identified as a contributor to this project. Your feedback has already made a big difference, and I hope to see you all on github!


Zach BeaneCorman Lisp sources are now available

· 20 days ago

Corman Lisp sources are now available on github under the MIT license.

In 1998, Roger Corman announced his new project, Corman Lisp, to comp.lang.lisp:

On Lisp’s 40th birthday, I am pleased to announce a new Common Lisp compiler and development environment for Windows 95/98/NT. This is a full featured system with very fast performance (competitive with the fastest Windows Common Lisps) and full support for using Win32 to build applications. It compiles to machine code (no interpreter is included), supports OS-level threads (minimal support now, more under development) save-image, save-application, etc.

The compiler is free, and I am distributing the source code along with it (in Common Lisp). A free console app may be used to interact with the compiler (a listener) but the included IDE application provides a much richer lisp-enhanced editor and development environment. I plan to ask a modest license fee for the IDE, although details are not finished. The included evaluation copy of the IDE is fully functional for 30 days, after which it will add a nag dialog (and I hope to have licensing details finalized by then).

I know many of you in this newsgroup will be both interested and possibly skeptical of this system, and I encourage you to please download a copy and try it out. I have included some documentation (in the form of a Word 97 format manual) but have not had time to document it extensively. Any of you who get back to me with helpful feedback I will be happy to repay you with a free registration code for the IDE.

I am the developer of PowerLisp for the Macintosh, which has been useful for many years for a large number of people. This new product, called Corman Lisp, is far superior, however, and has been written from the ground up for the Win32 environment. I have been working on it for over 2 years, and am eager to get some feedback. I believe it will fill an important niche and make Common Lisp a more viable development platform.

It filled a void in the Common Lisp world. Roger later wrote:

When Corman Lisp was first developed in the late 90s, there was really no competition on Windows platforms. Franz only had a 16-bit Lisp they were selling, and not really taking the Windows market seriously. Mac Common Lisp was on 680x0 and later PowerPC but didn’t get to Windows for a very long time, and LispWorks didn’t support Windows until much later. Now I think most all of those have good implementations on Windows (though only MCL is free). I have used Allegro extensively for a large contract with SRI and I see the value of a mature cross-platform system like they have. It is however extremely expensive, and developing applications for distribution requires lots of negotiation and per-license payments to Franz. Corman Lisp still has some advantages, I think—it is really a good hackers Lisp, when you want to easily get down into the assembly level, or in the guts of the compiler, to do almost anything. You have the power of Lisp to do those things with macros and a nice high-level dynamic environment.

The final release, 3.0, came out in 2006.

In 2013, I contacted Roger about the future of Corman Lisp. He decided it would be good to release the sources under a permissive license. At the start of 2015, he allowed me to update and publish the source code with the MIT license.

The code isn’t something you can use right away in a modern environment. Here’s Roger’s take:

I see two primary issues at this point. First, the Corman Lisp kernel needs to be built with Visual Studio 2005, which is an old version of VS. At one point I built it with VS2008 and it built and ran, but some problem with the FFI caused applications saved, and the IDE, to have problems. This type of thing is fairly common as Microsoft makes subtle changes to the code generation of their C compiler, which in turn affects the Lisp kernel which has very tight rules about how it expects its code to look. I did a lot to reduce the kernel (move things from the kernel to Lisp code, which is then compiled safely), but did not fully resolve the VS 2008 issues. Now there is VS 2010 and 2012, and I never tried building with either of those. In general I find each newer version of VS is worse for native C/C++ debugging, as .NET has become Microsoft’s primary platform for new software.

The other issue is running on 64-bit OS. Again, the FFI misbehaves when you have saved an application, or just doing a bunch of FFI stuff in an application. It is something to do with GC and the 64-bit support for running 32-bit applications (which is what CL is). It could be related to the same issue as I encountered with building under VS2008.

Tracking down this problem is difficult.

Regarding converting to a full 64-bit Lisp, this would be a much bigger effort. Corman Lisp gets such good performance by a large amount of hand-optimized x86 assembly code. This would all have to be rewritten/replaced in a 64-bit Lisp.

And:

Going forward with the code, I would probably say that the first step is getting the kernel (Corman Lisp server) to compile using a new version of MS Visual Studio (such as VS2012 or VS2013)—it was last compiled with VS2005. I tried at one point to get it to build with VS2008 (and I think the project files are still there) but ran into some bugs and didn’t resolve them.

Getting the kernel to compile properly and the GC and FFI to work properly is tricky. The kernel is very sensitive to the generated code, and you pretty much have to disable all optimizations (since the GC depends on things like proper stack frames and the various code patterns when it is looking for references). The Makefiles and project files should have the settings set correctly (for VS2005) but newer compiler versions try to add new sophisticated optimizations, which then causes new issues.

Turning off optimizations shouldn’t really negatively affect performance, as most of the kernel code gets replaced by compiled Lisp code during the build process. Some functions don’t, however (the kernel code generator, for instance) and these are probably the source of the compiled code sensitivity.

Even though it may not be easy to use directly, I think it’s fantastic that Roger has relicensed the code. It’s a piece of Common Lisp history. It was a real, shipping, commercial Common Lisp environment, with a compiler, garbage collector, standard Common Lisp library, IDE, and an interesting set of add-ons. I hope that it helps people understand implementation techniques and provides inspiration for future Common Lisp projects.

The source of Corman Lisp 3.0 is now available at https://github.com/sharplispers/cormanlisp.

Enjoy!

Christophe Rhodesa year in review

· 24 days ago

A brief retrospective, partly brought to you by grep:

Blogging's been a broad success; slightly tailed off of late, what with

so there's an obvious New Year's Resolution right there.

Happy New Year!

Nathan Froydironclad's history

· 26 days ago

Like a lot of Common Lisp packages that I've written, Ironclad was inspired by somebody else. The following is my recollection of the history of Ironclad.

In one of the perennial debates on comp.lang.lisp about whether Common Lisp was a decent large for writing high-performance code, Pierre R. Mai posted an implementation of MD5 written for CMUCL that was at least competitive with implementations written in C. (This was over a decade ago and MD5 was still on the cusp of being secure.) Hash algorithms were one place where people thought Common Lisp couldn't compete with C—the requirements for efficient, unboxed arithmetic were thought to be beyond the reach of Common Lisp implementations.

Given the close history of SBCL and CMUCL, Pierre's implementation was quickly made available as an addon in SBCL's contrib/ directory. Intrepid SBCL hackers Christophe Rhodes and Alexey Dejneka also figured out how to compile portable Common Lisp implementations of modulo-2^32 arithmetic into efficient machine code. Obviously, the portable implementation wasn't going to be equally efficient on all implementations, but it was a good starting point.

Being in college, and needing something to avoid doing work for my classes, I started writing an implementation of SHA-1 that could be added as a contrib to SBCL. It was rejected, for reasons that I can't recall, but seemed reasonable at the time. However, it also set me to thinking: it would be silly to have separate MD5, SHA-1, SHA-2, SHA-512, etc. packages; it would be difficult to swap out implementations if you needed to, and each package was likely to have slightly different naming conventions, calling conventions, etc. etc. What you really wanted was a common interface for all of them.

And thus was the first release of Ironclad conceived.

I will not detail here the exact path by which bits were added to Ironclad. Hash algorithms came first, and then the big names in encryption algorithms; the AES competition was taking place around this time, so I added a few of the promising candidates from that competition. Basic, functional, insecure versions of RSA were added. There wasn't any grand plan to what algorithms were chosen: anytime I felt that my studies were too tedious is when something tended to be added to Ironclad.

Various refactorings took place along the way. The encryption algorithms and encryption modes had been implemented with macros masquerading as C++ templates and as such, took quite a long time to compile when changes were made. Changing them to better utilize generic function dispatch improved compilation and load time while maintaining performance. I distinctly remember getting frustrated when several bugs were reported in hash algorithms and having to change several different copies of code multiple times. I had cut-and-pasted code because I wasn't convinced that proper refactorings could provide the same performance, but the maintenance burden convinced me to do some benchmarking, and it turned out I had been wrong.

The best refactoring took place when I was writing non-Ironclad code and realized that I would really like to read and write integers of different endiannesses. Ironclad had this capability, of course, but it seemed silly to pull all of Ironclad in for this one bit of functionality. Thus was nibbles split out as a separate library, and slowly it gained its own set of improvements (inline assembly for SBCL, for instance), which in turn improved Ironclad as well.

I work significantly less on Ironclad than I used to. I still try to answer questions and investigate bug reports filed on Github, and an occasional week of nights spent hacking will produce something useful. But personal factors (e.g. no longer being in college) have lessened my motivation to write Ironclad particularly and Common Lisp generally.

There have also been numerous changes in the cryptographic landscape over Ironclad's lifetime. Increasing emphasis has been placed on not merely having secure algorithms, but implementing them in a secure way. Ironclad blatantly ignores much of the received wisdom about implementing algorithms securely, and a thorough audit would turn up many rookie mistakes. (See, for instance, the list of best practices at cryptocoding.net.) Not to mention that some of the techniques for implementing algorithms securely would be well-nigh impossible to implement in portable Common Lisp (bit-masking of raw pointer values comes to mind). I don't have any good solutions to this problem in general; I suppose you could write appropriately unportable code for those implementations that expose the necessary bits, and provide wrappers to known-good crypto implementations in C. But half the fun of Ironclad was doing all of this in Common Lisp, rather than writing FFI code.

The public-key algorithm implementations are particularly bad; improving those would be a lot of work. All the cryptographic tricks alluded to above are likely required, and then there's also things like writing your own bignum library, since implementations's bignums were likely not written with cryptographic applications in mind. I simply do not have the inclination to track down all the relevant standards (for padding messages and the like), academic papers (for telling you how not to do things), and reading other crypto implementations (for showing you how things might be done properly, if you can puzzle out the why from the lack of comments) to do the requisite work.

However, it is clear that Ironclad has been useful despite its many flaws in this area; the patches and the well-wishes I have received over the years are abundant evidence of this. If people wanted to improve Ironclad, the following suggestions may prove useful:

Quicklisp newsClient update available: silent mode, improved system manifests, and more

· 34 days ago
Yesterday I uploaded a new version of the Quicklisp client code. (The client is the software responsible for fetching and managing Quicklisp-provided libraries.)

To get the update, use (ql:update-client).

Here's what's new:
Enjoy!

Luís OliveiraLOOP quiz

· 36 days ago
  1. Does (loop for i below 10 finally (return i)) return 9 or 10?
     
  2. Does (loop for i upto 10 finally (return i)) return 10 or 11?
     
  3. What does (loop for i below 10 for j upto 10 finally (return (list i j))) return?
     
  4. What about (loop for i below 10 and j upto 10 finally (return (list i j)))?

I stumbled upon the semantics of this last example in a recent bugfix and thought it was worth sharing. (Reminded me of the joke about what's hard in CS, too.)

Turns out LOOP's FOR ... AND not only mimics LET (rather than LET*) in terms of binding visibility, it also influences when the loop termination checks take place. That was new to me. I initially expected examples 3 and 4 to return the same values. What about you? Which ones, if any, did you get wrong? :-)

P.S.: LOOP for Black Belts is my favorite LOOP tutorial.

Quicklisp newsDecember 2014 Quicklisp dist update now available

· 38 days ago
New projects:
Updated projects: architecture.service-provider, asdf-linguist, asteroids, avatar-api, babel, basic-binary-ipc, caveman, chunga, cl-ana, cl-async, cl-async-future, cl-autowrap, cl-cffi-gtk, cl-closure-template, cl-conspack, cl-enumeration, cl-fad, cl-freetype2, cl-fuse, cl-gd, cl-gendoc, cl-glfw3, cl-inflector, cl-json, cl-libevent2, cl-logic, cl-mediawiki, cl-opengl, cl-pass, cl-plplot, cl-ppcre, cl-quickcheck, cl-read-macro-tokens, cl-rethinkdb, cl-rlimit, cl-sdl2, cl-unicode, cl-who, clack, clazy, clip, clod, closer-mop, clsql-helper, clss, coleslaw, colleen, com.informatimago, commonqt, consix, crane, curry-compose-reader-macros, daemon, dbus, defpackage-plus, documentation-template, drakma, drakma-async, eco, envy, esrap, esrap-liquid, external-program, fast-http, fast-io, flexi-streams, form-fiddle, fset, gbbopen, gendl, glyphs, green-threads, hdf5-cffi, helambdap, hunchensocket, hunchentoot, iolib, jsown, lass, local-time, log4cl, lquery, mcclim, mel-base, mgl-pax, modularize-interfaces, myway, new-op, ningle, plump, plump-tex, policy-cond, pp-toml, prove, pzmq, qlot, qmynd, qtools, quri, readable, restas, rock, sdl2kit, serapeum, sheeple, slime, smug, spinneret, staple, stumpwm, sxql, telnetlib, towers, trivial-ldap, trivial-mimes, trivial-raw-io, utilities.print-items, verbose, vom, weblocks, weblocks-stores, weblocks-tree-widget, weblocks-utils, websocket-driver, wookie, xhtmlambda, yason, zs3.

Removed projects: cl-api, cl-binaural, cl-proc, lisp-magick, okra.

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

This Quicklisp update is supported by my employer, Clozure Associates. If you need commercial support for Quicklisp, or any other Common Lisp programming needs, it's available via Clozure Associates.



Zach BeaneELIZA from 1966

· 39 days ago

A few days ago Jeff Shrager posted that James Markevitch translated some 1966 BBN paper tape source code with the oldest known Eliza program. (Jeff’s site, elizagen.org, tracks the genealogy of Eliza.)

image

Picture from elizagen.org

(doctor
   (lambda nil
      (prog (sentence keystack phraselist)
               (setsepr "
" " " "	")
               (setbrk "." "," ? | - + "(" 
")" L32 @ BS L14)
               (setq flipflop 0)
               (control t)
               (sentprint (quote (tell me your troubles"." 
please terminate input with an enter)))
               (setnone)
         a     (prin1 xarr)
               (makesentence)
               (cond
                  ((equal sentence (quote (goodbye)))
                     (return (sentprint (quote (it's been 
my pleasure))))))
               (analyze)
               (terpri)
               (go a)
         )))

The 1966 Eliza code is on github.

Jeff’s post prompted some historical context from Jeff Barrett:

The original Eliza was moved to the ANFS Q32 at SDC (one of the (D)ARPA block grant sites) in the mid 1960’s. The programmer responsible was John Burger who was involved with many early AI efforts. Somehow, John talked to one of the Playboy writers and the next thing we knew, there was an article in Playboy much to Weizenbaum’s and everybody else’s horror. We got all sorts of calls from therapists who read the article and wanted to contribute their “expertise” to make the program better. Eventually we prepared a stock letter and phone script to put off all of this free consulting.

The crisis passed when the unstoppable John Burger invited a husband and wife, both psychology profs at UCLA, to visit SDC and see the Doctor in action. I was assigned damage control and about lost it when both visitors laughed and kept saying the program was perfect! Finally, one of them caught their breath and finished the sentence: “This program is perfect to show our students just exactly how NOT to do Rogerian* therapy. *I think Rogerian was the term used but it’s been a while.

A little latter we were involved in the (D)ARPA Speech Understanding Research (SUR) Program and some of the group was there all hours of day and night. Spouses and significant others tended to visit particularly in the crazy night hours and kept getting in our way. We would amuse them by letting them use Eliza on the Q32 Time Sharing System. One day, the Q32 became unavailable in those off hours for a long period of time. We had a Raytheon 704 computer in the speech lab that I thought we could use to keep visitors happy some of the time. So one weekend I wrote an interpretive Lisp system for the 704 and debugged it the next Monday. The sole purpose of this Lisp was to support Eliza. Someone else adopted the Q32 version to run on the new 704 Lisp. So in less than a week, while doing our normal work, we had a new Lisp system running Eliza and keeping visitors happy while we did our research.

The 704 Eliza system, with quite a different script, was used to generate a conversation with a user about the status of a computer. The dialogue was very similar to one with a human playing the part of a voice recognition and response system where the lines are noisy. The human and Eliza dialogues were included/discussed in A. Newell, et al., “Speech Understanding Systems; Final Report of a Study Group,” Published for Artificial Intelligence by North-Holland/ American Elsevier (1973). The content of that report was all generated in the late 1960s but not published immediately.

The web site, http://www.softwarepreservation.org/projects/LISP/, has a little more information about the Raytheon 704 Lisp. The SUR program was partially funded and on-going by 1970.

Zach BeaneThe unknown dependency tree

· 43 days ago

After posting about the Quicklisp verbosity conundrum, a few people emailed me with variations on this theme: “Since Quicklisp knows what the dependencies of a system are, can’t you just load those quietly first and then load your project verbosely?”

The problem is that the premise is not true. Quicklisp has an idea about the dependencies of Quicklisp-provided systems, but not of any other systems available through ASDF. 

And it’s actually pretty difficult to answer the question, for a given system, “What systems must be loaded first?” It’s not as simple as loading the system definition and then looking at it. The act of loading the system definition may trigger the loading of other systems, which then load other systems, which then load other systems. System definition files are not simply data files. They’re Lisp programs that can do arbitrary computation and manipulation of the environment. 

Quicklisp knows about its system dependency structures because, for every system in Quicklisp, I load it, and record what got loaded to support it. That dependency structure is then saved to a file, and that file is fetched by the Quicklisp client as part of a Quicklisp dist. This data is computed and saved once, on my dist-constructing computer, not each time, on the Quicklisp client computer. The data is evident whenever you see something like “To load foo, installing 5 Quicklisp releases: …”

But that “installing 5 Quicklisp releases” only works when foo itself is provided by Quicklisp. No dependency info is printed otherwise.

Quicklisp then loads foo by calling asdf:load-system. If some system that foo requires isn’t present, ASDF signals an asdf:missing-dependency error, which Quicklisp handles. If Quicklisp knows how to fetch the missing dependency, it does so, then retries loading foo. Otherwise, the missing dependency error is fatal.

Ultimately, though, only the top-level asdf:load-system can be wrapped with the verbosity-controlling settings. The fetching-on-demand error handling only happens the first time a system is installed, so it’s not a predictable point of intercession. After that first time, the system is found via asdf:find-system and no error handling takes place.

Writing this up has given me some twisted ideas, so maybe a fix is possible. I’ll keep you posted.

Luís Oliveiraparedit

· 44 days ago
Taylor Campbell's paredit is one of those Emacs extensions that I can't live without. In a nutshell, it forces you deal with Lisp code exclusively via operations that don't introduce unbalanced parenthesis (or other similar violations of structure). The genius about this approach is that it completely eliminates the step of making sure parentheses are properly balanced after you write or edit a piece of code. After you get used to paredit, performing — or even watching — manual parenthesis balancing becomes painful.

Recently, I've come across these two introductions to paredit:
  1. Emacs Rocks! Episode 14: Paredit
  2. The Animated Guide to Paredit
So, if you're still not using paredit, have a look at those and give it a try. At first you might feel like the karate kid doing frustrating chores — you can always take a break with M-x paredit-mode — but I promise it'll soon pay off!

Zach BeaneA verbosity conundrum

· 45 days ago

Here’s the scoop: Quicklisp hides too much information when building software, and it can’t easily be controlled.

That is partly intentional. Remember the post about clbuild a few days ago? The information hiding is a reaction to the (often joyous) sense, when using clbuild, that you were on the cutting, unstable edge of library development, likely at any given time to hack on a supporting library in addition to (or instead of) your primary application.

To muffle that sense, I wanted the libraries Quicklisp provided to be loaded quietly. Loaded as though they were building blocks, infrastructure pieces that can be taken for granted. Loaded without seeing pages of style-warnings, warnings, notices, and other stuff that you shouldn’t need to care about. (I realize, now, that this voluminous output isn’t common to all CL implementations, but even so, one of the loudest implementations is also one of the most popular.)

I still feel good about the concept. I don’t usually want to see supporting library load output, but if I do, there’s always (ql:quickload "foo" :verbose t).

But the default quiet-output mode of quickload interacts with something else in a way I didn’t expect, a way I don’t like, and a way that I don’t really know how to fix.

I switched from using (asdf:load-system "foo") to using (ql:quickload "foo"). This works because Quicklisp’s quickload can “see” any system that can be found via ASDF, even if it isn’t a system provided by Quicklisp. Quickload also automatically fetches, installs, and loads Quicklisp-provided systems on demand, as needed, to make the system load. It’s super-convenient.

Unfortunately, that now means that the quiet-output philosophy is being applied to very non-infrastructure-y code, the code I’m working on at the moment, the code where I really do want to know if I’m getting warnings, style-warnings, notes, and other stuff.

It didn’t bother me a lot at first. When you’re writing something interactively in slime, C-c C-c (for a single form) and C-c C-k (for an entire file) will highlight the things you need to care about. But over time I’ve really started to miss seeing the compile and load output of my own projects differently, and more verbosely, than the output from “infrastructure.” It would be nice to be able to see and fix new warnings I accidentally introduce, in code that I’m directly responsible for.

Unfortunately, I don’t know enough about ASDF to know if it’s possible, much less how to implement it.

The special variables and condition handlers that implement quiet-output are installed around a single toplevel call to asdf:load-system. Everything after that point is handled by ASDF. Loading a given system may involve loading an unknown mix of Quicklisp-provided systems and other systems. I can think of many ways to identify systems as originating from Quicklisp, but even if they’re identified as such, I can’t think of a way to intercede and say “When loading a system provided by Quicklisp, be quiet, otherwise, be verbose.”

Ideally, of course, it would be nice to be able to be totally verbose, totally quiet, or a mix of the two, depending on some property of a system. But at the moment, I just don’t see where I can hook into things temporarily to implement the policy I want.

If you have any ideas about how this might be done, please email me at xach@xach.com. Working proof-of-concept code would be the most welcome form of help; I don’t have much time to chase down a lot of “have-you-tried-this?” speculation. But I’ll gratefully take whatever I can get.

Zach BeaneelPrep 2.0 available, and ported to SBCL

· 46 days ago

I wrote a bit about elPrep, a “high-performance tool for preparing SAM/BAM/CRAM files for variant calling in DNA sequencing pipelines,” back in August. The initial version was LispWorks-only.

There’s a new version 2.0 available, and, along with new features and bugfixes, elPrep now supports SBCL. (Charlotte Herzeel’s announcement cautions that “performance on LispWorks 64bit editions is generally better” and “the use of servers with large amounts of RAM is also more convenient with LispWorks.”)

The elPrep source is available on github.

Zach Beanecl-async updates

· 47 days ago

Andrew Lyon has updated cl-async to use libuv as the backend, switching from libevent. This is an incompatible change, so if you use cl-async, be sure to check the upgrade guide.

There is some discussion about the change on reddit.

Zach Beaneclbuild and Quicklisp

· 48 days ago

Listen, friends, to the story of clbuild and how it influenced the design and implementation of Quicklisp.

I can’t tell a full story of clbuild, since I didn’t use it very much, but here’s what I remember.

clbuild was trivial to install. Download a single file, a shell script, to get started. From there, clbuild could fetch the source code of dozens of interesting projects and set up an environment where it was easy to use that code to support your own projects. It was also trivial to hack on most of the projects, since in most cases you were getting a source control checkout. It was nice to be able to hack directly on a darcs or git checkout of a useful library and then send patches or pull requests upstream.

Luke Gorrie created it, and, like many of his projects, quickly encouraged a community of contributors and hackers that kept evolving and improving clbuild.

clbuild was fantastic in many ways. So why didn’t I use it? Why create Quicklisp, which lacks some of the best features of clbuild?

My biggest initial issue was the firewall at work.

Since clbuild checked out from various version control systems, some of them used ports outside of the range allowed by a typical corporate firewall. I was limited almost exclusively to HTTP or HTTPS service.

A subsequent problem was obtaining all the prerequisite version control tools. Although git and github are dominant today, in 2007, cvs, darcs, svn, and several other version control systems were more frequently used than today. It took a series of errors about missing commands before I could finally get things rolling.

In 2007, for 20 different projects, there might be 20 different computers hosting them. In 2014, it’s more likely that 18 are hosted on github. Because of the diversity of hosting back then, it wasn’t all that uncommon for a particular source code host to be unavailable. When that happened to a critical project’s host, it could mean that bootstrapping your project from clbuild was dead in the water, waiting for the host to come back.

Even if everything was available, there was no particular guarantee that everything actually worked together. If the package structure of a particular project changed, it could break everything that depended on it, until everything was updated to work together again.

Pulling from source control also meant that the software you got depended heavily on the time you got it. If you had separate clbuild setups on separate computers, things could get out of sync unless you made an effort to sync them.

One final, minor issue was that clbuild was Unix-only. If you wanted to use it on Windows, you had to set up a Unix-like environment alongside your Lisp environment so you could run shell scripts and run cvs, darcs, svn, etc. as though they were Unix command-line programs. This didn’t affect me personally, since I mostly used Linux and Mac OS X. But it did limit the audience of clbuild to a subset of CL users.

Elements of Quicklisp’s design are in reaction to these issues.

Quicklisp’s software structure shifts the task of fetching from source control, building, and distribution of software from the end user to a central server. Rather than continuously updating all sources all the time, the updates happen periodically, typically once per month.

This is based on the observation that although there are intermittent problems with software incompatibility and build-breaking bugs, most of the time things work out ok. So the Quicklisp process is meant to slow down the pace of updates and “freeze” a configuration of the Common Lisp project universe at a working, tested, known-good point in time. 

In Quicklisp terms, that universe is called a dist, and a dist version represents its frozen state at a particular point in time. The software is checked out of every source control system, archived into a .tar.gz file, built and tested, and then finally frozen into a set of HTTP-accessible archive files with a few metadata and index files. Fetching libraries is then a matter of connecting to the central server via HTTP to get the metadata and archives. There are no source-control programs to install or firewall ports to open. The build testing means there is a reduced risk of one project’s updates being fatally out-of-sync with the rest of the project universe.

By default, a Quicklisp installation uses the latest version of the standard dist, but it’s a short, easy command to get a specific version instead either at installation time or at some later time. So even if you install Quicklisp multiple times on multiple computers, you can make sure each has the same software “universe” available for development. The uncertainty introduced by the time of installation or update can be completely managed.

This works even for the oldest dist versions; if you started a project in October, 2010, you can still go back to that state of the Common Lisp library world and continue work. That’s because no archive file is ever deleted; it’s made permanently available for just this purpose.

In the mid-2000s, it would have been hard to make a design like that very reliable for a reasonable cost. Amazon web services have made it cheap and easy. I have had only a few minutes of HTTP availability issues with Amazon in the past four years. I’ve never lost a file. 

Quicklisp mitigates the Unix-only issue by using Common Lisp for the installation script and Common Lisp as the library management program. It fetches via HTTP, decompresses, and untars archives with code that has been adapted to work on each supported Common Lisp on each platform. No Unix shell or command-line tools are required. 

There are still some bugs and issues with Quicklisp on Windows, because it doesn’t receive as much testing and use as non-Windows platforms, but it’s just as easy to get started on Windows as it is anywhere else.

Despite fixing some of my personal issues with clbuild, Quicklisp is missing a big, key feature. When using clbuild, it’s easy to get to the forefront of development for the universe of CL software. You can work with the bleeding-edge sources easily and submit bug fixes and features. With Quicklisp, it’s harder to find out where a particular library came from, and it’s harder to get a source-control copy of it suitable for hacking and tweaking. It’s harder to be a contributor, rather than just a consumer, of projects that aren’t your own.

I’d like to improve the situation in Quicklisp, but some of the old obstacles remain. It would require a bunch of Unix-only or Unix-centric command-line tools to be installed and properly configured. Maybe that’s not such a big deal, but it’s loomed large in my mind and blocked progress. Maybe someone will take a look at the Quicklisp project metadata and write a nice program that makes it easy to combine the best of clbuild and Quicklisp. If you do, please send me a link.

PS. clbuild lives on in clbuild2. It looks like it’s still active, with commits from just a few months ago. Maybe that’s the right thing to use when the hacking urge strikes? I’ll have to give it a try.

Gábor MelisINCLUDE locative for PAX

· 50 days ago

I'm getting so used to the M-. plus documentation generation hack that's MGL-PAX, that I use it for all new code which highlighted an issue of with code examples.

The problem is that [the ideally runnable] examples had to live in docstrings. Small code examples presented as verifiable transcripts within docstrings were great, but developing anything beyond a couple of forms of code in docstrings or copy-pasting them from source files to docstrings is insanity or an OOAO violation, respectively.

In response to this, PAX got the INCLUDE locative (see the linked documentation) and became its own first user at the same time. In a nutshell, the INCLUDE locative can refer to non-lisp files and sections of lisp source files which makes it easy to add code examples and external stuff to the documentation without duplication. As always, M-. works as well.

LispjobsKwelia full stack developer, including Clojure

· 51 days ago

Kwelia is building the most accurate, up-to-date and comprehensive data and analytics platform for rental housing data ever constructed. We're looking for our first non-founder software engineering hire to work closely with the founders to help grow our application, analytics stack and engineering team. The ideal candidate is an experienced full-stack developer with analytics experience who can hit the ground running, and thrives in a fast-paced early-stage startup environment.

In this position, you'll be called upon to lead by example and to help establish our engineering culture. Because of our early stage (and your level of responsibility in the company's growth) compensation will include a significant equity stake. Despite our early stage, we will also provide a competitive salary and benefits. Our current team is spread between Philadelphia, PA and Austin, TX. You're welcome to join us in either of those cities, or remotely from your preferred location.

Our Technology Stack:

Ruby on Rails/JavaScript (web application)
PostgreSQL (OLTP database)
Clojure (data collection & processing)
Apache Spark (analytics cluster)
Amazon Web Services (hosting platform)

Please contact us at info@kwelia.com if you are interested.


Didier Verna[CfP] ELS 2015, 8th European Lisp Symposium, Apr. 20-21, London

· 51 days ago
		 ELS'15 - 8th European Lisp Symposium
		    Goldsmiths College, London, UK

			  April 20-21, 2015

	       http://www.european-lisp-symposium.org/

	  Sponsored by EPITA, Franz Inc. and Lispworks Ltd.


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

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

Topics include but are not limited to:

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

We invite submissions in the following forms:

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

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

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

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

All submissions should be formatted following the ACM SIGS guidelines
and include ACM classification categories and terms. For more
information on the submission guidelines and the ACM keywords, see:
http://www.acm.org/sigs/publications/proceedings-templates and
http://www.acm.org/about/class/1998.

Important dates:

  - 22 Feb 2015: Submission deadline
  - 15 Mar 2015: Notification of acceptance
  - 29 Mar 2015: Early registration deadline
  - 05 Apr 2015: Final papers
  - 20-21 Apr 2015: Symposium

Programme chair:
    Julian Padget, University of Bath, UK

Local chair:
    Christophe Rhodes, Goldsmiths, University of London, UK

Programme committee:

    To be announced

Search Keywords:

#els2015, ELS 2015, ELS '15, European Lisp Symposium 2015,
European Lisp Symposium '15, 8th ELS, 8th European Lisp Symposium,
European Lisp Conference 2015, European Lisp Conference '15


For older items, see the Planet Lisp Archives.


Last updated: 2015-01-25 16:19