# -*- html -*-
---
timestamp: Wed 25 Apr 2012 03:36:45 AM PDT
title: in which we plot an escape from the quagmire of equality
tags: emacs, clojure, immutability
id: 159
content: |-
<p>If you follow happenings in the Clojure world, you may have
noticed that the announcement
of <a href="https://github.com/halgari/clojure-py">clojure-py</a>
brings the number of runtimes targeted by Clojure up to four.
While it's great to see the language expand beyond the JVM, it's
not too exciting to me personally since the runtime I spend the
most time in by far is that of Emacs. Of course, Emacs can already
be programmed with lisp, but the dialect it uses leaves much to be
desired. I miss first-class functions[<a href="#fn1">1</a>],
destructuring, literals for associative data, and immutability
whenever I find myself writing nontrivial Emacs Lisp code, and the
lack of these features makes me reluctant to write in it even
though it offers an environment with live feedback unmatched by anything
but
the <a href="http://en.wikipedia.org/wiki/Smalltalk#Image-based_persistence">Smalltalk
images</a>
and <a href="http://en.wikipedia.org/wiki/Genera_(operating_system)">Lisp
Machines</a> of yore.</p>
<img src="http://p.hagelb.org/duck-hand.png" align="right"
alt="why? why do you need a reason?"
title="why? why do you need a reason?" />
<p>Part of what makes ClojureScript interesting is that it has
distilled the number of primitives needed to port Clojure to a new
runtime down to a small number due to its push towards
self-hosting. One of the Summer of Code projects for this year is
to allow for pluggable backends in the ClojureScript compiler,
with Lua as a proof of concept. I started to think through what
would be necessary for this to happen on the Emacs runtime, but I
ran into an interesting quandary
regarding <a href="http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)">referential
transparency</a>.</p>
<p>A function is referentially transparent when it is guaranteed to
return the same value every time it is called with a given set of
arguments. This is a great guarantee to be able to make about your
functions as it simplifies the number of things you need to keep
in your head. Referentially transparent functions really can be
thought of as black boxes: always deterministic and predictable.
But a function that operates on mutable objects cannot be
referentially transparent—it cannot make any guarantees that
future calls involving that same object will result in the same
value since that object could have a different value at any time.</p>
<p>Since Emacs Lisp does not provide any immutable data types other
than numbers, only functions that operate on numbers alone can be
referentially transparent. This is a shame, since referential
transparency allows you to have much greater confidence that your
code is correct. Without it, the best you can say is "as long as
the rest of this program behaves itself, this function should
work". This works a lot like older OSes with cooperative
multitasking and no process memory isolation, which is to say not
very well.</p>
<p>But arguably the worst thing about lacking referential
transparency is that you can't check for equality in a
meaningful way. Henry Baker's
paper <a href="http://home.pipeline.com/~hbaker1/ObjectIdentity.html">"Equal
Rights for Functional Objects"</a> addresses the problem of
equality in Common Lisp[<a href="#fn2">2</a>], which is notable for
having a plethora of equality predicates depending on what level
of coarseness you want:</p>
<ul>
<li><code>EQ</code>: are both arguments the same object in memory?</li>
<li><code>EQL</code>: like <code>EQ</code>, but compares value for
non-immediate numbers like tagged fixnums and bignums.</li>
<li><code>EQUAL</code>: do both arguments have the same structure
and contents?</li>
<li><code>EQUALP</code>: like <code>EQUAL</code>, but allows
integers to equal floats and ignores string case.</li>
<li><code>=</code>: are both numbers of equal value?</li>
<li><code>CHAR=</code>, <code>STRING=</code>, <code>STRING-EQUAL</code>,
ad nauseum.</li>
</ul>
<p>Baker argues that this confusion is due to a muddled notion of
object identity. You want to be able to think in terms of values,
but the fact that some values can change forces you to take into
account the fact that two lists that currently have the same value
may not always be the same in the future. Everything would be so
much simpler if we could think in terms of operational
equivalence:</p>
<blockquote>Two objects are "operationally equivalent" if and only
if there is no way that they can be distinguished, using ...
primitives other than [equality primitives].[RNRS]</blockquote>
<p>Asking "Are these two objects stored in the same memory
location?" lets implementation details leak into your code.
Equality should really be about "Can these two objects behave
differently in any observable way?", which is what the
<code>egal</code> function attempts to answer. <code>egal</code>
is an equality predicate that respects the notion of object
identity as a transitive closure of immutable attributes of an
object. But without immutability, <code>egal</code> always
returns false.</p>
<p>Of course, with a compiler that targets Emacs Lisp, you can work
around this by implementing your own immutable types. But this
makes any form of interop much more cumbersome; close integration
with its host platform is one of the core design tenets of
Clojure, and having to perform conversions on basic types like
strings just to call native elisp functions would be too
cumbersome to be practical. So with the Emacs runtime as it is,
you have to choose between getting equality right and seamless
interop. Damned if you do; damned if you don't.</p>
<p>There are two possible solutions to this. There has been an
ongoing effort to
get <a href="http://www.emacswiki.org/emacs/GuileEmacs">Emacs Lisp
running on the Guile VM</a>.
<hr />
<p>[<a name="fn1">1</a>] Common Lisp fans claim that lisp-2s have
first-class functions, but the way they are kept separate from
other first-class values in their own namespace ghetto brings to
mind claims of "separate but equal"—at best it is Jim Crow
functional programming.</p>
<p>[<a name="fn2">2</a>] Emacs Lisp is not Common Lisp, but the two
dialects are very closely related, and for the purposes of this
post share the same problems.</p>