Archive for August, 2009

My (First) OCaml Program

August 11, 2009

I spent a long time doing not much, reading occasionally; then too long fighting w/ syntax (long story short, parentheses don’t behave like I’d expect — or more precisely, operators require parens for arguments where I wouldn’t think it would matter…)

Anyway, here is my code (as a Word doc, with notes) — feel free to comment.

Update before I even posted — I found a bug.

Here is the revised code (see p. 2) — the function find_a_b is asymmetrical; that is, “half way” thru the list of factors (at which pt, normally a*b = b*a, isn’t at the sqrt of n…)  That’s a very poor description, but if you want the full math, let me know and I’ll elaborate (in a new post).

Now on to the interesting project.  I finally did what I set out to do.

Here is the result — view that PDF while reading my commentary here:

lns. 11-15 create a Map structure (integer based index) — not an array;
l. 17-18 define the input/result — I was having some problems w/ input parameters and return value(s), so I switched to this structure; I could convert back now that I know what I’m doing, but it was easiest to leave it as is…

l. 29-59 are the first implementation — it works, it does what I want, but has much debugging and offered a couple of easy improvements
l. 61-62 are a first attempt, and I examined the result to see I was on the right track (see also the commented out section l. 73-87
l. 64-65, 58-71 define two functions for displaying the result(s) and aiding in debugging

l. 97-122 give a second definition, with some debugging commented out, and primarily move the base-case “up” so I only need one conditional, and I also remove old elts from the map as I “use them up.”

Lines 145-170 present the “final” version of the function — which very closely matches the Haskell code in the paper that was the “inspiration” for me learning OCaml to begin with…

Lines 173-186 are the code that runs for a million, then 1.2 million following that (and shows how to “loop”).

Riddle me this: the “compiled” code (ocamlc.exe produced byte-code executable) runs for two million, but gives a stack overflow at 2.1 * 10^6 (after two hours of run time).  The optimizing compiler [ocamlc.opt.exe] produced slower code that overflowed the stack much sooner…  I don’t get it.  (Besides, shouldn’t this func. be tail-recursive and, as such, never overflow the stack??)

Finally, lines 188- present a final function which worked up to 1 billion (I executed w/ count=100,000 ten thousand times — I see I changed to 50,000 in the print-out; but, if you want proof, the resulting trace is a half-gig text file, but it compresses to 83 MB!).

Having done what I set out to do, I’ve grown bored w/ OCaml.  I may do more later, but for now, I’m on to Clojure, because it’s Lisp-like, JVM-based, and functional/multi-threading friendly.

If you have an interesting problem for me to work on, please let me know.

Someone suggested a comparison between various programming languages’ treatment of operators (@kaleidic on twitter, but he also programs in J, which is also interesting…)

What I haven’t learned about OCaml yet

August 11, 2009
Posted 11 August; written (lasted edited) 14 May…

Where to look when Google isn’t it

Other sources (this list is not complete, by any stretch of the imagination):

OCaml links

From the OCaml tutorial, I found the info I was looking for — at the end of the list of tutorials is a link to “comparison of standard containers,” including maps. I’m subscribed to the OCaml beginners group (Yahoo!)

I should also list info about Camlp4.  And more later…