pages tagged european-lisp-symposiumnoteshttp://christophe.rhodes.io/notes/tag/european-lisp-symposium/notesikiwiki2018-05-26T08:02:23Zsbcl method-combination fixeshttp://christophe.rhodes.io/notes/blog/posts/2018/sbcl_method-combination_fixes/2018-05-26T08:02:23Z2018-05-26T08:02:23Z
<p>At
the
<a href="https://www.european-lisp-symposium.org/2018/index.html">2018 European Lisp Symposium</a>,
the most obviously actionable feedback
for <a href="http://www.sbcl.org/">SBCL</a> from a presentation was
from
<a href="https://www.european-lisp-symposium.org/static/2018/verna.pdf">Didier's remorseless deconstruction</a> of
SBCL's support for method combinations (along with the lack of
explicitness about behavioural details in
the
<a href="http://www.xach.com/clhs?q=define-method-combination">ANSI CL specification</a> and
the
<a href="http://metamodular.com/CLOS-MOP/method-combinations.html">Art of the Metaobject Protocol</a>).
I don't think that Didier meant to imply that SBCL was particularly
bad at method combinations, compared with other available
implementations – merely that SBCL was a convenient target. And, to
be fair, there
was <a href="https://bugs.launchpad.net/sbcl/+bug/309084">a bug report</a> from a
discussion with Bruno Haible back in SBCL's history – May/June 2004,
according to my search – which had languished largely unfixed for
fourteen years.</p>
<p>I <a href="http://christophe.rhodes.io/notes/blog/posts/2018/els2018_reflections/">said</a> that I found the Symposium energising.
And what better use to put that energy than addressing user feedback?
So, I spent a bit of time earlier this month thinking, fixing and
attempting to work out what behaviours might actually be useful. To
be clear, SBCL’s support for <code>define-method-combination</code> was (probably)
standards-compliant in the usual case, but if you follow the links
from above, or listen to Didier’s talk, you will be aware that that’s
not saying all that much, in that almost nothing is specified about
behaviours under redefinition of method combinations.</p>
<p>So, to start with, I solved the cache invalidation (one of
the
<a href="https://martinfowler.com/bliki/TwoHardThings.html">hardest problems in Computer Science</a>),
making sure that discriminating functions and effective methods are
reset and invalidated for all affected generic functions. This was
slightly complicated by the strategy that SBCL has of distinguishing
short and long <code>method-combination</code>s with distinct classes (and distinct
implementation strategies
for
<a href="http://metamodular.com/CLOS-MOP/compute-effective-method.html"><code>compute-effective-method</code></a>);
but this just needed to be methodical and careful. Famous last words:
I think that all method-combination behaviour in SBCL is now coherent
and should meet user expectations.</p>
<p>More interesting, I think, was coming up with test cases for desired
behaviours. Method combinations are not, I think, widely used in
practice; whether that is because of lack of support, lack of
understanding or lack of need of what they provide, I don't know. (In
fact in conversations at ELS we discussed another possibility, which
is that everyone is more comfortable customising
<code>compute-effective-method</code> instead – both that and
<code>define-method-combination</code> provide ways for inserting arbitrary code
for the effect of a generic function call with particular arguments.
But what this means is that there isn’t, as far as I know at least, a
large corpus of interesting method combinations to play with.</p>
<p>One interesting one which came up: <code>Bike</code> on <code>#lisp</code> designed
an
<a href="https://gist.github.com/Bike/5ca14ba142f3ca3fc65e4c912f4cde9f">implementation using method-combinations of finite state machines</a>,
which I adapted to add to SBCL’s test suite. My version looks like:</p>
<pre><code>(define-method-combination fsm (default-start)
((primary *))
(:arguments &key start)
`(let ((state (or ,start ',default-start)))
(restart-bind
(,@(mapcar (lambda (m) `(,(first (method-qualifiers m))
(lambda ()
(setq state (call-method ,m))
(if (and (typep state '(and symbol (not null)))
(find-restart state))
(invoke-restart state)
state))))
primary))
(invoke-restart state))))
</code></pre>
<p>and there will be more on this use
of <a href="http://www.xach.com/clhs?q=restart-bind"><code>restart-bind</code></a> in a
later post, I hope. Staying on the topic of method combinations, how
might one use this <code>fsm</code> method combination? A simple example might
be to recognize strings with an even number of <code>#\a</code> characters:</p>
<pre><code>;;; first, define something to help with all string parsing
(defclass info ()
((string :initarg :string)
(index :initform 0)))
;;; then the state machine itself
(defgeneric even-as (info &key &allow-other-keys)
(:method-combination fsm :yes))
(defmethod even-as :yes (info &key)
(with-slots ((s string) (i index)) info
(cond ((= i (length s)) t) ((char= (char s i) #\a) (incf i) :no) (t (incf i) :yes))))
(defmethod even-as :no (info &key)
(with-slots ((s string) (i index)) info
(cond ((= i (length s)) nil) ((char= (char s i) #\a) (incf i) :yes) (t (incf i) :no))))
</code></pre>
<p>(Exercise for the reader: adapt this to implement a Turing Machine)</p>
<p>Another example of (I think) an interesting method combination was one
which I came up with in the context of generalized specializers, for
an ELS a while ago:
the <a href="http://christophe.rhodes.io/notes/blog/posts/2014/http-content-negotiation-and-generalized-specializers/">HTTP Request method-combination</a> to
be used
with <a href="http://research.gold.ac.uk/9924/">HTTP Accept specializers</a>.
I'm interested in more! A github search
found
<a href="https://github.com/sirherrbatka/herrblog/blob/aa53949b984bd8eecb34a046f7d1c2d1060a4f2d/src/common/method-combinations.lisp">some</a> <a href="https://github.com/sellout/method-combination-utilities/blob/9abd3ffd8c10cbaa16664dec05e0db9c87ab51dc/src/method-combinations.lisp">examples</a> before
I ran out of patience; do you have any examples?</p>
<p>And I have one further question. The method combination takes
arguments at generic-function definition time (the <code>:yes</code> in
<code>(:method-combination fsm :yes)</code>). Normally, arguments to things are
evaluated at the appropriate time. At the moment, SBCL (and indeed
all other implementations I tested, but that's not strong evidence
given the shared heritage) do not evaluate the arguments to
<code>:method-combination</code> – treating it more like a macro call than a
function call. I’m not sure that is the most helpful behaviour, but
I’m struggling to come up with an example where the other is
definitely better. Maybe something like</p>
<pre><code>(let ((lock (make-lock)))
(defgeneric foo (x)
(:method-combination locked lock)
(:method (x) ...)))
</code></pre>
<p>Which would allow automatic locking around the effective method of
<code>FOO</code> through the method combination? I need to think some more here.</p>
<p>In any case: the <code>method-combination</code> fixes are in the current SBCL
<code>master</code> branch, shortly to be released as sbcl-1.4.8. And there is
still time (though not very much!) to apply for
the
<a href="https://www.jobs.ac.uk/search/?keywords=goldsmiths&salary_from=&salary_to=&category=0600&category=0700&jobtype=&location=01&sector=&x=41&y=5">many jobs</a> advertised
at
<a href="https://www.gold.ac.uk/">Goldsmiths</a> <a href="https://www.gold.ac.uk/computing/">Computing</a> –
what better things to do on a Bank Holiday weekend?</p>
els2018 reflectionshttp://christophe.rhodes.io/notes/blog/posts/2018/els2018_reflections/2018-05-26T08:02:23Z2018-05-04T09:29:07Z
<p>A few weeks ago, I attended
the
<a href="https://www.european-lisp-symposium.org/2018/index.html">2018 European Lisp Symposium</a>.</p>
<p>If you were at
the
<a href="https://www.european-lisp-symposium.org/2017/index.html">2017 iteration</a>,
you might (as I do) have been left with an abiding image of greyness.
That was not at all to fault the location (Brussels) or the
organization (co-located with ) of the symposium;
however,
the <a href="https://twitter.com/ascii19/status/848796581822386176">weather</a>
was <a href="https://twitter.com/ascii19/status/848797424902602752">unkind</a>,
and that didn't help with my own personal low-energy mood at the time.</p>
<p>This year, the event was organized
by <a href="https://www.ravenpack.com/">Ravenpack</a> in Marbella. And the first
thing that I noticed on landing was the warmth. (Perhaps the only
“perk” of low-cost airlines is that it is most likely that one will
disembark on to <em>terra firma</em> rather than a passenger boarding bridge.
And after quite a miserable winter in the UK, the warmth and the
sunshine at the bus stop, while waiting for the bus from Malagá
airport to Marbella, was very welcome indeed. The sense of community
was strong too; while waiting for the bus, I hopped on to
<code>#lisp</code> IRC and Nic Hafner volunteered to meet me at the Marbella bus
station and walk with me to my hotel; we ended up going for drinks at
a beachside bar that evening with Dimitri Fontaine, Christian
Schafmeister, Mikhail Raskin and others – and while we were sitting
there, enjoying the setting, I saw other faces I recognised walking
past along the beach promenade.</p>
<p>The setting for the conference itself,
the
<a href="http://www.marbella.es/cultura/centros/item/35-c-c-cortijo-de-miraflores.html">Centro Cultural Cortijo de Miraflores</a>,
was charming. We had the use of a room, just about big enough for the
90ish delegates; the centre is the seat of the Marbella Historical
Archives, and our room was next to the olive oil exhibition.</p>
<p><a href="http://christophe.rhodes.io/notes/blog/posts/2018/els2018_reflections/els2018.jpeg"><img src="http://christophe.rhodes.io/notes/blog/posts/2018/els2018_reflections/els2018.jpeg" width="778" height="583" alt="2018 European Lisp Symposium opening" class="img" /></a></p>
<p>We also had an inside courtyard for the breaks; sun, shade, water and
coffee were available in equal measure, and there was space for good
conversations – I spoke with many people, and it was great to catch up
and reminisce with old friends, and to discuss the finer points of
language implementation and release management with new ones. (I
continue to maintain that the SBCL time-boxed monthly release cadence
of <code>master</code>, initiated by Bill Newman way back in the SBCL 0.7 days in
2002 [!], has two distinct advantages, for our situation, compared
with other possible choices, and I said so more than once over
coffee.)</p>
<p>The formal programme, curated by Dave Cooper, was great too. Zach's
written
about
<a href="http://lispblog.xach.com/post/173467550358/thoughts-on-els-2018">his highlights</a>;
I enjoyed hearing Jim Newton's latest
on
<a href="https://www.european-lisp-symposium.org/static/2018/newton.pdf">being smarter about typecase</a>,
and Robert Smith's presentation about quantum computing, including a
walkthrough of a quantum computing simulator. As well as quantum
computing, application areas mentioned in talks this year included
computational chemistry, data parallel processing, pedagogy, fluid
dynamics, architecture, sentiment analysis and enterprise resource
planning – and there were some implementation talks in there too, not
least from R. “it’s part of the brand” Matthew Emerson, who gave a
paean to <a href="https://ccl.clozure.com/">Clozure Common Lisp</a>. Highly
non-scientific SBCL user feedback from ELS presenters: most of the
speakers with CL-related talks or applications at least mentioned
SBCL; most of those mentions by speaker were complimentary, but it's
possible that most by raw count referred to bugs – solely due to
Didier Verna's presentation
about
<a href="https://www.european-lisp-symposium.org/static/2018/verna.pdf">method combinations</a> (more
on this in a future blog post).</p>
<p>Overall, I found this year's event energising. I couldn't be there
any earlier than the Sunday evening, nor could I stay beyond Wednesday
morning, so I missed at least the organized social event, but the two
days I had were full and stress-free (even when chairing sessions and
for my own talk). The local organization was excellent; Andrew
Lawson, Nick Levine and our hosts at the foundation did us proud; we
had a great conference dinner, and the general location was
marvellous.</p>
<p>Next year's event will once again be co-located with <Programming>,
this time in Genova (sunny!) on 1st-2nd April 2019. Put it in your
calendar now!</p>
karatsuba multiplication in sbclhttp://christophe.rhodes.io/notes/blog/posts/2017/karatsuba_multiplication_in_sbcl/2017-04-02T20:48:17Z2017-04-02T20:45:22Z
<p>Possible alternative title: I’m on a train!</p>
<p>In particular, I’m on the train heading to the
<a href="http://www.european-lisp-symposium.org/">European Lisp Symposium</a>,
and for the first time since December I don’t have a criticially
urgent piece of teaching to construct. (For the last term, I’ve been
under the cosh of attempting to teach Algorithms & Data Structures to
a class, having never learnt Algorithms & Data Structures formally,
let along properly, myself).</p>
<p>I have been giving the students some structure to help them in their
learning by constructing multiple-choice quizzes. “But
multiple-choice quizzes are easy!”, I hear you cry! Well, they might
be in general, but these quizzes were designed to probe some
understanding, and to help students recognize what they did not know;
of the ten quizzes I ran this term, several had a period where the
modal mark in the quiz was zero. (The students were allowed take the
quizzes more than once; the idea behind that being that they can learn
from their mistakes and improve their score; the score is correlated
to a mark in some minor way to act as a tiny carrot-bite of
motivation; this means I have to write <em>lots</em> of questions so that
multiple attempts aren’t merely an exercise in memory or screenshot
navigation).</p>
<p>The last time I was on a train, a few weeks ago, I was travelling to
and from Warwick to sing Haydn’s Nelson Mass (“Missa in angustiis”;
troubled times, indeed), and had to write a quiz on numbers. I’d
already decided that I would show the students the clever Karatsuba
trick for big integer multiplication, and I wanted to write some
questions to see if they’d understood it, or at least could apply some
of the results of it.</p>
<p>Standard multiplication as learnt in school is, fairly clearly, an
Ω(d<sup>2</sup>) algorithm. My children learn to multiply using the
“grid method”, where: each digit value of the number is written out
along the edges of a table; the cells of the table are the products of
the digit values; and the result is found by adding the cells
together. Something like:</p>
<pre><code> 400 20 7
300 120000 6000 2100
90 36000 1800 630
3 1200 60 21
</code></pre>
<p>for 427×393 = 167811. Similar diagrammatic ways of multiplying (like
[link]) duplicate this table structure, and traditional long
multiplication or even the online multiplication trick where you can
basically do everything in your head all multiply each digit of one of
the multiplicands with each digit of the other.</p>
<p>But wait! This is an Algorithms & Data Structures class, so there
must be some recursive way of decomposing the problem into smaller
problems; divide-and-conquer is classic fodder for Computer
Scientists. So, write a×b as
(a<sub>hi</sub>×2<sup>k</sup>+a<sub>lo</sub>)×(b<sub>hi</sub>×2<sup>k</sup>+b<sub>lo</sub>),
multiply out the brackets, and hi and lo and behold we have
a<sub>hi</sub>×b<sub>hi</sub>×2<sup>2k</sup>+(a<sub>hi</sub>×b<sub>lo</sub>+a<sub>lo</sub>×b<sub>hi</sub>)×2<sup>k</sup>+a<sub>lo</sub>×b<sub>lo</sub>,
and we’ve turned our big multiplication into four multiplications of
half the size, with some additional simpler work to combine the
results, and big-O dear! that’s still quadratic in the number of
digits to multiply. Surely there is a better way?</p>
<p>Yes there is.
<a href="https://en.wikipedia.org/wiki/Karatsuba_algorithm">Karatsuba multiplication</a>
is a better (asymptotically at least) divide-and-conquer algorithm.
It gets its efficiency from a clever
observation[<a href="http://cr.yp.to/papers/m3.pdf">1</a>]: that middle term in
the expansion is expensive, and in fact we can compute it more
cheaply. We have to calculate
c<sub>hi</sub>=a<sub>hi</sub>×b<sub>hi</sub> and
c<sub>lo</sub>=a<sub>lo</sub>×b<sub>lo</sub>, there’s no getting
around that, but to get the cross term we can compute
(a<sub>hi</sub>+a<sub>lo</sub>)×(b<sub>hi</sub>+b<sub>lo</sub>) and
subtract off c<sub>hi</sub> and c<sub>lo</sub>: and that’s then one
multiply for the result of two. With that trick, Karatsuba
multiplication lets us turn our big multiplication into three
multiplications of half the size, and that eventaully
<a href="https://en.wikipedia.org/wiki/Master_theorem">boils down</a> to an
algorithm with complexity Θ(d<sup>1.58</sup>) or thereabouts. Hooray!</p>
<p>Some of the questions I was writing for the quiz were for the students
to compute the complexity of variants of Karatsuba’s trick: generalize
the trick to cross-terms when the numbers are divided into thirds
rather than halves, or quarters, and so on. You can multiply numbers
by doing six multiplies of one-third the size, or ten multiplies of
one-quarter the size, or... wait a minute! Those generalizations of
Karatsuba’s trick are <em>worse</em>, not better! That was completely
counter to my intuition that a generalization of Karatsuba’s trick
should be asymptotically better, and that there was probably some
sense in which the limit of doing divide-bigly-and-conquer-muchly
would turn into an equivalent of FFT-based multiplication with
Θ(d×log(d)) complexity. But this generalization was pulling me back
towards Θ(d<sup>2</sup>)! What was I doing wrong?</p>
<p>Well what I was doing wrong was applying the wrong generalization. I
don’t feel too much shame; it appears that Karatsuba did the same. If
you’re
<a href="https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication">Toom or Cook</a>,
you probably see straight away that the right generalization is not to
be clever about how to calculate cross terms, but to be clever about
how to multiply polynomials: treat the divided numbers as polynomials
in 2<sup>k</sup>, and use the fact that you need one more value than
the polynomial’s degree to determine all its coefficients. This gets
you a product in five multiplications of one-third the size, or seven
multiplications of one-quarter, and this is much better and fit with
my intuition as to what the result should be. (I decided that the
students could do without being explicitly taught about all this).</p>
<p>Meanwhile, here I am on my train journey of relative freedom, and I
thought it might be interesting to see whether and where there was any
benefit to implement Karatsuba multiplication in
<a href="http://www.sbcl.org/">SBCL</a>. (This isn’t a pedagogy blog post, or an
Algorithms & Data Structures blog post, after all; I’m on my way to a
Lisp conference!). I had a go, and have a half-baked implementation:
enough to give an idea. It only works on positive bignums, and bails
if the numbers aren’t of similar enough sizes; on the other hand, it
is substantially consier than it needs to be, and there’s probably
still some room for micro-optimization. The results?</p>
<p><a href="http://christophe.rhodes.io/notes/blog/posts/2017/karatsuba_multiplication_in_sbcl/fit.png"><img src="http://christophe.rhodes.io/notes/blog/posts/2017/karatsuba_multiplication_in_sbcl/fit.png" width="800" height="600" alt="Linear model fit for built-in and Karatsuba multiply" class="img" /></a></p>
<p>The slopes on the built-in and Karatsuba mulitply (according to the
linear model fit) are 1.85±0.04 and 1.52±0.1 respectively, so even
million-(binary)-digit bignums aren’t clearly in the asymptotic
régimes for the two multiplication methods: but at that size (and even
at substantially smaller sizes, though not quite yet at Juho’s
<a href="https://www.snellman.net/blog/archive/2004-08-22.html">1000 bits</a>) my
simple Karatsuba implementation is clearly faster than the built-in
multiply. I should mention that at least part of the reason that I
have even <em>heard</em> of Karatsuba multiplication is Raymond Toy’s
<a href="https://www.cons.org/cmucl/news/2002.html">implementation</a> of it in
<a href="http://cmucl.org/">CMUCL</a>.</p>
<p>Does anyone out there use SBCL for million-digit multiplications?</p>
going to els2017http://christophe.rhodes.io/notes/blog/posts/2017/going_to_els2017/2017-04-02T13:24:33Z2017-04-02T13:24:33Z
<p>I’m going to the
<a href="http://www.european-lisp-symposium.org/">European Lisp Symposium</a>
this year! In fact, I have to catch a train in two and a half hours,
so I should start thinking about packing.</p>
<p>I don’t have a paper to present, or indeed any agenda beyond catching
up with old and new friends and having a little bit of space to think
about what might be fun to try. If you’re there and you want to make
suggestions, or just tell me what you’re up to: I’d love to hear.
(And if you’re not there: bad luck, and see you another time!)</p>
not going to els2016http://christophe.rhodes.io/notes/blog/posts/2016/not_going_to_els2016/2016-05-07T20:30:37Z2016-05-07T20:30:37Z
<p>I’m not going to the
<a href="http://www.european-lisp-symposium.org/">European Lisp Symposium</a>
this year.</p>
<p>It’s a shame, because this is the first one I’ve missed; even in the
height of the confusion of having <a href="http://www.teclo.net/">two</a>
<a href="http://www.gold.ac.uk/computing/">jobs</a>, I managed to make it to
Hamburg and Zadar. But
<span class="createlink">organizing ELS2015</span> took a lot out of
me, and it feels like it’s been relentless ever since; while it would
be lovely to spend two days in Krakow to recharge my batteries and
just listen to the good stuff that is going on, I can’t quite spare
the time or manage the complexity.</p>
<p>Some of the recent complexity: following one of those “two jobs” link
might give a slightly surprising result. Yes, Teclo Networks AG was
acquired by <a href="http://www.sandvine.com/">Sandvine, Inc</a>. This involved
some fairly intricate and delicate negotiations, sucking up time and
energy; some minor residual issues aside, I think things are done and
dusted, and it’s as positive an outcome for all as could be expected.</p>
<p>There have also been a number of sadder outcomes recently; others have
<a href="http://mjg59.dreamwidth.org/41948.html">written</a> about
<a href="http://www.inference.phy.cam.ac.uk/mackay/">David MacKay</a>’s recent
death; I had the privilege to be in his lecture course while he was
writing
<a href="http://www.inference.eng.cam.ac.uk/mackay/itila/"><em>Information Theory, Inference, and Learning Algorithms</em></a>,
and I can trace the influence of both the course material and the
lecturing style on my thought and practice. I (along with many
others) admire his book about
<a href="http://www.withouthotair.com/">energy and humanity</a>; it is
beautifully clear, and starts from the facts and argues from those.
“Please don’t get me wrong: I’m not trying to be pro-nuclear. I’m just
pro-arithmetic.” – a rallying cry for advocates of rationality. I
will also remember David cheefully agreeing to play the viola for the
<a href="http://jcms.jesus.cam.ac.uk/">Jesus College Music Society</a> when some
preposterous number of independent viola parts were needed (my
fallible memory says
“<a href="https://en.wikipedia.org/wiki/Brandenburg_Concertos#No._3_in_G_major.2C_BWV_1048">Brandenburg 3</a>”).
David’s last interview is available to
<a href="https://vimeo.com/163698553/10d1bbe16e">view</a>; iPlayer-enabled
listeners can hear <a href="http://www.cl.cam.ac.uk/~afb21/">Alan Blackwell</a>’s
(computer scientist and double-bassist) tribute on BBC Radio 4’s
<a href="http://www.bbc.co.uk/programmes/b0783lqk">Last Word</a>.</p>
<p>So with regret, I’m not travelling to Krakow this year; I will do my
best to make the 10th European Lisp Symposium (how could I miss a nice
round-numbered edition?), and in the meantime I’ll raise a glass of
Croatian Maraschino, courtesy of my time in
<a href="http://ozk.unizd.hr/els2012/">Zadar</a>, to the success of ELS 2016.</p>
els2015 is nearly herehttp://christophe.rhodes.io/notes/blog/posts/2015/els2015_is_nearly_here/2015-03-20T17:32:13Z2015-03-20T17:04:33Z
<p>This year, I have had the dubious pleasure of being the Local
Organizer for the
<a href="http://www.european-lisp-symposium.org/">European Lisp Symposium 2015</a>,
which is now exactly one month away; in 31 days, hordes of people will
be descending on South East London
<a href="http://christophe.rhodes.io/notes/blog/posts/2015/els2015_is_nearly_here/new-cross-gate-01545-750.jpg"><img src="http://christophe.rhodes.io/notes/blog/posts/2015/els2015_is_nearly_here/200x-new-cross-gate-01545-750.jpg" width="200" height="133" alt="New Cross Gate" class="img" /></a>
to listen to presentations, give lightning talks and engage in general
discussions about all things Lisp – the programme isn’t <em>quite</em>
finalized, but expect Racket, Clojure, elisp and Common Lisp to be
represented, as well as more... minority interests, such as C++.</p>
<p><a href="http://www.european-lisp-symposium.org/content-registration-full.html">Registration is open</a>!
In fact, for the next nine days (until <strong>29th March</strong>) the
registration fee is set at the absurdly low price of €120 (€60 for
students) for two days of talks, tutorials, demos, coffee, pastries,
biscuits, convivial discussion and a conference dinner. I look
forward to welcoming old and new friends alike to
<a href="http://www.gold.ac.uk/">Goldsmiths</a>.</p>