tag:blogger.com,1999:blog-320495492024-03-08T15:37:39.514-08:00A Nickel's WorthJacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-32049549.post-83054847934250724152019-12-19T19:34:00.004-08:002019-12-19T19:34:43.807-08:00Avoiding fallback in distributed systems<div dir="ltr" style="text-align: left;" trbidi="on">
As <a href="https://a-nickels-worth.blogspot.com/2019/12/challenges-with-distributed-systems.html" target="_blank">previously mentioned</a>, I was recently able to contribute to the <a href="https://aws.amazon.com/builders-library/?cards-body.sort-by=item.additionalFields.customSort&cards-body.sort-order=asc" target="_blank">Amazon Builders' Library</a>. I'd also like to share another post that I wrote for the series, entitled <a href="https://aws.amazon.com/builders-library/avoiding-fallback-in-distributed-systems/?did=ba_card&trk=ba_card" target="_blank">Avoiding fallback in distributed systems</a>. I'm especially excited to be able to publish it, as it's based on an internal Amazon document I wrote in 2006 entitled <i>Modes Considered Harmful</i>. It provoked a lot of interesting discussions over the years, so I'm happy to be able to share a (hopefully slightly better written) version of it publicly. Here's a quick abstract of the <a href="https://aws.amazon.com/builders-library/avoiding-fallback-in-distributed-systems/?did=ba_card&trk=ba_card" target="_blank">article</a>:<br />
<br />
<blockquote class="tr_bq">
<i>This article covers fallback strategies and why we almost never use them at Amazon. In the world of distributed systems, fallback strategies are among the most difficult challenges to handle, especially for time-sensitive services. Compounding this difficulty is that bad fallback strategies can take a long time (even years) to leave repercussions, and the difference between a good strategy and a bad strategy is subtle. In this article, the focus will be on how fallback strategies can cause more problems than they fix. We’ll include examples of where fallback strategies have caused problems at Amazon. Finally, we’ll discuss alternatives to fallback that we use at Amazon.</i></blockquote>
</div>
Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com3tag:blogger.com,1999:blog-32049549.post-49267704349866279502019-12-19T19:24:00.000-08:002020-01-06T13:47:20.056-08:00Challenges with distributed systems<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: left;">
<span style="font-family: , , "blinkmacsystemfont" , "segoe ui" , "roboto" , "helvetica neue" , "fira sans" , "ubuntu" , "oxygen" , "oxygen sans" , "cantarell" , "droid sans" , "apple color emoji" , "segoe ui emoji" , "segoe ui symbol" , "lucida grande" , "helvetica" , "arial" , sans-serif;"><span style="background-color: white;"><span style="font-size: 14px;">I was recently invited to contribute to the </span><a href="https://aws.amazon.com/builders-library/?cards-body.sort-by=item.additionalFields.customSort&cards-body.sort-order=asc" style="font-size: 14px;" target="_blank"><span style="color: blue;">Amazon Builders' Library</span></a><span style="font-size: 14px;">. One article I'd been wanting to publish publicly is about how bizarre distributed systems are, and what's been the biggest challenge building them, in my experience.</span></span></span></div>
<div style="text-align: left;">
<span style="background-color: white;"><span style="font-family: , , "blinkmacsystemfont" , "segoe ui" , "roboto" , "helvetica neue" , "fira sans" , "ubuntu" , "oxygen" , "oxygen sans" , "cantarell" , "droid sans" , "apple color emoji" , "segoe ui emoji" , "segoe ui symbol" , "lucida grande" , "helvetica" , "arial" , sans-serif;"><span style="font-size: 14px;"><br /></span></span>
</span></div>
<span style="font-family: , , "blinkmacsystemfont" , "segoe ui" , "roboto" , "helvetica neue" , "fira sans" , "ubuntu" , "oxygen" , "oxygen sans" , "cantarell" , "droid sans" , "apple color emoji" , "segoe ui emoji" , "segoe ui symbol" , "lucida grande" , "helvetica" , "arial" , sans-serif;"><span style="background-color: white; font-size: 14px;">Please check out the <a href="https://aws.amazon.com/builders-library/challenges-with-distributed-systems/?did=ba_card&trk=ba_card" target="_blank"><span style="color: blue;">article</span></a> and here's a quick abstract:</span></span><br />
<span style="background-color: white;"><br /></span>
<br />
<div style="text-align: left;">
</div>
<blockquote class="tr_bq" style="text-align: left;">
<span style="font-family: , , "blinkmacsystemfont" , "segoe ui" , "roboto" , "helvetica neue" , "fira sans" , "ubuntu" , "oxygen" , "oxygen sans" , "cantarell" , "droid sans" , "apple color emoji" , "segoe ui emoji" , "segoe ui symbol" , "lucida grande" , "helvetica" , "arial" , sans-serif; font-size: 14px;"><i style="background-color: white;">Developing distributed utility computing services, such as reliable long-distance telephone networks, or Amazon Web Services (AWS) services, is hard. Distributed computing is also weirder and less intuitive than other forms of computing because of two interrelated problems. Independent failures and nondeterminism cause the most impactful issues in distributed systems. In addition to the typical computing failures most engineers are used to, failures in distributed systems can occur in many other ways. What’s worse, it’s impossible always to know whether something failed. This article reviews the concepts that contribute to why distributed computing is so, well, weird.</i></span></blockquote>
</div>
Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.comtag:blogger.com,1999:blog-32049549.post-49809067562020754852016-05-26T18:50:00.000-07:002016-05-27T09:06:33.556-07:00Please Don't Write Bruby<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<meta name="generator" content="Org-mode" />
<style type="text/css">
<!--/*--><![CDATA[/*><!--*/
.title { text-align: center;
margin-bottom: .2em; }
.subtitle { text-align: center;
font-size: medium;
font-weight: bold;
margin-top:0; }
.todo { font-family: monospace; color: red; }
.done { font-family: monospace; color: green; }
.priority { font-family: monospace; color: orange; }
.tag { background-color: #eee; font-family: monospace;
padding: 2px; font-size: 80%; font-weight: normal; }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
.org-right { margin-left: auto; margin-right: 0px; text-align: right; }
.org-left { margin-left: 0px; margin-right: auto; text-align: left; }
.org-center { margin-left: auto; margin-right: auto; text-align: center; }
.underline { text-decoration: underline; }
#postamble p, #preamble p { font-size: 90%; margin: .2em; }
p.verse { margin-left: 3%; }
pre {
border: 1px solid #ccc;
box-shadow: 3px 3px 3px #eee;
padding: 8pt;
font-family: monospace;
overflow: auto;
margin: 1.2em;
}
pre.src {
position: relative;
overflow: visible;
padding-top: 1.2em;
}
pre.src:before {
display: none;
position: absolute;
background-color: white;
top: -10px;
right: 10px;
padding: 3px;
border: 1px solid black;
}
pre.src:hover:before { display: inline;}
pre.src-sh:before { content: 'sh'; }
pre.src-bash:before { content: 'sh'; }
pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
pre.src-R:before { content: 'R'; }
pre.src-perl:before { content: 'Perl'; }
pre.src-java:before { content: 'Java'; }
pre.src-sql:before { content: 'SQL'; }
table { border-collapse:collapse; }
caption.t-above { caption-side: top; }
caption.t-bottom { caption-side: bottom; }
td, th { vertical-align:top; }
th.org-right { text-align: center; }
th.org-left { text-align: center; }
th.org-center { text-align: center; }
td.org-right { text-align: right; }
td.org-left { text-align: left; }
td.org-center { text-align: center; }
dt { font-weight: bold; }
.footpara { display: inline; }
.footdef { margin-bottom: 1em; }
.figure { padding: 1em; }
.figure p { text-align: center; }
.inlinetask {
padding: 10px;
border: 2px solid gray;
margin: 10px;
background: #ffffcc;
}
#org-div-home-and-up
{ text-align: right; font-size: 70%; white-space: nowrap; }
textarea { overflow-x: auto; }
.linenr { font-size: smaller }
.code-highlighted { background-color: #ffff00; }
.org-info-js_info-navigation { border-style: none; }
#org-info-js_console-label
{ font-size: 10px; font-weight: bold; white-space: nowrap; }
.org-info-js_search-highlight
{ background-color: #ffff00; color: #000000; font-weight: bold; }
/*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart The following is the entire license notice for the
JavaScript code in this tag.
Copyright (C) 2012-2013 Free Software Foundation, Inc.
The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version. The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU GPL for more details.
As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.
@licend The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
function CodeHighlightOn(elem, id)
{
var target = document.getElementById(id);
if(null != target) {
elem.cacheClassElem = elem.className;
elem.cacheClassTarget = target.className;
target.className = "code-highlighted";
elem.className = "code-highlighted";
}
}
function CodeHighlightOff(elem, id)
{
var target = document.getElementById(id);
if(elem.cacheClassElem)
elem.className = elem.cacheClassElem;
if(elem.cacheClassTarget)
target.className = elem.cacheClassTarget;
}
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<div id="outline-container-orgheadline1" class="outline-2">
<div class="outline-text-2" id="text-orgheadline1">
<p>
This doc is about how to write <i>Ruby</i> code instead of writing hybrid
yuck <i>Bruby</i> code. Ruby code, is, well, Ruby code; i.e., code written
in Ruby and not some other language. I strongly believe that once you
have chosen to write code in Ruby, you should try to <span class="underline">keep</span> writing
code in Ruby. Specifically, please don't write <span class="underline">Bruby</span>, which is an
unholy mishmash of Bash and Ruby. Bruby is hard to read, flaky, slower
(usually), and always harder to reason about. It's even harder to
write. There is almost no reason to shell out to Bash from Ruby.
</p>
<p>
Here's a canonical example of Bruby code:
</p>
<div class="org-src-container">
<pre class="src src-ruby">output = <span style="color: #008000;">`somecommand | egrep -v '^snord[123]' | sort | uniq`</span>
<span style="color: #0000FF;">if</span> <span style="color: #006FE0;">$?</span> == 0
<span style="color: #8D8D84;"># </span><span style="color: #8D8D84; font-style: italic;">...do stuff with 'output' such as:</span>
foo output
<span style="color: #0000FF;">end</span>
</pre>
</div>
<p>
There are a number of problems with this code. For one thing, it's
unnecessary to use Bash in the first place. Ruby is just as good at
grepping, regular expressions, sorting and uniqifying. The more you
mix different programming languages, the more the reader of the code
has to switch gears mentally. As a frequent code-reviewer, I implore
you: please don't make your readers switch gears mentally (unless
there's a really good reason), it causes brain damage after a while.
Also, Bash pipelines easily hide bugs and mask failures. By default,
Bash ignores errors from an "interior" command in a pipeline, as the
following code illustrates:
</p>
<div class="org-src-container">
<pre class="src src-ruby"><span style="color: #0000FF;">def</span> <span style="color: #006699;">lower_nuclear_plant_control_rods</span>
<span style="color: #8D8D84;"># </span><span style="color: #8D8D84; font-style: italic;">The following line will *not* raise an exception, even though it</span>
<span style="color: #8D8D84;"># </span><span style="color: #8D8D84; font-style: italic;">will barf.</span>
rods = <span style="color: #008000;">`cat /etc/plants/springfield/control_rods | sort --revesre | uniq`</span>
<span style="color: #8D8D84;"># </span><span style="color: #8D8D84; font-style: italic;">'rods' is now an empty string and $? will be 0, indicating that </span>
<span style="color: #8D8D84;"># </span><span style="color: #8D8D84; font-style: italic;">everything is ok, when it isn't.</span>
<span style="color: #0000FF;">if</span> <span style="color: #006FE0;">$?</span> != 0
<span style="color: #8D8D84;"># </span><span style="color: #8D8D84; font-style: italic;">This will never happen. Millions of lives will be lost in the</span>
<span style="color: #8D8D84;"># </span><span style="color: #8D8D84; font-style: italic;">ensuing calamity.</span>
page_operator <span style="color: #008000;">"Springfield Ops Center"</span>, <span style="color: #D0372D;">:sev_1</span>, <span style="color: #008000;">"Meltdown Imminent"</span>
<span style="color: #0000FF;">else</span>
rods.split.each <span style="color: #0000FF;">do</span> |rod|
lower rod
<span style="color: #0000FF;">end</span>
<span style="color: #0000FF;">end</span>
<span style="color: #0000FF;">end</span>
</pre>
</div>
<p>
Despite the subtly bad arguments to <code>sort</code>, the above code won't raise
an exception, and will fail to lower the control rods <i>and</i> also fail
to notify the operators (because <code>$?</code> will be <code>0</code>). Thus the town of
Springfield will be wiped off the map. Do you want the same type of
errors to accidentally blow away all of your production databases from
an errant invocation of some admin script?
</p>
<p>
One way to fix the above would be to add the <code>pipefail</code> option into
the string of Bash code:
</p>
<div class="org-src-container">
<pre class="src src-ruby">rods = <span style="color: #008000;">`set -o pipefail; cat /etc/plants/springfield/control_rods | sort --revesre | uniq`</span>
</pre>
</div>
<p>
But that's easy to forget, difficult to mechanistically catch, and
ugly to read. The better solution is to remember that you can write
Ruby in Ruby:
</p>
<div class="org-src-container">
<pre class="src src-ruby"><span style="color: #0000FF;">def</span> <span style="color: #006699;">lower_nuclear_plant_control_rods</span>
<span style="color: #6434A3;">File</span>.readlines<span style="color: #707183;">(</span><span style="color: #008000;">'/etc/plants/springfield/control_rods'</span><span style="color: #707183;">)</span>.sort.reverse.uniq <span style="color: #0000FF;">do</span> |rod|
lower rod
<span style="color: #0000FF;">end</span>
<span style="color: #0000FF;">rescue</span>
page_operator <span style="color: #008000;">"Springfield Ops Center"</span>, <span style="color: #D0372D;">:sev_1</span>, <span style="color: #008000;">"Meltdown Imminent"</span>
<span style="color: #006FE0;">raise</span>
<span style="color: #0000FF;">end</span>
</pre>
</div>
<p>
The above code is shorter, easier to read (no switching mental gears)
and is guaranteed to raise exceptions if something is wrong. The
specific changes are:
</p>
<dl class="org-dl">
<dt><code>cat</code></dt><dd>Ruby's good at opening files, just use <code>File.readlines</code> if
you want to read a file line-by-line.</dd>
<dt><code>sort</code></dt><dd>Ruby Enumerables have <code>sort</code> built in.</dd>
<dt><code>--reverse</code></dt><dd>Use Enumerable's built-in <code>reverse</code> method.</dd>
<dt><code>uniq</code></dt><dd>Use Enumerable's <code>uniq</code> method.</dd>
<dt>Error-handling</dt><dd>Any errors in the invocation (for example
misspelling <code>reverse</code> as <code>revesre</code>) will result in an exception
being raised).</dd>
</dl>
</div>
</div>
<div id="outline-container-orgheadline2" class="outline-2">
<h2 id="orgheadline2">Tips</h2>
<div class="outline-text-2" id="text-orgheadline2">
<p>
The rest of this document contains a series of tips to help you write
Ruby instead of Bruby.
</p>
</div>
<div id="outline-container-orgheadline3" class="outline-3">
<h3 id="orgheadline3">Tip 1: Google for Pure Ruby Bash Equivalents</h3>
<div class="outline-text-3" id="text-orgheadline3">
<p>
Whenever you're tempted to shell out in a Ruby script, stop,
flagellate yourself 23 times with a birch branch, and then Google for
an alternative in Pure Ruby. For example, imagine your script must
create a directory, and not fail if the directory already exists, and
also create any intermediary directories. But you don't want to write
that code yourself because it's yucky and complicated and you know
you'll fail to handle some edge condition properly. If you're familiar
with Unix, your first inclination might be to write Bruby:
</p>
<div class="org-src-container">
<pre class="src src-ruby"><span style="color: #006FE0;">system</span> <span style="color: #008000;">"mkdir -p '</span><span style="color: #BA36A5;">#{ROOT_DIR}</span><span style="color: #008000;">'"</span>
<span style="color: #0000FF;">if</span> <span style="color: #006FE0;">$?</span> != 0
<span style="color: #006FE0;">raise</span> <span style="color: #008000;">"Unable to create directory </span><span style="color: #BA36A5;">#{ROOT_DIR}</span><span style="color: #008000;">"</span>
<span style="color: #0000FF;">end</span>
</pre>
</div>
<p>
The above is clunky. It's also easy to forget to check the value of
<code>$?</code>, in which case your code will silently continue even though the
directory was not created. Fortunately, this is easy to fix. Just
<a href="http://bfy.tw/44X5">Google for it</a> (after flagellating yourself).
You will see that Ruby has a built-in version of <code>mkdir -p</code>.
</p>
<div class="org-src-container">
<pre class="src src-ruby"><span style="color: #006FE0;">require</span> <span style="color: #008000;">'fileutils'</span>
<span style="color: #6434A3;">FileUtils</span>.mkdir_p <span style="color: #6434A3;">ROOT_DIR</span>
</pre>
</div>
<p>
This version is shorter and easier to read, and, most importantly,
raises an exception if anything went wrong:
</p>
<pre class="example">
irb(main):666:0> FileUtils.mkdir_p "/bogon/adfadf"
Errno::EACCES: Permission denied @ dir_s_mkdir - /bogon
from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:253:in `mkdir'
from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:253:in `fu_mkdir'
from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:227:in `block (2 levels) in mkdir_p'
from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:225:in `reverse_each'
from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:225:in `block in mkdir_p'
from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:211:in `each'
from /usr/local/Cellar/ruby/2.3.0/lib/ruby/2.3.0/fileutils.rb:211:in `mkdir_p'
from (irb):666
from /usr/local/bin/irb:11:in `<main>'
</pre>
<p>
This obnoxious error might be obnoxious, but it also might <i>save your life</i>.
</p>
</div>
</div>
<div id="outline-container-orgheadline4" class="outline-3">
<h3 id="orgheadline4">Tip 2: Keep unavoidable Bash usage to a minimum</h3>
<div class="outline-text-3" id="text-orgheadline4">
<p>
Sometimes it does make sense to shell out. For example, it is hard to
find a Ruby equivalent of the command-line <code>dig</code> DNS utility. In these
situations, don't throw out the baby with the bathwater; keep the Bash
to a minimum. For example, in Bruby, you would write:
</p>
<div class="org-src-container">
<pre class="src src-ruby">dig_command = <span style="color: #008000;">"dig +qr www.springfield.us any -x 127.0.0.1 isc.org ns +noqr"</span>
mail_server = <span style="color: #008000;">`</span><span style="color: #BA36A5;">#{dig_command}</span><span style="color: #008000;"> | egrep -w MX | awk '{print $6}'`</span>.chomp
</pre>
</div>
<p>
Whereas in Ruby, by contrast, you should use Bash only to run <code>dig</code>,
everything else (such as processing the standard output of <code>dig</code>)
should be done in Ruby. The built-in <code>Open3</code> module makes this
straightforward in many cases:
</p>
<div class="org-src-container">
<pre class="src src-ruby"><span style="color: #006FE0;">require</span> <span style="color: #008000;">'open3'</span>
output, error, status = <span style="color: #6434A3;">Open3</span>.capture3 dig_command
</pre>
</div>
<p>
<code>Open3.capture3</code> returns a stream containing the standard output of
running <code>dig_command</code>, as well as the status of running the command.
The next tip covers how to actually replicate the rest of the above
pipeline that populated the <code>mail_server</code> variable.
</p>
</div>
</div>
<div id="outline-container-orgheadline5" class="outline-3">
<h3 id="orgheadline5">Tip 3: Use Enumerable to replace Bash pipelines</h3>
<div class="outline-text-3" id="text-orgheadline5">
<p>
A distinguishing feature of Bash is its ability to chain commands
together using pipes, as illustrated in the previous tip:
</p>
<div class="org-src-container">
<pre class="src src-ruby">mail_server = <span style="color: #008000;">`</span><span style="color: #BA36A5;">#{dig_command}</span><span style="color: #008000;"> | egrep -w MX | awk '{print $6}'`</span>.chomp
</pre>
</div>
<p>
Most of the time you can replicate pipelines using Ruby's built-in
<code>Enumerable</code> module. Almost everything you think <i>might</i> be an
<code>Enumerable</code> actually <i>is</i> an <code>Enumerable</code>: arrays, strings, open
files, etc. In particular, if you're trying to convert Bruby to Ruby,
you can use methods like <code>IO.popen</code>, or better yet the methods in
<code>Open3</code>, to get an <code>Enumerable</code> (or else a string, which can be
converted into one with <code>split</code>) over the standard output of that
process. From there, you can take advantage of methods such as
<code>Enumerable.grep</code> (which, for example, seamlessly handles regular
expressions).
</p>
<p>
In those cases where <code>Enumerable</code> itself doesn't immediately solve the
problem, you have the Ruby programming language itself at your beck
and call. For example, many of the features of Awk can be found
directly in Ruby (if you did enough programming language research
you'd probably dig up some indirect connection between the two
languages, but that shall be left as an exercise for the reader).
</p>
<p>
Here are all the equivalents of each part of the above Bash pipeline.
</p>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<colgroup>
<col class="org-left" />
<col class="org-left" />
</colgroup>
<thead>
<tr>
<th scope="col" class="org-left"><b>Bruby</b></th>
<th scope="col" class="org-left"><b>Ruby</b></th>
</tr>
</thead>
<tbody>
<tr>
<td class="org-left"><code>`#{dig_command}`</code></td>
<td class="org-left"><code>Open3.capture3(dig_command)</code></td>
</tr>
<tr>
<td class="org-left"><code>egrep -w MX</code></td>
<td class="org-left"><code>split("\n").grep(/\WMX\W/)</code></td>
</tr>
<tr>
<td class="org-left"><code>awk '{print $6}'</code></td>
<td class="org-left"><code>split[5]</code></td>
</tr>
</tbody>
</table>
<p>
Putting it all together:
</p>
<div class="org-src-container">
<pre class="src src-ruby"><span style="color: #006FE0;">require</span> <span style="color: #008000;">'open3'</span>
dig_command = <span style="color: #008000;">"dig +qr www.springfield.us any -x 127.0.0.1 isc.org ns +noqr"</span>
o, e, s = <span style="color: #6434A3;">Open3</span>.capture3 dig_command
mail_server = <span style="color: #0000FF;">if</span> s.success?
o.split<span style="color: #707183;">(</span><span style="color: #008000;">"\n"</span><span style="color: #707183;">)</span>.grep<span style="color: #707183;">(</span><span style="color: #008000;">/\WMX\W/</span><span style="color: #707183;">)</span><span style="color: #707183;">[</span>0<span style="color: #707183;">]</span>.split<span style="color: #707183;">[</span>5<span style="color: #707183;">]</span>
<span style="color: #0000FF;">else</span>
<span style="color: #006FE0;">raise</span> <span style="color: #008000;">"Failed: </span><span style="color: #BA36A5;">#{dig_command}</span><span style="color: #008000;">\n</span><span style="color: #BA36A5;">#{e}</span><span style="color: #008000;">"</span>
<span style="color: #0000FF;">end</span>
</pre>
</div>
<p>
Here are some other common mappings from Bash to <code>Enumerable</code> methods:
</p>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<colgroup>
<col class="org-left" />
<col class="org-left" />
</colgroup>
<thead>
<tr>
<th scope="col" class="org-left"><b>Bash</b></th>
<th scope="col" class="org-left"><b>Enumerable</b></th>
</tr>
</thead>
<tbody>
<tr>
<td class="org-left"><code>head -n 2</code></td>
<td class="org-left"><code>take(2)</code></td>
</tr>
<tr>
<td class="org-left"><code>tail -n 2</code></td>
<td class="org-left"><code>reverse_each.take(2)</code></td>
</tr>
<tr>
<td class="org-left"><code>sort</code></td>
<td class="org-left"><code>sort</code></td>
</tr>
<tr>
<td class="org-left"><code>uniq</code></td>
<td class="org-left"><code>to_a.uniq</code></td>
</tr>
<tr>
<td class="org-left"><code>grep</code></td>
<td class="org-left"><code>grep</code></td>
</tr>
<tr>
<td class="org-left"><code>grep -v</code></td>
<td class="org-left"><code>grep_v</code></td>
</tr>
</tbody>
</table>
</div>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com0tag:blogger.com,1999:blog-32049549.post-82933258016414991122016-04-14T19:18:00.000-07:002016-05-27T09:02:46.238-07:00A Guide to Naming Variables<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<meta name="generator" content="Org-mode" />
<style type="text/css">
<!--/*--><![CDATA[/*><!--*/
.title { text-align: center;
margin-bottom: .2em; }
.subtitle { text-align: center;
font-size: medium;
font-weight: bold;
margin-top:0; }
.todo { font-family: monospace; color: red; }
.done { font-family: monospace; color: green; }
.priority { font-family: monospace; color: orange; }
.tag { background-color: #eee; font-family: monospace;
padding: 2px; font-size: 80%; font-weight: normal; }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
.org-right { margin-left: auto; margin-right: 0px; text-align: right; }
.org-left { margin-left: 0px; margin-right: auto; text-align: left; }
.org-center { margin-left: auto; margin-right: auto; text-align: center; }
.underline { text-decoration: underline; }
#postamble p, #preamble p { font-size: 90%; margin: .2em; }
p.verse { margin-left: 3%; }
pre {
border: 1px solid #ccc;
box-shadow: 3px 3px 3px #eee;
padding: 8pt;
font-family: monospace;
overflow: auto;
margin: 1.2em;
}
pre.src {
position: relative;
overflow: visible;
padding-top: 1.2em;
}
pre.src:before {
display: none;
position: absolute;
background-color: white;
top: -10px;
right: 10px;
padding: 3px;
border: 1px solid black;
}
pre.src:hover:before { display: inline;}
pre.src-sh:before { content: 'sh'; }
pre.src-bash:before { content: 'sh'; }
pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
pre.src-R:before { content: 'R'; }
pre.src-perl:before { content: 'Perl'; }
pre.src-java:before { content: 'Java'; }
pre.src-sql:before { content: 'SQL'; }
table { border-collapse:collapse; }
caption.t-above { caption-side: top; }
caption.t-bottom { caption-side: bottom; }
td, th { vertical-align:top; }
th.org-right { text-align: center; }
th.org-left { text-align: center; }
th.org-center { text-align: center; }
td.org-right { text-align: right; }
td.org-left { text-align: left; }
td.org-center { text-align: center; }
dt { font-weight: bold; }
.footpara { display: inline; }
.footdef { margin-bottom: 1em; }
.figure { padding: 1em; }
.figure p { text-align: center; }
.inlinetask {
padding: 10px;
border: 2px solid gray;
margin: 10px;
background: #ffffcc;
}
#org-div-home-and-up
{ text-align: right; font-size: 70%; white-space: nowrap; }
textarea { overflow-x: auto; }
.linenr { font-size: smaller }
.code-highlighted { background-color: #ffff00; }
.org-info-js_info-navigation { border-style: none; }
#org-info-js_console-label
{ font-size: 10px; font-weight: bold; white-space: nowrap; }
.org-info-js_search-highlight
{ background-color: #ffff00; color: #000000; font-weight: bold; }
/*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart The following is the entire license notice for the
JavaScript code in this tag.
Copyright (C) 2012-2013 Free Software Foundation, Inc.
The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version. The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU GPL for more details.
As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.
@licend The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
function CodeHighlightOn(elem, id)
{
var target = document.getElementById(id);
if(null != target) {
elem.cacheClassElem = elem.className;
elem.cacheClassTarget = target.className;
target.className = "code-highlighted";
elem.className = "code-highlighted";
}
}
function CodeHighlightOff(elem, id)
{
var target = document.getElementById(id);
if(elem.cacheClassElem)
elem.className = elem.cacheClassElem;
if(elem.cacheClassTarget)
target.className = elem.cacheClassTarget;
}
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<div id="outline-container-orgheadline1" class="outline-2">
<h2 id="orgheadline1">Names Considered Useful</h2>
<div class="outline-text-2" id="text-orgheadline1">
<p>
Software is written for <i>people</i> to understand; variable names should
be chosen accordingly. People need to comb through your code and
understand its <i>intent</i> in order to extend or fix it. Too often,
variable names waste space and hinder comprehension. Even
well-intentioned engineers often choose names that are, at best, only
superficially useful. This document is meant to help engineers choose
good variable names. It artificially focuses on code reviews because
they expose most of the issues with bad variable names. There are, of
course, other reasons to choose good variable names (such as improving
code maintenance). This document is also a work-in-progress, please
send me any constructive feedback you might have on how to improve it.
</p>
</div>
<div id="outline-container-orgheadline2" class="outline-3">
<h3 id="orgheadline2">Why Name Variables?</h3>
<div class="outline-text-3" id="text-orgheadline2">
<p>
The primary reason to give variables meaningful names is so that a
human can understand them. Code written strictly for a computer could
just as well have meaningless, auto-generated names<sup><a id="fnr.1" class="footref" href="#fn.1">1</a></sup>:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">int</span> <span style="color: #0432fe;">f1</span><span style="color: #707183;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">a1</span>, <span style="color: #228b22;">Collection</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Integer</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">a2</span><span style="color: #707183;">)</span>
<span style="color: #707183;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">a5</span> = 0;
<span style="color: #932092;">for</span> <span style="color: #7388d6;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">a3</span> = 0; a3 < a2.<span style="color: #228b22;">size</span><span style="color: #909183;">(</span><span style="color: #909183;">)</span> && a3 < <span style="color: #228b22;">a1</span>; a3++<span style="color: #7388d6;">)</span> <span style="color: #7388d6;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">a6</span> = a2.get<span style="color: #909183;">(</span>a3<span style="color: #909183;">)</span>;
<span style="color: #932092;">if</span> <span style="color: #909183;">(</span>a6 >= 0<span style="color: #909183;">)</span> <span style="color: #909183;">{</span>
System.out.println<span style="color: #709870;">(</span>a6 + <span style="color: #8b2252;">" "</span><span style="color: #709870;">)</span>;
<span style="color: #909183;">}</span> <span style="color: #932092;">else</span> <span style="color: #909183;">{</span>
a5++;
<span style="color: #909183;">}</span>
<span style="color: #7388d6;">}</span>
System.out.println<span style="color: #7388d6;">(</span><span style="color: #8b2252;">"\n"</span><span style="color: #7388d6;">)</span>;
<span style="color: #932092;">return</span> a5;
<span style="color: #707183;">}</span>
</pre>
</div>
<p>
All engineers would recognize the above code is needlessly difficult
to understand, as it violates two common guidelines: 1) don't
abbreviate, and 2) give meaningful names. Perhaps surprisingly, these
guidelines can be counter-productive. Abbreviation isn't <i>always</i> bad,
as will be discussed later. And <i>meaningful</i> is vague and subject to
interpretation. Some engineers think it means that names should always
be verbose (such as <code>MultiDictionaryLanguageProcessorOutput</code>). Others
find the prospect of coming up with <i>truly</i> meaningful names daunting,
and give up before putting in much effort. Thus, even when trying to
follow the above two rules, a coder might write:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">int</span> <span style="color: #0432fe;">processElements</span><span style="color: #707183;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">numResults</span>, <span style="color: #228b22;">Collection</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Integer</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">collection</span><span style="color: #707183;">)</span>
<span style="color: #707183;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">result</span> = 0;
<span style="color: #932092;">for</span> <span style="color: #7388d6;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">count</span> = 0; count < collection.<span style="color: #228b22;">size</span><span style="color: #909183;">(</span><span style="color: #909183;">)</span> && count < <span style="color: #228b22;">numResults</span>; count++<span style="color: #7388d6;">)</span> <span style="color: #7388d6;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">num</span> = collection.get<span style="color: #909183;">(</span>count<span style="color: #909183;">)</span>;
<span style="color: #932092;">if</span> <span style="color: #909183;">(</span>num >= 0<span style="color: #909183;">)</span> <span style="color: #909183;">{</span>
System.out.println<span style="color: #709870;">(</span>num + <span style="color: #8b2252;">" "</span><span style="color: #709870;">)</span>;
<span style="color: #909183;">}</span> <span style="color: #932092;">else</span> <span style="color: #909183;">{</span>
result++;
<span style="color: #909183;">}</span>
<span style="color: #7388d6;">}</span>
System.out.println<span style="color: #7388d6;">(</span><span style="color: #8b2252;">"\n"</span><span style="color: #7388d6;">)</span>;
<span style="color: #932092;">return</span> result;
<span style="color: #707183;">}</span>
</pre>
</div>
<p>
Reviewers could, with effort, understand the above code more easily
than the first example. The variable names are accurate and readable.
But they're unhelpful and waste space, because:
</p>
<dl class="org-dl">
<dt><code>processElements</code></dt><dd>most code "processes" things (after all, code
runs on a "processor"), so <code>process</code> is seven wasted characters
that mean nothing more that "compute". <code>Elements</code> isn't much
better. While suggestive that the function is going to operate on
the collection, that much was <i>already obvious</i>. There's even a
bug in the code that this name doesn't help the reader spot.</dd>
<dt><code>numResults</code></dt><dd>most code produces "results" (eventually); so, as
with <code>process</code>, <code>Results</code> is seven wasted
characters. The full variable name, <code>numResults</code> is
<i>suggestive</i> that it might be intended to limit the
amount of output, but is vague enough to impose a
mental tax on the reader.</dd>
<dt><code>collection</code></dt><dd>wastes space; it's obvious that it's a collection
because the previous tokens were
<code>Collection<Integer></code>.</dd>
<dt><code>num</code></dt><dd>simply recapitulates the type of the object (<code>int</code>)</dd>
<dt><code>result</code>, <code>count</code></dt><dd>are coding cliches; as with <code>numResults</code> they
waste space and are so generic they don't help the reader
understand the code.</dd>
</dl>
<p>
However, keep in mind the true purpose of variable names: the reader
is trying to <i>understand</i> the code, which requires <i>both</i> of the
following:
</p>
<ol class="org-ol">
<li>What was the coder's <i>intent</i>?</li>
<li>What does the code actually do?</li>
</ol>
<p>
To see how the longer variable names that this example used are
actually a mental tax on the reader, here's a re-write of the function
showing what <i>meaning</i> a reader would actually glean from those names:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">int</span> <span style="color: #0432fe;">doSomethingWithCollectionElements</span><span style="color: #707183;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">numberOfResults</span>,
<span style="color: #228b22;">Collection</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Integer</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">integerCollection</span><span style="color: #707183;">)</span>
<span style="color: #707183;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">resultToReturn</span> = 0;
<span style="color: #932092;">for</span> <span style="color: #7388d6;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">variableThatCountsUp</span> = 0;
variableThatCountsUp < integerCollection.<span style="color: #228b22;">size</span><span style="color: #909183;">(</span><span style="color: #909183;">)</span>
&& variableThatCountsUp < <span style="color: #228b22;">numberOfResults</span>;
variableThatCountsUp++<span style="color: #7388d6;">)</span> <span style="color: #7388d6;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">integerFromCollection</span> = integerCollection.get<span style="color: #909183;">(</span>count<span style="color: #909183;">)</span>;
<span style="color: #932092;">if</span> <span style="color: #909183;">(</span>integerFromCollection >= 0<span style="color: #909183;">)</span> <span style="color: #909183;">{</span>
System.out.println<span style="color: #709870;">(</span>integerFromCollection + <span style="color: #8b2252;">" "</span><span style="color: #709870;">)</span>;
<span style="color: #909183;">}</span> <span style="color: #932092;">else</span> <span style="color: #909183;">{</span>
resultToReturn++;
<span style="color: #909183;">}</span>
<span style="color: #7388d6;">}</span>
System.out.println<span style="color: #7388d6;">(</span><span style="color: #8b2252;">"\n"</span><span style="color: #7388d6;">)</span>;
<span style="color: #932092;">return</span> resultToReturn;
<span style="color: #707183;">}</span>
</pre>
</div>
<p>
The naming changes have almost made the code worse than the
auto-generated names, which, at least, were short. This rewrite shows
that coder's intent is still mysterious, and there are now more
characters for the reader to scan. Code reviewers review a lot of
code; poor names make a hard job even harder. How do we make code
reviewing less taxing?
</p>
</div>
</div>
<div id="outline-container-orgheadline3" class="outline-3">
<h3 id="orgheadline3">On Code Reviews</h3>
<div class="outline-text-3" id="text-orgheadline3">
<p>
There are two taxes on code reviewers' mental endurance: <i>distance</i>
and <i>boilerplate</i>. Distance, in the case of variables, refers to how
far away a reviewer has to scan, visually, in order to remind
themselves what a variable does. Reviewers lack the <i>context</i> that
coders had in mind when they wrote the code; reviewers must
reconstruct that context on the fly. Reviewers need to do this
quickly; it isn't worth spending as much time reviewing code as it
took to write it<sup><a id="fnr.2" class="footref" href="#fn.2">2</a></sup>. Good variable names eliminate the problem of distance
because they remind the reviewer of their purpose. That way they don't
have to scan back to an earlier part of the code.
</p>
<p>
The other tax is <i>boilerplate</i>. Code is often doing something
complicated; it was written by someone else; reviewers are often
context-switching from their own code; they review a lot of code,
every day, and may have been reviewing code for many years. Given all
this, reviewers struggle to maintain <i>focus</i> during code reviews.
Thus, every useless character drains the effectiveness of code
reviewing. In any one small example, it's not a big deal for code to
be unclear. Code reviewers can figure out what almost any code does,
given enough time and energy (perhaps with some follow-up questions to
the coder). But they can't afford to do that over and over again, year
in and year out. It's death by 1,000 cuts.
</p>
</div>
</div>
<div id="outline-container-orgheadline4" class="outline-3">
<h3 id="orgheadline4">A Good Example</h3>
<div class="outline-text-3" id="text-orgheadline4">
<p>
So, to communicate intent to the code reviewer, with a minimum of
characters, the coder could rewrite the code as follows:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">int</span> <span style="color: #0432fe;">printFirstNPositive</span><span style="color: #707183;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">n</span>, <span style="color: #228b22;">Collection</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Integer</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">c</span><span style="color: #707183;">)</span>
<span style="color: #707183;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">skipped</span> = 0;
<span style="color: #932092;">for</span> <span style="color: #7388d6;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">i</span> = 0; i < c.<span style="color: #228b22;">size</span><span style="color: #909183;">(</span><span style="color: #909183;">)</span> && i < <span style="color: #228b22;">n</span>; i++<span style="color: #7388d6;">)</span> <span style="color: #7388d6;">{</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">maybePositive</span> = c.get<span style="color: #909183;">(</span>i<span style="color: #909183;">)</span>;
<span style="color: #932092;">if</span> <span style="color: #909183;">(</span>maybePositive >= 0<span style="color: #909183;">)</span> <span style="color: #909183;">{</span>
System.out.println<span style="color: #709870;">(</span>maybePositive + <span style="color: #8b2252;">" "</span><span style="color: #709870;">)</span>;
<span style="color: #909183;">}</span> <span style="color: #932092;">else</span> <span style="color: #909183;">{</span>
skipped++;
<span style="color: #909183;">}</span>
<span style="color: #7388d6;">}</span>
System.out.println<span style="color: #7388d6;">(</span><span style="color: #8b2252;">"\n"</span><span style="color: #7388d6;">)</span>;
<span style="color: #932092;">return</span> skipped;
<span style="color: #707183;">}</span>
</pre>
</div>
<p>
Let's analyze each variable name change to see why they make the code
easier to read and understand:
</p>
<dl class="org-dl">
<dt><code>printFirstNPositive</code></dt><dd>unlike <code>processElements</code>, it's now clear
what the coder <i>intended</i> this function to do (and there's a
fighting chance of noticing a bug)</dd>
<dt><code>n</code></dt><dd>obvious given the name of the function, no need for a more
complicated name</dd>
<dt><code>c</code></dt><dd><code>collection</code> wasn't worth the mental tax it imposed, so at
least trim it by 9 characters to save the reader the mental
tax of scanning boilerplate characters; since the function is
short, and there's only one collection involved, it's easy to
remember that <code>c</code> is a collection of integers</dd>
<dt><code>skipped</code></dt><dd>unlike <code>results</code>, now self-documents (without a
comment) what the return value is supposed to be. Since
this is a short function, and the declaration of
<code>skipped</code> as an <code>int</code> is plain to see, calling it
<code>numSkipped</code> would have just wasted 3 characters</dd>
<dt><code>i</code></dt><dd>iterating through a <code>for</code> loop using <code>i</code> is a
well-established idiom that everyone instantly understands.
Give that <code>count</code> was useless anyway, <code>i</code> is preferable since
it saves 4 characters</dd>
<dt><code>maybePositive</code></dt><dd><code>num</code> just meant the same thing <code>int</code> did,
whereas <code>maybePositive</code> is hard to misunderstand and may help one
spot a bug</dd>
</dl>
<p>
It's also easier, now, to see there are two bugs in the code. In the
original version of the code, it wasn't clear if that the coder
intended to only print positive integers. Now the reader can notice
that there's a bug, because zero isn't positive (so <code>n</code> should be
greater than 0, not greater-than-or-equals). (There should also be
unit tests). Furthermore, because the first argument is now called
<code>maxToPrint</code> (as opposed to, say, <code>maxToConsider</code>), it's clear the
function won't always print enough elements if there are any
non-positive integers in the collection. Rewriting the function
correctly is left as an exercise for the reader.
</p>
</div>
</div>
<div id="outline-container-orgheadline5" class="outline-3">
<h3 id="orgheadline5">Naming Tenets (Unless You Know Better Ones)</h3>
<div class="outline-text-3" id="text-orgheadline5">
<ul class="org-ul">
<li>As <b>coders</b> our job is to communicate to <b>human readers</b>, not
computers.</li>
<li><i>Don't make me think</i>. Names should communicate the coder's
<b>intent</b> so the reader doesn't have to try to figure it out.</li>
<li>Code reviews are essential but <b>mentally taxing</b>. <b>Boilerplate</b> must
be minimized, because it drains reviewers' ability to concentrate on
the code.</li>
<li>We prefer good names over comments but can't replace all comments.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-orgheadline6" class="outline-2">
<h2 id="orgheadline6">Cookbook</h2>
<div class="outline-text-2" id="text-orgheadline6">
<p>
To live up to these tenets, here are some practical guidelines to use
when writing code.
</p>
</div>
<div id="outline-container-orgheadline7" class="outline-3">
<h3 id="orgheadline7">Don't Put the Type in the Name</h3>
<div class="outline-text-3" id="text-orgheadline7">
<p>
Putting the type of the variable in the name of the variable imposes a
mental tax on the reader (more boilerplate to scan over) and is often
a poor substitute for thinking of a better name. Modern editors like
Eclipse are also good at surfacing the type of a variable easily,
making it redundant to add the type into the name itself. This
practice also invites being wrong; I have seen code like this:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">Set</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #a0522d;">hostList</span> = hostSvc.getHosts<span style="color: #707183;">(</span>zone<span style="color: #707183;">)</span>;
</pre>
</div>
<p>
The most common mistakes are to append <code>Str</code> or <code>String</code> to the name,
or to include the type of collection in the name. Here are some
suggestions:
</p>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<colgroup>
<col class="org-left" />
<col class="org-left" />
</colgroup>
<thead>
<tr>
<th scope="col" class="org-left">Bad Name(s)</th>
<th scope="col" class="org-left">Good Name(s)</th>
</tr>
</thead>
<tbody>
<tr>
<td class="org-left">hostList, hostSet</td>
<td class="org-left">hosts, validHosts</td>
</tr>
<tr>
<td class="org-left">hostInputStream</td>
<td class="org-left">rawHostData</td>
</tr>
<tr>
<td class="org-left">hostStr, hostString</td>
<td class="org-left">hostText, hostJson, hostKey</td>
</tr>
<tr>
<td class="org-left">valueString</td>
<td class="org-left">firstName, lowercasedSKU</td>
</tr>
<tr>
<td class="org-left">intPort</td>
<td class="org-left">portNumber</td>
</tr>
</tbody>
</table>
<p>
More generally:
</p>
<ul class="org-ul">
<li>Pluralize the variable name instead of including the name of a
collection type</li>
<li>If you're tempted to add a scalar type (int, String, Char) into your
variable name, you should either:
<ul class="org-ul">
<li>Explain better what the variable <i>is</i></li>
<li>Explain what transformation you did to derive the new variable
(lowercased?)</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-orgheadline8" class="outline-3">
<h3 id="orgheadline8">Use Teutonic Names Most of The Time</h3>
<div class="outline-text-3" id="text-orgheadline8">
<p>
Most names should be Teutonic, following the spirit of languages like
Norwegian, rather than the elliptical vagueness of Romance languages
like English. Norwegian has more words like <i>tannlege</i> (literally
"tooth doctor") and <i>sykehus</i> (literally "sick house"), and fewer
words like <i>dentist</i> and <i>hospital</i> (which don't break down into other
English words, and are thus confusing unless you already know their
meaning). You should strive to name your variables in the Teutonic
spirit: straightforward to understand with minimal prior knowledge.
</p>
<p>
Another way to think about Teutonic naming is to <i>be as specific as
possible without being incorrect</i>. For example, if a function is
hard-coded to only check for CPU overload, then name it
<code>overloadedCPUFinder</code>, not <code>unhealthyHostFinder</code>. While it may be used
to find unhealthy hosts, <code>unhealthyHostFinder</code> makes it sound more
generic that it actually is.
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #b22222;">// </span><span style="color: #b22222;">GOOD</span>
<span style="color: #228b22;">Set</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #a0522d;">overloadedCPUs</span> = hostStatsTable.search<span style="color: #707183;">(</span>overCPUUtilizationThreshold<span style="color: #707183;">)</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">BAD</span>
<span style="color: #228b22;">Set</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #a0522d;">matches</span> = hostStatsTable.search<span style="color: #707183;">(</span>criteria<span style="color: #707183;">)</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">GOOD</span>
<span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">String</span><span style="color: #707183;">></span> <span style="color: #a0522d;">lowercasedNames</span> = people.apply<span style="color: #707183;">(</span>Transformers.toLowerCase<span style="color: #7388d6;">(</span><span style="color: #7388d6;">)</span><span style="color: #707183;">)</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">BAD</span>
<span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">String</span><span style="color: #707183;">></span> <span style="color: #a0522d;">newstrs</span> = people.apply<span style="color: #707183;">(</span>Transformers.toLowerCase<span style="color: #7388d6;">(</span><span style="color: #7388d6;">)</span><span style="color: #707183;">)</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">GOOD</span>
<span style="color: #228b22;">Set</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #0432fe;">findUnhealthyHosts</span><span style="color: #707183;">(</span><span style="color: #228b22;">Set</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Host</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">droplets</span><span style="color: #707183;">)</span> <span style="color: #707183;">{</span> <span style="color: #707183;">}</span>
<span style="color: #b22222;">// </span><span style="color: #b22222;">BAD</span>
<span style="color: #228b22;">Set</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #0432fe;">processHosts</span><span style="color: #707183;">(</span><span style="color: #228b22;">Set</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Host</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">hosts</span><span style="color: #707183;">)</span> <span style="color: #707183;">{</span> <span style="color: #707183;">}</span>
</pre>
</div>
<p>
The exceptions to the Teutonic naming convention are covered later on
in this section: idioms and short variable names.
</p>
<p>
It's also worth noting that this section isn't suggesting to <i>never</i>
use generic names. Code that is doing something truly generic <i>should</i>
have a generic name. For example, <code>transform</code> in the below example is
valid because it's part of a generic string manipulation library:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #932092;">class</span> <span style="color: #228b22;">StringTransformer</span> <span style="color: #707183;">{</span>
<span style="color: #228b22;">String</span> <span style="color: #0432fe;">transform</span><span style="color: #7388d6;">(</span><span style="color: #228b22;">String</span> <span style="color: #a0522d;">input</span>, <span style="color: #228b22;">TransformerChain</span> <span style="color: #a0522d;">additionalTransformers</span><span style="color: #7388d6;">)</span>;
<span style="color: #707183;">}</span>
</pre>
</div>
</div>
</div>
<div id="outline-container-orgheadline9" class="outline-3">
<h3 id="orgheadline9">Move Simple Comments Into Variable Names</h3>
<div class="outline-text-3" id="text-orgheadline9">
<p>
As illustrated earlier, variable names cannot (and should not) replace
<i>all</i> comments. But if a short comment <i>can</i> fit into the variable
name, that's probably where it should go. This is because:
</p>
<ul class="org-ul">
<li>It's less visual clutter for the code reviewer to wade through
(comments are a mental tax, so should provide true value)</li>
<li>If a variable is used a long <i>distance</i> from the comment, the code
reviewer doesn't have to break their <i>focus</i> and scroll back to the
comment to understand the variable</li>
</ul>
<p>
For example,
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #b22222;">// </span><span style="color: #b22222;">BAD</span>
<span style="color: #228b22;">String</span> <span style="color: #a0522d;">name</span>; <span style="color: #b22222;">// </span><span style="color: #b22222;">First and last name</span>
<span style="color: #b22222;">// </span><span style="color: #b22222;">GOOD</span>
<span style="color: #228b22;">String</span> <span style="color: #a0522d;">fullName</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">BAD</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">port</span>; <span style="color: #b22222;">// </span><span style="color: #b22222;">TCP port number</span>
<span style="color: #b22222;">// </span><span style="color: #b22222;">GOOD</span>
<span style="color: #228b22;">int</span> <span style="color: #a0522d;">tcpPort</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">BAD</span>
<span style="color: #b22222;">// </span><span style="color: #b22222;">This is derived from the JSON header</span>
<span style="color: #228b22;">String</span> <span style="color: #a0522d;">authCode</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">GOOD</span>
<span style="color: #228b22;">String</span> <span style="color: #a0522d;">jsonHeaderAuthCode</span>;
</pre>
</div>
</div>
</div>
<div id="outline-container-orgheadline10" class="outline-3">
<h3 id="orgheadline10">Avoid Over-used Cliches</h3>
<div class="outline-text-3" id="text-orgheadline10">
<p>
In addition to not being Teutonic, the following variable names have
been so horribly abused over the years that they should never be used,
ever.
</p>
<ul class="org-ul">
<li><code>val</code>, <code>value</code></li>
<li><code>result</code>, <code>res</code>, <code>retval</code></li>
<li><code>tmp</code>, <code>temp</code></li>
<li><code>count</code></li>
<li><code>str</code></li>
</ul>
<p>
The moratorium on these names extends to variations that just add in a
type name (not a good idea anyway), such as <code>tempString</code>, or <code>intStr</code>,
etc.
</p>
</div>
</div>
<div id="outline-container-orgheadline11" class="outline-3">
<h3 id="orgheadline11">Use Idioms Where Meaning is Obvious</h3>
<div class="outline-text-3" id="text-orgheadline11">
<p>
Unlike the cliches, there are some idioms that are so
widely-understood and unabused that they're safe to use, even if by
the letter of they law they're too cryptic. Some examples are (these
are Java/C specific examples, but the same principles apply to all
languages):
</p>
<ul class="org-ul">
<li>use of <code>i</code>, <code>j</code> and <code>k</code> in straightforward <code>for</code> loops</li>
<li>use of <code>n</code> for a limit/quantity when it's obvious what it would do</li>
<li>use of <code>e</code> for an Exception in a <code>catch</code> clause</li>
</ul>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #b22222;">// </span><span style="color: #b22222;">OK</span>
<span style="color: #932092;">for</span> <span style="color: #707183;">(</span><span style="color: #228b22;">int</span> <span style="color: #a0522d;">i</span> = 0; i < hosts.<span style="color: #228b22;">size</span><span style="color: #7388d6;">(</span><span style="color: #7388d6;">)</span>; i++<span style="color: #707183;">)</span> <span style="color: #707183;">{</span> <span style="color: #707183;">}</span>
<span style="color: #b22222;">// </span><span style="color: #b22222;">OK</span>
<span style="color: #228b22;">String</span> <span style="color: #0432fe;">repeat</span><span style="color: #707183;">(</span><span style="color: #228b22;">String</span> <span style="color: #a0522d;">s</span>, <span style="color: #228b22;">int</span> <span style="color: #a0522d;">n</span><span style="color: #707183;">)</span>;
</pre>
</div>
<p>
<b>Warning</b>: idioms should only be used in cases where it's <i>obvious</i>
what they mean.
</p>
</div>
</div>
<div id="outline-container-orgheadline12" class="outline-3">
<h3 id="orgheadline12">May Use Short Names Over Short Distances When Obvious</h3>
<div class="outline-text-3" id="text-orgheadline12">
<p>
Short names, even one-letter names, are preferable in certain
circumstances. When reviewers see a long name, they tend to think they
should pay attention to them, and then if the name turns out to be
completely useless, they just wasted time. A short name can convey the
idea that the only useful thing to know about the variable is its
type. So it is okay to use short variable names (one- or two-letter),
when both of the following are true:
</p>
<ol class="org-ol">
<li>The <i>distance</i> between declaration and use isn't great (say within
5 lines, so the declaration is within the reader's field of
vision)</li>
<li>There isn't a better name for the variable than its type</li>
<li>The reader doesn't have too many other things to remember at that
point in the code (remember, studies show people can remember about
<a href="http://en.wikipedia.org/wiki/Working_memory#Capacity">7 things</a>).</li>
</ol>
<p>
Here's an example:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">void</span> <span style="color: #0432fe;">updateJVMs</span><span style="color: #707183;">(</span><span style="color: #228b22;">HostService</span> <span style="color: #a0522d;">s</span>, <span style="color: #228b22;">Filter</span> <span style="color: #a0522d;">obsoleteVersions</span><span style="color: #707183;">)</span>
<span style="color: #707183;">{</span>
<span style="color: #b22222;">// </span><span style="color: #b22222;">'hs' is only used once, and is "obviously" a HostService</span>
<span style="color: #228b22;">List</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Host</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">hs</span> = s.fetchHostsWithPackage<span style="color: #7388d6;">(</span>obsoleteVersions<span style="color: #7388d6;">)</span>;
<span style="color: #b22222;">// </span><span style="color: #b22222;">'hs' is used only within field of vision of reader</span>
<span style="color: #228b22;">Workflow</span> <span style="color: #a0522d;">w</span> = startUpdateWorkflow<span style="color: #7388d6;">(</span>hs<span style="color: #7388d6;">)</span>;
<span style="color: #932092;">try</span> <span style="color: #7388d6;">{</span>
w.wait<span style="color: #909183;">(</span><span style="color: #909183;">)</span>;
<span style="color: #7388d6;">}</span> <span style="color: #932092;">finally</span> <span style="color: #7388d6;">{</span>
w.close<span style="color: #909183;">(</span><span style="color: #909183;">)</span>;
<span style="color: #7388d6;">}</span>
<span style="color: #707183;">}</span>
</pre>
</div>
<p>
You <i>could</i> also write:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">void</span> <span style="color: #0432fe;">updateJVMs</span><span style="color: #707183;">(</span><span style="color: #228b22;">HostSevice</span> <span style="color: #a0522d;">hostService</span>, <span style="color: #228b22;">Filter</span> <span style="color: #a0522d;">obsoleteVersions</span><span style="color: #707183;">)</span>
<span style="color: #707183;">{</span>
<span style="color: #228b22;">List</span><span style="color: #7388d6;"><</span><span style="color: #228b22;">Host</span><span style="color: #7388d6;">></span> <span style="color: #a0522d;">hosts</span> = hostService.fetchHostsWithPackage<span style="color: #7388d6;">(</span>obsoleteVersions<span style="color: #7388d6;">)</span>;
<span style="color: #228b22;">Workflow</span> <span style="color: #a0522d;">updateWorkflow</span> = startUpdateWorkflow<span style="color: #7388d6;">(</span>hosts<span style="color: #7388d6;">)</span>;
<span style="color: #932092;">try</span> <span style="color: #7388d6;">{</span>
updateWorkflow.wait<span style="color: #909183;">(</span><span style="color: #909183;">)</span>;
<span style="color: #7388d6;">}</span> <span style="color: #932092;">finally</span> <span style="color: #7388d6;">{</span>
updateWorkflow.close<span style="color: #909183;">(</span><span style="color: #909183;">)</span>;
<span style="color: #7388d6;">}</span>
<span style="color: #707183;">}</span>
</pre>
</div>
<p>
But this takes up more space with no real gain; the variables are all
used so close to their source that the reader has no trouble keeping
track of what they mean. Furthermore, the long name <code>updateWorkflow</code>
signals to the reviewer that there's something significant about the
name. The reviewer then loses mental energy determining that the name
is just boilerplate. Not a big deal in this one case, but remember,
code reviewing is all about death by 1,000 cuts.
</p>
</div>
</div>
<div id="outline-container-orgheadline13" class="outline-3">
<h3 id="orgheadline13">Remove Thoughtless One-Time Variables</h3>
<div class="outline-text-3" id="text-orgheadline13">
<p>
One-time variables (OTVs), also known as <i>garbage variables</i>, are
those variables used passively for intermediate results passed between
functions. They <i>sometimes</i> serve a valid purpose (see the next
cookbook items), but are often left in thoughtlessly, and just clutter
up the codebase. In the following code fragment, the coder has just
made the reader's life <b>more</b> difficult:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #a0522d;">results</span> = hostService.fetchMatchingHosts<span style="color: #707183;">(</span>hostFilter<span style="color: #707183;">)</span>;
<span style="color: #932092;">return</span> dropletFinder<span style="color: #707183;">(</span>results<span style="color: #707183;">)</span>;
</pre>
</div>
<p>
Instead, coders should make a pass through their code and simplify to:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #932092;">return</span> dropletFinder<span style="color: #707183;">(</span>hostService.fetchMatchingHosts<span style="color: #7388d6;">(</span>hostFilter<span style="color: #7388d6;">)</span><span style="color: #707183;">)</span>;
</pre>
</div>
</div>
</div>
<div id="outline-container-orgheadline14" class="outline-3">
<h3 id="orgheadline14">Use Short OTVs to Break Long Lines</h3>
<div class="outline-text-3" id="text-orgheadline14">
<p>
Sometimes you need an OTV in order to break up a really long line:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #a0522d;">hs</span> = hostService.fetchMatchingHosts<span style="color: #707183;">(</span>hostFilter<span style="color: #707183;">)</span>;
<span style="color: #932092;">return</span> DropletFinderFactoryFactory<span style="color: #707183;">(</span><span style="color: #707183;">)</span>.getFactory<span style="color: #707183;">(</span><span style="color: #707183;">)</span>.getFinder<span style="color: #707183;">(</span>region<span style="color: #707183;">)</span>.dropletFinder<span style="color: #707183;">(</span>hs<span style="color: #707183;">)</span>;
</pre>
</div>
<p>
This is ok, although since the <i>distance</i> is so short, you can give
the OTV and one- or two-letter name (<code>hs</code>) to save visual clutter.
</p>
</div>
</div>
<div id="outline-container-orgheadline15" class="outline-3">
<h3 id="orgheadline15">Use Short OTVs to Break up Complicated Expressions</h3>
<div class="outline-text-3" id="text-orgheadline15">
<p>
It can be difficult to read code like this:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #932092;">return</span> hostUpdater.updateJVM<span style="color: #707183;">(</span>hostService.fetchMatchingHosts<span style="color: #7388d6;">(</span>hostFilter<span style="color: #7388d6;">)</span>,
JVMServiceFactory.factory<span style="color: #7388d6;">(</span>region<span style="color: #7388d6;">)</span>.getApprovedVersions<span style="color: #7388d6;">(</span><span style="color: #7388d6;">)</span>,
RegionFactory.factory<span style="color: #7388d6;">(</span>region<span style="color: #7388d6;">)</span>.getZones<span style="color: #7388d6;">(</span><span style="color: #7388d6;">)</span><span style="color: #707183;">)</span>;
</pre>
</div>
<p>
So it's ok to write:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">Host</span><span style="color: #707183;">></span> <span style="color: #a0522d;">hs</span> = hostService.fetchMatchingHosts<span style="color: #707183;">(</span>hostFilter<span style="color: #707183;">)</span>;
<span style="color: #228b22;">Set</span><span style="color: #707183;"><</span><span style="color: #228b22;">JVMVersions</span><span style="color: #707183;">></span> <span style="color: #a0522d;">js</span> = JVMServiceFactory.factory<span style="color: #707183;">(</span>region<span style="color: #707183;">)</span>.getApprovedVersions<span style="color: #707183;">(</span><span style="color: #707183;">)</span>,
<span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">AvailabilityZone</span><span style="color: #707183;">></span> <span style="color: #a0522d;">zs</span> = RegionFactory<span style="color: #707183;">(</span>region<span style="color: #707183;">)</span>.getZones<span style="color: #707183;">(</span><span style="color: #707183;">)</span>;
<span style="color: #932092;">return</span> hostUpdater.updateJVM<span style="color: #707183;">(</span>hs, js, zs<span style="color: #707183;">)</span>;
</pre>
</div>
<p>
Again, because the <i>distances</i> are all short and the meanings are all
obvious, short names can be used.
</p>
</div>
</div>
<div id="outline-container-orgheadline16" class="outline-3">
<h3 id="orgheadline16">Use Longer OTVs to Explain Confusing Code</h3>
<div class="outline-text-3" id="text-orgheadline16">
<p>
Sometimes you need OTVs simply to explain what code is doing. For
example, sometimes you have to use poorly-named code that someone else
(ahem) wrote, so you can't fix the name. But you can use a meaningful
OTV to explain what's going on. For example,
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">Column</span><span style="color: #707183;">></span> <span style="color: #a0522d;">pivotedColumns</span> = olapCube.transformAlpha<span style="color: #707183;">(</span><span style="color: #707183;">)</span>;
updateDisplay<span style="color: #707183;">(</span>pivotedColumns<span style="color: #707183;">)</span>;
</pre>
</div>
<p>
Note in this case you should not use a short OTV:
</p>
<div class="org-src-container">
<pre class="src src-java"><span style="color: #228b22;">List</span><span style="color: #707183;"><</span><span style="color: #228b22;">Column</span><span style="color: #707183;">></span> <span style="color: #a0522d;">ps</span> = olapCube.transformAlpha<span style="color: #707183;">(</span><span style="color: #707183;">)</span>;
updateDisplay<span style="color: #707183;">(</span>ps<span style="color: #707183;">)</span>;
</pre>
</div>
<p>
That just adds too much visual clutter without helping to explain the
code sufficiently.
</p>
</div>
</div>
</div>
<div id="outline-container-orgheadline17" class="outline-2">
<h2 id="orgheadline17">Updates</h2>
<div class="outline-text-2" id="text-orgheadline17">
<dl class="org-dl">
<dt>26-May-2016</dt><dd>fixed some of the issues brought up in the comments -
thanks for the feedback!</dd>
</dl>
</div>
</div>
<div id="footnotes">
<h2 class="footnotes">Footnotes: </h2>
<div id="text-footnotes">
<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1">1</a></sup> <div class="footpara">This code
example is used for illustrative purposes only and is not meant to be
an example of well-designed code, variable names notwithstanding.</div></div>
<div class="footdef"><sup><a id="fn.2" class="footnum" href="#fnr.2">2</a></sup> <div class="footpara">There are obvious exceptions such as nuclear
power plant control rod algorithms, distributed locking protocols, and
so forth.</div></div>
</div>
</div></div>
<div id="postamble" class="status">
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com25tag:blogger.com,1999:blog-32049549.post-64356930639622743722009-04-28T11:05:00.000-07:002009-04-28T11:24:30.910-07:00Six Audacious Goals for Your SystemWith apologies to the authors of the <a href="http://www.graficaobscura.com/future/futnotes.html">futurist programming notes</a>, here is a set of audacious goals for your system (by which I mean your collection of web sites, webservices, databases, and so on):<div><ol><li>Make your <b>entire </b>system runnable (for debugging/development) on a single machine, via a single command,</li><li>...without manual configuration,</li><li>...without an Internet connection.</li><li>Demonstrate that your system works flawlessly even when you permanently and unexpectedly unplug the power cable from any one machine (even your most precious database).</li><li>Make one of your N-tier architectures M-tier, where M < N.</li><li>Optimize every <b>user-visible</b> action so that it is perceived to complete in less than one second.</li></ol><br /></div>Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com0tag:blogger.com,1999:blog-32049549.post-69414292517614069412008-05-21T22:11:00.000-07:002008-05-21T23:00:56.353-07:00Ulrich Drepper's Memory Paper and CLI recently came across Ulrich Drepper's excellent paper, <a href="http://udrepper.livejournal.com/19557.html">What Every Programmer Should Know About Memory</a>. There is a lot of fascinating stuff in there about an important class of things you <i>sometimes</i> need to do to achieve excellent performance. While the paper concentrates on C, I was wondering if some of the same effects could be observed in a high-level language like <a href="http://en.wikipedia.org/wiki/Common_Lisp">CL</a> (for the record, I think CL is <i>both</i> high- and low-level, but whatever...) I did a quick experiment which <i>suggests</i> that at least one of Ulrich's optimizations works in CL. [Note: the following is <i>not</i> an attempt to produce mathematically correct results, as Ulrich did; I just wanted to see if the order in which memory was accessed seemed to matter.]:<pre class="code">(<span class="keyword">declaim</span> (optimize (speed 3) (safety 0)))<br /><br />(<span class="keyword">defun</span> <span class="function-name">matrix-multiply-fast?</span> ()<br /> (<span class="keyword">let</span> ((m1 (make-array '(1000 1000) <span class="builtin">:element-type</span> 'fixnum))<br /> (m2 (make-array '(1000 1000) <span class="builtin">:element-type</span> 'fixnum))<br /> (m3 (make-array '(1000 1000) <span class="builtin">:element-type</span> 'fixnum)))<br /> (<span class="keyword">loop</span> repeat 100<br /> do<br /> (<span class="keyword">loop</span> for i upto 1000<br /> do<br /> (<span class="keyword">loop</span> for j upto 1000<br /> do<br /> (setf (aref m3 i j) (* (aref m1 i j) (aref m2 i j))))))))<br /><br />(<span class="keyword">defun</span> <span class="function-name">matrix-multiply-slow?</span> ()<br /> (<span class="keyword">let</span> ((m1 (make-array '(1000 1000) <span class="builtin">:element-type</span> 'fixnum))<br /> (m2 (make-array '(1000 1000) <span class="builtin">:element-type</span> 'fixnum))<br /> (m3 (make-array '(1000 1000) <span class="builtin">:element-type</span> 'fixnum)))<br /> (<span class="keyword">loop</span> repeat 100<br /> do<br /> (<span class="keyword">loop</span> for i upto 1000<br /> do<br /> (<span class="keyword">loop</span> for j upto 1000<br /> do<br /> (setf (aref m3 i j) (* (aref m1 i j) (aref m2 j i))))))))</pre>Note the only difference between the two functions is the order in which the elements of the 2nd array are accessed. After compiling the above file I did the following from the CL prompt:<pre class="code"><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(time (matrix-multiply-fast?))</span><br /><div class="codepop"><span class="slime-repl-output">Evaluation took:<br /> 2.776 seconds of real time<br /> 2.508157 seconds of user run time<br /> 0.048003 seconds of system run time<br /> [Run times include 0.028 seconds GC run time.]<br /> 0 calls to %EVAL<br /> 0 page faults and<br /> 12,000,160 bytes consed.</span><span class="slime-repl-result"></span></div><br /><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(time (matrix-multiply-slow?))</span><br /><div class="codepop"><span class="slime-repl-output">Evaluation took:<br /> 3.926 seconds of real time<br /> 3.632227 seconds of user run time<br /> 0.016001 seconds of system run time<br /> 0 calls to %EVAL<br /> 0 page faults and<br /> 12,008,280 bytes consed.</span></div></pre>Assuming the above is all correct, it sort-of duplicates Ulrich's result where accessing an array in a column-major order is slower (see figure 6.1 for an illustration). Now, I have to admit that, for lack of time, I didn't read Ulrich's paper in great depth and kind of lazily jumped to section six. I'd be curious to know if this sort of optimization is already well-known in the CL world (and/or for other "high-level" programming languages). Some casual googling turned up an excellent <a href="http://www.lrde.epita.fr/~didier/research/verna.06.imecs.pdf">paper</a> about optimizing CL via type annotations, but I didn't see anyone directly addressing Ulrich's points. I'd be curious if any readers of this blog know more.Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com1tag:blogger.com,1999:blog-32049549.post-63391519579360584942008-03-23T23:58:00.000-07:002008-04-06T12:46:48.649-07:00Optimizing CLThis blog is about mechanically optimizing <a href="http://en.wikipedia.org/wiki/Common_Lisp">CL</a> code. We will not discuss optimizing algorithms; instead we'll transform the code in rote ways to improve performance. To illustrate these techniques, we'll re-implement Perl's core <b>Text::Soundex</b> function in CL. Let's start with the Perl code, straight from the 5.8.8 distribution.<pre class="code">$<span class="variable-name">soundex_nocode</span> = undef;<br /><br /><span class="keyword">sub</span> <span class="function-name">soundex</span><br />{<br /> <span class="type">local</span> (@<span class="underline"><span class="variable-name">s</span></span>, $<span class="variable-name">f</span>, $<span class="variable-name">fc</span>, $<span class="variable-name">_</span>) = @<span class="underline"><span class="variable-name">_</span></span>;<br /><br /> push @<span class="underline"><span class="variable-name">s</span></span>, <span class="string">''</span> <span class="keyword">unless</span> @<span class="underline"><span class="variable-name">s</span></span>; <span class="comment"># handle no args as a single empty string<br /></span><br /> <span class="keyword">foreach</span> (@<span class="underline"><span class="variable-name">s</span></span>)<br /> {<br /> $<span class="variable-name">_</span> = uc $<span class="variable-name">_</span>;<br /> tr<span class="string">/A-Z//</span>cd;<br /><br /> <span class="keyword">if</span> ($<span class="variable-name">_</span> eq <span class="string">''</span>)<br /> {<br /> $<span class="variable-name">_</span> = $<span class="variable-name">soundex_nocode</span>;<br /> }<br /> <span class="keyword">else</span><br /> {<br /> ($<span class="variable-name">f</span>) = <span class="string">/^(.)/</span>;<br /> tr<span class="string">/AEHIOUWYBFPVCGJKQSXZDTLMNR/00000000111122222222334556/</span>;<br /> ($<span class="variable-name">fc</span>) = <span class="string">/^(.)/</span>;<br /> s<span class="string">/^$fc+//</span>;<br /> tr<span class="string">///</span>cs;<br /> tr<span class="string">/0//</span>d;<br /> $<span class="variable-name">_</span> = $<span class="variable-name">f</span> . $<span class="variable-name">_</span> . <span class="string">'000'</span>;<br /> s<span class="string">/^(.{4}).*/$1/</span>;<br /> }<br /> }<br /><br /> wantarray ? @<span class="underline"><span class="variable-name">s</span></span> : shift @<span class="underline"><span class="variable-name">s</span></span>;<br />}</pre>We do not implement the auxiliary behavior of the Perl version, namely we do not optionally accept a list of strings, nor do we support overriding the <b>NIL</b> return case. Both would be easy to implement but would be tangential to this blog entry. We port the rest of the functionality as faithfully as possible, though, so that the Perl can serve as a useful performance benchmark.<br /><br />Perl's <b>soundex</b> uses regular expressions and string substitution operators heavily, some having analogues in CL and some not. For example, CL lacks Perl's <a href="http://perldoc.perl.org/functions/tr.html">tr///</a> operator, so we implement a crude version:<pre class="code">(<span class="keyword">defparameter</span> <span class="variable-name">*ascii-table*</span> (<span class="keyword">let</span> ((table (make-array '(256) <span class="builtin">:element-type</span> 'character)))<br /> (<span class="keyword">loop</span><br /> for i below 256<br /> do (setf (aref table i) (code-char i)))<br /> table))<br /><br />(<span class="keyword">defun</span> <span class="function-name">tr</span> (string from-table to-table)<br /> <span class="doc">"Crude version of Perl's tr/// operator."</span><br /> (<span class="keyword">let</span> ((table (copy-seq *ascii-table*)))<br /> (<span class="keyword">loop</span><br /> for from-char across from-table<br /> and to-char across to-table<br /> do (setf (aref table (char-code from-char)) to-char))<br /> (map 'string<br /> #'(<span class="keyword">lambda</span> (c) (aref table (char-code c)))<br /> string)))<br /></pre>Our <b>TR</b> supports only the limited case needed by <b>SOUNDEX</b> (i.e., mapping one set of characters to another). The Perl version can do more, such as removing letters that don't appear in the first set, and removing duplicates. In fact, the Perl <b>soundex</b> relies on that ability to remove duplicates, so we implement a function to do that as well.<pre class="code">(<span class="keyword">defun</span> <span class="function-name">uniq!</span> (seq)<br /> (<span class="keyword">cond</span><br /> ((> (length seq) 1)<br /> (<span class="keyword">do*</span> ((cur 0)<br /> (cur-elt (elt seq cur) (elt seq cur))<br /> (next 1 (1+ next)))<br /> ((>= next (length seq)) (subseq seq 0 (1+ cur)))<br /> (<span class="keyword">let</span> ((next-char (elt seq next)))<br /> (<span class="keyword">unless</span> (eql cur-elt next-char)<br /> (incf cur)<br /> (setf (elt seq cur) next-char)))))<br /> (t seq)))</pre><b>UNIQ!</b> coalesces adjacent duplicate items into one item. CL's built-in <b><a href="http://www.lisp.org/HyperSpec/Body/fun_remove-du_e-duplicates.html">DELETE-DUPLICATES</a></b> doesn't work because it coalesces <i>all</i> duplicates, not just adjacent ones.<br /><br />These two utility functions make porting the rest of the <b>soundex</b> easy. The following shows the CL equivalents of each important line of <b>soundex</b>:<table class="code"><tr><th>Perl</th><th>What It Does</th><th>CL Equivalent</th></tr><tr><td>$<span class="variable-name">_</span> = uc $<span class="variable-name">_</span>;</td><td>Uppercase the string</td><td>(<a href="http://www.lisp.org/HyperSpec/Body/fun_string-up_g-capitalize.html">string-upcase</a> ...)</td></tr><tr><td>tr<span class="string">/A-Z//</span>cd;</td><td>Remove any non-upper-alpha characters</td><td>(<a href="http://www.lisp.org/HyperSpec/Body/fun_removecm__elete-if-not.html">remove-if-not</a> 'alpha-char-p string)</td></tr><tr><td>($<span class="variable-name">f</span>) = <span class="string">/^(.)/</span>;</td><td>Gets the first character of the string</td><td>(<a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_char_.htm">char</a> s 0)</td></tr><tr><td>tr<span class="string">/AE.../00.../</span>;</td><td>Map letters to digits values</td><td>(tr s <span class="string">"AE..."</span> <span class="string">"00..."</span>)</td></tr><tr><td>s<span class="string">/^$fc+//</span>;</td><td>Remove leading copies of the character in $fc</td><td>(<a href="http://www.lisp.org/HyperSpec/Body/fun_string-tr_g-right-trim.html">string-left-trim</a> (vector fc) s2)</td></tr><tr><td>tr<span class="string">///</span>cs;</td><td>Remove adjacent duplicates</td><td>(uniq! ...)</td></tr><tr><td>tr<span class="string">/0//</span>d;</td><td>Delete any '0' characters</td><td>(<a href="http://www.lisp.org/HyperSpec/Body/fun_removecm__elete-if-not.html">delete</a> #\0 ...)</td></tr><tr><td>$<span class="variable-name">_</span> = $<span class="variable-name">f</span> . $<span class="variable-name">_</span> . <span class="string">'000'</span>;</td><td>Concatenate, plus ensure length of at least 4</td><td>(<a href="http://www.lisp.org/HyperSpec/Body/fun_concatenate.html">concatenate</a> 'string ...)</td></tr><tr><td>s<span class="string">/^(.{4}).*/$1/</span>;</td><td>Strip off all but the first 4 characters</td><td>(<a href="http://www.lisp.org/HyperSpec/Body/acc_subseq.html">subseq</a> ... 0 4)</td></tr></table><br />Here is the actual code:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">soundex</span> (string)<br /> (<span class="keyword">let</span> ((s (string-upcase (remove-if-not 'alpha-char-p string))))<br /> (<span class="keyword">when</span> (plusp (length s))<br /> (<span class="keyword">let</span> ((f (char s 0)))<br /> (<span class="keyword">let*</span> ((s2 (tr s <span class="string">"AEHIOUWYBFPVCGJKQSXZDTLMNR"</span> <span class="string">"00000000111122222222334556"</span>))<br /> (fc (char s2 0)))<br /> (setf s2 (delete #\0<br /> (uniq! (string-left-trim (vector fc) s2))))<br /> (subseq (concatenate 'string (vector f) s2 <span class="string">"000"</span>) 0 4))))))</pre><br />Now let's see if it works. Using <a href="http://common-lisp.net/project/slime/">SLIME</a>, type <b>C-c C-k</b> to compile the file. Then try <b>SOUNDEX</b> at the CL prompt:<pre class="code"><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(soundex "supercalifrag")</span><br /><div class="codepop"><span class="slime-repl-result"><span class="slime-repl-inputed-output">"S162"</span></span><span class="slime-repl-result"></span></div></pre>If you try the Perl version, you'll find it returns the same thing (I tried other test cases, as well, but they are not relevant to this blog).<br /><br />At this point you might be feeling rather proud of yourself, after all you ported that Perl code pretty quickly, right? And I bet it even performs better already; after all Perl is interpreted and CL is compiled! Let's verify that assumption using the <a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_time.htm"><b>TIME</b></a> macro built in to CL:<pre class="code"><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(time (dotimes (i 100000) (soundex "supercalifrag")))</span><br /><div class="codepop"><span class="slime-repl-output">Evaluation took:<br /> 2.644 seconds of real time<br /> 2.640165 seconds of user run time<br /> 0.012001 seconds of system run time<br /> [Run times include 0.076 seconds GC run time.]<br /> 0 calls to %EVAL<br /> 0 page faults and<br /> 207,987,480 bytes consed.<br /></span></div></pre>Now let's compare that to the Perl code's performance:<pre class="code"><span class="comint-highlight-prompt">$ </span><span class="comint-highlight-input">time ./soundex-bench.pl 100000</span><br /><div class="codepop">real 0m1.069s<br />user 0m1.064s<br />sys 0m0.008s</div></pre>D'oh! The Perl code <i>kicked our ass</i>! It's more than twice as fast as our CL! How could this have happened to us? Maybe we forgot to turn on some optimizations? We add: <pre class="code">(<span class="keyword">declaim</span> (optimize (speed 3) (safety 0)))</pre> to the top of our file and recompile. Now let's see the results:<pre class="code"><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(time (dotimes (i 100000) (soundex "supercalifrag")))</span><br /><div class="codepop"><span class="slime-repl-output">Evaluation took:<br /> 2.061 seconds of real time<br /> 2.040128 seconds of user run time<br /> 0.020001 seconds of system run time<br /> [Run times include 0.1 seconds GC run time.]<br /> 0 calls to %EVAL<br /> 0 page faults and<br /> 183,988,752 bytes consed.<br /></span></div></pre>Ok, that's a <i>little</i> better, but come <i>on</i>, it is still approximately <i>twice</i> as slow as the Perl! And look at how much memory is allocated ("consed") in the course of doing only 100,000 calls: that's approximately 175 megabytes (admittedly not all at once, but still, that's just plain embarrassing!)<br /><br />Now before diving into optimization, let us review a good approach to optimizing CL.<ol><li>Measure first.<br /> </li><li>Avoid guessing!<br /> </li><li>Fix your algorithm(s) first (not shown in this blog entry).<br /> </li><li>Fix memory consumption next.<br /> </li><li>Then go after CPU consumption, primarily by adding type information.<br /></li></ol>Remember, this blog is <i>not</i> about algorithmic optimizations; we will pretend (for the sake of illustration only!) that you've already ruled out the need, in order to focus on mechanical optimization.<br /><br />Following step one from the above strategy, start by profiling. Define a function, <b>MANY-SOUNDEX</b> that performs our <b>TIME</b> loop from above. Also define a function <b>PROFILE-SOUNDEX</b> that employs <a href="http://sbcl.sourceforge.net/">SBCL</a>'s <a href="http://www.sbcl.org/manual/Deterministic-Profiler.html">sb-profile</a> package to profile the functions involved in implementing <b>SOUNDEX</b>, including some built-ins that it calls. To profile a function, pass its name to <b>SB-PROFILE:PROFILE</b>. After exercising the code, call <b>SB-PROFILE:REPORT</b>, which prints timing information. Call <b>SB-PROFILE:RESET</b> between runs unless you want the results to accumulate (we don't, in this case).<pre class="code">(<span class="keyword">defun</span> <span class="function-name">many-soundex</span> ()<br /> (time<br /> (<span class="keyword">dotimes</span> (i 100000)<br /> (soundex <span class="string">"supercalifrag"</span>))))<br /><br />(<span class="keyword">defun</span> <span class="function-name">profile-soundex</span> ()<br /> <span class="comment-delimiter">;; </span><span class="comment">Don't accumulate results between runs.<br /></span> (sb-profile:reset)<br /> <span class="comment-delimiter">;; </span><span class="comment">Calling this every time through in case any of the user-defined<br /></span> <span class="comment-delimiter">;; </span><span class="comment">functions was recompiled.<br /></span> (sb-profile:profile soundex soundex-tr uniq!<br /> concatenate make-string subseq<br /> string-left-trim delete-if-not<br /> tr delete string-upcase nsubseq)<br /> (many-soundex)<br /> (sb-profile:report))</pre>If you notice some unfamiliar functions there, don't worry, they're going to be defined later; for the purposes of this blog I just want to define this function once, even though in real life I modified it many times.<br /><br />Let's see what it produces:<pre class="code"><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(profile-soundex)</span><br /><div class="codepop"><span class="slime-repl-output"> 3.713 seconds of real time<br /> 3.160197 seconds of user run time<br /> 0.548034 seconds of system run time<br /> [Run times include 0.08 seconds GC run time.]<br /> 0 calls to %EVAL<br /> 0 page faults and<br /> 200,022,056 bytes consed.<br /> seconds | consed | calls | sec/call | name <br />-----------------------------------------------------------<br /> 1.394 | 140,115,928 | 100,000 | 0.000014 | TR<br /> 0.618 | 26,230,456 | 100,000 | 0.000006 | CONCATENATE<br /> 0.210 | 661,840 | 100,000 | 0.000002 | REMOVE-IF-NOT<br /> 0.170 | 3,864,248 | 100,000 | 0.000002 | DELETE<br /> 0.164 | 9,865,784 | 100,000 | 0.000002 | SOUNDEX<br /> 0.131 | 0 | 100,000 | 0.000001 | UNIQ!<br /> 0.130 | 9,274,680 | 100,000 | 0.000001 | STRING-UPCASE<br /> 0.058 | 10,012,888 | 100,003 | 0.000001 | SUBSEQ<br /> 0.000 | 0 | 7 | 0.000000 | STRING-LEFT-TRIM<br />-----------------------------------------------------------<br /> 2.878 | 200,025,824 | 800,010 | | Total<br /></span></div></pre>This shows that we probably should optimize <b>TR</b> for memory consumption first. What's wrong with <b>TR</b>? Every call to <b>TR</b> copies <b>*ASCII-TABLE*</b> into the <b>TABLE</b> local variable, which will later be used to map each character to a (potentially) different one. The inefficiency is that <b>TABLE</b> only varies based on the 2nd and 3rd arguments (<b>FROM-TABLE</b> and <b>TO-TABLE</b>). Since <b>SOUNDEX</b> <i>always</i> passes in the same thing for those two arguments every time, it is wasteful to continually recreate the same <b>TABLE</b>. To fix it use a closure that "closes over" a single instance of <b>TABLE</b>:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">make-tr-fn</span> (from-table to-table)<br /> (<span class="keyword">let</span> ((table (copy-seq *ascii-table*)))<br /> (<span class="keyword">loop</span><br /> for from-char across from-table<br /> and to-char across to-table<br /> do (setf (aref table (char-code from-char)) to-char))<br /> (<span class="keyword"><span class="slime-highlight">lambda</span></span> (string)<br /> (<span class="keyword">declare</span> ((simple-array character) string))<br /> (map-into string<br /> #'(<span class="keyword">lambda</span> (c) (aref table (char-code c)))<br /> string))))<br /><br />(<span class="keyword">defparameter</span> <span class="variable-name">*soundex-tr-fn*</span> (make-tr-fn <span class="string">"AEHIOUWYBFPVCGJKQSXZDTLMNR"</span> <span class="string">"00000000111122222222334556"</span>))<br /><br />(<span class="keyword">defun</span> <span class="function-name">soundex-tr</span> (string)<br /> (funcall *soundex-tr-fn* string))</pre>This is an example of the sort of rote transformations you often need to do in order to speed up performance.<ol><li>Separate out the part of the function that varies dynamically into a <b><a href="http://www.lisp.org/HyperSpec/Body/mac_lambda.html">LAMBDA</a></b>.<br /> </li><li>Return the <b>LAMBDA</b> instead of the original value so that it can be reused over and over again.<br /></li></ol>This is something you often do in Java, too, where the pattern goes:<ol><li>Create a class.</li><li>Have the constructor do the stuff that only needs to happen once (equivalent to the part outside of the <b>LAMBDA</b>.)</li><li>Create a method that does the dynamic part.</li></ol>The main difference the CL and Java is that the Java would be more verbose.<br /><br />You may notice another difference between <b>MAKE-TR-FN</b> and <b>TR</b>; it's now calling <b><a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_map_in.htm">MAP-INTO</a></b> instead of <b><a href="http://www.lisp.org/HyperSpec/Body/fun_map.html">MAP</a></b>, which avoids making a copy of the result, thus reducing the memory consumption further. Now this particular optimization <i>does</i> change the semantics of the function to modify its argument. In this case it's ok because we've already made a copy of the string passed to <b>SOUNDEX</b>, but do not use this technique without thinking through the consequences. Also, the <b><a href="http://www.lisp.org/HyperSpec/Body/sym_declare.html">DECLARE</a></b> statement fixes a minor compiler warning caused by the change. <b>DECLARE</b> is discussed later.<br /><br />When originally doing this work, I re-ran <b>PROFILE-SOUNDEX</b> after making each change, to see if it helped. That is not shown here in order to save space, but obviously you'd want to do the same thing. Let's now move on to the next biggest offender in the list, <b>CONCATENATE</b>. It's called towards the end of <b>SOUNDEX</b> in order to ensure that the return value is at least 4 characters (right-padded with '0' characters). This was a direct port of the Perl code (or at least as direct as you can get without using CL-PPCRE), and it's inefficient. Since the return value is <i>always</i> a 4-character string, we need only allocate a fixed-size string (using <b><a href="http://www.lisp.org/HyperSpec/Body/fun_make-string.html">MAKE-STRING</a></b>), prefilled with '0', and then copy in the (up to) 4 characters we need. We no longer need <b>SUBSEQ</b> which allocates a copy of its result (note: most of the memory consumed by <b>SUBSEQ</b> comes from it being called by <b>UNIQ!</b>).<br /><br />In fact, since <b>SUBSEQ</b> is next on our list of memory hogs, let's find a way to fix it. When <b>UNIQ!</b> calls it, it's operating on a so-called "garbage" sequence (<b>S2</b> from <b>SOUNDEX</b>); i.e., an intermediate result that is not used outside of the bowels of <b>SOUNDEX</b>. As such, we <i>could</i> modify it, so it is a shame to use <b>SUBSEQ</b> on it within <b>UNIQ!</b>. CL has a loosely-followed convention that "destructive" (non-copying) version of functions begin with the letter <i>N</i>. There is no built-in <b>NSUBSEQ</b> but a quick Google search finds one that works for our purposes:<pre class="code"><span class="comment-delimiter">;; </span><span class="comment">From http://darcs.informatimago.com/lisp/common-lisp/utility.lisp<br /></span>(<span class="keyword">defun</span> <span class="function-name">nsubseq</span> (sequence start <span class="type">&optional</span> (end nil))<br /> <span class="doc">"<br />RETURN: When the SEQUENCE is a vector, the SEQUENCE itself, or a displaced<br /> array to the SEQUENCE.<br /> When the SEQUENCE is a list, it may destroy the list and reuse the<br /> cons cells to make the subsequence.<br />"</span><br /> (<span class="keyword">if</span> (vectorp sequence)<br /> (<span class="keyword">if</span> (and (zerop start) (or (null end) (= end (length sequence))))<br /> sequence<br /> (make-array (- (<span class="keyword">if</span> end<br /> (min end (length sequence))<br /> (length sequence))<br /> start)<br /> <span class="builtin">:element-type</span> (array-element-type sequence)<br /> <span class="builtin">:displaced-to</span> sequence<br /> <span class="builtin">:displaced-index-offset</span> start))<br /> (<span class="keyword">let</span> ((result (nthcdr start sequence)))<br /> (<span class="keyword">when</span> end<br /> (setf (cdr (nthcdr (- end start -1) sequence)) nil))<br /> result)))</pre>We'll call this from <b>UNIQ!</b> and that should take care of that 10MB of allocations. The last bit of memory we're going to take care of is that allocated by <b>STRING-UPCASE</b> and <b>REMOVE-IF-NOT</b>. Now we have to be careful here because we <i>want</i> one copy of the argument to <b>SOUNDEX</b>; it would be rude to transform the caller's argument unexpectedly. So we actually <i>relying</i> on either <b>STRING-UPCASE</b> or <b>REMOVE-IF-NOT</b> making a copy of <b>STRING</b>. As such, we have to pick one to optimize. Since <b>REMOVE-IF-NOT</b> has a destructive equivalent, <b>DELETE-IF-NOT</b>, we will use that instead. Unfortunately, it's not as simple as just dropping in <b>DELETE-IF-NOT</b>. If you read the <a href="http://www.lisp.org/HyperSpec/Body/fun_string-up_g-capitalize.html">CLHS entry</a> you'll discover that <b>STRING-UPCASE</b> is allowed to return the same string it was passed in (i.e., <i>not</i> a copy) if it doesn't need to change it (e.g., all the letters are already uppercase). We account for this by calling <b>REMOVE-IF-NOT</b> in the case where <b>STRING-UPCASE</b> does this by seeing if the return value is <b><a href="http://www.lisp.org/HyperSpec/Body/fun_eq.html">EQ</a></b> (same object) to the original string. You can see this in the new code listing, which has certain key optimizations highlighted for your convenience:<pre class="code">(<span class="keyword">defparameter</span> <span class="variable-name">*ascii-table*</span> (<span class="keyword">let</span> ((table (make-array '(256) <span class="builtin">:element-type</span> 'character)))<br /> (<span class="keyword">loop</span><br /> for i below 256<br /> do (setf (aref table i) (code-char i)))<br /> table))<br /><br />(<span class="keyword">defun</span> <span class="function-name">make-tr-fn</span> (from-table to-table)<br /> (<span class="keyword">let</span> ((table (copy-seq *ascii-table*)))<br /> (<span class="keyword">loop</span><br /> for from-char across from-table<br /> and to-char across to-table<br /> do (setf (aref table (char-code from-char)) to-char))<br /> (<span class="keyword">lambda</span> (string)<br /> (<span class="keyword">declare</span> ((simple-array character) string))<br /> (map-into string<br /> #'(<span class="keyword">lambda</span> (c) (aref table (char-code c)))<br /> string))))<br /><br />(<span class="keyword">defparameter</span> <span class="variable-name">*soundex-tr-fn*</span> (make-tr-fn <span class="string">"AEHIOUWYBFPVCGJKQSXZDTLMNR"</span> <span class="string">"00000000111122222222334556"</span>))<br /><br />(<span class="keyword">defun</span> <span class="function-name">soundex-tr</span> (string)<br /> (funcall *soundex-tr-fn* string))<br /><br />(<span class="keyword">defun</span> <span class="function-name">uniq!</span> (seq)<br /> (<span class="keyword">cond</span><br /> ((> (length seq) 1)<br /> (<span class="keyword">do*</span> ((cur 0)<br /> (cur-elt (elt seq cur) (elt seq cur))<br /> (next 1 (1+ next)))<br /> ((>= next (length seq)) (<span class="slime-highlight">nsubseq</span> seq 0 (1+ cur)))<br /> (<span class="keyword">let</span> ((next-char (elt seq next)))<br /> (<span class="keyword">unless</span> (eql cur-elt next-char)<br /> (incf cur)<br /> (setf (elt seq cur) next-char)))))<br /> (t seq)))<br /><br />(<span class="keyword">defun</span> <span class="function-name">soundex</span> (string)<br /> (<span class="keyword">let</span> ((s (<span class="keyword">let</span> ((maybe-a-copy (string-upcase string)))<br /> <span class="comment-delimiter">;; </span><span class="comment">STRING-UPCASE can return original string if no changes<br /></span> <span class="comment-delimiter">;; </span><span class="comment">were needed.<br /></span> (<span class="keyword">if</span> (<span class="slime-highlight">eq</span> maybe-a-copy string)<br /> <span class="comment-delimiter">;; </span><span class="comment">REMOVE-IF-NOT makes a copy<br /></span> (remove-if-not 'alpha-char-p maybe-a-copy)<br /> <span class="comment-delimiter">;; </span><span class="comment">DELETE-IF-NOT doesn't<br /></span> (<span class="slime-highlight">delete-if-not</span> 'alpha-char-p maybe-a-copy)))))<br /> (<span class="keyword">when</span> (plusp (length s))<br /> (<span class="keyword">let</span> ((f (char s 0)))<br /> (<span class="keyword">let*</span> ((s2 (soundex-tr s))<br /> (fc (char s2 0))<br /> (result (<span class="slime-highlight">make-string</span> 4 <span class="builtin">:initial-element</span> #\0)))<br /> (setf s2 (delete #\0 (uniq! (string-left-trim (vector fc) s2))))<br /> (setf (char result 0) f)<br /> (<span class="keyword">loop</span><br /> for i from 0 below (min (length s2) 4)<br /> do (setf (char result (1+ i)) (char s2 i)))<br /> result)))))<br /></pre>As mentioned above, in the course of actually doing this work I ran <b>PROFILE-SOUNDEX</b> many times, but I don't show the intermediate results here in order to save space. Now that we've completed a major chunk of work, however, let's see how we're doing:<pre class="code"><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(many-soundex)</span><br /><div class="codepop"><span class="slime-repl-output">Evaluation took:<br /> 0.464 seconds of real time<br /> 0.460029 seconds of user run time<br /> 0.0 seconds of system run time<br /> [Run times include 0.008 seconds GC run time.]<br /> 0 calls to %EVAL<br /> 0 page faults and<br /> 22,402,176 bytes consed.<br /></span></div></pre>We run <b>MANY-SOUNDEX</b> here in a fresh instance of SBCL to remove any injected profiling code or other stuff that might affect the results. It also has speed optimizations turned on. As you can see, the benefit of simply removing memory allocations is significant. The new code is a whopping 4.4 times faster! It's also now more than twice as fast as the Perl code.<br /><br />We could continue to to whittle away at the memory allocation, as you can see we're still at around 21MB of memory allocated. However, since we have to copy the argument to <b>SOUNDEX</b> no matter what, 21MB is only about twice the minimum (if you look at the profiling results, we can't do better than the memory allocated by <b>STRING-UPCASE</b>). To keep this blog entry to a reasonable length we shall deem this acceptable.<br /><br />On to CPU optimization. SBCL automatically detects certain performance problems when you up <b>SPEED</b> to 3. Fix these first, as it makes little sense to manually search out problems when the compiler has already found some. Using SLIME makes it easy:<ol><li>Put <pre class="code">(<span class="keyword">declaim</span> (optimize (speed 3) (debug 0) (safety 0)))</pre> at the top of the file.</li><li>Type <b>C-c C-k</b> to compile the file.</li><li>Hit <b>M-n</b> and <b>M-p</b> to get SLIME to highlight the next (or previous) compiler warning.</li></ol>I won't go through all of the compiler warnings I got when I did this, but instead will highlight some of them.<pre class="code">(<span class="keyword">defun</span> <span class="function-name">soundex-tr</span> (string)<br /> <span class="slime-note">(funcall *soundex-tr-fn* string)</span>)<br /><div class="codepop">; note: unable to<br />; optimize away possible call to FDEFINITION at runtime<br />; due to type uncertainty:<br />; The first argument is a (OR FUNCTION SYMBOL), not a FUNCTION.</div></pre>This example seems a little strange at first, if, say, you're used to primitive type systems such as Java's. CL types can be defined in sophisticated ways that deserve a blog entry of their own. In this particular case, the compiler has inferred the type of <b>*SOUNDEX-TR-FN*</b> to be <b>(OR FUNCTION SYMBOL)</b>, meaning it isn't sure if it could sometimes be null (figuring that out would require "global" analysis to ensure that <b>*SOUNDEX-TR-FN*</b> is never modified by any function anywhere, which is still, apparently, beyond the scope of most compilers). We can fix the warning with a <b><a href="http://www.lisp.org/HyperSpec/Body/speope_the.html">THE</a></b> expression. <b>THE</b> is one of CL's ways of adding manual static typing (which you may be familiar with from more primitive languages such as Java) into your code. Although CL implementations such as SBCL perform <a href="http://en.wikipedia.org/wiki/Type_inference">type inference</a>, the compiler occasionally needs your help:<pre class="code">(funcall (<span class="keyword">the</span> function *soundex-tr-fn*) ...)</pre>Since we're sure that <b>*SOUNDEX-TR-FN*</b> is effectively constant (it's all private code under our own control, after all), it is safe to add in this <b>THE</b>.<br /><br />Another interesting set of warnings comes from <b>NSUBSEQ</b>:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">nsubseq</span> (sequence start <span class="type">&optional</span> (end nil))<br /> (<span class="keyword">if</span> (vectorp sequence)<br /> (<span class="keyword">if</span> (and <span class="slime-note">(zerop start)</span> (or (null end) <span class="slime-note">(= end (length sequence))</span>))<br /> sequence<br /> (make-array (<span class="slime-note">-</span> (<span class="keyword">if</span> end<br /> <span class="slime-note">(min end (length sequence))</span><br /> (length sequence))<br /> start)<br /> <span class="builtin">:element-type</span> (array-element-type sequence)<br /> <span class="builtin">:displaced-to</span> sequence<br /> <span class="builtin">:displaced-index-offset</span> start))<br /> (<span class="keyword">let</span> ((result (nthcdr start sequence)))<br /> (<span class="keyword">when</span> end<br /> (setf (cdr (nthcdr <span class="slime-note">(- end start -1)</span> sequence)) nil))<br /> result)))<div class="codepop">; in: DEFUN NSUBSEQ<br />; (ZEROP START)<br />; ==><br />; (= START 0)<br />;<br />; note: unable to<br />; open-code FLOAT to RATIONAL comparison<br />; due to type uncertainty:<br />; The first argument is a NUMBER, not a FLOAT.<br />;<br />; note: unable to<br />; optimize<br />; due to type uncertainty:<br />; The first argument is a NUMBER, not a (COMPLEX SINGLE-FLOAT).<br />;<br />; note: unable to<br />; optimize<br />; due to type uncertainty:<br />; The first argument is a NUMBER, not a (COMPLEX DOUBLE-FLOAT).<br />...blah blah blah...</div></pre>Those warnings go on for a while. What they all boil down to, though, is that the compiler doesn't know the type of <b>START</b> or <b>END</b>. Now here is a key point. Should you find yourself in this sort of situation, always remember what the great computer scientist Igor Stravinsky once said, "Lesser artists borrow, great artists steal." In other words, don't try to figure out the type declarations; steal them from SBCL. Using SLIME makes this easy. Just type <b>M-.</b> and then type <b>SUBSEQ</b>, because obviously it should take the same parameters. This will take you to the source code (you should always have the SBCL source code handy) for <b>SUBSEQ</b>:<pre class="code"><span class="secondary-selection">(</span><span class="keyword">defun</span> <span class="function-name">subseq</span> (sequence start <span class="type">&optional</span> end)<br /> #!+sb-doc<br /> <span class="string">"Return a copy of a subsequence of SEQUENCE starting with element number<br /> START and continuing to the end of SEQUENCE or the optional END."</span><br /> (seq-dispatch sequence<br /> (list-subseq* sequence start end)<br /> (vector-subseq* sequence start end)<br /> (sb!sequence:subseq sequence start end))<span class="secondary-selection">)</span></pre>Since we only care about the vector case here, move the cursor to <b>VECTOR-SUBSEQ*</b> and hit <b>M-.</b> again, to see how it declares its arguments:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">vector-subseq*</span> (sequence start end)<br /> (<span class="keyword">declare</span> (type vector sequence))<br /> (<span class="keyword">declare</span> (type index start)<br /> (type (or null index) end))<br /> ;; blah blah blah</pre>Ah! So what is the type <b>INDEX</b>? Use <b>M-.</b> once more and you'll discover this:<pre class="code">(def!type index () `(integer 0 (,sb!xc:array-dimension-limit)))</pre>This makes sense. The type obviously has to be an integer, cannot be negative, and cannot be more than the maximum array length allowed by your CL implementation. This particular type definition is internal to SBCL and cannot be used directly, but we create our own. Improved <b>NSUBSEQ</b> looks like:<pre class="code">(<span class="slime-highlight"><span class="keyword">deftype</span> <span class="type">index</span></span> () `(integer 0 ,array-dimension-limit))<br /><br /><span class="comment-delimiter">;; </span><span class="comment">From http://darcs.informatimago.com/lisp/common-lisp/utility.lisp<br /></span>(<span class="keyword">defun</span> <span class="function-name">nsubseq</span> (sequence start <span class="type">&optional</span> (end nil))<br /> (<span class="keyword">if</span> (vectorp sequence)<br /> (<span class="slime-highlight"><span class="keyword">locally</span><br /> (<span class="keyword">declare</span> (index start)<br /> ((or null index) end))</span><br /> (<span class="keyword">if</span> (and (zerop start) (or (null end) (= end (length sequence))))<br /> sequence<br /> (make-array (- (<span class="keyword">if</span> end<br /> (min end (length sequence))<br /> (length sequence))<br /> start)<br /> <span class="builtin">:element-type</span> (array-element-type sequence)<br /> <span class="builtin">:displaced-to</span> sequence<br /> <span class="builtin">:displaced-index-offset</span> start)))<br /> (<span class="keyword">let</span> ((result (nthcdr start sequence)))<br /> (<span class="keyword">when</span> end<br /> (setf (cdr (nthcdr (- end start -1) sequence)) nil))<br /> result)))</pre>Note we use <a href="http://www.lisp.org/HyperSpec/Body/speope_locally.html"><b>LOCALLY</b></a> only when the argument is actually a vector; we can't make the same assumptions about other types of sequences. Plus we don't care about the list case (in fact a compiler warning for that case remains, but since we're not using lists in this example we'll skip the fix for it).<br /><br />Let's look at optimizing <b>UNIQ!</b>. When we compile it, we get a number of warnings such as:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">uniq!</span> (seq)<br /> (<span class="keyword">cond</span><br /> ((> <span class="slime-note">(length seq)</span> 1)<br /> (<span class="keyword">do*</span> ((cur 0)<br /> (cur-elt <span class="slime-note">(elt seq cur)</span> <span class="slime-note">(elt seq cur)</span>)<br /> (next 1 (1+ next)))<br /> ((>= next <span class="slime-note">(length seq)</span>) (nsubseq seq 0 (1+ cur)))<br /> (<span class="keyword">let</span> ((next-char <span class="slime-note">(elt seq next)</span>))<br /> (<span class="keyword">unless</span> <span class="slime-note">(eql cur-elt next-char)</span><br /> (incf cur)<br /> <span class="slime-note">(setf (elt seq cur) next-char)</span>))))<br /> (t seq)))<div class="codepop">; in: DEFUN UNIQ!<br />; (LENGTH SEQ)<br />;<br />; note: unable to<br />; optimize<br />; due to type uncertainty:<br />; The first argument is a SEQUENCE, not a (SIMPLE-ARRAY * (*)).<br />;<br />; note: unable to<br />; optimize<br />; due to type uncertainty:<br />; The first argument is a SEQUENCE, not a VECTOR.<br /><br />; (ELT SEQ CUR)<br />;<br />; note: unable to<br />; optimize<br />; due to type uncertainty:<br />; The first argument is a SEQUENCE, not a (SIMPLE-ARRAY * (*)).<br />...blah blah blah...</div></pre>Here the compiler is telling us that it could make some optimizations if it knew for sure that the <b>SEQ</b> were a <b><a href="http://www.lispworks.com/documentation/HyperSpec/Body/t_smp_ar.htm">SIMPLE-ARRAY</a></b>. What the heck is a simple array? Clicking link (or using <b>C-c C-d h</b> in SLIME), shows: <blockquote>The type of an array that is not displaced to another array, has no fill pointer, and is not<br />expressly adjustable is a subtype of type simple-array. The concept of a simple array exists to<br />allow the implementation to use a specialized representation and to allow the user to declare that<br />certain values will always be simple arrays.</blockquote>In case you're wondering, "displaced" means an array slice (as in Perl or Python), and the other two concepts refer to various ways an array can be (or appear to be) extensible. Is it safe for <b>UNIQ!</b> to assume it is receiving a simple array? Yes; its input comes from <b>STRING-LEFT-TRIM</b>. Although <b>STRING-LEFT-TRIM</b> <i>is</i> allowed to return its input when there are no changes to be made, we know that it will <i>always</i> make a change because we always remove at least the first character of <b>S2</b>, and thus its return value will always be simple. So let's add a function declaration for <b>UNIQ!</b>:<pre class="code">(<span class="keyword">declaim</span> (ftype (function (simple-array) string) uniq!))</pre>This tells the compiler that <b>UNIQ!</b>'s single argument is a <b>SIMPLE-ARRAY</b> and that it returns a <b>STRING</b>. The reason we say it returns a <b>STRING</b> (instead of a "simple" sequence type) is that <b>UNIQ!</b> uses <b>NSUBSEQ</b>, which <i>does</i> return an array slice. Unfortunately, we still get compiler warnings after making this change (albeit fewer):<pre class="code"> (cur-elt <span class="slime-note">(elt seq cur)</span> <span class="slime-note">(elt seq cur)</span>)<div class="codepop">; note: unable to<br />; optimize<br />; due to type uncertainty:<br />; The first argument is a (SIMPLE-ARRAY * (*)), not a SIMPLE-STRING.<br />...blah blah blah...<br /></div></pre>This is telling us that it could generate better code if it knew the sequence was a string. <b><a href="http://www.lisp.org/HyperSpec/Body/acc_elt.html">ELT</a></b> is a generic accessor that works on any sequence type; presumably if the compiler knows the sequence type is a string it can take advantage of the fact that each element is the same size. Anyway, this is easy to fix. <b>SOUNDEX</b> only deals in strings, so we can safely change the declaration from <b>SIMPLE-ARRAY</b> to <b>SIMPLE-STRING</b>. Sure enough, this makes the compiler warnings disappear.<br /><br />The remaining changes made were generally of the same nature as the above so are not covered here in detail, but you can see them in the following complete code listing that highlights all the CPU-related changes:<pre class="code">(<span class="keyword">declaim</span> (optimize (speed 3) (debug 0) (safety 0)))<br /><br />(<span class="keyword">defparameter</span> <span class="variable-name">*ascii-table*</span> (<span class="keyword">let</span> ((table (make-array '(256) <span class="builtin">:element-type</span> 'character)))<br /> (<span class="keyword">loop</span><br /> for i below 256<br /> do (setf (aref table i) (code-char i)))<br /> table))<br /><span class="slime-highlight"><br /></span>(<span class="keyword">defun</span> <span class="function-name">make-tr-fn</span> (from-table to-table)<br /><span class="slime-highlight"> (declare (simple-string from-table to-table)<br /> (simple-array *ascii-table*))<br /> (let ((table (the (simple-array character) (copy-seq *ascii-table*))))<br /></span> (<span class="keyword">loop</span><br /> for from-char across from-table<br /> and to-char across to-table<br /> do (setf (aref table (char-code from-char)) to-char))<br /> (<span class="keyword">lambda</span> (string)<br /> (<span class="keyword">declare</span> ((simple-array character) string))<br /> (map-into string<br /> #'(<span class="keyword">lambda</span> (c) (aref table (char-code c)))<br /> string))))<br /><br />(<span class="keyword">defparameter</span> <span class="variable-name">*soundex-tr-fn*</span> (make-tr-fn <span class="string">"AEHIOUWYBFPVCGJKQSXZDTLMNR"</span> <span class="string">"00000000111122222222334556"</span>))<br /><br /><span class="slime-highlight">(declaim (ftype (function (simple-string) simple-string) soundex-tr))<br /></span>(<span class="keyword">defun</span> <span class="function-name">soundex-tr</span> (string)<br /><span class="slime-highlight"> (funcall (the function *soundex-tr-fn*) string))<br /><br />(deftype index () `(integer 0 ,array-dimension-limit))<br /></span><br /><span class="comment-delimiter">;; </span><span class="comment">From http://darcs.informatimago.com/lisp/common-lisp/utility.lisp<br /></span>(<span class="keyword">defun</span> <span class="function-name">nsubseq</span> (sequence start <span class="type">&optional</span> (end nil))<br /> <span class="doc">"<br />RETURN: When the SEQUENCE is a vector, the SEQUENCE itself, or a displaced<br /> array to the SEQUENCE.<br /> When the SEQUENCE is a list, it may destroy the list and reuse the<br /> cons cells to make the subsequence.<br />"</span><br /> (<span class="keyword">if</span> (vectorp sequence)<br /><span class="slime-highlight"> (locally<br /> (declare (index start)<br /> ((or null index) end))</span><br /> (if (and (zerop start) (or (null end) (= end (length sequence))))<br /> sequence<br /> (make-array (- (if end<br /> (min end (length sequence))<br /> (length sequence))<br /> start)<br /> :element-type (array-element-type sequence)<br /> :displaced-to sequence<br /> :displaced-index-offset start)))<br /> (<span class="keyword">let</span> ((result (nthcdr start sequence)))<br /> (<span class="keyword">when</span> end<br /> (setf (cdr (nthcdr (- end start -1) sequence)) nil))<br /> result)))<br /><br /><span class="slime-highlight">(declaim (ftype (function (simple-string) string) uniq!))<br /></span>(<span class="keyword">defun</span> <span class="function-name">uniq!</span> (seq)<br /><span class="slime-highlight"> (let ((seq-len (length seq)))</span><br /> (cond<br /> ((> seq-len 1)<br /> (do* ((cur 0)<br /> (cur-elt (elt seq cur) (elt seq cur))<br /> (next 1 (1+ next)))<br /> ((>= next <span class="slime-highlight">seq-len</span>) (nsubseq seq 0 (1+ cur)))<br /> (let ((next-char (elt seq next)))<br /> (unless (eql cur-elt next-char)<br /> (incf cur)<br /> (setf (elt seq cur) next-char)))))<br /> (t seq))))<br />(<span class="keyword">defun</span> <span class="function-name">soundex</span> (string)<br /> (let ((s <span class="slime-highlight">(the simple-string</span><br /> (let ((maybe-a-copy (string-upcase string)))<br /> ;; STRING-UPCASE can return original string if no changes<br /> ;; were needed.<br /> (if (eq maybe-a-copy string)<br /> ;; REMOVE-IF-NOT makes a copy<br /> (remove-if-not 'alpha-char-p maybe-a-copy)<br /> ;; DELETE-IF-NOT doesn't<br /> (delete-if-not 'alpha-char-p maybe-a-copy))))))<br /> (<span class="keyword">when</span> (plusp (length s))<br /> (<span class="keyword">let</span> ((f (char s 0)))<br /> (<span class="keyword">let*</span> ((s2 (soundex-tr s))<br /> (fc (char s2 0))<br /> (result (make-string 4 <span class="builtin">:initial-element</span> #\0)))<br /> (setf s2 <span class="slime-highlight">(the string</span> (delete #\0 (uniq! (string-left-trim (vector fc) s2)))))<br /> (setf (char result 0) f)<br /><span class="slime-highlight"> (let ((end (min (length s2) 4)))</span><br /> (loop<br /> for i from 0 below <span class="slime-highlight">end</span><br /> do (setf (char result (1+ i)) (char s2 i))))<br /> result)))))</pre><br /><br />Here's the effect of the CPU optimizations:<pre class="code"><span class="slime-repl-prompt">CL-USER> </span><span class="slime-repl-input">(many-soundex)</span><br /><span class="slime-repl-output">Evaluation took:<br /> 0.357 seconds of real time<br /> 0.360022 seconds of user run time<br /> 0.0 seconds of system run time<br /> [Run times include 0.008 seconds GC run time.]<br /> 0 calls to %EVAL<br /> 0 page faults and<br /> 22,406,384 bytes consed.<br /></span></pre>Although the results vary from run to run, 0.357 seconds is a pretty typical on my hardware. This is approximately a 23% reduction in time compared to before. Not nearly as big of a gain, which is why one should optimize memory first. Still, 23% is nothing to sneeze at for a relatively small number of changes, most of which were pointed out to us by the compiler! If you're interested in learning more about optimizing CL, I recommend checking out SBCL's <b>SB-SPROF</b> package, which is more sophisticated than the <b>SB-PROFILE</b> package used here.Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com14tag:blogger.com,1999:blog-32049549.post-79157193937872540122008-02-12T21:29:00.000-08:002008-03-29T12:46:22.659-07:00Scripting in CL<a href="http://en.wikipedia.org/wiki/Common_Lisp">CL</a> has been overlooked as a scripting language, even though scripting in CL is faster than it is in traditional scripting languages. CL's interactivity and macro system make it ideal for quick-and-dirty hacking.<br /><br />For one thing, its syntax is so simple that almost anything can be typed in at the CL command-line:<br /><pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">23</span><br /><div class="codepop">23</div></pre>That's a valid CL "program". It returns 23. So say that you forgot how part of the language works; resolve the problem by typing some test code at the command-line without breaking your concentration. For example, say you forget how division works in CL; you may have forgotten whether CL has support for rationals. Don't look it up, just try it out immediately:<br /><pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(/ 23 45)</span><br /><div class="codepop">23/45</div></pre>Sure enough, it doesn't return a float! This interactivity isn't just useful for exploring (or remembering) basic language features. It's also how you script in CL. <br /><br />For example, here is how to write a CL version of the popular Unix utility <a href="http://en.wikipedia.org/wiki/Grep">grep</a>, which you might then use as the basis for a log analyzer or some other script. Start by working interactively on a small part of the problem, such as how to see if a string contains a regexp. Of course our goal is to pick lines out of a file, but let's ignore the file part for now, we have to walk before we run. First define some sample data:<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(defparameter *lines* "hi there<br />my name is bob<br />I live in Kalamazoo")</span></pre>Now google for how to use regular expressions in CL. All roads lead to <a href="http://www.weitz.de/cl-ppcre/">CL-PPCRE</a>. To install it, do this:<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(require :asdf-install)</span> ; if you haven't already<br /><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(asdf-install:install :cl-ppcre)</span> ; if you don't have it already<br /></pre>To use it, do this:<br /><pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(require :cl-ppcre)</span><br /><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(use-package :cl-ppcre)</span> ; to save typing cl-ppcre: a lot<br /></pre>Next use <a href="http://common-lisp.net/project/slime/">SLIME</a>'s autocomplete to figure out what functions are available:<br /><pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(cl-ppcre:<span class="slime-highlight"><TAB></span></span><br /><div class="codepop">Flags: boundp fboundp generic-function class macro special-operator package<br /><br />Completion: Flags: Score:<br />---------------------------------- ------- --------<br /><span class="bold">cl-ppcre</span>: b------ 98.44<br /><span class="bold">cl-ppcre</span>-test: b------ 90.11<br /><span class="bold">cl-ppcre</span>:*allow-named-registers* b------ 0.98<br /><span class="bold">cl-ppcre</span>:*allow-quoting* b------ 0.98<br /><span class="bold">cl-ppcre</span>:*regex-char-code-limit* b------ 0.98<br /><span class="bold">cl-ppcre</span>:*use-bmh-matchers* b------ 0.98<br /><span class="bold">cl-ppcre</span>:all-matches -f----- 0.98<br /><span class="bold">cl-ppcre</span>:all-matches-as-strings -f----- 0.98<br /><span class="bold">cl-ppcre</span>:create-scanner -fg---- 0.98<br /><span class="bold">cl-ppcre</span>:define-parse-tree-synonym -f--m-- 0.98<br /><span class="bold">cl-ppcre</span>:do-matches -f--m-- 0.98<br /><span class="bold">cl-ppcre</span>:do-matches-as-strings -f--m-- 0.98<br /><span class="bold">cl-ppcre</span>:do-register-groups -f--m-- 0.98<br /><span class="bold">cl-ppcre</span>:do-scans -f--m-- 0.98<br /><span class="bold">cl-ppcre</span>:parse-tree-synonym -f----- 0.98<br /><span class="bold">cl-ppcre</span>:ppcre-error ---c--- 0.98<br />...etc...<br /></div></pre>Although this technique may seem haphazard, in practice one finds what one wants in about a minute or two (at most), typically without losing one's concentration. Most of the functions can be trivially filtered out simply based on their names (e.g., <b>PARSE-TREE-SYNONYM</b> is obviously not what I'm looking for). Of the rest, you can either quickly check their documentation (<span style="font-weight:bold;">C-c C-d d</span> if you're using SLIME) or else, heck, just try them out immediately. In this particular case I settled on <b>SCAN</b>.<br /><pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(scan "Kalamazoo" *line*)</span><br /><div class="codepop">34<br />43<br />#()<br />#()</div></pre>It doesn't matter what those return values mean (probably the offset of the match is in there somewhere), the key point is that <span style="font-weight:bold;">SCAN</span> would have returned <span style="font-weight:bold;">NIL</span> if there hadn't been a match. Or so we hope. We had better verify that (quickly; <i>don't look at the documentation</i>, just try it!):<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(scan "snord" *line*)</span><br /><div class="codepop">NIL</div></pre><br />Ok, now how do we read in a line from a file? Well, first we have to open the file:<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(open "/etc/motd")</span><br /><div class="codepop">#<SB-SYS:FD-STREAM for "file /etc/motd" {A78C2E9}></div></pre>That looks promising. A little more research on Google shows that it's best to use <a href="http://www.lisp.org/HyperSpec/Body/mac_with-open-file.html">WITH-OPEN-FILE</a> because that will automatically close the file (even if an exception is thrown).<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(with-open-file (stream "/etc/motd"))</span><br /><div class="codepop">NIL</div></pre>How do you read a line from a file? Turns out there's a function <a href="http://www.lisp.org/HyperSpec/Body/fun_read-line.html">READ-LINE</a>:<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(with-open-file (stream "/etc/motd") (read-line stream nil nil))</span><br /><div class="codepop">"Linux D830 2.6.22-14-generic #1 SMP Fri Feb 1 04:59:50 UTC 2008 i686"</div></pre>Ok, so we can read lines from a file, now what? Well, let's play around with the <a href="http://www.gigamonkeys.com/book/loop-for-black-belts.html">LOOP</a> macro to print out <span style="font-style:italic;">all</span> the lines of the file (don't worry about the regexp matching just yet):<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(defparameter *motd* (open "/etc/motd"))</span><br /><span class="slime-repl-result">*MOTD*</span><br /><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(loop for line = (read-line *motd* nil nil)<br /> while line<br /> do (format t "~A~%" line))</span><br /><div class="codepop">Linux D830 2.6.22-14-generic #1 SMP Fri Feb 1 04:59:50 UTC 2008 i686<br /><br />The programs included with the Ubuntu system are free software;<br />the exact distribution terms for each program are described in the<br />individual files in /usr/share/doc/*/copyright.<br /><br />Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by<br />applicable law.</div></pre>Ok, that worked. Now let's scan for all the lines that contain the word "Ubuntu".<pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(defparameter *motd* (open "/etc/motd"))</span><br /><span class="slime-repl-result">*MOTD*</span><br /><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(loop for line = (read-line *motd* nil nil)<br /> while line<br /> do (when (scan "Ubuntu" line)<br /> (format t "~A~%" line)))</span><br /><div class="codepop">The programs included with the Ubuntu system are free software;<br />Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by</div></pre>Ok, that looks good. Now let's write a function with everything we just did:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">grep</span> (regexp filename)<br /> (<span class="keyword">with-open-file</span> (stream filename)<br /> (<span class="keyword">loop</span> for line = (read-line stream nil nil)<br /> while line<br /> do (<span class="keyword">when</span> (scan regexp line)<br /> (format t <span class="string">"~A~%"</span> line)))))<br /><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(grep "Ubuntu" "/etc/motd")</span><br /><div class="codepop">The programs included with the Ubuntu system are free software;<br />Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by</div></pre>At this point you've seen what a typical CL scripting session is like, working from the bottom up.<br /><br />Now the above was a pretty simplistic example, and it used (apart from CL-PPCRE) good old fashioned CL, which hasn't changed since the mid-1980s. Since then, scripting languages like Perl have been invented by smart people like Larry Wall, having many built-in features that are missing from stock CL. Why suffer without them? It would seem that you have to either choose between a general-purpose, compiled language like CL or purpose-built, interpreted Perl. Fortunately, this is <i>not</i> the case! I've found that each piece of Perl functionality I've wanted has taken on the order of 45 minutes to 1 hour to implement using CL's powerful <a href="http://www.lisp.org/HyperSpec/Body/mac_defmacro.html">DEFMACRO</a> facility. <br /><br />Let's take, for example, Perl's magic <> operator. In Perl, you can write:<pre class="code">#!/usr/bin/env perl<br /># file: "foo.pl"<br /><br />for $line (<>) {<br /> print $line;<br />}</pre>Which will slurp up all the filenames on the command-line and let you iterate over each line. E.g.,<pre class="code">% foo.pl /etc/motd /etc/resolv.conf</pre>would print out those files, sort of like <a href="http://en.wikipedia.org/wiki/Cat_(Unix)">cat</a>. Wouldn't it be nice to have a similar feature in CL? Let's start by taking our <b>GREP</b> function and adding the ability to customize the action taken on each line:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">do-lines</span> (fn filename)<br /> (<span class="keyword">with-open-file</span> (stream filename)<br /> (<span class="keyword">loop</span> for line = (read-line stream nil nil)<br /> while line<br /> do (<span class="keyword">when</span> (scan regexp line)<br /> (funcall fn line)))))</pre><B>DO-LINES</B> is almost exactly the same as <B>GREP</B>, except that it just calls a function on each line of the file rather than assume grep-like behavior. To verify that we can implement <span style="font-weight:bold;">GREP</span> in terms of <span style="font-weight:bold;">DO-LINES</span> we try the following at the command-line:<br /><pre class="code"><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(do-lines (lambda (line)<br /> (when (scan "Ubuntu" line) (format t "~A~%" line))) "/etc/motd")</span><br /><div class="codepop">The programs included with the Ubuntu system are free software;<br />Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by</div></pre>Isn't that great? Baaaarf. Not really, eh? Kind of verbose compared to the Perl code, and it doesn't even handle multiple files like the Perl code does! <br /><br />What we'd <i>really</i> like to be able to do is something CL-esque yet approximately equal to the Perl code in brevity. This sounds like a good use for a CL macro. Let's start by just fantasizing about what we'd like:<pre class="code">(with-lines-from-files (line <span class="string">"/etc/motd"</span> <span class="string">"/etc/resolv.conf"</span>) <br /> (format t <span class="string">"~A~%"</span> line)) <span class="comment-delimiter">; </span><span class="comment">just a simple example, could put anything here</span></pre>Well, before going further, we need to enhance <span style="font-weight:bold;">DO-LINES</span> to take more than one file:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">do-all-lines</span> (fn <span class="type">&rest</span> filenames)<br /> (<span class="keyword">dolist</span> (filename-or-list filenames)<br /> <span class="comment-delimiter">;; </span><span class="comment">For convenience we allow you also to pass in lists of filenames<br /></span> (<span class="keyword">dolist</span> (filename (<span class="keyword">typecase</span> filename-or-list<br /> (cons filename-or-list)<br /> (t (list filename-or-list))))<br /> (<span class="keyword">with-open-file</span> (stream filename)<br /> (<span class="keyword">loop</span><br /> for line = (read-line stream nil nil)<br /> while line<br /> do (funcall fn line))))))</pre>Now we just need to write a macro so that you don't have to write all that crazy <span style="font-weight:bold;">LAMBDA</span> stuff:<pre class="code">(<span class="keyword">defmacro</span> <span class="function-name">with-lines-from-files</span> ((var <span class="type">&rest</span> filenames) <span class="type">&body</span> body)<br /> `(do-all-lines (<span class="keyword">lambda</span> (,var) ,@body) ,@filenames))</pre>Armed with this macro, we can re-write <span style="font-weight:bold;">GREP</span> with way fewer lines (and the ability to grep across multiple files):<pre class="code">(<span class="keyword">defun</span> <span class="function-name">grep</span> (regexp <span class="type">&rest</span> filenames)<br /> (with-lines-from-files (line filenames)<br /> (<span class="keyword">when</span> (scan regexp line)<br /> (format t <span class="string">"~A~%"</span> line))))<br /><span class="slime-repl-prompt">CL-USER></span> <span class="slime-repl-input">(grep "Ubuntu|name" "/etc/motd" "/etc/resolv.conf")</span><br /><div class="codepop">The programs included with the Ubuntu system are free software;<br />Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by<br />nameserver 68.87.69.146<br />nameserver 68.87.85.98</div></pre>If it weren't for macros, we'd be stuck implementing grep with the clunky use of <span style="font-weight:bold;">LAMBDA</span>:<pre class="code">(<span class="keyword">defun</span> <span class="function-name">clunky-grep</span> (regexp <span class="type">&rest</span> filenames)<br /> (do-all-lines (<span class="keyword">lambda</span> (line) <br /> (<span class="keyword">when</span> (scan regexp line) <br /> (format t <span class="string">"~A~%"</span> line)))<br /> filenames))</pre>The <span style="font-weight:bold;">LAMBDA</span>-free version of <span style="font-weight:bold;">GREP</span> is <i>much</i> easier to read, it almost reads like English: "with lines from the files, when lines scan the regexp, format the line". Whereas the <span style="font-weight:bold;">LAMBDA</span> version reads "with lines, LAMBDA (huh!!!?), when lines scan the regexp, format the line, across the filenames". No contest!<br /><br />Similarly, other Perl operations can be easily implemented with macros:<pre class="code"><span class="comment-delimiter">;; </span><span class="comment">The following macro is mostly like Perl's foreach, in the sense<br /></span><span class="comment-delimiter">;; </span><span class="comment">that you can pass in as many references to sequences or "scalars"<br /></span><span class="comment-delimiter">;; </span><span class="comment">as you want and it will iterate over them and allow you to modify<br /></span><span class="comment-delimiter">;; </span><span class="comment">them. Unlike the Perl code, it sets the variable IT to each<br /></span><span class="comment-delimiter">;; </span><span class="comment">element rather than $_. Also, you have to just pass in the hash<br /></span><span class="comment-delimiter">;; </span><span class="comment">table directly, not a flattened list of hash keys.<br /></span>(<span class="keyword">defmacro</span> <span class="function-name">perl-foreach</span> ((<span class="type">&rest</span> refs) <span class="type">&body</span> body)<br /> (<span class="keyword">let*</span> ((gensyms (<span class="keyword">loop</span> repeat (length refs) collect (gensym))))<br /> (list*<br /> 'let<br /> (mapcar #'list gensyms refs)<br /> (<span class="keyword">loop</span><br /> for ref in refs<br /> and indirect-ref in gensyms<br /> collect<br /> `(<span class="keyword">typecase</span> ,indirect-ref<br /> (hash-table <br /> (maphash #'(<span class="keyword">lambda</span> (key value)<br /> (<span class="keyword">declare</span> (ignore value))<br /> (<span class="keyword">symbol-macrolet</span> ((it (gethash key ,indirect-ref)))<br /> ,@body))<br /> ,indirect-ref))<br /> ((and (or vector list) (not string))<br /> (map-into ,indirect-ref<br /> #'(<span class="keyword">lambda</span> (it)<br /> ,@body<br /> it)<br /> ,indirect-ref))<br /> (t <br /> (<span class="keyword">symbol-macrolet</span> ((it ,ref))<br /> ,@body)))))))<br /><br /><span class="comment-delimiter">;; </span><span class="comment">trim whitespace in the scalar, the list, the array, and all the<br /></span><span class="comment-delimiter">;; </span><span class="comment">values in the hash<br /></span>(perl-foreach (scalar my-list my-array my-hash)<br /> (setf it (regex-replace <span class="string">"^\\s+"</span> it <span class="string">""</span>))<br /> (setf it (regex-replace <span class="string">"\\s+$"</span> it <span class="string">""</span>)))</pre>Or:<pre class="code">(<span class="keyword">defmacro</span> <span class="function-name">perl-splice</span> (sequence-place <span class="type">&optional</span> (offset 0) length replacement-sequence)<br /> (<span class="keyword">let*</span> ((seq (gensym <span class="string">"SEQUENCE-PLACE-"</span>))<br /> (off-arg (gensym <span class="string">"OFFSET-ARG-"</span>))<br /> (off (gensym <span class="string">"OFFSET-"</span>))<br /> (len (gensym <span class="string">"LENGTH-"</span>))<br /> (end (gensym <span class="string">"END-"</span>))<br /> (rep (gensym <span class="string">"REPLACEMENT-SEQUENCE-"</span>))<br /> (left-part (list `(subseq ,seq 0 ,off)))<br /> (right-part (<span class="keyword">when</span> length<br /> (list `(subseq ,seq ,end)))))<br /> `(<span class="keyword">let*</span> ((,seq ,sequence-place)<br /> (,off-arg ,offset)<br /> (,off (<span class="keyword">if</span> (minusp ,off-arg)<br /> (+ (length ,seq) ,off-arg)<br /> ,off-arg))<br /> (,len ,length)<br /> (,end (<span class="keyword">when</span> ,len<br /> (<span class="keyword">if</span> (minusp ,len)<br /> (+ (length ,seq) ,len)<br /> (+ ,off ,len))))<br /> (,rep ,replacement-sequence))<br /> (<span class="keyword">prog1</span> (subseq ,seq ,off ,end)<br /> (<span class="keyword">when</span> (or ,rep (not (eql ,off ,end)))<br /> (setf ,sequence-place (concatenate (<span class="keyword">typecase</span> ,seq<br /> (cons 'list)<br /> (t 'vector))<br /> ,@left-part<br /> ,rep<br /> ,@right-part)))))))<br /><br /><span class="comment-delimiter">;; </span><span class="comment">Now the syntax is almost exactly the same.<br /></span>(setf front (perl-splice my-array 0 n))<br />(setf end (perl-splice my-array 0 (- n)))</pre>Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com4tag:blogger.com,1999:blog-32049549.post-50595735513982499002007-11-06T21:23:00.000-08:002008-03-21T16:17:27.293-07:00Effective .emacs<span style="font-weight: bold;">Tip #0: Use Emacs 22</span><br />Emacs 22 is super stable. About half of my .emacs file (before I cleaned it up) was loading stuff that's now part of Emacs 22 and has autoloads.<br /><br /><span style="font-weight: bold;">Tip #1: Never quit Emacs</span><br />Okay, this has nothing to do with your .emacs file, but I have to put it in here. Just because your .emacs file should load quickly doesn't imply that you should quit and restart all the time. Figure it out!<br /><br /><span style="font-weight: bold;">Tip #2: (require 'cl)</span><br />I put this at the top of my .emacs. It's a no-brainer. It adds in a ton of compatibility with <a href="http://en.wikipedia.org/wiki/Common_Lisp">CL</a>, so that you can just use the CL functions you know and love (well, most of them, anyway), without a second thought.<br /><br /><span style="font-weight: bold;">Tip #3: Never LOAD, never REQUIRE</span><br />Your .emacs file shouldn't contain any calls to <span style="font-weight: bold;">LOAD </span>or <span style="font-weight: bold;">REQUIRE </span>(which are slow and often cause errors on startup). The only possible exceptions are loading files that contain nothing but autoloads (or similar stuff). How do you avoid loads and requires? First try removing each call to <span style="font-weight: bold;">LOAD </span>or <span style="font-weight: bold;">REQUIRE </span><span>to </span>see if it's needed at all. Often (e.g., if you follow <span style="font-weight: bold;">Tip #0</span>) Emacs already has autoloads in place for the library already (e.g., "cc-mode"). For other libraries, where that's not true, put your own autoloads in your .emacs file. For example, rather than load <a href="http://common-lisp.net/project/slime/">SLIME</a> in my .emacs (so I can bind the <span style="font-family:courier new;">F1 </span>key to <span style="font-weight: bold;">SLIME-SELECTOR</span>), instead I have:<pre class="code">(autoload 'slime-selector "slime" t)</pre>The only call to <span style="font-weight: bold;">LOAD </span>in my .emacs file is for "erlang-start", but if you look inside the file you can see it contains only autoloads (and morally equivalent stuff). I also load the custom file, but that's different, see <span style="font-weight: bold;">Tip #7</span>. I don't have a single call to <span style="font-weight: bold;">REQUIRE</span> (beyond that mandated by <span style="font-weight: bold;">Tip #2</span>).<br /><br /><span style="font-weight: bold;">Tip #4: Understand and use EVAL-AFTER-LOAD</span><br />Another reason why you might have strewn needless <span style="font-weight: bold;">REQUIRE</span> and <span style="font-weight: bold;">LOAD</span> calls throughout your .emacs file is that you need to call a function from a specific library. For example, let's say you want to set your default SQL database type to MySQL:<pre class="code">(sql-set-product 'mysql)</pre>If you put this in your .emacs, you'll get an error because the SQL library isn't loaded so <span style="font-weight: bold;">SQL-SET-PRODUCT</span> isn't yet defined. But before you add a <span style="font-weight: bold;">LOAD</span> or <span style="font-weight: bold;">REQUIRE</span>, stop! Instead do:<pre class="code">(eval-after-load "sql"<br /> '(progn<br /> (sql-set-product 'mysql)<br /> ;; any other config specific to sql<br /> ))</pre>As the name suggests, this will defer calling that code until the SQL module is actually loaded. This saves startup time <i>and</i> prevents errors!<br /><br /><span style="font-weight: bold;">Tip #5: Time your .emacs</span><br />You really ought to know how much time it's taking to load your .emacs file. Use the following in your .emacs:<pre class="code">(require 'cl) ; a rare necessary use of REQUIRE<br />(defvar *emacs-load-start* (current-time))<br /><br />;; rest of your .emacs goes here<br /><br />(message "My .emacs loaded in %ds" (destructuring-bind (hi lo ms) (current-time)<br /> (- (+ hi lo) (+ (first *emacs-load-start*) (second *emacs-load-start*)))))</pre>After Emacs finishing initializing, you can switch to the <span style="font-family:courier new;">*Messages*</span> buffer and see how much of that time was taken by loading your .emacs. Mine now contributes less than one second!<br /><br /><span style="font-weight: bold;">Tip #6: Set background colors</span><br />Don't just stand for the default colors! Set them to what you really want. In my case I want a reverse video effect:<pre class="code">(set-background-color "black")<br />(set-face-background 'default "black")<br />(set-face-background 'region "black")<br />(set-face-foreground 'default "white")<br />(set-face-foreground 'region "gray60")<br />(set-foreground-color "white")<br />(set-cursor-color "red")</pre><br /><span style="font-weight: bold;">Tip #7: Separate custom file</span><br />It's annoying to have your .emacs file modified by Emacs' "custom" library, especially if you check in your .emacs to a source code control system such as Subversion (which you should do) and synchronize it on multiple machines. Keep those customizations in a separate file:<pre class="code">(setq custom-file "~/.emacs-custom.el")<br />(load custom-file 'noerror)</pre>Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com16tag:blogger.com,1999:blog-32049549.post-86534117350176002062007-09-02T10:41:00.000-07:002008-03-21T16:38:07.325-07:00The Icarus UltimatumIt is unlikely that <i>every</i> programmer is familiar with <a href="http://en.wikipedia.org/wiki/Icarus">Icarus</a>, but I bet that almost all programmers have something in common with him. Programmers are saturated with advice <i>not</i> to do things, similar to the advice Icarus' dad gave him about aviation. Don't use threads unless you really know what you're doing (and then don't use them anyway.) Don't use new language features (they're too dangerous.) Use the "right tool for the right job" (i.e., not the one <i>you</i> like.) Don't "prematurely" optimize (note: it's <i>always</i> premature.) Don't use macros, nobody will be able to read your code. Don't use multiple inheritance. You ain't gonna need it (you dork!) Don't, don't, don't; no, No, NO! For the rest of this essay I will refer to such advice as "Dead" advice, in honor of Icarus' father, Daedalus (and also to honor my own lack of spelling ability.)<br /><br />Let's remember one thing about Icarus. Yes, he died a fiery, horrible death. But at the same time, he flew close to the freakin' <i>Sun</i>! How cool is that? Likewise, the most exciting developments in software have been <i>crazy stupid</i>. I remember how quixotic the notion that you could index and search the entire Internet (or even a significant part of it) once seemed. Only by thinking big does anything cool get done, it doesn't get done by sitting around pondering all the things you <i>shouldn't</i> be doing.<br /><br />Dead advice exists for many reasons, of course. Programming is so open-ended that it is easy to create unmaintainable, unreliable, slow software. Programs start out as a blank slate; one can do <i>anything</i>. Without discipline, <i>anything</i> turns into <i>unmitigated crap</i>. Thus experienced programmers observe mistakes (including their own) and, sometimes, craft memorable axioms as a result. Unfortunately, these well-intentioned rules-of-thumb often turn into blindly-followed commandments by the time they penetrate the consciousness of millions of programmers.<br />For example, the original advice about <a href="http://a-nickels-worth.blogspot.com/2007/08/proactive-optimization.html">premature optimization</a> has become twisted over the years, such that programmers are afraid ever to optimize lest their effort be labeled "premature". Similarly, Microsoft's infamous detour into Hungarian notation started with a <a href="http://www.joelonsoftware.com/articles/Wrong.html">misunderstood</a> paper by future astronaut Charles Simonyi. But this sort of telephone game isn't the only source of Dead advice.<blockquote>"It's not guns that kill people, It's these little hard things!"<br /> --- <i>the Flash from "The Trickster Returns"</i></blockquote>Sometimes Dead advice emerges not from a misinterpretation of the original advice but from a failure to perceive a problem's underlying cause. The treatment of threads in computer science illustrates this phenomenon well. Typical computer science programs teach little, if anything about threads; threads are an "implementation detail" with minor theoretical import (compared, say, to data structures, Big O, recursion, etc). What one <i>does</i> learn about them, though, makes them sound cool. Heck, let's face it, they <i>are</i> pretty darn cool. They're the expression of multitasking; a piece of magic. Junior programmers are disappointed when, on their first job, their mentors seem ready to pour boiling sulphuric acid on their keyboard if they so much as <i>mention</i> the possibility of using a thread. "My advice is not to use threads unless you're extremely experienced, a thread wizard, and even then don't use them." That's what they'll hear.<br /><br />I'm going to step out on a limb here, insert earplugs to drown out the chorus of "boos" that I can already hear even though nobody's read this post yet, and state: there's nothing wrong with using threads. This is a big reversal for me; I spread the <i><a href="http://home.pacbell.net/ouster/threads.pdf">threads are evil</a></i> gospel for many years. Yet I have confidence in this assertion for a number of reasons, foremost among them being that the admonitions <i>against</i> threads haven't helped much. How many applications have you used where the user interface freezes up every time the application does something that takes longer than a second or two? How many times have you found Cancel buttons (you know, those ones you're trying to hit when you realize you're accidentally deleting all of your un-backed-up files?) that take minutes to have any effect?<br /><br />If anti-thread prohibitions haven't worked, what would? I've been casually researching this issue for a long time. At first I decided, like many, that threads are indeed evil, and that <a href="http://en.wikipedia.org/wiki/Event-driven_programming">event-driven programming</a> was the <i>only</i> way to go (programmers love nothing more than a dichotomy.) When other programmers would point out to me that event-driven programming is, at times, a giant pain in the rear, I'd silently mark them as wimps. Finally, I read a series of papers, including <a href="http://www.usenix.org/events/usenix02/full_papers/adyahowell/adyahowell.pdf">this one</a>, that convinced me there was, at least, more to the story. Even more recently, someone clued me in to the <a href="http://erlang.org/">work</a> of <a href="http://www.sics.se/~joe/ericsson/">Joe Armstrong</a>, one of the only people outside of academia to have stepped back from the problem of threads and tackle, instead, <i>concurrency</i>, which was the <i>real</i> issue all along. By far the coolest thing Joe did was realize that you can in fact fly close to the Sun and spawn <i>as many darn "threads" as the problem you're solving truly warrants</i>. You can also use events, too, there having been, it turns out, no dichotomy between events and threads either.<br /><br />I found this revelatory after having wasted a lot of time, over the years, writing things like HTTP parsers in frameworks that either force you to use only events, or frameworks that let you spawn threads easily (though not necessarily efficiently) but have no standard event-passing mechanism. It's not just that I didn't think of it myself, it's that almost everyone I talked to about this sort of issue was either in the "threads are evil" camp or the "events are confusing" camp. I wasted a lot of time following bad advice.<br /><br />Experiences with Dead advice such as "threads are evil" have led me to question other Dead advice, such as:<ul><li>Premature optimization is the root of all evil.</li><br /><li>Never use multiple inheritance.</li><br /><li>YAGNI.</li><br /><li>Never use macros.</li></ul>Each of these have a kernel of truth to them, but are also too easily misunderstood and have not had the <i>overall</i> effect on programming that was originally intended. If I have some time I'll try to give more examples of each of the above. In the meantime, I do have to mention one piece of (arguably) Dead advice that I haven't found any fault with yet:<ul><li><a href="http://en.wikipedia.org/wiki/Don't_repeat_yourself">Don't repeat yourself</a>.<br /></ul>Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com2tag:blogger.com,1999:blog-32049549.post-32332425917313572292007-08-25T23:36:00.000-07:002007-08-26T00:32:50.607-07:00MacrophobiaAs a fledgling CL programmer, I've found macros to be one of its most enduring charms. Yet it is also one of its most criticized (or at least feared) features. Much like threads have become the bogeyman of the programming world, so macros would be too, if more than a handful of programmers actually knew about them. Among this handful, though, it would be nice to dispel the myth that macros are too powerful.<br /><br />I mean, obviously, they are, in some sense, too powerful. The common complaint about them is that junior programmers (especially) can create what appear to be language-level constructs that confuse the heck out of everyone else, impairing the code's "readability". As with most broadly-accepted maxims (in this case, broadly accepted by the 15 people in the world who actually know about the issue in the first place), it is both well-intended, intuitively reasonable, and incorrect, for the simple reason that if, at your company, junior programmers are running amok with no mentors to teach them, the code will be unreadable whether or not it uses macros.<br /><br />Frankly, I'd like to dispel the whole myth that there's great import to be placed on the "readability" of a programming language. I see blog after blog, each about as scientifically sound as my 10th grade Chemistry report (in case you're wondering, I'm not a chemist), about whether Perl is more readable than C, or vice-versa, or whether Python is more readable than CL, etc. This tiresome, endless debate stirs the fanboy in all of us, but is missing not just the forest for the trees, but the solar system for the planet.<br /><br />I've read a lot of code in my day, I'll have you know. What matters most to readability is, first, comments, followed by identifier names, followed by there being as little code as possible, followed by program structure. Ok, I can hear the chorus of "boos" in the background at the preceding statement. All I can say is, most programmers have no idea how to write good comments (even though, as they say, the "force" is with them; they just have no idea, and lack a Yoda-like figure to explain it to them). When comments are good, there is nothing quite like it. The code could be written in <a href="http://en.wikipedia.org/wiki/Text_Editor_and_Corrector">TECO</a> for all I care. Maybe blog, will I, about it, some day.<br /><br />So macros, in fact, cannot really get in the way of readability. In fact, they have the potential to greatly enhance readability, used judiciously (and as pointed out earlier, if your company is not run judiciously, you have larger issues to work out first). How many of you out there have worked somewhere that had some kind of coding guidelines? I'd warrant that a fair number of you have. I certainly have. I'm talking about stuff like <a href="http://www.doc.ic.ac.uk/lab/cplus/c++.rules/">Ellemtel's Programming in C++, Rules and Recommendations</a>.<br /><br />Give those rules a once-over, if you haven't already. It's pretty complicated stuff. Use this feature this way, use that feature that other way, don't do this, do do that, etc, etc. Yawn. I've worked at companies that successfully enforced such rules (at least 80% of the time), and some that failed utterly. In both cases, it was wickedly hard to enforce these rules (successfully or not). All programmers had to read the coding guidelines document, understand it, remember it, and periodically re-read it when it was updated. Senior programmers had to enforce the guidelines during code reviews (which was sometimes easier than other times, depending on the stubbornness of the reviewee).<br /><br />At more sophisticated shops, one could imagine, at least, that some of the rules would be enforced by build scripts. A poor solution if ever there was one. For one thing, build scripts tend to be written in a different language (e.g., Perl), and usually resort to crude regexp-matching in order to catch offending code. Only a handful of programmers at your company are brave (or foolish) enough to grok the build scripts. These poor souls find themselves, before too long, at the bottom of a pit of despair from which they never return (save by leaving for another team or company). Eventually they label themselves with self-deprecating monikers such as "build bitch".<br /><br />Macros afford the possibility, at least, that some of these conventions be enforced within the language itself, rather than by a bunch of hacky Perl scripts (or no automated process at all). Take, for instance, the use of CL's <a href="http://www.lisp.org/HyperSpec/Body/mac_defclass.html">DEFCLASS</a>. Now DEFCLASS has roughly one grillion options for how to do this, that, or the other thing. It's also remarkably lax about, well, almost everything. If you want a member variable ("slot") called FOO but wish for the accessor to it to be called BAR, you can do that. <br /><br />If you wanted to prevent such wanton creativity on the part of your less-trustworthy programmers, you could do so by writing a macro wrapping DEFCLASS which might both limit its complexity and enforce constraints such as the regular naming of accessors and the like. You could prevent the use of multiple inheritance if you found it too frightening (I'm not suggesting you go out and do this, just pointing out that you could). These rules would be enforce using code written in the same language as everything else, making them easier to write (in that they can harness the reflective power of the language itself, i.e., no hack regexps) and easier to find volunteers to maintain and develop.<br /><br />I could go on and on about this, but it's getting late so I'll just wrap it up there. One last thing, though, I urge the readers of this blog (all three of you) to re-evaluate the various maxims you may have assimilated over the years. Are threads really that bad if there is a problem facing you that is genuinely concurrent? Are you really <a href="http://a-nickels-worth.blogspot.com/2007/08/proactive-optimization.html">optimizing prematurely</a>? Is there really such thing as a "scripting language"? Should operating systems and programming languages keep each other at arm's length? The list goes on.Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com8tag:blogger.com,1999:blog-32049549.post-56963347304382124052007-08-24T23:58:00.000-07:002007-08-25T00:10:11.447-07:00Proactive OptimizationIn the programming world, one of the most widely repeated maxims is, "Premature optimization is the root of all evil." Having found this to be one of the most well-intended yet misunderstood pieces of advice in the history of the Universe, I was all set to write a blog about why. Unfortunately, for me, a quick trip to Wikipedia led me to this article: <a href="http://www.acm.org/ubiquity/views/v7i24_fallacy.html">The Fallacy of Premature Optimization</a>, by Randall Hyde, which said everything I intended to say, and more, and did so more eloquently that I could ever hoped to have (although I might have put in some better jokes).<br /><br />So the only thing I really have to add to that article is the following crude attempt at marketing: let's put a little spin on that phrase and turn it around! Whenever you hear "premature optimization is the root of all evil", retort (politely) with "but proactive optimization is the root of all goodness."Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com0tag:blogger.com,1999:blog-32049549.post-78976157348889272512007-06-17T13:16:00.000-07:002008-03-21T16:22:26.381-07:00CL-ROGUEOver the last six months I have been porting the <a href="http://roguelikedevelopment.org/archive/files/executables/rogue3.6.2-linux.tar.gz">1981 version</a> of <a href="http://www.wichman.org/roguehistory.html">Rogue</a> to <a href="http://en.wikipedia.org/wiki/Common_Lisp">CL</a>. My intention was to learn the basics of CL; it's a straight port of the game. I wish I had thought of porting something sooner (especially Rogue, which I once ported to <a href="http://www.geocities.com/originalravinray/geos/history.htm">PC/GEOS</a>), but for some reason this didn't occur to me until recently. It is a great way to learn a language if you don't have much time. I heartily recommend it (over, say, trying to think of a "pet project" to code up in the new language, which is cool, but requires a substantial investment). With porting, the project is already written and working, and you can pick it up and drop it frequently (if you have only a few hours a week, for example) without losing too much context (the original authors did all the hard work!) In the case of C and CL, porting was a good way to learn all the side-effect-y features of CL that are often glossed over in CL books (which focus more on functional programming).<br /><br />Having spent most of my career doing C/C++/Unix (and a bit of C#/Windows), it is interesting to see first-hand the alternative road that CL would have taken us down. One cannot compare C and CL directly, because in CL the operating system and language are indivisible. That is probably its biggest strength. By contrast, although C is the "first class" language of Unix, it was not treated especially royally. For example, you cannot use C directly in the command shell. When I was first learning Unix, it was confusing that I couldn't call C functions from the so-called "C Shell".<br /><br />At first, CL's REPL seems alien. Once you realize it is the same thing as the command shell, all makes sense. For example, I had a little difficulty understanding what <a href="http://www.cliki.net/asdf">ASDF</a> was until I realized it's equivalent to <b>make</b> or <b>ant</b>. Many CL functions and packages correspond to Unix utilities that you'd normally have to run from the command-line. Likewise, the lack of an Eclipse- or Visual Studio-like debugger at first seemed to be a major weakness, until it dawned on me that <i>you're always in the debugger</i> in CL.<br /><br />Porting C to CL was mostly mechanical and surprisingly easy. What was most intriguing was that some relatively obscure-sounding features of CL proved extremely useful (unfortunately I didn't discover this until late in the game). In particular, <a href="http://www.lisp.org/HyperSpec/Body/speope_symbol-macrolet.html">SYMBOL-MACROLET</a> and <a href="http://www.lisp.org/HyperSpec/Body/mac_define-symbol-macro.html">DEFINE-SYMBOL-MACRO</a> helped immensely (or at least they did once I figured out how to use them!)<br /><br />The port itself is <a href="http://code.google.com/p/cl-rogue/">here</a>.Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com0tag:blogger.com,1999:blog-32049549.post-5037882441679245082007-03-12T23:26:00.000-07:002008-03-21T16:07:44.178-07:00Everything in ModerationOn the night of November 18th, 1849, lovable, bearded mountain man Grizzly Adams found himself stranded on the Alaskan tundra in his simple canvas tent, with nothing to do but wait out the blizzard raging all around him. At such times Adams was wont to compose computer programs in his head. Sometimes he would write the code on his notepad, and when next he found himself in a larger town, such as Fairbanks, he would have it telegraphed to the nearest computing facility. On this particular night, however, he did something extraordinary; he conceived of a brilliant improvement over assembly language, until then the only option available to programmers on the Difference Engine MXVII. His conception was the "C" programming language, which has dominated the programming world ever since (along with its minor variants, C++, C#, Java, Smalltalk and Lisp). C is a coating of syntactic sugar over Difference Engine Assembler (DEA). For example, C's "++" operator corresponds to the DEA <tt>ADD-YE-THE-NUMERAL-ONE-TO-THE-NUMERAL-IN-QUO</tt> operation code (which was a real b***h to write, by all accounts). C's other statement types translated readily into DEA, too. For example, the "for" loop reduced 30 lines of DEA (on average) down to about 10 lines (on average) of C: a big savings in those days, when one had to write code by hand, telegraph it to a computing facility (at a penny a word!), and wait patiently for the results.<br /><br />Computer Science being the conservative field that it is, programming languages have changed little in the 158 years following C's inception. A few small enhancements have been added by C's successors, but these have been relatively minor, and have upheld the "spirit" of C. For example, Danish inventor Bjarne Stroustrup created "C++" by adding to C the concept of a "class", a convenient syntax for limiting the scope of global variables. Meanwhile, other language designers took different tacks. Whereas Stroustrup created a "higher-level" C with C++, Stanford professor John McCarthy created a "lower-level" C, which he named "Lisp", wherein one programs directly in the intermediate representation (aka "abstract syntax tree") that C compilers generate. Similarly, Alan Kay's "Smalltalk" is a minor variation of Lisp: it represents the C abstract syntax tree using fewer parentheses. Although Smalltalk and Lisp remain exceedingly close to C, they are the most daring of any new programming languages. Perl, Ruby, ML, Haskell, Python, SNOBOL, and others all fall somewhere on the spectrum between C and Lisp/Smalltalk.<br /><br />Lest you worry that I'm suggesting progress in the field of programming languages has been glacial, fear not! I commend heartily the <i>intentionally</i> moderate pace of development. It has been for a good cause, after all: ensuring that programmers do not misuse overly-powerful language features which they do not understand. By limiting programming languages to the small set of primitive operations that Charles Babbage developed, over 160 years ago, we ensure that programmers only attempt those problems for which they are qualified. Think of these intentional limitations on programming languages as being akin to those signs you see at amusement parks, consisting of a leering Technicolor elf with a big cartoon bubble saying, "You must be <b>this</b> tall to ride <i>The Bombaster</i>". The intense feat of abstract thinking required to see how useful applications could be built from such low-level functionality acts as a sort of programmer's amusement park sign. Weak programmers recognize when they're "too short" and stay off the ride (and stay out of trouble!) This is, in fact, the cornerstone of the widespread high quality, stability and performance of modern software applications that we experience every day. So do not worry, I'm not suggesting it <i>ever</i> change!<br /><br />That said, it is interesting, purely as an exercise, to consider what scientific and technological breakthroughs from the last 158 years could be taken advantage of in a new programming language. Let's see.<br /><br />First, our basic notions about <i>time</i> have changed since 1849. Back then, Einstein's theory of Special Relativity, and all of the subsequent work in modern Physics, was, of course, unknown. Newtonian mechanics was the only thing Grizzly Adams would have known about, and that meant action-at-a-distance. Although Newton would not have told Grizzly that everything happened simultaneously, he would have become downright confused trying to explain to Grizzly how multiple concurrent activities would <i>actually</i> work. Thus C, and its variants, have no easy way to represent simultaneous activities. Everything happens in a single stream of time. For example, if you want multiple things to happen simultaneously, you have to "fake it" by interleaving them in your code. For example, take this simple email client written in C:<pre class="code">TextBox toTxt = new TextBox("To: ", ...);<br />TextBox ccTxt = new TextBox("CC: ", ...);<br />TextBox cc2Txt = new TextBox("CCRider: ", ...);<br />TextBox subjectTxt = new TextBox("Subject: ", ...);<br />TextBox bodyTxt = new TextBox("", 24, ...);<br />TextBox statusTxt = new TextBox("Status", ReadOnly, ...);<br />Button sendButton = new Button("Send", &doSend);<br />Button cancelButton = new Button("Cancel");<br />Button resetButton = new Button("Reset");<br />Frame frame = new MainFrame("Email");<br />frame.Add(toTxt, ccTxt, cc2Txt, ...);<br /><br />// ... imagine lots of gnarly code here ...<br /><br />private const ipated void doSend(Button b) <br />{<br /> String[] smtpHosts = Config["smtp-hosts"];<br /> if (smtpHosts != null) {<br /> for (smtpHostIP, port in LookupViaDNS(smtpHosts)) {<br /> Socket sock = Socket.Open(smtpHostIP, port);<br /> int err = sock.Send("ELHO", ...);<br /> if (err != 0) {<br /> statusTxt.Update(String.Format("send error {0}", strerror(err)));<br /> }<br /> // etc...<br /> }<br /> }<br />}</pre>This code functions, but suffers from problems such as the entire user interface freezing while hosts are being looked up via DNS, connections opened, handshakes shook, the contents of the mail being sent, etc. That could take a long time, and users get peevish when they cannot interact with an application for extended periods.<br /><br />Since Grizzly Adam's day, Albert Einstein (and some other physicists, too, I think), frustrated by the dearth of good email clients, spent time extending Newton's concept of time. The details are far beyond the scope of this essay (or, for that matter, my own comprehension) but suffice it to say that they can all be distilled thusly: <i>everything is relative</i>. For example, if I am riding my skateboard down the freeway at 10mph, then an 18-wheel tractor-trailer rig bearing down on me from behind, at 60mph, will appear <i>to me</i> to be going 50mph (if I should be smart enough to turn around and look, that is). Of course, the driver of the truck perceives her truck to be moving at 60mph, and me to be moving at <i>negative</i> 50mph. Furthermore, the only way I'm even <i>aware</i> of the tractor-trailer's presence is due to <i>signals</i> of one sort or the other (light and sound) bouncing around between the truck and myself. For example, I can <i>see</i> the photons that have bounced my way from the gleaming chrome grille on the front of the truck, and I can <i>hear</i> the desperate shrieking of the truck's horn as the driver attempts to avoid turning me (and my skateboard) into a pancake.<br /><br />To keep programmers from turning <i>themselves</i> (and others) into <i>metaphorical</i> pancakes, these two concepts (concurrent activities happening in their own space/time continuum, and the signals that can pass between them) have been kept strictly separate, <i>and</i> have been kept rigorously out of any programming languages. This has been accomplished through the tireless efforts of a secret, underground organization (the cryptically-named <i>Association for Moderation in Computing</i> (AMC), a group about which little is known beyond their name and the few scant facts I am about to relay to you) that has maintained a long-standing disinformation campaign:<ol><li>AMC agents have infiltrated all language development committees and have ensured that these groups allow concurrency and signaling primitives to exist <b>only in libraries</b>, if indeed they exist at all.<br /></li><li>These same agents are also responsible for promulgating a false dichotomy between the two features, via strategically placed blogs, Usenet posts, blackmail and hallway conversations. Calling concurrency "threads" and signals "events", the agents have, Jason-like, thrown a proverbial rock into the crowd of computer scientists. Half of them are convinced that threads are evil and must be obliterated in favor of events, and the other half that the <i>exact opposite</i> is true. These camps war constantly with each other. And while the AMC's real aim is to prevent use of <i>either</i> feature, at least this way the damage is mitigated.<br /></li></ol>With all of that as a caveat, one could imagine a language where this sort of everything-is-relative concept, as well as signaling, were <i>both</i> built in <i>directly</i> to the language. To save me some typing in the remainder of this essay, I refer to this hypothetical language as <i>Relang</i> (for <b>RE</b>lative <b>LANG</b>uage; get it?) In Relang, anything logically concurrent could simply be coded that way, explicitly, without significant performance penalties. Just as in real life, the only way these concurrent activities could interact with each other would be through "signals", sort of like the photons and sound waves that physicists have discovered since Grizzly Adam's time. Each concurrent activity would probably have a data structure, such as a queue, to hold incoming signals, so that they could be processed in a comprehensible way.<br /><br />If we were to imagine the above example code re-written in this new language, each of the UI objects would exist in its own space/time continuum and communicate with other UI objects by sending signals (such as photons, sound waves, folded-up pieces of paper, and lewd gestures) to them. One required change would be that lines like this:<pre class="code">statusTxt.Update(String.Format("send error {0}", strerror(err)));</pre>would now read:<pre class="code">send(statusTxt, update, String.Format("send error {0}", strerror(err)));</pre><br />Meanwhile, the statusTxt object would be sitting in a loop looking something like so:<pre class="code">// This function is operating in its own<br />// space/time continuum.<br />static private isolated formless void superTextTNT()<br />{<br /> E = receive(infinity);<br /> case E:<br /> {update, txt} -> self.txt = txt; send(mainFrame, update, self);<br /> {invert} -> self.invert(); send(mainFrame, update, self);<br /> ...etc...<br /> superTextTNT(); // this is a tail-call optimizing version of C<br />}</pre>Now it is clear that each UI element is "doing its own thing" in its own personal space, and not trying to grope any of the attractive UI elements sitting on neighboring barstools. As a side-benefit, the UI would no longer freeze up all the time.<br /><br />Now, of course, you are probably thinking, "Ok, wise guy, why <i>don't</i> languages work this way?" Well, first off, this feature falls smack dab into the <i>too powerful</i> category; it would be misused left, right, up, down, and sideways (hence the AMC's disinformation campaign). Even were that not the case, however, there's this other problem. To implement the above efficiently, the language would have to be <i>aware</i> of when blocking (e.g., I/O) could occur. Otherwise each of those "receive" statements would tie up a real OS thread, which is too expensive in the general case. And so here is where the story takes a slightly sad turn. Why <i>not</i> make the programming aware of when blocking occurs? Simple, because it is <b>impossible</b> to do that. While I am unsure of all the particulars, I have been assured by many top-notch computer scientist that that would be flat-out, 100%, totally, and absolutely, impossible. No way in heck it could ever be implemented. Oh well.<br /><br />On the bright side, while the language feature is unavailable, there is an easy work-around. Use just <i>two</i> threads of execution. One creates a "user interface" (UI) thread and an "everything else" thread. Then one ensures that <i>only</i> UI-related activities occur on the UI thread and that, well, <i>everything else</i> occur on the other. In practice, this has turned out to be a model of simplicity (as anyone who has done UI programming could tell you, it is trivial to separate UI from "everything else") and is a big part of why most applications with graphical user interfaces work so flawlessly. It <i>is</i> unfortunate that one uses threads at all (they are deprecated for a reason, you know), but at least there are only two, and they can be implemented in a library, without polluting the language itself. Further, because there are only two threads, signaling is kept entirely out of the picture; that extra bit of complexity is unnecessary with so few space/time continua to keep track of. In fact, the <i>only</i> downside is that two or more UI elements cannot update themselves simultaneously, since they are both operating on the UI thread. Fortunately, I have never heard of a graphical application that actually required this. Let us hope that such a beast never comes crawling out of the proverbial swamp.<br /><br />Speaking of UI, let us now consider another as-yet untapped technological advance: modern display technology. Back when C was first invented, all programs had to be written down in long hand by the programmer, and then a telegraph operator had to manually translate it into Morse code (unless the programmer happened to be at the computing facility). C's extreme terseness stems from this. All languages inspired by C have kept true to its roots; they are easy to write longhand, too, just in case one has to write software without a modern display handy. If we were to give up this requirement (a bad idea in practice, mind you), how might a language make use of this Faustian feature?<br /><br />Since the features that have been added to C (e.g., object-oriented programming) have focused on new ways to scope data, why not start using, say, color for scope, too? For example:<pre class="code">int <span style="color:red;">i</span> = 0;<br />private explicit adults only int foo()<br />{<br /> return <span style="color:red;">i</span>++;<br />}</pre>This trivial example shows how one can avoid typing "static", and make it a little easier to see where the variable is used. You could imagine more complicated uses of this, though:<br /><pre class="code">public mutable implicit void CrawlSites(String hostsFile)<br />{<br /> try {<br /> Stream hostStream = <span style="color:red;">File.Open</span>(hostsFile, "r");<br /> String host;<br /> int port;<br /> while (host, port = <span style="color:purple;">Parse</span>(hostStream)) {<br /> sock = <span style="color:blue;">Socket.Open</span>(host, port);<br /> <span style="color:pink;">CrawlSite</span>(sock);<br /> }<br /> } catch (<span style="color:red;">IOError fileError</span>) {<br /> Blub.System.Console.ErrorStream.Writeln("unable to open hosts file: %s", fileError.toString());<br /> } catch (<span style="color:blue;">IOError socketError</span>) {<br /> MaybeThrottleFutureConnections(host, port);<br /> Blub.System.Console.ErrorStream.Writeln("unable to connect to %s:%s: %s", host.toString(), port.toString(), socketError.toString());<br /> } catch (<span style="color:purple;">IOError parseError</span>) {<br /> Blub.System.Console.ErrorStream.Writeln("error reading from '%s': %s", hostsFile, parseError.toString());<br /> } catch (<span style="color:pink;">IOError socketReadError</span>) {<br /> Blub.System.Console.ErrorStream.Writeln("error reading from host '%s':%d: %s", host, port, socketReadError.toString());<br />}</pre><br />One could do more than just set the color of the variables themselves. For example, one could use the mouse to right-click on an entire line and set its background. Say you want to make sure that nobody messes with the log object in the following function:<pre class="code">private static cling void foo()<br />{<br /> <span style="background-color: yellow;">Log log = new Log("foo starting")</span>;<br /> // ...imagine lots of stuff here...<br /> <span style="background-color: yellow;">log.End()</span>;<br />}</pre>The rule would be that lines with the same background color would all be in a special sub-scope that was unavailable to anyone else. If someone accidentally added in some code that referred to "log" in the middle of the big, hairy function, it would be flagged as an error.<br /><br />As stated earlier, this feature (and related features that would require a graphical user interface) is kept out of programming languages for a reason: we might have to start writing code without computers around, someday. If languages themselves depended on a GUI, society would probably collapse while programmers scrambled to re-write everything in C or one of its variants.<br /><br />A friend of mine thought of a solution for this problem, but it is so far "out there", I'm only going to mention it in passing: one could use XML to "annotate" the hand-writable parts of code. He noticed noticed this as he was typing in the examples such as the ones above, in fact: he was doing stuff like... [<font color="red">Editor's note</font>: Ok, dammit, here's the problem. I can't figure out how to "quote" XML in this dang blog. It keeps getting interpreted as HTML, and so, while I'd like to show you what the code would look like the way I envision it, I'm going to have to hack around the problem. Instead of actual XML, I'm going to use a mock XML that uses parentheses instead of less-than and greater-than. It's also kind of late at night, and I'm getting tired, so I'm going to not type the end tags in. Let's call this XML variant PXML, for <i>Parenthetical XML</i>.] The example above, in PXML, would look like:<pre class="code">private static cling void foo()<br />{<br /> (color :yellow Log log = new Log("foo starting"));<br /> // ...imagine lots of stuff here...<br /> (color :yellow log.End());<br />}</pre>The way this would work, with PXML (again, sorry I can't write out the real XML as I would prefer), is that, if you were writing out the code using a pen and paper (or a typewriter, or the dusty teletype you came across in your company's storeroom while looking for a place to smoke) then you'd write out the annotations such as the "color" PXML form directly. If you were using a modern IDE, on the other hand, the IDE wouldn't actually show you the PXML (well, not unless you actually <i>asked</i> it to). It would just show the whizzy colors (again, unless for some reason you <i>preferred</i> the PXML). And of course, you could use this mechanism for something more than just coloring and scope.<br /><br />For example, suppose you were a big Python fan. You could edit your code in a sort of Python-looking mode. Under the covers, the IDE would be generating PXML, but it wouldn't show that to you, after all, you're a Python fan, right? I.e., if you wrote this in Python:<pre class="code">def foo(a, b):<br /> return a + b;</pre>Then the IDE could just generate the following under the covers:<br /><pre class="code">(def foo (a b)<br /> (return (+ a b)))</pre>Of course, in order to let you write code using <i>any</i> Python feature (list comprehensions, iterators, etc.), there would have to be some way for you to express those things in XML. Fortunately, as we all know, XML can represent anything, so this would not be a problem.<pre class="code"># Python<br />(x * y for x in l1 for y in l2 if x % 2 == 0])</pre>would be:<pre class="code">(generator (* x y)<br /> ((x l1))<br /> (y l2))<br /> (= (mod x 2) 0))</pre><br />[Again, <i>sorry</i> for not being able to write out the actual XML, which would look a lot cooler; I know that PXML is painful to look at. Darn blog! Actually, I guess since there is no fundamental difference between XML and PXML, the IDE could probably use either one, interchangeably, under the covers. But I doubt anyone in their right mind would actually <i>choose</i> PXML over XML, so it would not be worth the extra time to implement that.]<br /><br />In any case, the AMC would look askance at <i>any</i> of these proposed features, so let us resume thinking about another technology!<br /><br />Perhaps the biggest invention to come along has been the "Internet". No longer are computers linked together via a tenuous chain of telegraph wires and human operators, as Grizzly Adams had to endure. Modern computers are linked up more or less directly by a vast web of routers, operated not by humans but tiny elves who can move with great precision at near-light speed. It would be incredibly dangerous to make this "Internet" into a first-class concept within a programming language. Programmers would just share bad code with each other that much more easily! Nevertheless, just for fun, let's look at how things might work if one <i>were</i> to add such a dangerous feature. For inspiration, let us consider a feature that Sun Microsystems playfully suggested via an in-joke, of sorts, in Java's package system. <br /><br />To use another company's Java package, Sun requires the following procedure:<ol><li>The programmer mails in a form, ordering a magnetic tape containing the desired Java package from the appropriate vendor.<br /><li>After a few weeks it arrives on a donkey cart, driven by a crusty old farmer.<br /><li>The programmer tips the farmer generously (if they ever want another delivery).<br /><li>The programmer must then use the cpio utility to remove the package from the tape.<br /><li>At this point, the package (which is in a "jar" file, named for irrepressible <i>Star Wars</i> character Jar Jar Binks) is intentionally not usable until you go through the further step of adding its location to an environment variable called the CLASSPATH.<br /><li>The programmer is now <i>almost</i> ready to use the package, provided that s/he restarts any Java software running on their machine, and did not mistype the path to the jar file.<br /><li>It may also be helpful, at this point, for them to do a Navajo rain dance and sacrifice a chicken, especially if trying to get more than one "jar" file installed properly.</ol>Now, the in-joke that I referred to above is the following: Sun's convention for <i>naming</i> these packages is to use "Internet" addresses (well, actually, <i>reversed</i> addresses, to make it more of an in-joke). I think they were making a subtle reference to the unimplemented feature whereby this:<pre class="code">import com.sun.java.jaaxbrpc2ee;</pre>would cause the Java Virtual Machine to download the jaaxbrpc2ee package directly from "java.sun.com", without the programmer having to do anything. For numerous reasons this would never work. What if your computer weren't connected to this "Internet"? Or what if you were to download an evil version written by evil hackers? It is well-known that both of these problems are completely intractable, whereas the manual steps listed above <i>ensure</i> nothing like this could ever happen. Nonetheless, the direct downloading way does seem like it might speed up the pace of software development a bit! Too bad there are all those problems with it.<br /><br />What if writing:<pre class="code">import com.sun.java.jaaxbrpc2ee;</pre>actually <i>did</i> download, install, and, well, import the jaaxbrpc2ee package? Ignoring the impossibility of actually making a socket connection, finding space on local disk, etc (more intractable problems, I'm afraid), I can think of two major issues with this:<ol><li>Security<br /><li>Versioning<br /></ol>Security would be a toughie. You might have to have an MD5 or SHA1 hash of the Jar Jar file available somewhere for the JVM to check on in order to determine if it has downloaded a valid copy. Not sure this would work, but if it did you could actually download the Jar Jar file from your cousin Harold's warez site that he runs out of his basement. That way if com.sun.java was down you'd have at least one other option.<br /><br />Then there's the versioning issue. What if you were developing against version 2.3.5 of jaaxbrpc2ee and Sun released version 3.0.0? How would the JVM know not to use it? Chances are, you'd have to add some syntax to Java in order to handle this. You could use a regular expression to indicate which versions were acceptable:<pre class="code">import com.sun.java.jaaxbrpc2ee 2.3.*;<br />import org.asm.omygawd *.*.*.*;<br />import org.standards.jdbc.odbc.dbase2 19.007a*;</pre><br />Of course, as you can see, anyone can publish a package that others could download and use directly. There could even be a free service that maintained these packages, for people who lacked the wherewithal to host their own packages. They'd just have to prove they owned their domain name. Also, people wouldn't be allowed to update an existing version, they'd have to release a new version.<br /><br />Ideally, one would be able to use the "Internet" anywhere in your code, not just when importing packages. Pretty much anything could use the "Internet":<pre class="code">com.att.bell-labs.int32 i = org.ieee.math.pi * (radius ^ 2);</pre>For example, if you wanted to run code on another machine, you might say (in PXML with Relang extensions):<pre class="code">(on com.megacorp.server11:90210<br /> (if ...mumble... (send com.megacorp.server23:2001 '(d00d u suck))</pre>The above would run the "if" expression on server11.megacorp.com (port 90210), and that code would sometimes send a message to yet another machine. Of course, you could use variables instead of hard-coded machine names and ports. Web servers could communicate with web browsers (if they supported PXML/Relang) like so:<pre class="code">(import com.niftystuff.clock 1.*)<br /><br />(def clock ()<br /> (register :clock)<br /> (receive infinity<br /> (update-thine-self (com.niftystuff.clock:draw)))<br /> (clock))<br /><br />(def display-time ()<br /> (while true<br /> (sleep 1)<br /> (send :clock 'update-thine-self)))<br />;; imagine lots more code here...<br />(html<br /> (body<br /> (on browser<br /> (spawn clock)<br /> (spawn display-time)<br /> (do some other stuff))))</pre><br />Ah, but it's getting late, and I can see a strange van parked outside, and my dog is acting nervous (and I have heard something about an AMC "wet" team.) Maybe it is time to post this blog and go to bed! The crazy language sketched out above, is, well, just that: crazy!Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com4tag:blogger.com,1999:blog-32049549.post-68747471202066888562007-02-16T20:19:00.000-08:002007-06-18T22:57:05.197-07:00Losing Big Is EasyWhat's the connection between soda and the failure of programming languages? I would have thought "zero" had I not recently stumbled across a wikipedia article about a little-known predecessor of Coca-Cola. As it turns out, in 1879, a scrappy Norwegian immigrant named Jan Kjarti (who, incidentally, also coined the term "artificial sweetener") started a soda company. His company, Slug Cola (the motto was "you'll love to Slug it down!"), produced a soda that cost a little more than Coke but which actually tasted much better (note that it didn't actually use artificial sweetener, either). It's hard to even find out what it tasted like anymore, as none of the small but loyal customer base of Slug Cola are still alive. Fortunately, a noted Boston historian and Slug researcher has found a few scattered journal entries and newspaper clippings from the era. By all accounts drinking Slug, relative to drinking Coke, was something akin to a transcendent experience. Of course, since you've heard of Coke and haven't heard of Slug, you can probably guess what happened: Coke kicked their ass. One of Jan's protégés (one Richard Angel) later wrote a newspaper editorial entitled "Coke is Better", about the failure of their company. It was both heartfelt and poignant, and included a frank assessment of why Slug Cola failed. He pointed to the fact that, just as Slug was making a few gains in the marketplace, the US entered what became known as the "Soda Winter", a period of about 10 years where the public became irrationally convinced that carbonated water was bad for your stomach. Coke survived this period relatively unscathed, in part aided by the fact that people felt that some of Coke's ingredients actually offset the purported stomach-damaging properties of carbonation. Aside from that, and perhaps more importantly, Coke was cheaper to produce, allowing Coke to expand more rapidly into new markets. Try as they might, the proprietors of Slug Cola just couldn't convince members of the public (who had invariably tasted Coke already) of Slug's merits.<br /><br />Well, that's most of the story, at least. At the very end of the wikipedia article, the author points out a fact that, once I read it, I could have kicked myself for not having figured out myself. I mean, it was a long article and went into all this detail about how the company failed. And not once did it dawn on me, and this is the part the author pointed out, that the <i>name</i> of the product might be the most significant factor in its downfall. Slug! Duh! Of course nobody wants to drink something called Slug! I mean, you can try to tell them that Slug refers to the concept of eagerly drinking (i.e., "SLUGging down") a transcendent carbonated beverage. But I just don't think you can overcome first impressions. And, let's face it, the first impression of Slug is of, well, a slimy, oozing insect. Of course, I'm guessing all of you reading this were way ahead of me this whole time, so I bet you think I'm pretty dumb. All I can say is, go read the article and you might get a sense for how I could have failed to notice the obvious. The story just got so poignant, convoluted, and interesting, that I experienced a momentary lapse of common sense.<br /><br />Naturally I couldn't help, at this point, thinking about other poignant and convoluted stories that I've read about, and, like a flash, something that has probably been in my mind for years now hit me like a ton of proverbial bricks! The reason why my 3 favorite programming languages failed is that their names sucked ass! Just like Slug! I don't know why this didn't hit me before, but it just seems glaringly obvious now. What's more, I did a bit of research, and determined that there seems to be an almost inverse correlation between the coolness of a language's name and the coolness of the language itself. This might explain why we're still writing code using the equivalent of blunt, hollowed-out turtle bones, bits of twigs and leaves and stuff, just like our primitive Neanderthal ancestors.<br /><br />If you don't believe me already, let's look at the all-time coolest programming language names:<br /><br />C. Yup. C. C is cool. It's mysterious. It's cryptic. It's one syllable. It could even stand for Cool. In my mind, there is no better name for a programming language, and never will be (any attempts to replicate its coolness by picking other, single letters of the alphabet, such as D, will come off as mere me-too-ism). I remember in college, everyone wanted to know C. People would ask questions in CS211 that they already knew the answer to, just so they could mention some feature of C that they'd learned. I think the name has a lot to do with it. The language itself was my favorite programming language for many years, until I finally started learning more about real programming languages.<br /><br />C++. You can't improve upon the name C, but C++ was about as good as you can get. I think C++ kicked the ass of its nearest competitor due to its name. What would you rather use (if you didn't know anything about either language's technical merits): "C++" or "Objective-C". Obj-jeck-tive-See. Talk about clunky. I write code in Ob-jeck-tive-See. By the time you get to the third syllable you've just lost people's attention completely. They'll be staring off in another direction asking questions like, "is there a breeze in here?"<br /><br />FORTRAN. Yup. You may hate it, but it sure is popular, even to this day. FORTRAN always sounded cool to me, before I learned anything about it. It sounds like "fortress", but with a cool sci-fi twist to it.<br /><br />Java. Gotta hand it to Sun for picking a kick-ass name. It's short, it's cryptic, it's friendly; it implies a connection with a caffeinated beverage, something near and dear to many programmers' hearts. Its success tracked the explosive growth of upscale coffee shops, such as Starbucks. Yep, Java's stratospheric success has much to do with its name.<br /><br />Now let's look at the all-time loser names.<br /><br />Coming in with the 3rd worst name for a computer language, of all time, is Erlang. I write code in Ur-lang. I am caveman. I grunt and say Ur a lot. After laughing at you for a while, anyone you're trying to convince of Erlang's merits next question is, "Why is it called ERlang? Does it stand for Ericsson Language?" You're pretty much sunk at this point. It would be like if you were trying to get people to use MicrosoftLanguage instead of C#. Wouldn't happen. They'd just feel too silly.<br /><br />Coming in with the 2nd worst name of all time is... Smalltalk. This list just gets sadder as we get towards number one, doesn't it folks? Because the languages just keep getting better. Let me ask you this, folks: Smalltalk was designed by some of the best and brightest computer scientists of all time. Numerous of them have won Turing awards and other accolades. Why wasn't someone amongst them smart enough to point out this dead obvious fact: something called SMALLtalk is <i>never</i> going to be successful? I remember when I took Intro to Programming Languages and we were supposed to use SMALLtalk at one point. I just couldn't believe it. This is America, folks. Bigger is better. I wasn't about to use a puny, wimpy language that went so far as to point out its diminutive nature in its own name! I remember I just suffered through the SMALLtalk portion of the course and didn't pay the slightest attention to any of the language's merits. I mean, even if you ignore the SMALL aspect, what does "small talk" actually mean? It refers to trivial, banal conversation. Who wants to engage in banal conversation? Does that mean the messages you send between objects are trivial and banal? Sigh. It only gets worse. Smalltalk's latest incarnation is called Squeak. That's right, it's named after the sound a small rodent/pest makes. Might as well call it Slug.<br /><br />Last but certainly not least, here is the worst programming language name of all time: Lisp. OMFG this is a bad name. Bad bad bad. What does "lisp" mean? Lisp means "speech impediment"!! Do you want a speech impediment!? I don't think so! Back in college I had even less patience for Lisp than I did for Smalltalk. I mean, when it came down to it, I'd rather at least be able to make small talk, at a party, without having a lisp. Hint to John McCarthy: next time you come up with something brilliant, name it after something POSITIVE. Geez. And, as with Erlang, it just doesn't get any better when you try to explain why Lisp is called Lisp. It's short for LISt Processing... Get it? Isn't that funny? I don't hear you laughing. Yeah, 'cuz it's one of the worst puns ever. And not only is it not funny, guess what, most programmers don't actually think they're going to <i>do</i> much "list processing", so they're like, "maybe it IS good at List Processing, but I could give a flying monkey's posterior because that's just not what I want to be working on" (these programmers would much rather be working on their ORM layer, ironically).<br /><br />Phew. So there it is folks. One of the great tragedies of modern computer science turns out to have such a simple, prosaic explanation. I would be more surprised that nobody else has ever mentioned this before, except that it took me 16 years and an obscure wikipedia article to see the light, so I guess I shouldn't expect anyone else to have done so, either.Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com54tag:blogger.com,1999:blog-32049549.post-65415920058958891392007-01-17T21:07:00.000-08:002007-01-17T22:20:16.543-08:00Living SoftwareSteve Yegge's latest essay, <a href="http://steve-yegge.blogspot.com/2007/01/pinocchio-problem.html">The Pinocchio Problem</a> discusses how liveness, or the QWAN, is what makes software great. Like many great ideas, his is a crystallization of something that one already knows (e.g., Emacs is uniquely amazing) but somehow cannot quite formalize. In retrospect, of course, it seems almost obvious. Now that I've read his essay, I can think of a few other pieces of software that are alive.<br /><br />One is Erlang, one of the two programming languages in existence that I wish I could use professionally but can't (the other is Common Lisp). Erlang's live code migration feature allows upgrading code in a running system (such as an ATM switch, with tight availability requirements) in an extremely robust way. As far as I know, no other programming language (even ones that support something like this, such as Common Lisp) have sufficient support built in to really be able to do this safely in production systems. It also has a REPL, and is still the only reasonably well-supported language (i.e., one could consider using it without being laughed off the face of the planet) that actually tackles concurrency well.<br /><br />Another is, well, any serious relational database. Although much maligned, SQL is actually a cool programming language. And the development environment provided by the database is actually a REPL and is much better than your typical dead IDE. Every time I have to do serious database programming, I actually find myself enjoying the interactivity of the experience. Databases tackle some really thorny problems (such as persistence) that most programming languages treat as a secondary concern, unworthy of treatment directly in the language itself. This is one of the major failings of most programming languages. The C# team seems to be at least trying to remedy this with LINQ in C# 3.0, although I don't know too much about it.<br /><br />So I guess in addition to the qualities that Steve mentions that make software alive, I would add support for <b>concurrency</b> (or, more generally, explicit support for dealing with the passage of time), and <b>persistence</b>. There are probably a few other qualities as well (such as dealing with uncertainty, but it's too late at night to write any more about that).Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com0tag:blogger.com,1999:blog-32049549.post-1155270486459364652006-10-28T21:12:00.000-07:002008-03-21T16:19:49.039-07:00How poopy is YOUR code?After numerous years at the top, <i>object-oriented</i> still reigns as the number-one programming buzzword (this claim is based on a wide-ranging, highly scientific, double-blind study of my opinion on the subject). I find this interesting because, in my observation, programmers rarely use OOP. They may use OO <em>languages</em>, but your typical chunk of <em>code</em> is rarely terribly OOP-y. Despite this, there has been an obsession with OOP over the last 20 years that has possibly obscured more significant techniques.<br /><br />Even the experts do not agree on what OOP truly is, but it is most<br />often associated with the following:<ul><li>Subclassing<br /><li>Interfaces<br /><li>Polymorphism<br /><li>Encapsulation<br /></ul>All of these things are programming techniques, rather than inherently desirable qualities. So why do we spend all our time writing stuff like <tt>ProtocolFactory.Instance().Create(new AddressAdapter(anAddress, aPort))</tt>? In a word, <i>maintainability</i>. In case you haven't heard, <i>maintainable</i> code is defined as "code I like". "Your code isn't maintainable," should you ever hear it, usually means, "I don't like your code but I'm not sure why exactly and/or I don't feel like explaining myself." (If someone is really unhappy with your code, rather than say it's unmaintainable, they'll say that it "doesn't scale"). Cynics would point out, here, that 20 years of struggling to use OO techniques correctly has been motivated by solely something this subjective. Of course, I don't agree with these cynics.<br /><br />In my experience, OO has been useful for a few things. For one thing, it's a way to see if a programmer can understand abstract concepts such as subclassing, not only because they will periodically stumble across a use for them, but also because it provides a sense of how well they'll be able to learn all the <i>other</i> tools that they'll need to do their job. I.e., being able to learn to use programming techniques, in general, is a useful skill in and of itself. As with anything, though, simply using tools doesn't necessarily mean they're being used correctly or appropriately. In fact, in programming, emphasis on techniques has not been accompanied by a serious focus on why those techniques should be used. See, <i>that</i> problem is considered too subjective. It's easier to give the same tired example of an <b>Animal</b> class hierarchy than it is to explain <i>why</i> polymorphism should be used to make good software in some real-life case.<br /><br />Fortunately, I don't think it has to be that hard or subjective. So enough theorizing, for now, let's get down to a real example. What is the <i>biggest</i> problem with the following code?<pre class="code"><span class="comment-delimiter">// </span><span class="comment">Socket.h<br /></span><br /><span class="keyword">struct</span> <span class="type">Socket</span> {<br /> ...mumble...<br />};<br /><br /><span class="type">Socket</span> <span class="function-name">CreateSocket</span>();<br /><br /><span class="type">void</span> <span class="function-name">Open</span>(<span class="type">Socket</span> <span class="variable-name">s</span>, <span class="type">Address</span> <span class="variable-name">addr</span>, <span class="type">Port</span> <span class="variable-name">port</span>);<br /><br /><span class="comment-delimiter">// </span><span class="comment">Returns number of bytes actually read.<br /></span><span class="type">int</span> <span class="function-name">Read</span>(<span class="type">Socket</span> <span class="variable-name">s</span>, byte[] outBuffer);<br /><br /><span class="comment-delimiter">// </span><span class="comment">Returns number of bytes actually written.<br /></span><span class="type">int</span> <span class="function-name">Write</span>(<span class="type">Socket</span> <span class="variable-name">s</span>, byte[] buffer);<br /><br /><span class="type">void</span> <span class="function-name">Close</span>(<span class="type">Socket</span> <span class="variable-name">s</span>);</pre>(Ok, no points to the wiseacre who said, "It's written in Blub.")<br /><br />One could point out that it's not very OOP-y. It doesn't use encapsulation (at least not officially), in that the <b>Socket</b> struct is just a plain old struct. It has no class definition, and doesn't implement an interface. It also doesn't make use of polymorphism! What if I want to be able to pass this <b>Socket</b> to something that expects a <b>Stream</b>?<br /><br />These might be valid concerns in one situation or another, but remain, nonetheless, mostly mechanical issues. The big problem is that this code is difficult to use correctly. Worst of all, it's difficult to debug. For example, you can write this:<pre class="code"><span class="comment-delimiter">// </span><span class="comment">More pseudo-C<br /></span><span class="type">Socket</span> <span class="variable-name">s</span> = CreateSocket();<br />s.Write(myBuffer);</pre>In this case <b>Open()</b> was never called, but to figure out that this is a problem requires diagnosing a mysterious failure at run-time, which may not be easy to track down to its source. And while the above is a rather trivial case that you'd likely notice simply by looking at it, there are more insidious and realistic examples, such as:<pre class="code"><span class="type">void</span> <span class="function-name">Handshake</span>(<span class="type">Socket</span> <span class="variable-name">s</span>)<br />{<br /> <span class="keyword">const</span> <span class="type">byte</span>[] header = { 0xBEEF, 0xBEEF };<br /> <span class="keyword">if</span> (s.Write(header) != header.length) {<br /> ...mumble...<br /> }<br />}<br /><br /><span class="comment-delimiter">// </span><span class="comment">The following is in a file/library far, far away<br /></span>...<br /><span class="type">void</span> Mumble(...)<br />{<br /> ...<br /> Socket s1 = Socket();<br /> Open(s1, <span class="string">"www.google.com"</span>, 80);<br /> <span class="type">Socket</span> <span class="variable-name">s2</span> = Socket();<br /> Open(s1, <span class="string">"localhost"</span>, 2341); <span class="comment-delimiter">// </span><span class="comment">OOPS!<br /></span> Handshake(s1);<br /> Handshake(s2); <span class="comment-delimiter">// </span><span class="comment">BOOM!<br /></span> ...<br />}</pre>This could easily happen, just a slip of the finger while typing. Since this code is written in C, the results will be catastrophic and hard to diagnose. This code is like a city sidewalk filled with open manholes; you can avoid them, but you have to watch where you step. And did I mention you're in one of those large, cold, unfriendly cities where your fellow pedestrians are unlikely to warn you of your imminent demise?<br /><br />This does actually relate to OOP. The problem is that programmers are taught all about how to write OO code, and how doing so will improve the <i>maintainability</i> of their code. And by "taught", I don't just mean "taken a class or two". I mean: have pounded into head in school, spend years as a professional being mentored by senior OO "architects" and only then finally kind of understand how to use properly, some of the time. Most engineers wouldn't consider using a non-OO language, even if it had amazing features ... the hype is that major.<br /><br />So what, then, about all that code programmers write before their <a href="http://www.norvig.com/21-days.html">10 years</a> OO apprenticeship is complete? Is it just doomed to suck? (Well, obviously I don't think so becuase, if I didn't, I wouldn't have been writing this essay.) Of course not, as long as they apply other techniques than OO. These techniques are out there but aren't as widely discussed. Going back to the example, here's an improved version.<pre class="code"><span class="comment-delimiter">// </span><span class="comment">Socket.h<br /></span><br /><span class="keyword">enum</span> <span class="type">MagicNumbers</span> {<br /> <span class="variable-name">OpenSocket</span> = 0xE474BEEF,<br /> <span class="variable-name">ClosedSocket</span> = 0xBEEF4A11,<br />}<br /><br /><span class="keyword">struct</span> <span class="type">Socket</span> {<br /> ...<br /> MagicNumber magicNumber;<br />}<br /><br /><span class="type">void</span> <span class="function-name">Open</span>(<span class="type">Socket</span> <span class="variable-name">s</span>, <span class="type">Address</span> <span class="variable-name">addr</span>, <span class="type">Port</span> <span class="variable-name">port</span>)<br />{<br /> ...<br /> s.magicNumber = OpenSocket;<br />}<br /><br /><span class="comment-delimiter">// </span><span class="comment">Returns number of bytes actually read.<br /></span><span class="type">int</span> <span class="function-name">Read</span>(<span class="type">Socket</span> <span class="variable-name">s</span>, byte[] outBuffer) <br />{<br /> Assert(s.magicNumber != ClosedSocket, <span class="string">"you already Closed that Socket!"</span>);<br /> Assert(s.magicNumber == OpenSocket, <span class="string">"using never-Opened or corrupt Socket!"</span>);<br /> ...<br />}<br /><br /><span class="comment-delimiter">// </span><span class="comment">Returns number of bytes actually written.<br /></span><span class="type">int</span> <span class="function-name">Write</span>(<span class="type">Socket</span> <span class="variable-name">s</span>, byte[] buffer) <br />{<br /> ...same stuff as Read...<br />}<br /><br /><span class="type">void</span> <span class="function-name">Close</span>(<span class="type">Socket</span> <span class="variable-name">s</span>)<br />{<br /> Assert(s.magicNumber == OpenSocket, <span class="string">"attempt to Close an unopened Socket!"</span>);<br /> ...<br />}</pre>The improvement here has little to do with any specific programming technique (in fact, there are better ways to implement the change). It's more a matter of <i>empathy</i>; in this case, for the programmer who might have to use your code. The author of this code actually thought through what kinds of mistakes another programmer might make, and strove to make the <i>computer</i> tell the programmer what they did wrong.<br /><br />In my experience the best code, like the best user interfaces, seems to magically anticipate what you want (or need) to do next. Yet it's discussed infrequently relative to OO. Maybe what's missing is a buzzword. So let's make one up, <i>Programming fOr Others</i>, or <i>POO</i> for short.<br /><br />One good example of POO in action is <a href="http://sqlite.org">sqlite</a>. One of the many relational database technologies out there, this one distinguishes itself by <i>just working</i>. I downloaded it and ran it without any configuration and it just kind of did what I expected it to, gave me a SQL prompt. You'd think this would be obvious, but setting up most databases is far from trivial, involving setting up users, passwords, config files, etc. It's as if the sqlite programmers actually read <i><a href="http://www.graficaobscura.com/future/futnotes.html">Futurist Programming Notes</a></i>. Sqlite doesn't restrict its poopy behavior to startup. When you create a table, for example, you don't have to specify the type of each row. It just lets you put in whatever the heck you want. Of course, you <i>may</i> specify the type if you <i>want</i> to, but the point is that the creators of this fine piece of software actually realized that you just might not care.<br /><br />By contrast, there are numerous software packages and APIs that aren't, frankly, very POO. For example, take your typical, basic IO API:<pre class="code"><span class="type">int</span> <span class="function-name">read</span>(<span class="type">File</span> <span class="variable-name">f</span>, <span class="type">char</span> *<span class="variable-name">buffer</span>, <span class="type">int</span> <span class="variable-name">bytesToRead</span>);<br /><span class="type">int</span> <span class="function-name">write</span>(<span class="type">File</span> <span class="variable-name">f</span>, <span class="type">char</span> *<span class="variable-name">buffer</span>, <span class="type">int</span> <span class="variable-name">bytesToWrite</span>);</pre> This code has a major (albeit subtle) issue: the values chosen for <b>bytesToRead</b> and <b>bytesToWrite</b> may have serious performance implications. But how do you even know that in the first place? And once you do, what do you do about it? You have little choice but to conduct a series of laborious experiments to figure out the best buffer size to use in each particular case. Maybe on some machines it's the size of a page, maybe on others a different size. And of course it might change with the next revision of your operating system, etc.<br /><br />At this point you may be wondering, "Gee, so it's a little hard to use, what's the big deal?" Well, imagine 5 people were standing around a room talking, and one of them wanted to know what 3.1451515 * 92.003 was? Now I haven't told you one critical piece of information, which is that there is, in addition to the 5 people already mentioned, a <i>computer</i> in the corner of the room. Given all this, what would you expect the people to do:<ul type="a"><li>Bust out some paper and pencils and try to remember how to do long division by hand, or,<li>Use the computer?</ul>This wasn't a hard question to answer. Yet, for some reason, in almost the exact same situation (ok, not the <i>exact</i> same situation, but closer than most people would like to admit), programmers tend to leave a problem (such as figuring out optimal buffer sizes) to (human) programmers rather than let computers figure it out.Jacob Gabrielsonhttp://www.blogger.com/profile/13887274100244616103noreply@blogger.com3