I’ve updated the Textile formatter on the site and the code
for this entry is now displaying correctly. The previous version was
swalling the == operators in the code.
Lisp 1.5 Programmer’s Manual
I stumbled across this in
Bill Clementson’s blog and remembered using the Lisp 1.5 Prgrammers
manual from the college years. I have strong memories of pouring over
that particular page in the manual and attempting to understand all
the nuances.
If you’ve never read the Lisp 1.5 Programamers Manual, page 13 is
the guts of a Lisp Interpreter, the “eval” and “apply” functions. It
is written in Lisp, although the notation used is a bit funky. The
entire interpreter (minus two utility functions) is presented on a
single page of the book. Talk about a concise language definition!
In Ruby?
I had often thought about implementing a Lisp interpreter, but back in
the “old days”, the thought of implementing garbage collection and the
whole runtime thing was a bit daunting. This was in the day before C,
so my implementation language would have been assembler … yech.
But as I was reviewing the page, I realized that with today’s modern
languages, I could problably just convert the funky M-Expressions used
on page 13 directly into code. So … why not?
The Code
Here is the complete Ruby source code for the Lisp interpreter from
page 13 of the Lisp Programmers manual:
# Kernel Extensions to support Lisp
class Object
def lisp_string
to_s
end
end
class NilClass
def lisp_string
"nil"
end
end
class Array
# Convert an Array into an S-expression (i.e. linked list).
# Subarrays are converted as well.
def sexp
result = nil
reverse.each do |item|
item = item.sexp if item.respond_to?(:sexp)
result = cons(item, result)
end
result
end
end
# The Basic Lisp Cons cell data structures. Cons cells consist of a
# head and a tail.
class Cons
attr_reader :head, :tail
def initialize(head, tail)
@head, @tail = head, tail
end
def ==(other)
return false unless other.class == Cons
return true if self.object_id == other.object_id
return car(self) == car(other) && cdr(self) == cdr(other)
end
# Convert the lisp expression to a string.
def lisp_string
e = self
result = "("
while e
if e.class != Cons
result << ". " << e.lisp_string
e = nil
else
result << car(e).lisp_string
e = cdr(e)
result << " " if e
end
end
result << ")"
result
end
end
# Lisp Primitive Functions.
# It is an atom if it is not a cons cell.
def atom?(a)
a.class != Cons
end
# Get the head of a list.
def car(e)
e.head
end
# Get the tail of a list.
def cdr(e)
e.tail
end
# Construct a new list from a head and a tail.
def cons(h,t)
Cons.new(h,t)
end
# Here is the guts of the Lisp interpreter. Apply and eval work
# together to interpret the S-expression. These definitions are taken
# directly from page 13 of the Lisp 1.5 Programmer's Manual.
def apply(fn, x, a)
if atom?(fn)
case fn
when :car then caar(x)
when :cdr then cdar(x)
when :cons then cons(car(x), cadr(x))
when :atom then atom?(car(x))
when :eq then car(x) == cadr(x)
else
apply(eval(fn,a), x, a)
end
elsif car(fn) == :lambda
eval(caddr(fn), pairlis(cadr(fn), x, a))
elsif car(fn) == :label
apply(caddr(fn), x, cons(cons(cadr(fn), caddr(fn)), a))
end
end
def eval(e,a)
if atom?(e)
cdr(assoc(e,a))
elsif atom?(car(e))
if car(e) == :quote
cadr(e)
elsif car(e) == :cond
evcon(cdr(e),a)
else
apply(car(e), evlis(cdr(e), a), a)
end
else
apply(car(e), evlis(cdr(e), a), a)
end
end
# And now some utility functions used by apply and eval. These are
# also given in the Lisp 1.5 Programmer's Manual.
def evcon(c,a)
if eval(caar(c), a)
eval(cadar(c), a)
else
evcon(cdr(c), a)
end
end
def evlis(m, a)
if m.nil?
nil
else
cons(eval(car(m),a), evlis(cdr(m), a))
end
end
def assoc(a, e)
if e.nil?
fail "#{a.inspect} not bound"
elsif a == caar(e)
car(e)
else
assoc(a, cdr(e))
end
end
def pairlis(vars, vals, a)
while vars && vals
a = cons(cons(car(vars), car(vals)), a)
vars = cdr(vars)
vals = cdr(vals)
end
a
end
# Handy lisp utility functions built on car and cdr.
def caar(e)
car(car(e))
end
def cadr(e)
car(cdr(e))
end
def caddr(e)
car(cdr(cdr(e)))
end
def cdar(e)
cdr(car(e))
end
def cadar(e)
car(cdr(car(e)))
end
An Example
And to prove it, here’s an example program using Lisp. I didn’t
bother to write a Lisp parser, so I need to express the lists in
standard Ruby Array notation (which is converted to a linked list via
the “sexp” method).
Here’s the ruby program using the lisp interpreter. The Lisp system
is very primitive. The only way to define the function needed is to
put them in the environment structure, which is simply an association
list of keys and values.
require 'lisp'
# Create an environment where the reverse, rev_shift and null
# functions are bound to an appropriate identifier.
env = [
cons(:rev_shift,
[:lambda, [:list, :result],
[:cond,
[[:null, :list], :result],
[:t, [:rev_shift, [:cdr, :list],
[:cons, [:car, :list], :result]]]]].sexp),
cons(:reverse,
[:lambda, [:list], [:rev_shift, :list, nil]].sexp),
cons(:null, [:lambda, [:e], [:eq, :e, nil]].sexp),
cons(:t, true),
cons(nil, nil)
].sexp
# Evaluate an S-Expression and print the result
exp = [:reverse, [:quote, [:a, :b, :c, :d, :e]]].sexp
puts "EVAL: #{exp.lisp_string}"
puts " => #{eval(exp,env).lisp_string}"
The program will print:
$ ruby reverse.rb
EVAL: (reverse (quote (a b c d e)))
=> (e d c b a)
All I need to do is write a Lisp parser and a REPL, and I’m in business!
The Example in Standard Lisp Notation
If you found the Ruby-ized Lisp code hard to read, here is the reverse
funtions written in a more Lisp-like manner.
I received some feedback on the ‘Presenting Code’ post from
yesterday.
Presenting Code … An Update
I got lots of feedback on the “Presenting Code” post. In addition to
Cédric Beust’s initial comments, the
following people had something to say on the topic:
John Wilger asked on Twitter why I didn’t use
“file:” (rather than “http:” and a local web server). Unfortunately,
Keynote will not do a web view from a “file:” style URL.
Luke Kanies reports that he does something
similar. He uses Vim (rather than Ruby + the Syntax gem) to generate
the highlighted HTML. He also adds:
In general, this method works out great, but the one thing I
would say is that you should always uncheck “automatic update”.
Otherwise, you’ll find that it tries to update 10 seconds before your
presentation starts and your web server isn’t available.
Ok, that’s good advice. BTW, I would be very interested in a script
(AppleScript or Ruby+OSA) that would iterate over the pages in a
Keynote presentation and refresh all the WebViews. Any takers?
I noticed the following twitter conversation this evening between
objo and superchris:
superchris: any good recommendations on showing code samples in OpenOffice Impress?
objo: @superchris yeah, get a mac and use Keynote
objo: otherwise, I would screenshot emacs
superchris: @objo.. ya know, i almost added “And I’ll smack anyone who says get a Mac” but ran out of space
superchris: @objo… but actually your idea of using NetBeans screenshots is pretty good
objo: @superchris you never listen …. EMACS not netbeans. Come on man.
superchris: @objo just being helpful by translating for you.. :)
superchris: planning to code with NetBeans on linux
forever for no other reason but to annoy @objo
ScreenShots … Yuck!
The problem Chris is trying to solve is putting code snippets into a
presentation. There just isn’t a good way to do this in modern
presentation programs.
In the old days, I would generate my presentation completely in HTML
from a simple text markup file. The generation process was controlled
by rake. This allowed me to changed the code, run the unit tests and
rebuild the presentation all with a simple rake command. Eventually,
I got up to speed with CSS and could make some really nice looking
presentations, all from HTML.
Although I could get nice looking slides with CSS, it was a lot of
work getting it to work just so. Eventually, I abandoned that
approach and swithed to a modern slide presentation program (Keynote
in my case).
Although generating the slides is a bit easier in Keynote (or
PowerPoint, or Open Office Impress), reproducing code for technical
talks is much harder. You generally have two choices:
Cut and paste the code text into Keynote losing any syntax
highlighting you might have had, or
Take a screen shot of the code in your fancy editor, preserving the
syntax highlighting but losing the “text” nature of the code.
Neither option is pleasant. The former punishes the audience by
making the code harder to read, the latter punishes you making the
presentation hard to change. (I once saw Dave Thomas giving a Ruby
talk and he noticed that he had a minor typo in the code. He switched
to edit mode in Keynote with the intent of fixing it on the spot, then
he realized that the code was in a graphic image and was uneditable).
Of the two options, I’ve been using the text cut’n’paste technique for
most things. In the twitter conversation above, Chris is considering
the edit snapshot technique.
Other Options?
I’ve heard rumors of someone working on a script that will insert code
snippets into the Keynote data file directly. Unfortunately, as far
as I know, they are still rumors at this time.
But here’s another idea. I’ve prototyped this, and think it will
work. But be warned I haven’t tried this on a really presentation
yet.
Presenting Code … A Proof of Concept
While perusing the options in Keynote, I noticed an insert option called “Web View”
It turns out that this option allows you to include a web page in your
presentation. For example, here is my blog inserted directly into the
presentation. Clicking on the “web view” object will show an “update”
button that will refresh that page from the web.
So, all I have to do is get the code onto a web page, formatted nicely
with syntax highlighting, and Keynote will suck it into the
presentation, more or less automatically for me. Cool.
Getting it formatted is easy. That’s just a small little Rake task
with a good syntax highlighting library. I used Syntax (its a gem,
docs on Rubyforge), but there are other options out there.
Edit the CSS styles above to tweek the output to exactly the colors
you want. I’ve added a large font-size line to make the code big
enough for teh presentation (I hate small code fonts in presentations,
you can ask objo about my rants on that
topic.)
Now we need to get the code on a web page. No need to get fancy here.
I have a script called servefiles that will start a webrick process
that serves files from the current directory. Just start it up with
“servefiles 3333” (the 3333 is the port to use). Servefiles will
display its URL in its startup message, like so:
$ servefiles 3333
URL: http://tardis.local:3333
[2008-03-23 00:47:37] INFO WEBrick 1.3.1
[2008-03-23 00:47:37] INFO ruby 1.8.6 (2008-03-03) [i686-darwin9.2.0]
[2008-03-23 00:47:37] INFO WEBrick::HTTPServer#start: pid=874 port=3333
Here’s the code for servefiles:
#!/usr/bin/env ruby
require 'webrick'
include WEBrick
dir = Dir::pwd
port = (ARGV.first || (12000 + (dir.hash % 1000))).to_i
puts "URL: http://#{Socket.gethostname}:#{port}"
s = HTTPServer.new(
:Port => port,
:DocumentRoot => dir
)
trap("INT"){ s.shutdown }
s.start
Now all we have to do is cut and paste the URL given by servefiles
into keynote and append the HTML file name we wish to add to our
presentation:
Now, to update the code in the presentation, I need to:
Edit the original code base (and run unit tests against it).
Run rake
Press the “Update Now” button in Keynote.
Not bad.
It’s Just a Proof of Concept
Just be warned, I haven’t tried this in a real presentation yet. I’ve
just spent an hour or so seeing if all the pieces would work together.
There are some obvious things to explore.
The extraction code could be enhanced to pull snippets from files
based on tags. Or even better, being able to say “Extract Method m
from Class C”.
I’m using a fixed font size, but extract could easily take the font
size as an argument or even calculate the proper font size given the
amount of text found in the snippet.
I’ve not played with the “Update automatically” checkbox in the
Keynote dialog. I’m not sure when it automatically updates, but
it is possible that using it might mean you don’t even need step
three above.
I will probably experiment some more with then in my next code heavy
presentation. Let me know if you try this and how it work for you.
UPDATE
Cédric Beust points out that cutting and
pasting from Eclipse to PowerPoint does preserve syntax highlighting.
I verified the same is true for Eclipse and Keynote. However all the
other IDEs and editors I tried (NetBeans, Coda, TextMate, Emacs) will
paste as plain, uncolored text in Keynote. So, if you are going the
cut and paste route, you might want to consider using Eclipse for the
cut source.
Just for kicks I tried the presentation software in OpenOffice with
the same result. Eclipse copies will preserve highlighting, none of
the others will.
Ryan Tomayko has pointed out, my blog title does not conform to standard Ruby coding conventions. We need to fix this.
Ryan Tomayko has done a review of blogs using
code snippets as
there title and has pointed out that mine does not conform to
generally accepted Ruby coding standards. You see, in
“{ | one, step, back | }” I use spaces
between the vertical bars and the argument names. Proper Ruby code
would never be written that way.
He’s right. So in order to promote better Ruby coding practices, I’m
renaming the blog to “{ |one, step, back| }”.
Let it never be said that I ignore standards.
An aside: The use of {||} in the title was inspired by a
Smalltalk logo that used [|]. See the powered by banner at the bottom
of the sidebar in James Robertson’s
blog for an example.
Paul Graham issues the Arc Challenge … who could resist?
Paul Graham’s Arc Challenge
You can read about the Arc Challenge here: The Arc
Challenge. Go ahead a
read it now, but I will summarize the challenge.
Write a web program such that:
The first page of the program displays nothing but a text box and a
submit button. You enter some arbitrary text and press the submit
button, which takes you to …
The second page is nothing but a single link labeled “click here”.
The URL linked to must not contain the text entered in the first
step (i.e. you are not supposed to pass the text as a parameter on
the link). Clicking the link takes you to …
The third page which contains “You said: XXX” (where XXX is the text
you entered in the first step).
Here’s a screen cast demoing my solution to the Arc Challenge. (We
will show the code shortly).
Paul’s Solution
Paul has been working on designing Arc, his ideal programming language
for the future. Given Paul’s language preferences, it is no surprise
that Arc is very Lisp-like. Here is Paul’s solution written in Arc:
Paul points out that the solution is very short and elegant, only 23
nodes in the codetree. I’m sure I don’t quite understand exactly what
it is doing (I’d love to see a step by step explanation of the code).
He wonders what it would look like in other languages.
Several people have responded with solutions in their own languages.
I’ve seen a Smalltalk
Solution
as well as a Ruby solution (which
pretty closely mimics the Arc code from Paul) on the Arc Language
Forum page that was setup for
responses.
Continuation Web Servers
The Arc challenge is a perfect candidate for a continuation based
server solution. And I recalled that Chad Fowler and I had written a
demo continuation based server for the Continuations
Demystified talk we did at
RubyConf 2005. (Look for the “Poor Man’s Seaside Demo in that
presentation.) I wondered how easy it be to code up an Arc challenge
solution using that code base.
The key to a continuation based server is that it allows the
programmer to code in a linear fashion. All the request/response
nature of web interaction is completely hidden from you as a
programmer.
For example, let’s pretend we wanted to solve the Arc challenge using
a terminal and command line rather than a web based solution. How
would you write it? Probably something like this:
Simple, linear programming. (OK, printing “click here” is silly in a
text program, but you get the idea). You ask a question and read a
response. You pause for a click. You then tell the user what the
result is.
Ask. Pause. Tell.
Those are our basic abstract operations for this problem. Lets
rewrite our text based solution using these abstractions. We’ll put
this in a file called “arc_challenge.rb”.
Conversation.interact do |io|
text = io.ask
io.pause("click here")
io.tell("You said: #{text}")
end
I’ve introduced three operations (methods) that are provided by an I/O
object (let’s ignore the interact line for now). “ask” will ask the
user for input, returning the string. “pause” will pause until the
user indicates he/she is ready to continue (e.g. pressing return in our
command line version). “tell” sends the given string to the user.
So, what does “Conversation.interact” do? It creates the environment
where the user have a conversation with the program. The interation
is controlled through our ask/pause/tell functions provided by the I/O
object passed to the interact block.
Here is an implementation of a text based conversation.
class TextBased
def interact
yield(self)
end
def ask(prompt=nil)
print prompt, " " if prompt
gets.chomp
end
def pause(prompt="")
print prompt, " " if prompt
gets
end
def tell(message)
puts message
end
end
Conversation = TextBased.new
To run the text based conversation, just require the text. Here’s a demo:
Arc on the Web
Well, anybody can solve the challenge in text mode. How much work do
we have to do to get it on the web.
The answer: Zero!
The code Chad and I wrote for Continuations
Demystified includes a
web-based version of the conversation object that is ready to go. All
we have to do is plug it in and run it. No changes are required to
our basic Arc challenge solution.
Again, a screen demo:
Yes, we know that although we now have our Arc Challenge on the web,
we haven’t quite conformed to the exact requirements of the challenge.
We will handle that next.
The Final Arc Solution
The problem is that the current Web based conversation object makes
all kinds of assumptions that are not appropriate for the final Arc
solution.
In particular, we need to change:
Get rid the head line, restart link and other extraneous HTML
elements.
Don’t keep a running log of the conversation. When you move to a
new page, you start from scratch.
The “click here” should be a real link, not just a text box where
you can press enter.
To get to here, we will have to make some modifications to the
conversation web library. It turns out the changes are pretty
straight forward. The whole interaction framework is controlled by
the Conversation object that implements ask/pause/tell methods. You
can see the changes made for the Arc challenge in the
“noecho_web_based.rb” file (see the end of this post for the
availability of the source code).
The Final Conversation Based Solution
In cased you missed it, here is the Arc Challenge Solution:
Conversation.interact do |io|
text = io.ask
io.pause("click here")
io.tell("You said: #{text}")
end
Yep, it’s the exact same file we used for the text based solution. I
don’t know if it is as elegant as Paul’s version, but I certainly find
it easy to read and understand. (Rerun the very first screen
cast in this posting if you want
to see it in action again).
If you want to look at the code, there is a
tarball available
that contains all the continuation server demo code from
Continuations Demystified
talk, as well as the two new files I added for the Arc challenge.
“arc_challenge.rb” is the actually solution and “noecho_web_based.rb”
is the conversation library that renders the solution in the style set
forth by the challenge.
Erlang defines functions by listing a set of possible argument lists
and the body of the function to be executed for each argument list.
For example, the factorial function might be defined in Erlang as:
factorial(0) -> 1;
factorial(N) -> N * fac(N-1).
If factorial is called with a 0 (zero) for an argument, the first
argument list will be chosen and the value of the factorial function
will be 1. Otherwise, the value returned will be calculated by a
recursive call to factorial.
FlexMock and Erlang
While playing around with FlexMock the other day, I realized that it
does parameter matching, much like Erlang, when deciding what mock
method to call. So I started wondering if you could write Erlang-like
function definitions in FlexMock.
The deadline for the proposals is August 20. However, I have it on
good authority that the deadline will be extended to Aug 23, 5:00 pm
EST. (Ahh … I see the announcement made it to Ruby-Talk) So you still have some time.
Some Hints
RubyCentral has been having some problems with getting their
registration responses delivered (I found my registration confirmation
in GMail’s spam box). I would recommend that you go ahead and
register a proposal now, even if you don’t have all the details ready.
By the time you are ready to submit the final version, you won’t have
to worry about any last minite registration hassles.
Good luck with your proposals. I hope to see you at RubyConf!
This is on my MacBook Pro. How in the world to you go from this HTML:
As Rendered in the Browser
To this in the browser?
Look carefully at the sequence of digits for the default font.
This happens in both safari and firefox. Javascript is disabled.
Disabling CSS will cause all 7s to look like 9s (because everything is
then in the defaualt font).
Huh?
Any clues on how to fix this would be welcome.
Update
Several people have reported they can’t reproduce it. Here is
additional information:
Mac OS 10.4.10
Firefox 2.0.0.6
Safari 3.0.3
Also, copying and pasting what looks to be “0123456979” into a text
editor will give “0123456789”. Perhaps a font is corrupted so the “7”
is displaying as a “9” glyph?
Update 2—Problem Fixed
John Guenin suggests: Try resetting your font caches:
http://www.jamapi.com/pr/fn
Thanks John. I downloaded FontNuke from the link provided and
although the program itself was a bit flaky, I finally got a clean run
from it and after rebooting the problem has been fixed. So the
verdict is that it was probably a bad font cache that was displaying
the “7” glyph incorrectly.
Just wanted to drop a quick note that a new version of FlexMock is now
available.
There are two nice enhancements and a minor bug fix in this version.
The first enhancement is for mocking ActiveRecord objects. The folks
at EdgeCase use a mockmodel() method for the RSpec mock that returns a
mock that has some common ActiveRecord methods mocked (stubbed) with
some reasonable values. This make is a bit more convenient when
mocking Rails models. FlexMock now supports this natively, just say
flexmock(:model, YourRailsModel) to create a mock object
that mimics a YourRailsModel object.
The second enhancement is in regard to the What Should
flexmock(real_obj)
Return?
question I blogged about last May. I asked the question: What should
flexmock(real_obj) return, the real object or the mock object?
Someone had suggested returning the real object when flexmock() is
given a block. There was some positive response to that, so that was
included in the FlexMock release.
But after several months of using it, I found it difficult to remember
which version of flexmock() returned what. At one point I found
myself caling flexmock() with an empty block, just to get the real
object back. That was madness.
So starting with release 0.6.4, flexmock will always return the real
object. This is the best of both worlds, but it comes with a small
price. Real objects partially mocked by FlexMode will now be enhanced
with some extra methods, just enough methods so that addition mock
behavior can be added to it. For example, should_receive
is added to the partially mocked real object. This pollutes the
method namespace for an object, but the result is much simplier for
the programmer to use. If you really want to avoid method namespace
pollution, there is a :safe mode offered. Read the docs for all the
gory details.
By The Way, If You Grabbed Version 0.6.3 …
If you are one of the handful of people that downloaded verion 0.6.3
yesterday, then go ahead and grab 0.6.4. The only difference is in
the API for mocking ActiveRecord models. After using it for a bit, I
realized that the API could be improved, hence version 0.6.4. Sorry
about that.