pages tagged mopnoteshttp://christophe.rhodes.io/notes/tag/mop/notesikiwiki2014-11-08T22:38:14Zeuropean lisp symposium 2014http://christophe.rhodes.io/notes/blog/posts/2014/european_lisp_symposium_2014/2014-11-08T22:38:14Z2014-05-14T11:23:23Z
<p>My <a href="http://christophe.rhodes.io/notes/blog/posts/2014/on_my_way_to_els2014/">train ride to Paris</a> was uneventful, and I
arrived at my accommodation only several hours after bedtime. I <em>did</em>
manage to write my talk, and it was good to discover the number of
<s>obsessive</s> <a href="http://planet.lisp.org/">planet.lisp</a> readers when I
showed up to register – “good to see you again. How’s the talk?” was
the median greeting. For the record, I had not only written my talk
on the train but also had a chance to relax a little. Go trains.</p>
<p>The conference was fun; gatherings of like-minded people usually are,
but of course it takes substantial effort from determined people to
create the conditions for that to happen. Kent’s work as programme
chair, both before and during the conference, came with a feeling of
apparent serenity while never for a moment looking out of control, and
the groundwork that the local organizing team (Didier Verna, Gérard
Assayag and Sylvie Benoit) had done meant that even the problem of the
registrations exceeding the maximum capacity of the room – nice
problem to have! – could be dealt with.</p>
<p>I liked the variety in the keynotes. It was very interesting to hear
<a href="http://www.dreamsongs.com/">Richard Gabriel</a>’s talk on his research
in mood in Natural Language processing and generation; in many ways,
those research directions are similar to those in the Transforming
Musicology world. The distinction he drew between programming for a
purpose and programming for exploration was very clear, too: he made
it clear that he considered them two completely different things, and
with my hat as a researcher on I have to agree: usually when I'm
programming for research I don’t know what I'm doing, and the domain
of investigation is so <em>obviously</em> more unknown than the program
structure that I had better have a malleable environment, so that I
can minimize the cost of going down the wrong path.
<a href="http://www.p-cos.net/">Pascal Costanza</a> gave a clear and detailed
view of the problems in parallel programming, drawing a distinction
between parallelism and concurrency, and happened to use examples from
several of my previous lives (Smooth-Particle Hydrodynamics, Sequence
Alignment) to illustrate his points.
<a href="http://quotenil.com/">Gábor Melis</a> talked about his own learning and
practice in the context of machine learning, with a particular focus
on his enviable competition record; his call to aim for the right-hand
side of the curves (representing clear understanding and maximum
use-case coverage) was accompanied by announcements of two libraries,
<a href="https://github.com/melisgl/mgl-pax">mgl-pax</a> and
<a href="https://github.com/melisgl/mgl-mat">mgl-mat</a>.</p>
<p>My own presentation was, I suppose, competent enough
(<a href="http://christophe.rhodes.io/notes/blog/posts/2014/european_lisp_symposium_2014/slides.pdf">slides</a>). Afterwards, I had a good talk with my
previous co-author in the generalizes research line, Jim Newton, about
the details, and Gábor told me he’d like to try it “on by default”.
But the perils of trying to get across a highly-technical topic
struck, and I got a number of comments of the form that the talk had
been enjoyable but I’d “lost them at
<a href="http://mop.lisp.se/dictionary.html#compute-applicable-methods-using-classes"><code>compute-applicable-methods-using-classes</code></a>”.
I suppose I could still win if the talk was enjoyable <em>enough</em> for
them to read and work through the paper; maybe next time I might risk
the demo effect rather more than I did and actually do some
programming live on stage, to help ground the ideas in people’s minds.
I did get a specific request: to write a blog post about
<a href="http://www.lispworks.com/reference/HyperSpec/Body/s_eval_w.htm"><code>eval-when</code></a>
in the context of metaobject programming, and hopefully I'll find time
for the in the next few train journeys...</p>
<p>Meanwhile, highlights (for me) among the contributed papers:
<a href="http://enlivend.livejournal.com/">Nick Levine</a> driving Lispworks’
CAPI graphical user interface library from SBCL using his
<a href="http://www.nicklevine.org/claude/claude-1.0.2/manual/">Common Lisp AUdience Expansion</a>
toolkit (preaching to the choir, though: his real target is Python
developers); <a href="http://fare.livejournal.com/">Faré Rideau</a>’s description
of a
<a href="http://fare.livejournal.com/176185.html">decade-long exploration of defsystem design space</a>;
François-Xavier Bois’ demonstration of
<a href="http://web-mode.org/"><code>web-mode.el</code></a>, an Emacs mode capable of
handling CSS, Javascript and PHP simultaneously; and two talks
motivated by pedagogy: Pedro Ramos’ discussion of the design tradeoffs
involved in an implementation of Python in Racket, and the team
presentation of the approach taken for a new robotics- and
Scheme-oriented undergraduate first-year at Middlesex University, on
which more in a subsequent post.</p>
<p>Lightning talks of particular note to me: Martin Simmons talking about
<a href="http://www.lispworks.com/">Lispworks</a> for mobile; Didier Verna and
Marco Antoniotti talking about their respective
<a href="https://www.lrde.epita.fr/~didier/software/lisp/misc.php#declt">documentation</a>
<a href="http://helambdap.sourceforge.net/">generation</a> systems
(<a href="https://twitter.com/ascii19/status/463347894326939648">my response</a>);
Mikhail Raskin’s argument about the opportunity to push
<a href="http://julialang.org/">Julia</a> in a lispy direction; and probably
others which will come back to mind later.</p>
<p>I was also pleased to be able to contribute to the last full session
of the symposium, a workshop/panel about Lisp in the area of music
applications: an area which is serendipitously close to the day job.
I worked on getting a version of audioDB, our feature-vector search
engine for similarity matching, built and working on my laptop, and
finding a sufficiently interesting search among my Gombert/Josquin
collection to demo – and I also had the chance to talk about
<a href="http://research.gold.ac.uk/9547/">Raymond Whorley’s work</a> on using
multiple viewpoint systems for hymn harmonizations, and what that
teaches us about how people do it (<a href="http://christophe.rhodes.io/notes/blog/posts/2014/european_lisp_symposium_2014/music-slides.pdf">slides</a>, for
what they're worth). Other systems of interest in the session
included <a href="http://repmus.ircam.fr/openmusic/home">OpenMusic</a> (of
course, given <a href="http://www.ircam.fr/">where we were</a>),
<a href="http://www2.siba.fi/PWGL/">PWGL</a>,
<a href="http://repmus.ircam.fr/omax/home">OMax</a>, modalys, and
<a href="http://overtone.github.io/">overtone</a>; there was an interesting
conversation about whether the choice of implementation language was
restricting the userbase, particularly for tools such as OpenMusic
where the normal interface is a graphical one but a large fraction of
users end up wanting to customize behaviour or implement their own
custom patches.</p>
<p>And then it was all over bar the dinner! On a boat, sadly immobile,
but with good conversation and good company. The walk home in company
was fun, though in retrospect it was probably a mistake to stop off at
<a href="http://www.larhumerie.com/">a bar</a> for a nightcap... the train
journey back to the UK the following morning was definitely less
productive than it could have been; closing eyes and letting the world
go past was <em>much</em> more attractive.</p>
<p>But now I'm on another train, going off to record the complete works
of Bernadino de Ribera. Productivity yay.</p>
on my way to els2014http://christophe.rhodes.io/notes/blog/posts/2014/on_my_way_to_els2014/2014-11-08T22:38:14Z2014-05-04T17:48:41Z
<p>After a packed weekend of music-making with
<a href="http://www.deprofundis.org.uk/">De Profundis</a> (go
<a href="http://www.adcticketing.com/whats-on/concert/weeping-in-sharps-and-flats.aspx">buy tickets</a>!),
I’m now at St Pancras, waiting for a train to Paris to go to the
<a href="http://www.european-lisp-symposium.org/">European Lisp Symposium</a>,
where I’ll be presenting my work (with Jan Moringen and David
Lichteblau) on
<a href="http://research.gold.ac.uk/9924/">generalizer metaobjects</a>. I’m
looking forward to the event: it’s being held at
<a href="http://www.ircam.fr/">IRCAM</a>, which as an institution neatly combines
two of my interests (computing and music) – there’s going to be a
special session on Tuesday on Lisp and composition, though I might try
to participate and broaden it a bit to talk about some of our current
problems and approaches in
<a href="http://www.transforming-musicology.org/">Transforming Musicology</a>.</p>
<p>I’m not (yet) looking forward to my talk. Over the next few hours,
I’m going to be putting to the test my current belief that I am most
productive on trains, because I haven’t yet written my talk, and it
turns out that I am in the first session tomorow morning. (I know, I
know, this is the sound of
<a href="http://boingboing.net/2010/06/05/worlds-tiniest-open.html">the world’s tiniest violin</a>).
2h20 should be enough fo anyone.</p>
<p>The flip side of the stress of being first is the ability to enjoy the
rest of the symposium <em>without</em> the stress of an upcoming presentation
hanging over me – as well as the ability to ask <s>nasty</s> difficult
and probing questions without too much fear of instant reprisal. (I
suppose that by putting this out there before the talk I open myself
up to pre-reprisals; all I can say is that I welcome a constructive
and robust exchange of views: there is definitely more work to be done
in the world of extended dispatch, and suggestions will be welcome.)</p>
<p>And of course it <em>will</em> be good to meet up with a community of
like-minded people; I may not be highly active in the Lisp world these
days (though I have been making an effort to be more engaged with at
least the <a href="http://www.sbcl.org/">SBCL</a> team for more than the one day
a month of release activity, and it’s been fun to watch the
<a href="http://christophe.rhodes.io/notes/blog/posts/2014/just_like_old_times/">ARM port progress on <code>#sbcl</code></a>) but I retain a
good helping of interest in what’s going on, and it will be great to
meet up with old friends and maybe even to make new ones.
(Registration got to the room capacity <em>very</em> quickly, and hopefully
the overflow room will have a good atmosphere too). Hopefully the
conversations I have and ideas generated will mean that I have a
productive train ride <em>back</em>, too!</p>
http-content-negotiation-and-generalized-specializershttp://christophe.rhodes.io/notes/blog/posts/2014/http-content-negotiation-and-generalized-specializers/2014-03-13T12:22:26Z2014-03-13T12:22:26Z
<p>I promised a non-trivial example of a use for generalized specializers
<a href="http://christophe.rhodes.io/notes/blog/posts/2014/seeking_real_life_uses_for_generalized_specializers/">a while ago</a>.
Here it is: automatic handling of HTTP
(<a href="http://www.w3.org/Protocols/rfc2616/rfc2616.html">RFC 2616</a>)
<a href="http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.1">Content-Type negotiation</a>
in computed responses.</p>
<p>In
<a href="http://en.wikipedia.org/wiki/Representational_state_transfer">RESTful services</a>
and things of that ilk, a client indicates that it wants to apply a
verb (GET, for example) to a particular resource (named by a URN, or
possibly identified by a URI). This resource is a conceptual object;
it will have zero or more concrete manifestations, and content
negotiation provides a way for the client to indicate which of those
manifestations it would prefer to receive.</p>
<p>That's all a bit abstract. To take a concrete example, consider the
woefully incomplete list of
<a href="https://openlibrary.org/people/csrhodes/lists/OL43186L/seeds">books in my living room</a>
at <a href="http://openlibrary.org">openlibrary</a>. A user operating a
graphical web browser to access that resource is presumed to want to
retrieve HTML and associated resources, in order to view a shiny
representation of the information associated with that resource (a
“web page”, if you will). But the human-oriented representation of
the information is not the only possible one, and it is common
practice in some circles to provide machine-readable representations
as well as human-oriented ones, at the same URL; for example, try:</p>
<pre><code>curl -H 'Accept: application/json' https://openlibrary.org/people/csrhodes/lists
</code></pre>
<p>and observe the difference between that and visiting the same URL in a
graphical browser.</p>
<p>How does the web server know which representation to send? Well, the
example has given away the punchline (if the links above to RFC
sections haven't already). The graphical web browser will send an
<code>Accept</code> header indicating that it prefers to receive objects with
presentational content types – <code>text/html</code>, <code>image/*</code> and so on; the
browser I have to hand sends
<code>text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8</code> as
its <code>Accept</code> header, meaning “please give me <code>text/html</code> or
<code>application/xhtml+xml</code>, or failing that <code>application/xml</code>, or failing
<em>that</em> anything else”. If the server has more than one representation
for a given resource, it can use this client-supplied information to
provide the best possible content; if the client has particular
requirements – for example, attempting to find machine-readable
content for further processing – it can declare this by specifying
particular acceptable content-types in its <code>Accept</code> header.</p>
<p>For a resource for which more than one representation exists, then,
the server must dispatch between them based on the client <code>Accept</code>
header. And this is exactly a non-standard dispatch of the kind I've
been discussing. Consider a resource <code>http://foo.example/</code> which is
implemented by sending the return value of the generic function <code>foo</code>
back to the client:</p>
<pre><code>(defgeneric foo (request)
(:generic-function-class accept-generic-function))
</code></pre>
<p>The default behaviour is somewhat a matter of taste, but one
reasonable choice is that if no content-type matches we should use the
defined HTTP status code to indicate that the responses we could
generate are not acceptable to the client:</p>
<pre><code>(defmethod foo ((request t))
(http:406 request))
</code></pre>
<p>Maybe we have a couple of presentational representations for the
resource:</p>
<pre><code>(defmethod foo ((request (accept "text/plain")))
"Foo")
(defmethod foo ((request (accept "text/html")))
"<!DOCTYPE html>
<html>
<head><title>Foo</title></head>
<body><p>Foo</p></body>
</html>")
</code></pre>
<p>And we might have some machine-readable representations:</p>
<pre><code>(defmethod foo ((request (accept "text/turtle")))
"@prefix foo: <http://example.org/ns#> .
@prefix : <http://other.example.org/ns#> .
foo:bar foo: : .")
(defmethod foo ((request (accept "application/rdf+xml")))
"<?xml version=\"1.0\"?>
<rdf:RDF xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\"
xmlns:foo=\"http://example.org/ns#\">
<rdf:Description about=\"http://example.org/ns#bar\">
<foo:>
<rdf:Description about=\"http://other.example.org/ns#\"/>
</foo:>
</rdf:Description>
</rdf:RDF>")
</code></pre>
<p>(I apologize to any fans of XML/RDF if I have mangled that).</p>
<p>Now a graphical web browser sending an accept header of
<code>text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8</code> as
above will cause the server to send the HTML version, as that is the
most specific applicable method <em>to that accept string</em>. Given this,
it is perfectly possible to construct specialized clients with
alternative preferences expressed in the accept header. A
terminal-based client might prioritize <code>text/plain</code> over <code>text/html</code>
(though in fact neither <a href="http://w3m.sourceforge.net/">w3m</a> nor
<a href="http://lynx.isc.org/">lynx</a> does that, at least in the versions I
have installed). A client for the Semantic Web might instead accept
data in serialized RDF, preferring more modern serializations, by
sending an accept string of <code>text/turtle,application/rdf+xml;q=0.9</code>.
All these clients could each be served the resource in their preferred
format.</p>
<p>The case of serving one of a set of alternative files hosted on the
filesystem in response to a request with an arbitrary accept string is
different; in this case, it doesn't make sense to do the dispatch
through methods. If we were to try to do so, it would look something
like</p>
<pre><code>(defmethod filesystem-handler (url (content-type (accept "text/html")))
(let ((prospect (pathname-for-url url "html")))
(if (probe-file prospect)
(serve-file prospect "text/html")
(call-next-method))))
</code></pre>
<p>but we would need to define one such method per possible mime-type we
might want to serve: doable, but unnecessary compared with the
alternative strategy of finding all content-types servable for a given
url, then choosing the one with the highest score:</p>
<pre><code>(defun filesystem-handler (url accept)
(do* ((prospects (files-for url) (cdr prospects))
(mime-types (mapcar #'mime-type prospects) (cdr mime-types))
result mime-type (q 0))
((null prospects) (serve-file result mime-type))
(when (> (q (car mime-types) accept) q)
(setf result (car prospects)
mime-type (car mime-types)
q (q (car mime-types))))))
</code></pre>
<p>(the set of files on the filesystem effectively already define a set
of methods for a given url; it doesn't make sense to try to mirror
that as a set of reified methods on a generic function. Also, I've
written this out using
<a href="http://www.lispworks.com/reference/HyperSpec/Body/m_do_do.htm"><code>do*</code></a>
largely to keep the <code>do*</code>-is-not-that-bad society alive.)</p>
<p>Anyway. There's an interesting detail I've elided so far; not only do
response-generating functions have to generate the content they wish
to send in the response; they <em>also</em> have to indicate what
content-type they are actually sending. Our <code>accept-generic-function</code>
already handles dispatching on content-type; can it also take
responsibility for setting the content-type of the response?</p>
<p>Why yes! The way to do this is using a method combination; it might
look something like this:</p>
<pre><code>(defvar *actual-content-type*)
(defgeneric handle-content-type (request))
(define-method-combination content-negotiation/or ()
((around (:around))
(primary () :required t))
(:arguments request)
(labels ((transform/1 (method)
`(make-method
(progn
(let ((s (car (sb-mop:method-specializers ,method))))
(when (typep s 'accept-specializer)
(setf *actual-content-type* (media-type s))))
(call-method ,method))))
(transform (primaries)
(mapcar #'(lambda (x) `(call-method ,(transform/1 x)))
primaries))
(wrap (form)
`(let ((*actual-content-type*))
(multiple-value-prog1
,form
(handle-content-type ,request)))))
(let ((form (if (rest primary)
`(or ,@(transform primary))
`(call-method ,(transform/1 (car primary))))))
(if around
(wrap `(call-method ,(first around)
(,@(rest around) (make-method ,form))))
(wrap form)))))
</code></pre>
<p>This behaves just like the <code>or</code> built-in
<a href="http://www.lispworks.com/reference/HyperSpec/Body/a_method.htm"><code>method-combination</code></a>,
except that when calling a primary method whose specializer for the
first argument is one of our <code>accept-specializer</code>s, the content-type
of the specializer is stored in a special variable; the last thing the
effective method does is to call the new <code>handle-content-type</code> generic
function, passing it the original generic function's first argument.</p>
<p>Now let's redefine our <code>foo</code> generic function to have the new method
combination, and a method on <code>handle-content-type</code>:</p>
<pre><code>(defgeneric foo (request)
(:generic-function-class accept-generic-function)
(:method-combination content-negotiation/or))
(defmethod handle-content-type ((x string))
(format t "Content-Type: ~A~%" *actual-content-type*))
</code></pre>
<p>and now, finally, we can try it all out:</p>
<pre><code>SPECIALIZABLE> (foo "text/plain,text/html;q=0.9,*/*;q=0.8")
Content-Type: text/plain
"Foo"
SPECIALIZABLE> (foo "text/turtle,application/rdf+xml;q=0.9")
Content-Type: text/turtle
"@prefix foo: <http://example.org/ns#> .
@prefix : <http://other.example.org/ns#> .
foo:bar foo: : ."
SPECIALIZABLE> (foo "audio/mp3")
406
</code></pre>
<p>OK, but by what magic do these <code>accept-specializer</code> objects exist and
function? I wrote a paper about that, with Jan Moringen and David
Lichteblau: as part of my ongoing open access experimentation, the
version we submitted to the European Lisp Symposium is viewable
<a href="http://eprints.gold.ac.uk/9924/">at Goldsmiths' e-prints repository</a>
or <a href="http://arxiv.org/abs/1403.2765v1">on arXiv</a>. The ELS Chairs have
just announced a deadline extension, so there's still time (until
<strong>March 23</strong>) for anyone to submit technical papers or abstracts for
tutorials and demonstration sessions: please do, and I hope to see
many of my readers there.</p>
generic function precompilationhttp://christophe.rhodes.io/notes/blog/posts/2014/generic_function_precompilation/2014-03-05T14:36:05Z2014-02-03T09:56:36Z
<p>Once upon a time, I wrote
<a href="http://www.advogato.org/person/crhodes/diary/160.html">two</a>
<a href="http://www.advogato.org/person/crhodes/diary/162.html">blog entries</a>
about precompiling the dispatch for generic functions in order to
improve the responsiveness at application startup, and obviously
planned a third but didn't get around to writing it. Some time later,
I asked the lazyweb about it, and unfortunately this time didn't get
anything much back. On further reflection, I think I was going to
discuss a couple of additional technical points.</p>
<p>First of all, there's the question about having this kind of
precompilation on all the time; wouldn't it be nice if generic
functions were always at their most efficient, ready to be called?
Well, yes, but what we actually want is for functions to be at their
most efficient when we want to call them, and we don't particularly
care at other times. Why draw that distinction? Well, when we write
code that uses generic functions, it is usually of the form:</p>
<pre><code>(defgeneric foo (x y))
(defmethod foo ((x t) (y t)) ...)
(defmethod foo ((x integer) (y integer)) ...)
(defmethod foo ((x rational) (y float)) ...)
</code></pre>
<p>a sequence of method definitions; sometimes contiguous, as above;
often distributed among various files.
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_load.htm"><code>load</code></a>ing
such code will execute the
<a href="http://www.lispworks.com/reference/HyperSpec/Body/m_defmet.htm"><code>defmethod</code></a>
forms in series. And each of those executions will call
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_add_me.htm"><code>add-method</code></a>,
changing the generic function's methods, so any aggressive dispatch
precompilation scheme will kick in at <em>every</em> <code>defmethod</code>. That would
be bad enough, being <em>O</em>(<em>N</em>) in the number of methods, but it's
actually worse than that: the amount of work involved in
precompilation will tend to be <em>O</em>(<em>N</em>) in the number of methods, or
in the number of concrete classes applicable to those methods, so
there's <em>O</em>(<em>N</em><sup>2</sup>) or worse behaviour from having
precompilation active all the time. <a href="http://www.sbcl.org/">SBCL</a> is
routinely mocked for having slow-loading FASL files (originally, FASL
probably stood for FASt Load; we don't advertise that much); expensive
and poorly-scaling computations at load-time probably won't win us any
extra friends. (Though having written that, I now wonder if recording
changed generic functions using the dependent-update protocol, and
hooking <code>load</code> or <code>asdf:load-system</code> to precompile after loading a
whole <em>file</em> or <em>system</em>, might be a tasteful compromise).</p>
<p>Secondly, there's the detail of exactly how to pre-fill the cache for
a given generic function (given that its specializers are mostly or
entirely classes). The simplest strategy, of filling the cache with
exactly those classes used as specializers, fails as soon as abstract
or protocol classes are used to organize the implementation of the
generic function. The next simplest, which is to fill the cache with
all possible subclasses of specializers at all argument positions,
well, just <em>reading</em> that should set alarm bells ringing – it might
not be too problematic for generic functions with one argument, but
the cross-product effect of multiple arguments will probably cause the
implementation to collapse under its own weight into a virtual black
hole. It might be that the best approach is to allow the user to
specify an exact set of classes: and to allow the user to introspect a
running system to find out which class combinations have actually been
seen and hence cached in a given session.</p>
<p>In fact, SBCL itself depends on a particular, specific version of
this. The generic function
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_pr_obj.htm"><code>print-object</code></a>
is used for printing almost everything; even without user
specialization, it is called whenever a
<a href="http://www.lispworks.com/reference/HyperSpec/Body/t_stu_ob.htm"><code>structure-object</code></a>
or
<a href="http://www.lispworks.com/reference/HyperSpec/Body/t_std_ob.htm"><code>standard-object</code></a>
needs to be output to any stream. Users <em>can</em> write methods on it,
though, and that then invalidates any previous precomputed dispatch
information. But there are times when it's really important that
<code>print-object</code> just work, without any kind of extra computation to go
on: in particular, when the debugger needs to inform the user that the
Lisp is running out of storage space (heap or stack), it's pretty
important that that reporting can happen without using more heap or
stack than necessary. So for <code>print-object</code>, we never reset the cache
state to empty; it is always prefilled with entries for
<code>control-stack-exhausted</code>, <code>binding-stack-exhausted</code>,
<code>alien-stack-exhausted</code>, <code>heap-exhausted-error</code> and
<a href="http://www.lispworks.com/reference/HyperSpec/Body/t_rst.htm"><code>restart</code></a>
for its first argument. (This strategy only works if there are no
specializations of the second argument to <code>print-object</code> anywhere in
the system; there's no good reason for a user to try to specialize the
second argument in any case, so we emit a warning if they do that and
hope that they read and learn from it.)</p>
extended specializer responseshttp://christophe.rhodes.io/notes/blog/posts/2014/extended_specializer_responses/2014-01-28T17:03:09Z2014-01-28T17:03:09Z
<p>I got a few responses to my
<a href="http://christophe.rhodes.io/notes/blog/posts/2014/seeking_real_life_uses_for_generalized_specializers/">call for use cases for generalized specializers</a>;
I'll try to summarize them in this post. Before I do, it's perhaps
worth noting that the work on generalized specializers that Jim Newton
and I did was written up at about the same time as Charlotte Herzeel,
Jorge Vallejos, Theo D'Hondt and
<a href="http://www.p-cos.net/">Pascal Costanza</a>'s work on
<a href="http://www.p-cos.net/documents/filtered-dispatch.pdf">filtered dispatch</a>,
and so our
<a href="http://www.jucs.org/jucs_14_20/custom_specializers_in_object"><em>Custom Specializers in Object-Oriented Lisp</em> paper</a>
doesn't refer to it. I'll talk more about filtered dispatch in a
later post, when I tie all these threads together, but for those who
aren't aware of it it's
<a href="http://common-lisp.net/project/closer/filtered.html">worth looking at</a>,
along with
<a href="http://common-lisp.net/project/closer/contextl.html">ContextL</a> for
dispatch that varies based on dynamic program state.</p>
<p>Meanwhile, some other ideas for extended specializers: James Anderson
suggested duck typing, and I think working along similar lines Patrick
Stein thought of specializers that could dispatch on the dimensions of
array arguments (or length of sequence arguments). That <em>feels</em> to me
as though there should be a fairly compelling use case, but the toy
example of</p>
<pre><code>(defmethod cross-product ((x (length 3)) (y (length 3)))
...)
</code></pre>
<p>doesn't generalize. I suppose there might be an example of selecting
particular numerical algorithms based on overall matrix dimensions or
properties, something like</p>
<pre><code>(defmethod invert ((x (total-size> 1000000000)))
... invert big matrix ...)
(defmethod invert ((x (total-size<= 1000000000)))
... invert small matrix ...)
</code></pre>
<p>but it doesn't feel concrete yet.</p>
<p>On the other hand, just about <em>everyone</em>'s first response to the
question (Jan Moringen, and the crowded wisdom of <code>#lisp</code> IRC) was
pattern specializers, usually through regular expressions or
<a href="https://github.com/m2ym/optima">optima</a> in particular; one example
concrete use case given was to dispatch among handlers for urls. This
is a very interesting case; I first considered this in the early days
of extended specializers, and indeed
<a href="https://sourceforge.net/p/sbcl/sbcl/ci/master/tree/tests/mop-27.impure.lisp"><code>mop-27.impure.lisp</code></a>
from the SBCL test suite captures one other use case, in a (toy)
simplifier for arithmetic expressions, redolent of implementations of
symbolic differentiation from a bygone age. At the time, I took that
example no further, both because I didn't have a real use case, and
also because I didn't fancy writing a full-strength pattern matching
engine; now that optima exists, it's probably worth revisiting the
example.</p>
<p>In particular, it's worth considering how to handle capturing of
pattern variables. To continue with the toy simplifier, the existing
dispatch and specializer implementation would allow one to write</p>
<pre><code>(defmethod simplify1 ((p (pattern (+ x 0))))
(cadr p))
</code></pre>
<p>but what would be really neat and convenient would be to be able to
write</p>
<pre><code>(defmethod simplify1 ((p (pattern (+ x 0))))
x)
</code></pre>
<p>and in order to do that, we need to intercede in the generation of the
actual method function in order to add bindings for pattern variables
(which, helpfully, optima can tell us about).</p>
<p>The awkwardness in terms of the protocol – beyond the
<a href="http://www.p-cos.net/documents/make-method-lambda.pdf">problems with metaprogramming at compile-time in the first place</a>
– is that
<a href="http://mop.lisp.se/dictionary.html#make-method-lambda"><code>make-method-lambda</code></a>
operates in ignorance of the specializers that will be applied to the
method. In fact, this was the root cause of a
<a href="http://thread.gmane.org/gmane.lisp.steel-bank.devel/17817">recently-reported SBCL bug</a>:
SBCL itself needs to communicate the name and method lambda list from
<a href="http://www.lispworks.com/reference/HyperSpec/Body/m_defmet.htm"><code>defmethod</code></a>
to <code>make-method-lambda</code>, and has no other way of doing that than
special variables, which weren't being cleared to defend against
nested calls to <code>make-method-lambda</code> through code-walking and
macroexpansion.</p>
<p>But <code>make-method-lambda</code> is the function which generates the method
body; it is exactly the function that we need to extend or override in
order to do the desired automatic matching. So how can we expose this
to the metaprogrammer? We can't change the signature of
<code>make-method-lambda</code>; it might seem obvious to extend it by adding
<a href="http://www.lispworks.com/reference/HyperSpec/Body/03_da.htm"><code>&optional</code></a>
arguments, but that changes the signature of the generic function and
would break backwards compatibility, as methods must accept the same
number of optional arguments as their generic function does;
similarly, adding keyword arguments to the generic function doesn't
work.</p>
<p>We could export and document the special variables that we ourselves
use to propagate the information; in some ways that's cleanest, and
has the virtue of at least having been tested in the wild. On the
other hand, it feels unusual, at least in the context of the
metaobject protocol; usually, everything of interest is an argument to
a protocol function. So, we could define a new protocol function, and
have <code>make-method-lambda</code> default to trampolining to it (say,
<code>make-method-lambda-with-specializer-specifiers</code>; the basic idea,
though not the horrible name, is due to Jan Moringen). But we'd need
to be careful in doing that; there is some implementation-specific
logic deep in PCL that performs extra optimizations to methods (the
fast-method calling convention) if the system detects that only the
standardized methods on <code>make-method-lambda</code> are applicable to a
particular call; if we add any extra metaobject protocol functions in
this area, we'll need to make sure that we correctly update any
internal logic based on detecting the absence of metaprogrammer
overrides or extensions...</p>
more prototypes with multiple dispatchhttp://christophe.rhodes.io/notes/blog/posts/2014/more_prototypes_with_multiple_dispatch/2014-01-24T14:41:58Z2014-01-24T14:41:58Z
<p>I received a couple of points in feedback regarding
<span class="createlink">protoypes with multiple dispatch</span>. Firstly, from
<a href="http://www.p-cos.net/">Pascal Costanza</a>, the observation that there's
already a prototype-based dispatch system present in the
quasi-standard CL MOP; the key is to view all the prototype objects as
singletons, and to use introspection to manage delegation and the
<a href="http://mop.lisp.se/dictionary.html#class-mo-readers"><code>class-prototype</code></a>
as the actual object. Thus (any mistakes are mine, not Pascal's):</p>
<pre><code>(defun clone (o)
(let* ((scs (sb-mop:class-direct-superclasses (class-of o)))
(new (make-instance 'standard-class :direct-superclasses scs)))
(sb-mop:finalize-inheritance new)
(sb-mop:class-prototype new)))
(defun add-delegation (o d)
(let ((scs (sb-mop:class-direct-superclasses (class-of o))))
(reinitialize-instance (class-of o)
:direct-superclasses (list* (class-of d) scs))))
</code></pre>
<p>I don't think that this works in quite the same way as a traditional
prototype-based system, mind you: here, a cloned object inherits all
the behaviours provided by delegation, but not the behaviours from the
cloned object itself. It's pretty close, though, and might help those
to whom all this is new (but who are intimately familiar with the CLOS
MOP – hm, actually, the intersection of those two sets might be a
little small) get a bit of a handle on this.</p>
<p>Secondly, Lee Salzman was kind enough to get in touch, and we had a
conversation about his thesis and his reflections on that work. I'll
paraphrase, so again any misrepresentation is mine, but regarding the
question at the end of my
<a href="http://christophe.rhodes.io/notes/blog/posts/2014/prototypes_with_multiple_dispatch/">previous post</a> about the
semantics of redefinition, Lee was quite clear that the expectation
was that previously-cloned objects should retain their previous
behaviour, even if the original object is later updated (in prototypes
and multiple dispatch terms, even if the original method is
redefined). In other words, the <code>???</code> is indeed expected by
prototype-oriented programmers to be <code>(FOO[1] /B/)</code>.</p>
<p>Lee also said that, in his subsequent experience, he has come to
believe that class-based systems are a necessity – particularly in
image-based systems (where there is a persistent world). He's happy
with prototypes as a mechanism in a world with static programme
descriptions, where you can just edit the source code, then compile
and run the programme, but believes that directly modifying running
programmes makes classes or some equivalent abstraction necessary.
I'm not sure I completely understand this point (though I'm fairly
convinced by now that I don't much like the semantics of method
redefinition in a world with long-lived objects), but I'm still
waiting for a good example to highlight the advantages of
prototype-oriented programmes.</p>
<p>Meanwhile, what does this imply for the implementation of prototypes
with multiple dispatch within the extended CLOS metaobject protocol?
Defining a new method specialized on an must override any existing
behaviour for that object, but must leave unchanged the previous
behaviour for any clones; that therefore implies that the generic
function cannot discard the old method, as it must remain applicable
to any clones. The consequences of this include: two prototype
specializers, specialized on the same object, must not be considered
to be the <em>same</em> specializers (otherwise the standard semantics of
method definition would replace the old method with the new); and that
the specializers must be annotated with the method that they belong to
(so that it is possible to compute for a given specializer and
argument whether that argument is acceptable to the specializer,
remembering that the acceptability of an object to a prototype
specializer in this world is primarily a function of the object
itself). One piece of good news: the CLOS MOP already provides a
mechanism for associating specializers with methods, through the
<a href="http://mop.lisp.se/dictionary.html#specializer-direct-methods"><code>specializer-direct-methods</code></a>
generic function, so that's at least some of the battle.</p>
<p>All of this merits a fuller description, a reference implementation,
and some example code using it. I'm working on the first two, aiming
to top up my all-important publications list by presenting at some
conferences (and also helping to justifying my attendance); I'd love
to hear about ideas for the third...</p>
prototypes with multiple dispatchhttp://christophe.rhodes.io/notes/blog/posts/2014/prototypes_with_multiple_dispatch/2014-01-19T08:56:20Z2014-01-18T21:20:32Z
<p>On New Year's Day (did I have nothing better to do?) I asked the wider
world
<a href="http://christophe.rhodes.io/notes/blog/posts/2014/seeking_real_life_uses_for_generalized_specializers/">real life uses of non-standard method selection</a>,
and I hinted that I had an real-life example of my own. This post does not discuss that example.</p>
<p>Instead, I'm going to discuss my limited understanding of another
non-standard (at least, non-CLOS-standard) method selection system,
and demonstrate what its use looks like in my current development
world. I'm talking about a prototype-based object system:
specifically, a mostly-faithful reimplementation of the <em>Prototypes
with Multiple Dispatch</em>
[<a href="http://files.slatelanguage.org/doc/pmd/ecoop.pdf">1</a>,<a href="http://files.slatelanguage.org/doc/pmd/pmd.pdf">2</a>]
system found in <a href="http://slatelanguage.org/">Slate</a> and described by
Lee Salzman and Jonathan Aldrich. I'll try to introduce the semantics
as I understand them to an audience used to class-based multiple
dispatch, but I'm left with some questions that I don't know how to
answer, not being used to programming in this way myself.</p>
<p>So, first, what's going on? Well, the proper answer might be to read
the linked papers, which have a relatively formal specification of the
semantics, but the high-level idea could perhaps be summarised as
finding what happens when you try to support prototype-based object
systems (where the normal way to instantiate an object is to copy
another one; where objects implement some of their functionality by
delegating to other objects; and where single-dispatch methods are
stored in the object itself) and multiple dispatch systems (where
methods do not have a privileged receiver but dispatch on all of their
arguments) simultaneously. The authors found that they could
implement some reasonable semantics, and perform dispatch reasonably
efficiently, by storing some dispatch metainformation within the
objects themselves. The example code, involving the interactions
between fish, healthy sharks and dying sharks, can be translated into
my extended-specializer CL as:</p>
<pre><code>(defpvar /root/ (make-instance 'prototype-object :delegations nil))
(defpvar /animal/ (clone /root/))
(defpvar /fish/ (clone /root/))
(defpvar /shark/ (clone /root/))
(defpvar /healthy-shark/ (clone /root/))
(defpvar /dying-shark/ (clone /root/))
(add-delegation /fish/ /animal/)
(add-delegation /shark/ /animal/)
(add-delegation /shark/ /healthy-shark/)
(defgeneric encounter (x y)
(:generic-function-class prototype-generic-function))
(defmethod encounter ((x /fish/) (y /healthy-shark/))
(format t "~&~A swims away~%" x))
(defmethod encounter ((x /fish/) (y /animal/))
x)
(defgeneric fight (x y)
(:generic-function-class prototype-generic-function))
(defmethod fight ((x /healthy-shark/) (y /shark/))
(remove-delegation x)
(add-delegation x /dying-shark/)
x)
(defmethod encounter ((x /healthy-shark/) (y /fish/))
(format t "~&~A swallows ~A~%" x y))
(defmethod encounter ((x /healthy-shark/) (y /shark/))
(format t "~&~A fights ~A~%" x y)
(fight x y))
</code></pre>
<p>(compare figures 4 and 7 of
[<a href="http://files.slatelanguage.org/doc/pmd/ecoop.pdf">1</a>]; <code>defpvar</code>
is secretly just
<a href="http://www.lispworks.com/reference/HyperSpec/Body/m_defpar.htm"><code>defvar</code></a>
with some extra debugging information so I don't go crazy trying to
understand what a particular <code>#<PROTOTYPE-OBJECT ...></code> actually is.)</p>
<p>Running some of the above code with</p>
<pre><code>(encounter (clone /shark/) (clone /shark/))
</code></pre>
<p>prints</p>
<pre><code>#<PROTOTYPE-OBJECT [/HEALTHY-SHARK/, /ANIMAL/] {10079A8713}> fights
#<PROTOTYPE-OBJECT [/HEALTHY-SHARK/, /ANIMAL/] {10079A8903}>
</code></pre>
<p>and returns</p>
<pre><code>#<PROTOTYPE-OBJECT [/DYING-SHARK/, /ANIMAL/] {10079A8713}>
</code></pre>
<p>(and I'm confident that that's what is meant to happen, though I don't
really understand why in this model sharks aren't fish).</p>
<p>The first question I have, then, is another lazyweb question: are
there larger programs written in this style that demonstrate the
advantages of prototypes with multiple dispatch (specifically over
classes with multiple dispatch; i.e. over regular CLOS). I know of
<a href="https://github.com/sykopomp/sheeple">Sheeple</a>, another lisp
implementation of prototype dispatch, probably different in subtle or
not-so-subtle ways from this one; what I'm after, though, probably
doesn't exist: if there's no easy way of using prototype dispatch in
Lisp, it won't be used to solve problems, and some other way will be
used instead (let's call that the computer programmer's weak version
of the Sapir-Whorf hypothesis). What's the canonical example of a
problem where prototype-based object systems shine?</p>
<p>The second question I have is more technical, and more directly
related to the expected semantics. In particular, I don't know what
would be expected in the presence of method redefinition, or even if
method redefinition is a concept that can make sense in this world.
Consider</p>
<pre><code>(defpvar /a/ (clone /root/))
(defgeneric foo (x)
(:generic-function-class prototype-generic-function))
(defmethod foo ((x /a/)) `(foo[1] ,x))
(defpvar /b/ (clone /a/))
(foo /a/) ; => (FOO[1] /A/)
(foo /b/) ; => (FOO[1] /B/)
(defmethod foo ((x /a/)) `(foo[2] ,x))
(foo /a/) ; => (FOO[2] /A/)
(foo /b/) ; => ???
</code></pre>
<p>What should that last form return? Arguments from the
prototype-oriented world would, I suspect, lead to the desired return
value being <code>(FOO[1] /B/)</code>, as the redefinition of the method on <code>foo</code>
specialized to <code>/a/</code> is completely irrelevant to <code>/b/</code>. This is my
reading of the semantics described in
[<a href="http://files.slatelanguage.org/doc/pmd/ecoop.pdf">1</a>], for what
it's worth. Arguments from the world of generic functions and
expected behaviour would probably argue for <code>(FOO[2] /B/)</code>, because
redefining a method is an action on a generic function, not an action
on a set of application objects. And the argument of my
implementation in practice (at present, subject to change) is to
signal
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_no_app.htm"><code>no-applicable-method</code></a>,
because method redefinition is the successive removal of the old
method and addition of the new one, and removal of the old method of
the generic function affects dispatch on all the objects, whereas
adding the new one affects dispatch on just <code>/a/</code>.</p>
the dangers of writing lesshttp://christophe.rhodes.io/notes/blog/posts/2014/the_dangers_of_writing_less/2014-01-13T20:35:49Z2014-01-11T13:57:33Z
<p>A year or so ago, I wrote a couple of blog entries on precompiling
discriminating functions for generic functions, both given
<a href="http://www.advogato.org/person/crhodes/diary/160.html">mostly class-based dispatch</a>
and also when
<a href="http://www.advogato.org/person/crhodes/diary/162.html">most of the methods were specialized on individual objects</a>
(<em>i.e.</em> methods with specializers of class
<a href="http://mop.lisp.se/concepts.html#inherit-struct-figure"><code>eql-specializer</code></a>).</p>
<p>I signed off the second entry with</p>
<blockquote><p>Next up, unless I've made further oversights which need correction:
automating this process, and some incidental thoughts.</p></blockquote>
<p>and of course never got back to this topic. Now it's over a year
later, and I can no longer remember either my incidental thoughts,
which I'm sure were fascinating, nor my strategy for automating this
(because this was an attempt to address an actual user need, in – if I
remember correctly – a CL implementation of
<a href="http://code.google.com/p/protobuf">protobuf</a>). Suggestions for what
I might have been thinking at the time gratefully received.</p>
<p>Write more: you know it makes sense.</p>
more efficient hyperlinked blogginghttp://christophe.rhodes.io/notes/blog/posts/2014/more_efficient_hyperlinked_blogging/2014-01-06T22:02:46Z2014-01-06T22:02:46Z
<p>How <a href="http://christophe.rhodes.io/notes/tag/meta/">meta</a>. To maintain my progress on my
<a href="http://christophe.rhodes.io/notes/blog/posts/2013/new_year's_resolution/">new year's resolution</a>, I have written <a href="http://christophe.rhodes.io/notes/blog/posts/2014/more_efficient_hyperlinked_blogging/heuristic-linkify.el">some code</a> (<em>*gasp!*</em>)
– yes, that counts as writing. And what does that code do? Why, it
makes me more efficient at highly hyperlinked blogging: it is a
certain amount of fairly trivial and mildly tedious elisp, which
allows the easy insertion of markdown markup to create links to
various authoritative sources of information about Lisp. Well, OK, to
the Hyperspec and the MOP dictionary, but as an implementor that's all
I really need, right? So, now I can talk about
<a href="http://mop.lisp.se/dictionary.html#compute-effective-method"><code>compute-effective-method</code></a>
or
<a href="http://mop.lisp.se/dictionary.html#make-method-lambda"><code>make-method-lambda</code></a>
and my eager readers can be taken to the relevant documentation at the
speed of thought.</p>
<p>Questions that arose during the process:</p>
<ul>
<li>why are all the fake packages in
<a href="https://github.com/slime/slime/blob/master/hyperspec.el"><code>hyperspec.el</code></a>
created with <code>(make-vector 67 0)</code>?</li>
<li>has anyone in the 23 years since
<a href="http://en.wikipedia.org/wiki/The_Art_of_the_Metaobject_Protocol">AMOP</a>
was published ever been glad that the MOP standardizes the
<a href="http://mop.lisp.se/dictionary.html#extract-lambda-list"><code>extract-lambda-list</code></a>
and
<a href="http://mop.lisp.se/dictionary.html#extract-specializer-names"><code>extract-specializer-names</code></a>
functions? (Fun fact: <a href="http://www.sbcl.org/">SBCL</a> also has
<code>extract-parameters</code> and <code>extract-required-parameters</code> functions,
unexported and unused.)</li>
</ul>
seeking real life uses for generalized specializershttp://christophe.rhodes.io/notes/blog/posts/2014/seeking_real_life_uses_for_generalized_specializers/2014-01-01T20:20:56Z2014-01-01T20:20:56Z
<p>Some time ago (call it half a decade or so),
<a href="http://www.cadence.com/community/posts/team-skill.aspx">Jim Newton</a>
of <a href="http://www.cadence.com">Cadence</a> and I did some work on
<a href="http://dx.doi.org/10.3217/jucs-014-20-3370">extensible specializers</a>:
essentially coming up with a proof-of-concept protocol to allow users
to define their own specializers with their own applicability and
ordering semantics. That's a little bit vague; the concrete example
we used in the writeup was a code walker which could warn about the
use of unbound variables (and the non-use of bindings), and which
implemented its handling of special forms with code of the form:</p>
<pre><code>(defmethod walk ((expr (cons (eql 'quote))) env call-stack)
nil)
(defmethod walk ((var symbol) env call-stack)
(let ((binding (find-binding env var)))
(if binding
(setf (used binding) t)
(format t "~&unbound: ~A: ~A~%" var call-stack))))
(defmethod walk ((form (cons (eql 'lambda))) env call-stack)
(destructuring-bind (lambda lambda-list &rest body) form
(let* ((bindings (derive-bindings-from-ll lambda-list))
(env* (make-env bindings env)))
(dolist (form body)
(walk form env* (cons form call-stack)))
(dolist (binding bindings)
(unless (used (cdr binding))
(format t "~&unused: ~A: ~A~%" (car binding) call-stack))))))
</code></pre>
<p>The idea here is that it's possible to implement support in the walker
for extra special forms in a modular way; while this doesn't matter
very much in Common Lisp (which, famously, is not dead, just smells
funny), in other languages which have made other tradeoffs in the
volatility/extensibility space. And when I say “very much” I mean it:
even SBCL allows extra special forms to be loaded at runtime; the
<code>sb-cltl2</code> module includes an implementation of <code>compiler-let</code>, which
requires its own special handling in the codewalker which is used in
the implementation of CLOS.</p>
<p>So modularity and extensibility is required in a code walker, even in
Common Lisp implementations; in
<a href="http://en.wikipedia.org/wiki/Cadence_SKILL">Cadence Skill++</a> it might
even be generally useful (I don't know). In SBCL, the extensibility
is provided using an explicit definer form; <code>sb-cltl2</code> does</p>
<pre><code>(defun walk-compiler-let (form context env)
#1=#<implementation elided>)
(sb-walker::define-walker-template compiler-let walk-compiler-let)
</code></pre>
<p>and that's not substantially different from</p>
<pre><code>(defmethod sb-walker:walk ((form (cons (eql 'compiler-let))) context env)
#1#)
</code></pre>
<p>So far, so unexpected, for Lisp language extensions at least: of
<em>course</em> the obvious test for a language extension is how many lines
of code it can save when implementing another language extension.
Where this might become interesting (and this, dear lazyweb, is where
you come in) is if this kind of extension is relevant in application
domains. Ideally, then, I'm looking for real-life examples of
patterns of selecting ‘methods’ (they don't have to be expressed as
Lisp methods, just distinct functions) based on attributes of objects,
not just the objects' classes. The walker above satisfies these
criteria: the objects under consideration are all of type <code>symbol</code> or
<code>cons</code>, but the dispatch partly happens based on the <code>car</code> of the
<code>cons</code> – but are there examples with less of the meta nature about
them?</p>
<p>(I do have at least one example, which I will keep to myself for a
little while: I will return to this in a future post, but for now I am
interested in whether there's a variety of such things, and whether
the generalization of specializer metaobjects is capable of handling
cases I haven't thought of yet. Bonus points if the application
requires multiple dispatch and/or non-standard method combination.)</p>