Friday, March 18, 2005


OCAML and Type inference

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];;
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))
(lambda (x) (set! sum (+ (* 10 sum) (cdr (assoc x letter-table))))) word)

(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))
(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)))

(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.

Actually, the performance of Ocaml has got little to do with type inference. If you disable the type checking in Chicken, Ocaml is still twice as fast. I'd blame it on the CPS-conversion instead. It can slow down the execution of some types of code. But hey, you get continuations, being safe for space, and garbage collection in return. Everything has its drawbacks.

Ocaml is a fine compiler, of course.
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?