/dev/code

Adding 1 to a binary number in sed

2008-05-22T13:30:00.000-07:00

I have an odd fascination with binary clocks. I just recently built my own, based on an AVR microcontroller, which I will post more about soon. I also have a binary watch that was a present from Ceal a few years ago. During a particular boring meeting yesterday, I was watching it count the seconds, and I realized that to increment a binary number by 1, you are really looking for the pattern: 01*$ (the last part of the number consisting of 0 followed by only 1s to the end of the line). When you find that pattern, you just invert the bits.

For example, to add 1 to 10011 (19 decimal), you are only interested in the 011 at the end. You invert that part and get 10100 (20 decimal). The only time the 01*$ pattern doesn't work is when the number is all 1s. In that case, you can insert a leading 0 and again just invert the bits. For example, 1111 (15 decimal) first becomes 01111, then inverted becomes 10000 (16 decimal).

So, after that little epiphany, I began to wonder if I could write a sed script that functioned as a binary adder. At first I didn't think it could be done, because I was thinking purely in terms of doing substitutions. I have since learned much more about the capabilities of sed and found it was possible. Here is the script, along with an explanation of what each line does:


s/^1*$/0&/
h
s/\(.*\)01*$/\1/
x
s/^.*\(01*\)$/\1/
y/01/10/
x
G
s/\n//

`s/^1*$/0&/`	If the number is all 1s, insert a leading 0
`h`	Copy the current line to the hold buffer
`s/$.$01$/\1/`	Strip off the 01*$ pattern from the end
`x`	Exchange the current pattern with the hold buffer
`s/^.$01$$/\1/`	Strip off everything but the 01*$ pattern
`y/01/10/`	Invert the bits in the current line
`x`	Exchange the current pattern with the hold buffer (go back to the prefix bits)
`G`	Join the hold buffer (the end bits that were just inverted) to the current pattern (sed puts it on a separate line)
`s/\n//`	Join the two lines

To test this, I wrote a little script that starts with 0, runs it through the adder, prints the result, and the runs the result through the adder. This is the script (caution, it loops forever):


#!/bin/sh
NUM=0
while true; do
   NUM=`echo $NUM | sed -f adder.sed`
   echo $NUM
done

And here is a snippet of the results:

Beyond XML, part 2

2006-03-09T13:15:00.000-08:00

I have come to the realization that the thing I was trying to describe in my previous post is fairly close to ASN.1 (Abstract Syntax Notation 1). The thing about ASN.1 that I never really grasped was that you can have different encoding rules. Thus, you can have an encoding that encodes as XML, or another one that has a more efficient binary protocol. I came to this realization while reading about Sun's Fast Infoset for SOAP requests, during my desperate search for a production-ready Java SOAP implementation that was reasonably fast. Still looking, though..

Beyond XML

2005-08-14T11:57:00.000-07:00

Most people I have worked with will tell you that I am not a fan of XML. It has its places, but people seem to try to use it everywhere they can just because it is popular. I was reflecting this morning on XML Schemas and how ugly they are. It is difficult to look at a schema and visualize the data layout.

At first, I wondered why this is so, and why you can look at a data definition in other languages and get a good idea how everything fits. Some of this is probably the noise of XML -- all those tags just give your brain more information to process. I think another part of it, though, is that XML is so explicit about things. In other languages, you can define things more positionally. That is, you can define a variable declaration as "type varname". In XML, you can do the same thing in your schema, but you still need tags for the type and varname.

As I thought about this, it occurred to me that maybe all we need is a really super schema language. One where we define mappings to and from an abstract data notation. Instead of just mapping to/from XML, it would be great if you could map to/from all kinds of formats -- property files, flat files, comma-delimited, etc. You could couple this with some kind of interface definition language that expresses an interface in terms of the abstract data notation and then you could have something like SOAP but with support for multiple syntactic forms.

For example, suppose I define a remote-call interface in an abstract notation that looks something like this:
remote_call_request = string call_name, any params[];
remote_call_response = any result;

Then I could define multiple syntaxes for the remote call. One might looks like a SOAP request, one might be pipe-delimited text. It seems like the syntax definition might be pretty complicated to write, but it also seems like it could solve some headaches. It would be more friendly to legacy systems, you could get closer to a binary XML kind of format, you could convert easily from one format to another (like you do with XSLT, but with better support for non-XML formats).

I don't know if anyone is working on something like this, or if it is even possible, but it is interesting to think about.

Lispy or not?

2005-07-14T12:24:00.000-07:00

I just started making Lisp versions my cop and robber entries from the ICFP contest. I am aware that because other languages I use don't have anything like Lisp's macros, I tend not to use macros in Lisp. I am trying to change that.

When I was coding my parser in ocaml, I thought it was cool to use the match statement to parse the various lines, like this:


let parse_line line =
  match Str.split (Str.regexp "[ \t]+") line with
      "wsk\\" :: [] -> handle_wsk_start()
    | "name:" :: name :: [] -> handle_name name
    | "robber:" :: name :: [] -> handle_robber name
    | "cop:" :: name :: [] -> handle_cop name
    | "nod\\" :: [] -> handle_nodes_start()
    | "nod:" :: name :: tag :: x :: y :: [] -> handle_node name (node_tag_of_string tag)
                                            (int_of_string x) (int_of_string y)

Since I don't have match in Lisp, I wondered what would be a good way to do this in Lisp. I decided to do it with a macro. I keep a global hash table that maps keywords like "wsk\\" and "name:" to functions that handle the data for those keywords. I use a macro named defparse to create a function where instead of the name of the function, I supply the keyword name. Here is how I handle the "nod:" line for example:


(defparse "nod:" (name tag x# y#)
  (push (make-instance 'node :name name :tag tag :x x# :y y#) *build-node-list*))

One of the interesting things here is that you are seeing the function that handles the line, not just my definition of what is on the "nod:" line. In the ocaml version, I had all the keywords in one big match statement and made them call separate functions. I could have implemented the functions in the match statements but I thought it might look ugly. I like the Lisp solution here because I define the line contents and the function in one place, but it isn't all cluttered with other line definitions.

There are a couple of things going on in defparse. First, it turns the function body into a lambda expression that is mapped in the global keyword hash table. Next, it looks for parameters whose names end in # and automatically converts them from string to integer. This is what the expansion of my (defparse "nod:" ...) looks like:


(SETF (GETHASH "nod:" *COMMAND-HANDLERS*)
        (LAMBDA (NAME TAG #:G4171 #:G4172)
          (LET ((|X#| (PARSE-INTEGER #:G4171)) (|Y#| (PARSE-INTEGER #:G4172)))
            (PUSH (MAKE-INSTANCE 'NODE :NAME NAME :TAG TAG :X |X#| :Y |Y#|)
                  *BUILD-NODE-LIST*))))

Those #:G4171 and #:G4172 names are unique symbol names generated by the gensym function. A macro in Lisp is basically a function whose return value is code that will be compiled. This means that it blends in well with the language - there are a few syntactic differences having to do with quoting, but otherwise, you don't learn a separate macro language. One of the difficulties is that the macros run at compile time, so you can make use of all the functions you have defined (as far as I can tell, at least).

For the curious, here is my defparse macro:


(defmacro defparse (command param-list &body body)
  (let* ((int-params (remove-if-not
                     #'(lambda (param)
                         (let ((ps (symbol-name param)))
                         (char= (elt ps (1- (length ps))) #\#))) param-list))
         (param-map (mapcar #'(lambda (x) (cons x (gensym))) int-params))
         (param-list-with-syms (mapcar
                      #'(lambda (param) (if (assoc param param-map) (cdr (assoc param param-map)) param))
                      param-list))
         (let-list (mapcar #'(lambda (pg) (list (car pg) (list 'parse-integer (cdr pg)))) param-map)))
    `(setf (gethash ,command *command-handlers*)
           (lambda ,param-list-with-syms
             (let ,let-list ,@body)))))

The thing I am a bit curious about is whether this is a Lispy way to approach the problem. Would a Lisp pro nod his or her head at this, or start to gag?

My 2005 ICFPC Submission

2005-07-10T13:02:00.000-07:00

My Ocaml code for the 2005 ICFP Programming Contest is now available at http://www.wutka.com/download/markwutka_icfpc.tgz
I'm sorry to say that there is only one barely informative comment. The only other comments are code that has been commented out.

One of the things I learned last night on IRC was that I can optimize some of my match statements. The parser (parser.ml) has lines like this in its match:


    | "nod:" :: name :: tag :: x :: y :: [] -> handle_node name (node_tag_of_string tag)
                                                  (int_of_string x) (int_of_string y)

Apparently, I can make this a little shorter with:


    | ["nod:";name;tag;x;y] -> handle_node name (node_tag_of_string tag)
                                                  (int_of_string x) (int_of_string y)

Although I am happy with my choice of Ocaml for doing this project, I am not happy with my usage of Ocaml. I didn't use the "O" part of it at all - no objects. I did things as modules and it was a little cumbersome. I should have made a generic Bot class and then derived the cop and robber from that. I ended up copying too much code back and forth.

36+7 hours of coding

2005-07-10T00:25:00.000-07:00

I submitted my final entry for the 2005 ICFP Programming Contest and the deadline has passed, so now I feel free to share the mini diary I kept while working on the project.

June 24-27, 2005 - It Begins

Friday, 7:08 PM
I'm finally home and eating supper. The contest started 9 hours ago. I had to work today, so the best I have been able to manage is to look through the rules. I am excited to get going. Last night, I did a few tests with Chicken Scheme since I suspected I might have to do some socket code. The LiveCD the contest people put out mentioned something about game servers. Now that I see that I just read from stdin and write to stdout, I am back to Ocaml. The other thing that leads me back to Ocaml is that I will have 5 seconds to make a move each turn, I might need all the speed I can get.

Friday, 7:28 PM
I'm starting on the parser now. I will make a callback interface similar to the way SAX works to handle each message event. For nested messages like wsk, I will have callbacks for each sub-message. The callback interface will allow me to simulate the server in code later without actually having to do the full protocol.

Friday, 9:24 PM
It has been a little bumpy with Ocaml, but the problem is a disconnect between the chair and the keyboard. I am getting the parser written now. I have code to dump out the wsk structure, am trying to get it running now.

Friday, 9:54 PM
Got the basic parser running a little while ago. Now I am adding in support for all the commands the server can send. I have been on #icfpc on freenode for a while now (I am mr_pengy) and it is a blast chatting with these folks. It makes me wish we were all in one big lab.

Friday, 11:48 PM
All the parsing is coded, now I am trying to build the graphs for foot and car paths. After that I think I may go to bed.

Saturday, 12:14 AM
I decided to keep a list of foot edges and car edges in each node, so I essentially have two trees. I am going to bring in my old fibheap code and add dijkstra's algorithm so I can do shortest path computations. I want to see if I can compute the shortest path between all points in each tree. There are < 300 nodes in the graph, so that's just a few hundred thousand distances to compute. I'll have to see how long it takes. If the size of the world increases substantially, though, this will be a bad idea. Time for bed now.

Saturday, 10:02 AM
I probably slept a lot later than I should have. I finally got caught up with the ICFPC mailing list – lots of rule clarifications. Time to code.

Saturday, 11:57 AM
If I were to quit now, it wouldn't be a total loss. I was wrestling with trying to squeeze my fibheap code into this project without making it become really ugly. Then I started thinking about alternate ways to compute the distances. I worked out a way to do Dijkstra's shortest path algorithm without a priority queue. Basically, I start with distance D=0 and I iterate through each node N looking for node Nadj with distance=D. Then, I look at each node Nadj' that is an edge node of Nadj. If the distance from N to Nadj' is greater than D+1, I update the distance from N to Nadj' to be D. When I have done that for all nodes, I then repeat the procedure for all nodes with D=1 and so forth, until I do not find a node to update. On my machine, doing this calculation for all 229 nodes takes about 0.03 seconds. The max distance on foot is 29, the max distance by car is 17. This isn't bad considering the map is roughly a 15x15 grid. This is pretty exciting, even though I have yet to write a complete bot, so I am going to get started on a robber bot.

Saturday, 1:15 PM
Still reorganizing the code and making a bot interface. Still no bot, but this should make it easier to write one. There was a mention on #icfpc to look up the Floyd-Warshall shortest path algorithm, I think that's essentially what I came up with. I am pretty sure mine is O(n^3) like Floyd.

Saturday, 4:16 PM
I'm working on a robber bot. As a first try, I am having it look for banks that it can get to before the cops do, with a certain margin for error. If it can't find one, it picks another place to go. I'm writing lots of functions that should make it easier to add other behavior.

Saturday, 8:53 PM
I have a pretty dumb robber bot. He got caught after robbing one bank. It's not that my cop is smart, the robber ran right into him. The robber targeted banks that were farthest away from the cops, but didn't know how to avoid cops in its path. I have been thinking for a while about what to do about that, and my current thinking is that I need to make a new shortest path algorithm that avoids cops. Basically, before traversing an edge, see if the destination falls within some constraints (no cop within 2 spaces, for example). That would allow me to plot a short path around a cop.

Saturday, 10:13 PM
My robber just made all the way through without getting caught, and having robbed several banks. The cops are still very dumb, and the robber needs some work. His choice of banks is still determined by how far away the cops are, but not how close he is. Also, I need to make some adjustments to make sure it picks valid moves. I had a problem with that and I need to make absolutely sure it validates the move. Still, I feel good about my progress.

Saturday, 10:43 PM
I figured out where the invalid moves were coming from and made several adjustments there. I also changed the algorithm to go for the closest bank now that the distances take cop proximity into account. If it were to get surrounded right now, it wouldn't be able to pick a path because it wouldn't find nodes that are “safe”. In that case, I will make an emergency flee function. I may let it go for a “less safe” path first, then any path where there is no cop. Otherwise, stay put.

Saturday, 11:45 PM
I added the emergency flee function, so it should be able to get out of a jam. Tomorrow I have to make a better cop. I submitted an entry already just in case my machine crashes. Can't be too careful.

Sunday, 9 AM
Over breakfast, I modified the robber's calculations for cop distances to account for cops changing from foot to car. I'm leaving for Meeting for Worship shortly, won't be able to get going again until after noon.

Sunday, 4:04 PM
I have been working on the cop for a while. I tried assigning the cops a beat where they walked from bank to bank. My robber still got a ton of money. Now I am trying to compute the vicinity where the robber should be.

Sunday, 5:29 PM
I have been working on smartening up my cop. The contest rules state that in the initial tournament, your cop must win – not just come in the top 3. Because of the way the evidence collection works, that means if the other cops stumble on evidence and you aren't the one to capture the robber, you lose. This seems a little too random for me. My cop now directs the other cops to the general vicinity of the last known location of the robber, adjusting for time (“Our fugitive has been on the run for 90 minutes...”), but also within a certain minimum distance away. The idea is that my cop comes in to the actual area and snoops around. It doesn't quite work that way, but it isn't too bad. Whenever my cop smells the robber, it computes the possible locations of the robber (based on last-known location) and joins that with the locations that are exactly the smell distance away. Then it picks a random one if there are any. My cop can now occasionally beat my robber. I'm going to see what the ratio is.

Sunday, 5:42 PM
Oops! In computing how far a robber could have moved, I forgot that the robber only moves on every other turn, so the area was much too wide.

Sunday, 5:55 PM
In 20 games, the robber won 12 and my cop won 8. Also, my cop lost to the other cops in 1 out of those 8.

Sunday, 7:12 PM
I am really starting to feel tired. This has been a tough project and I am sure I won't win. I would like to be able to get through the regular season part of it, at least. I have modified the robber a little bit. Before, when it couldn't find a regular move, it would look for a “safe” move, which was a move that maximized the distance from the cops. Now, it looks at the set of those moves and tries to maximize the safe moves from that move as well. I could probably play with the logic there a little, but I will first see if that improves its performance against my current cop.

Sunday, 7:27 PM
The robber won 14 out of 20 this time. It might be just a tiny bit better than before. I started logging its searches and I have seen it get out of a jam when it has picked an emergency move, but usually when it has to do that, it gets caught.

Sunday, 10:03 PM
I submitted my updated cop & robber. My team name is “O Caml, My Caml”. I just recently put in code to look at the informs from the Mcgruff bots again and now I am starting to see how I might use Bayes theorem to predict user location. Someone mentioned Bayes on #icfpc yesterday, but I didn't know what he was getting at. I googled and found a paper on predicting customer location on a wireless network and now I am beginning to understand. Unfortunately, there are less than 12 hours left, and I know I won't be able to last all night. I don't know if I can create a smarter cop in the next few hours or not. I'll give it a try.

Sunday, 11:07 PM
I tried a few other things with probabilities, trying to incorporate Bayes theorem, but it seemed to be a little worse than my previous algorithm. Perhaps the Mcgruff bots aren't so good at estimating probabilities. It looks like I'll be sticking with what I have.

Sunday, 11:32 PM
I just sent in my final submission for the first part of the contest. Time for bed.

Monday, 2:24 AM
I was in bed with the light off when I realized that if a robber never hit a bank, my cop wouldn't find him. I switched the cop to start off in beat mode. Now I am doing some analysis on what bank a robber hits last before getting caught. So far, "60-and-blackstone" and "53-and-the-other-lake-park" lead by far. I tried eliminating 60&B already and cops won 17 out of 30 times. I am trying again with all banks allowed. Then I will try with 60&B and 53&OLP removed.

Monday, 3:44 AM
I tried a number of combinations, including picking random banks, the farthest bank, sticking with a bank until it was robbed. In the end, the best strategy was still to aim for the closest bank, but don't rob the bank at 60-and-blackstone. That should be enough right there to disqualify me from the Judge's Prize. NOW I'm going to bed.

July 9-10, 2005 - And now, The Twist
The interesting thing about this contest was that after the initial 72-hour period, there was almost a two-week lull, then they announced a change in the rules that we had 24 hours to respond to. I can't say that my response was great, but at least I submitted something.

Saturday, 10:10 AM
I am in Blacksburg, VA getting ready to come home after a week at the Friends General Conference Gathering. My dorm room at Va. Tech has an internet connection so I have just logged in to start reading the "twist" in the problem specification. UGH! Cops can be bribed! I don't know how I am going to do this. I spend the next 20 minutes looking over the requirements.

Saturday, 3:20 PM
Ceal is driving right now as I work on my program. I have just adapted my original cop and robber to the new protocol. The robber doesn't offer any bribes and the cop doesn't accept them. At least I have something.

Sunday, 12:45 AM
I have just submitted my final code. I am really tired after waking up at 6, packing the van and driving about 4 of the 7 hours of the return trip. My robber tried to bribe cops, but my cop does not take bribes. I decided to leave the cop alone. This will probably cost me the judges prize, even though I don't think I had a realistic shot at it to begin with. This has been a fun project and I hope to go back and try to add better strategy to my programs later.

Coding my head off

2005-06-26T19:46:00.000-07:00

It has been a really long time since I posted anything here. This weekend I have been participating in The Eighth Annual ICFP Programming Contest.

There were a few accidental clues given before the contest started. The LiveCD they distributed mentioned something about game servers, and the submission instructions mentioned a cop and a robber executable. Thinking that the contest might require some socket programming, I looked at the languages available to see which ones would be best for that. I always had Python and Java to fall back on, but Chicken Scheme seemed like a possibility.

When the contest was announced on friday, however, the cop and robber executables just had use stdin and stdout for all communication, which left the choice of language pretty wide open. I decided to go with OCaml. There are things about OCaml that really annoy me. I get syntax errors in odd places and I have to put parens in places I wouldn't expect. It is probably just because I don't know the language well enough. When the contest is over, I'd love to have someone who knows the language well to look over my code and tell me what stupid things I do.

Despite the minor annoyances, I am really happy that I picked OCaml. Toby Reyelts was arguing with me here about static vs. dynamic typing when I first started this blog. I think that OCaml's static type checking really saved me many times on this project. When I changed something significant, the compiler dutifully told me when I broke an interface.

There will be more about the contest in a future blog entry. I have been keeping a little log during the contest, just updating what I am working with, along with the time, so you get some idea what it might be like. I just don't want to say anything until the contest is over (in 2 weeks, after the requirements change) because I don't want to give away anything to my opponents.

I submitted a cop & robber a little while ago and I think they may end up being my final entries. It is almost 11pm EDT, so there are only 11 hours left in the contest and I'm really tired. Realistically, I don't think I have any shot at winning. I think that my bots have a good chance of making it out of the regular season round, but I expect them to be trounced in the playoffs.

The Steele Fortress

2005-04-27T05:53:00.000-07:00

There has been some discussion on Lambda the Ultimate about a new language that Guy Steele (of Scheme fame, among other things) has been working on at Sun Labs. It is called Fortress and is targeted towards the same application domain as Fortran. This is *not* Fortran, however. Take a look at this list of features (shamelessly cut&pasted from LtU):

an advanced component and linking architecture

objects and traits (which look similar to Moby and Scala)

multiple dispatch

type inference

parameterized types

extensible syntax

first-class functions

proper tail calls

labelled jumps, exceptions

contracts

some interesting parallelism features (including futures, parallel loops, atomicity primitives, transactions)

matrices

comprehensions

bignums, fixnums (signed and unsigned), floating-point, imaginary and complex numbers

dimensions

It is nice to see type inference popping up again, as well as proper tail calls, parameterized types and contracts (kinda sounds like Nice except for the tail calls). I have only glanced at the spec but one of the interesting things that popped out is that do-loops are assumed to execute in parallel by default. It will be interesting to see what happens with this language.

On second thought..

2005-04-10T09:56:00.000-07:00

Well, I was doing pretty well with the lambda-calculus-in-ocaml thing until I tried to define XOR for Church booleans. I defined it as:
λa.λb.a (not b) b

I worked this out on paper and it seems to be correct. It fails when I define it in OCAML as:
let xorx = fun a b -> a (notx b) b;;

When I say it fails, I mean that I get a type error when I try something like this:
(xorx fls tru) "true" "false"
(or if I just call my print_cbool function). It works if I define xorx as:
let xorx = fun a b -> a (notx b) (b tru fls);;
Since b is supposed to be a boolean, (b tru fls) should be redundant.

A patient gentleman on the #ocaml channel tried to explain to me why OCAML wasn't good for doing Church booleans, but when I started hearing terms like "predicative polymorphism" and "prenex normal form" I realized that I wasn't going to understand the explanation. I hope I will understand some of these terms better by the time I finish Types and Programming Languages.

Lambda Calculus and OCAML

2005-04-08T06:21:00.000-07:00

I've been working my way through Types and Programming Languages (TAPL). Chapter 5 discusses the untyped lambda calculus, which is a theoretical representation of computation that predates computers.

There are a number of lambda calculus tutorials out on the web, including this one (PDF). Basically, lambda calculus lets you define functions like this:

λx.x
This is a function that takes a single argument x and returns x. A function can only take a single argument, but you can nest functions to handle multiple arguments, like this:

λx.λy.x*y
In this case, the outermost function's return value is a function that multiplies its argument by x.So (λx.λy.x*y) 5 3 becomes (λy.5*y) 3 which becomes 15. This method of converting multiple arguments into nested functions is called currying.

The thing I find really interesting is that it is very easy to translate basic lambda calculus expressions into OCAML and try them out. For example, I'll start with Church Booleans.

A Church Boolean is a method of defining true and false as functions. Both functions take two arguments (using the nested notation). True returns its first argument, while false returns its second:

true = λt.λf.t
false = λt.λf.f

This translates very easily into OCAML (I am using an older form of function declaration because it matches more closely with the lambda calculus form):


let tru = fun t f -> t;;
let fls = fun t f -> f;;

Now, tru and fls are not static values, but functions. This function prints Church booleans as "true" or "false":


let print_cbool = fun b -> print_string (b "true" "false");;

You can define boolean and in lambda calculus as:

and = λa.λb.a b fls
Each argument to this function is a boolean function like tru or fls. If a is tru, then it returns its first argument, which is b, otherwise it returns fls. If b is tru, then the result of a and b is tru, otherwise it is fls.
In a similar manner, you can define or and not as:
or = λa.λb.a tru b
not = λa.a fls tru

In OCAML, these can be defined as:


let andx = fun a b -> a b tru;;
let orx = fun a b -> a tru b;;
let notx = fun a -> a fls tru;;

You can then play around with various expressions like:


print_cbool (andx tru tru);;
print_cbool (andx tru fls);;
print_cbool (andx (notx fls) tru);;

Booleans are fun, but it gets much more interesting when you get into numbers. Church numerals are formed by a combination of two functions s and z. The s function is the "successor" function and z is the zero function. The first few church numerals are defined as:
C(0) = λs.λz.z
C(1) = λs.λz.s z
C(2) = λs.λz.s (s z)
C(3) = λs.λz.s (s (s z))

If you think of s as "1+" and z as 0, then C(0) = 0, C(1) = 1+ 0, C(2) = 1+ (1+ 0), etc.
I defined a function p1 as shorthand for adding 1, and created a print_church function to display an integer version of a Church numeral:


let p1 = (+) 1;;
let print_church = fun c -> print_int (c p1 0);;

In this case, p1 is a partial function, the (+) operator takes two arguments, but since I only supplied 1, p1 actually returns a function that adds 1 to its argument.

Now, since I don't want to manually define each Church numeral, I defined a simple function that generates Church numerals:


let rec church = fun n s z->
  if n = 0 then z
  else s (church (n-1) s z);;

If you call print_church (church 55) you'll see 55.

It is also possible to define the addition operation. Since a Church numeral is essentially defined by adding 1 over and over starting from 0, addition can just be defined as adding 1 over and over starting from another number, like this:
plus=λa.λb.λs.λz.a s (b s z)
That is, instead of the usual z function, let a's z function be the evaluation of b (instead of counting from 0, a is calculated by starting from b). In OCAML, this can be defined as:


let plus = fun a b s z -> a s (b s z)

If you call print_church (plus (church 12) (church 34)) you should see a result of 46.
Multiplication can be defined in a similar way. Instead of adding 1 every time, you add b, like this:
mult=λa.λb.λs.λz.a (b s) z
In OCAML, this is:


let mult = fun a b s z -> a (b s) z;

Again, using print_church, you can test the mult function. If you call print_church (mult (church 12) (church 34)) you should see 408.

You can get a little closer to the lambda calculus notation by using only single arguments in function definitions:


let tru = fun t -> fun f -> t;;
let fls = fun t -> fun f -> f;;

OCAML oddity

2005-04-03T12:05:00.000-07:00

I kept getting this message from OCAML saying:
This expression has type map_path but is here used with type 'a
The type constructor map_path would escape its scope.

The error was occurring when I was trying to add a record to a Hashtbl. Here is a shorter piece of code that will generate the same error:


let ht=Hashtbl.create 100;;
type footype={foo1:int;foo2:int};;
Hashtbl.add ht "foo" {foo1=5;foo2=10};;

You'll get an error that the constructor footype would escape its scope. The thing that seems odd to me is that this error occurs because the hash table was created before the type was known, even though the hash table hasn't really been bound to a specific type yet. If you just reverse the order of the first two statements, everything works:


type footype={foo1:int;foo2:int};;
let ht=Hashtbl.create 100;;
Hashtbl.add ht "foo" {foo1=5;foo2=10};;

Although the error message is a bit confusing, the error itself makes sense when you think about it. The reason it is an error is that if you had to explicitly declare the type of the hash table when you created it, you wouldn't be able to because footype hasn't been declared yet. Once you realize that, even the error message makes sense. The type is declared after the hash table, so it was not "in scope" when the table was created. This makes more sense if you think of the statements as really being nested inside successive lets, although this isn't valid OCAML syntax:


let ht=Hashtbl.create 100 in
   let type footype={foo1:int;foo2:int} in
      Hashtbl.add ht "foo" {foo1=5; foo2=10};
      ht;;

Written like this, you see that the scope of footype would really be within the scope of "let ht=".. and you shouldn't be able to see footype outside of the let. Since the let returns the table, though, you would be violating the scoping rules. Again, that's not exactly how OCAML does it, but it makes sense when you think of it this way.

Fibonacci heap consolidate function

2005-03-31T09:26:00.000-08:00

While redoing my fib heap code in OCAML, I figured out a nice tail-recursive way to do part of the heap consolidation function. The pseudo-code of the algorithm, as specified in CLRS is:


CONSOLIDATE(H)
  for i := 0 to d(n[H])
    fo A[i] := NIL

  for each node w in the root list of H
    do x <= w
       d := degree[x]
       while A[d] != NIL
         do y := A[d]
           if key[x] > key[y]
             then exchange x <-> y
           FIB-HEAP-LINK (H,y,x)
           A[d] := nil
           d := d + 1
       A[d] := x
  min[H] := nil
  for i := 0 to D(n[H])
    do if A[i] != NIL
         then add A[i] to the root list of H
              if min[H] = nil or key[A[i]] < key[min[H]]
                then min[H] := A[i]

I tend to split this into two pieces. The first part (the "for each node w ...") creates an array of root-level nodes, each with a different degree (number of children). If two nodes have the same degree, one becomes the child of the other - the one with the lower key being the parent. Once this array has been created, the second part wipes out the old root list and re-inserts the new nodes, adjusting the min pointer to point to the node with the lowest key.

The second part, in OCAML, looks like this:


let fh_consolidate2 heap node =
  match node with
      Empty -> ()
    | Node(n) ->
        if is_empty heap.min then
          heap.min <- node
        else
          (fh_splice_nodes heap.min node;
           if (heap.compare_func n.data (as_fh_node_rec heap.min).data) then
             heap.min <- node);;

I call fh_consolidate2 using an iterator (see my earlier blog on partial functions if you don't understand how I can pass (fh_consolidate2 heap) this way):


Array.iter (fh_consolidate2 heap) a;;

The first part is more interesting because it is a pain to write in OCAML. The LISP version looks like this:


    (do* ((num-roots (fib-heap-node-list-length (fib-heap-min heap)) (decf num-roots))
      (x (fib-heap-min heap) next)
      (d (fib-heap-node-degree x) (fib-heap-node-degree x))
      (next (fib-heap-node-right x) (fib-heap-node-right x)))
     ((<= num-roots 0))
      (do ((y (aref a d) (aref a d)))
      ((null y))
    (when (funcall (fib-heap-compare-func heap)
               (fib-heap-node-data y) (fib-heap-node-data x))
      (let ((temp x))
        (setf x y)
        (setf y temp)))
    (fib-heap-link x y)
    (setf (aref a d) nil)
    (incf d))
      (setf (aref a d) x))

As you can see, this is pretty much an imperitive Lisp version of the pseudo-code.
One observation I made was that since I am clearing out the root level of the heap, I can go ahead and do that as I iterate through the heap. I created a destructive foreach that removes nodes from the heap as it goes through. Since the list is circular, the loop is done when a node's right pointer points to itself (meaning it is the last one):


let destructive_foreach f node =
  match node with
      Empty -> ()
    | Node(n) ->
        let rec foreach_iter curr next =
          fh_remove_from_list curr;
          (f curr);
          if next != curr then
            (foreach_iter next next.right)
        in
          foreach_iter n n.right;;

Now that destructive_foreach handles the "for each node w in the root list of H", I just need a better way to store the nodes in the A array. The "while A[d] != NIL" loop is really just a loop that looks for an empty slot in A. I rewrote the loop as a tail recursive procedure like this:


  let rec put_in_slot x =
    let d = x.degree in
      if is_empty a.(d) then
        a.(d) <- Node(x)
      else
        (let y = (as_fh_node_rec a.(d)) in
           a.(d) <- Empty;
           if heap.compare_func x.data y.data then
             (fh_link x y; put_in_slot x)
           else
             (fh_link y x; put_in_slot y))

Basically, look at the degree of x, if a[d] is empty, put x in there. Otherwise, pull the item out of a[d] and call it y. Link x and y together and then look for a slot to put the new joined-together nodes. Now, the guts of the consolidate routine just look like this:


    destructive_foreach put_in_slot heap.min;
    heap.min <- Empty;
    Array.iter (fh_consolidate2 heap) a;;

Followup on "Duh!"

2005-03-27T11:43:00.001-08:00

One of the things that has been bothering me about my "Duh!" moment is that it seems like a bit of a cop-out. I shouldn't have to use a list to represent a null reference - I should be able to represent it using the Empty | Node of 'a fh_node_rec. I decided to go back and make the code work the way I originally thought it should, and except for a few lingering bugs with decreasing a key value, I have the heap working with Empty representing null.

Two things that helped me a lot were the definition of an is_empty function:


let is_empty node =
    match node with
        Empty -> true
     | x -> false;;

and as as_fh_node_rec that is essentially like a cast (there may be a built-in way to do this in OCaml, I just don't know about it):


let as_fh_node_rec node =
    match node with
        Empty -> failwith "Expected fh_node_rec, found empty"
       | Node(n) -> n;;

When I need to refer to an fh_node_rec as a Node, I can just do Node(x). The combination of these things made the solution a little more palatable, but it is still a bit of an annoyance.

DUH!

2005-03-23T19:57:00.000-08:00

I had a "Duh!" moment this evening. A "Duh!" moment is an "Aha!" moment where you say "Aha! I am an idiot!". I have been translating my Fibonacci Heap code from Lisp to OCAML. In my implementation, a heap node has left and right pointers for storing nodes in a circular list, and also parent and child pointers. Since a pointer could be null, I defined a type that could be either Empty or an fh_node_rec object, like this:


type 'a fh_node_rec = {
    mutable data : 'a;
    mutable parent : 'a fh_node;
    mutable left : 'a fh_node_rec;
    mutable right : 'a fh_node_rec;
    mutable child : 'a fh_node;
    mutable degree : int;
    mutable mark : bool;
} and 'a fh_node = Empty | Node of 'a fh_node_rec;;

So, mistake number one was that the left and right pointers were a different type from the parent and child. This got really complicated when I started processing the lists. When handling the left and right nodes, I could work directly with fh_node_rec types, but for parent and child, I had to use match, like:


match x with
    Empty -> ()
  | Node(xn) -> (* do something with xh as an fh_node_rec *)

I ended up defining multiple functions, some that worked with fh_node and others that worked with fh_node_rec. I started to have trouble keeping track of whether something was an fh_node or an fh_node_rec. I really had trouble when writing the consolidate function. In fact, I never could get it right.

I came across a paper called Design Patterns in OCaml by Antonio Vicente and Earl Wagner that suggested using a list to represent items that may be null, using [] to represent null. That's when I just wanted to slap my forehead for not thinking of it before. I was able to define a single record type:


type 'a fh_node = {
    mutable data : 'a;
    mutable parent : 'a fh_node list;
    mutable left : 'a fh_node;
    mutable right : 'a fh_node;
    mutable child : 'a fh_node list;
    mutable degree : int;
    mutable mark : bool;
};;

I was able to eliminate all the duplicate functions and I got the consolidate function written. It was much easier to see if a node was equal to [] than it was to see if it was either an Empty type or an fh_node. Once I get the rest of the code finished and working, I'll post it on my web site.

Partial functions in OCAML

2005-03-23T06:04:00.000-08:00

OCAML supports something called "partial functions". Suppose you define a function that takes two arguments and adds them together:


let adder x y = x + y;;

You can obviously call adder 2 3 and expect to get back 5. OCAML lets you call adder 2 and get back a function that adds 2 to whatever argument you pass it. For example:


let add2 = adder 2;;
let add3 = adder 3;;
Printf.print "%d %d\n" (add2 5) (add3 7);;

You would see "7 10" printed out.

I must admit, my first reaction to this was "Neat. So what?" I am starting to see the usefulness of it, however. In Scheme, if I want to loop through a list and add 5 to every member of the list, I can do something like this:


(map (lambda (x) (+ x 5)) '(1 2 3 4 5 6))

In OCAML, you could do this:


List.map (function x -> (x + 5)) [1;2;3;4;5];;

Since I have defined my adder function, though, I can do this instead:


List.map (adder 5) [1;2;3;4;5];;

I think the trick to taking advantage of partial functions may be to determine which arguments are likely to change and place those last. For example, if I have a function called heap_consolidate, I can define it as:


let heap_consolidate x heap = (* do something with x and the heap *)

or I can do:


let heap_consolidate heap x = (* do something with x and the heap *)

If I am going to be passing a lot of different x values for the same heap, especially if I want to iterate through a list or an array, I might want to make heap the first parameter so I can do something like this:


List.map (heap_consolidate myheap) myheap.root;;

If heap is the second argument, I would have to do:


List.map (function x -> heap_consolidate x myheap) myheap.root;;

While partial functions may seem error-prone, I don't think that is the case. If you accidentally omit a function argument, OCAML's type checker will notice that you are using a function type where it is expecting you to use something else. Without type checking, partial functions seem pretty dangerous.

OCAML and Type inference

2005-03-18T06:20:00.000-08:00

I have been playing around with OCAML a bit. I was amazed at how well it did in the Great Computer Language Shootout, so I decided to see what it was like.

After working with Scheme and Lisp for a while, OCAML is really not that different. Where you might do (let ((x 1) (y 2)) (something)) in Lisp, you do:
let x=1 and y=2 in something;;

I really haven't gotten into the meat of the language yet - I've really just been playing with the CAML part and not the O. Any way, OCAML was my first encounter with type inference (that I can recall, at least). OCAML is strictly typed, but you don't usually have to indicate the type of a variable. The OCAML compiler figures it out. If a function can accept different types of variables, that's okay, too.

For example, here is a simple recursive function that removes all occurrences of x from a list:


let rec remove x l =
    match l with
        [] -> []
    | h::t -> if x == h then remove x t else h::(remove x t)

Because of the usage, l must be a list. If I try to pass anything else as the second parameter to remove, I will get an error at compile time. The x parameter can be any type, but it must match the type of elements in l. So, I can do this:
remove 3 [1;2;3;4;5];;
or
remove 'B' ['A','B','C','D'];;

I can't do:
remove 'A' [1;2;3;4;5];;

The interesting thing is that these errors get caught at compile time. I don't declare any types in my definition of remove, the compiler just figures out the type restrictions at compile time. Now, if I add a print statement to print out x as an integer value, I am now constraining x to be only an integer (and l to be only a list of integers):


let rec remove2 x l =
    match l with
        [] -> []
    | h::t -> if x == h then ((Printf.printf "Removed %d\n" x);remove2 x t)
        else h::(remove2 x t)

Now I can still do:
remove2 3 [1;2;3;4;5];;
but I now get an error if I try to do:
remove2 'B' ['A','B','C','D'];;

Last night I took a little Chicken Scheme program that I had written to solve the puzzle USA+USSR=PEACE and rewrote it in OCAML. It is a brute force program and isn't the most efficient way to do it, but it only took a few minutes to write:


(require-extension srfi-1 srfi-13 format)
(define usa "USA")
(define ussr "USSR")
(define peace "PEACE")
 
(define digit-pool '(0 1 2 3 4 5 6 7 8 9))
(define letter-pool '(#\U #\S #\A #\R #\P #\E #\C))
 
(define (word-to-number word letter-table)
  (let ((sum 0))
    (string-for-each
      (lambda (x) (set! sum (+ (* 10 sum) (cdr (assoc x letter-table))))) word)
    sum))
 
(define print-solution (lambda (letter-table)
  (format #t "~A + ~A = ~A~%"
          (word-to-number usa letter-table)
          (word-to-number ussr letter-table)
          (word-to-number peace letter-table))))
 
(define test-solution (lambda (letter-table)
  (when (= (+ (word-to-number usa letter-table)
              (word-to-number ussr letter-table))
           (word-to-number peace letter-table))
    (print-solution letter-table))))
 
(define try-letter (lambda (letters digits letter-table)
  (cond ((null? letters) (test-solution letter-table))
        (#t
         (let ((curr-letter (first letters))
               (curr-letter-pool (cdr letters)))
          (for-each (lambda (digit)
            (try-letter curr-letter-pool
                        (delete digit digits)
                        (alist-cons curr-letter digit letter-table)))
        digits))))))
   
(try-letter letter-pool digit-pool '())

I was able to just about translate the program without any major rewriting:


let usa = "USA";;
let ussr = "USSR";;
let peace = "PEACE";;
 
let digit_pool = [0;1;2;3;4;5;6;7;8;9];;
let letter_pool = ['U';'S';'A';'R';'P';'E';'C'];;
 
let word_to_number word letter_table =
    let rec rec_word_to_number pos num =
        if pos >= (String.length word) then num
            else rec_word_to_number (pos + 1) (num * 10 +
                (List.assoc word.[pos] letter_table)) in
    rec_word_to_number 0 0;;
 
let print_solution letter_table =
    Printf.printf "%d + %d = %d\n" (word_to_number usa letter_table)
        (word_to_number ussr letter_table)
        (word_to_number peace letter_table);;
 
let test_solution letter_table =
    if (word_to_number usa letter_table) + (word_to_number ussr letter_table)
        = (word_to_number peace letter_table) then
            print_solution letter_table;;
 
let rec remove x l =
    match l with
        [] -> []
    | h::t -> if x == h then remove x t else h::(remove x t)
 
let rec try_letter letters digits letter_table =
    match letters with
        [] -> (test_solution letter_table)
    | curr_letter::curr_letter_pool ->
            List.iter (function digit ->
                (try_letter curr_letter_pool (remove digit digits)
                    ((curr_letter,digit)::letter_table))) digits;;
 
try_letter letter_pool digit_pool [];;

Although the code is pretty similar, the OCAML version runs more than twice as fast as the Chicken Scheme version. I think that a lot of the speed difference is due to the fact that OCAML knows the type of everything ahead of time. The cool thing, though, is that I didn't have to tell OCAML about the types, it figured them out on its own.

Communicating with the outside world

2005-03-10T17:30:00.000-08:00

Many languages provide something a mechanism to call into external libraries. I thought I'd mention two ways this is done, one in Lisp and another in Python. The example I am using for Python uses the dynamic libraries package. There is also an excellent package called ctypes that works well under Windows, Linux and MacOS X.

I have a C library that works with Directed Acyclic Word Graphs, specifically, the type of file used to store words for the Hasbro Scrabble game. I use the DAWG for automated cryptogram solvers as well. The C library is available at http://www.wutka.com/download/dawg.c. If you want to play with this, the dictionary file is available at http://www.wutka.com/download/twl98.daw. The 3 functions that you would care about are:


int load_dawg(char *filename); // Load the DAWG into memory
int match(char *word); // Returns non-zero if WORD is a valid word in the dawg
int longest_match(char *word); // Returns the length of the longest word found at the beginning
                               // of the string passed in. (MARKFOOBAR would return 4, 
                               // since MARK is valid, but MARKF isn't)

Under Linux, I compiled this into a shared library with the following commands:


gcc -fPIC -c dawg.c
gcc -shared -Wl,-soname,libdawg.so.1 -o libdawg.so.1 dawg.o

Now, from Python, I can use dl.open and dl.call to invoke these functions:


import dl

dawglib=dl.open("libdawg.so.1")

def dawg_open(filename):
    return dawglib.call("load_dawg", filename)

def dawg_match(word):
    return dawglib.call("match", word)

def dawg_longest_match(word):
    return dawglib.call("longest_match", word)

dawg_open("twl98.daw")

print "FOO=%d" % (dawg_match("FOO"))
print "AA=%d" % (dawg_match("AA"))
print "A=%d" % (dawg_match("A"))
print "MARK=%d" % (dawg_match("MARK"))
print "longest PRINTFOOBAR=%d" % (dawg_longest_match("PRINTFOOBAR"))

As you can see, I wrapped these calls with convenience methods. I do the same thing in the Lisp code below, which uses the Universal Foreign Function Interface.


(uffi:load-foreign-library #p"libdawg.so.1" :module "dawg" :supporting-libraries '("c"))

(uffi:def-function ("load_dawg" dawg-load-c) ((name :cstring)) :module "dawg" :returning :int)
(uffi:def-function ("match" dawg-match-c) ((word :cstring)) :module "dawg" :returning :int)
(uffi:def-function ("longest_match" dawg-longest-match-c) ((word :cstring))
  :module "dawg" :returning :int)

(defun dawg-load (filename)
  (let* ((c-filename (uffi:convert-to-cstring filename))
        (result (dawg-load-c c-filename)))
    (uffi:free-cstring c-filename)
    result))

(defun dawg-match (word)
  (let* ((c-word (uffi:convert-to-cstring word))
        (result (dawg-match-c c-word)))
    (uffi:free-cstring c-word)
    result))

(defun dawg-longest-match (word)
  (let* ((c-word (uffi:convert-to-cstring word))
        (result (dawg-longest-match-c c-word)))
    (uffi:free-cstring c-word)
    result))

(defun run-test ()
  (dawg-load "twl98.daw")
  (format t "FOO=~A~%" (dawg-match "FOO"))
  (format t "AA=~A~%" (dawg-match "AA"))
  (format t "A=~A~%" (dawg-match "A"))
  (format t "MARK=~A~%" (dawg-match "MARK"))
  (format t "longest PRINTFOOBAR=~A~%" (dawg-longest-match "PRINTFOOBAR")))

Again, I defined convenience methods, mostly because I needed to allocate and free the C strings. It's really nice when a language lets you use external library without having to write any glue code in C or some other language.

Fun With Lisp

2005-03-09T18:48:00.000-08:00

I have occasionally played with Lisp and Scheme in the past, but never long enough to get a good feel for the language. Lately, however, I have spent a significant amount of time working with Lisp and I am really beginning to appreciate the beauty of the language.

I have started a web page for Lisp stuff where I will put some of the interesting things I come up with. So far, it has an implementation of the Fibonacci Heap, which I can tell you is a bear to implement. I also have an implementation of Dijkstra's Shortest Path algorithm and some code to parse Tiger/Line files.

Why do I think Lisp is cool?

First of all, the syntax is extremely simple. Yes, there are a lot of parentheses, but I think the reason that they stand out so much is that, apart from quotes, there's not a lot of punctuation required. You don't have to end statements with a semi-colon, or put commas between list items, or put curly braces around statements. It is simple and direct.

First class functions are really cool, as well. Although they are not unique to Lisp, first class functions are not found in Java, which is my current day-job-language. By saying a function is "first class", it means that a function has the same status as other data items. You can pass a function as a parameter to another function. You can store functions in other data structures. You could, for example, iterate over a list and apply each function in the list to a particular piece of data. This would make it easier to apply business rules, for example. You can do this in Java with Interfaces, it's just a bit easier in Lisp.

There are lots of functions for dealing with data structures. For all the different containers that Java has, it really falls down on the job when it comes to actually using them. One of the things that always impressed me about Smalltalk was the things you could do with containers (Ruby has this as well, and Python's list comprehensions are close enough). In Lisp, for example, there is the (map) function, which in its simple form is just like iterating through a list with a for loop.
For example:

(mapc #'print '(1 2 3 4 5 6 7))
loops through a list and calls the (print) function for each item in the list. There are numerous (map) functions, some return no result, some return a list of the result of applying the function. Where the (map) functions excel beyond a simple loop, however, is that it can use multiple lists and invoke functions that take more than one argument. A simple example would be adding together corresponding elements in two lists:

(mapcar #'+ '(1 2 3 4 5) '(6 7 8 9 10))
which returns the list
(7 9 11 13 15).

There are other cool things, one last one I'd like to mention is that a Lisp environment tends to be highly interactive. You can write some functions and immediately interact with them from a Lisp prompt.