Lambda the Ultimate

I am looking for references to the above, especially for implementations in ML-like languages.

Rationale, I needed to write a comparison function for the content of binary trees. Using a coalgebraic structure to decompose the two trees in steps was the only solution I could think of. I am looking for possible generalizations of what I used.

It looks like CPS, but it would be interesting to see it explained better.

Greetings all. I just wanted to tell people that Jane Street is (still) interested in hiring functional programmers (of which many are of course denizens of LtU). Despite the problems besetting much of the financial industry, we have grown strongly in the last few years in our people, our technology, the scope of our business and its profitability. We now have over 30 OCaml developers, and we are actively looking to hire more in Tokyo, London and New York.

For someone who cares about functional programming, Jane Street is an interesting place to consider. Jane Street has invested deeply in OCaml, to the point where we now have the largest team of OCaml programmers in any industrial setting, and probably the world's largest OCaml codebase--almost a million lines. We really believe in functional programming, and use OCaml for everything from research to systems adminstration to trading systems.

The atmosphere is informal and intellectual, with a focus on learning. The work itself is deeply challenging, and you get to see the practical impact of your efforts in quick and dramatic terms. Jane Street is also a small enough place that people have the freedom to get involved in many different areas of the business.

Unlike many financial firms, software and technology are considered a core part of what we do, not some segmented-off cost center that the people who run the business don't think about. Jane Street is a place where people really care about the quality of the software, to the point that several of the most senior members of the firm, who do not have technology backgrounds, nonetheless review critical portions of the codebase before they can go into production.

If you'd like to learn more, here are some links. First, here's a paper I wrote for the Monad Reader:

http://www.haskell.org/sitewiki/images/0/03/TMR-Issue7.pdf

We also have a technically-oriented blog:

http://ocaml.janestreet.com

For a (recruiting-oriented) overview of Jane Street, here's the firm website:

http://janestreet.com

If you're interested, send a resume and cover letter to yminsky@janestreet.com

ompilers transform programs, either to optimize performance or to translate language-level constructs into hardware primitives. For concurrent programs, ensuring that a transformation preserves the semantics of the input program can be challenging. In particular, the emitted code must correctly emulate the semantics of the language-level memory model when running on hardware with a relaxed memory model. In this paper, we present a novel proof methodology for proving the soundness of compiler transformations for concurrent programs. Our methodology is based on a new formalization of memory models as dynamic rewrite rules on event streams. We implement our proof methodology in a first-of-its-kind semi-automated tool called Traver to verify or falsify compiler transformations. Using Traver, we prove or refute the soundness of several commonly used compiler transformations for various memory models. In this process, we find subtle bugs in the CLR JIT compiler and in the JSR-133 Java JIT compiler recommendations.

The goal is to reason about the effects that different memory models may have on the validity of transformations. Program execution is modeled as an event stream, with the memory model being able to alter the event stream by swapping or eliminating events. Each concurrent execution thread produces a separate event stream. The event stream produced by the execution of the concurrent program is the (possibly altered) result of merging the event streams of each component. The validity of transformation can thus be proved relative to a specific memory model (i.e., a set of stream rewrite rules).

Traver lives here.