Monday, 31 December 2007

C++ vs OCaml: Ray tracer language comparison

One of our older free articles about OCaml recently resurfaced in terms of popularity, being cited from numerous French discussion forums.

This page compares and contrasts implementations of a small ray tracer in C++ and in OCaml. The resulting implementations show how easily succinct and efficient programs can be constructed in the OCaml programming language, even matching the performance of well-written C++.

For a detailed discussion of optimization in OCaml, read our book OCaml for Scientists.

Sunday, 30 December 2007

Top 10 most popular OCaml programs

We have collated a list of the world's most popular Linux software written in OCaml based upon the Debian and Ubuntu package popularity contest results and the ara database's classification of the packages:

1. FFTW

FFTW is arguably the world's fastest Fourier transform implementation and is used in many commercial applications including MATLAB as well as being freely available and prepackaged for almost all Linux distributions. The FFT routines that make up the FFTW library are C code generated by an OCaml program called genfft.

143,802 registered installs on Debian and Ubuntu.

2. Unison

Unison is a file-synchronization tool for Unix and Windows. It allows two replicas of a collection of files and directories to be stored on different hosts (or different disks on the same host), modified separately, and then brought up to date by propagating the changes in each replica to the other.

8,786 registered installs on Debian and Ubuntu.

3. MLDonkey

MLDonkey is an open source eDonkey2000 client for peer-to-peer file sharing on Linux, Unix, Solaris, MacOSX, MorphOS and Windows.

5,010 registered installs on Debian and Ubuntu.

4. Planets

Planets is a simple interactive program for playing with simulations of planetary systems, released under the GPL. It runs on Linux and Windows.

2,429 registered installs on Debian and Ubuntu.

5. Hevea

Hevea is a high-performance LaTeX to HTML translator.

2,095 registered installs on Debian and Ubuntu.

6. FreeTennis

FreeTennis is a tennis simulator with advanced AI and real-time interactive 3D graphics.

1,837 registered installs on Debian and Ubuntu.

7. LEdit

LEdit adds line editing capabilities to programs running in shells such as bash or tcsh.

1,708 registered installs on Debian and Ubuntu.

8. Polygen

Polygen is an advanced program for generating spontaneous sentences according to a grammar definition, following custom syntactical and lexical rules.

1,594 registered installs on Debian and Ubuntu.

9. MTASC

MTASC is the world's first open source ActionScript 2 compiler.

1,030 registered installs on Debian and Ubuntu.

10. ADVI

ADVI is a viewer and presenter for DVI files that recognizes visual effects designed for giving rich presentations from a laptop.

983 registered installs on Debian and Ubuntu.

Friday, 28 December 2007

Parser combinators

The OCaml Journal just published an article explaining how concepts from functional programming can be used to construct powerful and expressive parsers:

"Certain applications are extremely well suited to functional programming and parsing is one of them. Specifically, the ability to write functional combinators that allow parsers for everything from integers up to symbolic expressions to be composed is more general and provides more opportunity for code reuse than the use of conventional parser generators such as ocamllex and ocamlyacc. This article explains how parser combinators may be designed and implemented in OCaml, using the standard example of a calculator..."

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

OpenGL 2 for OCaml

Following our use of the GLCaml bindings to OpenGL 2 for OCaml, Elliott Oti has announced his intention to work on GLCaml more over the next month.

Elliott is one of the more practically minded contributors to the OCaml community, with a wealth of interesting examples on his site. Hopefully we can work together to get a suite of OpenGL 2 demos out there for others to learn from.

Monday, 24 December 2007

JIT compilation from OCaml using LLVM

Gordon Henriksen just took the next step in using the Low Level Virtual Machine (LLVM) project from OCaml by extending the bindings to support JIT compilation. In a post to the LLVM developers mailing list, Gordon explains how to JIT compile a simple Hello World program from OCaml using LLVM. Note that OCaml is one of the only languages to have first class bindings to LLVM bundled as part of the core LLVM distribution.

This is a really exciting development because it now makes compiler writing in OCaml much more accessible than ever before. The next milestone will be the first successful integration of an existing garbage collector with code generated by LLVM. Gordon is already working on garbage collection, several other people are working on compiler front-ends written in OCaml and dozens more people have expressed a keen interest in this project.

Thursday, 20 December 2007

Measuring memory usage in OCaml

Dimitry Grebeniuk has kindly released his objsize library. This simple C library allows you to compute the size in bytes and depth of any OCaml value.

The ability to compute the memory requirements of individual values in OCaml programs is a step towards full memory profiling and can be extremely useful in a variety of circumstances. Most notable, perhaps, is the utility of memory profiling when hunting down memory leaks, e.g. caused by unbounded memoization. This library should be in the arsenal of any self-respecting OCaml programmer.


Friday, 14 December 2007

Festive fun wth OpenGL and GTK+



The OCaml Journal just published an article that walks through the construction of a GTK application with an embedded OpenGL renderer:

"This article marries the ability to render high-quality graphics in real-time using OpenGL with the ability to build GUI applications using GTK+. Specifically, a small program is developed that builds upon functionality encountered in previous articles to render a decorated christmas tree with snow in real time..."

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

Thursday, 29 November 2007

Camlp4 3.10: writing parsers and macros

The OCaml Journal just published an article explaining how camlp4 can be used to write parsers and syntax extensions quickly and easily:

"The latest OCaml tool stack includes a revamped preprocessor called camlp4 that serves several purposes including providing extensions to the OCaml language that allow parsers to be embedded in ordinary OCaml code as well as the ability to extend the syntax of OCaml itself by writing macros. This article explains how camlp4 can be used to write general parsers and OCaml syntax extensions..."

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

Wednesday, 21 November 2007

Try OCaml on the web!

OCaml is an awesome programming language but its use is sometimes stifled by a lack of libraries, particularly in the areas of web and database programming. The F# programming language is an fantastic solution to this problem because it is a closely related language but it only runs natively on Windows and tens of millions of people are now working with other operating systems on a regular basis.

Consequently, we were extremely excited when Xavier Clerc announced the release of ocamljava, an OCaml compiler than generates code for the JVM. The project is still in its infancy but, in theory, this combines the awesome expressive power of the OCaml programming language with the bewildering selection of libraries available for the JVM.

Even better, Xavier recently built a Java applet that provides an OCaml top-level in your web browser. So you can type OCaml definitions into your browser and have them checked and evaluated by OCaml without having to install any software beyond Java!


Thursday, 15 November 2007

Introduction to OpenGL

The OCaml Journal just published an article explaining just how easily real-time visualizations can be created using the OCaml programming language:

"OpenGL is the defacto-standard cross-platform graphics API and provides an efficient way to leverage the high-performance hardware accelerators found in almost all modern computers. The OCaml programming language has unusually good support for OpenGL with the LablGL library providing an elegant interface to OpenGL on all three major platforms. This article introduces OpenGL programming using OCaml, demonstrating how functional programming can be leveraged to produce visualization software that is simple and efficient..."

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

Friday, 9 November 2007

Most popular functional languages on Linux

The Linux operating system is unique in providing a wide variety of tools for developers. In particular, Linux offers an incredible variety of programming languages. This post describes our attempt to measure the popularity of functional programming languages on Linux.

There are many language popularity comparisons out there. The TIOBE programming community index is a famous one based upon the number of search hits indicated by various search engines. Like every comparison, the TIOBE results are flawed in various different ways. Some of the most important problems with this particular measure are:

  • Legacy: older languages have more out-of-date web pages.
  • Unpopularity: this metric is an equally good measure of the unpopularity of a language.
  • Subjectivity: the estimated number of search results returned by search engines is highly dependent upon unrelated factors like Google's algorithm du jour.

We are going to try to measure language popularity on Linux using a more objective metric: the results of the Debian and Ubuntu package popularity contests. Amongst other things, the results allow us to determine how many installations there are for core development tools for each language. Summing the number of installations gives a much more accurate estimate of the number of people actually developing in each language.

Before we go into detail, let's consider some of the flaws in this approach. Firstly, the absolute number of installations is not equivalent to the number of users. Many users will have their favorite language installed on several different systems. Secondly, programmers using languages with multiple different implementations are likely to have several different compilers for that language on each machine. This will bias the results in favor of languages with multiple implementations (such as GHC and Hugs for Haskell). Finally, these results only apply to Ubuntu and Debian users who elected to contribute to the popularity contests. We are assuming that other Linux distributions will give similar results and we can test this to some extent by comparing the results between Debian and Ubuntu.

The results were compiled by summing the contributions from the following major development packages for each language:

  • Erlang: erlang-base
  • OCaml: ocaml-nox
  • Haskell: ghc6 and hugs
  • Lisp: clisp, sbcl, gcl and cmucl
  • Scheme: mzscheme, mit-scheme, bigloo, scheme48 and stalin
  • Standard ML: smlnj, mosml and mlton
  • Eiffel: smarteiffel
  • Mercury: mercury
  • Oz: mozart

The results are illustrated in the graph above. Sure enough, the number of installations is similar between Debian and Ubuntu and, therefore, it seems likely that these results will reflect the trend for most Linux users.

We found the results surprising for several reasons:

  • Lisp is often cited as the world's most popular functional programming language yet it comes 4th after OCaml, Haskell and Erlang in our results.
  • There is no clear preference for a most popular functional programming language. Instead, we find that OCaml, Haskell and Erlang are all equally popular.
  • Despite the bias against OCaml because it is unified by a single implementation, this language still appears to be among the most popular functional programming languages on Linux. This is even more surprising before there are few OCaml books.

Following Microsoft's productization of their OCaml derivative F#, it seems likely that OCaml will continue to grow in popularity on the Linux platform.

OCaml in Finance: a derivatives pricer

Sean Hunter has written an interesting series of articles about writing a derivatives pricer in OCaml. In particular, he discusses the various formulations that can be represented in the OCaml programming language and the surprisingly good performance of the resulting program.

Thursday, 1 November 2007

Interest in OCaml boosted by F#


Microsoft recently announced that they are productizing their CAML derivative functional programming language F#, a cousin of the OCaml language. This has sparked enormous interest from existing .NET developers and the effect is rubbing off on OCaml, which has seen a considerable rise in interest according to Google Trends.

Wednesday, 24 October 2007

Balanced binary search trees

The OCaml Journal just published an article describing why balanced trees are so important in functional programming languages and how they can be implemented easily and efficiently in OCaml:

"Immutable data structures are a core concept in functional programming and balanced binary trees are the single most important such data structure. The OCaml programming language allows balanced binary tree implementations to be written clearly and efficiently. This article describes the design and implementation of a basic balanced binary search tree data structure similar to that of the built-in Set module..."

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

Saturday, 13 October 2007

Implementing the FFT in OCaml

The OCaml Journal just published an article describing a simple but efficient implementation of the Fast Fourier Transform:

"Writing an implementation of the Fourier transform is an excellent lesson in algorithm design and optimization. Moreover, the Fourier transform is one of the most essential tools in numerical computing, with applications ranging from spectral analysis in science to the multiplication of large integers in mathematics. This article describes the design, implementation and optimization of a high-performance FFT implementation in OCaml..."

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

Tuesday, 2 October 2007

What do you take with you when police are banging on your door at 4am and telling you to exit the building?

Joel Reymont posted the following review of OCaml for Scientists in August 2006 that was since lost in the aether:

"Objective CAML for Scientists August 23rd, 2006

There’s a trash compartment a few meters in front of our windows and down a few steps of stairs. It’s a small pass-through room of sorts with exit to the street. It houses a few large wheeled garbage bins and it also happens to be right next to the electrical room housing the transformer for our urbanization.

There was a huge fire in the garbage room about 4am today and there, apparently, was a dead body. I’ll try to take and post some pictures later to help you visualize what I’m talking about.

What do you take with you when police are banging on your door at 4am and telling you to exit the building? Why, of course passports, bank cards, cell phone, my wife’s 15” PowerBook G4, my 17” MacBook Pro, a pair of Nintendo DS Lites plus cartridges. Also The Tipping Point by Malcolm Gladwell, All Marketers are Liars by Seth Godin and, here’s the kicker, Objective CAML for Scientists by Jon Harrop of the Flying Frog Consultancy.

This is a self-published book that cost me about 130 euro and it’s also one of the best, if not the best, OCaml tutorials around. The book consists of 260 spiral-bound pages printed on a good ink-jet or color laser printer. All the code examples are colored according to syntax.

The book follows a logical path through introduction to OCaml (syntax, types, pattern-matching, etc.), program structure, data structures, visualization, optimization, libraries, examples and advanced topics. The coverage is encompassing and the writing is clear.

I particularly like the chapters on visualization with OpenGL (very useful) and optimization. I haven’t seen such a thorough treatment of optimization in any other OCaml tutorials. I wish there was more material on improving cache coherency, though.

Overall, the book is pricey but unique or I wouldn’t have taken it with my passports!"

Friday, 28 September 2007

Book review: OCaml for Scientists

The following review of the book OCaml for Scientists was posted on Digg by Lloyd Moore:

"This is one of the most informative books on any subject. After reading Practical Ocaml and being thoroughly disappointed, I almost gave up on finding that 'helping hand' when coming to terms with a new language - especially one that introduces some of the more lesser known concepts in the world of functional programming. In stark contrast to the Practical Ocaml tome, from physical make-up of the book, logical sequencing of information and chapters from start to finish, to the beautifully crafted illustrations exactly placed where relevant, this ocaml masterpiece will enable to not only master the ocaml language but also to appreciate functional programming constructs and much better programming style (clarity, shorter, reusable, less bugs). There is even a brief, but pragmatic treatment of lexing and parsing which will open the doors to anyone wishing to save and retrieve obscure data formats, including their own DSL language. Visualization is dealt with in chapter 6 which explains the use of the GLUT (openGL) library in an extremely efficient manner and the later chapters on optimization complete this master class on ocaml and some very powerful programming techniques."

Thursday, 27 September 2007

Using lex and yacc

The OCaml Journal just published an article describing how the ocamllex and ocamlyacc tools can be used to create parsers:

"The tool stack bundled with the OCaml distribution provides some awesome functionality. The ocamllex and ocamlyacc tools provide a mainstream approach to the parsing of data. This article introduces the concepts of lex and yacc-based parsing and describes the use of these tools in implementing robust and efficient parsers quickly and easily..."

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

Monday, 24 September 2007

Book Reviews

Andrei Formiga has been kind enough to write a thorough and impartial review of our book OCaml for Scientists.

Also, we were thrilled to discover that Amazon (who do not even sell OCaml for Scientists) are hosting a book review for Practical OCaml that states "I bought OCaml for Scientists from Flying Frog Consultancy, and it makes for a much better grounding in OCaml...".

OCaml Summer projects at Jane St.

Jane St. Capital are unquestionably one of the most influential industrial players in the OCaml world. They were kind enough to fund a variety of student projects this summer and a set of talks about the projects was recently put on-line. Makes for an interesting read!

More controversy from O'Reily

O'Reily are usually only a publisher of cheap books but they recently diversified into posters. Specifically, they are selling their own rehash of the famous Computer Language History poster in the form of a bigger, color poster that only includes languages that O'Reilly publish books on and omits almost all of the inheritance relationships.

Although the original clearly shows that OCaml is one of the most up-to-date languages in existence, O'Reily's poster indicates that OCaml died five years ago! Perhaps this is when "Développement d'applications avec Objective Caml" stopped selling?

Wednesday, 19 September 2007

XenSource sell for $500M

XenSource, one of the world's most prominent players in virtualization and a customer of Flying Frog Consultancy, recently announced their sale to Citrix for $500M. The core value-add of XenSource's product line over the open source Xen virtualization package is a sophisticated management tool stack written almost entirely in OCaml.

Following the announcement of the sale, Anil Madhavapeddy of XenSource posted an advertisement asking for OCaml programmers to join their team. We were fortunate enough to consult at the Cambridge branch of XenSource last year and I can tell you that they have the most talented engineering team I have ever seen. If you are an expert OCaml programmer I would not hesitate to recommend a position at this company.

If your company uses OCaml, let us know and we can tell the world about your successes!

Saturday, 15 September 2007

Spectral norm

The Computer Language Shootout is a well-known set of benchmarks that is still gradually evolving. Although the shootout is infamous because most of its benchmark tasks are trivially reducible (e.g. computing constants like pi and prime numbers) and that creates a strong subjective bias because submissions must be rejected or selectively crippled, a few contributors have created better benchmark tasks such as k-nucleotide and spectral-norm.

Our primary machines for high performance computing using OCaml are based upon Athlon 64 CPUs. At least on these machines, the current OCaml implementation of the spectral-norm benchmark can be made significantly faster. This post describes how.

The core of the spectral-norm benchmark is a pair of nested loops. For no particular reason, the shootout requires that this functionality be replicated in two separate functions. Let us focus on the first such function as the other is virtually identical:

let eval_A_times_u u v =
let n = Array.length v - 1 in
for i = 0 to n do
v.(i) <- 0.0;
for j = 0 to n do
v.(i) <- v.(i) + eval_A i j * u.(j)
done
done
This implementation, currently on the shootout, takes 14.4s to run with n=5500 on this machine (4400+ Athlon64).

Most of the time is, of course, spent in the inner loop over j. However, the current implementation on the shootout does not hoist the subexpression v.(i) from the inner loop. This can be done by accumulating the result of the inner loop in a variable and storing it in v.(i) only once, after the inner loop completes:

let eval_A_times_u u v =
let n = Array.length v - 1 in
for i = 0 to n do
let vi = ref 0.0 in
for j = 0 to n do
vi := !vi +. eval_A i j *. u.(j)
done;
v.(i) <- !vi
done
This brings the time taken down to 12.0s.

The next most important optimization in the OCaml is to remove bounds checking. Although this can be done globally using the -unsafe flag as the shootout does, this is very bad practice. Specifically, many OCaml programs assume that out of bounds array accesses incur an appropriate exception and compiling them with -unsafe renders such code invalid, essentially changing the semantics of the language.

Using explicitly unsafe array accesses on minimal performance-critical portions of code is much more preferable and this benchmark is a good illustration of how this can be done. Specifically, there is only one array access in the inner loop, to u.(j), and this can be made unsafe. To ensure correctness, we can simply derive n from the length of u rather than v:

let eval_A_times_u u v =
let n = Array.length u - 1 in
for i = 0 to n do
let vi = ref 0.0 in
for j = 0 to n do
vi := !vi +. eval_A i j *. Array.unsafe_get u j
done;
v.(i) <- !vi
done
This brings the time down to 9.4s, over 50% faster than the original.

The forms of optimization described here are generally-applicable and may be used to improve the performance of a wide variety of OCaml programs. For detailed and comprehensive information on high-performance OCaml, read the book OCaml for Scientists. For general information on the OCaml programming language and tutorial articles, read the OCaml Journal.

Friday, 14 September 2007

Combinator Heaven

The OCaml Journal published an article discussing the unique way that functions may be composed in functional languages using combinators:

"The ability to write higher-order functions that compose other functions in interesting ways is one of the most powerful forms of abstraction provided by the functional programming paradigm. Such functions are known as combinators . This article describes the basic concepts behind combinators with a variety of examples to demonstrate how practically useful this form of functional abstraction can be..."

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

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.

Thursday, 26 July 2007

Data Structures in the Standard Library

The OCaml Journal just published its fourth article, covering the List, Array, Set, Map, Hash table, Stack, Queue, String and Weak hash table data structures in detail:

"The OCaml standard library includes a wealth of mutable and immutable data structures that cover a wide variety of needs. This article introduces all of the data structures provided by the OCaml standard library and describes when and how to use each of them..."

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

Review: OcaIDE

The Visual Studio mode for F# has really shown what an IDE can do for a modern functional programming language. We recently took a look at OcaIDE for OCaml and were very impressed with the functionality it provides.

Throwback of inferred types is hugely important when developing programs in languages that support type inference. OcaIDE is on par with Visual Studio in this respect, displaying the inferred types of subexpressions when the mouse is hovered over one. However, this does not provide as much functionality as the type throwback in emacs, which allows the type of an arbitrary selected subexpression to be displayed.

OCamldoc-compatible documentation is parsed correctly and displayed whenever possible. Again, this is the same as the Visual Studio mode, although OcaIDE is slightly prettier and Visual Studio often has problems parsing comments correctly. Editing was always fluid in OcaIDE, with no perceivable stalls.

Interestingly, OcaIDE integrates support for OCaml's bytecode debugger. An usual feature of OCaml's debugger is the ability to step backwards as well as forwards through the execution of a program. However, there is no support for memory or performance profiling and OCaml's excellent design renders a debugger almost useless.

The build system is not so easy to use, mainly because it predates OCaml 3.10 and, consequently, lacks ocamlbuild support as well as support for camlp4. The lack of support for any non-standard parsers raises the question of whether it is worth trying to build an IDE on top of Eclipse in Java rather than writing one from scratch in OCaml.

We believe the OCaml community could benefit greatly from a good IDE and OCaIDE is definitely a step in the right direction. The main advantage of OCaIDE is that it makes it easier for beginners to get started with OCaml. The main disadvantages are lack of development because all tools for OcaIDE must be written in Java or interfaced to Java and there is a lack of tools as a consequence, such as memory and performance profiling.

We have expressed an interest in writing a cheap commercial IDE for OCaml in the past. Let us know if you'd be interested.

Tuesday, 10 July 2007

GUI programming: Sudoku Solver

The latest article in the OCaml Journal describes the design and implementation of a complete GUI application for solving Sudoku puzzles:

"Powerful cross-platform GUI applications can be developed quickly and easily in the OCaml programming language. This article describes the design and implementation of a cross-platform GUI application for solving sudoku puzzles..."

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

Thursday, 21 June 2007

The Essence of Functional Programming

"OCaml is fundamentally a functional programming language and the use of functions instead of objects often leads to shorter and clearer code. Indeed, many of the benefits of functional programming are already known to OO programmers in the form of design patterns..."

To read the rest of this article and more, subscribe to The OCaml Journal today.

Monday, 18 June 2007

High-performance vector graphics update

We just released a new version of Smoke, including a free byte-code edition.

Smoke is a high-performance cross-platform 2D vector graphics library written entirely in OCaml that renders using OpenGL to exploit hardware acceleration. Version 2.01 adds:

  • OCaml 3.10 compatibility
  • Vector text using the Computer Modern fonts (see demo3.ml)

We are working towards typesetting, GUIs and a vector graphics replacement for the OCaml top-level...

How to Leverage Pattern Matching

The jaw-droppingly great OCaml Journal published its first article, covering pattern matching with a detailed case study on term rewriting:

"Compared to conventional programming languages, OCaml takes dynamic dispatch to a whole new level using an approach called pattern matching. This article guides the reader through the fundamental concepts that underpin pattern matching before providing some examples demonstrating the power of pattern matching in general programming..."

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

Saturday, 16 June 2007

OCaml top-level compiling to native code

Alain Frisch recently announced on the OCaml mailing list that he has successfully added support for dynamic linking of native-code compiled OCaml and, in particular, has used this to make OCaml's interactive top-level compile to native code.

This is a tremendous achievement and greatly improves the performance of interactive OCaml, making it an even better technical computing environment.

Friday, 8 June 2007

The OCaml Journal

We just released a subscription journal for articles about the OCaml programming language, starting with an issue for beginners:

http://www.ffconsultancy.com/products/ocaml_journal/

Check back here for article abstracts as they're published!

Tuesday, 5 June 2007

OCaml + Concurrency = JoCaml

The pioneering researchers at INRIA pushed the boundaries of computer programming forward again this week by announcing the first public release of their next-generation concurrent programming language JoCaml.

The JoCaml language draws upon the success of INRIA's OCaml language by augmenting it with a native implementation of the Join calculus to provide a robust mechanism for exploiting concurrency in OCaml programs.

The JoCaml authors present a beautiful distributed ray tracer among their examples, which is derived from our own work.

Combined with core OCaml developments such as a completely revamped camlp4 implementation and the recent surge in new users, the future looks bright for OCaml!

Monday, 28 May 2007

Vector Graphics library for OCaml

We just released a new graphics library for OCaml programmers. The Smoke Vector Graphics library provides easy-to-use, hardware-accelerated vector graphics rendered using OpenGL:

http://www.ffconsultancy.com/products/smoke_vector_graphics/

A compiled bytecode implementation of the library is freely available for download. The source code and Linux executables are provided for three demos.

As the third demo shows, our library facilitates interactivity in the conventional style of GUI programming, with callbacks invoked via events.

We are working on add-ins to provide mathematical typesetting, network visualization, graphing, charting, a new cross-platform vector GUI and securely scripted graphical web programming.

Sunday, 20 May 2007

OCaml whups Lisp on Pythagorean Triplets micro-benchmark

Giovanni Intini recently posted a great suite of programs written in C, Ruby, Erlang and Python that count the number of Pythagorean triplets (a^2 = b^2 + c^2 for integers a, b and c<n):


http://tempe.st/2007/05/erlang-ruby-and-php-battle-it-out/

This micro-benchmark quickly caught the attention of programmers from various backgrounds and snowballed into a miniature language comparison.

We submitted a simple OCaml implementation that turned out to be roughly as fast as the C implementation (faster than -O2 but slower than -O3 -ffast-math) and slightly shorter:

let n = 5000
let () =
let i = ref 0 in
for c=2 to n do
for b=1 to c-1 do
let a = sqrt(float(c*c - b*b)) in
if float(truncate a) = a then incr i
done
done;
print_endline (string_of_int !i)
After several days of conferring and much performance-related deliberation, the Lisp community announced their completion of a longer and slower but "more flexible" solution written in Lisp.

For a thorough introduction to high-performance computing using OCaml, read OCaml for Scientists.

Saturday, 19 May 2007

Functional programmer stole my Job

Middle-class white-collar American computer programmers are feeling the squeeze again today, and its not from Sharon in accounts.

Only months after many programmers lost their jobs when they were offshored to third world countries like Europe, it seems that programming jobs are now being stolen by a second crowd.

Gangs of ruthless functional programmers are overwhelming interviewers by listing programming languages like OCaml, Haskell and even Lisp on their CVs.

The horrifying trend is thought to have begun in Germany, with a growing number of singles citing "OCaml" among their hobbies. In the US, starving unemployed programmers were spotted on street corners holding signs saying "Will code for Food (but only in OCaml)".

The effect is being compounded by the number of employers who now regard unenlightened programmers as second-class citizens, driving a trend of employing functional programmers in the interests of productivity. The result: functional programming is the new black.

The only programmers unaffected by this revolution are the self-employed, who have known for years that functional programming offers order of magnitude improvements in development speed, maitainability, reliability and mojo.

You have to ask yourself one question: is OCaml on your CV?

The OCaml revolution

The man behind the O'Reilly book publishers, Tim O'Reilly, recently released a series of articles analysing book sales in the programming industry and, in particular, devoted one article to breakdown by programming language.

OCaml can be seen right at the bottom under the heading "Irrelevant Programming Languages". The interesting thing from our point of view is that these statistics do not include sales of our book OCaml for Scientists, which introduces professionals in science and engineering to the OCaml programming language as a high-performance tool to help them with their research.

Naturally, by diregarding profits and more prolific publications like magazines, O'Reilly's article shows O'Reilly topping the charts in terms of units sold. Although selling many units is nice, particularly for advertising, most industries are more concerned with profits. To estimate profits it is necessary to take the cost of the book into account. This changes the results drastically and, in particular, penalises O'Reilly for publishing very cheap books.

Several amazing results come from such an analysis. Firstly, Flying Frog Consultancy have long wondered how we could boost sales and compete with mainstream publishers. From these statistics, it seems that we have been beating the mainstream publishers at their own game for some time.
We even outsold Practical OCaml in Q1 2007 in terms of units sold!

Secondly, we had been wondering if OCaml is a comparatively profitable market to enter. According to these statistics, OCaml is one of the most profitable languages to choose, beating Lisp, Scheme, Haskell and even C/C++ and Python.

Thirdly, dissecting the results by profit indicates that OCaml for Scientists is in the top 5% of the world's favorite programming books. This is probably due to the fact that OCaml for Scientists received universally fantastic reviews.

Finally, the growth of the market determines whether or not we can stay. The OCaml market has shown the second largest growth of any programming language, topped only by Ruby. We have felt this ourselves, as sales of our OCaml-related products have quadrupled over the past year and continue to rise.

Overall, we are very happy with the result. So happy that we will write a very cheap introductory book on OCaml and publish it through a mainstream publisher as well as release a second edition of our best-selling book OCaml for Scientists.

We predict that the F# programming language from Microsoft Research (which is derived from OCaml) will explode in popularity over the next year, starting with the publication of Foundations of F# by Robert Pickering later this month, then Expert F# and our own F# for Scientists.

Thursday, 17 May 2007

Rigid Body Simulator

Here is a real-time 2D rigid body simulator that renders some balls bouncing around a scene using OpenGL:

http://www.ffconsultancy.com/ocaml/balls/?ob

The whole program is under 400 lines of OCaml and performance is excellent: the program can simulate 100 balls in real-time with sub-centisecond accuracy on my machine.

Thursday, 26 April 2007

Ray tracer language comparison (update)

We've updated our ray tracer language comparison with better implementations and new timings on a dual-core 4400+ Athlon64:

http://www.ffconsultancy.com/languages/ray_tracer/

OCaml now covers almost the whole range from most succinct language to almost the fastest (only 9% slower than optimized C++!).

Tuesday, 17 April 2007

On-line Journal

Flying Frog Consultancy just started the F#.NET Journal, an on-line publication composed of articles, example source code and tutorial videos aimed at beginner programmers learning the F# programming language from Microsoft Research:

http://www.ffconsultancy.com/products/fsharp_journal/

Given the current explosion in the adoption of functional programming languages, we're considering trying to mimic this success with an OCaml Journal. If you'd be interested in subscribing, please let us know.

Thursday, 12 April 2007

Symbolic Manipulation

For those of you who missed it the first time around, our Benefits of OCaml pages have a section on writing interpreters:

http://www.ffconsultancy.com/ocaml/benefits/interpreter.html

Friday, 23 February 2007

New OpenGL bindings for OCaml

I just stumbled upon an exciting new project that revitalises the use of OpenGL from OCaml:

GLCaml

Hopefully this project will catch on and become the basis an even better OpenGL interface for OCaml in the future.

Cheers,
Jon.

Wednesday, 21 February 2007

Updated Maze Generator

I've updated the Maze Generator on our site to use arrays (instead of a functional map) and continuation passing style instead of an explicit stack. The new version is 30% shorter and several times faster.

Cheers,
Jon.

Friday, 16 February 2007

Benefits of pattern matching

Modern functional programming languages like OCaml provide many beneficial features not found in older languages like Lisp. ML-style pattern matching is one such feature that is heavily used by OCaml programmers both because it is fundamental to the language and because it is useful in many different situations.

In a recent thread on comp.lang.functional entitled "ML vs. Lisp", Paul Rubin asked what a Lisp programmer learning ML should focus on. I suggested pattern matching as one of the more important topics, giving the example of OCaml functions to simplify symbolic expressions:

let rec ( +: ) f g = match f, g with
| Q n, Q m -> Q (n +/ m)
| Q (Int 0), e | e, Q (Int 0) -> e
| f, Add(g, h) -> f +: g +: h
| f, g -> Add(f, g)

let rec ( *: ) f g = match f, g with
| Q n, Q m -> Q (n */ m)
| Q (Int 0), e | e, Q (Int 0) -> Q (Int 0)
| Q (Int 1), e | e, Q (Int 1) -> e
| f, Mul(g, h) -> f *: g *: h
| f, g -> Mul(f, g)

let rec simplify = function
| Q _ | Var _ as e -> e
| Add(f, g) -> simplify f +: simplify g
| Mul(f, g) -> simplify f *: simplify g

Two Lisp programmers responded with Lisp implementations of this function. Nathan Froyd gave an implementation resembling the OCaml code after pattern match compilation:

(defun simplify-common-funcs (xexpr)
(declare (optimize (speed 3)))
(if (atom xexpr)
xexpr
(labels ((make-expr (op f g)
(list op f g))
(optimize-plus (f g)
(cond
((eql f 0) g)
((eql g 0) f)
((and (numberp f) (numberp g)) (+ f g))
(t (optimize-associatively '+ #'optimize-plus f g))))
(optimize-multiply (f g)
(cond
((or (eql f 0) (eql g 0)) 0)
((eql f 1) g)
((eql g 1) f)
((and (numberp f) (numberp g)) (* f g))
(t (optimize-associatively '* #'optimize-multiply f g))))
(optimize-associatively (op opt-func f g)
(cond
((and (listp g) (eq op (first g)))
(let ((a (funcall opt-func f (second g))))
(funcall opt-func a (third g))))
(t (make-expr op f g)))))
(declare (inline make-expr optimize-associatively))
(let* ((op (first xexpr))
(f (simplify-common-funcs (second xexpr)))
(g (simplify-common-funcs (third xexpr))))
(cond
((eq op '+) (optimize-plus f g))
((eq op '*) (optimize-multiply f g)))))))

Pascal Constanza gave a Lisp implementation that used structs instead of s-exprs to represent the symbolic expression and leveraged method dispatch to gain some of the benefits of pattern matching:

(defgeneric simplify-add (x y)
(declare (optimize (speed 3)))
(:method ((x number) (y number)) (+ x y))
(:method ((x (eql 0)) y) y)
(:method (x (y (eql 0))) x)
(:method (x (y add))
(simplify-add (simplify-add x (add-x y)) (add-y y)))
(:method (x y) (make-add :x x :y y)))

(defgeneric simplify-mul (x y)
(declare (optimize (speed 3)))
(:method ((x number) (y number)) (* x y))
(:method ((x (eql 0)) y) 0)
(:method (x (y (eql 0))) 0)
(:method ((x (eql 1)) y) y)
(:method (x (y (eql 1))) x)
(:method (x (y mul))
(simplify-mul (simplify-mul x (mul-x y)) (mul-y y)))
(:method (x y) (make-mul :x x :y y)))

(defgeneric simplify (exp)
(declare (optimize (speed 3)))
(:method (exp) exp)
(:method ((exp add))
(simplify-add (simplify (add-x exp)) (simplify (add-y exp))))
(:method ((exp mul))
(simplify-mul (simplify (mul-x exp)) (simplify (mul-y exp)))))

Firstly, note that the expressiveness of OCaml's built-in pattern matching makes for very concise code (almost half the size). Secondly, note that OCaml's pattern matching provides static checking, catching many possible errors in pattern matches at compile time. Thirdly, performance measurements show that the simple OCaml implementation is 3-20x faster than the Lisp implementations.

So ML-style pattern matching has many benefits and is one of the most interesting aspects of this family of languages.

For more information on pattern matching, see here

Cheers,
Jon.

Tuesday, 13 February 2007

Structure and Interpretation of Computer Programs

This is a famous book that introduces the reader to computer programming using the Scheme language (a simplified dialect of Lisp).

Chris Rathman has been kind enough to upload translations of the code in the book to various other languages, including OCaml:

http://www.codepoetics.com/wiki/index.php?title=Topics:SICP_in_other_languages

The original code mimicked many unwanted features of the Scheme code (particularly sources of run-time error). As Chris is not an expert ML programmer and was having trouble with some of the examples, I decided to lend a helping hand and rewrite much of the code in more idiomatic OCaml.

Although the final two chapters cover the metacircular evaluator (Lisp's EVAL function that was stripped from ML in order to implement static typing) I think the first three chapters present a good opportunity to show how ML can be more concise, expressive, robust and efficient than Lisp the rest of the time.

Cheers,
Jon.

Friday, 2 February 2007

Simple OpenGL demo

I recently added another OCaml demo to my company site. This time it is a simple OpenGL demo that reads vertex information from the file format used by the Stanford mesh database and renders the mesh using diffuse and specular lighting:

http://www.ffconsultancy.com/free/bunny/

Functional programming languages like OCaml often provide a means to "memoize" a function. This entails recording the results of previous function applications so that they can be looked up in the future, without needing to be recomputed.

The concept of memoization can actually be applied to OpenGL with good effect by memoizing rendering calls in an OpenGL display list. This simple OpenGL demo does exactly that. The resulting display list is heavily optimised by the OpenGL driver and performance is superb as a consequence.

Thanks to the simplicity of the OpenGL API and the incredible expressiveness of the OCaml programming language, the entire program (including loading the mesh, setting up the perspective projection and rendering) takes only 85 lines of code.

I have also written a more sophisticated implementation that incrementally computes the silhouette of a mesh in order to render sharp shadows by extruding the silhouette from the light. I'll post this ASAP and probably do a port to F#.

Cheers,
Jon.

Saturday, 13 January 2007

Solving the n-queens problem

The n-queens problem is one of the pedagogical example problems solved by computer scientists. The problem is easy to describe: enumerate all of the ways to place n queens on an nxn chessboard such that no queen is attacking any other.

As a functional programming language with list literals and pattern matching, OCaml can be used to solve this problem quickly and simply. The following OCaml code solves the problem by generating a list of all possible board positions and then searches by considering a queen at each position and filtering out the attacked squares from the remaining list:

open List

let rec safe (x1, y1) (x2, y2) =
x1 <> x2 && y1 <> y2 && x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1;;

let rec search f n qs ps accu = match ps with
| [] -> if length qs = n then f qs accu else accu
| q::ps -> search f n (q::qs) (filter (safe q) ps) (search f n qs ps accu)

let n = try int_of_string Sys.argv.(1) with _ -> 8

let rec init n f = if n=0 then [] else f(n-1) :: init (n-1) f

let ps = flatten (init n (fun i -> init n (fun j -> i, j)))

let print qs =
let a = Array.init n (fun _ -> String.make n '.') in
List.iter (fun (x, y) -> a.(y).[x] <- 'Q') qs;
Array.iter print_endline a;;

let sols = search (fun qs -> print qs; (+) 1) n [] ps 0;;

Cheers,
Jon.