Hello
Here is the latest Caml Weekly News, for the week of January 16 to 23, 2007.
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).
http://people.csail.mit.edu/mikelin/ocaml+twt
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...
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
include
* 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;
profiling
* Practice and experience: novel results drawn from experience in
education or industry
* Functional pearls: elegant, instructive examples of functional
programming
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
http://www.timeanddate.com/worldclock/fixedtime.html?month=4&day=6&year=2007&hour=11&min=0&sec=0&p1=282
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 http://www.acm.org/sigplan/republicationpolicy.htm .
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
http://icfp07.eecs.harvard.edu/blind.html .
Formatting
~~~~~~~~~~
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 http://www.acm.org/sigs/sigplan/authorInformation.htm . 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.
Citation
~~~~~~~~
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
techniques.
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
references.
* 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
education
* 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
productive.
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
Email: icf...@eecs.harvard.edu
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
~~~~~~~~~~~~~~~~~~
http://www.informatik.uni-bonn.de/~ralf/icfp07.html
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.
> 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]
than
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 *)
Regards,
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
end
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
end
module type AddT = sig
include AddTE
val eval : (int, exp) t Lazy.t
end
module AddF(X : AddT with type ('a,'exp) t = private ('a,'exp) #visit_add) =
struct
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
end
let eval = lazy (new eval)
end
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
end
module type AddNegT = sig
include AddT
val neg : exp -> exp
end
module AddNegF(X : AddNegT with
type ('a,'exp) t = private ('a,'exp) #visit_add_neg) =
struct
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
end
let eval = lazy (new eval)
end
module rec AddNeg : AddNegT with type ('a,'exp) t = ('a,'exp) visit_add_neg =
AddNegF(AddNeg)
open AddNeg
let n = (add (neg (add (num 3) (num 2))) (num 7))#accept (Lazy.force eval)
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: http://syn.cs.pdx.edu/~jsnow/glome/ 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, > > http://www.openrt.de/Gallery/OliverDeussen_Sunflowers/Images/sunflowers_2.jpg) > 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 > > ompf.org: http://ompf.org/forum/viewtopic.php?t=336 > 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: http://graphics.ucsd.edu/~henrik/images/gbox.jpg :) 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.
CALL FOR PAPERS Trends in Functional Programming 2007 New York, USA April 2-4, 2007 http://cs.shu.edu/tfp2007/ NEW: Abstract submission is now opened! Link: http://cs.shu.edu/tfp2007/submissions.html 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 campus. SCOPE OF THE SYMPOSIUM 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 work 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 project Overview Articles summarizing work with respect to a trendy subject 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 tfp2007@shu.ed. SUBMISSION AND DRAFT PROCEEDINGS 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. POST-SYMPOSIUM REFEREEING AND PUBLICATION 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. IMPORTANT DATES 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 PROGRAMME COMMITTEE John Clements California Polytechnic State University, USA Marko van Eekelen Radboud Universiteit Nijmegen, The Netherlands 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, Germany 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 ORGANIZATION 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 http://cs.shu.edu/tfp2007/
I am releasing a syntax extension which translates quasi-OCaml type definitions into converters from/to generic JSON data: http://martin.jambon.free.fr/json-static.html (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 signature: 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 library. 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: http://martin.jambon.free.fr/yahoo.ml.html
> 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. [1] http://www.lri.fr/~signoles/prog.en.htmlskaller 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; elapsed ;; 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 ;; try (* 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
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.
> 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.
> 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.
> 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...
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}$'?'<1':1
zM
If you know of a better way, please let me know.
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.