Alieniloquent

I wanted to share a snippet of code. This code will print a call stack to STDOUT every time a Ruby class definition is evaluated. It is particularly useful when you find that class constants are being mysteriously redefined.

class Foo
  puts "\nRequired from:\n  #{Kernel.caller.join("\n  ")}"
  # ...
end

What inspired me to write that code? Rails did. The key to writing Ruby on Rails is that you’re writing Ruby on Rails. You don’t follow the Rails best practices because they’re convenient. You follow the Rails best practices because your program won’t work unless you do. Just like trains, you stay on the track and everything is great. If you try to take your train off-track, then it’s gruesome enough to make the nightly news.

How did I derail my application such that I cared how and where a file was being required? I wrote a unit test that explicitly required a model object. Oops. Remember that the semantics of require is load-once based on the name. So:

and:

are very different to require. Rails is super helpful and requires everything that it makes for you. So it requires models for you, even when you run your unit tests.

So take this code:

class Foo < ActiveRecord::Base
  RAILS_IS_A_GHETTO = true
end

And then write a test for something that Rails didn’t generate (such as something in the lib directory like I did):

# Require some other stuff
require "foo"

class TestTruth < Test::Unit::TestCase
  def test_truth
    assert true
  end
end

If you rake test you will get an error complaining that RAILS_IS_A_GHETTO was reinitialized, and that’s because Rails loads it for you as “models/foo” and you load it as “foo” so it gets loaded twice.

The moral of the story is: let Rails load the things it built, and you load the things you built.

I’ve been using Macintosh computers for several years now, but I came to them from the Unix world. There were several expectations I had from my terminal emulator. Among them were that the key that says Alt on it should be my Meta key for Emacs key-chords, and that the Page Up and Page Down keys should page up and page down in my application. None of those behaviors are the default, so fixing them is one of the first things I do when I get a Mac.

In Leopard these settings are all in the Settings section of Preferences (Cmd-, or Terminal > Preferences…), but in previous versions they are in the Window Settings screen (Terminal > Window Settings…).

First, to take care of the Alt key issue, go to the Keyboard section of the settings. There is a checkbox toward the bottom that says “Use option key as meta.” Check it.

With that problem solved, all that is left are the paging keys. The default behavior is to have Shift Page Up send Page Up to the terminal and Page Up and do the same for Page Down. In the Keyboard Settings you should see a grid with keystrokes on the left and text on the right. In many cases it will be an ANSI escape sequence to send to the terminal, in some cases it will be a special action. Here’s what you want to set things to.

• page down = send string to shell: \033[6~
• page up = send string to shell: \033[5~
• shift page down = scroll to next page in buffer
• shift page up = scroll to previous page in buffer

That effectively just swaps the keys, so that you still have the ability to scroll your Terminal buffer with the keyboard.

After I fix the keyboard, I like to fiddle with colors and other things, which will all be in the same preferences dialogs. Then, after all the tweaks and fixes, Terminal is ready to use.

I have joined up with some of the guys from ODYNUG who have started meeting for breakfast and learning Common Lisp together. We are all using some version of Emacs, SLIME, and SBCL.

Blaine shared a cool way to make SLIME load much faster by taking advantage of the fact that Lisp uses images like Smalltalk (or more accurately, Smalltalk uses images like Lisp). He posted it for the group to see, but I wanted to post it here for my readers.

SBCL allows you to specify an image, or as they call it a core, by passing the --core option along with (as far as I can tell) an absolute path to the core file (well, at least it doesn’t know that ~ means $HOME). It, of course, also provides a way to create these core files, so you can load a bunch of stuff in, and then save a core file that has all of that already loaded.

So first, go into your SLIME directory and copy swank-loader.lisp to swank-loader-original.lisp. Then make swank-loader.lisp look like this (changing slime-dir to be wherever your SLIME is, of course):

(if (not (find-package 'swank-loader))
    ;; Edit SLIME-DIR to be where you have SLIME installed.
    (let ((slime-dir (merge-pathnames ".elisp/slime/" (user-homedir-pathname))))
      (load (merge-pathnames "swank-loader-original" slime-dir))))

Then, make a file called bootstrap.lisp with the following content:

;; Load Swank
(load (merge-pathnames ".elisp/slime/swank-loader" (user-homedir-pathname)))

;; Save image
(sb-ext:save-lisp-and-die "sbcl-with-slime.core")

And run this command:

$ sbcl --load bootstrap.lisp

Then copy sbcl-with-slime.core somewhere safe, I put mine in with my slime code to keep it all together. Then you just have to add the following to your .emacs:

(let* ((slime-dir (concat elisp-dir "/slime"))
       (core-file (concat slime-dir "/sbcl-with-slime.core")))
  (setq inferior-lisp-program (concat "sbcl --core " core-file)))

Then you can M-x slime and it will be super fast.

Yesterday I was reminded the importance of familiarity and comfort with my tools. Over the years I have developed a set of configurations that work for me. I have configurations for BASH and I have configurations for emacs and they help me be productive. Yesterday I started configuring my new computer here at my new job (yes I got a new job) and I couldn’t get to them because they were on my laptop at home.

Several years ago I had a system that involved keeping all of my config files in a Subversion repository and a shell script to make symlinks from the real locations to the ones in ~/.config. I eventually stopped using it, mostly because it was a little clunky and hard to get set up on new machines. Last night I devised a similar system but tweaked a few things and it has made it so much better.

The first thing I changed was the revision control tool. I’m using darcs as the version control. It is a distributed version control system and it is much simpler to use. To top it all off, it does not put a directory in each directory I add to my repository, it just puts one _darcs folder at the top level. To top it all off, it’s written in Haskell, so it gets cool points for that.

The second thing I tweaked was that instead of using symbolic links I’m using hard links. This means that both ~/.bashrc and ~/.config/home/.bashrc are actually pointing to the same file on disk. So I can update the darcs repository and the linked files out in the rest of my home directory will get updated too, but if I delete the repository, I’ll still have copies of the config.

Last, instead of keeping a flat list of files like ~/.config/bashrc and ~/.config/ssh_config, I’m keeping the files in a directory with their exact file names and the directory structure that they’d be stored in under my home directory. This makes writing the linking script much easier.

So with this structure in place I wrote an update script that makes directories and hard links so that what’s in my home directory mirrors what’s in my config repository. I even protected against files already existing with a friendly prompt (courtesy of ln -i).

A darcs repository of my config, including the update script, is available here.

Alonzo Church invented the lambda calculus. He also figured out how to encode many kinds of data as lambda expressions. Take your simple booleans, for example.

This is true:

fn x y. x

And this is false:

fn x y. y

That makes the identity function the if then else construct:

> (fn p. p) (fn x y. x) a b;
a
> (fn p. p) (fn x y. y) a b;
b

And similarly you can get a logical and:

> (fn p. p) ((fn p q. p q p) (fn x y. x) (fn x y. x)) a b;
a
> (fn p. p) ((fn p q. p q p) (fn x y. x) (fn x y. y)) a b;
b
> (fn p. p) ((fn p q. p q p) (fn x y. y) (fn x y. x)) a b;
b

Fiddling around with these church booleans revealed several bugs in my code, which I’ve fixed. I’ve additionally added a new node to the parse tree to represent the () grouping that is typed into the code so that when it is formatted for display it looks better.

You can get the newest code here.

One of the first things I wanted to do to improve the readability of my language was to add the currying of function parameters. Since it is such a common pattern to have three or four abstractions right in a row to bind variables, there is a syntax for expressing them more consisely.

So this:

fn x. fn y. fn z. x y z

Becomes this:

fn x y z. x y z

Adding the code do this was nearly trivial, and all in the parser. First I wrote a function that given a list of variables and an expression for the body, would be able to construct the parse tree for a curried function:

let curry ids body =
  List.fold_right (fun id expr -> Abstraction(id, expr)) ids body

Then I took the existing production for recognizing expressions:

expr:
  aexprs {apply $1}
| FN VAR PERIOD expr {Abstraction ($2, $4)}
;

And turned it into this:

expr:
  aexprs {apply $1}
| FN ids PERIOD expr {curry $2 $4}
;

ids:
  VAR {[$1]}
| VAR ids {$1::$2}
;

That ids production is using the OCaml :: operator which performs the cons operation. So as I recurse on the right, I’m building up a list and consing each new id onto it all the way up.

And just like that I’ve added currying to my language.

Earlier this fall I wrote a little functional programming language. However, the guts of it were not based on the lambda calculus. I used more of a denotational semantics approach to the evaluation, which worked fine. But, I still wanted to implement an actual lambda calculus interpreter.

So, now that I am done with school and have some free time, I threw a little something together. I used it as an introductory project to OCaml, and really enjoyed writing it.

So what is the lambda calculus, you might ask?

There are three basic concepts in lambda calculus. There are variables:

x

There are abstractions:

fn x. x

And there are applications:

f x

Applications are left associative so:

f x y

is the same as:

(f x) y

So for a more complicated example from the REPL:

> (fn f. fn x. f x) (fn y. y) z;
z

The first part declares a function which binds f and returns a function which binds x and returns the application of f to x. We pass to that the identity function (fn y. y) and the variable z. That all reduces to just z.

You can download my code here. I will be posting snippets of it in future posts. I will also be blogging as I extend it to add more features.

An update came down from Gentoo for Samba updating it to version 2.0.26a. We had been having trouble with a problem in 3.0.24 that had been fixed in a intervening release of Samba. So, naturally, I wanted to upgrade. But when I did, I got this mysterious error in my log.winbindd.

[2007/11/19 13:27:16, 0] nsswitch/winbindd.c:request_len_recv(517)
  request_len_recv: Invalid request size received: 2084

I have spent the entire day googling and yahooing and searching and grepping to no avail. Nothing I have tried worked. Now at one point I was reading and somebody said “reboot, some other services are using stale references to libnss_winbind.so.” I couldn’t imagine that was right, because if I rolled back to 3.0.24 everything worked again.

Well, through a course of events I ended up with the following line in /etc/nsswitch.conf:

shadow: shadow

As you can imagine, that didn’t work too well for my unix user that I keep on the box for when ADS is hosed. So I broke out the trusty install CD, rebooted, and fixed the file. I then rebooted and re-emerged samba. I thought I had put the mask in /etc/portage/package.mask to make sure it was 3.0.24 I was installing, but I hadn’t. Lo and behold everything worked.

All I had to do was reboot.

That was it.

So I got my language working. But there are still some things I want to add to it. One thing that was bothering me was that both this code:

fn x => x

and this code:

x => x

parsed to the same thing.

I banged my head against this. My grammar had the production right:

expr : ...
     | FN ident RARROW expr (T.FnDef (ident,expr))
     ...

and my lexer produced the tokens just fine:

<INITIAL> "fn" => (Tokens.FN(!pos, !pos));
<INITIAL> "=>" => (Tokens.RARROW(!pos, !pos));

So, I was confused. I downloaded the source for SML/NJ in hopes that their grammar and lexer would shed insight on what I was (obviously) doing wrong. But, inasmuch as SL is like SML, the grammar and lexer were the same.

Sleep beckoned, so I went. This morning I banged my head at it some more. Then once I started combing over the documentation, it hit me. ML-Yacc produces error-correcting parsers. It will perform single-token substitutions in order to get a valid parse. And, if you notice, it only has to make a single-token correction to get from the bad code to the good code.

My solution? The same as SML/NJ’s, set the lookahead to zero for interactive sessions and fail fast, so that if you are trying stuff interactively (or from unit tests) it will be relentless about grammar. On the other hand, if you are parsing a file, my interpreter will be forgiving. After all, why should it fail the whole file if all you’re missing is fn?

So I’m taking “Principles of Programming Languages” at UNO with Dr. Winter. There is a group project, and he is letting me do the project on my own. The project is to make a small imperative (and Turing-complete) language.

Well, as you may or may not know, I’m crazy about functional languages. I love them. So, while I have to write an imperative language for the project, I decided to spend some of the precious free time I have writing a functional one instead. As of now, my language (Samuel’s Lambda, or SL for short) is Turing-complete.

My test for this was that I could calculate the factorial using the most venerable of functional programming tools: the fixed point combinator (a.k.a. the Y combinator).

For my example of recursion, I’ll show you the factorial. What sort of discussion of recursion would this be if I didn’t?

let
  val y = fn f =>
      (fn g => g g) (fn g => f (fn x => g g x))
  val fac = fn f =>
            fn n =>
               if eq n 0 then 1
               else multiply n (f (subtract n 1))
in y fac 5
end

When run at the SML/NJ prompt:

- SLParser.evalPrintFile("examples/factorial.sl");
120
val it = () : unit

It helps that I’m working with a functional language to start with. That makes implementing things such as closures and let nearly trivial. I’m going to add static type checking (sans-inferencing like ML after which the syntax has been modeled) and then I’ll be done with SL. It has been a fun little exercise.