fidzu : LISP

Boston Lisp meetings are a lot of fun. Here's Alex Plotnick's announcement for the next meeting:

I'm pleased to announce that François-René Rideau will speak at the next Boston Lisp meeting on his recent work on ASDF 3. The meeting will take place on Thursday, 23 May at 6:30 PM, in the Star Conference room at MIT's Stata Center (MIT 32-D463; <http://whereis.mit.edu/?go=32>).

I'm sorry about the short notice on this one; communications problems of all kinds have been gumming up the works. Please feel free to spread the word about the meeting via whatever mechanisms are available to you.

Talk details (courtesy of Faré) follow. I hope to see you all there!

Title: "ASDF 3, or lessons in building portable Common Lisp programs"

Summary:
"ASDF (Another System Definition Facility) has been the de facto standard Common Lisp build system for over ten years. I recently rewrote it completely, several times, all the time (mostly) preserving backwards compatibility. The latest incarnation, ASDF 3, in addition to fixing deep design bugs older than ASDF itself, also includes extensive portability library, UIOP, not to be confused with an existing parallelizing extension, POIU. I will show how to use ASDF, explain the recent improvements, and discuss the challenges of writing portable Common Lisp programs and what that means for the past and future of Lisp."

About the speaker:
"François-René Rideau is a Lisp plumber. On good days, he designs great piping for persistent data, to be used in airline reservation system of ITA (now part of Google). On bad days, he dons his rubber gloves and scrubs the pipes. He also has a blog, Cybernethics, where he writes on liberty, music, programming, and dynamic systems in general."

I can't make it, but if you're in the Boston area, you should go!

22 May 2013 12:26pm GMT

IT JUNIOR SOFTWARE DEVELOPER (Event Management Systems and Portals)

CREATE-NET is seeking a well motivated Junior Software Developer to be part of our Innovation team, that will contribute to the analysis, development and testing of a comprehensive portfolio of specialized software products for supporting the workflow of events and conference organization and management, including the creation of web portals and web applications.

The candidate will be directly responsible of the analysis, development and testing of a set of software components that offer events management services, and he will contribute to and will coordinate his activities with other IT developers and graphic designers, in the specification, design, implementation, testing of web portals and web applications.
Specific Job responsibilities will include:

· Contribution to the maintenance of our camera ready submission system, payment system, public journal and proceedings archive conference web site CMS and general administration tool.
· Interacting with the project responsibles and the user community to determine requirements, communicating with the support team to handle any problems or new features required.
· Contribution to technical support to systems in operations.

This position requires hands-on experience in the design, implementation and maintenance of software systems in a Drupal/PHP, Common Lisp and Haskell environment.

Applicants should have a Master's degree (or equivalent) in computing or other related disciplines, and a proven experience in software development.

Knowledge or interest in the following areas would be given preference:
functional programming, Haskell, Common Lisp, Scala, OCaml.

Technical skills for the proposed position:

· Web technologies; HTML5, CSS, AJAX, web services, etc.
· Working experience and knowledge of functional programming, familiarity with associated development environments (e.g. Common Lisp's SLIME).
· Confident understanding and experience with Git (mandatory)
· JavaScript (mandatory)
· Proven Common Lisp experience (mandatory)
· Proven Haskell experience (mandatory)
· PHP (preferable)
· Experience with relational DBMSs (PostgreSQL in particular)
· Linux environments (Redhat and Ubuntu preferable)
· skills on mobile apps development (ios, android) will be considered as a plus;
· Experience and knowledge of agile methodologies, software design methods are also considered a plus.

The following organizational skills are requested for this position:

· Autonomous thinking and problem solving skills;
· Prioritization, time management skills and capability to adapt to dynamic environments;
· Ability to work hands-on and with little supervision;
· Attitude to collaborative working.

Working place:
Trento, top ranked Italian city for quality of life and known for hosting a large number of cutting-edge worldwide recognized research institutions.

Languages:
Excellent command of the English language (written and spoken) is essential.
knowledge of the Italian language both spoken and written is not required, but can be helpful.

Working schedule: Full-Time

How to apply: Please send your resume/CV in English to careers@create-net.org, specifying in the email subject: "IT JUNIOR SOFTWARE DEVELOPER (Event Management Systems and Portals) - CN". Only applications submitted in English will be taken into consideration.

Please include any Github/Bitbucket or otherwise links to open source contributions you have made with the above technologies.

Important: due to Italian Privacy Protection Law n.196/03 any resume not mentioning explicitly the following wording: "I authorize the use of my personal data in accordance with Italian Privacy Protection Law (30/06/2003, n.196/03)" will be automatically deleted from our database and consequently not taken into consideration.

20 May 2013 2:56pm GMT

Important news:

Subject: ECLM 2013 - two days left to register
Date: Mon, 13 May 2013 19:17:26 +0200
From: Edi Weitz

Ladies and Gentlemen,

This is our last call - there are two days left to register for this year's ECLM in case you haven't done so already:

http://weitz.de/eclm2013/

We have more than 50 registrations so far, but we wouldn't mind seeing another dozen or two...

Best regards,
Arthur & Edi.

I greatly enjoyed my last visit to ECLM and I can't recommend it highly enough if you want to meet people with interesting Common Lisp projects and ideas.

13 May 2013 5:33pm GMT

Last week came with two bank holidays in a row, and I took the opportunity to design a command language for pgloader. While doing that, I unexpectedly stumbled accross a very nice AHAH! moment, and I now want to share it with you, dear reader.

AHAH, you'll see!

The general approach I'm following code wise with that command language is to first get a code API to expose the capabilities of the system, then somehow plug the command language into that API thanks to a parser. It turns out that doing so in Common Lisp is really easy, and that you can get a compiler for free too, while at it. Let's see about that.

A very simple toy example

In this newsgroup article What is symbolic compoutation?, Pascal Bourguignon did propose a very simple piece of code:

(defparameter *additive-color-graph*
  '((red   (red white)   (green yellow) (blue magenta))
    (green (red yellow)  (green white)  (blue cyan))
    (blue  (red magenta) (green cyan)   (blue white))))

(defun symbolic-color-add (a b)
  (cadr (assoc a (cdr (assoc b *additive-color-graph*)))))

This is an example of symbolic computation, and we're going to build a little language to express the data and the code. Not that we would need to build one, mind you, more in order to have a really simple example leading us to the ahah moment you're now waiting for.

Before we dive into the main topic, you have to realize that the previous code example actually works: it's defining some data, using an implicit data structure composed by nesting lists together, and defines a function that knows how to sort out the data in that anonymous data structure so as to compound 2 colors together.

TOY-PARSER> (symbolic-color-add 'red 'green)
YELLOW

A command language and parser

I decided to go with the following language:

color red   +red white    +green yellow  +blue magenta
color green +red yellow   +green white   +blue cyan
color blue  +red magenta  +green cyan    +blue white

mix red and green

And here's how some of the parser looks like, using the esrap packrat lib:

(defrule color-name (and whitespaces (+ (alpha-char-p character)))
  (:destructure (ws name)
    (declare (ignore ws))               ; ignore whitespaces
    ;; CL symbols default to upper case.
    (intern (string-upcase (coerce name 'string)) :toy-parser)))

;;; parse string "+ red white"
(defrule color-mix (and whitespaces "+" color-name color-name)
  (:destructure (ws plus color-added color-obtained)
    (declare (ignore ws plus))          ; ignore whitespaces and keywords
    (list color-added color-obtained)))

;;; mix red and green
(defrule mix-two-colors (and kw-mix color-name kw-and color-name)
  (:destructure (mix c1 and c2)
    (declare (ignore mix and))          ; ignore keywords
    (list c1 c2)))

Those rules are not the whole parser, go have a look at the project on github if you want to see the whole code, it's called toy-parser over there. The main idea here is to show that when we parse a line from our little language, we produce the simplest possible structured data: in lisp that's symbols and lists.

The reason why it makes sense doing that is the next rule:

The one grammar rule to bind them all

(defrule program (and colors mix-two-colors)
  (:destructure (graph (c1 c2))
    `(lambda ()
       (let ((*additive-color-graph* ',graph))
         (symbolic-color-add ',c1 ',c2)))))

This rule is the complex one to bind them all. It's using a quasiquote, a basic lisp syntax element allowing the programmer to very easily produce data that looks exactly like code. Let's see how it goes with a very simple example:

TOY-PARSER> (pprint (parse 'program
                           "color red +green yellow mix green and red"))

(LAMBDA NIL
  (LET ((*ADDITIVE-COLOR-GRAPH* '((RED (GREEN YELLOW)))))
    (SYMBOLIC-COLOR-ADD 'RED 'GREEN)))

The parser is producing structure (nested) data that really looks like lisp code, right? So maybe we can just run that code...

What about a compiler now?

Here is my AHAH moment!

Let's see about actually running the code:

TOY-PARSER> (let* ((code "color red +green yellow mix green and red")
                   (program (parse 'program code)))
              (compile nil program))
#<Anonymous Function #x3020027CF0EF>
NIL
NIL
TOY-PARSER> (let* ((code "color red +green yellow mix green and red")
                   (program (parse 'program code)))
              (funcall (compile nil program)))
YELLOW

So we have a string reprensing code in our very little language, and a parser that knows how to produce a nested list of atoms that looks like lisp code. And as we have lisp, we can actually compile that code at run-time with the same compiler that we used to produce our parser, and we can then funcall that function we just built.

Oh and the function is actually compiled down to native code, of course:

TOY-PARSER> (let* ((code "color red +green yellow mix red and green")
                   (program (parse 'program code))
                   (func    (compile nil program)))
              (time (loop repeat 1000 do (funcall func))))

(LOOP REPEAT 1000 DO (FUNCALL FUNC))
took 108 microseconds (0.000108 seconds) to run.
During that period, and with 4 available CPU cores,
     105 microseconds (0.000105 seconds) were spent in user mode
      13 microseconds (0.000013 seconds) were spent in system mode
NIL

Yeah, it took the whole of 108 microseconds to actually run the code generated by our own parser a thousand times, on my laptop. I can believe it's been compiled to native code, that seems like the right ballpark.

Conclusion

The toy-parser code is there on GitHub and you can actually load it using Quicklisp: clone the repository in ~/quicklisp/local-projects/ then (ql:quickload "toy-parser"), and play with it in (in-package :toy-parser).

The only thing I still want to say here is this: can your programming language of choice make it that easy?

13 May 2013 9:08am GMT

Coleslaw 0.9.2

It still amuses me that my most successful project to date is a blog engine. Not that I'm complaining about having contributors. When I last mentioned it, version 0.8 had just been released. Since then there have been 2 new contributors and a bunch of new features. I think the code has mostly improved in cleanliness.

The biggest changes are new shiny docs, a new tags implementation, cleanups to theming, and plugins for Google Analytics, Github Pages, and Sitemap Generation. For the full details, see the changelog.

My plans for 1.0 are primarily to take advantage of the extensible content types added in 0.8 and add some sort of tumblr-like auto-embedding support. But I probably won't get around to working on that for a spell. Why?

Other Lispiness

Because my lisp emulation experiment/art project is ongoing. Nyef was kind enough to share some code he'd hacked up for NES emulation years ago and it helped give me the motivation to rewrite famiclom's PPU (Graphics Card). The former code was largely cribbed from Patrick Walton's sprocketnes and I didn't understand it very well. I've hit the nesdev wiki again and am getting more comfortable with the PPU's actual workings. The code is on github in the new-ppu branch and I'm hoping to spend more time on it this coming week.

I also spent the last week porting cl-6502 to clojurescript for giggles. Heresy, I know. ;)
cljs-6502 is in a basic working state but there are bugs aplenty and I haven't implemented the assembler or disassembler. The must frustrating part was dealing with A) differences in macro hygiene and B) poor macro debugging facilities.

The browser is a fun target though. I'll have to try parenscript or ... jscl! JSCL is a full CL->JS compiler in early development, which I contributed a tiny patch to for fboundp. It's a great project and if you have any interest in helping implement a lisp, I'd encourage you to get involved. The maintainers are very approachable and there's plenty of fun hacking to be had.

All for now. It's time to play around trying static analysis of Nintendo ROMs with Lisp. I'm bound to learn something...hopefully.

11 May 2013 11:41am GMT

In doing a problem set from the Internet a few weeks ago, I found myself writing awkward constructions with REDUCE and LOOP to try to find the best one (or two or three) things in a big bag of things based on various criteria: similarity to English, hamming distance from their neighbor, etc.

I wrote a macro that encapsulated the pattern. I've reworked that macro into a library for public use.

Acquiring

• Home page: http://nklein.com/software/track-best-library/
• Main git repository: http://git.nklein.com/lisp/libs/track-best.git
• Browsable repository: https://github.com/nklein/track-best

Using

There are a variety of examples in the README and the tests directory.

Here is one example to pique your interest. Suppose you have some data about the elevations of various cities in various states and you (being a Moxy Fruvous fan) want to know What Is the Lowest Highest Point? Here's how you might tackle that with the TRACK-BEST library:

(let ((data '(("Alabama"  ("Birmingham" 664)
                          ("Mobile" 218)
                          ("Montegomery" 221))
              ("Alaska"   ("Anchorage" 144)
                          ("Fairbanks" 531))
              ("Arizona"  ("Grand Canyon" 6606)
                          ("Phoenix" 1132)
                          ("Tuscon"  2641)))))
  (with-track-best (:order-by-fn #'<)
    (dolist (state-info data)
      (multiple-value-bind (city altitude)
          (with-track-best ()
            (dolist (city-info (rest state-info))
              (track (first city-info) (second city-info))))
        (track (list (first state-info) city) altitude)))))

With this limited dataset, the end result would be (VALUES '("Alaska" "Fairbanks") 531). The inner WITH-TRACK-BEST finds the highest city in each state. The outer WITH-TRACK-BEST finds the lowest of these.

09 May 2013 11:27pm GMT

I'm very excited to be attending both ECLM and ELS in Madrid this year. This is the last week to register for ECLM, so if you want to go, you should register ASAP.

08 May 2013 7:13pm GMT

I had need recently to create quick x-y plots on the screen. I have been generating TikZ and PGFplots from Lisp for journal and conference papers and presentations. They look very nice but are not quick, either in writing or displaying. There are a number of CL packages listed for plotting, and I gave cl-plplot a try. It is in quicklisp. Though there is no active work on it, I was able to generate plots that I wanted quickly.

Here is an example, plotting the square function. First load needed libraries

sudo aptitude install libplplot-dev plplot11-driver-cairo plplot11-driver-xwin

(in Ubuntu 12.04LTS), then in Lisp

(ql:quickload :cl-plplot)
(defun x-y-plot ()
       (let* ((x (iter (for x from 0.0 to 10.0 by 0.25) (collect x result-type vector)))
              (y (map 'vector (alexandria:rcurry 'expt 2) x))
              (p (cl-plplot:new-x-y-plot x y))
              (w (cl-plplot:basic-window :x-label "x" :y-label "x squared" :title "The square function")))
         (cl-plplot:add-plot-to-window w p)
         (cl-plplot:render w "xwin")))
(x-y-plot)

Click on window and Enter to close; clicking on the close box for the window causes Lisp to crash, at least from Slime.

06 May 2013 2:14am GMT

One of the things that's often said about Lisp is that it allows you to build up the language to you. Here are two examples that really drive home that point, for me.

The Problem Domain

I read an article about Treaps on reddit yesterday. The article used pretty direct pylisp to present Treaps.

I thought it would be fun to go through the exercise in Common Lisp instead. Pylisp made a number of things awkward that would melt away in Common Lisp.

I began by defining a node structure to encapsulate the information at a given node:

(defstruct node
  (priority (random 1.0d0) :type real :read-only t)
  (key 0 :read-only t)
  (value 0 :read-only t)
  (left nil :type (or null node) :read-only t)
  (right nil :type (or null node) :read-only t))

Then, I defined a top-level structure to hold the root node, track the function used to sort the tree, and track the function used to create a key from a value. I used the convention that two keys are equivalent if neither is less than the other.

(defstruct treap
  (root nil :type (or null node) :read-only t)
  (less-than #'< :read-only t)
  (key #'identity :read-only t))

The First Build Up

The article was using a functional style. As you may have guessed by the liberal use of :read-only t in those DEFSTRUCT clauses, I also used a functional style.

When working with functional data structures, one often needs to copy a whole structure with only slight modifications. Here, Lisp's keyword arguments made everything simple and clean. I made this functions:

(defun copy-node (node &key (priority (node-priority node))
                            (key (node-key node))
                            (value (node-value node))
                            (left (node-left node))
                            (right (node-right node)))
  (make-node :priority priority
             :key key
             :value value
             :left left
             :right right))

Now, for any node, I could copy it and only have to specify the fields that I wanted to change. Here is a left-rotation using this:

(defun left-rotate (node)
  (let ((left (node-left node)))
    (copy-node left
               :right (copy-node node
                                 :left (node-right left)))))

What other languages let you do anything like that so simply? You could pull it off in Perl if you were willing to have your node be a hash (which, admittedly, you probably are if you're writing Perl). What other language lets you do anything like that? Even other languages with named arguments don't let you have the defaults based on other arguments.

The Second Build Up

As with any binary tree, you find yourself having to deal with four specific cases over and over again with Treaps.

• You ran out of tree
• Your key is less than the current node's key
• Your key is greater than the current node's key
• Your key is equivalent to the current node's key

I wrote myself a TREAP-CASES macro that streamlines all of these checks. It also validates to make sure you don't have duplicate cases or cases other than these four. It makes sure that no matter which order you write the cases (or even if you leave some out), they end up organized in the order listed above. The four cases are mutually exclusive so the order doesn't matter except that you want to make sure you haven't run out of tree before doing comparisons and that once you're beyond the less-than and greater-than cases you already know you're in the equivalence case.

With this macro, my TREAP-FIND function looks like this:

(defun treap-find (key treap)
  (check-type treap treap)
  (labels ((treap-node-find (root)
             (treap-cases (key root treap)
               (null (values nil nil))
               (< (treap-node-find (node-left root)))
               (> (treap-node-find (node-right root)))
               (= (values (node-value root) t)))))
    (treap-node-find (treap-root treap))))

The little DSL makes writing and reading the code so much easier. All of the mess of comparing the key to the node's key is hidden away.

With years of practice and days of debugging, you might be able to pull off some quasi-readable control construct like this using C++ templates. With enough therapy, you could convince yourself you can get a close-enough effect with C-preprocessor macros. In Lisp, it's the work of minutes (without lying to yourself).

Here is the TREAP-CASES macro for reference/completeness.

(defmacro treap-cases ((key root treap) &rest clauses)
  (validate-treap-case-clauses clauses)
  (let ((k (gensym "KEY-"))
        (tr (gensym "TREAP-"))
        (r (gensym "ROOT-"))
        (t< (gensym "<-")))
    `(let* ((,k ,key)
            (,tr ,treap)
            (,r ,root)
            (,t< (treap-less-than ,tr)))
       (cond
        ((null ,r) ,@(rest (assoc 'null clauses)))
        ((funcall ,t< ,k (node-key ,r)) ,@(rest (assoc '< clauses)))
        ((funcall ,t< (node-key ,r) ,k) ,@(rest (assoc '> clauses)))
        (t ,@(rest (assoc '= clauses)))))))

I suppose I should also include #'VALIDATE-TREAP-CASE-CLAUSES, too, but it's what you'd expect:

(defun validate-treap-case-clauses (clauses)
  (let ((all-choices '(null < > =)))
    (flet ((assert-all-choices-valid ()
             (dolist (c clauses)
               (unless (member (first c) all-choices)
                 (error "Unrecognized clause type: ~S" (first c)))))
           (assert-no-duplicates ()
             (dolist (c all-choices)
               (unless (<= (count c clauses :key #'first) 1)
                 (error "Duplicate ~S clause not allowed." c)))))
      (assert-all-choices-valid)
      (assert-no-duplicates))))

05 May 2013 6:05am GMT

MLWorks is an "industrial strength" Standard ML compiler and integrated development environment, developed by Harlequin in the 1990s.

Ravenbrook Limited (whose directors were members of the original MLWorks team) acquired the rights to MLWorks on 2013-04-26 and have open sourced the project. Source code is under the BSD license on GitHub.

03 May 2013 5:27pm GMT