Hello

Here is the latest Caml Weekly News, for the week of January 04 to 11, 2011.

1. patch to update SWIG to work with OCaml 3.12 and camlp4
2. Ocaml-based web intro to functional programming
3. Native OCaml iPhone app now in iTunes Store
4. Lwt Patch For Tuareg 2.0.2
5. New release of core.
6. Mark-region GC
7. Identity crisis
8. Other Caml News

Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00040.html

https://gist.github.com/766233

Examples/std_string does not work as I had to remove access to std::string 
and std::wstring. These are converted to OCaml strings.
      

And on SourceForge

https://sourceforge.net/tracker/?func=detail&atid=301645&aid=3151788&group_id=1645
			

Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00059.html

Chris Barker (NYU Linguistics) and I (Jim Pryor, NYU Philosophy) just
finished teaching a grad seminar on "What Philosophers and Linguists Can
Learn From Theoretical Computer Science But Didn't Know To Ask". It was
basically an intro to functional programming oriented to our fields,
most of whose audience had done no programming before, but had some
background in formal semantics or philosophical logic.

They weren't there to learn programming, but to learn how reasoning
about types, effects, monads, continuations, and so on would be useful
to philosophers and linguists. We had to teach them how to program along
the way, so that they could understand what all those things were.

We moved back and forth between untyped lambda calculus, Scheme, a bit
of System F, OCaml, and a bit of Haskell. But when working in typed
languages, we primarily used OCaml.

We were very happy with how the seminar worked out, and it was a lot of
fun. Along the way, we developed a pretty substantial website, housed at
http://lambda.jimpryor.net/. We hope to continue developing and
refining this.

Some highlights of the website: a pretty good Javascript lambda reducer,
a hefty library of arithmetic and list operations in untyped lambda
calculus, a monad + monad transformer library in OCaml, a walk-through
of how to implement a classic paper from the dynamic semantics
literature using monads, an explanation of monads in category theory and
how that correlates with their use in functional programming, a bunch of
exposition and exercises, and lots of links.

At several places we had very useful input from Chung-chieh Shan,
Oleg Kiselyov, and Wren Thornton. (Some of their generous and useful
feedback has yet to be folded in.)

I'm posting this pointer to the website for two reasons: first of all,
we'd be very glad for feedback from others in the broader functional
programming community. (Our website is generated by ikiwiki, but it's
not in fact a wiki. However, we'd be glad to incorporate contributions.)

Second, and primarily, we hope the material there might be useful to
others learning these fundamentals. If you agree, you may want to point
them to it.
      

Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00023.html

I'm happy to say that our iPhone app written in OCaml is now available
in the iTunes store.  It plays the classic card game Cassino, which is
actually quite fun.  But it also shows that you can use OCaml to build
native iOS apps.

You can check out the app here:

    http://itunes.apple.com/us/app/cassino/id411381417?mt=8&uo=4

I posted about our OCaml-to-iOS cross compiler a while back on this
list.  It's based on OCaml 3.10.2 and uses patches from Toshiyuki Maeda
and us (Psellos).  Since I last posted about it, I've fixed at least one
bug, so if you're interested you might want to try the newest version.
I created a web page that describes how to build it, here:

    http://psellos.com/ocaml/compile-to-iphone.html

It's really enjoyable to work with the power and flexibility of OCaml on
the iPhone.  OCaml offers excellent leverage for building iPhone apps,
once the lower layers are in place.

I'd be very happy to answer questions about our experiences and methods,
either on- or off-list.
      

> Are you bundling OCaml code as a library and putting a GUI layer of
> ObjC on top?

All the code is in OCaml; there's no ObjC except in the (thin)
wrappers around the native iOS libraries.  We wanted to write as
much in OCaml as possible.

As we say on the website, the OO subsystem of OCaml is very helpful
for this.  We have essentially a one-to-one correspondence between
native iOS (Cocoa Touch) classes and OCaml classes.

Even though we follow the Cocoa Touch design, we find that OCaml still
has advantages in the GUI implementation.  It's nice not to have to
worry so much about object lifetimes, for example.  We use idiomatic
OCaml values for the low-level objects (like points and rectangles)
and for small collections (where ObjC often uses rather cumbersome
class instances).  Often you can use the powerful parts of OCaml on
the components of your GUI.
			

> How did you wrap the native libraries then?

We went through a few iterations of plans for generating wrappers
automatically.  But we determined that automatically generated
wrappers that follow Objective C idioms are too cumbersome to use from
OCaml.  An automatic tool is going to require a lot of human input on
data structure choices, at the very least.

What we did in the end was to design a basic framework with an OCaml
class for each ObjC class.  The method APIs use idiomatic OCaml types
for values and collections.  The support code uses Cocoa foundation
classes to do dynamic method invocation, so the amount of ObjC code in
each wrapper is kept to a minimum (typically there is none).  The
framework lets us build individual wrappers quickly and keeps things
coherent and consistent.  We code up wrappers by hand as we need them.

> I've been meaning to write a Cocoa bridge for OCaml but haven't
> gotten to it yet.

It would be a big project.

> Are your wrappers available?

We'll be happy to release source to our Cocoa wrapper layer once we
recoup some of our investment in it.  In the meantime we can offer
advice on things that worked and didn't work for us.
			

Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00082.html

Hey everyone, I patched Tuareg-mode 2.0.2 to support Lwt. Sorry it's 2.0.2,
when I did this, I didn't realize I was using an older version of Tuareg-mode,
hopefully updating for the latest is easy enough. I think I have done most of
the boring work of patching, so hopefully someone more knowledgeable than I
can fix any obvious errors I made. I'll continue to try to keep the mode
updated though.

The patch can be found at:

https://forge.ocamlcore.org/tracker/index.php?func=detail&aid=845&group_id=43&atid=257

The *lwt-1.patch file is the latest version.

Disclaimer:
- This is my first foray into the world of emacs-lisp, I was mostly
  semi-blindly merging changes from the 1.46 patch into this, that means I may
  have done nonsensical things. There are undoubtedly bugs.

- I do not guarantee this works completely. I have fixed the bugs as I come
  across them, but so far I have only used the 'lwt' syntax extension so I
  cannot guarantee it works for the rest.
      

Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00089.html

We are pleased to announce the third major release of Jane street's core
library and support libraries (type-conv, sexplib,bin-prot and fieldslib). Due
to our development process we are not able to provide a detailed changelog
because this is very active codebase and there have been a lot of improvements
and added features.

The changes include:
-> Everything is now packaged with oasis
-> Type-conv does not require the user to set type_conv_path anymore (it can
use the filename).
-> Core has a new highly optimized version of Hashtables which is about as
space and time efficient as (ocaml's) Hashtbl but degrades gracefully in the
presence of hash collisions.
-> A lot of the functions in the List modules have been optimized (map,@...).
They are now about as fast as the ones in the standard library but are also
tail recursive.

But wait there's more to come!

This is a beta release;
We are hoping to carve out a release soon that will work on ocaml 3.12;
include support for generating the ocamldocs automatically and bundle
core_extended.

All the packages are available on:
;http://www.janestreet.com/ocaml

We would love to hear your feedback and bug reports at:
opensource AT janestcapital.com
 
<mailto:opensource AT janestcapital.com>

All of the released libraries are licensed under the
LGPL-plus-linking-exception.

I would also like to thank Sylvain le Gall, Markus Mottl, Nicolas Pouillard
and Xavier Clerc for their help.
      

Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00102.html

Thought you guys might appreciate my recent foray into GC design:

http://flyingfrogblog.blogspot.com/2011/01/importance-of-locality-and-sparsity-in.html
  http://flyingfrogblog.blogspot.com/2011/01/sweeping-700-faster.html

In summary, I think I have found a way to make a simple GC for HLVM that is
almost as fast as OCaml's on serial functional code, significantly faster on
imperative code and can easily support both parallelism among mutators and
even parallel+concurrent collection.

Specifically, I noted that the advantage of OCaml's generational GC is
largely its ability to sweep large numbers of dead infants from the nursery
in constant time but the disadvantage is the overhead of evacuating
survivors. I was able to mimic the advantage without the disadvantage by
allocating regions and storing bitvectors representing the blocks within the
region that are allocated and marked. Hundreds of heap allocated blocks in a
region can then be swept simply by reading those two bitvectors, computing
the bitwise AND and writing the result as an updated allocated bitvector
(with everything unmarked zeroed out). Moreover, 512-bit bitvectors fill a
cache line and offer near-optimal granularity for the rest of the system.
Thus, the new collector is sweeping at a rate of 40Gb of heap blocks per
second (!), not only for the "nusery" (thread-local region) but potentially
also for the entire "major heap" (global queues of full and non-full
regions).

I was also able to mimic the advantage of Appel's semi-generational
collector with the added benefit of reducing synchronization by sweeping the
thread-local region when it fills. Many local sweeps are typically performed
before the local region fills so contention for obtaining new regions from
the global queue is greatly reduced.

However, my design does degrade the performance of allocation. Rather than
using a bump allocator, I search for the next non-255 byte in the allocated
bitvector and then use a 255-element lookup table to find the next zero bit,
set it, calculate and return the corresponding pointer into the region. I
haven't profiled the overhead of this allocator but my C++ prototype gets
within 10% of OCaml's performance on the list-based n-queens solver. I am
*extremely* happy with that result! :-)
      

Archive: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00109.html

As is well known, ocaml as no true equality comparison: (=) conflates
observably distinct values (mutable records that happen to have the
same contents at the time of comparison), whereas (==) introduces
distinctions that would otherwise been unobservable (between immutable
records that have the same contents but happen to have different
addresses). Also, (=) fails with an exception if it encounters
something it doesn't like (abstract values).

Moreover, since addresses are not stable (objects can be moved during
GC), there is no way efficient way to use record identities as keys in
trees or hash tables.

What all this means is that if the programmer wants to have an
efficiently implemented set of stateful mutable records, she has to
make sure that each record contains a unique id, and she has to
provide a custom hash or compare operation that uses this id, and she
also has to write wrappers if these stateful things are ever elements
of some other structures that need comparison or hashing. This is
superbly tedious.

Strangely enough, there is a class of stateful values that Does The
Right Thing straight out of the box: objects. You can use the standard
equality, hashing and comparison operations with objects, and they all
use a stable identity that isn't affected by GC.

Hence, if you want references in your data structures to be compared
by identity (and I can't see a reason why you would ever want
otherwise), you could use this as an alternative implementation of refs:

class ['a] ref (x : 'a) = object
    val mutable contents = x
    method get = contents
    method set x = contents <- x
end

let ref = new ref
let (!) r = r#get
let (:=) r = r#set

However, it seems really strange that one has to use objects (which
are usually considered a wholly optional component of the language) in
order to get correct semantics for stateful identities.

I don't really have any good suggestions. It would be nice if records
with mutable fields were compared like objects (and had stable ids
internally). But with e.g. strings there is no solution in sight since
the very same type is used both for string values and mutable string
buffers, so every comparison would be wrong in some context. Perhaps
we must simply accept that ocaml is irredeemably broken in this
regard.

And perhaps I will begin to use objects more from now on. I don't like
their complexity, but at least objects know who they are.
      

I've written a blog entry related to these questions a few days ago:

http://www.lexifi.com/blog/references-physical-equality

In particular, I show an ugly hack to tell OCaml to use physical equality for
records (you have to manage explicitly the unique id).
			

Thanks to Alp Mestan, we now include in the Caml Weekly News the links to the
recent posts from the ocamlcore planet blog at http://planet.ocamlcore.org/.

A jolt, or a shock?:
  http://alaska-kamtchatka.blogspot.com/2011/01/jolt-or-shock.html

Mascot: 1.0-alpha:
  https://forge.ocamlcore.org/forum/forum.php?forum_id=764

Argot: 1.0-alpha:
  https://forge.ocamlcore.org/forum/forum.php?forum_id=763

OCaml DB-Library:
  https://forge.ocamlcore.org/projects/odblib/

OCaml judy bindings:
  https://forge.ocamlcore.org/projects/ocamljudy/

European workshop on computational effects:
  http://math.andrej.com/2011/01/04/european-workshop-on-computational-effects/
      

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