pages tagged cclnoteshttp://christophe.rhodes.io/notes/tag/ccl/notesikiwiki2018-05-26T08:02:23Zels2018 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>
reproducible builds - a month ahead of schedulehttp://christophe.rhodes.io/notes/blog/posts/2014/reproducible_builds_-_a_month_ahead_of_schedule/2014-11-10T17:00:04Z2014-11-08T22:38:14Z
<p>I think this might be my last blog entry on the subject of building
<a href="http://www.sbcl.org/">SBCL</a> for a while.</p>
<p>One of the premises behind SBCL as a separate entity from
<a href="http://www.cons.org/cmucl/">CMUCL</a>, its parent, was to make the
result of its build be independent of the compiler used to build it.
To a world where separate compilation is the norm, the very idea that
building some software should persistently modify the state of the
compiler probably seems bizarre, but the Lisp world evolved in that
way and Lisp environments (at least those written in themselves)
developed build recipes where the steps to construct a new Lisp system
from an old one and the source code would depend critically on
internal details of <em>both</em> the old and the new one: substantial
amounts of introspection on the build host were used to bootstrap the
target, so if the details revealed by introspection were no longer
valid for the new system, there would need to be some patching in the
middle of the build process. (How would you know whether that was
necessary? Typically, because the build would fail with a
more-or-less – usually more – cryptic error.)</p>
<p>Enter SBCL, whose strategy is essentially to use the source files
first to build an SBCL!Compiler running in a host Common Lisp
implementation, and then to use that SBCL!Compiler to compile the
source files again to produce the target system. This requires some
contortions in the source files: we must write enough of the system in
portable Common Lisp so that an arbitrary host can execute
SBCL!Compiler to compile SBCL-flavoured sources (including the
standard headache-inducing <code>(defun car (list) (car list))</code> and
similar, which works because SBCL!Compiler knows how to compile calls
to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_car_c.htm"><code>car</code></a>).</p>
<p>How much is “enough” of the system? Well, one answer might be when
the build output actually works, at least to the point of running and
executing some Lisp code. We got there about
<a href="http://www.advogato.org/person/crhodes/diary/23.html">twelve years ago</a>,
when <a href="http://ccl.clozure.com/">OpenMCL</a> (as it was then called)
compiled SBCL. And yet... how do we know there aren't odd differences
that depend on the host compiler lurking, which will not obviously
affect normal operation but will cause hard-to-debug trouble later?
(In fact there were plenty of those, popping up at inopportune
moments).</p>
<p>I’ve been working intermittently on dealing with this, by attempting
to make the Common Lisp code that SBCL!Compiler is written in
sufficiently portable that executing it on different implementations
generates bitwise-identical output. Because then, and only then, can
we be confident that we are not depending in some unforseen way on a
particular implementation-specific detail; if output files are
different, it <em>might</em> be a harmless divergence, for example a
difference in ordering of steps where neither depends on the other, or
it might in fact indicate a leak from the host environment into the
target. Before this latest attack at the problem, I last worked on it
seriously in 2009, getting most of the way there but with some
problems remaining, as measured by the number of output files (out of
some 330 or so) whose contents differed depending on which host Common
Lisp implementation SBCL!Compiler was running on.</p>
<p>Over the last month, then, I have been slowly solving these problems,
one by one. This has involved refining what is probably my second
most useless skill, working out what SBCL fasl files are doing by
looking at their contents in a text editor, and from that intuiting
the differences in the implementations that give rise to the
differences in the output files. The final pieces of the puzzle fell
into place earlier this week, and the
<a href="http://sourceforge.net/p/sbcl/sbcl/ci/dc73c76ff9fbe44d3a9be5722655ec7ba7af3b92/">triumphant commit</a>
announces that as of Wednesday all 335 target source files get
compiled identically by SBCL!Compiler, whether that is running under
Clozure Common Lisp (32- or 64-bit versions), CLISP, or a different
version of SBCL itself.</p>
<p>Oh but wait. There is another component to the build: as well as
SBCL!Compiler, we have SBCL!Loader, which is responsible for taking
those 335 output files and constructing from them a Lisp image file
which the platform executable can use to start a Lisp session.
(SBCL!Loader is maybe better known as “genesis”; but it is to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_load.htm"><code>load</code></a>
what SBCL!Compiler is to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_cmp_fi.htm"><code>compile-file</code></a>).
And it was slightly disheartening to find that despite having 335
identical output files, the resulting <code>cold-sbcl.core</code> file differed
between builds on different host compilers, even after I had
remembered to discount the build fingerprint constructed to be
different for every build.</p>
<p>Fortunately, the actual problem that needed fixing was relatively
small: a call to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_maphas.htm"><code>maphash</code></a>,
which (understandably) makes no guarantees about ordering, was used to
affect the Lisp image data directly. I then spent a certain amount of
time being thoroughly confused, having managed to construct for myself
a Lisp image where the following forms executed with ... odd results:</p>
<pre><code>(loop for x being the external-symbols of "CL" count 1)
; => 1032
(length (delete-duplicates (loop for x being the external-symbols of "CL" collect x)))
; => 978
</code></pre>
<p>(shades of
<a href="http://www.advogato.org/person/crhodes/diary/12.html">times</a>
<a href="http://www.advogato.org/person/crhodes/diary/57.html">gone by</a>).
Eventually I realised that</p>
<pre><code>(unless (member (package-name package) '("COMMON-LISP" "KEYWORD" :test #'string=))
...)
</code></pre>
<p>was not the same as</p>
<pre><code>(unless (member (package-name package) '("COMMON-LISP" "KEYWORD") :test #'string=)
...)
</code></pre>
<p>and all was well again, and as of
<a href="http://sourceforge.net/p/sbcl/sbcl/ci/80c4401cf00909700fa942cf8bd34de500cbc73b/">this commit</a>
the <code>cold-sbcl.core</code> output file is identical no matter the build
host.</p>
<p>It might be interesting to survey the various implementation-specific
behaviours that we have run into during the process of making this
build completely repeatable. The following is a probably
non-exhaustive list – it has been twelve years, after all – but maybe
is some food for thought, or (if you have a particularly demonic turn
of mind) an ingredients list for a maximally-irritating CL
implementation...</p>
<ul>
<li>Perhaps most obviously, various constants are
implementation-defined. The ones which caused the most trouble were
undoubtably
<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_most_p.htm"><code>most-positive-fixnum</code></a>
and
<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_most_p.htm"><code>most-negative-fixnum</code></a>
– particularly since they could end up being used in ways where
their presence wasn’t obvious. For example, <code>(deftype fd ()
`(integer 0 ,most-positive-fixnum))</code> has, in the SBCL build
process, a subtly different meaning from <code>(deftype fd () (and
fixnum unsigned-byte))</code> – in the second case, the <code>fd</code> type will
have the intended meaning in the target system, using the target’s
<a href="http://www.lispworks.com/reference/HyperSpec/Body/t_fixnum.htm"><code>fixnum</code></a>
range, while in the first case we have no way of intercepting or
translating the <em>host</em>’s value of <code>most-positive-fixnum</code>. Special
mentions go to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_ar_dim.htm"><code>array-dimension-limit</code></a>,
which caused Bill Newman to be
<a href="http://www.advogato.org/person/wnewman/diary/21.html">cross on the Internet</a>,
and to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_intern.htm"><code>internal-time-units-per-second</code></a>;
I ended up tracking down one difference in output machine code from
a leak of the host’s value of that constant into target code.</li>
<li>Similarly,
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_random.htm"><code>random</code></a>
and
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_sxhash.htm"><code>sxhash</code></a>
quite justifiably differ between implementations. The practical
upshot of that is that these functions can’t be used to implement a
cache in SBCL!Compiler, because the access patterns and hence the
patterns of cache hits and misses will be different depending on the
host implementation.</li>
<li>As I’ve already mentioned,
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_maphas.htm"><code>maphash</code></a>
does not iterate over hash-table contents in a specified order, and
in fact that order need not be deterministic; similarly,
<a href="http://www.lispworks.com/reference/HyperSpec/Body/m_w_pkg_.htm"><code>with-package-iterator</code></a>
can generate symbols in arbitrary orders, and set operations
(<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_isec_.htm"><code>intersection</code></a>,
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_set_di.htm"><code>set-difference</code></a>
and friends) will return the set as a list whose elements are in an
arbitrary order. Incautious use of these functions tended to give
rise to harmless but sometimes hard-to-diagnose differences in
output; the solution was typically to sort the iteration output
before operating on any of it, to introduce determinism...</li>
<li>... but it was possible to get that wrong in a harder-to-detect way,
because
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_sort_.htm"><code>sort</code></a>
isnot specified to be stable. In some implementations, it actually
<em>is</em> a stable sort in some conditions, but for cases where it’s
important to preserve an already-existing partial order,
<code>stable-sort</code> is the tool for the job.</li>
<li>The language specification explicitly says that the initial contents
of uninitialized arrays are undefined. In most implementations, at
most times, executing <code>(make-array 8 :element-type (unsigned-byte
8))</code> will give a zero-filled array, but there are circumstances in
some implementations where the returned array will have arbitrary
data.</li>
<li>Not only are some constants implementation-defined, but so also are
the effects of normal operation on some variables.
<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_gensym.htm"><code>*gensym-counter*</code></a>
is affected by macroexpansion if the macro function calls <code>gensym</code>,
and implementations are permitted to macroexpand macros an arbitrary
number of times. That means that our use of <code>gensym</code> needs to be
immune to whatever the host implementation’s macroexpansion and
evaluation strategy is.</li>
<li>The object returned by
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_by_by.htm"><code>byte</code></a>
to represent a bitfield with size and position is
implementation-defined. Implementations (variously) return
bitmasks, conses, structures, vectors; host return values of <code>byte</code>
must not be used during the execution of SBCL!Compiler. More
subtly, the various
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_boole.htm"><code>boole</code></a>-related
constants
(<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_b_1_b.htm"><code>boole-and</code></a>
and friends) also need special treatment; at one point, their host
values were used when SBCL!Compiler compiled the <code>boole</code> function
itself, and it so happens that CLISP and SBCL both represent the
constants as integers between 0 and 15... but with a different
mapping between operation and integer.</li>
<li>my <a href="http://christophe.rhodes.io/notes/blog/posts/2014/still_working_on_reproducible_builds/">last blog entry</a> talked
about constant coalescing, and about printing of <code>(quote foo)</code>. In
fact printing in general has been a pain, and there are still
significant differences in interpretation or at least in
implementation of pretty-printing: to the extent that at one point
we had to minimize printing <em>at all</em> in order for the build to
complete under some implementations.</li>
<li>there are a number of things which are implementation-defined but
have caused a certain amount of difficulty. Floating point in
general is a problem, not completely solved (SBCL will not build
correctly if its host doesn’t have distinct single- and double-float
types that are at least approximately IEEE754-compliant). Some
implementations lack denormalized numbers; some do not expose signed
zeros to the user; and some implementations compute <code>(log 2d0 10d0)</code>
more accurately than others, including SBCL itself, do. The
behaviour of the host implementation on legal but dubious code is
also potentially tricky: SBCL’s build treats full
<a href="http://www.lispworks.com/reference/HyperSpec/Body/e_warnin.htm"><code>warning</code></a>s
as worthy of stopping, but some hosts emit full warnings for
constructs that are tricky to write in other ways: for example to
write portable code to handle multiple kinds of string, one might
write <code>(typecase string (simple-base-string ...) ((simple-array
character (*)) ...)) (string ...))</code> but some implementations emit
full <code>warning</code>s if a clause in a
<a href="http://www.lispworks.com/reference/HyperSpec/Body/m_tpcase.htm"><code>typecase</code></a>
is completely shadowed by other clauses, and if
<a href="http://www.lispworks.com/reference/HyperSpec/Body/t_base_c.htm"><code>base-char</code></a>
and
<a href="http://www.lispworks.com/reference/HyperSpec/Body/a_ch.htm"><code>character</code></a>
are identical in that implementation the <code>typecase</code> above will
signal.</li>
</ul>
<p>There were probably other, more minor differences between
implementations, but the above list gives a flavour of the things that
needed doing in order to get to this point, where we have <em>some</em>
assurance that our code is behaving as intended. And all of this is a
month ahead of my self-imposed deadline of SBCL’s 15th birthday: SBCL
was <a href="http://sbcl10.sbcl.org/sbcl-0.0">announced to the world</a> on
December 14th, 1999. (I’m hoping to be able to put on an sbcl15
workshop in conjunction with the
<a href="http://www.european-lisp-symposium.org/">European Lisp Symposium</a>
around April 20th/21st/22nd – if that sounds interesting, please
pencil the dates in the diary and let me know...)</p>
still working on reproducible buildshttp://christophe.rhodes.io/notes/blog/posts/2014/still_working_on_reproducible_builds/2014-10-14T06:51:19Z2014-10-14T06:51:19Z
<p>It’s been nearly fifteen years, and <a href="http://www.sbcl.org/">SBCL</a> still
can’t be reliably built by other Lisp compilers.</p>
<p>Of course, other peoples’ definition of “reliably” might differ. We
did achieve successful building under unrelated Lisp compilers
<a href="http://www.advogato.org/person/crhodes/diary.html?start=23">twelve years ago</a>;
there were a couple of nasty bugs along the way, found both before and
after that triumphant announcement, but at least with a set of
compilers whose interpretation of the standard was sufficiently
similar to SBCL’s own, and with certain non-mandated but expected
features (such as the type <code>(array (unsigned-byte 8) (*))</code> being
distinct from <code>simple-vector</code>, and <code>single-float</code> being distinct from
<code>double-float</code>), SBCL achieved its aim of being buildable on a system
without an SBCL binary installed (indeed, using CLISP or XCL as a
build host, SBCL could in theory be bootstrapped starting with only
gcc).</p>
<p>For true “reliability”, though, we should not be depending on any
particular implementation-defined features other than ones we actually
require – or if we are, then the presence or absence of them should
not cause a visible difference in the resulting SBCL. The most common
kind of leak from the host lisp to the SBCL binary was the <em>host</em>’s
value of
<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_most_p.htm"><code>most-positive-fixnum</code></a>
influencing the target, causing problems from documentation errors all
the way up to type errors in the assembler. Those leaks were mostly
plugged a while ago, though they do recur every so often; there are
other problems, and over the last week I spent some time tracking down
three of them.</p>
<p>The first: if you’ve ever done <code>(apropos "PRINT")</code> or something
similar at the SBCL prompt, you might wonder at the existence of
functions named something like
<code>SB-VM::|CACHED-FUN--PINSRB[(EXT-2BYTE-XMM-REG/MEM ((PREFIX (QUOTE (102))) (OP1 (QUOTE (58))) (OP2 (QUOTE (32))) (IMM NIL TYPE (QUOTE IMM-BYTE))) (QUOTE (NAME TAB REG , REG/MEM ...)))]-EXT-2BYTE-XMM-REG/MEM-PRINTER|</code>.</p>
<p>What is going on there? Well, these functions are a part of the
disassembler machinery; they are responsible for taking a certain
amount of the machine code stream and generating a printed
representation of the corresponding assembly: in this case, for the
<a href="http://www.felixcloutier.com/x86/PINSRB:PINSRD:PINSRQ.html"><code>PINSRB</code></a>
instruction. Ah, but (in most instruction sets) related instructions
share a fair amount of structure, and decoding and printing a <code>PINSRD</code>
instruction is basically the same as for <code>PINSRB</code>, with just one
<code>#x20</code> changed to a <code>#x22</code> – in both cases we want the name of the
instruction, then a tab, then the destination register, a comma, the
source, another comma, and the offset in the destination register. So
SBCL arranges to reuse the <code>PINSRB</code> instruction printer for <code>PINSRD</code>;
it maintains a cache of printer functions, looked up by printer
specification, and reuses them when appropriate. So far, so normal;
the ugly name above is the generated name for such a function,
constructed by interning a printed, string representation of some
useful information.</p>
<p>Hm, but wait. See those <code>(QUOTE (58))</code> fragments inside the name?
They result from printing the list <code>(quote (58))</code>. Is there a
consensus on how to print that list? Note that
<a href="http://www.lispworks.com/reference/HyperSpec/Body/v_pr_pre.htm"><code>*print-pretty*</code></a>
is bound to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/a_nil.htm"><code>nil</code></a>
for this printing; prior experience has shown that there are strong
divergences between implementations, as well as long-standing
individual bugs, in pretty-printer support. So, what happens if I do
<code>(write-to-string '(quote foo) :pretty nil)</code>?</p>
<ul>
<li>SBCL: <code>"(QUOTE FOO)"</code>, unconditionally</li>
<li><a href="http://ccl.clozure.com/">CCL</a>: <code>"'FOO"</code> by default; <code>"(QUOTE FOO)"</code> if
<code>ccl:*print-abbreviate-quote*</code> is set to <code>nil</code></li>
<li><a href="http://www.clisp.org/">CLISP</a>: <code>"'FOO"</code>, unconditionally (I read
the <code>.d</code> code with comments in half-German to establish this)</li>
</ul>
<p>So, if SBCL was compiled using CLISP, the name of the same function in
the final image would be
<code>SB-VM::|CACHED-FUN--PINSRB[(EXT-2BYTE-XMM-REG/MEM ((PREFIX '(102)) (OP1 '(58)) (OP2 '(32)) (IMM NIL TYPE 'IMM-BYTE)) '(NAME TAB REG , REG/MEM ...))]-EXT-2BYTE-XMM-REG/MEM-PRINTER|</code>.
Which is shorter, and maybe marginally easier to read, but importantly
for my purposes is not bitwise-identical.</p>
<p>Thus, here we have a difference between host Common Lisp compilers
which leaks over into the final image, and it must be eliminated.
Fortunately, this was fairly straightforward to eliminate; those names
are never in fact used to find the function object, so generating a
unique name for functions based on a counter makes the generated
object file bitwise identical, no matter how the implementation prints
two-element lists beginning with <code>quote</code>.</p>
<p>The second host leak is also related to <code>quote</code>, and to our old friend
<code>backquote</code> – though not related in any way to the
<a href="http://christophe.rhodes.io/notes/blog/posts/2014/backquote_and_pretty_printing/">new implementation</a>. Consider this
apparently innocuous fragment, which is a simplified version of some
code to implement the <code>:type</code> option to
<a href="http://www.lispworks.com/reference/HyperSpec/Body/m_defstr.htm"><code>defstruct</code></a>:</p>
<pre><code>(macrolet ((def (name type n)
`(progn
(declaim (inline ,name (setf ,name)))
(defun ,name (thing)
(declare (type simple-vector thing))
(the ,type (elt thing ,n)))
(defun (setf ,name) (value thing)
(declare (type simple-vector thing))
(declare (type ,type value))
(setf (elt thing ,n) value)))))
(def foo fixnum 0)
(def bar string 1))
</code></pre>
<p>What’s the problem here? Well, the functions are declaimed to be
<a href="http://www.lispworks.com/reference/HyperSpec/Body/d_inline.htm"><code>inline</code></a>,
so SBCL records their source code. Their source code is generated by
a macroexpander, and so is made up of conses that are generated
programmatically (as opposed to freshly consed by the reader). That
source code is then stored as a literal object in an object file,
which means in practice that instructions for reconstructing a similar
object are dumped, to be executed when the object file is processed by
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_load.htm"><code>load</code></a>.</p>
<p><a href="http://www.lispworks.com/documentation/HyperSpec/Body/02_df.htm">Backquote</a>
is a reader macro that expands into code that, when evaluated,
generates list structure with appropriate evaluation and splicing of
unquoted fragments. What does this mean in practice? Well, one
reasonable implementation of reading <code>`(type ,type value)</code> might
be:</p>
<pre><code>(cons 'type (cons type '(value)))
</code></pre>
<p>and indeed you <em>might</em> (no guarantees) see something like that if you
do</p>
<pre><code>(macroexpand '`(type ,type value))
</code></pre>
<p>in the implementation of your choice. Similarly, reading <code>`(setf
(elt thing ,n) value)</code> will eventually generate code like</p>
<pre><code>(cons 'setf (cons (cons 'elt (list 'thing n)) '(value)))
</code></pre>
<p>Now, what is “similar”? In this context, it has a technical
definition: it relates two objects in possibly-unrelated Lisp images,
such that they can be considered to be equivalent despite the fact
that they can’t be compared:</p>
<blockquote><p>similar <em>adj</em>. (of two objects) defined to be equivalent under the
similarity relationship.</p>
<p>similarity <em>n</em>. a two-place conceptual equivalence predicate, which
is independent of the Lisp image so that two objects in different
Lisp images can be understood to be equivalent under this
predicate. See
<a href="http://www.lispworks.com/documentation/HyperSpec/Body/03_bd.htm">Section 3.2.4</a>
(Literal Objects in Compiled Files).</p></blockquote>
<p>Following that link, we discover that similarity for
<a href="http://www.lispworks.com/reference/HyperSpec/Body/a_cons.htm"><code>cons</code></a>es
is defined in the obvious way:</p>
<blockquote><p>Two conses, <em>S</em> and <em>C</em>, are similar if the car of <em>S</em> is similar to
the car of <em>C</em>, and the cdr of <em>S</em> is similar to the cdr of <em>C</em>.</p></blockquote>
<p>and also that implementations have some obligations:</p>
<blockquote><p>Objects containing circular references can be externalizable
objects. The file compiler is required to preserve eqlness of
substructures within a file.</p></blockquote>
<p>and some freedom:</p>
<blockquote><p>With the exception of symbols and packages, any two literal objects
in code being processed by the file compiler may be coalesced if and
only if they are similar [...]</p></blockquote>
<p>Put this all together, and what do we have? That <code>def</code> macro above
generates code with similar literal objects: there are two instances
of <code>'(value)</code> in it. A host compiler may, or may not, choose to
coalesce those two literal <code>'(value)</code>s into a single literal object;
if it does, the inline expansion of <code>foo</code> (and <code>bar</code>) will have a
circular reference, which must be preserved, showing up as a
difference in the object files produced during the SBCL build. The
fix? It’s ugly, but portable: since we can’t stop an aggressive
compiler from coalescing constants which are similar but not
identical, we must make sure that any similar substructure is in fact
identical:</p>
<pre><code>(macrolet ((def (name type n)
(let ((value '(value)))
`(progn
(declaim (inline ,name (setf ,name)))
(defun ,name (thing)
(declare (type simple-vector thing))
(the ,type (elt thing ,n)))
(defun (setf ,name) (value thing)
(declare (type simple-vector thing))
(declare (type ,type . ,value))
(setf (elt thing ,n) . ,value)))))
(def foo fixnum 0)
(def bar string 1))
</code></pre>
<p>Having dealt with a problem with
<a href="http://www.lispworks.com/reference/HyperSpec/Body/s_quote.htm"><code>quote</code></a>,
and a problem with
<a href="http://www.lispworks.com/documentation/HyperSpec/Body/02_df.htm"><code>backquote</code></a>,
what might the Universe serve up for my third problem? Naturally, it
would be a problem with a code walker. This code walker is
<a href="http://christophe.rhodes.io/notes/blog/posts/2014/naive_vs_proper_code-walking/">somewhat naïve</a>, assuming as it does
that its body is made up of forms or tags; it is the <code>assemble</code> macro,
which is used implicitly in the definition of VOPs (reusable assembly
units); for example, like</p>
<pre><code>(assemble ()
(move ptr object)
(zeroize count)
(inst cmp ptr nil-value)
(inst jmp :e DONE)
LOOP
(loadw ptr ptr cons-cdr-slot list-pointer-lowtag)
(inst add count (fixnumize 1))
(inst cmp ptr nil-value)
(inst jmp :e DONE)
(%test-lowtag ptr LOOP nil list-pointer-lowtag)
(error-call vop 'object-not-list-error ptr)
DONE))
</code></pre>
<p>which generates code to compute the length of a list. The expander
for <code>assemble</code> scans its body for any atoms, and generates binding
forms for those atoms to labels:</p>
<pre><code>(let ((new-labels (append labels
(set-difference visible-labels inherited-labels))))
...
`(let (,@(mapcar (lambda (name) `(,name (gen-label))) new-labels))
...))
</code></pre>
<p>The problem with this, from a reproducibility point of view, is that
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_set_di.htm"><code>set-difference</code></a>
(and the other set-related functions:
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_unionc.htm"><code>union</code></a>,
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_isec_.htm"><code>intersection</code></a>,
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_set_ex.htm"><code>set-exclusive-or</code></a>
and their n-destructive variants) do not return the sets with a
specified order – which is fine when the objects are truly treated as
sets, but in this case the <code>LOOP</code> and <code>DONE</code> label objects ended up in
different stack locations depending on the order of their binding.
Consequently the machine code for the function emitting code for
computing a list’s length – though not the machine code emitted by
that function – would vary depending on the host’s implementation of
<a href="http://www.lispworks.com/reference/HyperSpec/Body/f_set_di.htm"><code>set-difference</code></a>.
The fix here was to sort the result of the set operations, knowing
that all the labels would be symbols and that they could be treated as
string designators.</p>
<p>And after all this is? We’re <em>still</em> not quite there: there are three
to four files (out of 330 or so) which are not bitwise-identical for
differing host compilers. I hope to be able to rectify this situation
in time for SBCL’s 15th birthday...</p>