TITLE: StrangeLoop 1: A Miscellany of Ideas
AUTHOR: Eugene Wallingford
DATE: September 25, 2012  8:35 PM
DESC: 
-----
BODY:
For my lunch break, I walked a bit outside, to see the sun and
bend my knee a bit.  I came back for a set of talks without an
obvious common thread.  After seeing the talks, I saw a theme:
ideas for writing programs more conveniently or more concisely.

<B>ClojureScript</B>

<A HREF="https://twitter.com/swannodette">
   David Nolen</A>
talked about
<A HREF="https://github.com/clojure/clojurescript">
   ClojureScript</A>,
a Clojure-like language that compiles to Javascript.  As he
noted, there is a lot of work in this space, both older and
newer.  The goal of all that work is to write Javascript more
conveniently, or generate it from something else.  The goal of
ClojureScript is to bring the expressibility and flexible
programming style of the Lisp world to JS world.  Nolen's talk
gave us some insights into the work being done to make the
compiler produce efficient Javascript, as well as into why you
might use ClojureScript in the first place.

<B>Data Structures and Hidden Code</B>

The message of
<A HREF="https://thestrangeloop.com/sessions/data-structures-the-code-that-isnt-there">
   this talk</A>
by Scott Vokes is that your choice in data structures plays a
big role in determining how much code you have to write.  You
can make a lot of code disappear by using more powerful data
structures.  We can, of course, generalize this claim from data
structures to <EM>data</EM>.  This is the theme of functional
and object-oriented programming, too.  This talk highlights how
often we forget the lowly data structure when we think of writing
less code.

As Vokes said, your choice in data structures sets the "path of
least resistance" for what your program will do and also for the
code you will write.  When you start writing code, you often
don't know what the best data structure for your application is.
As long as you don't paint yourself into a corner, you should be
able to swap a new structure in for the old.  The key to this is
something novice programmers learn early, writing code not in
terms of a data structure but in terms of higher-level behaviors.
Primitive obsession can become implementation obsession if you
aren't careful.

The meat of this talk was a quick review of four data structures
that most programmers don't learn in school:
<A HREF="http://en.wikipedia.org/wiki/Skip_list">
   skip lists</A>,
<A HREF="http://en.wikipedia.org/wiki/Difference_list">
   difference list</A>,
<A HREF="http://en.wikipedia.org/wiki/Rolling_hash">
   rolling hashes</A>,
and <EM>jumpropes</EM>, a structure Vokes claims to invented.

This talk was a source of several good quote, including
<UL>
<LI> "A data structure is just a stupid programming language."
     -- Bill Gosper  </LI>
<LI> "A data structure is just a virtual machine." -- Vokes
     himself, responding to Gosper  </LI>
<LI> "The cheapest, fastest, and most reliable components are
     those that aren't there."  -- Gordon Bell  </LI>
</UL>

The first two quotes there would make nice mottos for a debate
between functional and OO programming.  They also are two sides
of the same coin, which destroys the premise of the debate.

<B>miniKanren</B>

As a Scheme programmer and a teacher of programming languages,
I have developed great respect and fondness for the work of
<A HREF="https://www.cs.indiana.edu/~dfried/">
    Dan Friedman</A>
over the last fifteen years.  As a computer programmer who
began his studies deeply interested in AI, I have long had a
fondness for
<A HREF="http://en.wikipedia.org/wiki/Prolog">
    Prolog</A>.
How could I not go to the talk on miniKanren?  This is a small
implementation (~600 lines written in a subset of Scheme) of
<A HREF="http://kanren.sourceforge.net/">
   Kanren</A>,
a declarative logic programming system described in 
<A HREF="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10663">
   The Reasoned Schemer</A>.

This talk was like a tag-team vaudeville act featuring Friedman
and co-author
<A HREF="http://www.cs.indiana.edu/~webyrd/">
  William Byrd</A>.
I can't so this talk justice in a blog entry.  Friedman and Byrd
interleaved code demo with exposition as they
<UL>
<LI> showed miniKanren at its simplest, built from three operators
     (<TT>fresh</TT>, <TT>conde</TT>, and <TT>run</TT>)  </LI>
<LI> extended the language with a few convenient operators for
     specifying constraints, types, and exclusions, and </LI>
<LI> illustrated how to program in miniKanren by building a
     language interpreter, EOPL style.  </LI>
</UL>

The cool endpoint of using logic programming to build the
interpreter is that, by using variables in a specification,
the interpreter produces legal programs that meet a given
specification.  It <EM>generates code via constraint resolution</EM>.

If that weren't enough, they also demo'ed how their system can,
given a language grammar, produce
<A HREF="http://www.nyx.net/~gthompso/quine.htm">
   quines</A>
-- programs <EM>p</EM> such that
<PRE>
    (equal p (eval p))
</PRE>
-- and <B>twines</B>, pairs of programs <EM>p</EM> and <EM>q</EM>
such that
<PRE>
    (and (equal p (eval q))
         (equal q (eval p)))
</PRE>

Then they live-coded an implementation of typed lambda calculus.

Yes, all in fifty minutes.  Like I said, you really need to watch
the talk at InfoQ as soon as it's posted.

In the course of giving the talk, Friedman stated a rule that my
students can use:
<BLOCKQUOTE><EM>
<B>Will's law</B>:
If your function has a recursion, do the recursion last.
</EM></BLOCKQUOTE>

Will followed up with cautionary advice:
<BLOCKQUOTE><EM>
<B>Will's second law</B>:
If your function has two recursions, call Will.
</EM></BLOCKQUOTE>

We'll see how serious he was when I put a link to his e-mail
address in my Programming Languages class notes next spring.
-----