Sunday, 26 August 2007

Writing a bytecode interpreter

The OCaml Journal just published an article describing the design, implementation and optimization of an interpreter for a minimal bytecode language:

"As a high-performance functional programming language, OCaml is perfect for writing interpreters. These programs involve a wide variety of different techniques from lexing and parsing to various methods of evaluation, compilation, simplification and rewriting. All of these techniques will be described in future OCaml Journal articles and this article describes the implementation of three progressively optimized interpreters for a minimal byte code language..."

To read this article and more, subscribe to The OCaml Journal today!

Tuesday, 14 August 2007

Power Set

The Haskell community are discussing the confusion surrounding Monads on their mailing list at the moment. The example of a function to compute the powerset in Haskell using the List monad was given:

$ ghci
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.6.1, for Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\____/\/ /_/\____/|_| Type :? for help.

Loading package base ... linking ... done.
Prelude> :m + Control.Monad
Prelude Control.Monad> let powerset = filterM (const [True, False])
Prelude Control.Monad> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

This is an impressive one-liner. However, it took me the best part of an hour to get it to run, by discovering that "import name" in compiled Haskell source code is written ":m + name" when you're writing interactively in GHCi, and "powerset = filterM (const [True, False])" must be preceded by "let".

I thought I'd post an OCaml equivalent, complete with the response of the top-level:

$ ocaml
Objective Caml version 3.10.0

# let rec powerset = function


| [] -> [[]]


| h::t -> List.fold_left (fun xs t -> (h::t)::t::xs) [] (powerset t);;


val powerset : 'a list -> 'a list list =


# powerset [1;2;3];;


- : int list list = [[1; 3]; [3]; [1; 2; 3]; [2; 3]; [1]; []; [1; 2]; [2]]


I hadn't really appreciated until now that OCaml code is the same whether you compile it or enter it into the interactive top-level, except for the ";;" suffix to get the interactive mode to evaluate.

Monday, 13 August 2007

Exploiting Tail Recursion

The OCaml Journal just published an article describing one of the core features of functional programming in detail:

"Recursion is essential to functional programming and practical use of functional programming languages and a functional style requires the ability to write recursive functions that do not consume stack space. Function calls that require no stack space are called tail calls. This article describes the use of tail calls to write robust and efficient tail recursive functions in OCaml..."

To read this article and more, subscribe to The OCaml Journal today!

Thursday, 2 August 2007

Compiler course from Japan

I recently stumbled upon this compiler course by Yutaka Oiwa from the University of Tokyo. Although much of the text is written in Japanese, the code is perfectly comprehensible and very well written. The lectures include a mini ML interpreter, a lazy-ML interpreter and a Prolog interpreter all written in OCaml as well as some graphical examples in Java.