Previous week   Up   Next week

Here is the latest Caml Weekly News, weeks 30 april to 7 may, 2002. 

1) Danvy "Functional Unparsing" style output in OCaml
2) "high end" type theory for working programmers?
3) input_line is blocking

1) Danvy "Functional Unparsing" style output in OCaml
T. Kurt Bond answered Francois Pottier and announced:

> Check out Olivier Danvy's paper `Functional Unparsing':
> It describes a very nice way of programming `printf' within ML's type
> system. `scanf' could be handled in a similar way. Furthermore, this approach
> yields code that is claimed to be more efficient than O'Caml's current
> `printf' implementation (because the overhead of interpreting format strings
> is lower). Lastly, it scales up to more expressive format directives, such as
> a directive for printing a list.
> It might be worth adding a module that implements Danvy-style `printf' and
> `scanf' to the standard library. Has anyone written such a module already?
> Otherwise, I might consider doing it.

Back during an earlier discussion of Danvy-style output (probably on
this) I implemented a simple module for this (possibly starting from
some code that flew by on the list).

This round of discussion prompted me to go back and finish it up and
knock of a few of the rough edges and package it up.  Here's the README:

Cpsio is an Objective Caml implementation of the
continuation-passing-style output from Olivier Danvy's paper
Functional Unparsing.  It is available from:

The distribution is a gzipped tar file. It includes two modules:

   + Cpsio, which has a format function comparable to sprintf; and

   + Cpsio_exp, which has format_string, format_out, and
     format_err functions comparable to sprintf, printf, and
     eprintf, and a format function that allows the user to
     specify an accumulator/output function and an initial value
     (the later function is used to build the three previous
     functions and is available to clients for use with
     client-defined accumualtor/output functions).

Both modules have (rough) Ocamldoc documentation. The distribution
also includes test/example/benchmark programs for both Cpsio and Cpsio_exp,
and benchmark programs for comparing against OCaml and C
printf-style output. Perfomance with the bytecode compiler mostly
seems slightly faster than the OCaml printf, while performance with
the native code compiler seems to range from slower than the OCaml
printf to barely faster than the OCaml printf.

   + Despite the "io" in the name, it unfortunately does not
     include input at this time, just output.
   + The Makefile is weak and does not have an install target.

I do not claim that this code is most elegant or most efficent
implementation of this idea.

I would welcome comments on the code.

This software is in the public domain.

2) "high end" type theory for working programmers?
Chris Hecker asked:

The list has had a lot of discussions about type theory behind the module
system, tuples, and the like lately.  Most of it has been over my head, 
which is fun, because it presents a challenge to try to figure out what
people are saying.  I am wondering how much of it is useful for actually
writing "regular" code (as opposed to compilers or theorem provers).  Are
there books (or survey papers) on this stuff that are meant to educate
working programmers, as opposed to language researchers?  For example,
where should I go to learn what this means, and whether I care (just a
randomly chosen sentence representative of stuff that's currently over my
head from the past few days on the list):

"That functor is essentially the polymorphic identity functor, while the
other variation was a polymorphic eta-expansion of the abstraction operator."

or another example:

"In this encoding, modules are only records, so module types are ordinary
types, and there is no distinction between ordinary abstract types
(introduced by explicit polymorphic abstraction) and ``abstract
signatures''. There is, as far as I can tell, no need for kind polymorphism."

I started using caml to find out if a "higher level" language could make a
difference in my programming productivity (writing video games).  As I
continue with that experiment, I'm curious to know whether understanding
this high end type theory stuff would help make me a better programmer, or
just more able to understand the list lately.  Either is fine, but both
would obviously be great.  :)

Michael Vanier replied:

I highly recommend Benjamin Pierce's new book "Types in Programming
Languages" from MIT press.  It's very well-written, covers much of the  
material you describe, and includes implementations in ocaml ;-)

Neel Krishnaswami added:

Let me second this recommendation. It's a great book. I'm a regular
programmer and I found it extremely useful.

I think that Olivier Danvy's "Functional Unparsing" paper is one
of the best illustrations of why this stuff is useful for regular
programming. There's nothing more practical in the world than
printing text, and here he uses continuation-passing style, combinators,
higher-order functions, and all that stuff to derive a blisteringly   
fast statically-typed printf. It's amazing. (And you can make the 
library nearly perfect to use if you use labels and optional arguments.)

This technique is apparently an instance of a more general technique
that Zhe Yang describes in his paper "Encoding Types in ML-like
Languages", at <>.

And Will Benton said:

Some great references (that explain these issues fairly clearly) are:

The first one (a massive survey that came from a CRC handbook) covers
what is meant by "well-typed" and contains the rules for proving that a
language/construct is well-typed.  The second covers type inference in
the face of polymorphism and other "fun" language features.  The third
covers lambda-calculus, the formal model for all functional (and
otherwise) languages (it also covers pi-calculus, which is a model for
communicating processes).  As a general rule, if you see the greek
letters alpha, beta, or eta in a PL-theory context, you can assume that
it's because someone is talking about the lambda calculus.  :-)

In any case, I think if you read those, you'll be able to follow some of 
the more "esoteric" discussions.

If you are really interested in learning about this stuff (types,
l-calculus, and PL theory in general), a great book is _Essentials of
Programming Languages_ by Friedman, Wand, and Haynes.  I have the first
edition, which is supposedly better for self-study (it was my undergrad
PL textbook), but the second edition is supposedly a better textbook
from what I've heard.  I have not seen the 2e, but I know that it has
some newer/improved algorithms for some program transformations.

This stuff *will* make you a better programmer -- you have probably
already observed that the strong typing in OCaml makes it easier to
write working code, and learning about how and why it works is helpful
for a lot of peoples' thought/design processes.  However, other PL
theory topics (ones that might seem esoteric, or only useful for
interpreter/compiler writers) will even make you write better code, as
the following anecdotes indicate:

The last one in particular is a gem.

3) input_line is blocking
Gerd Stolpmann answered Warp and announced:

> Hi
> I'm running "ocamlc" by using Unix.open_process_full in order to write an
> automatic compiler.
> Right now, it's working fine, but I got now a problem with input_line :
> after running open_process_full , i'm first reading all its stdout lines of
> the process until End_of_file is raised, then all its stderr lines using the
> same function.
> It has work fine for few weeks now, but now I found that in some cases
> input_line will block, not raising End_of_file.

I wrote a library exactly for such advanced usage of sub processes:  

For example, to call ocamlc one would do:

open Shell
let stdout = Buffer.create 16 in
let stderr = Buffer.create 16 in
call ~stdout:(to_buffer stdout) ~stderr:(to_buffer stderr) [ cmd "ocamlc" args ]

The Shell library includes the necessary logic to read from multiple
file descriptors (using

One drawback: Shell works only for Unix (because of Unix.fork). I think
that you have to use multi-threading for a platform-independent


Alan Schmitt