Simon Dobson

Tutorial on good Lisp programming style

https://www.cs.umd.edu/%7Enau/cmsc421/norvig-lisp-style.pdf

Expression + Understanding = Communication

A great discussion of style, perhaps the most elusive programming skill. Illustrated across all the levels of abstraction that one finds in Lisp: of data, functions, control, and syntax (the last being essentially unique to Lisp macros). The discussion of control abstraction deals extensively with catch/throw and other primitives in the condition system that are dealt with at greater length in The Common Lisp condition system.

The extended example (starting on page 71) of how to simplify logical expressions is amazingly clear, and really shows the progression from simple functions to embedded languages targeting specific tasks and making them easy to describe and extend to new applications: something that lies at the heart of the Lisp experience.

Much of the advice is actually language-agnostic, even though the concrete examples are in Lisp. Norvig, of course, is the author of Paradigms of artificial intelligence programming, and has made enormous contributions to the theory and practice of Lisp.

Lisp: Style and design

nil

Molly Miller and Eric Benson. Lisp: Style and Design. Digital Press. ISBN 978-0135384220. 1990.

A book that would serve as a primer for someone tackling a significant piece of programming for the first time.

The style is a bit stiff and occasionally slightly patronising, definitely positioned as being from senior to junior programmers. The depth of the material is variable: I found the treatment of macros quite superficial, not helped by the examples generating questionable code. It also places relatively little emphasis on CLOS and generic functions, which would get more space in a more modern treatment..

The best chapters are those on debugging and (especially) performance engineering, which dig into the interactive tools generally available within Lisp and give a good end-to-end description of the use of declare forms to aid compiler optimisations.

But again the book’s age shows. It predates the obsessive relationship that many modern programmers have with unit testing and test automation, treating testing as an interactive activity alongside debugging rather than as a core and permanent part of program development and maintenance.

New release of epydemic

It’s been a while – about 15 months since v.1.13.1 – but today I finally released v.1.14.1 of epydemic, a library for epidemic (and) other simulation over complex networks.

This release include several bug-fixes and two major changes.

Better Newman-Ziff percolation

The Newman-Ziff algorithm for bond and site percolation is widely used. The version that’s been in epydemic for a while emphasise speed over everything. However, in the course of some work by one of my MSc students on how grids of different dimensions respond to random failure, we discovered that we needed to be able to do some more flexible operations. In particular, we wanted to sample things other than just the size of the largest connected component, and wanted to be able to dig into to exactly how the network was deforming.

The problem was that this information wasn’t readily available. It was encoded within the algorithm’s data structure, but it wasn’t being reflected as an evolving network that was easy to get at. So we upgraded the algorithm to build a working copy of the network as it was constructed, so that it could be interrogated by normal networkx operations within the sampling process. This adds some time penalty, but it’s acceptable slowdown for the extra capability.

Multiple process instances

epydemic defines different epidemic processes (and indeed non-disease processes like pulse-coupled oscillators). Until now these have been usable alone in a simulation, but not together: one couldn’t run two diseases in the same simulation over the same population simultaneously. Doing so is obviously very desirable, especially if you want to explore co-infecting diseases.

Co-infection is a difficult problem. As a first step we’ve added multiple process instances which can have their own parameters and results – or can share parameters if required. This involves assigning distinct names to each instance, and then optionally using them to decorate parameter/result names.

This is fiddly if done manually, so we also added some methods on the Process class to get and set parameters and results using any instance name on the calling process. For example:

   params = dict()

   # network
   N = 10000
   kmean = 100
   params[ERNetwork.N] = N
   params[ERNetwork.KMEAN] = kmean

   # first infection
   p1 = SIR("Disease1")
   p1.setParameters(params,
                        {SIR.P_INFECT: 0.1,
                         SIR.P_INFECTED: 5.0 / N
                         })

   # second infection
   p2 = SIR("Disease2")
   p2.setParameters(params,
                        {SIR.P_INFECT: 0.3,
                         SIR.P_INFECTED: 5.0 / N
                         })

   # common removal rate
   params[SIR.P_REMOVE] = 0.005

   # run the processes together
   ps = ProcessSequence([p1, p2])
   e = StochasticDynamics(ps, ERNetwork())
   rc = e.set(params).run(fatal=True)

The setParameters call sets the parameters decorated with the name of the process, if it has one. There are other operations for extracting the parameters, and for interacting with experimental results without getting into the details of decoration.

See the project documentation for more details, as well as an updated tutorial and a cookbook recipe for co-infection (which is based around the code above). The Github repo is also available. To upgrade, just run:

   pip install --upgrade epydemic

or delete and re-build any virtual environments.

Lisp as a second language

Peter Desain. Lisp as a Second Language: Functional Aspects. Perspectives on New Music 20, pp.192–222. 1990.

In some ways this article should come under “applications”, as it’s mainly concerned with using Lisp to represent and manipulate music. Indeed, it presents a system that can be used to perform all sorts of common transformations of the tones and timing of a piece. It’s easy to see how the resulting system could be used to compose and then to drive instruments, for example through a MIDI interface.

The music perspective is however secondary to the goal of teaching and showcasing Lisp through the medium of a realistic example of symbolic programming. It covers a lot of ground, starting with lists and functions and including first-class functions and combinators as means of implementing the musical structures. It’s a great piece of pedagogy that treats the application and the language as closely linked, and not shying-away from some quite advanced techniques that have clear applications in the domain. It would be great to see this used as a basis for actual musical composition and performance.

Two Lisp compilers written in Lisp

A Lisp compiler to ARM written in Lisp

A Lisp compiler to RISC-V written in Lisp

Two native-code compilers written in the uLisp dialect that targets microcontroller-class machines. Both use a combination of stack and register allocation to get efficiency – and they’re very efficient, with the compiled versions sometimes being 100x faster than the interpreted code.

These are not complete ports, and indeed not on a complete or standard underlying Lisp implementation. But it’s still fascinating to see how simple it is, built as a recursive-descent tree-walker that emits assembler directly. With careful initial design even a compiler with no optimisation pathways can still get great speed-up over an interpreter.