Structure and interpretation of computer programs

Structure and interpretation of computer programs

nil

Harold Abelson and Gerald Jay Sussman. Structure and Interpretation of Computer Programs. MIT Press. 1985.

A book once described (by me, actually) as “the only computer science book worth reading twice”, and which was the foundational text for teaching programming at MIT for decades.

There are many reasons that this book is so popular and long-lived. It’s resolutely an introductory text, but it treats topics that are uncommon in introductions, and does so to a depth that’s quite astonishing – although it has to be said that the authors avoid the more complex constructions like conditions and the complexities of macros, (They do deal with continuations, however, which are essential for good Scheme programming.)

But what other introduction to programming includes a complete meta-linguistic re-implementation of the language itself? – and in two different styles! It can do this because Scheme is so regular and so simple – homoiconic (one representation for programs and data), (although they don’t use that term).

Learn Common Lisp in Y minutes

Learn Common Lisp in Y minutes

https://learnxinyminutes.com/docs/common-lisp/

A one-web-page introduction to Common Lisp covering pretty much all the language in enough detail to at least start writing simple command-line programs (and understanding those of others). Includes macros and CLOS. Quite an achievement to make it all so readable.

Practical Common Lisp

Practical Common Lisp

nil

Peter Seibel. Practical Common Lisp. Apress. ISBN 978-1-4302-0017-8. 2005.

The classic, very thorough and hands-on tutorial introduction that doesn’t skip the hard parts like the condition system and non-local blocks and exists (and the relationship between the two). It’s also got good chapters on CLOS.

The text is complemented by a set of modern examples, for web services, database, and binary file parsers: quite a long way removed from the examples in many introductory texts. It doesn’t make much use of macro programming in these examples, which is a shame, so follow with On Lisp or Let over Lambda once the structure of the language is clear.

TIL: An RSS-focused search engine

TIL: An RSS-focused search engine

Today I learned about feedle, a search engine focused on searching blogs and podcasts – web sites that export an RSS feed, in other words. And the search results are themselves RSS feed that can be subscribed to live.

This feels like a quite a big thing for accessing content without resort to the internet giants, and for the IndieWeb in general. It means that search can prefer syndicated and typically small-scale content rather than being influenced by search engine optimisation (SEO) or sponsorship affecting the link rankings.

Of course this also need management, and feedle is a curated source: you have to submit your RSS feed to it for review and (hopefully) inclusion. I’ve done that for this site’s feed.

Locally overriding a function throughout a dynamic extent

Locally overriding a function throughout a dynamic extent

A horribly dangerous but occasionally useful Lisp technique.

My use case is as follows. ebib has a command to copy a formatted reference to the kill ring, using citar-citeproc-format-reference to actually do the formatting. This means it’s easy to change the style of the formatted reference. However, citar-citeproc-format-reference itself uses citar-render-bib with a plain-text formatter. This is a sensible default, but since I’m almost always copying references into org-more documents, it loses a lot of information: it’d be better to use the org formatter, but there’s no argument to specify it.

Clearly the correct solution is to change citar-citeproc-format-reference to take a key or optional argument to specify the formatter, but that involves changing someone else’s code. The hacker solution is to change the call (citeproc-render-bib proc 'plain) to (citeproc-render-bib proc 'org), but without re-writing the entire surrounding function to keep the change just to the case where I need it.

One way to do this would be to define a variant citeproc-render-bib that ignores its second argument (the formatter) and always uses 'org instead, and then substitute this variant for the original – but only in the dynamic extent of a particular call to citar-citeproc-format-reference. In most languages this would be impossible – but not in Emacs Lisp.

The solution is to use cl-letf, which overrides the values of general places for the duration of its body forms and restores the original value on exit (normal or otherwise). The important point is that the change occurs across the extent of the body – the body and all the code called from the body – and not merely in the scope of the body, which would only affect calls made there directly.

For example, consider in the following:

(defun f(a b)
  (+ a b))

(defun first (a)
  (f a 10))

Which when called gives:

(first 26)
36

If we want to override the default value (10) that’s passed to f and instead use 25, we can define a new version that ignores the second argument and uses our preferred default, and then temporarily override the definition of f in the calling environment. If we want to use the original in the overriding definition we need to grab it first. This gives:

(let ((origf (symbol-function 'f)))
  (cl-letf (((symbol-function 'f) (lambda (a b)
				    (funcall origf a 25))))
    (first 26)))
51

What’s going on? The cl-letf macro is like let but works with general places (as in setf). It sets the places in its argument list for the duration of its body, and then restores them on exit, regardless of whether that exit is normal or via a condition.

The (symbol-function 'f) form returns the place that stores the function associated with symbol f. We use it twice: once to capture this function so we can use it later, and once to identify the place where we store our new variant function. This new binding is then used for all calls made from the body of the cl-letf, regardless of depth, so the call to first makes use of our variant definition of f rather than the original – but with the original then being used in the variant in our case!

If we’d used let or cl-flet instead of cl-letf we wouldn’t have got the behaviour we’re looking for:

(let ((origf (symbol-function 'f)))
  (cl-flet ((f (a b)
	      (funcall origf a 25))))
    (first 26))
36

Why? Because let and cl-flet work over the scope of the body, so only calls to f directly from the body of the assignment are affected – not calls from calls. This is a great illustration of the difference between the closely-related concepts of (static, lexical) scope and (dynamic, run-time) extent, incidentally.

I did say it was horrible :-). It’s basically like adding temporary :around advice, and could probably benefit from a macro to wrap it up. It’s also inconceivable that it’s thread- or co-routine-safe, although I haven’t checked.

Part of the horribleness comes from the fact that the redefinition is made for the entire dynamic extent of the body forms, which means all instances of the overridden function will use the overridden value. There might be more than you think! But for well-understood code it’s sometimes useful, avoiding duplicating code to make tiny changes.