New release of epydemic

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

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

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.

The different energy footprints of different programming languages

The different energy footprints of different programming languages

I’ve recently been thinking about low-power computing, from AI and data centres down to sensors, as part of a new initiative the University is considering. It’s easy to forget the resource footprint of our computing systems – especially those that are “out of sight, out of mind” in the cloud – but there’s growing evidence that their growth threatens the renewable energy transition. Some of the figures for AI electricity and water usage are astonishing.

One aspect of this is the effect of choice of programming language. I can across some work from 2017 on this:

Rui Pereira, Marco Couto, Francisco Ribeiro, Rui Rua, Cunha Jácome, João Paulo Fernandes, and João Saraiva. Energy Efficiency across Programming Languages: How Do Energy, Time, and Memory Relate? In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering. 2017.

The authors compare 13 benchmarks run in 27 different languages, with the benchmarks being chosen widely to avoid being biased by numeric performance. I was expecting some patterns: compiled languages doing better on performance, memory, and energy usage, for example. But I wasn’t expecting exactly how widely the figures diverged, or some of the details.

The following table is from the paper, annotated by me. The figures are normalised against the best result in each category (so the top language has value 1, and so on).

pl-energy.png

The two most-used languages for web application, Python and JavaScript, perform uniformly pretty badly: 75 times C’s energy usage, in Python’s case. But although JavaScript does substantially better on energy (only a factor of 4), TypeScript – which is usually thought of as JavaScript with type pre-processing – requires 21 times C’s energy, or 5 times JavaScript’s. Why is that? – I can’t think of a reason.

But the real surprise was that “research” languages like Haskell and Lisp both hold up well: twice C’s energy, in Lisp’s case. I don’t think that would surprise modern Lisp programmers, who are used to their compilers’ efficiencies – but it would surprise someone used only to the “hearsay” about Lisp. The same for Haskell, actually, whose modern compilers really leverage the extra structure. When you consider that both those languages are pretty much dependent on garbage collection and so are doing substantially more work than the equivalent C program, it’s impressive.

(Also look in the table for Racket, consistently lower than Lisp despite their close similarities. I suspect this is a compiler optimisation issue more than anything else.)

This work clearly isn’t complete or definitive. Clojure is entirely missing, as is Scala, and there will have been compiler improvements since 2017 for the languages with the most active developer communities. But it’s still quite sobering that the differences are so wide, and that we’ve chosen to push languages that exacerbate energy usage rather than managing it.

Purely functional data structures

Purely functional data structures

Chris Okasaki. Purely Functional Data Structures. Cambridge University Press. ISBN 978-051153-010-4. 1998.

Not a Lisp book per se, but a treatment of data structures from a functional programming perspective. The code examples are in Standard ML, but the ideas apply strongly to Lisp and Scheme. Definitely a useful source for an alternative take on data structuring that doesn’t start from assumptions of imperative programming and mutability.