Alieniloquent

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.

You may have noticed that my layout changed a little. I got rid of my Google ads.

I’ve noticed that when I paste code snippets or other bits of pre-formatted text that is narrower than 80 columns, I still get a horizontal scroll. That was because my content area was simply too narrow. I intend to be posting more code, so I started looking for ways to get some space.

Changing the layout to only have one column on the right was a start. I was simply going to move the google ads down, but then Erica asked me how much money I was making off of them. The answer is not much at all. So I just got rid of them entirely.

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.

I gave a talk at ODYNUG on Tuesday about one of my favorite dynamic languages: Erlang. It went pretty well, I think. Unlike my Lisp talk from last year, I don’t think I caused too many heads to explode.

I’ve posted my slides and some example code here.

I’ll be giving a talk on ML on Febuary 5, 2008.

Movie: Shoot Em Up
Hates a pussy with a gun
After, I need a smoke