Previous week Up Next week


Here is the latest Caml Weekly News, for the week of January 16 to 23, 2007.

  1. ocaml+twt v0.90
  2. ICFP07 Call for Papers
  3. Polymorphic Variants
  4. glome-0.2
  5. Final Call for Papers: TFP 2007, New York, USA
  6. json-static: syntax magic for JSON
  7. Time stamp module floating around?
  8. native-code stack backtraces
  9. color on linux terminal
  10. va_arg values
  11. function definition

ocaml+twt v0.90


Mike Lin announced:
I just posted a new version of ocaml+twt, a preprocessor that lets you use 
indentation to avoid multi-line parenthesization (like Python or Haskell). 

This version introduces a major backwards-incompatible change: the 
eradication of "in" from let expressions, and the need to indent the let 
body (as suggested by the F# lightweight syntax). This reduces the 
familiar phenomenon of long function bodies getting progressively more 
indented as they go along. That is, before where you had: 

let x = 5 in 
  printf "%d\n" x 
  let y = x+1 in 
    printf  "%d\n" y 

You'd now just write: 

let x = 5 
printf "%d\n" x 
let y = x+1 
printf "%d\n" y 

I was hesitant to introduce this feature because it's extra hackish in 
implementation (even moreso than the rest of this house of cards). It also 
removes some programmer freedom, because you cannot have the let body on the 
same line as the let, and you cannot have a statement sequentially following 
the let, outside the scope of the binding. But after playing with it, I 
think it is worthwhile. Please let me know what you think. I am still not 
completely sure that I haven't broken something profound that will force me 
to totally backtrack this change, but let's give it a try. I will obviously 
keep the 0.8x versions around for those who prefer it and for existing code 
(including a lot of my own). 

Standard disclaimer: ocaml+twt is a flagrant, stupendous, 
borderline-ridiculous hack, but it works quite well, I write all my new code 
using it, and I recommend it if you like this style. On the other hand, if 
someone with more free time and knowledge of camlp4 wants to step up, I have 
a couple ideas about how you might do it right...

ICFP07 Call for Papers


Matthew Fluet announced:
                             Call for Papers 
      ICFP 2007: International Conference on Functional Programming 
                   Freiburg, Germany, 1-3 October 2007 
ICFP 2007 seeks original papers on the art and science of functional 
programming. Submissions are invited on all topics from principles to 
practice, from foundations to features, from abstraction to application. 
The scope includes all languages that encourage functional programming, 
including both purely applicative and imperative languages, as well as 
languages with objects and concurrency. Particular topics of interest 
  * Applications and domain-specific languages: systems programming; 
    scientific and numerical computing; symbolic computing; artificial 
    intelligence; databases; graphical user interfaces; multimedia 
    programming; scripting; system administration; distributed-systems and 
    web programming; XML processing; security 
  * Foundations: formal semantics; lambda calculus; type theory; monads; 
    continuations; control; state; effects 
  * Design: algorithms and data structures; modules; type systems; 
    concurrency and distribution; components and composition; relations to 
    object-oriented or logic programming 
  * Implementation: abstract machines; compile-time and run-time 
    optimization; just-in-time compilers; memory management; parallel 
    hardware; interfaces to foreign functions, services, components or 
    low-level machine resources 
  * Transformation and analysis: abstract interpretation; partial 
    evaluation; program transformation 
  * Software-development techniques: design patterns; specification; 
    verification; validation; debugging; test generation; tracing; 
  * Practice and experience: novel results drawn from experience in 
    education or industry 
  * Functional pearls: elegant, instructive examples of functional 

A functional pearl need not report original research results, but it must 
be instructive, elegant, and fun. 

ICFP 2007 also seeks Experience Reports. An Experience Report is a short 
paper (2-4 pages) which need not present novel results, but which should 
provide evidence that functional programming really works or should 
describe obstacles that prevented it from working.  Detailed guidelines 
appear below. 

What's new this year? 
Experienced ICFP authors may want to pay special attention to the points 
below, which are new this year. 
  * Double-blind review 
  * Author-date citations 
  * Supplemental material in a separate document, 
    not appended to the main text 
  * Morning deadline (but equivalent to late afternoon or early evening in 
    many time zones of interest) 
  * Experience Reports 

                       Instructions for authors 

By 11:00 AM Friday, 6 April 2007, Samoan time, submit an abstract of at 
most 300 words and a full paper of at most 12 pages or an Experience 
Report of at most 4 pages. Submissions will be accepted electronically, at 
a URL to be named later. The deadline is set at Samoan time, so if your 
submission is in by 11:00 AM Friday according to your local time, wherever 
you are, the submission will be on time. The world clock at
can give you the equivalent in your local time, e.g., 3:00 PM Friday 
in Portland, 6:00 PM Friday in Boston, and midnight Friday in Freiburg. 

The deadline is firm. 

Your submission should explain its contributions in both general and 
technical terms, clearly identifying what has been accomplished, 
explaining why it is significant, and comparing it with previous work. 
Make the technical content understandable to a broad audience. 

Each submission must adhere to SIGPLAN's republication policy, which 
appears in full at . 
The policy means in part that your paper may not have already appeared in 
a journal, conference, or workshop with published proceedings; that 
you may not submit substantially the same work simultaneously to ICFP 
and to another venue; and that your submission must discuss any 
closely related material, including your own, that was previously 
accepted at a journal, conference, or workshop with or without 
published proceedings. Full details of the policy are available at the 
SIGPLAN site. If you are in any doubt about whether this policy 
applies to your paper, either consult the program chair in advance or 
notify the chair when you submit. To do otherwise risks summary 
rejection of your submission. 

If your submission is accepted, you must assign copyright to ACM. 
Proceedings will be published by the ACM Press. 

Double-blind review 
To increase confidence in the fairness and objectivity of the reviewing 
process, reviewing will be double blind. Make it possible for reviewers to 
evaluate your paper without having to know who you are. It should suffice 
to omit your names from your submission and to avoid revealing your 
identity through citation; detailed guidelines are available at . 

Your submission must be printable on US Letter sized paper and be either 
PDF or PostScript that is interpretable by Ghostscript. If this 
requirement is a hardship, make contact with the program chair at least 
one week before the deadline. 

Your submission must be at most 12 pages (4 pages for an Experience 
Report), including bibliography and figures, in the standard ACM 
conference format: two columns, nine-point font on a ten-point baseline, 
with pages 20pc (3.33in) wide and 54pc (9in) tall, with a column gutter of 
2pc (0.33in). (A suitable LaTeX class file is available from SIGPLAN; 
see . Categories, 
keywords, and so on are optional.) If you wish to supply material beyond 
the 12-page limit, up to and including a full technical report, you may 
attach a separate document to your submission, on the understanding that 
reviewers are not expected to read it. (As a particular example, if you 
feel that your submission should be supported by a lengthy technical 
report, do not cite such a technical report on the web, since doing so 
would reveal your identity. Please instead attach that report to your 
submission.)  Detailed instructions for attaching supplementary documents 
will be available on the submission web site. 

The length limit is firm; submissions that do not meet these guidelines 
will not be considered. 

We recommend (but do not require) that you put your citations into 
author-date form. This procedure makes your paper easier to review. For 
example, if you cite a result on testing as ``(Claessen and Hughes 
2000)'', many reviewers will recognize the result instantly. On the other 
hand, if you cite it as ``[4]'', even the best-informed reviewer has to 
page through your paper to find the reference. By using author-date form, 
you enable a knowledgeable reviewer to focus on content, not arbitrary 
numbering of references. LaTeX users can simply use the natbib package 
along with the plainnat bibliography style. 

Author response 
You will have a 48-hour period (11:00 23 May to 11:00 25 May 2007 Samoa 
time) to read and respond to reviews. Details of the author-response 
process will be available as it approaches. 

                     Special categories of papers 

In addition to research papers, ICFP solicits two kinds of papers that do 
not require original research contributions: functional pearls, which are 
full papers, and Experience Reports, which are limited to four pages. 
Authors submitting such papers may wish to consider the following advice. 

Functional pearls 
To paraphrase both Jon Bentley and Richard Bird, the ideal pearl goes 
beyond solid engineering into the realm of insight and creativity. Just as 
a natural pearl grows from a grain of sand that has irritated an oyster, a 
topnotch functional pearl should grow from a real problem that has 
irritated a programmer. A pearl should be polished, elegant, instructive, 
and entertaining. Ideally it should teach important programming techniques 
and fundamental design principles. Past pearls have included instructive 
examples of program calculation or proof, nifty presentations of old or 
new data structures, and interesting applications and programming 

Papers submitted to ICFP as pearls often miss the mark, by being too 
trivial, too complicated, or somehow not quite the elegant solution one 
hopes for. The key to an accepted pearl is polishing. Your pearl is likely 
to be rejected if your readers get bored, if the material gets too 
complicated, if too much specialized knowledge is needed, or if the 
writing is distasteful. 

Richard Bird advises: 
  * Throw away the rule book for writing research papers. 
  * Get in quick; get out quick. 
  * Be self-contained; don't go deep into related work, with lengthy 
  * You are telling a story, so some element of surprise is welcome. 
  * Above all, be engaging. 
  * Give a talk on the pearl to non-specialists, your students, or your 
    department.  If you changed the order of presentation for the talk, 
    consider using the new order in the next draft. 
  * Put the pearl away for a while, then take it out and polish it again. 

Experience reports 

ICFP has long solicited submissions on the practice and experience of 
functional programming. But reports of experience are inherently different 
from research papers, and when judged by the criteria of scientific merit, 
novelty, or research contribution, they have not competed well against 
traditional ICFP submissions. Yet we believe that the functional- 
programming community would benefit from being able to draw on and cite 
the experience of others. For this reason, we have introduced the ICFP 
Experience Report. 

Unlike a normal ICFP paper, the purpose of an Experience Report is not to 
add to the body of knowledge of the functional-programming community. 
Rather, the purpose of an Experience Report is to help create a body of 
published, refereed, citable *evidence* that functional programming really 
works---or to describe obstacles that prevented it from working. 

An Experience Report is distinguished from a normal ICFP paper by its 
title, by its length, and by the criteria used to evaluate it. 

  * Both in the proceedings and in any citations, the title of each 
    accepted Experience Report must begin with the words 
    "Experience Report", followed by a colon. 

  * Experience Reports are limited in length: the suggested length is 
    2 pages and the maximum length is 4 pages. Each accepted Experience 
    Report will be presented at the conference, but depending on the 
    number of Experience Reports and regular papers accepted, authors of 
    Experience Reports may be asked to give shorter talks. 

  * Because the purpose of Experience Reports is to enable our community 
    to accumulate a published, citable body of evidence about the efficacy 
    of functional programming, an acceptable Experience Report need not 
    present novel results or conclusions. It is sufficient if the Report 
    states a clear thesis and provides supporting evidence. The thesis 
    must be relevant to ICFP, but it need not be novel. 

    The program committee will accept or reject Experience Reports based 
    on whether they judge the evidence to be convincing. Anecdotal 
    evidence will be acceptable provided it is well argued and the author 
    explains what efforts were made to gather as much evidence as 
    possible. The committee will be especially convinced by evidence that 
    includes *comparisons* of situations before and after the introduction 
    or discontinuation of functional programming. Evidence drawn from a 
    single person's experience may be sufficient, but more weight will be 
    given to evidence drawn from the experience of groups of people. 

Possible topics for an Experience Report include, but are not limited to 

  * Insights gained from real-world projects using functional programming 

  * Comparison of functional programming with conventional programming in 
    the context of an industrial project or a university curriculum 

  * Project-management, business, or legal issues encountered when using 
    functional programming in a real-world project 

  * Curricular issues encountered when using functional programming in 

  * Real-world constraints that created special challenges for an 
    implementation of a functional language or for functional programming 
    in general 

An Experience Report should be short and to the point: if functional 
programming worked for you in the same ways it has worked for others, you 
need only to summarize the results---the main part of your paper should 
discuss how well it worked and in what context. Most readers will not want 
to know all the details of your project and its implementation, but please 
characterize your project and its context well enough so that readers can 
judge to what degree your experience is relevant to their own projects. Be 
especially careful to highlight any unusual aspects of your project. Also 
keep in mind that specifics about your project are more valuable than 
generalities about functional programming; for example, it is more 
valuable to say that your team delivered its software a month ahead of 
schedule than it is to say that functional programming made your team more 

If your paper not only describes experience but also presents new 
technical results, or if your experience refutes cherished beliefs of the 
functional-programming community, you may be better off submitting it as a 
full paper, which will be judged by the usual criteria of novelty, 
originality, and relevance. If you unsure in which category to submit, the 
program chair will be happy to help you decide. 

                          Other information 

Conference Chair 
Ralf Hinze (Universität Bonn) 

Program Chair 
Norman Ramsey 
Harvard University 
Cambridge, MA, 02148 USA 
Phone: +1 617 496 8615 

Mail sent to the address above is filtered for spam. If you send mail and 
do not receive a prompt response, particularly if the deadline is looming, 
feel free to telephone and reverse the charges. 

Program Committee 
Nick Benton (Microsoft Research) 
Matthew Fluet (Toyota Technological Institute) 
Jeremy Gibbons (University of Oxford) 
Kevin Hammond (University of St Andrews) 
Bastiaan Heeren (Utrecht University) 
Graham Hutton (University of Nottingham) 
Mark P. Jones (Portland State University) 
Gabriele Keller (University of New South Wales) 
Fabrice Le Fessant (INRIA/LIX, France) 
Todd Millstein (UCLA) 
Mike Sperber (DeinProgramm) 
Christopher A. Stone (Harvey Mudd College) 
Andrew Tolmach (Portland State University and INRIA Rocquencourt) 
Janis Voigtländer (Technische Universität Dresden) 
Stephanie Weirich (University of Pennsylvania) 

Important Dates 
Submission:       11:00 6 April 2007, Samoa time (AST) 
Author response:  11:00 23 May to 11:00 25 May 2007 (AST) 
Notification:     8 June 2007 
Final papers due: 20 July 2007 

ICFP 2007 Web Site 

Special Issue of JFP 
Authors of the best final papers, as determined by the program committee, 
will be invited to submit journal versions for a special issue of the 
Journal of Functional Programming.

Polymorphic Variants


Continuing the thread from last week, Jacques Garrigue said:
> So... why actually are polymorphic variants useful? Why can't they simply be 
> implemented as normal, concrete (or how would you call them? ...) variants? 

The original motivation was for the LablTk library, where some types 
(index for instance) have lots of small variations. At that point 
there where several options 
* overloading (but ocaml loathes overloading, you could say that the 
  total absence of overloading is essential to the language) 
* refinement types: define a type with all constructors, and have 
  restricted versions of it where only some constructors are allowed 
* full polymorphism, i.e. polymorphic variants 
If you eliminate the first option, then the choice is between 
refinement types and polymorphic variants. Refinement types are rather 
attractive: they combine precise typing with explicit declarations. 
The arguments in favour of polymorphic variants are 
* they were somehow easier to add, as they are an orthogonal extension 
  of the type system 
* one can add new cases afterwards. 
* they are defined structurally: two identical definitions in two 
  different modules are equivalent. This can be pretty handy at times. 
* you don't need to open a module to use them: mixes nicely with ocaml 
  programming style 

>From modularity considerations, it ends up being nicer to write 

     type t = [`A of int |`B of bool] 
     type u = [t | `C of char] 
     type u = A of int | B of bool | C of char 
     type t = u[A B] 
Afterwards I discovered that, using some idioms, they also allow 
extensible programs in a very concise way. (Much more concise than 
objects, when they are relevant.) 

> Doesn't the use of polymorphic variants just mess up the function type? 

What do you mean by "mess up the function type"? 
If you mean that, without type annotations, types and errors become 
very hard to read, this is true, but the manual explicitely encourages 
to add type annotations :-) 
> I'm not orthogonally against polymorphic variants, it's just that I am 
> looking for an alternative concept that could be used instead... Maybe 
> subtyped records? 

In terms of expressiveness, you can simulate polymorphic variants 
using objects (which are subtyped records,) but this is often much 
more verbose, and requires higher order types. I have some code using 
objects (visitor pattern), recursive modules, lazyness, and private 
row types, in an utterly non trivial way, just to do what can be done 
by standard recursive function definitions using polymorphic variants...
Tom then said and Jacques Garrigue replied:
> > The original motivation was for the LablTk library, where some types 
> > (index for instance) have lots of small variations. At that point 
> > there where several options 
> > * overloading (but ocaml loathes overloading, you could say that the 
> >   total absence of overloading is essential to the language) 

> Is there a reason for that? Is it only hard to implement or are there any 
> conceptual / strategical / theoretical reasons? 

There are two kinds of theoretical reasons. 
The most theoretical one is about semantics: with generic overloading, 
all your semantics must take types into account. This is a problem as 
most theoretical studies of lambda-calculus are based on so-called 
erasure semantics, where types are discarded at execution. So this 
means you must design your own, more complex semantics. Not that this 
reason may not apply to constructor or record overloading, if you do 
not allow the semantics to change according to the type. 

The other one is about type inference. Basically, overloading has a 
huge impact on overloading. The direct way to handle it, using types 
alone, is deeply disruptive, as it means that some programs will be 
refused for lack of type information. It is very hard to define a 
clear criterion on which programs should be refused, notwithstanding 
internal details of the compiler. This also applies to record and 
constructor overaloading. There are other approach the problem, with 
constrained type variables (either Haskell's type classes or G'Caml's 
generic type variables,) but of course they add complexity to the type 
system. And it is not clear that they solve the problem for 
constructor and record overloading: in Haskell, records fields are not 
overloaded, and constructor overloading has to be done by hand for 
each type, through an explicit encoding into type classes. 

Both reasons have practical impact. For the first one, using erasure 
semantics means that the programmer also can discard types when 
understanding the runtime behaviour of a program. For the second one, 
you can write code that is maximally polymorphic, without too much 
fear about the impact of performance (equality is overloaded, so 
it still matters...) or strange ambiguity-related error messages. 

So for the time being ocaml keeps to no overloading at all. 

> > OCaml does not, as far as I know, have any structural typing for 
> > records.. 

Not for records, but for objects. From a type-theoretic point of view 
they are just equivalent. 
> Hm... Actually, what I had in mind is nominal subtyping... similar to 
> objects, in fact, objects in C++-like languages, just that they have no 
> class methods. 

Reading the description below, this all looks nice, independently of 
the semantics limitation described above. However, you can kiss 
farewell to type inference. With such an extensive overloading, you 
would need type annotations all over the place. 
By the way, this all looks likes the "used this feature in C++" 
syndrome. Sure C++ is incredibly powerful. But it is built on rather 
shaky theoretical fundations. So you can't expect to bring everything 
from C++ to a new language. Why not think about new ways to solve 
problems :-) 
(To be completely honest, this also looks a bit like ML2000, and the 
Moby language, which has a sound theoretical fundation, but never 
really took off. You might want to go see for yourself.) 
Jacques Garrigue 

> Now... close your eyes (but try to continue reading this ;) ) and imagine 
> you're in a dreamworld. You are programming in a language that has 
>   * function overloading that allows you to have 
>        length "abcd" + length [1; 2; 3] 
>   * Constructor overloading, eliminating the need of 
>        type parse_expression = 
>            Pexp_name of string 
>          | Pexp_constant of constant 
>          | Pexp_let of (pattern * parse_expression) * parse_expression 
>          | Pexp_apply of parse_expression * parse_expression list 
>          | Pexp_try of parse_expression * (pattern * parse_expression) list 
>        type typed_expression = 
>            Texp_ident of ident 
>          | Texp_constant of constant 
>          | Texp_let of (pattern * typed_expression) * typed_expression 
>          | Texp_apply of typed_expression * typed_expression list 
>          | Texp_try of typed_expression * (pattern * typed_expression) list 
>     as it can be coded as 
>        type parse_expression = 
>            Name of string 
>          | Constant of constant 
>          | ... 

>        type typed_expression = 
>            Ident of ident 
>          | Constant of constant 
>          | ... 

>   * nominal subtyping of records, with overloaded field names: 
>        type widget = {x : float; y : float; width: float; height: float} (* 
> top-level type *) 
>        type button = {widget | text : string } 
>        type checkbox = {button | checked : bool} 
>        type image = {widget | url : string} 

>        type vector = {x : float; y : float} 
>        type document {url : url} 

>     so subtypes could be applied to a function 
>        fun move : widget -> (float * float) -> unit 

>        let chk = {x = 0.0; y = 0.0; width = 10.0; height = 12.0; text = 
> "Check me!"; checked = false} 
>        move chk (3.0, 3.0) 
>     and types could be "discovered" at runtime: 
>        let draw widget = 
>          typematch widget with 
>              w : widget -> draw_box (w.x, w.y, w.height, w.width) 
>            | b : button -> draw_box (b.x, b.y, b.height, b.width); draw_text 
> b.text 
>            | i : image -> draw_image i.url (i.x, i.y) 
>            | ... 

> Do you think you would be "satisfied" even without polymorphic variants? 

> I am not saying this just for fun... I want to create a language with 
> overloading, but I kinda don't really like polymorphic variants... thou if 
> they turn out to be really useful, I would probably start to like them. 

> Any comments?
skaller said and Jacques Garrigue replied:
> > The most theoretical one is about semantics: with generic overloading, 
> > all your semantics must take types into account. This is a problem as 
> > most theoretical studies of lambda-calculus are based on so-called 
> > erasure semantics, where types are discarded at execution. 
> Can you explain this more? The kind of overloading I'm used 
> to is a matter of lookup not semantics, i.e. its just syntactic 
> sugar to save the human reader's memory. 

Because you're doing some partial evaluation :-) 
Namely you can view an overloaded function as a function taking extra 
hidden parameters: the types of its arguments. If these types are 
monomorphic, then you can immediately partially evaluate your function 
to choose the right implementation. But if they are polymorphic, you 
need to pass extra information around. This is what is done in Haskell 
for instance, passing dictionnaries for type classes. 
So an alternative view is that overloading is a type dependent 
translation from the source code to an explicit version. You can only 
drop the types after this translation. So this means that you cannot 
understand the source code locally: you need to be aware of the type 
information around it. 
> > Reading the description below, this all looks nice, independently of 
> > the semantics limitation described above. However, you can kiss 
> > farewell to type inference. With such an extensive overloading, you 
> > would need type annotations all over the place. 
> Felix makes this tradeoff. Types are deduced bottom up (s-attributes), 
> so variables and function return types are calculated, but function 
> parameters must be explicitly typed. 

This works if you don't add either subtyping or return-type 
overloading to the mix. Then you must also know the type of variables 
and the return type of functions. 
> Even in Ocaml it is necessary to write some annotations 
> in two cases: 
> (a) hard to understand error messages from type inference 

> (b) polymorphic variants 

This is not exactly the same thing, as these annotations have no 
impact on the semantics. Of course, one could say: if we have the 
annotation, why not use it for the semantics? But this is another 
story, with different implications. 
> On the other hand some code would just be impossible 
> without overloading. For example C has 
>    char, short, int, long, long long 
>    unsigned versions 
>    float, double, long double 

> which is 13 distinct 'number' types, and I would hate 
> to have to write: 

>    1 int_add 2 
>    1L long_add 2L 

Actually this is not only overloading that is used here, but also 
automatic conversions. When writing numeric computations in ocaml, I 
find it just as painful to have to add float_of_int, as to add the dot 
after all operators. (In number of characters, float_of_int might be 
the biggest...) 
For overloading alone, the module system could help. 
If we had the operators defined with different types in each of the 
numeric type modules, then one could just choose the numeric type used 
with "open Mynumtype". This is one of the reasons I pushed for having 
a local "let open" construct... which can be simulated by "let 
module", at a slight cost. 
> So in some cases with inference and without overloading, 
> *you need the annotations anyhow*, they just go into the 
> function names in an unprincipled manner, instead of going 
> into the function parameter types in a principled -- 
> and indeed syntactically enforced -- manner. 

I believe this is the strongest argument for overloading: that it 
allows using types in a principled way. Of course, whether this is 
really principled depends on the code you write...
Christophe TROESTLER said and Jacques Garrigue answered:
> > [...] I have some code using objects (visitor pattern), recursive 
> > modules, lazyness, and private row types, in an utterly non trivial 
> > way, just to do what can be done by standard recursive function 
> > definitions using polymorphic variants... 
> Sounds like a good case to see & learn the power of polymorphic 
> variants in action.  Are the two codes available somewhere (if 
> possible with some explanations ?) or are you simply referring to your 
> paper "Code reuse through polymorphic variants" ? 

Well, I am. Other examples end up being much longer, even using 
polymorphic variants :-) 
But still, I include at the end of this mail the code to obtain a 
fully extensible purely functional polymorphic visitor pattern. 
(This is the polymorphic part that is particularly hard, even more 
if you want to stay purely functional.) 

For comparison, here is the equivalent complete code using polymorphic 
variants. Note that there is no explicit visitor pattern: the match 
construct provides it, with all the polymorphism needed. 

type 'a eadd = [ `Num of int | `Add of 'a * 'a ] 
let eval_add eval_rec : 'a eadd -> int = function 
  | `Num i -> i 
  | `Add (e1, e2) -> eval_rec e1 + eval_rec e2 
let rec eval_add' e = eval_add eval_add' e 
(* val eval_add' : ('a eadd as 'a) -> int *) 
type 'a eaddneg = ['a eadd | `Neg of 'a] 
let eval_add_neg eval_rec : 'a eaddneg -> int = function 
  | #eadd as e -> eval_add eval_rec e 
  | `Neg e -> - eval_rec e 
let rec eval_add_neg' e = eval_add_neg eval_add_neg' e 
(* val eval_add_neg' : ('a eaddneg as 'a) -> int *) 
let n = eval_add_neg' (`Add (`Neg(`Add(`Num 3, `Num 2)), `Num 7)) 
(* val n : int = 2 *) 

This also means that providing a method returning a polymorphic 
variant describing the contents of an object is probably a simpler 
approach to implementing the visitor pattern, even for objects. Here 
is the code needed if you still want to use objects. 

class type ['a] expr = object method repr : 'a end 
let rec eval_add_expr (e : _ expr) = eval_add eval_add_expr e#repr 
(* val eval_add_expr : ('a eadd expr as 'a) -> int *) 
let rec eval_add_neg_expr (e : _ expr) = eval_add_neg eval_add_neg_expr e#repr 
(* val eval_add_neg_expr : ('a eaddneg expr as 'a) -> int *) 


Jacques Garrigue 

(* A fully extensible polymorphic visitor pattern. 
   Code written with Keiko Nakata *) 

class type ['a,'exp] visit_add = object 
  method visitNum : int -> 'a 
  method visitAdd : 'exp -> 'exp -> 'a 

module type AddTE = sig 
  type ('a,'exp) t 
  type exp = < accept : 'a. ('a, exp) t -> 'a > 
  val num : int -> exp 
  val add : exp -> exp -> exp 

module type AddT = sig 
  include AddTE 
  val eval : (int, exp) t Lazy.t 

module AddF(X : AddT with type ('a,'exp) t = private ('a,'exp) #visit_add) = 
  type ('a, 'exp) t = ('a, 'exp) X.t 
  class type exp = object ('e) method accept : 'a. ('a, 'e) t -> 'a end 
  class num x = object (_ : #exp) method accept v = v#visitNum x end 
  let num x = new num x 
  class add a b = object (_ : #exp) method accept v = v#visitAdd a b end 
  let add x = new add x 
  class eval = object (eval) 
    method private visit (e : exp) = e#accept (Lazy.force X.eval) 
    method visitNum (i : int) = i 
    method visitAdd r l = eval#visit r + eval#visit l 
  let eval = lazy (new eval) 

module rec Add : AddT with type('a,'exp) t = ('a,'exp) visit_add = AddF(Add) 

class type ['a,'exp] visit_add_neg = object 
  inherit ['a,'exp] visit_add 
  method visitNeg : 'exp -> 'a 

module type AddNegT = sig 
  include AddT 
  val neg : exp -> exp 

module AddNegF(X : AddNegT with 
               type ('a,'exp) t = private ('a,'exp) #visit_add_neg) = 
  module Add = AddF(X) 
  include (Add : AddTE with type ('a,'e) t = ('a,'e) X.t) 
  class neg x = object (_ : #Add.exp) method accept v = v#visitNeg x end 
  let neg x = new neg x 
  class eval = object (eval) 
    inherit Add.eval 
    method visitNeg e = - eval#visit e 
  let eval = lazy (new eval) 

module rec AddNeg : AddNegT with type ('a,'exp) t = ('a,'exp) visit_add_neg = 

open AddNeg 
let n = (add (neg (add (num 3) (num 2))) (num 7))#accept (Lazy.force eval)



Jim Snow announced:
New version (0.3) of glome is up: now with a new more elegant (and 
presumably asymptotically optimal but still abysmally slow) kdtree 
compiler, which unfortunately segfaults on large models.  (Thanks to the 
"marshalling limits" thread, I discovered that the size of the kdtree I 
can construct depends on the size of the stack.  I shall have to look 
into this further.)  It is also free of objects - I used Jon Harrop's 
suggestion to implement mutual recursion by passing the generic 
rayintersection function as an argument to any of the rayintersection 
functions that need to be recursive.  (It seems to me like an odd 
solution, but I think I can live with it.)  Mutation has been removed 
from much of the rayintersection code, (also at Jon's suggestion) which 
actually sped things up noticeably (about 15% or so). 
Webpage is here: 

Jon Harrop wrote: 
> It didn't the last time I looked. Using "include" instead of "open" is often 
> faster, probably for that reason. 

I'll have to experiment with that and see what happens. 

> > There are some hybrid renderers that do just that.  There are some 
> > reasons not to do that, though; for instance, ray tracing scales better 
> > on big models (see, for instance, 
> >
> That simply isn't true. You can use trees with OpenGL and get the same 
> asymptotic efficiency whilst also being 100x faster in real terms. 

> I've written a planet renderer that adaptively tesselates a 2^80-triangle 
> planet in real-time for OpenGL. 

> I've written a 2D vector graphics engine that adaptively tesselates PostScript 
> paths into triangles so you can fly around 1Gb PDF images in real time. 

> If what you said was true, that wouldn't have been possible. 

Perhaps I should be more specific about exactly what it is that is 
scaling.  With level-of-detail schemes (which could apply to ray-tracing 
as well as GL), you can render datasets of enormous complexity, provided 
you aren't trying to render it all at the same time.  Your planet demo 
looks very interesting, but it looks like your polygon counts at any 
particular moment aren't very high.  If you add some realistic 
vegetation, the high polgygon counts would slow things down quite a 
bit.  OpenGL scales linearly with the number of triangles it has to 
draw; ray-tracers scale logarithmically.  You can avoid some of the 
memory overhead of large scenes by using instancing, but GL still has to 
draw every single triangle. 
Ray-tracing has its own costs; sorting an acceleration structure, for 
instance, can be very slow.  Also, they currently only surpass the 
performance of traditional polygon renderers on very complex scenes.   
For most current rendering problems, it makes more sense to use GL right 
now.  But as computers get faster, and real-time global illumination 
starts to become feasible, ray tracing is likely to look very 
appealing.  This is my opinion; you are free to disagree. 

> Ray tracing is simply a bad way to render images, unless they 
> are closeups of reflective spheres. 

Opinions vary.  So do datasets and application requirements. 
> > So, I switched over to objects.  This reduced 
> > memory use a little, I think, but didn't help much.  It did make things a 
> > little slower, though.  There's some more detailed discussion over at 
> > 

> What is the memory use of my version like? 

About 1.5 gigs for the 800k triangle level 4 sphereflake, same as my 
version 0.2.  I think the memory consumption is elsewhere.  Most of the 
memory gets consumed as the kdtree is being built. 
> Apart from the texture mapping bugs, check out these screenshots of my planet 
> demo. Now write me a ray tracer that can do that... 

I doubt that whatever level-of-detail algorithms you employ in any way 
preclude the use of raytracing, it would just be rather slow.  (The 
OpenRT people, for instance, are working on a drop-in OpenGL 
replacement, and the XFRT are working on an OpenRT replacement that is 
actually open.)  Now write me an OpenGL app that can render this 
correctly: :) 
Nathaniel Gray wrote: 
> I wonder if you really need the mutual recursion.  You can often avoid 
> mutual recursion by using closures.  Instead of, say, a list of 
> objects with an isect (intersect) method you can use a list of 
> closures.   

That's more or less what my original implementation did.  I switched to 
objects because I wasn't sure if closures were allocating space 
efficiently.  Then I switched to my current implementation because 
calling object methods is slow (as evidenced by the results presented in 
the "Benchmarking different dispatch types" thread).  In the end, I 
don't think it made a big difference - I'm just not intersecting with 
very many primitives per ray.  Every little bit helps, though.

Final Call for Papers: TFP 2007, New York, USA


Marco T Morazan announced:
Trends in Functional Programming 2007 
New York, USA 
April 2-4, 2007 

NEW: Abstract submission is now opened! Link: 

NEW: Invited Talk: John McCarthy, Standford University 

The symposium on Trends in Functional Programming (TFP) is an 
international forum for researchers with interests in all aspects of 
functional programming languages, focusing on providing a broad view of 
current and future trends in Functional Programming. It aspires to be a 
lively environment for presenting the latest research results through 
acceptance by extended abstracts. A formal post-symposium refereeing 
process then selects the best articles presented at the symposium for 
publication in a high-profile volume. 
TFP 2007 is co-hosted by Seton Hall University and The City College of New 
York (CCNY) and will be held in New York, USA, April 2-4, 2007 at the CCNY 


The symposium recognizes that new trends may arise through various routes. 
As part of the Symposium's focus on trends we therefore identify the 
following five article  categories. High-quality articles are solicited in 
any of these categories: 

Research Articles        leading-edge, previously unpublished research 
Position Articles          on what new trends should or should not be 
Project Articles           descriptions of recently started new projects 
Evaluation Articles       what lessons can be drawn from a finished 
Overview Articles         summarizing work with respect to a trendy 

Articles must be original and not submitted for simultaneous publication 
to any other forum. They may consider any aspect of functional 
programming: theoretical,  implementation-oriented, or more 
experience-oriented. Applications of functional programming techniques to 
other languages are also within the scope of the symposium. 

Articles on the following subject areas are particularly welcomed: 

o Dependently Typed Functional Programming 
o Validation and Verification of Functional Programs 
o Debugging for Functional Languages 
o Functional Programming and Security 
o Functional Programming and Mobility 
o Functional Programming to Animate/Prototype/Implement Systems from 
Formal or Semi-Formal Specifications 
o Functional Languages for Telecommunications Applications 
o Functional Languages for Embedded Systems 
o Functional Programming Applied to Global Computing 
o Functional GRIDs 
o Functional Programming Ideas in Imperative or Object-Oriented Settings 
(and the converse) 
o Interoperability with Imperative Programming Languages 
o Novel Memory Management Techniques 
o Parallel/Concurrent Functional Languages 
o Program Transformation Techniques 
o Empirical Performance Studies 
o Abstract/Virtual Machines and Compilers for Functional Languages 
o New Implementation Strategies 
o any new emerging trend in the functional programming area 

If you are in doubt on whether your article is within the scope of TFP, 
please contact the TFP 2007 program chair, Marco T. Morazan, at 


Acceptance of articles for presentation at the symposium is based on the 
review of extended abstracts (6 to 10 pages in length) by the program 
committee. Accepted  abstracts are to be completed to full papers before 
the symposium for publication in the draft proceedings and on-line. 
Further details can be found at the TFP 2007 website. 


In addition to the draft symposium proceedings, we intend to continue the 
TFP tradition of publishing a high-quality subset of contributions in the 
Intellect series on Trends in Functional Programming. 


Abstract Submission: February 1, 2007 
Notification of Acceptance: February 20, 2007 
Registration Deadline: March 2, 2007 
Camera Ready Full Paper Due: March 9, 2007 
TFP Symposium: April 2-4, 2007 


John Clements                   California Polytechnic State University, 
Marko van Eekelen               Radboud Universiteit Nijmegen, The 
Benjamin Goldberg               New York University, USA 
Kevin Hammond           University of St. Andrews, UK 
Patricia Johann                 Rutgers University, USA 
Hans-Wolfgang Loidl             Ludwig-Maximilians Universität München, 
Rita Loogen                     Philipps-Universität Marburg, Germany 
Greg Michaelson         Heriot-Watt University, UK 
Marco T. Morazán (Chair)        Seton Hall University, USA 
Henrik Nilsson                  University of Nottingham, UK 
Chris Okasaki                   United States Military Academy at West 
Point, USA 
Rex Page                        University of Oklahoma, USA 
Ricardo Pena                    Universidad Complutense de Madrid, Spain 
Benjamin C. Pierce              University of Pennsylvania, USA 
John Reppy                      University of Chicago, USA 
Ulrik P. Schultz                                University of Southern 
Denmark, Denmark 
Clara Segura                    Universidad Complutense de Madrid, Spain 
Jocelyn Sérot                   Université Blaise Pascal, France 
Zhong Shao                      Yale University, USA 
Olin Shivers                    Georgia Institute of Technology, USA 
Phil Trinder                    Heriot-Watt University, UK 
David Walker                    Princeton University, USA 


Symposium Chair:        Henrik Nilsson, University of Nottingham, UK 
Programme Chair:        Marco T. Morazan, Seton Hall University, USA 
Treasurer:              Greg Michaelson, Heriot-Watt University, UK 
Local Arrangements:     Marco T. Morazan, Seton Hall University, USA 

*************************************************************************** ********* 
Dr. Marco T. Morazan 
TFP 2007 
Program Committee Chair

json-static: syntax magic for JSON


Martin Jambon announced:
I am releasing a syntax extension which translates quasi-OCaml type 
definitions into converters from/to generic JSON data: 
   (version 0.9.0, BSD license) 

JSON (JavaScript Object Notation) is a language-neutral data format, which 
is readily available in JavaScript, but also for many other 
programming languages thanks to its simplicity. 

This tool uses the json-wheel library that Mika Illouz and myself released 
a few weeks ago. Using the json-static facility is not mandatory at all, 
but it can be a timesaver. 

For example, the following declaration defines the type of a point object: 

   type json point = < x: float; y: float > 

This automatically makes two functions available, with the following 

   val json_of_point : point -> Json_type.t 
   val point_of_json : Json_type.t -> point 

Json_type.t is the type of any JSON data, as defined by the json-wheel 

A typical use of this library is illustrated by an HTTP client that 
queries a web service which returns JSON data. There is an example of a 
program that queries Yahoo!'s JSON web service:

Time stamp module floating around?


Denis Bueno asked and Chris King answered:
> I'm looking for simple bit of code that will print human-readable 
> timestamps. Something suitable for a log file. 

I noticed Calendar [1] on the Hump a while ago... it looks pretty 
useful.  The API includes a pretty printer. 
skaller also answered:
Scrap used in Felix for lines like: 
//Timestamp: 2007/1/12 18:36:37 UTC 
//Timestamp: 2007/1/13 5:36:37 (local) 

let tim() = 
  let now = (Unix.times()).Unix.tms_utime in 
  let elapsed = now -. !last_time in 
  last_time := now; 

let format_time tm = 
  si (tm.Unix.tm_year + 1900) ^ "/" ^ 
  si (tm.Unix.tm_mon + 1) ^ "/" ^ 
  si tm.Unix.tm_mday ^ " " ^ 
  si tm.Unix.tm_hour ^ ":" ^ 
  si tm.Unix.tm_min ^ ":" ^ 
  si tm.Unix.tm_sec 
  (* Time initialisation *) 
  let compile_start = Unix.time () in 
  let compile_start_gm = Unix.gmtime compile_start in 
  let compile_start_local = Unix.localtime compile_start in 
  let compile_start_gm_string = format_time compile_start_gm ^ " UTC" in 
  let compile_start_local_string = format_time compile_start_local ^ 
" (local)" in

native-code stack backtraces


Xavier Leroy said:
Among the 150 messages that accumulated while I was at the POPL 
conference, I notice that the topic of native-code exception 
backtraces is making its come-back: 
> Well, seeing that the very useful native exception backtrace patch has 
> been 
> sitting idle (acknowledged) for more than a year, I think that's not 
> working it out too well :\ 

Like elephants, I'm slow, but never forget :-)  You'll be pleased to 
learn that I've been working recently on exception backtraces for 
ocamlopt.  The code (nearly finished) currently sits in the 
"opt_backtrace" branch of the repository and should be part of 
release 3.10. 
It implements an exception backtrace mechanism similar to that already 
available in bytecode, but different from Markus Mottl's call backtrace. 
The two kinds of backtraces are incomparable in general, but while 
Markus's solution is quite low overhead already, mine has even lower 
overhead, especially in terms of code size. 

Native-code backtraces will be available initially for the following 
back-ends: i386, amd64 and powerpc, both for Unix-like OS and for 
Windows.  Ports to other back-ends will be considered if there is 
sufficient demand.

color on linux terminal


Continuing the thread from last week, Xavier Leroy said:
> This is my biggest "pet peeve" about OCaml.  It uses *decimal* escapes 
> for characters, 

Hexadecimal is also supported ("\x1b[31m blabla") and highly recommended. 
> not octal like everywhere else in the UNIX and C-influenced universe. 

Well, how many fingers do you have? :-)  Octal is a left-over from the 
PDP-11 days and should have been abandoned a long time ago.

va_arg values


Continuing the thread from last week, Xavier Leroy said:
> value func(value obj, char *method, int n, ...) 
> { 
>   va_list ap; 
>   int i; 
>   value *args = calloc(n + 1, sizeof(value)); 
>   value r; 
>   args[0] = obj; 
>   va_start(ap, n); 
>   for (i = 0; i < n; i++) 
>     args[i + 1] = va_arg(ap, value); 
>   va_end(ap); 

>   r = caml_callbackN(caml_get_public_method(obj, hash_variant(method)), 
>                      n + 1, args); 
>   free(args); 
>   return r; 
> } 

> Is it an invalid assumption that it is unnecessary to bother with the 
> CAMLparam/CAMLlocal stuff since there's nothing to trip the GC? 

It's a valid assumption.  The hard rule is that you must register as 
root all local variables that need to survive a call to the GC or to a 
function that might trigger the GC.  In general it's hard to keep 
track of those variables, which is why the OCaml manual advocates 
registering everything that has type "value".  But in your case you 
cannot, and the code fragment above look safe to me.  (Make sure you 
document this in a big comment, though...)  As others pointed out, 
you're also relying on the fact that caml_get_public_method 
and hash_variant never trigger a GC, which is true now and in the 
foreseeable future, but again a big comment is warranted. 
> Should probably check calloc for success and maybe throw an exception 
> if it failed... Which actually brings me to another quick question: if 
> I throw an exception, say caml_failwith("..."), is it necessary to 
> still call CAMLreturn after it? Or will the exception cause the 
> function to exit? 

The latter: the exception triggers something like a longjmp(), causing 
immediate return from the C function (and de-registration of the local 
roots, if any). 
> One last quick question: is the line "args[i + 1] = va_arg(ap, value);" 
> above legal? args[] is an array of value and va_arg(ap, value) will 
> return a value. So, essentially, it's the same thing as the assignment 
> in the following example: 
> value func(value v1) 
> { 
>   value v2 = v1; 
>   ... 
> } 

> I know values are just pointers so it is syntactically correct, but 
> what I'm asking is: is it safe to do? Should I be using some function 
> instead to create a copy of the value? 

No copying is necessary.

function definition


Vu Ngoc San asked and Jon Harrop answered:
> I'm sure this is a basic question: 
> what is the difference between these ways of defining a function, and 
> what is the most efficient (I mean for the resulting function f = binop 
> o f1 f2, which typically will be called x*1000 times) 

That's a very hard question, and is probably platform specific but I'll throw 
some ideas at you off the top of my head. I'm sure someone like Brian Hurt 
will dive into the assembler and prove me wrong. ;-) 
> type operator = Plus | Minus;; 
> let binop1 o f1 f2 = 
>    fun x -> match o with 
>    | Plus -> (f1 x) +. (f2 x) 
>    | Minus -> (f1 x) -. (f2 x) 

That is equivalent to: 
  let binop1 o f1 f2 x = .. 

it waits for all arguments before doing anything. ocamlopt optimises currying 
for that case. 

> let binop2 o f1 f2 = 
>    match o with 
>    | Plus -> fun x -> (f1 x) +. (f2 x) 
>    | Minus -> fun x -> (f1 x) -. (f2 x) 

After 3 args, this returns a closure waiting for the fourth arg. 
> let binop3 o f1 f2 = 
>    let op = match o with 
>    | Plus ->  (+.) 
>    | Minus -> (-.) in 
>    fun x -> op (f1 x) (f2 x) 

After 3 args, this creates a closure to do the op and another closure that 
captures the first closure. ocamlopt might inline the closure "op" but I 
doubt it. 
> let binop4 o f1 f2 = 
>    fun x -> 
>      let op = match o with 
>    | Plus ->  (+.) 
>    | Minus -> (-.) in 
>      op (f1 x) (f2 x) 

This waits for all four args again (same as first case) and the closure "op" 
might be inlined. 
Assuming you invoke the function will all four arguments, I would expect the 
first solution to be the fastest by a significant margin. If you factor out a 
closure of binop with its first three arguments passed and use it multiple 
times then the second solution might be faster. 

I've found this with a pattern matcher written in OCaml that was faster when 
the pattern matcher evaluated when partially applied to the pattern, 
returning a closure that matched against the pattern it had been partially 
applied to. I was surprised to find that. I still don't know why that would 
be faster...

Using folding to read the cwn in vim 6+

Here is a quick trick to help you read this CWN if you are viewing it using vim (version 6 or greater).

:set foldmethod=expr
:set foldexpr=getline(v:lnum)=~'^=\\{78}$'?'&lt;1':1

If you know of a better way, please let me know.

Old cwn

If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.

If you also wish to receive it every week by mail, you may subscribe online.

Alan Schmitt