Pascal Cuoq and Damien Doligez. Weak pointers and Hashconsing in Ocaml 3.10.2 |
Abstract: This article describes the implementations of weak pointers, weak hashtables and hashconsing in version 3.10.2 of the Objective Caml system, with focus on several performance pitfalls and their solutions. |
Benjamin Canou, Vincent Balat and Emmmanuel CHAILLOUX. O'Browser : Objective Caml on browsers |
Abstract: We present a way to run Objective Caml programs on a standard, unmodified web browser, with a compatible data representation and execution model, including concurrency. To achieve this, we designed a bytecode interpreter in JavaScript, as well as an implementation of the runtime library. Since the web browser does not provide the same interaction mechanisms as a typical Objective Caml environment, we provide an add-on to the standard library, enabling interaction with the web page. As a result, one can now build the client side of a web application with the standard Objective Caml compiler and run it on any modern web browser. |
luc maranget. Compiling Pattern Matching to good Decisions Trees |
Abstract: We address the issue of compiling ML pattern matching to compact and efficient decisions trees. Traditionally, compilation to decision trees is optimized by (1) implementing decision trees as dags with maximal sharing; (2) guiding a simple compiler with heuristics. We first design new heuristics that are inspired by necessity, a concept from lazy pattern matching that we rephrase in terms of decision tree semantics. Thereby, we simplify previous semantical frameworks and demonstrate a straightforward connection between necessity and decision tree runtime efficiency. We complete our study by experiments, showing that optimizing compilation to decision trees is competitive with the optimizing match compiler of Le Fessant and Maranget (2001). |
Jérôme Vouillon. Lwt: a cooperative thread library |
Abstract: We present a cooperative thread library for Objective Caml. The library is entirely written in Objective Caml and does not rely on any external C function. Programs involving threads are written in a monadic style. This makes it possible to write threaded code almost as regular ML code, even though it has a different semantics. Cooperative threads are especially well suited for concurrent network applications, where threads perform little computation and spend most of their time waiting for input or output, at which time other threads can run. This library has been successfully used in the Unison file synchronizer and the Ocsigen Web server. |
Jean-Christophe Filliatre. A Functional Implementation of the Garsia-Wachs Algorithm |
Abstract: This functional pearl proposes an ML implementation of the Garsia-Wachs algorithm. This somewhat obscure algorithm builds a binary tree with minimum weighted path length from weighted leaf nodes given in symmetric order. Our solution exhibits the usual benefits of functional programming (use of immutable data structures, pattern-matching, polymorphism) and nicely compares to the purely imperative implementation from The Art of Computer Programming. |
Sam Lindley. Many holes in Hindley-Milner |
Abstract: We implement statically-typed multi-holed contexts in OCaml using an underlying algebraic datatype augmented with phantom types. Existing approaches require dynamic checks or more complex type systems. In order to support concatenation we use two type parameters to represent the number of holes in a context as the difference between two Peano numbers. In order to support plugging a context with contexts of different arity we introduce a datatype of lists of contexts of length n with a total of m holes. Further, we extend our representation to allow holes to be marked with additional type information. As an example, we use these marks to implement statically-typed multi-holed XHTML contexts. We take advantage of Garrigue's relaxed value restriction. |
Alec Heller and Jesse Tov. Caml-Shcaml: An OCaml Library for UNIX Shell Programming |
Abstract: Objective
Caml is a flexible, expressive programming language, but for
manipulating Unix processes, nothing beats the terseness and clarity of
Bourne Shell: ls *.docx | wc -l To achieve the same effect in C requires several more lines of code and very likely a glance at the manual page for readdir(3). Despite OCaml's excellent Unix module, which provides access to a wide variety of system calls, as simple as counting the ".docx" files in the current directory is hardly easier in OCaml than in C. The code looks largely the same. Caml-Shcaml addresses this problem by bringing high-level abstractions for Unix systems and shell programming to OCaml. In particular, we take advantage of OCaml's type system to offer statically-checked data pipelines. External Unix processes and internal OCaml stream transducers communicate seamlessly within these pipelines. Caml-Shcaml brings other essential systems concepts into the world of typed functional programming as well, including high-level interfaces to Unix facilities for I/O redirection, signal handling, program execution, and subprocess reaping. |
Michael Rainey, John Reppy and Matthias Blume. Calling variadic functions from a strongly typed language |
Abstract: The importance of providing a mechanism to call C functions from high-level languages has been understood for many years and, these days, almost all statically-typed high-level-language implementations provide such a mechanism. One glaring omission, however, has been support for calling variadic C functions, such as printf. Variadic functions have been ignored because it is not obvious how to give static types to them and because it is not clear how to generate calling sequence when the arguments to the function may not be known until runtime. In this paper, we address this longstanding omission with an extension to the NLFFI foreign-interface framework used by Standard ML of New Jersey (SML/NJ) and the MLton SML compiler. We describe two different ways of typing variadic functions in NLFFI and an implementation technique based on the idea of using state machines to describe calling conventions. Our implementation is easily retargeted to new architectures and ABIs, and can also be easily added to any HOT language implementation that supports calling C functions. |
Andy Gill, Johan Nordlander and Magnus Carlsson. Unrestricted call-by-value recursion |
Abstract: Call-by-value languages commonly restrict recursive definitions by only allowing functions and syntactically explicit values in the right-hand sides. As a consequence, some very appealing programming patterns that work well in lazy functional languages are hard to apply in a call-by-value setting, even though they might not be using laziness for any other purpose than to enable the desired form of recursion. In this paper we present an operational semantics as well as a straightforward implementation technique for unrestricted recursion under call-by-value. On that basis we are able to demonstrate that highly recursive programming idioms such as combinator-based parsing are indeed compatible with call-by-value evaluation. |