Older blog entries for crhodes (starting at number 177)

more efficient hyperlinked blogging

How meta. To maintain my progress on my new year's resolution, I have written some code (*gasp!*) – 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 compute-effective-method or make-method-lambda and my eager readers can be taken to the relevant documentation at the speed of thought.

Questions that arose during the process:

  • why are all the fake packages in hyperspec.el created with (make-vector 67 0)?
  • has anyone in the 23 years since AMOP was published ever been glad that the MOP standardizes the extract-lambda-list and extract-specializer-names functions? (Fun fact: SBCL also has extract-parameters and extract-required-parameters functions, unexported and unused.)

Syndicated 2014-01-06 22:02:46 from notes

bugs all the way down

There are times when being in control of the whole software stack is a mixed blessing.

While doing investigations related to my previous post, I found myself wondering what the arguments and return values of make-method-lambda were in practice, in SBCL. So I did what any self-respecting Lisp programmer would do, and instead of following that link and decoding the description, I simply ran (trace sb-mop:make-method-lambda), and then ran my defmethod as normal. I was half-expecting it to break instantly, because the implementation of trace encapsulates named functions in a way that changes the class of the function object (essentially, it wraps the existing function in a new anonymous function; fine for ordinary functions, not so good for generic-function objects), and I was half-right: an odd error occurred, but after trace printed the information I wanted.

What was the odd error? Well, after successfully calling and returning from make-method-lambda, I got a no-applicable-method error while trying to compute the applicable methods for... make-method-lambda. Wait, what?

SBCL's CLOS has various optimizations in it; some of them have been documented in the SBCL Internals Manual, such as the clever things done to make slot-value fast, and specialized discriminating functions. There are plenty more that are more opaque to the modern user, one of which is the “fast method call” optimization. In that optimization, the normal calling convention for methods within method combination, which involves calling the method's method-function with two arguments – a list of the arguments passed to the generic function, and a list of next methods – is bypassed, with the fast-method-function instead being supplied with a permutation vector (for fast slot access) and next method call (for fast call-next-method) as the first two arguments and the generic function's original arguments as the remainder, unrolled.

In order for this optimization to be valid, the call-method calling convention must be the standard one – if the user is extending or overriding the method invocation protocol, all the optimizations based on assuming that the method invocation protocol might be invalid. We have to be conservative, so we need to turn this optimization off if we can't prove that it's valid – and the only case where we can prove that it's valid is if only the system-provided method on make-method-lambda has been called. But we can't communicate that after the fact; although make-method-lambda returns initargs as well as the lambda, an extending method could arbitrarily mess with the lambda while returning the initargs the system-provided method returns. So in order to find out whether the optimization is safe, we have to check whether exactly our system-provided method on make-method-lambda was the applicable one, so there's an explicit call to compute-applicable-methods of make-method-lambda after the method object has been created. And make-method-lambda being traced and hence not a generic-function any more, it's normal that there's an error. Hooray! Now we understand what is going on.

As for how to fix it, well, how about adding an encapsulations slot to generic-function objects, and handling the encapsulations in sb-mop:compute-discriminating-function? The encapsulation implementation as it currently stands is fairly horrible, abusing as it does special variables and chains of closures; there's a fair chance that encapsulating generic functions in this way will turn out a bit less horrible. So, modify sb-debug::encapsulate, C-c C-c, and package locks strike. In theory we are meant to be able to unlock and continue; in practice, that seems to be true for some package locks but not others. Specifically, the package lock from setting the fdefinition from a non-approved package gives a continuable error, but the ones from compiling special declarations of locked symbols have already taken effect and converted themselves to run-time errors. Curses. So, (mapcar #'unlock-package (list-all-packages)) and try again; then, it all goes well until adding the slot to the generic-function class (and I note in passing that many of the attributes that CL specifies are generic-function SBCL only gives to standard-generic-function objects), at which point my SLIME repl tells me that something has gone wrong, but not what, because no generic function works any more, including print-object. (This happens depressingly often while working on CLOS).

That means it's time for an SBCL rebuild, which is fine because it gives me time to write up this blog entry up to this point. Great, that finishes, and now we go onwards: implementing the functionality we need in compute-discriminating-function is a bit horrible, but this is only a proof-of-concept so we wrap it all up in a labels and stop worrying about 80-column conventions. Then we hit C-c C-c and belatedly remember that redefining methods involves removing them from their generic function and adding them again, and doing that to compute-discriminating-function is likely to have bad consequences. Sure enough:

  There is no applicable method for the generic function 
  #<STANDARD-GENERIC-FUNCTION COMPUTE-DISCRIMINATING-FUNCTION (1)>
when called with arguments
  (#<STANDARD-GENERIC-FUNCTION NO-APPLICABLE-METHOD (1)>).

Yes, well. One (shorter) rebuild of just CLOS later, and then a few more edit/build/test cycles, and we can trace generic functions without changing the identity of the fdefinition. Hooray! Wait, what was I intending to do with my evening?

Syndicated 2014-01-03 22:30:36 (Updated 2014-01-03 22:36:49) from notes

seeking real life uses for generalized specializers

Some time ago (call it half a decade or so), Jim Newton of Cadence and I did some work on extensible specializers: 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:

  (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))))))

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 sb-cltl2 module includes an implementation of compiler-let, which requires its own special handling in the codewalker which is used in the implementation of CLOS.

So modularity and extensibility is required in a code walker, even in Common Lisp implementations; in Cadence Skill++ it might even be generally useful (I don't know). In SBCL, the extensibility is provided using an explicit definer form; sb-cltl2 does

  (defun walk-compiler-let (form context env)
  #1=#<implementation elided>)
(sb-walker::define-walker-template compiler-let walk-compiler-let)

and that's not substantially different from

  (defmethod sb-walker:walk ((form (cons (eql 'compiler-let))) context env)
  #1#)

So far, so unexpected, for Lisp language extensions at least: of course 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 symbol or cons, but the dispatch partly happens based on the car of the cons – but are there examples with less of the meta nature about them?

(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.)

Syndicated 2014-01-01 20:20:56 from notes

new year's resolution

So here we are: 31st December. Sitting here, with a film of dubious plot playing on the television, waiting for a sufficient approximation to the New Year to arrive, and thinking about the year just gone and the year that is yet to come, and making resolutions. And on looking back at 2013, one thing that I'm not happy about (while counting my many, many blessings) is the level of output: somewhat limited code, very limited publications – honestly, thanks to my PhD students Ray and Polina for any publications at all: they did the vast majority of the work on papers with my name listed as co-author. There are of course reasons for that, stemming both from personal and professional life, but it doesn't change my dissatisfaction with the end result: there's more that I can do, and more that I should be doing. And doing, as Yoda never said, leads to writing: if the act is sufficiently interesting, it should be natural to talk to people about it, to be enthusiastic about it, and to write about it.

I certainly feel that it's in my nature not to be enthusiastic. Friends, if I have any left, are likely to put my typical disposition somewhere near the cynical extreme – I like to think not without some provocation, but I can also acknowledge that an excess of cynicism can obscure those things that are in fact worth celebrating. I'm certainly not promising to be less cynical about those things which deserve it – many an academic will point at a number of things wrong with the current state of the profession, and I think we're not all harking back to a mislaid golden age when academics were free and academia was purely communitarian – but I think I need to act in positive ways as well as grind my teeth and bang my head against the wall when the negatives arise.

Baby steps first, though. The commitment: I will write more. I will write more about my ideas, my processes, my interactions and my achievements, and I'll do it publically where possible, as it's part of my self-image as an academic to educate by example. (And maybe at some point I will also make this website look pretty. If you're reading this through syndication, count yourself lucky.)

Syndicated 2013-12-31 21:49:30 from notes

some sbcl wiki entries

One of the potential advantages of this new wiki/blog setup is that I should be able to refer easily to my notes in my blog. It's true that the wiki-like content will change, whereas a mostly-static blog entry will naturally refer to the content of the wiki as it is at the point of blogging; in theory I should be able to find the content at the time that the link was made through a sufficiently advanced use of the version control system backing the ikiwiki installation, and in practice the readers of the blog (if any) are likely to follow (or not) any links within a short time-window of the initial publication of any given entry. So that shouldn't prove too confusing.

In order to test this, and to provide some slightly-relevant content for anyone still reading this on planet lisp: I've transferred my non-actionable notes from my sbcl org-mode file to an sbcl wiki section. This new setup gets heaps of bonus points if someone out there implements the development projects listed there as a result of reading this post, but even if not, it's a useful decluttering...

Syndicated 2013-12-30 22:05:24 from notes

29 Dec 2013 (updated 30 Dec 2013 at 11:20 UTC) »

new year new gpg key

I've been putting this off for long enough. My current PGP key was generated in a different age, with somewhat different threat models and substantially different computational power (let alone social and political power) available to those who might be interested in subverting the general ability of individuals to identify themselves and communicate in private. It's true that not much of what I do is likely to be of vast interest to security agents worldwide, but as SBCL release manager (on holiday for a month!) I do publish documents that purport to assure that the source code and binary that users can obtain are unmodified from my personal copies.

Therefore, I've created a new key, with 2013-era configuration settings: 2048-bit RSA encryption and signing, and SHA-1 hashes undesired (though still accepted, given the protocol requirement). I've created a transition document, signed with both keys, to help interested parties with the transition; while my older key will remain valid for a while (I have a stack of business cards with its fingerprint on to get through...) the new key should be preferred in all situations where that makes sense.

Observations:

  1. This is all quite fiddly and complicated. There's a reason (well, several reasons: all those business cards!) I have been putting this off for a while. I understand why at least some of the knobs and levers are there; I've taught Computer Security at undergraduate level – but I'm still not confident that I have got everything right, and that's worrying both personally and systemically.
  2. epa-sign-region appears to malfunction for me when given a prefix argument: what it's meant to do is give a UI for selecting keys to use for signing, and the option of which kind of signature to generate. What it actually seems to do is generate an undecryptable PGP Message block. [edit: this was caused by epa/epg version skew, from an old installation of the Debian easypg package. ]
  3. I stumbled over the --escape-from-lines GnuPG configuration option while reading the documentation. It's on by default.
  4. GnuPG is crowdfunding a new website and some infrastructure.

Syndicated 2013-12-29 22:04:59 (Updated 2013-12-30 10:16:26) from notes

new year's resolution more preparations

This new blogging setup, with the new domain, new feeds, and ideally new workflow, suggest the analysis of what was problematic with the old one.

Back when I was a PhD student, doing everything I could to avoid work on my thesis, I stumbled upon a culture of Lisp and Free Software developers – which may only come across as half ridiculous now but in 2001 seemed doubly counter-cultural. And so I joined a blogging platform for Free Software types that also happened to double as a testbed for trust metric research. And at the time, this offered neat features not easily available elsewhere: the word “blog” itself was only about two years old, and pertelote maintained a blog by hand for years, so having somewhere which would host my writing, and which moreover had some of the Social Network about it (the advogato userbase was responsible for certification of individuals' contribution to Free Software, and several of my then collaborators were on advogato before me) was ideal.

The principal downside for me, then as now, is the use of web browsers as the interface for text entry; a <textarea> just isn't rich enough in functionality. The situation is better now than it was – (mostly) gone are the days when an incautious C-q would instantly close all browser windows, including the one in which your meticulously-crafted draft was waiting for final polish before being submitted as a diary entry – but it's still a long way from using my text editor, moderately customized to my way of working, with all the comfort that that brings.

Meanwhile, for work, I've successfully used ikiwiki to document the processes and data around some of my academic administrative responsibilities over the years: postgraduate tutor, employability coordinator, director of postgraduate studies (the reality is even less glamorous than these titles); it's been really nice to be able to update documents while not at my desk, or while commuting, and even if I have never grown to love mercurial (ikiwiki's at-one-time default DVCS backend) it is at least worth knowing.

So when contemplating how to set up systems less likely to impede my productivity, it's perhaps natural that I should return to a recent success, and set up an ikiwiki instance. This time, though, I'm (obviously) explicitly using ikiwiki's support for blogging as well as its natural wiki nature; the idea is that the weblog is for timely, pertinent comments, while the wiki is for incrementally-refined notes on all subjects – probably replacing my org-mode note-taking habit, which while lovely relies too much on having a single emacs instance available at all times for when inspiration strikes. I fully expect to keep the org-mode setup I have for Getting (Some) Things Done, but will likely migrate the non-actionable notes I have to this wiki as and when.

Speaking of new feeds, the advogato tag will be punned into denoting content that should be syndicated to my diary on advogato. It's perhaps inevitable that something will go wrong, and including html tags in the text of the first syndicated entry is an excellent way to ensure that that happens, so if there's an editable textarea, escaped less-than and greater-than signs, or a sentence that seems to be missing something, then the Unix-Haters among the readers can reminisce about seeing >From in their e-mails oh wait that still happens...

Syndicated 2013-12-28 17:11:25 from notes

One of the portions of my job as an academic is to secure funding to enable the research that I would like to happen to be done. I'm lucky to find myself a member of a project that has been funded under the AHRC's “Digital Transformations” banner: my colleague and office-mate Tim Crawford [*] (once part of the Early Music revolution, late of The Parley of Instruments) is leading a team from a number of Universities in a three-year project in “Transforming Musicology”.

The project has multiple components; among other things, we'll be looking at methods for digitizing and interrogating historical source materials, including manuscripts and printed music, as well as relating those to modern performance artifacts; we'll be looking at the perception of music in context, trying to understand the compositional use and listener recognition of leitmotives (as in Wagner opera, but also in film scores); and we'll be trying to characterise the effects that social media, broadly considered, have had on the production, consumption and study of music itself.

On this last point, I have funding available for a PhD studentship. The award covers University fees, and provides a tax-free stipend (starting at £15,700) for three years, at the end of which the expectation is that there would be a sufficient body of research to write up as a dissertation for the award of a PhD. The full advert has all the details, but broadly I'm looking for someone who is sufficiently interested in the topic of music and social media to work at it for three to four years, has good computational knowledge and skills (Common Lisp programming experience definitely wouldn't hurt, but isn't necessary) and has training or relevant experience in music or social science. Does that sound like you? Please apply now! (Not sure? I'm happy to discuss the studentship or the project with anyone: just send me an e-mail).

[*] Tim Crawford has a Rhodes-Rhodes number of two.

SBCL’s code is hosted on SourceForge, for reasons that might be accurately summarized as historical. The occasional downtime aside, it has generally worked.

This weekend SourceForge “upgraded” (for which read “changed”) SBCL’s hosting to its new Allura implementation of its hosting infrastructure. In the process, the git repositories have changed their location. I hope that all people with commit access know where the new writeable location is; read-only access is from git://git.code.sf.net/p/sbcl/sbcl or http://git.code.sf.net/p/sbcl/sbcl. Please update your remotes.

In a similar fashion to embarrassing post-SBCL-release bug fixes, a bug fix to my previous diary entry. Having established the contrast between the corporate “interesting problems which we happen to solve with Lisp” presentations and those focussed on the lisp ecosystem itself, I intended to say that the talk given by Tiago Maduro Dias and Luís Oliveira from SISCOG about their company presented a difficult and interesting problem, but also presented their individual and corporate experiences of working with Lisp, which I think plays to the real strength of this kind of event, by offering experiences for other practitioners to learn from. I particularly loved the deadpan reporting of the informal surveys of the SISCOG engineers’ attitudes to Lisp and Emacs, and the frank assessments that some of the pieces are not good enough.

Instead of saying all that about the SISCOG talk, I left it out completely. Go me. Since making amends for that gives me another chance to talk about last week’s events, I'll also mention that I “live-tweeted” as an experiment; I'm not sure whether it's more annoying than useful, but the theory is that it acts as marketing and public relations as well as a handy notepad for when reconstructing events to make blog posts. I also managed to squeeze a tiny bit of development in: a minor improvement to SBCL’s console debugger, a fix to a long-standing bug in SBCL’s type derivation of expt, and adhering to codepoint-by-codepoint case consistency requirements imposed by the ANSI CL standard for characters composed with ypogegrammeni (that’s iota subscript to Attic scholars, or “is that a speck of dust or what?” to you and me).

168 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!