Thursday, July 31, 2008

Computer Science: How to Implement Compilers and Interpreters

I'm stuck.

I just finished watching the SICP lectures. They were really good. (Thanks Mike Cheponis!) I've written partial implementations of Lisp in Python (thanks to PLY and some creativity) and Haskell (thanks to Write Yourself a Scheme in 48 Hours). I'd like to get a lot more serious about implementing languages, but I'm stuck.

I know that EOPL is a really good book. So is the dragon book. I've started both of them at separate times and gotten discouraged. One main problem is that I can only work on this stuff between 12-3AM because of work and kids, so I don't have enough time or enough mental energy. Currently, I think my options are:
  • Give up until I magically have more time one day.
  • Start working on EOPL and plan on it taking several years.
Is there a more approachable book that will still teach me what I need?

One thing I'm really afraid of is that I'm always at risk for burnout, and I'm really afraid EOPL will send me over the edge. On the other hand, I really haven't given up on the dream of being a decent language implementor, and EOPL is the most direct route to making that happen.

With my constraints in mind, can you lend me some advice? Thanks!

Monday, July 28, 2008

Computer Science: Arbitrarily Fine Locking

This is a relatively simple idea concerning mutex usage. I imagine someone else has probably thought of it before. However, since I just thought of it, I figured I'd blog it. I have no clue why I was thinking about mutexes. I usually prefer share-nothing approaches like Erlang. Note, I am specifically not trying to comment on Python's GIL.

Imagine you have a bunch of resources (like objects or structs) that you wish to protect. One way to protect them is to use a single mutex. This is called coarse-grained locking. At the opposite end of the spectrum, you can create a new mutex for every resource. This is called fine-grained locking. However, what if you want something in the middle?

Having a single lock is unfortunate because it forces a lot of your code to be effectively single-threaded, even if you have multiple processors. However, perhaps creating a new mutex for every single resource might be overkill. (Personally, I'm unsure of why that might be the case.)

Here's an approach to get arbitrarily fine locking. Create N mutexes (where N is tunable). Protect each resource using mutex number resource_id % N. The resource_id could be whatever, as long as it's unique. Perhaps it's the index of an array, or perhaps it's a pointer to the resource in memory.

And now for something completely different! The best part of Lisp is that it has garbage collection. It recycles garbage so that you can grow new trees ;)

Wednesday, July 23, 2008

SICP: not not but rather unless

What happens if you search for "not foo" on Google? Surprisingly enough, it works, but it doesn't lead to what you might expect. It leads to pages that contain the phrase "not foo". If you want pages that don't contain the word "foo", the syntax is "-foo". Of course, if you type in "-foo" by itself, you don't get any interesting results. Rather you have to write something like "spam -foo", which leads to pages that contain the word spam, but not foo.

While I was at Foxmarks, I had to implement the logical operators for our own search engine, which is where I originally encountered this problem. If the user asks you for "not foo", you really can't efficiently give him any sort of answer. It only works if the user tries something like "spam and not foo", which is what I implemented.

The SICP lecture I was watching last night was about implementing logic languages like Prolog in Lisp. The same problem happens there. "(not)" in that language acts as a filter. Hence, "(and (color ?c) (not (color blue)))" works, but "(not (color blue))" doesn't. It's the same problem. It's efficient to implement "not" as a filter, but not efficient to let the user ask for everything in the database filtered by "not".

I think the problem is that the word "not" is a bit misleading. If you don't understand its limitations, you might write something like "(and (not slow) (not buggy))", and find out that your code is either slow or buggy.

Drum roll please: I suggest using not "not", but rather "unless". That is basically what Google does, but they use "-" as syntax. It makes sense to write "spam unless foo" or in Lisp "(unless (color ?c) (color blue))". Since "unless" is a binary operator, it forces you to think in the right direction.

Ok, enough about that. Here are some other thoughts.

Last night I realized just how similar SPARQL (a query language for RDF) and MQL (the query language for Freebase) are to Prolog (or at least the logic language I saw last night). All three use "query by example" in order to query graph engines. You give it a pattern, and it checks against everything in the database looking for matches. If something matches, it gives you your original query back, but with all the blanks filled in.

For instance, the language last night let me write "(employee ?name (computer ?subdept))" to find all the employees who work in the computer department. It responded with a list of things like "(employee (Joe Hacker) (computer r-and-d))"

Here's a similar query in MQL:
"type" : "/music/artist",
"name" : "The Police",
"album" : []
It says give me all the albums by the musical artists "The Police".

I know that SPARQL (at least what little my buddy Drew Perttula has shown me) even allows you to express rules like Prolog does. For instance, (hand waiving) "if A's son is B, and B's son is C, then A is C's grandfather, and C is A's grandson". I can only guess that Prolog had some influence on MQL and SPARQL, but of course I don't know for certain.

One last comment. The "MIT opinion" on Prolog is "interesting". When backed into a corner and forced to comment, Abelson said something like "We wrote a logic-based language like Prolog back in 1971. After about six months, we decided it was not the right thing for various reasons. When Prolog came along, we figured they had fixed all those problems, but it turned out they hadn't. Now, what makes Prolog really nice is that it's fast because of really excellent compiler technology." Heh, interesting.

Tuesday, July 22, 2008

Software Engineering: Agile Programming and IDEs Considered Harmful

Put away your IDE, code using a pencil, and do a big design up front. Get it right the first time. It can be done. Naturally, I'm trolling a bit, but that link is a very short, very fun read.

It reminds me of an interview with Donald Knuth that I've been thinking about a lot lately. Knuth said:
With the caveat that there’s no reason anybody should care about the opinions of a computer scientist/mathematician like me regarding software development, let me just say that almost everything I’ve ever heard associated with the term "extreme programming" sounds like exactly the wrong way to go...with one exception. The exception is the idea of working in teams and reading each other’s code. That idea is crucial, and it might even mask out all the terrible aspects of extreme programming that alarm me.
Somehow André Bensoussan and Donald Knuth are both capable of designing everything up front, and just getting it right. Since I've always been an agile coder, I find such stories amazing. I wonder if Bensoussan would still work that way these days. The systems are larger, the libraries are less stable, the timelines are shorter, and there are more people you have to integrate with.

Saturday, July 19, 2008

SICP: Broken Math

Here's a great little math trick from SICP:
v = 1 + 2 + 4 + 8 + ...
Let's play around with that equation a bit:
v - 1 = 2 + 4 + 8 + ...
(v - 1) / 2 = 1 + 2 + 4 + 8 + ...
But that's the same as the first line. Hence, we see that:
(v - 1) / 2 = v
Solving for v, we get:
v = -1
-1 = 1 + 2 + 4 + 8 + ...
Crazy, eh? Sussman said:
Arguments that are based on convergence are flaky, if you don't know the convergence beforehand. You can make wrong arguments. You can make deductions as if you know the answer and not be stopped somewhere by some obvious contradiction.
I think the bad assumption in this case is thinking that some v could exist and be a normal integer. Clearly, there is no such normal integer v that equals 1 + 2 + 4 + 8 + ...

Thursday, July 17, 2008

SICP: Lisp Inspired Python

I just finished the lecture on streams in SICP. Python has generators, which are quite lovely. However, it's fun to imagine reimplementing generators in various ways from scratch using some of the approaches in SICP.

First of all, there are promises. A promise says that you'll do something later. In Scheme, you create a promise with "delay" and you invoke that promise with "force":
> (delay (/ 1 0))
> (force (delay (/ 1 0)))
division by zero
Here's one way to translate that to Python:
class Promise(object):

"""This is a promise to execute something on demand."""

def __init__(self, f):
"""Wrap your expression in a lambda and pass it as f."""
self.f = f

def __call__(self):
"""Call the instance to get the value of the promise.

This is memoized so that it doesn't have to compute the value
more than once since promises shouldn't do that.

if not hasattr(self, 'result'):
self.result = self.f()
return self.result

promise = Promise(lambda: 1 / 0)
print repr(promise)
print "No error yet."
print "Now, we'll force the promise, causing the error."
Easy :)

Now, let's take a look at a generator. Here's a simple counter:
def generator(start=0):
while True:
yield start
start += 1

for i in generator():
print i
Clearly, you can do this with an iterator class. However, let's instead use a closure and continuation passing style. The syntax isn't the most beautiful in the world, but it definitely does the trick ;)
def generator(start=0):
scope = locals()

def top():
while True:
return scope['start'], bottom

def bottom():
scope['start'] += 1
return top()

return top

next = generator()
while True:
(i, next) = next()
print i

Tuesday, July 15, 2008

Lisp: List Comprehensions

Whenever I explain Python's list comprehensions, I always say that they were taken from Haskell. Apparently, Lisp had them too using a syntactic sugar construct called collect. Here's the Python:
[(i, j, i + j)
for i in range(1, n + 1)
for j in range(1, i - 1)
if is_prime(i + j)]
And here's the Lisp:
(list i j (+ i j))
((i (enum-interval 1 n))
(j (enum-interval 1 (-1+ i))))
(prime? (+ i j)))
I found this in SICP, but I'm a little confused about exactly which dialects of Lisp and Scheme it's present in. I doesn't appear to be in R5RS.

Monday, July 14, 2008

Software Engineering: Facebook Thrift

I read Facebook's Thrift Whitepaper. Thrift is, basically, Facebook's open source replacement for CORBA. In short, it looks fine.

The whitepaper mentions CORBA only very briefly: "Relatively comprehensive, debatably overdesigned and heavyweight. Comparably cumbersome software installation."

Thrift feels very C++-ish. For instance, they use Boost. The Thrift IDL compiler is written in C++ with Lex and Yacc. They also implemented their own C++ thread primatives, including Mutex, Condition, and Monitor. The whitepaper also discusses their threading and memory management issues in C++.

They have an interesting scheme for versioning APIs such as struct fields and function parameters. They put numbers on the fields so that if a client and server aren't currently running the same version of the IDL, things can continue working. This is important for rolling upgrades. Here's an example:
struct Example { 
1:i32 number=10,
2:i64 bigNumber,
3:double decimals,
4:string name="thrifty"
That was, perhaps, the most surprising thing to me. I was having BASIC flashbacks. I assume that if you need to delete a field, you just delete the whole line and leave a gap in the numbers.

However, an interesting case arises. What happens if you delete field 4 in the above example, and someone else unknowingly adds a new field, reusing the same id? It's probably important to leave a comment in the code saying which is the highest id that has been used so far.

I don't think I would have used numbers. Instead, I would have used a "deleted" keyword. Of course, numbers could still be used in the implementation, behind the scenes:
struct Example { 
i32 number=10,
deleted i64 bigNumber,
double decimals,
deleted string name="thrifty"
Perhaps they thought of this too, but there's some reason they dismissed it. For instance, it is sort of ugly to have those "deleted" lines, and you can only add new fields at the end. Heh, I guess this is one time where numbers actually enhance readability ;)

Anyway, I didn't actually try it out, but I'm sure it's fine.

Thursday, July 10, 2008

Python: A Few Decorator Tips

Here are a few tips for working with Python decorators.

Here's a simple Python decorator, along with some code using it:
def logged(f):

def wrapped(*args, **kargs):
print "I'm calling %s." % f.__name__
return f(*args, **kargs)
print "Done."

return wrapped

def sum(a, b):
return a + b

sum(1, 2)
If you run this, you get:
I'm calling sum.
Notice the way I used try, return, and finally. I'm either very cool or very naughty. It's hard to know.

The decorator package can make simple decorators (i.e. ones that don't have any of their own arguments) like this even easier:
from decorator import decorator

def logged(f, *args, **kargs):
print "I'm calling %s." % f.__name__
return f(*args, **kargs)
print "Done."

def sum(a, b):
return a + b

sum(1, 2)
Notice, I didn't need to write a "wrapped" function.

Furthermore, it preserves the method signature. In the first case, "help(sum)" says "wrapped(*args, **kargs)". In the second case, it says "sum(a, b)", which is better.

As a final tip, what happens if there's a decorator that contains some code, and you want to call it as if it were a normal function? This might happen if you want to call the decorator from the middle of some other function. Here's how:
def sum(a, b):
return a + b

logged(sum)(1, 2)
It makes sense once you think about it.

Lisp: Pattern Matching

As I mentioned earlier, I'm making my way through the SICP lectures.

Today, I'm excited about pattern matching. For instance, consider this:
(define deriv-rules
( (dd (+ (? x1) (? x2)) (? v))
(+ (dd (: x1) (: v))
(dd (: x2) (: v))) )
It says that the derivative of x1 + x2 with respect to v is the derivative of x1 with respect to v + the derivative of x2 with respect to v. Notice, it's all data. "No 'if' statements were harmed in the making of this film" ;)

I've played around with Haskell, Ocaml, and Erlang, so I'm familiar with match
statements. They make sense. However, I had never seen someone implement such a system, especially in such an elegant manner.

I'm so used to coding like "if this, then do this". Pattern recognition is all about "if the data matches this pattern, fill in this skeleton and then start over." I feel like I've just been "meta'd".

I've been thinking about how I might apply these things to C. A closure is a struct with a function pointer and a void * to hold some data. A continuation is a stack (perhaps an array) of closures. I would have never thought to code that way in C. However, now that I've seen it in Lisp, it just makes sense.

Of course, major props go to the graph database team at Metaweb. They actually *do* code that way in C, and the coder who started that code base is a woman ;)

The last thing I'd like to say is that it's funny watching the professors teach. They're so confident. They say things like "it's very simple" all the time. That's because they have the material mastered. They know where they're going. Researching is quite the opposite. You don't know where you're going. You don't know if there even is an answer. You're often wrong. It's a lot of fumbling around hoping something's going to work. Since MIT professors spend so much time both teaching and researching, it would seem they must have a bit of a split personality.

As a last statement, I don't know how those students survive without pause and rewind! Seriously, it takes me at least two hours to watch a one hour lecture! Watch, pause, think. Rinse and repeat.

Wednesday, July 09, 2008

Linux: Running Paster under runit on Ubuntu

I needed to setup Paster, Pylon's default Web server, on Ubuntu. I had a heck of a hard time deciding whether I wanted to run it under Supervisor, daemontools, monit, runit, or a handmade rc script.

Supervisor has been getting a lot of press lately, but I couldn't find a standard way of starting it on Ubuntu. This seemed like a chicken and egg problem. Furthermore, I knew my buddy Mike Orr was having a hard time getting log rotation working with it.

I wanted something that could restart my process as necessary, so I decided against a standard rc script, even though I knew Paster has a --monitor-restart option. I eventually settled on runit. I had used it in the past, the directions were clear, and it just "felt right". My buddy Allan Bailey even gave me a quick cheat sheet.

If anyone can show me a nice comparison of all of these options, I'd love to read it. I wasn't able to find much on Google that compared them all.

Anyway, here's what I did in outline form:
Setup myapp under runit:
Setup logging:
mkdir -p /etc/sv/myapp/log
mkdir -p /var/log/myapp

cat > /etc/sv/myapp/log/run << __END__

exec 2>&1
exec chpst -u www-data:www-data svlogd -tt /var/log/myapp

chmod +x /etc/sv/myapp/log/run
chown -R www-data:www-data /var/log/myapp
Setup Paster:

cat > /etc/sv/myapp/run << __END__

exec 2>&1
cd /home/myproject/source/trunk/myapp
exec chpst -u www-data:www-data paster serve production.ini

chmod +x /etc/sv/myapp/run
ln -s /etc/sv/myapp /etc/service/
Setup /var for the app:
mkdir /var/run/myapp
chown -R www-data:www-data /var/run/myapp
Edited various directory settings in production.ini.

Tuesday, July 08, 2008

Lisp: Hackable by Default

I'm watching the MIT lectures for the Structure and Interpretation of Computer Programs which my buddy Mike Cheponis was nice enough to give to me. I noticed a few interesting things.

In C, it's common to write "x->a". x is a pointer to a struct with a member a. In Lisp, you'd write (a x). a is a function that operates on some object x in order to return a value. That means that, by default, "a" has some "wiggle room" to do something special because it's a function. That's why in Java, the norm is to use getters and setters for everything. It provides "wiggle room" which I also call "hackability". In languages like Python, Ruby, and C#, "x.a" might or might not be an actual function call because those languages support properties. Depending on the details, in languages with inheritance, you might even say there's an extra dimension of hackability. For instance, in Java, x.getA() might be extended by subclasses.

One of the lectures covered symbolic manipulation of algebraic expressions. That means writing a system that can recognize that "(+ x x)" is the same as "(* x 2)". The professor had a procedure make-sum. "(make-sum x y)" is pretty straightforward. Under the covers, it returns "(list '+ x y)". However, he showed that there's no reason make-sum shouldn't be smarter. For instance "(make-sum x 0)" should really just return x. Internally, I was thinking of make-sum as a Java-like constructor for some class named Sum. However, a Java constructor can't just return x. It has to return an instance of the Sum class. Hence, if you were coding this in Java, you wouldn't use a constructor. You would use a static method that returns an Expression, where Expression is some interface. My point is that in Lisp make-sum is just a constructor, and constructors in Lisp by default have the freedom to return an instance of whatever they want. That means they're hackable by default.

I have one more thing I'd like to mention. Look at the image. This was filmed in 1986. First of all, it's amazing to me that something filmed 22 years ago is still very interesting and relevant to me today. It's even more amazing to consider that Lisp started in 1958. However, what's intriguing is that there are several women in the class. Not just one or two, but several. Where'd all the women go? There are so few female programmers these days.