OCaml Planet

August 31, 2014

Shayne Fletcher

Terms With Variables (C++)

Terms with Variables (C++)

In this earlier post I showed a nifty OCaml type for modeling terms with variables for problems involving substitutions. I got interested in what it would take to implement the type in C++(03) (doing 'sum' types in C++ elegantly is a perennial problem). It ain't nowhere near as succinct but we got there nonetheless.

#include <list>

#include <boost/variant.hpp>

/*
type ('a, 'b) term =
| Term of 'a * ('a, 'b) term list
| Var of 'b
*/

template <class A, class B> struct term;
template <class B> struct var;

template <class A, class B>
struct make_tree
{
typedef boost::variant <
boost::recursive_wrapper<term <A, B> >,
boost::recursive_wrapper<var<B> > > type;
};

template <class A, class B>
struct term
{
typedef typename make_tree <A, B>::type tree;
A a;
std::list <tree> children;
term (A a
, std::list<tree> const& children)
: a (a), children (children)
{}
};

template <class A, class B>
inline term <A, B> make_term (
A a, std::list<typename make_tree<A, B>::type> const& c, B const*)
{
return term<A, B> (a, c);
}

template <class B>
struct var
{
B tag;
var (B tag) : tag (tag) {}
};

template <class B>
inline var<B> make_var (B tag) { return var<B> (tag); }
For example, this little program builds the term represented by the concrete syntax "a(b(), c)".

int main ()
{
typedef make_tree<std::string, std::string>::type tree;
typedef std::list<tree> term_list;
std::string const* tag_str=(std::string const*)0L;

// a(b(), c)
term_list l;
l.push_back (make_term(std::string("b"), term_list (), tag_str));
l.push_back (make_var(std::string("c")));
tree t = make_term(std::string("a"), l, tag_str);

return 0;
}

by Shayne Fletcher (noreply@blogger.com) at August 31, 2014 05:06 PM

August 30, 2014

Anil Madhavapeddy

Talks from OCaml Labs during ICFP 2014

It’s the ever-exciting week of the International Conference on Functional Programming again in Sweden, and this time OCaml Labs has a variety of talks, tutorials and keynotes to deliver throughout the week. This post summarises all them so you can navigate your way to the right session. Remember that once you register for a particular day at ICFP, you can move between workshops and tutorials as you please.

Quick links to the below in date order:

Language and Compiler Improvements

The first round of talks are about improvements to the core OCaml language and runtime.

» Modular implicits

Leo White and Frederic Bour have been taking inspiration from Scala implicits and Modular Type Classes by Dreyer et al, and will describe the design and implementation of a system for ad-hoc polymorphism in OCaml based on passing implicit module parameters to functions based on their module type.

This provides a concise way to write functions to print or manipulate values generically, while maintaining the ML spirit of explicit modularity. You can actually get get a taste of this new feature ahead of the talk, thanks to a new facility in OCaml: we can compile any OPAM switch directly into an interactive JavaScript notebook thanks to iocamljs by Andy Ray.

» Multicore OCaml

Currently, threading in OCaml is only supported by means of a global lock, allowing at most one thread to run OCaml code at any time. Stephen Dolan, Leo White and Anil Madhavapeddy have been building on the early design of a multicore OCaml runtime that they started in January, and now have a (early) prototype of a runtime design that is capable of shared memory parallelism.

  • Abstract
  • Date: 09:10-10:00, OCaml Workshop, Fri Sept 5th

» Type-level Module Aliases

Leo White has been working with Jacques Garrigue on adding support for module aliases into OCaml. This significantly improves the compilation speed and executable binary sizes when using large libraries such as Core/Async.

» Coeffects: A Calculus of Context-dependent Computation

Alan Mycroft has been working with Tomas Petricek and Dominic Orchard on defining a broader notion of context than just variables in scope. Tomas will be presenting a research paper on developing a generalized coeffect system with annotations indexed by a correct shape.

  • Paper
  • Date: 16:30-17:20, ICFP Day 1, Mon Sep 1st.

 Mirage OS 2.0

We released Mirage OS 2.0 in July, and there will be several talks diving into some of the new features you may have read on the blog.

» Unikernels Keynote at Haskell Symposium

Since MirageOS is a unikernel written entirely in OCaml, it makes perfect sense to describe it in detail to our friends over at the Haskell Symposium and reflect on some of the design implications between Haskell type-classes and OCaml functors and metaprogramming. Anil Madhavapeddy will be doing just that in a Friday morning keynote at the Haskell Symposium.

  • Haskell Symposium Program
  • Date: 0900-1000, Haskell Symposium, Fri Sep 5th.

» Transport Layer Security in OCaml

Hannes Menhert and David Kaloper have been working hard on integrating a pure OCaml Transport Layer Security stack into Mirage OS. They’ll talk about the design principles underlying the library, and reflect on the next steps to build a TLS stack that we can rely on not to been more insecure than telnet.

  • Abstract
  • Date: 10:25-11:20, OCaml Workshop, Fri Sep 5th.

Hannes will also continue his travels and deliver a couple of talks the week after ICFP on the same topic in Denmark, so you can still see it if you happen to miss this week’s presentation:

  • 9th Sep at 15:00, IT University of Copenhagen (2A08), details
  • 11th Sep Aarhus University, same talk (time and room TBA)

» Irmin: a Branch-consistent Distributed Library Database

Irmin is an OCaml library to persist and synchronize distributed data structures both on-disk and in-memory. It enables a style of programming very similar to the Git workflow, where distributed nodes fork, fetch, merge and push data between each other. The general idea is that you want every active node to get a local (partial) copy of a global database and always be very explicit about how and when data is shared and migrated.

This has been a big collaborative effort lead by Thomas Gazagnaire, and includes contributions from Amir Chaudhry, Anil Madhavapeddy, Richard Mortier, David Scott, David Sheets, Gregory Tsipenyuk, Jon Crowcroft. We’ll be demonstrating Irmin in action, so please come along if you’ve got any interesting applications you would like to talk to us about.

  • Abstract
  • Blog Post
  • Date: 15:10-16:30, Joint Poster Session for OCaml/ML Workshop, Fri Sep 5th 2014.

» Metaprogramming with ML modules in the MirageOS

Mirage OS lets the programmer build modular operating system components using a combination of OCaml functors and generative metaprogramming. This ensures portability across both Unix binaries and Xen unikernels, while preserving a usable developer workflow.

The core Mirage OS team of Anil Madhavapeddy, Thomas Gazagnaire, David Scott and Richard Mortier will be talking about the details of the functor combinators that make all this possible, and doing a live demonstration of it running on a tiny ARM board!

  • Abstract
  • Date: 14:50-15:10, ML Workshop, Thu Sep 4th 2014.

» CUFP OCaml Language Tutorial

Leo White and Jeremy Yallop (with much helpful assistance from Daniel Buenzli) will be giving a rather different OCaml tutorial from the usual fare: they are taking you on a journey of building a variant of the popular 2048 game in pure OCaml, and compiling it to JavaScript using the js_of_ocaml compiler. This is a very pragmatic introduction to using statically typed functional programming combined with efficient compilation to JavaScript.

In this tutorial, we will first introduce the basics of OCaml using an interactive environment running in a web browser, as well as a local install of OCaml using the OPAM package manager. We will also explore how to compile OCaml to JavaScript using the js_of_ocaml tool.

The tutorial is focused around writing the 2048 logic, which will then be compiled with js_of_ocaml and linked together with a frontend based on (a pre-release version of) Useri, React, Gg and Vg, thanks to Daniel Buenzli. There’ll also be appearances from OPAM, IOCaml, Qcheck and OUnit.

There will also be a limited supply of special edition OCaml-branded USB sticks for the first tutorial attendees, so get here early for your exclusive swag!

» The OCaml Platform

The group here has been working hard all summer to pull together an integrated demonstration of the new generation of OCaml tools being built around the increasingly popular OPAM package manager. Anil Madhavapeddy will demonstrate all of these pieces in the OCaml Workshop, with guest appearances of work from Amir Chaudhry, Daniel Buenzli, Jeremie Diminio, Thomas Gazagnaire, Louis Gesbert, Thomas Leonard, David Sheets, Mark Shinwell, Christophe Troestler, Leo White and Jeremy Yallop.

The OCaml Platform combines the OCaml compiler toolchain with a coherent set of tools for build, documentation, testing and IDE integration. The project is a collaborative effort across the OCaml community, tied together by the OCaml Labs group in Cambridge and with other major contributors.

» The 0install Binary Installation System

Thomas Leonard will also be delivering a separate talk about cross-platform binary installation via his 0install library, which works on a variety of platforms ranging from Windows, Linux and MacOS X. He recently rewrote it in OCaml from Python, and will be sharing his experiences on how this went as a new OCaml user, as well as deliver an introduction to 0install.

  • Abstract
  • Date: 10:25-10:50, OCaml Workshop, Fri Sep 5th 2014.

» Service and Socialising

Heidi Howard and Leonhard Markert are acting as student volunteers at this years ICFP, and assisting with videoing various workshops such as CUFP Tutorials, Haskell Symposium, the Workshop on Functional High-Performance Computing and the ML Family Workshop. Follow their live blogging on the Systems Research Group SysBlog and leave comments about any sessions you’d like to know more about!

Anil Madhavapeddy is the ICFP industrial relations chair and will be hosting an Industrial Reception on Thursday 4th September in the Museum of World Culture starting from 1830. There will be wine, food and some inspirational talks from the ICFP sponsors that not only make the conference possible, but provide an avenue for the academic work to make its way out into industry (grad students that are job hunting: this is where you get to chat to folk hiring FP talent).

This list hasn’t been exhaustive, and only covers the activities of my group in OCaml Labs and the Systems Research Group at Cambridge. There are numerous other talks from the Cambridge Computer Lab during the week, but the artistic highlight will be on Saturday evening following the CUFP talks: Sam Aaron will be doing a live musical performance sometime after 8pm at 3vaningen. Sounds like a perfect way to wind down after what’s gearing to up to be an intense ICFP 2014. I look forward to seeing old friends and making new ones in Gothenburg soon!

August 30, 2014 10:00 PM

August 29, 2014

Richard Jones

virt-v2v: better living through new technology

If you ever used the old version of virt-v2v, our software that converts guests to run on KVM, then you probably found it slow, but worse still it was slow and could fail at the end of the conversion (after possibly an hour or more). No one liked that, least of all the developers and support people who had to help people use it.

A V2V conversion is intrinsically going to take a long time, because it always involves copying huge disk images around. These can be gigabytes or even terabytes in size.

My main aim with the rewrite was to do all the work up front (and if the conversion is going to fail, then fail early), and leave the huge copy to the last step. The second aim was to work much harder to minimize the amount of data that we need to copy, so the copy is quicker. I achieved both of these aims using a lot of new technology that we developed for qemu in RHEL 7.

Virt-v2v works (now) by putting an overlay on top of the source disk. This overlay protects the source disk from being modified. All the writes done to the source disk during conversion (eg. modifying config files and adding device drivers) are saved into the overlay. Then we qemu-img convert the overlay to the final target. Although this sounds simple and possibly obvious, none of this could have been done when we wrote old virt-v2v. It is possible now because:

  • qcow2 overlays can now have virtual backing files that come from HTTPS or SSH sources. This allows us to place the overlay on top of (eg) a VMware vCenter Server source without having to copy the whole disk from the source first.
  • qcow2 overlays can perform copy-on-read. This means you only need to read each block of data from the source once, and then it is cached in the overlay, making things much faster.
  • qemu now has excellent discard and trim support. To minimize the amount of data that we copy, we first fstrim the filesystems. This causes the overlay to remember which bits of the filesystem are used and only copy those bits.
  • I added support for fstrim to ntfs-3g so this works for Windows guests too.
  • libguestfs has support for remote storage, cachemode, discard, copy-on-read and more, meaning we can use all these features in virt-v2v.
  • We use OCaml — not C, and not type-unsafe languages — to ensure that the compiler is helping us to find bugs in the code that we write, and also to ensure that we end up with an optimized, standalone binary that requires no runtime support/interpreters and can be shipped everywhere.

by rich at August 29, 2014 09:26 PM

August 28, 2014

Functional Jobs

Senior Software Engineer (Functional) at McGraw-Hill Education (Full-time)

This Senior Software Engineer position is with the new LearnSmart team at McGraw-Hill Education's new and growing Research & Development center in Boston's Innovation District. We make software that helps college students study smarter, earn better grades, and retain more knowledge.

The LearnSmart adaptive engine powers the products in our LearnSmart Advantage suite — LearnSmart, SmartBook, LearnSmart Achieve, LearnSmart Prep, and LearnSmart Labs. These products provide a personalized learning path that continuously adapts course content based on a student’s current knowledge and confidence level.

On our team, you'll get to:

  • Move textbooks and learning into the digital era
  • Create software used by millions of students
  • Advance the state of the art in adaptive learning technology
  • Make a real difference in education

Our team's products are built with Flow, a functional language in the ML family. Flow lets us write code once and deliver it to students on multiple platforms and device types. Other languages in our development ecosystem include especially JavaScript, but also C++, SWF (Flash), and Haxe.

If you're interested in functional languages like Scala, Swift, Erlang, Clojure, F#, Lisp, Haskell, and OCaml, then you'll enjoy learning Flow. We don't require that you have previous experience with functional programming, only enthusiasm for learning it. But if you have do some experience with functional languages, so much the better! (On-the-job experience is best, but coursework, personal projects, and open-source contributions count too.)

We require only that you:

  • Have a solid grasp of CS fundamentals (languages, algorithms, and data structures)
  • Be comfortable moving between multiple programming languages
  • Be comfortable with modern software practices: version control (Git), test-driven development, continuous integration, Agile

Get information on how to apply for this position.

August 28, 2014 09:18 PM

Github OCaml jobs

Full Time: Software Developer (Functional Programming) at Jane Street in New York, NY; London, UK; Hong Kong

Software Developer (Functional Programming)

Jane Street is looking to hire great software developers with an interest in functional programming. OCaml, a statically typed functional programming with similarities to Haskell, Scheme, Erlang, F# and SML, is our language of choice. We've got the largest team of OCaml developers in any industrial setting, and probably the world's largest OCaml codebase. We use OCaml for running our entire business, supporting everything from research to systems administration to trading systems. If you're interested in seeing how functional programming plays out in the real world, there's no better place.

The atmosphere is informal and intellectual. There is a focus on education, and people learn about software and trading, both through formal classes and on the job. The work is challenging, and you get to see the practical impact of your efforts in quick and dramatic terms. Jane Street is also small enough that people have the freedom to get involved in many different areas of the business. Compensation is highly competitive, and there's a lot of room for growth.

You can learn more about Jane Street and our technology from our main site, janestreet.com. You can also look at a a talk given at CMU about why Jane Street uses functional programming (http://ocaml.janestreet.com/?q=node/61), and our programming blog (http://ocaml.janestreet.com).

We also have extensive benefits, including:

  • 90% book reimbursement for work-related books
  • 90% tuition reimbursement for continuing education
  • Excellent, zero-premium medical and dental insurance
  • Free lunch delivered daily from a selection of restaurants
  • Catered breakfasts and fresh brewed Peet's coffee
  • An on-site, private gym in New York with towel service
  • Kitchens fully stocked with a variety of snack choices
  • Full company 401(k) match up to 6% of salary, vests immediately
  • Three weeks of paid vacation for new hires in the US
  • 16 weeks fully paid maternity/paternity leave for primary caregivers, plus additional unpaid leave

More information at http://janestreet.com/culture/benefits/

August 28, 2014 01:04 PM

August 27, 2014

OCaml Book

More OCaml: Algorithms, Methods & Diversions

More OCaml: Algorithms, Methods & Diversions is now available on Amazon at $39.99 or less, or as a DRM-free PDF eBook for $14.99 at ocaml-book.com, where you will also find sample chapters, and the exercises and examples to download.

Here's the blurb:

 

In More OCaml John Whitington takes a meandering tour of functional programming with OCaml, introducing various language features and describing some classic algorithms. The book ends with a large worked example dealing with the production of PDF files. There are questions for each chapter together with worked answers and hints.

More OCaml will appeal both to existing OCaml programmers who wish to brush up their skills, and to experienced programmers eager to explore functional languages such as OCaml. It is hoped that each reader will find something new, or see an old thing in a new light. For the more casual reader, or those who are used to a different functional language, a summary of basic OCaml is provided at the front of the book.

 

If you buy the book, please do consider leaving a review on Amazon, which you can do even if you buy just the PDF eBook.

 

by John Whitington at August 27, 2014 12:00 PM

August 26, 2014

OCaml Platform

UTop: a much improved interface to the OCaml toplevel

This is a post about the utop toplevel provided in the OPAM repository as an alternative to the standard OCaml one.

OCaml comes with an interactive toplevel. If you type ocaml in a shell you will get a prompt where you can type OCaml code that is compiled and executed on the fly.

$ ocaml
    OCaml version 4.02.0+dev12-2014-07-30

# 1 + 1;;
- : int = 2

You can load libraries and your own modules in the toplevel, and is great for playing with your code. You'll quickly notice that the user experience is not ideal, as there is no editing support: you cannot conveniently chagne what you type nor can you rewind to previously typed phrases.

This can be improved by using tools such as ledit or rlwrap which adds line editing support for any program: rlwrap ocaml. This is better but still doesn't provides fancy features such as context sensitive completion.

That's why UTop was started. UTop is a shiny frontend to the OCaml interactive toplevel, which tries to focus on the user experience and features:

  • interactive line editing
  • real-time tab completion of functions and values
  • syntax highlighting

And many other things that makes life easier for users that have been added over time.

What does UTop stand for?

UTop stands for Universal Toplevel. Universal because it can be used in a terminal or in Emacs (I originally planned to add a windowed version using GTK but unfortunately never completed it).

The UTop prompt

The utop prompt looks much more 'blinky' than the one of the default toplevel. Install it using OPAM very simply:

opam install utop
eval `opam config env`  # may not be needed
utop

This is typically what you see when you start utop:

─( 16:36:52 )─< command 0 >───────────────────────{ counter: 0 }─
utop #
┌───┬────────────┬─────┬───────────┬──────────────┬───────┬─────┐
│Arg│Arith_status│Array│ArrayLabels│Assert_failure│Big_int│Bigar│
└───┴────────────┴─────┴───────────┴──────────────┴───────┴─────┘

It displays:

  • the time
  • the command number
  • the macro counter (for Emacs style macros)

The box at the bottom is for completion, which is described in the next section.

If the colors seem too bright you can type #utop_prompt_fancy_light, which is better for light backgrounds. This can be set permanently by adding the line to ~/.ocamlinit or by adding profile: light to ~/.utoprc.

The prompt can be customized by the user, by setting the reference UTop.prompt:

utop # UTop.prompt;;
- : LTerm_text.t React.signal ref = {contents = <abstr>}

LTerm_text.t is for styled text while React.signal means that it is a reactive signal, from the react library. This makes it very easy to create a prompt where the time is updated every second for instance.

Real-time completion

This is the main feature that motivated the creation of UTop. UTop makes use of the compiler internals to find possible completions on:

  • function names
  • function argument names
  • constructor names
  • record fields
  • method names

Instead of the classic way of displaying a list of words when the user press TAB, I chose to dynamically display the different possibilities as the user types. This idea comes from the dmenu tool from the dwm window manager.

The possible completions are displayed in the completion bar below the prompt. It is possible to navigate in the list by using the meta key (Alt by default most of the time) and the left and right arrows. A word can be selected by pressing the meta key and TAB. Also pressing just TAB will insert the longest common prefix of all possibilities.

Syntax highlighting

UTop can do basic syntax highlighting. This is disabled by default but can be enabled by writing a ~/.utoprc file. You can copy one from the repository, either for dark background or light background.

Emacs integration

As said earlier UTop can be run in Emacs. Instructions to set this up can be found in UTop's readme. The default toplevel can also be run this way but UTop is better in the following respects:

  1. it provides context-sensitive completion
  2. it behaves like a real shell, i.e. you cannot delete the prompt

They are several Emacs libraries for writing shell-like modes but I wrote my own because with all of the ones I found it is possible to insert or remove characters from the prompt, which I found frustrating Even with the mode used by the Emacs Shell mode it is possible. AFAIK at the time I wrote it the UTop mode was the only one where it was really impossible to edit the something in the frozen part of the buffer.

Other features

This is a non-exhaustive list of features that have been added over time to enhance the user experience. Some of them might be controversial, so I tried to choose what was the most requested most of the time.

  • when using the lwt or async libraries, UTop will automatically wait for ['a Lwt.t] or ['a Deferred.t] values and return the ['a] instead
  • made -short-paths the default. This option allow to display shorter types when using packed libraries such as core
  • hide identifiers starting with _ to the user. This is for hiding the churn generated by syntax extensions. This can be disabled with UTop.set_hide_reserved or with the command line argument -show-reserved.
  • automatically load camlp4 when the user requests a syntax extension. In the default toplevel one has to type #camlp4 first.
  • hide verbose messages from the findlib library manager.
  • add a typeof directive to show the type of modules and values.
  • automatically load files from $OCAML_TOPLEVEL_PATH/autoload at startup.
  • allow to specify libraries to be loaded on the command line.

Libraries developed to support UTop

For the needs of UTop I wrote lambda-term, which is kind of an equivalent of ncurses+readline, but written in OCaml. It was written because I wasn't happy with the ncurses API and I wanted something more fancy than readline, especially for completion. In the end I believe that it is much more fun to write terminal applications in OCaml using lambda-term.

The pure editing part is managed by the zed library, which is independent from the user interface.

UTop development

Utop is fairly feature-complete, and so I don't spend much time on it these days. It became the recommended toplevel to use with the Real World OCaml book, and most users are happier with the interactive interface than using the traditional toplevel.

Many thanks to Peter Zotov who recently joined the project to keep it up-to-date and add new features such as extension point support. Contributions from others (particularly around editor integration) are very welcome, so if you are interested on hacking on it get in touch via the GitHub issue tracker or via the OCaml Platform mailing list.

by Jérémie Dimino at August 26, 2014 12:00 AM

August 25, 2014

OCamlCore Forge News

OCaml EFL 1.11.0 released

Majors changes: - Moved to version 1.11 of the EFL - New API for signals (module Elm_connect) - More parts of the binding are generated

by Alexis Bernadet at August 25, 2014 10:01 AM