# OCaml Planet

The OCaml Planet aggregates various blogs from the OCaml community. If you would like to be added, read the Planet syndication HOWTO.

# Unicode 10.0.0 refresh — Daniel Bünzli, Jun 21, 2017

# Weekly News — OCaml Weekly News, Jun 20, 2017

# Weekly News — OCaml Weekly News, Jun 13, 2017

# Full Time: Software Developer (Functional Programming) at Jane Street in New York, NY; London, UK; Hong Kong — GitHub Jobs, Jun 08, 2017

Software Developer

Jane Street is a proprietary quantitative trading firm, focusing primarily on trading equities and equity derivatives. We use innovative technology, a scientific approach, and a deep understanding of markets to stay successful in our highly competitive field. We operate around the clock and around the globe, employing over 500 people in offices in New York, London and Hong Kong.

The markets in which we trade change rapidly, but our intellectual approach changes faster still…

Read more...Software Developer

Jane Street is a proprietary quantitative trading firm, focusing primarily on trading equities and equity derivatives. We use innovative technology, a scientific approach, and a deep understanding of markets to stay successful in our highly competitive field. We operate around the clock and around the globe, employing over 500 people in offices in New York, London and Hong Kong.

The markets in which we trade change rapidly, but our intellectual approach changes faster still. Every day, we have new problems to solve and new theories to test. Our entrepreneurial culture is driven by our talented team of traders and programmers. At Jane Street, we don't come to work wanting to leave. We come to work excited to test new theories, have thought-provoking discussions, and maybe sneak in a game of ping-pong or two. Keeping our culture casual and our employees happy is of paramount importance to us.

We are looking to hire great software developers with an interest in functional programming. OCaml, a statically typed functional programming language 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

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

Hide# Weekly News — OCaml Weekly News, Jun 06, 2017

# New in libguestfs: Rewriting bits of the daemon in OCaml — Richard Jones, Jun 04, 2017

libguestfs is a C library for creating and editing disk images. In the most common (but not the only) configuration, it uses KVM to sandbox access to disk images. The C library talks to a separate daemon running inside a KVM appliance, as in this Unicode-art diagram taken from the fine manual:

┌───────────────────┐ │ main program │ │ │ │ │ child process / appliance │ …Read more...

libguestfs is a C library for creating and editing disk images. In the most common (but not the only) configuration, it uses KVM to sandbox access to disk images. The C library talks to a separate daemon running inside a KVM appliance, as in this Unicode-art diagram taken from the fine manual:

┌───────────────────┐ │ main program │ │ │ │ │ child process / appliance │ │ ┌──────────────────────────┐ │ │ │ qemu │ ├───────────────────┤ RPC │ ┌─────────────────┐ │ │ libguestfs ◀╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍╍▶ guestfsd │ │ │ │ │ ├─────────────────┤ │ └───────────────────┘ │ │ Linux kernel │ │ │ └────────┬────────┘ │ └───────────────│──────────┘ │ │ virtio-scsi ┌──────┴──────┐ │ Device or │ │ disk image │ └─────────────┘

The library has to be written in C because it needs to be linked to any main program. The daemon (`guestfsd`

in the diagram) is also written in C. But there’s not so much a specific reason for that, except that’s what we did historically.

The daemon is essentially a big pile of functions, most corresponding to a libguestfs API. Writing the daemon in C is painful to say the least. Because it’s a long-running process running in a memory-constrained environment, we have to be very careful about memory management, religiously checking every return from `malloc`

, `strdup`

etc., making even the simplest task non-trivial and full of untested code paths.

So last week I modified libguestfs so you can now write APIs in OCaml if you want to. OCaml is a high level language that compiles down to object files, and it’s entirely possible to link the daemon from a mix of C object files and OCaml object files. Another advantage of OCaml is that you can call from C ↔ OCaml with relatively little glue code (although a *dis*advantage is that you still need to write that glue mostly by hand). Most simple calls turn into direct CALL instructions with just a simple bitshift required to convert between ints and bools on the C and OCaml sides. More complex calls passing strings and structures are not too difficult either.

OCaml also turns memory errors into a single exception, which unwinds the stack cleanly, so we don’t litter the code with memory handling. We can still run the mixed C/OCaml binary under valgrind.

Code gets quite a bit shorter. For example the case_sensitive_path API — all string handling and directory lookups — goes from 183 lines of C code to 56 lines of OCaml code (and much easier to understand too).

I’m reimplementing a few APIs in OCaml, but the plan is definitely not to convert them all. I think we’ll have C and OCaml APIs in the daemon for a very long time to come.

Hide

# Full Time: Front-end Developer at issuu in Copenhagen — GitHub Jobs, Jun 02, 2017

**Fulltime, Copenhagen**

issuu is the world's fastest-growing digital publishing platform. We are looking for a new member to join our fantastic team. With great people, unique ideas and stunning technology, we're changing the future of publishing today. Can you be the best at what you do? Join us!

**About this job**

As a Front-end Developer at issuu, you will be joining a team of highly skilled web enthusiasts building web applications in an agile environment. We currently develop for deskto…

Read more...**Fulltime, Copenhagen**

issuu is the world's fastest-growing digital publishing platform. We are looking for a new member to join our fantastic team. With great people, unique ideas and stunning technology, we're changing the future of publishing today. Can you be the best at what you do? Join us!

**About this job**

As a Front-end Developer at issuu, you will be joining a team of highly skilled web enthusiasts building web applications in an agile environment. We currently develop for desktops, tablets and mobile web. This requires great responsive sites that ensure the best possible user experience on all platforms.

We run a NodeJS server in a production system that serves billions of pages every month. Our client-side applications are a mix of vanilla JavaScript (transpiled with Babel from ES2015), and React / Redux, apps with an in-house developed, modular, BEM-styled styling framework.SASS enables us to keep our CSS well structured.

As our ideal candidate, you are excited about HTML5 features, like SVG and , and have a feel for the pulse of new developments in browser technology.In a system the size of issuu’s, code maintainability is just as important as accessibility. That also means that you are willing to share your code with other people or sit together for pair-programming sessions.

**What we Like**

- We think browsers are awesome.
- We love HTML5, CSS3 and all the new exciting web APIs.
- We use React, Redux, ES2015 and CSS Modules.
- We draw with Canvas, WebGL and SVGs.
- We build modern progressive web apps.
- We like declarative and functional programming.
- We used to like jQuery and Backbone, but now we sort of grew apart.
- We also like it if our front-end developers aren’t afraid of touching our backends, which we make with -
- Python, NodeJS, OCaml and Erlang.

**Qualifications**

- Demonstrated ability to deliver results in a fast-paced environment as a self-starter and quick learner
- Expert understanding of browsers, web technologies (object-oriented JavaScript, ES2015, HTML, CSS), and a passion for the latest and greatest web standards
- Experience in collaborating with UI Designers
- Experience architecting and building robust, high-performance production web applications
- Used to working with Design and Product teams in an agile fashion
- Experience with building web applications for mobile web is a plus
- Experience with MVC-based web applications is a plus
- Experience with server-side languages like Python is a plus
- Solid communications skills in English

**What we Offer**

- You’ll be a part of issuu – an amazing place with room for parents, foodies, geeks, odd birds and the occasional normal person
- Informal, inclusive and very flexible workplace
- Competitive compensation package
- Flat hierarchy – every opinion matters regardless of team and position
- Regular hackathons
- A sleek Mac and a pretty sweet desk setup
- Great offices in Copenhagen, Palo Alto and Berlin

**About the Team and Office**

You will be joining our DK engineering team in Copenhagen consisting of approx. 27 developers. We are a diverse office with members of all parts of issuu, including Customer Support, Product, Design, Data Analytics and Management.

In a company the size of issuu, code maintainability is just as important as site accessibility. That also means that you are willing to share your code with other people or sit together for pair programming sessions.

Our office is conveniently located next to the Copenhagen Central Station. We provide nice, catered lunches each day, regular outings and monthly Friday bars with drinks, snacks and activities.

**About issuu**

issuu connects the world’s publishers to an audience of active consumers, on a global scale. Every day millions of people find, read and share billions of pieces of content they find meaningful, from every device. Millions of magazine, newspaper and catalog creators are empowered to distribute, measure and monetize their work through the issuu platform issuu. If you are interested in a sneak peek of who we are as issuuees, have a look at our brandbook.

**Details**

It’s a prerequisite that you have a valid EU work permit

Hide# PureScript/React Front-End Developer at CollegeVine (Full-time) — Functional Jobs (FunctionalJobs.com), Jun 01, 2017

### Overview

CollegeVine is looking for a product-focused front-end developer to help engineer the future of guidance, mentorship, and higher education attainment.

There aren't many industries left that haven't been significantly disrupted by technology in some way, but you're reading about one right here! Public high school guidance departments are under-resourced in our country and we think near-peer mentorship is the solution. As it stands, the current admissions process is a hug…

Read more...### Overview

CollegeVine is looking for a product-focused front-end developer to help engineer the future of guidance, mentorship, and higher education attainment.

There aren't many industries left that haven't been significantly disrupted by technology in some way, but you're reading about one right here! Public high school guidance departments are under-resourced in our country and we think near-peer mentorship is the solution. As it stands, the current admissions process is a huge source of stress and confusion for students and parents alike. If we execute correctly, your work will impact the entire next generation of college graduates-to-be.

You will join a fast-moving company whose culture centers around authenticity, excellence, and balance. You'll find that everyone likes to keep things simple and transparent. We prefer to be goal-oriented and hands-off as long as you are a self-starter.

Our modern perspective on developer potential means we celebrate and optimize for real output. And that's probably the reason why we're a polyglot functional programming shop, with emphasis on Haskell, PureScript, and functional paradigms. Our infrastructure and non-mission-critical tooling tends to be in whatever works best for the task at hand: sometimes that's Haskell with advanced GHC extensions a-blazin', other times it's minimalist Ruby or bash—basically, it's a team decision based on whatever sits at the intersection of appropriateness, developer joy, quality, and velocity.

### Requirements

You know you are right for this position if:

- You have at least five years of professional software engineering experience, and at least two years of preference for a high-level programming language that's used in industry, like Haskell, Clojure, OCaml, Erlang, F#, or similar.
- You have front-end experience with JS or a functional language that compiles to JS, like PureScript, Elm, Clojurescript, or similar. We use PureScript, React, and ES6 on the front-end in a fairly seamless way. It's pretty awesome.
- You seek ownership beyond your own work, and look to the product and company as a whole.
- You are a self-starter and internally motivated, with a strong desire to be part of a successful team that shares your high standards.
- You have great written communication skills and are comfortable with making big decisions over digital presence (e.g. video chat).
- You have polyglot experience along several axes (dynamic/static, imperative/functional, lazy/strict, weird/not-weird).
- You are comfortable with modern infrastructure essentials like AWS, Heroku, Docker, CI, etc. You have basic but passable sysadmin skills.
- You are fluent with git.
- You instrument before you optimize. You test before you ship. You listen before you conclude. You measure before you cut. Twice.

### Benefits

We offer a competitive salary and a full suite of benefits, some of them unconventional, but awesome for the right person:

- Medical, dental, and vision insurance.
- Flexible hours with a 4-hour core - plan the rest of your workday as you wish, just give us the majority of your most creative hours. Productivity ideas: avoid traffic, never wait in line at the grocery store, wake up without an alarm clock.
- Goal-based environment (as opposed to grind-based or decree-based environment; work smarter, not harder; intelligently, not mindlessly). We collaborate on setting goals, but you set your own process for accomplishing those goals. You will be entrusted with a lot of responsibility and you might even experience fulfillment and self-actualization as a result.
- Join an engineering culture that celebrates mindfulness and takes the quality of your attention seriously.

Remember: We’re a startup. You’re an early employee. We face challenges. We have to ship. Your ideas matter. You will make a difference.

Get information on how to apply for this position.

Hide# Weekly News — OCaml Weekly News, May 30, 2017

# Frama-C 15 - Phosphorus is out. Download ithere. — Frama-C, May 30, 2017

# A modular formalization of type theory in Coq — Andrej Bauer, May 29, 2017

Here are the slides for the talk I just gave at TYPES 2017 in Budapest. It is joint work with Philipp Haselwarter and Théo Winterhalter. The abstract for the talk is available online.

It describes a complete formalization of dependent type theory which allows you to turn various features of type theory on and off, and it proves several basic formal theorems.

**GitHub repository:** formal-type-theory

**Slides:** TYPES 2017 – A modular formalization of type theory in Coq [PDF]

# Weekly News — OCaml Weekly News, May 23, 2017

# More type classes in OCaml — Shayne Fletcher (Evelgren), May 22, 2017

# More type classes

**Author:** Joel Björnson**About the author: **Joel has been enjoying functional programming ever since being introduced to Haskell at Chalmers University (Sweden). Since then he's been dabbling in F# and more recently OCaml. He's currently based in London, working at the intersection of functional programming and finance.

As demonstrated in previous articles on this blog, OCaml comes with a rich module system. Among other things it enables developers to …

Read more...# More type classes

**Author:** Joel Björnson**About the author: **Joel has been enjoying functional programming ever since being introduced to Haskell at Chalmers University (Sweden). Since then he's been dabbling in F# and more recently OCaml. He's currently based in London, working at the intersection of functional programming and finance.

As demonstrated in previous articles on this blog, OCaml comes with a rich module system. Among other things it enables developers to write code that is polymorphic over module signatures. As such, parameterized modules (aka functors) play a similar role to what type classes do in Haskell, and as explained here, it is straightforward to map simple type classes to modules in OCaml. In Haskell, type classes are often used as design patterns for structuring programs and over the years a taxonomy of type classes inspired by Category Theory has evolved. Standard patterns such as *functor*, *monad* and *monoid* have had a strong influence on the design of common APIs. In OCaml there is less focus on such idioms. In this post we explore how some of the Haskell patterns implemented in terms of type classes can be ported to OCaml and how that impacts program design. In particular we cover four commonly used type classes that ships with standard Haskell distributions:

- Functor
- Monoid
- Applicative Functor
- Traversable

- API design
- Code reusability
- Testability

`map`

function over some custom data type, one should expect it to have similar properties to the function `List.map`

operating on lists. The second point is about code reuse. By writing functions that are expressed solely in terms of other module signatures they become reusable in different contexts; For instance by implementing the primitive operators for a monoid we get additional combinators (such as `concat`

) defined generically for any monoid for free! Thirdly, these patterns all come with a set of theoretically well founded properties. As demonstrated by some of the examples below, it is also possible to write generic tests that can be used to validate concrete implementations of the patterns for different underlying data types. ## Prerequisites and conventions

From now on we'll be using lowercase names such as *applicative functor* to describe the patterns themselves. Names starting with uppercase, for instance `Applicative`

refers to the Haskell name of the type class, while signature names in OCaml are all uppercase (e.g `APPLICATIVE`

). To avoid confusion between the terms *functor* as in the *functor pattern* and OCaml functors referring to parameterized modules, we use the name *ocaml-functor* to mean the latter. Basic familiarity with Haskell syntax is also be assumed. Importantly, note that Haskell uses the infix operator `(.)`

for function composition:

`f . g = \x -> f (g x)`

In the OCaml code below we instead use

`( << )`

to be defined similarly along with (the more idiomatic) pattern of forward composition `( >> )`

, an identity function `id`

and a function `const`

: `let ( << ) f g x = f (g x);;`

let ( >> ) f g = g << f;;

let id x = x;;

let const x _ = x;;

We also deviate slightly from the naming conventions in Haskell for operations, for instance

`fmap`

becomes `map`

and `mconcat`

is named `concat`

. ## Representing the patterns

We use a standard approach for mapping type classes in Haskell to module signatures in OCaml.

### Functors

The `Functor`

type class captures the pattern of mapping over the value(s) of some parameterized data type. In Haskell it can be defined as:

`class Functor f where`

fmap :: (a -> b) -> f a -> f b

In OCaml we may instead construct a corresponding module signature:

`module type FUNCTOR = sig`

type 'a t

val map : ('a -> 'b) -> 'a t -> 'b t

end;;

In order for a type to qualify as a functor, one need to provide an implementation for `map`

(`fmap`

in Haskell) that satisfies the signature. For instance, the `Functor`

instance for the list type in Haskell is given by:

`instance Functor [] where`

fmap = map

Here,

`map`

is the standard map function over lists. In OCaml we create a module implementing the `FUNCTOR`

signature, which for lists may look like: `module ListFunctor : FUNCTOR with type 'a t = 'a list = struct`

type 'a t = 'a list

let map f = List.map f

end;;

One difference is that the module is named which allows for multiple instances of the same signature for the same type to coexist. The `with type`

construct is required in order to be able to export the type `'a t`

specified by the signature. It makes the fact that `ListFunctor.t`

is indeed the type `list`

transparent, allowing us to apply `ListFunctor.map`

to ordinary lists.

Type classes in Haskell often come with a set of *laws*. These are specifications that any instance of the type class must obey. However they are not enforced by the type system and thus need to be considered when writing the implementation. For `Functor`

s, any instances should satisfy the following constraints:

`fmap id = id fmap (f . g) = fmap f . fmap g`

These invariants state that the map function must be

*structure preserving*, i.e. is not allowed to change the shape of the given value mapped over. They also have a deeper theoretical justification when described in terms of Functors in Category Theory. From a practical point of view it is sufficient to note that violating this constraint leads to code that is difficult to reason about and refactor. Consider for instance a function:

`let increment_twice xs =`

xs

|> List.map (fun x -> x + 1)

|> List.map (fun x -> x + 1)

;;

One should expect that applying the following optimization:

`let increment_twice xs = List.map (fun x -> x + 2) xs;;`

does not impact its semantics. An immediate advantage of capturing the functor pattern explicitly via a signature (`FUNCTOR`

) is that it enables us to to define an additional parameterized module with tests for validating any concrete implementation of the signature:

`module TestFunctor (F : FUNCTOR) = struct`

let test_id x = F.map id x = x

let test_compose xs =

let f x = x mod 2 in

let g x = x - 1 in

F.map (g >> f) xs = F.map f (F.map g xs)

end;;

The tests here correspond to the two

*functor laws*stated above.

For instance to test `ListFunctor`

we first apply `TestFunctor`

to this module in order to retrieve a specialized version:

`module TFL = TestFunctor (ListFunctor);;`

Here are a few examples of using the module:

`TFL.test_id [];;`

TFL.test_id [1;2];;

TFL.test_compose [];;

TFL.test_compose [1;2;3];;

The `option`

type in OCaml also forms a functor:

`module OptionFunctor : FUNCTOR with type 'a t = 'a option = struct`

type 'a t = 'a option

let map f = function

| Some x -> Some (f x)

| None -> None

end;;

And similar to the list example, we get a test module for free:

`module TOF = TestFunctor (OptionFunctor);;`

TOF.test_id (Some 42);;

TOF.test_id None;;

TOF.test_compose (Some 42);;

TOF.test_compose None;;

As will be illustrated by some of the examples below, functors are not only applicable to container like types and also not all containers form functors.

### Monoids

Monoid is another example of a common pattern where instances can be found for a variety of types. In Haskell it's defined as:

`class Monoid m where`

mempty :: m

mappend :: m -> m -> m

Any type qualifying as a monoid must have identity value (

`mempty`

) and a binary operator (`mappend`

) for composing any two elements. The OCaml version can be specified by the following module type:

`module type MONOID = sig`

type t

val empty : t

val append : t -> t -> t

end;;

There are also a few laws that instances should obey:

`mappend mempty x = x`

mappend x mempty = x

mappend x (mappend y z) = mappend (mappend x y) z

The first two state that `mempty`

is an identity element with respect to `mappend`

and the second one that `mappend`

must be associative. Again, this can be captured by a test module:

`module TestMonoid (M : MONOID) = struct`

let test_left_id x = M.append M.empty x = x

let test_right_id x = M.append x M.empty = x

let test_assoc x y z =

M.append x (M.append y z) = M.append (M.append x y) z

end;;

One of the more famous monoids is given by the natural numbers with addition and identity element *0*:

`module IntAddMonoid : MONOID with type t = int = struct`

type t = int

let empty = 0

let append = ( + )

end;;

Another advantage of formalizing patterns by explicit signatures is that it enables us to define derived combinators generically. For example, the `append`

operation from `IntAddMonoid`

can be lifted to a sum function accepting a list of integers, adding them together or defaulting to 0 if the empty list is given:

`open IntAddMonoid;;`

let sum xs = List.fold_left append empty xs;;

The scheme can be generalized to operate on any list of monoids. To avoid having to specify the implementation manually for each monoid instance, one may construct a module-functor for generating extension functions:

`module MonoidUtils (M : MONOID) = struct`

include M

let ( <+> ) x y = append x y

let concat xs = List.fold_left ( <+> ) empty xs

end;;

Here `MonoidUtils`

takes a `MONOID`

module and re-exports its definition along with two additional utility functions, an infix version of append `( <+> )`

and `concat`

.

Another example of a monoid is a list, parameterized over any type. In Haskell the instance is given by:

instance Monoid [a] where

mempty = []

mappend x y = x ++ y

Where

`(++)`

is the concatenation operator for lists. In OCaml one could imagine attempting something like: `(* Pseudo-code - not valid OCaml! *)`

module ListMonoid : MONOID with type t = 'a list = struct

type t = 'a list

let empty = []

let append xs ys = xs @ ys

end;;

However it is not possible to directly parameterize modules by types. A work around can be achieved by first introducing a dummy module for wrapping the type and passing it along as a module parameter:

`module type TYPE = sig type t end;;`

module ListMonoid (T : TYPE) : MONOID with type t = T.t list = struct

type t = T.t list

let empty = []

let append xs ys = xs @ ys

end;;

This comes with an obvious disadvantage of having to create specialized versions for each concrete list type. Some of the inconvenience is compensated for by explicit type parameters and support for local modules, created at run-time. Here's an example implementing `concat`

for lists in terms of the generic list monoid:

`let concat (type a) xs =`

let module MU = MonoidUtils (ListMonoid(struct type t = a end)) in

MU.concat xs;;

Its signature is inferred as:

`val concat : 'a list list -> 'a list`

### Applicative Functors

An applicative functor has more structure than a regular functor. In Haskell it can be defined as:

class (Functor f) => Applicative f where

pure :: a -> f a

(<*>) :: f (a -> b) -> f a -> f b

The function

`pure`

turns a (pure) value into an applicative value and `( <*> )`

takes a function wrapped inside an applicative along with an applicative value and returns an applicative result corresponding to applying the value to the function. The additional constraint (`(Functor f) => Applicative f`

enforces that any type that instantiates the `Applicative`

type class must also be an instance of `Functor`

. In OCaml we can achieve something similar by including the `FUNCTOR`

signature within a new signature `APPLICATIVE`

as in:

`module type APPLICATIVE = sig`

include FUNCTOR

val pure : 'a -> 'a t

val apply : ('a -> 'b) t -> 'a t -> 'b t

end;;

Here the infix operator

`( <*> )`

is named `apply`

. For a concrete example consider the applicative instance for the list type. Using the `ListFunctor`

module from above:

`module ListApplicative : APPLICATIVE with type 'a t = 'a list = struct`

include ListFunctor

let pure x = [x]

let apply fs xs =

List.concat @@ List.map (fun f -> List.map (fun x -> f x) xs) fs

end;;

`ListApplicative`

simply re-exports the implementation of `ListFunctor`

to satisfy the functor part of the signature, also mirroring the constraint from the Haskell version. `pure`

wraps a value in a list. `apply`

takes a list of functions, a list of values and applies each function to all elements of the list. Once again we may construct a *utility module* with some extra operators implemented using the primitive functions:

`module ApplicativeUtils (A : APPLICATIVE) = struct`

include A

let ( <$> ) f = map f

let ( <*> ) f = apply f

let ( <* ) x y = const <$> x <*> y

let ( *> ) x y = (fun _ y -> y) <$> x <*> y

let liftA2 f x y = f <$> x <*> y

end;;

The infix operators are variations of apply and map, `liftA2`

is for conveniently *lifting* a regular function of two arguments into a function operating on two applicative values.

By applying `ListApplicative`

to the `ApplicativeUtils`

functor we obtain a concrete module for operating on lists:

`module LAU = ApplicativeUtils (ListApplicative);;`

Its full signature can be listed by:

`#show_module LAU;;`

Producing the following output:

`module LAU :`

sig

type 'a t = 'a ListApplicative.t

val map : ('a -> 'b) -> 'a t -> 'b t

val pure : 'a -> 'a t

val apply : ('a -> 'b) t -> 'a t -> 'b t

val ( <$> ) : ('a -> 'b) -> 'a t -> 'b t

val ( <* ) : 'a t -> 'b t -> 'a t

val ( *> ) : 'a t -> 'b t -> 'b t

val liftA2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

end

Finally let's a take a look at a concrete example to see what the applicative interface actually brings in terms of functionality. Say we want to generate some mock data to be used for testing. Given the following types:

`type offer = Ask | Bid;;`

type quote =

{

time : int;

offer : offer;

ticker : string;

value : float;

};;

The snippet below produces a list of all possible combinations of some example data by combining a set of properties:

`let quotes =`

let open LAU in

(fun time offer ticker value -> { time; offer; ticker; value })

<$> [1;2;3;4;5]

<*> [Ask; Bid]

<*> ["XYZ"; "ZYK"; "ABC";"CDE"; "QRZ"]

<*> [100.; 90.; 80.; 70.];;

By composing applications of

`pure`

and `( <*> )`

we lift functions of arbitrary arity into applicative versions. For the list applicative, that means a generalized version of Cartesian products. Another useful instance of an applicative functor is the `option`

type:

`module OptionApplicative : APPLICATIVE with type 'a t = 'a option =`

struct

include OptionFunctor

let pure x = Some x

let apply fo xo =

match fo, xo with

| Some f, Some x -> Some (f x)

| _ -> None

end;;

Here we rely on the `OptionFunctor`

module to manage the functor part. `pure`

returns a value wrapped by the `Some`

constructor and `apply`

only produces a value if neither of its arguments are `None`

values. As with many other examples of instances, there is basically only one feasible implementation to choose from given the type constraints of the function signature.

With the implementation of the core interface, utilities come for free:

`module OAU = ApplicativeUtils (OptionApplicative);;`

We can now use it to conveniently lift operations into versions accepting optional arguments. Consider the following (safe) versions of division and square-root functions:

`let ( //. ) n d = if d = 0. then None else Some (n /. d);;`

let ssqrt x = if x < 0. then None else Some (sqrt x);;

Say we want to implement the formula `f(x,y,z) = (x / y) + sqrt(x) - sqrt(y)`

. The obvious approach is to use pattern matching as in:

`let f x y z =`

match x //. y, ssqrt x, ssqrt y with

| Some z, Some r1, Some r2 -> Some (z +. r1 -. r2)

| _ -> None

;;

Using the applicative operators from the `OAU`

module enables an alternative (more succinct) definition:

`open OAU;;`

let f x y z =

(fun z r1 r2 -> z +. r1 -. r2) <$> (x //. y) <*> ssqrt x <*> ssqrt y

;;

Applicative functors also come with a set of laws. In Haskell expressed as:

-- Identity

pure id <*> v = v

-- Homomorphism

pure f <*> pure x = pure (f x)

-- Interchange

u <*> pure y = pure ($ y) <*> u

--- Composition

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

These may again be turned into a generic testing module:

`module TestApplicative (A : APPLICATIVE) = struct`

module AU = ApplicativeUtils(A)

open AU

let test_id x = (pure id <*> x) = x

let test_hom f x = pure f <*> pure x = pure (f x)

let test_interchange u y =

(u <*> pure y) = (pure (fun f -> f y) <*> u)

let test_composition u v w =

(pure ( << ) <*> u <*> v <*> w) = (u <*> (v <*> w))

end;;

and be used to validate arbitrary instances of this pattern.

For example to test the list instance, we first construct a concrete module using the `TestApplicative`

functor:

`module TAL = TestApplicative (ListApplicative);;`

This may be used as in:

`TAL.test_hom String.length "Homomorphism";;`

### Traversables

Traversable is an interesting type class which also brings a couple of additional challenges to our effort of mapping Haskell patterns to OCaml. It may be described as a generalization of the *iterator pattern* and is defined in Haskell as:

class (Functor t, Foldable t) => Traversable t where

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

sequenceA :: Applicative f => t (f a) -> f (t a)

mapM :: Monad m => (a -> m b) -> t a -> m (t b)

sequence :: Monad m => t (m a) -> m (t a)

Concrete instances can be written by implementing any one of the above functions as they can all be expressed in terms of each other. We could potentially replicate this flexibility in OCaml by a set of different module-functors with signatures wrapping each function. However, for the purpose of this exercise we settle on `traverse`

as the defining implementation. Traverse is also parameterized over an `Applicative`

functor. A first attempt in OCaml might be something along the lines of:

`(*Psuedo-code - not valid OCaml!*)`

module type TRAVERSABLE = sig

type 'a t

val traverse : (type a)

(module A : APPLICATIVE with type 'a t = 'a a)

('a -> 'b a) ->

'a A.t ->

('b t) a

end;;

However here the type `a`

would itself require a type parameter. In Haskell lingo it is said to have kind `(* -> *)`

. Unfortunately OCaml does not support higher-kinded polymorphism.

Instead of passing `APPLICATIVE`

as an argument to each invocation of `traverse`

we can embed it in the module signature:

`module type TRAVERSABLE = sig`

type 'a t

module Applicative : APPLICATIVE

val traverse : ('a -> 'b Applicative.t) -> 'a t -> ('b t) Applicative.t

end;;

To mimic the Haskell constraints it is tempting to also require the

`FUNCTOR`

interface by throwing in a extra `include FUNCTOR`

. However, there's a technical reason for why this may not be a good idea which we'll return to in a bit. Even though the signature references a specific implementation of an `APPLICATIVE`

we can recover genericity by relying on module-functors to specify the implementation of a traversable for any applicative argument. Let's consider the functor for list traversables:

`module ListTraversable (A : APPLICATIVE) :`

TRAVERSABLE with type 'a t = 'a list

and type 'a Applicative.t = 'a A.t =

struct

type 'a t = 'a list

module Applicative = A

let rec traverse f xs =

let module AU = ApplicativeUtils(A) in

let open AU in

match xs with

| [] -> A.pure []

| x :: xs -> (fun y ys -> y :: ys) <$> f x <*> traverse f xs

end;;

Here one has to accept some extra verbosity compared to the Haskell version, although the code itself is fairly straightforward. The functor argument `A`

of type `APPLICATIVE`

serves to fulfil the requirement of having to export the `APPLICATIVE`

module. The implementation of `traverse`

is the interesting bit. Note that it is indeed defined generically for any applicative functor. The `ApplicativeUtils`

module constructor comes in handy for accessing the infix versions of the operators.

To give `ListTraversable`

a try, consider how it can be used for option effects:

`module LTO = ListTraversable (OptionApplicative);;`

This results in a module with the following signature:

`module LTO :`

sig

type 'a t = 'a list

val map : ('a -> 'b) -> 'a t -> 'b t

module Applicative : sig end

val traverse : ('a -> 'b Applicative.t) -> 'a t -> 'b t Applicative.t

end;;

where we also know that the

`Applicative`

sub-module is in fact our `OptionApplicative`

. `traverse`

in this context is a function that allows us to map each element of a list to an optional value where the computation produces a list with all values collected, only in case every element was successfully mapped to a `Some`

value.

For example using the safe square root function from above we can transform it into a version operating on lists:

`let all_roots = LTO.traverse ssqrt;;`

It only returns a list of values with the results in case each element produced a valid square root. A few examples:

`# all_roots [4.;9.;16.];;`

- : float LTO.t LTO.Applicative.t = Some [2.; 3.; 4.]

# all_roots [4.;-9.; 16.];;

- : float LTO.t LTO.Applicative.t = None

Next, let's consider a custom type (`'a tree`

) for which we are also able to implement the traversable interface:

`type 'a tree =`

| Leaf

| Node of 'a tree * 'a * 'a tree

;;

let node l x r = Node (l,x,r);;

Following is an instance of traversable for `tree`

s:

`module TreeTraversable (A : APPLICATIVE) :`

TRAVERSABLE with type 'a t = 'a tree

and type 'a Applicative.t = 'a A.t =

struct

module Applicative = A

type 'a t = 'a tree

type 'a a = 'a A.t

let rec traverse f t =

let module AU = ApplicativeUtils(A) in let open AU in

match t with

| Leaf -> pure Leaf

| Node (l,x,r) -> node <$> traverse f l <*> f x <*> traverse f r

end;;

From the Haskell specification we know that any traversable must be a functor. Comparing the signatures for `map`

and `traverse`

also reveals their similarities:

`val map : ('a -> b) -> 'a t -> 'b t`

val traverse : ('a -> 't A.t) -> 'a t -> ('b t) A.t

However, embedding

`map`

in the module signature for `TRAVERSABLE`

forces the user to define it manually. Would it be possible to achieve a generic implementation expressed in terms of the traverse function? It can be done by choosing a suitable `Applicative`

where the effect does not impact the result. The simplest possible type forming an applicative functor is the identity type:

`type 'a id = 'a;;`

for which a trivial

`APPLICATIVE`

instance exist: `module IdApplicative : APPLICATIVE with type 'a t = 'a id = struct`

type 'a t = 'a id

let pure x = x

let map f = f

let apply f = map f

end;;

Using `IdApplicative`

for the effect, `traverse`

collapses into `map`

:

`module TreeTraversableId = TreeTraversable (IdApplicative);;`

let map f = TreeTraversableId.traverse f;;

Similar to the pattern of utility modules for extending the interface with additional functions we may implement another module-functor `TraversableFunctor`

that produces a functor instance given a module-functor for building traversables:

`module TraversableFunctor (MT : functor (A : APPLICATIVE) ->`

TRAVERSABLE with type 'a Applicative.t = 'a A.t) =

struct

module TI = MT(IdApplicative)

let map f = TI.traverse f

end;;

Following is an example creating a functor for trees derived from its traversable implementation:

`module TTU = TraversableFunctor (TreeTraversable);;`

Its map function can be used as in:

`TTU.map (fun x -> x * x) (node Leaf 3 (node Leaf 5 Leaf));;`

We could also define another utility module for deriving the `sequence`

operator, in order to recover some of the functionality from Haskell, where `sequence`

can be defined by instantiating `Traversable`

and only implementing `traverse`

:

`module TraversableSequence (T : TRAVERSABLE ) = struct`

let sequence xs = T.traverse id xs

end;;

The Haskell documentation for `Applicative`

also dictates a set of laws:

-- Naturality

t . traverse f = traverse (t . f)

-- Identity

traverse Identity = Identity

-- Composition

traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

The *naturality law* assumes that `t`

is a *natural transformation* from one applicative functor to another. Porting it to OCaml requires a couple of further tricks. First we dedicate a specific module functor for the task which takes two arguments for the applicatives mapped between, along with a traversable constructor. In order to also connect the types, an additional module `TYPE2`

representing types of kind `(* -> *)`

is introduced:

`module type TYPE2 = sig type 'a t end;;`

module TestTraversableNat (T2 : TYPE2)

(A1 : APPLICATIVE)

(A2 : APPLICATIVE)

(MT : functor (A : APPLICATIVE) ->

TRAVERSABLE with

type 'a Applicative.t = 'a A.t

and type 'a t = 'a T2.t ) =

struct

module T1 : TRAVERSABLE with

type 'a Applicative.t = 'a A1.t and type 'a t = 'a T2.t = MT (A1)

module T2 : TRAVERSABLE with

type 'a Applicative.t = 'a A2.t and type 'a t = 'a T2.t = MT (A2)

type nat = { t : 'a. 'a A1.t -> 'a A2.t }

let test f {t} x = t (T1.traverse f x) = T2.traverse ( f >> t) x

end;;

Here, `nat`

represents the mapping from `A1`

to `A2`

and the type is introduced in order to be able to express that the transformation is existentially quantified over all type parameters to `A1.t`

.

Here's an example of a concrete realization of a test module:

`module TTN =`

TestTraversableNat (struct type 'a t = 'a list end)

(IdApplicative)

(OptionApplicative)

(ListTraversable);;

end;;

The second law, *identity*, is expressed in terms of the type `Identity`

and its functor and applicative instances in Haskell. `Identity`

in haskell is defined as:

newtype Identity a = Identity a

instance Functor Identity where

fmap f (Identity x) = Identity (f x)

instance Applicative Identity where

pure = Identity

(Identity f) <*> (Identity x) = Identity (f x)

We've already seen its corresponding OCaml type `'a id`

and the applicative instance, `IdApplicative`

. Using that we may create another test module for the *identity* law:

`module TestTraversableId ( MT : functor (A : APPLICATIVE) ->`

TRAVERSABLE with type 'a Applicative.t = 'a A.t) =

struct

module TI = MT (IdApplicative)

let test x = TI.traverse id x = x

end;;

The following example shows how it can be used to test the `ListTraversable`

module-functor:

`module TTIL = TestTraversableId (ListTraversable);;`

TTIL.test [1;2;3];;

The final law, *composibility*, relies on the type `Compose`

which takes two higher-kinded type arguments and composes them:

newtype Compose f g a = Compose (f (g a))

Its functor and applicative functor instances are achieved by:

instance (Functor f, Functor g) => Functor (Compose f g) where

fmap f (Compose x) = Compose (fmap (fmap f) x)

instance (Applicative f, Applicative g) => Applicative (Compose f g) where

pure x = Compose (pure (pure x))

Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

Once again to circumvent the higher-kinded type restriction we need to resort to modules in OCaml. The following module-functor takes two applicatives as arguments and produces an `APPLICATIVE`

module for the composed type:

`module ComposeApplicative (F : APPLICATIVE)`

(G : APPLICATIVE)

: APPLICATIVE with type 'a t = ('a G.t) F.t =

struct

type 'a t = ('a G.t) F.t

let pure x = F.pure (G.pure x)

let map f = F.map (G.map f)

let apply f x =

let module FU = ApplicativeUtils(F) in let open FU in

(G.apply) <$> f <*> x

end;;

Finally tackling the law expressed using the `Compose`

type:

traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

requires some even heavier plumbing. To demonstrate that it's possible, here's an implementation:

`module TestTraversableCompose (T2 : TYPE2)`

(F : APPLICATIVE)

(G : APPLICATIVE)

(MT : functor (A : APPLICATIVE) ->

TRAVERSABLE with type 'a Applicative.t = 'a A.t

and type 'a t = 'a T2.t) =

struct

module AC : APPLICATIVE with

type 'a t = 'a G.t F.t = ComposeApplicative(F) (G)

module TF : TRAVERSABLE with

type 'a Applicative.t = 'a F.t

and type 'a t = 'a T2.t = MT (F)

module TG : TRAVERSABLE with

type 'a Applicative.t = 'a G.t

and type 'a t = 'a T2.t = MT (G)

module TC : TRAVERSABLE with

type 'a Applicative.t = 'a G.t F.t

and type 'a t = 'a T2.t = MT (AC)

let test f g x =

F.map (TG.traverse g) (TF.traverse f x) = TC.traverse (f >> F.map g) x

end;;

It can be used for testing various combinations of traversables and applicatives. For example:

`module TTCL = TestTraversableCompose (struct type 'a t = 'a list end)`

(ListApplicative)

(OptionApplicative)

(ListTraversable);;

TTCL.test (fun x -> [x; x + 1])

(fun x -> if x > 10 then Some (-x) else None)

[1;2;3;5];;

## Using the patterns

Now that we've laid the ground and introduced formalized interfaces for some common patterns, the next sections provide a couple of more examples of how these idioms can be used in practice when designing libraries and programs.

### A minimal parsing library

In the following example we implement a simple parsing library and see how monoids and applicative functors guide the design of the API.

First consider a suitable definition of a parser type:

`type 'a p = char list -> ('a * char list) option;;`

A parser `'a p`

is a function from a list of characters (input) to an option of a tuple of a value of type `'a`

, produced by the parser along with the remaining tokens of the input. The type is similar in spirit to parsing combinator libraries such as Haskell's Parsec.

To be able to define parsers that parses a single character, here's a function that takes a mapping function from a character to an optional value and returns a parser that, when successful, produces a value and consumes one element of the input:

`let token f = function`

| [] -> None

| x :: xs -> OptionFunctor.map (fun y -> (y, xs)) @@ f x

;;

It can be used to implement a specialized version `char`

for matching characters:

`let char c = token (fun c' -> if c = c' then Some c else None);;`

Another useful parser is the one matching an empty list of input:

`let empty = function`

| [] -> Some ((), [])

| _ -> None

;;

In order to compose parsers, either by sequencing them - one parser followed by another, or choosing between multiple parsers, we need to come up with a set of suitable combinators.

Rather than trying to derive such functions directly one can start by looking at existing patterns and identify the ones applicable to parsers.

Doing that requires little thinking besides coming up with feasible implementations and ensuring that the implementation is compliant with the corresponding set of constraints (laws).

For instance, with the parser definition above, we are able to to define an applicative functor interface:

`module ParserApplicative : APPLICATIVE with type 'a t = 'a p = struct`

type 'a t = 'a p

let map f p = p >> OptionFunctor.map (fun (x, cs) -> (f x, cs))

let pure x cs = Some (x, cs)

let apply f x cs =

match f cs with

| Some (f, cs) -> map f x cs

| None -> None

end;;

To convince ourselves that the implementation is sound we can use equational reasoning to prove the laws explicitly. Relying on the `TestApplicative`

module in this case is problematic since it requires comparing for equality and our parser type is a function. A better implementation of the test modules would also allow parameterization of a comparator module.

The `ParserApplicative`

module grants us access to the functions `( <*> )`

and `( <$> )`

for composing parsers of different types:

`module APU = ApplicativeUtils (ParserApplicative);;`

To give an example, here is a parser that parses the input `['a';'b';'c']`

and produces a unit result:

`open APU;;`

let abc = (fun _ _ _ -> ()) <$> char 'a' <*> char 'b' <*> char 'c';;

In order to represent grammars that allow alternative parsing constructs, we need a way to choose between a set of potential parsers. That is, collapsing a set of parsers into a single parser. Phrased differently, we are looking for a monoid:

`module ParserMonoid (T : TYPE) : MONOID with type t = T.t p = struct`

type t = T.t p

let empty _ = None

let append p q cs =

match p cs with

| Some x -> Some x

| None -> q cs

end;;

Here,

`empty`

is the parser that always fails and `append`

takes two parsers and returns a parser that for any input first attempts to run the first parser and in case it fails resorts to the second one. We can now use the `ParserMonoid`

to define a few utility functions:

`let fail (type a) =`

let module M = ParserMonoid(struct type t = a end) in

M.empty

;;

let choose (type a) ps =

let module MU = MonoidUtils (ParserMonoid(struct type t = a end)) in

MU.concat ps

;;

let ( <|> ) p q = choose [p; q];;

The functor, applicative functor and a monoid combinators for the parser type, form the baseline of the API. They are also sufficient for implementing a function for turning any parser into one that applies the parser recursively and collects the results in a list:

`open APU;;`

let delay f cs = f () cs;;

let rec many p =

List.cons <$> p <*> (delay @@ fun _ -> many p)

<|>

pure []

;;

The purpose of the function `delay`

is to avoid infinite recursion by allowing to construct parsers lazily (ones that are only realized on demand).

The definition of `many`

states that it is a parser that either parses one result of the given parser `p`

followed by many results; Or in case it fails, consumes no input and returns an empty list (`pure []`

).

Another handy combinator is `filter`

that takes a predicate function for *filtering* a parser by only allowing it to succeed when its result satisfies the predicate:

`let filter f p cs =`

match p cs with

| Some (x, cs) when f x -> Some (x,cs)

| _ -> None

;;

We can use it to define a variation of `many`

for parsing one or more elements:

`let many_one p = filter ((<>) []) @@ many p;;`

When it comes to actually exposing the API for a parser combinator library we may still choose to shield users from any references to modules such as `ParserApplicative`

or `ParserMonoid`

and also include a sub-set of the derived utility functions.

Here is an example of such a module signature:

`module type PARSER = sig`

type 'a t

val empty : unit t

val run : 'a t -> string -> 'a option

val map : ('a -> 'b) -> 'a t -> 'b t

val pure : 'a -> 'a t

val apply : ('a -> 'b) t -> 'a t -> 'b t

val ( <$> ) : ('a -> 'b) -> 'a t -> 'b t

val ( <*> ) : ('a -> 'b) t -> 'a t -> 'b t

val ( <* ) : 'a t -> 'b t -> 'a t

val ( *> ) : 'a t -> 'b t -> 'b t

val token : (char -> 'a option) -> 'a t

val char : char -> char t

val fail : 'a t

val choose : 'a t list -> 'a t

val ( <|> ) : 'a t -> 'a t -> 'a t

val many : 'a t -> 'a list t

val many_one : 'a t -> 'a list t

val filter : ('a -> bool) -> 'a t -> 'a t

end;;

Note that it also makes the parser type itself abstract and instead exposes a run function that takes a string as input rather than a list of characters. To turn a string into a list of characters, access to a function such as:

`let list_of_string s =`

let rec aux i l = if i < 0 then l else aux (i - 1) (s.[i] :: l) in

aux (String.length s - 1) []

;;

is assumed.

The following implementation realizes the signature using the `ParserMonoid`

and applicative utils (`APU`

) as defined above:

`module Parser : PARSER = struct`

include APU

let run p s = OptionFunctor.map fst @@ p @@ list_of_string s

let empty = function

| [] -> Some ((), [])

| _ -> None

let token f = function

| [] -> None

| x :: xs -> OptionFunctor.map (fun y -> (y, xs)) @@ f x

let char c = token (fun c' -> if c = c' then Some c else None)

let fail (type a) =

let module M = ParserMonoid(struct type t = a end) in

M.empty

let choose (type a) ps =

let module MU = MonoidUtils(ParserMonoid(struct type t = a end)) in

MU.concat ps

let ( <|> ) p q = choose [p; q]

let delay f cs = f () cs

let rec many p =

List.cons <$> p <*> (delay @@ fun _ -> many p)

<|>

pure []

let filter f p cs =

match p cs with

| Some (x, cs) when f x -> Some (x,cs)

| _ -> None

let many_one p = filter ((<>) []) @@ many p

end;;

Finally for an example of how to use the library, consider a parser for parsing dates of the format `YYYY-MM-DD`

:

`open Parser;;`

(* Parser for a single digit *)

let digit = "0123456789" |> list_of_string |> List.map char |> choose;;

(* Integer parser *)

let int =

let string_of_list = List.map (String.make 1) >> String.concat "" in

(string_of_list >> int_of_string) <$> many_one digit;;

(* Integers in a given range *)

let int_range mn mx = filter (fun n -> mn <= n && n <= mx) int;;

(* Parser for digit prefixed by '0'. Ex "07" *)

let zero_digit = char '0' *> int_range 1 9;;

(* Years between 1700 and 2400 *)

let year = int_range 1700 2400;;

(* Month as in '01, 02, .. , 11' *)

let month = zero_digit <|> int_range 11 12;;

(* Day as in '01, 02, .. 31 *)

let day = zero_digit <|> int_range 11 31;;

(* Parser for date of format "YYYY-MM-DD" *)

let date =

(fun y m d -> (y,m,d))

<$> (year <* char '-')

<*> (month <* char '-')

<*> day

;;

Here are a few examples of running the `date`

parser with different string inputs:

`# run date "2019-01-23";;`

- : (int * int * int) option = Some (2019, 1, 23)

# run date "2019-1-23";;

- : (int * int * int) option = None

# run date "999-1-23";;

- : (int * int * int) option = None

### Analyzing boolean expressions

In the next example we consider designing a library for representing and operating on boolean expressions. It naturally generalizes to other forms of deeply embedded domain specific languages (EDSLs).

Consider the following data type for representing a boolean expression with variables, parameterized over the variable type.

`type 'a exp =`

| True

| False

| And of 'a exp * 'a exp

| Or of 'a exp * 'a exp

| Not of 'a exp

| Var of 'a

;;

For convenience we define some helper functions corresponding to the expression constructors:

`let etrue = True;;`

let efalse = False;;

let ( <&> ) e1 e2 = And (e1, e2);;

let ( <|> ) e1 e2 = Or (e1, e2);;

let enot e = Not e;;

let var x = Var x;;

What patterns are applicable to the `'a exp`

type? There are two monoid instances corresponding to the boolean operators `and`

and `or`

. Expressions form a monoid with identity `false`

and the append function `or`

:

`module MonoidOrFalse (T : TYPE) : MONOID with type t = T.t exp = struct`

type t = T.t exp

let empty = efalse and append = ( <|> )

end;;

The other monoid is for `true`

and `and`

:

`module MonoidAndTrue (T : TYPE) : MONOID with type t = T.t exp = struct`

type t = T.t exp

let empty = etrue and append = ( <&> )

end;;

As demonstrated previously, monoids can be promoted to operate on lists. In this case for composing a list of expression values:

`let any (type a) es =`

let module M = MonoidUtils (MonoidOrFalse (struct type t = a end)) in

M.concat es;;

let all (type a) es =

let module M = MonoidUtils (MonoidAndTrue (struct type t = a end)) in

M.concat es;;

Continuing through the list of patterns - the expression type naturally forms a traversable:

`module ExpTraversable (A : APPLICATIVE) :`

TRAVERSABLE with type 'a t = 'a exp

and type 'a Applicative.t = 'a A.t =

struct

module Applicative = A

type 'a a = 'a A.t

type 'a t = 'a exp

let rec traverse f exp =

let module AU = ApplicativeUtils(A) in

let open AU in

match exp with

| True -> A.pure etrue

| False -> A.pure efalse

| And (e1, e2) -> (<&>) <$> traverse f e1 <*> traverse f e2

| Or (e1, e2) -> (<|>) <$> traverse f e1 <*> traverse f e2

| Not e -> enot <$> traverse f e

| Var v -> var <$> f v

end;;

Using this module we also obtain the functor instance for free and are able to implement a map function for expressions via:

`module EF = TraversableFunctor (ExpTraversable);;`

let map f = EF.map f;;

For example we may use `map`

to create a function that adds a prefix to each variable for values of type `string exp`

:

`let add_var_prefix p = map (Printf.sprintf "%s%s" p);;`

The traversable instance may also be utilized when it comes to evaluating expressions. First consider the following function for evaluating expressions parameterized by a boolean value, that is expressions where each variable is realized as concrete boolean value: `let rec eval_bool_exp = function`

| True -> true

| False -> false

| And (e1, e2) -> eval_bool_exp e1 && eval_bool_exp e2

| Or (e1, e2) -> eval_bool_exp e1 || eval_bool_exp e2

| Not e -> not (eval_bool_exp e)

| Var x -> x

;;

In order to write a more generic version that evaluates expressions parameterized by an arbitrary type we need to pass an environment for mapping variables to boolean values. The task can be solved by considering the traversable instance for expressions where the effect is given by the option applicative, and then map over the result and evaluate with `eval_bool_exp`

:

`let eval env =`

let module T = ExpTraversable (OptionApplicative) in

T.traverse env >> OptionFunctor.map eval_bool_exp

;;

To test, assume an environment with two variables (`x`

and `y`

):

`let env = function`

| "x" -> Some true

| "y" -> Some false

| _ -> None

;;

Here are a couple of examples of evaluation expressions using the environment:

`# eval env (var "x" <|> enot (var "y" <&> var "y"));;`

- : bool OptionFunctor.t = Some true

# eval env (var "z" <|> enot (var "y" <&> var "y"));;

- : bool OptionFunctor.t = None

Next, say we're asked to write a function that extracts all variables from an expression. Could we leverage the traversable instance for this task as well?

At a first glance this may seem like a stretch as traverse maps over an expression and rebuilds it. This time we're only interested in collecting the variables traversed over. The trick is to pick an appropriate applicative instance; In this case where the effect is accumulating the results. Following is a module-functor, for creating an applicative functor that accumulates results of some type in a list:

`module BagApplicative (T : TYPE) : APPLICATIVE with type 'a t = T.t list =`

struct

type 'a t = T.t list

let pure _ = []

let map _ x = x

let apply f = (@) f

end;;

Note that the type parameter `'a`

in `'a t`

is not actually used and its only purpose is to satisfy the signature of `APPLICATIVE`

. The function `pure`

creates an empty list ignoring its argument. `map`

is effectively a no-op and `apply`

simply concatenates the results of both arguments (which are both lists of accumulated items).

With `BagApplicative`

at our disposal, extracting the variables is a matter of traversing an expression and for each variable encountered putting it in the bag:

`let variables (type a) exp =`

let module T = ExpTraversable (BagApplicative (struct type t = a end)) in

T.traverse ListApplicative.pure exp

;;

This works for any expression type as the explicit type parameter `a`

is used to instantiate the `BagApplicative`

module-functor. The purpose of `ListApplicative.pure`

is to wrap a variable in a singleton list, synonymous with `fun x -> [x]`

.

Here's an example of using it to collect variables of a `string exp`

:

`# variables (var "x" <|> (var "y" <&> (enot (var "z"))));;`

- : string list = ["x"; "y"; "z"]

Let's take a look at yet another exercise for where traversables prove to be useful. Say we wish to expand an expression with variables into all possible realizations. For example, the expression `var "x" <|> (var "y" <&> (enot (var "z")))`

contains three variables so there are *2 ^{3}* different realizations corresponding to each permutation of

`true/false`

assignments to `x`

, `y`

and `z`

. Every one of them gives rise to an expression where the variable is replaced with a boolean value. The `variables`

function above already allows us to extract the list but how can we generate all permutations?

For traversing a list (in this case of variables, we may use `ListTraversable`

. Since each variable yields two possible values (variable and bool pair) we can collect them using the `ListApplicative`

:

`module LTLA = ListTraversable (ListApplicative);;`

The module `LTLA`

now contains a traverse function:

`val traverse : ('a -> 'b list) -> 'a list -> 'a list list`

Given that

`ListApplicative`

corresponds to the Cartesian product, the effect of `traverse`

is to generate all permutations. For instance:

`# LTLA.traverse (fun x -> ['a']) [1;2;3];;`

-: char LTLA.t LTLA.Applicative.t = [['a'; 'a'; 'a']]

Here, each value

*1*,

*2*and

*3*, can replaced with exactly one value

`a`

producing a list with a single permutation. Allowing each number to be mapped to two possible values yields *8* results:

`# LTLA.traverse (fun _ -> ['a'; 'b']) [1;2;3];;`

- : char LTLA.t LTLA.Applicative.t =

[['a'; 'a'; 'a']; ['a'; 'a'; 'b']; ['a'; 'b'; 'a']; ['a'; 'b'; 'b'];

['b'; 'a'; 'a']; ['b'; 'a'; 'b']; ['b'; 'b'; 'a']; ['b'; 'b'; 'b']]

In our case we're interested in mapping the unique set of collected variables to the values `true`

or `false`

for which each resulting permutation yields a lookup function. The function `realizations`

below also maps over the lookup function to replace the variables with their corresponding boolean values for the given expression:

`let realizations exp =`

variables exp

|> LTLA.traverse (fun x -> [(x,true); (x,false)])

|> ListFunctor.map (fun xs -> map (fun x -> List.assoc x xs) exp)

;;

Here's an example of using it: `# realizations (var "x" <|> (var "y" <&> (enot (var "z"))));;`

returning the following result:

`[`

Or (Var true, And (Var true, Not (Var true)));

Or (Var true, And (Var true, Not (Var false)));

Or (Var true, And (Var false, Not (Var true)));

Or (Var true, And (Var false, Not (Var false)));

Or (Var false, And (Var true, Not (Var true)));

Or (Var false, And (Var true, Not (Var false)));

Or (Var false, And (Var false, Not (Var true)));

Or (Var false, And (Var false, Not (Var false)))

]

To see why such a function may be useful, consider how it can be used for evaluating all expanded versions of an expression in order to deduce whether or not an expression always evaluates to true or false, irrespective of the choice of variables:

`let always_true exp =`

realizations exp

|> all

|> eval_bool_exp

;;

let always_false exp =

realizations exp

|> any

|> eval_bool_exp

|> not

;;

At last, a few examples to demonstrate their behavior:

`# always_true (var "x");;`

- : bool = false

# always_true (var "x" <|> etrue);;

- : bool = true

# always_true (var "x" <|> (enot (var "x")));;

- : bool = true

# always_false (var "x");;

- : bool = false

# always_false (var "x" <&> (enot (var "x")));;

- : bool = true

## Summary

Many Haskell patterns implemented in terms of type classes may indeed be ported to OCaml. As demonstrated by the introduction of functor, monoid, applicative functor and traversable module signatures, and the examples, there is a case to be made for why leveraging patterns can help with guiding the specification of APIs and enable code reuse.

On a more philosophical level - thinking in terms of patterns changes the methodology of writing programs. Under this regime, rather than solving isolated problems one starts by implementing generic functionality and later focus on how to make use of it for addressing more specific problems.

In the parser example we saw how two patterns, monoid and applicative functor, were sufficient for describing the primitive set of base combinators (`(<|>`

, `<*>`

etc), out of which others could be inferred (e.g. `many`

and `many_one`

).

In the example for representing and operating on boolean expressions, defining a traversable instance formed the cornerstone from which a variety of functionality was derived, including:

- Mapping over expression
- Evaluating expressions
- Collecting variables from expressions

*effect*of

`traverse`

by varying the applicative functor argument. Hide# Weekly News — OCaml Weekly News, May 16, 2017

- Transforming side-effects to a monad
- Clarity - functional programming library for OCaml
- PPX is harmful to our community in the long term
- discuss.ocaml.org now available
- Snabela 1.0: Logic-less @templates@
- Human-friendly Lwt: documenting and refactoring the Lwt core
- OCaml workshop 2017: call for presentations
- Ocaml Github Pull Requests
- Other OCaml News

# Proving a mem/map property — Shayne Fletcher, May 11, 2017

Here are two well known "classic" functions over polymorphic lists.

`map f l`

computes a new list from `l`

by applying `f`

to each of its elements.

`let rec map (f : 'a -> 'b) : 'a list -> 'b list = function`

| [] -> []

| h :: t -> f h :: map f t

;;

`mem x l`

returns `true`

is `x`

is an element of `l`

and returns `false`

if it is not.

`let rec mem (a : 'a) : 'a list -> bool = function`

| [] -> false

…

Read more...Here are two well known "classic" functions over polymorphic lists.

`map f l`

computes a new list from `l`

by applying `f`

to each of its elements.

`let rec map (f : 'a -> 'b) : 'a list -> 'b list = function`

| [] -> []

| h :: t -> f h :: map f t

;;

`mem x l`

returns `true`

is `x`

is an element of `l`

and returns `false`

if it is not.

`let rec mem (a : 'a) : 'a list -> bool = function`

| [] -> false

| x :: l -> a = x || mem a l

;;

If `y`

is an element of the list obtained by mapping `f`

over `l`

then there must be an element `x`

in `l`

such that `f x = y`

. Conversely, if there exists an `x`

in `l`

such that `y = f x`

, then `y`

must be a member of the list obtained by mapping `f`

over `l`

.

We attempt a proof of correctness of the given definitions with respect to this property.

**Lemma**

`mem_map_iff`

:

∀ (f : α → β) (l : α list) (y : β),

mem y (map f l) ⇔ ∃(x : α), f x = y ∧ mem x l.

**Proof:**

- We first treat the forward implication

and proceed by induction on

∀ (f : α → β) (l : α list) (y : β),

mem y (map f l) ⇒ ∃(x : α), f x = y ∧ mem x l

`l`

.

`l = []`

:- Show
`mem y (map f []) ⇒ ∃(x : α), f x = y ∧ mem x []`

. `mem y (map f []) ≡ False`

.- Proof follows
*(ex falso quodlibet)*.

- Show
`l`

has form`x' :: l`

(use`l`

now to refer to the tail):- Assume the induction hypothesis:
`mem y (map f l) ⇒ ∃x, f x = y ∧ mem x l`

.

- We are required to show for an arbitrary
`(x' : α)`

:`mem y (map f (x' :: l)) ⇒ ∃(x : α), f x = y ∧ mem x (x' :: l)`

.

- By simplification, we can rewrite the above to:
`f x' = y ∨ mem y (map f l) ⇒ ∃(x : α), f x = y ∧ (x' = x ∨ mem x l).`

- We assume then an
`(x' : α)`

and a`(y : β)`

such that:`f x' = y ∨ mem y (map f l)`

.`mem y (map f l) ⇒ ∃(x : α), f x = y ∧ mem x l`

.

- Show
`∃(x : α), f x = y ∧ (x' = x ∨ mem x l)`

:- First consider
`f x' = y`

in (1).- Take
`x = x'`

in the goal. - Then by (1)
`f x = y ∧ x = x'`

. - So
`x'`

is a witness.

- Take
- Now consider
`mem y (map f l)`

in (1).`∃(x`

by (2).^{*}: α), f x^{*}= y ∧ mem x^{*}l- Take
`x = x`

in the goal.^{*} - By the above
`f x`

^{*}= y ∧ mem x^{*}l - So
`x`

is a witness.^{*}

- First consider

- Assume the induction hypothesis:

- We now work on the reverse implication. We want to show that

and proceed by induction on

∀ (f : α → β) (l : α list) (y : β),

∃(x : α), f x = y ∧ mem x l ⇒ mem y (map f l)

`l`

.

`l = []`

:- Assume
`x`

,`y`

with`f x = y ∧ mem x []`

. - Show
`mem y (map f [])`

: `mem x [] ≡ false`

.- Proof follows
*(ex falso quodlibet)*.

- Assume
`l`

has form`x' :: l`

(use`l`

now to refer to the tail):- Assume the induction hypothesis:
`∃(x : α), f x = y ∧ mem x l ⇒ mem y (map f l)`

.

- We are required to show for an arbitrary
`(x' : α)`

:`∃ (x : α), f x = y ∧ mem x (x' :: l) ⇒ mem y (map f (x' :: l))`

- By simplification, we can rewrite the above to:
`∃ (x : α), f x = y ∧ x = x' ∨ mem x l ⇒ f x' = y ∨ mem y (map f l)`

.

- Assume the goal and induction hypotheses:
- There is
`(x : α)`

and`(y : β)`

such that:`f x = y ∧ (x = x' ∨ mem x l)`

`f x = y ∧ mem x l ⇒ mem y (map f l)`

- There is
- Show
`f x' = y ∨ mem y (map f l)`

:- Assume
`x = x'`

in (1) and show`f x' = y`

:- Since,
`f x = y`

is given by (1.),`f x' = y`

.

- Since,
- Assume
`mem x l`

in (1) and show`mem y (map f l)`

:- Rewrite
`mem y (map f l)`

via (2) to`f x = y ∧ mem x l`

. `f x = y`

by (1) so`mem y (map f l)`

.

- Rewrite

- Assume

- Assume the induction hypothesis:

References:

"Sofware Foundations" -- Pierce et. al.

# New opam features: more expressive dependencies — OCamlPro, May 11, 2017

This blog will cover yet another aspect of the improvements opam 2.0 has over opam 1.2. It may be a little more technical than previous issues, as it covers a feature directed specifically at packagers and repository maintainers, and regarding the package definition format.

### Specifying dependencies in opam 1.2

Opam 1.2 already has an advanced way of specifying package dependencies, using formulas on packages and versions, with the following syntax:

depends: [ "foo" {>= "3.0&q…Read more...

This blog will cover yet another aspect of the improvements opam 2.0 has over opam 1.2. It may be a little more technical than previous issues, as it covers a feature directed specifically at packagers and repository maintainers, and regarding the package definition format.

### Specifying dependencies in opam 1.2

Opam 1.2 already has an advanced way of specifying package dependencies, using formulas on packages and versions, with the following syntax:

depends: [ "foo" {>= "3.0" & < "4.0~"} ( "bar" | "baz" {>= "1.0"} ) ]

meaning that the package being defined depends on both package `foo`

, within the `3.x`

series, and one of `bar`

or `baz`

, the latter with version at least `1.0`

. See here for a complete documentation.

This only allows, however, dependencies that are static for a given package.

Opam 1.2 introduced `build`

, `test`

and `doc`

“dependency flags” that could provide some specifics for dependencies (*e.g.* `test`

dependencies would only be needed when tests were requested for the package). These were constrained to appear before the version constraints, *e.g.* `"foo" {build & doc & >= "3.0"}`

.

### Extensions in opam 2.0

Opam 2.0 generalises the dependency flags, and makes the dependencies specification more expressive by allowing to mix *filters*, *i.e.* formulas based on opam variables, with the version constraints. If that formula holds, the dependency is enforced, if not, it is discarded.

This is documented in more detail in the opam 2.0 manual.

Note also that, since the compilers are now packages, the required OCaml version is now expressed using this mechanism as well, through a dependency to the (virtual) package `ocaml`

, *e.g.* `depends: [ "ocaml" {>= "4.03.0"} ]`

. This replaces uses of the `available:`

field and `ocaml-version`

switch variable.

#### Conditional dependencies

This makes it trivial to add, for example, a condition on the OS to a given dependency, using the built-in variable `os`

:

depends: [ "foo" {>= "3.0" & < "4.0~" & os = "linux"} ]

here, `foo`

is simply not needed if the OS isn't Linux. We could also be more specific about other OSes using more complex formulas:

depends: [ "foo" { "1.0+linux" & os = "linux" | "1.0+osx" & os = "darwin" } "bar" { os != "osx" & os != "darwin" } ]

Meaning that Linux and OSX require `foo`

, respectively versions `1.0+linux`

and `1.0+osx`

, while other systems require `bar`

, any version.

#### Dependency flags

Dependency flags, as used in 1.2, are no longer needed, and are replaced by variables that can appear anywhere in the version specification. The following variables are typically useful there:

`with-test`

,`with-doc`

: replace the`test`

and`doc`

dependency flags, and are`true`

when the package's tests or documentation have been requested- likewise,
`build`

behaves similarly as before, limiting the dependency to a “build-dependency”, implying that the package won't need to be rebuilt if the dependency changes `dev`

: this boolean variable holds`true`

on “development” packages, that is, packages that are bound to a non-stable source (a version control system, or if the package is pinned to an archive without known checksum).`dev`

sources often happen to need an additional preliminary step (e.g.`autoconf`

), which may have its own dependencies.

Use `opam config list`

for a list of pre-defined variables. Note that the `with-test`

, `with-doc`

and `build`

variables are not available everywhere: the first two are allowed only in the `depends:`

, `depopts:`

, `build:`

and `install:`

fields, and the latter is specific to the `depends:`

and `depopts:`

fields.

For example, the `datakit.0.9.0`

package has:

depends: [ ... "datakit-server" {>= "0.9.0"} "datakit-client" {with-test & >= "0.9.0"} "datakit-github" {with-test & >= "0.9.0"} "alcotest" {with-test & >= "0.7.0"} ]

When running `opam install datakit.0.9.0`

, the `with-test`

variable is set to `false`

, and the `datakit-client`

, `datakit-github`

and `alcotest`

dependencies are filtered out: they won't be required. With `opam install datakit.0.9.0 --with-test`

, the `with-test`

variable is true (for that package only, tests on packages not listed on the command-line are not enabled!). In this case, the dependencies resolve to:

depends: [ ... "datakit-server" {>= "0.9.0"} "datakit-client" {>= "0.9.0"} "datakit-github" {>= "0.9.0"} "alcotest" {>= "0.7.0"} ]

which is treated normally.

#### Computed versions

It is also possible to use variables, not only as conditions, but to compute the version values: `"foo" {= var}`

is allowed and will require the version of package `foo`

corresponding to the value of variable `var`

.

This is useful, for example, to define a family of packages, which are released together with the same version number: instead of having to update the dependencies of each package to match the common version at each release, you can leverage the `version`

package-variable to mean “that other package, at the same version as current package”. For example, `foo-client`

could have the following:

depends: [ "foo-core" {= version} ]

It is even possible to use variable interpolations within versions, *e.g.* specifying an os-specific version differently than above:

depends: [ "foo" {= "1.0+%{os}%"} ]

this will expand the `os`

variable, resolving to `1.0+linux`

, `1.0+darwin`

, etc.

Getting back to our `datakit`

example, we could leverage this and rewrite it to the more generic:

depends: [ ... "datakit-server" {>= version} "datakit-client" {with-test & >= version} "datakit-github" {with-test & >= version} "alcotest" {with-test & >= "0.7.0"} ]

Since the `datakit-*`

packages follow the same versioning, this avoids having to rewrite the opam file on every new version, with a risk of error each time.

As a side note, these variables are consistent with what is now used in the `build:`

field, and the `build-test:`

field is now deprecated. So this other part of the same `datakit`

opam file:

build: ["ocaml" "pkg/pkg.ml" "build" "--pinned" "%{pinned}%" "--tests" "false"] build-test: [ ["ocaml" "pkg/pkg.ml" "build" "--pinned" "%{pinned}%" "--tests" "true"] ["ocaml" "pkg/pkg.ml" "test"] ]

would now be preferably written as:

build: ["ocaml" "pkg/pkg.ml" "build" "--pinned" "%{pinned}%" "--tests" "%{with-test}%"] run-test: ["ocaml" "pkg/pkg.ml" "test"]

which avoids building twice just to change the options.

#### Conclusion

Hopefully this extension to expressivity in dependencies will make the life of packagers easier; feedback is welcome on your personal use-cases.

Note that the official repository is still in 1.2 format (served as 2.0 at `https://opam.ocaml.org/2.0`

, through automatic conversion), and will only be migrated a little while after opam 2.0 is finally released. You are welcome to experiment on custom repositories or pinned packages already, but will need a little more patience before you can contribute package definitions making use of the above to the official repository.

HideNOTE: this article is cross-posted on opam.ocaml.org and ocamlpro.com. Please head to the latter for the comments!

# Weekly News — OCaml Weekly News, May 09, 2017

# Preprocessor extensions for code generation — Shayne Fletcher, May 04, 2017

## Preprocessor extensions for code generation

"A Guide to Extension Points in OCaml"[1] provides a great "quick-start" on using the OCaml extension points API to implement preprocessor extensions for abstract syntax tree rewrites. This post picks up where that tutorial leaves off by showing how to write a ppx that does code generation.

The problem treated here is one posed in Whitequark's blog : "Implement a syntax extension that would accept type declarations of …

Read more...## Preprocessor extensions for code generation

"A Guide to Extension Points in OCaml"[1] provides a great "quick-start" on using the OCaml extension points API to implement preprocessor extensions for abstract syntax tree rewrites. This post picks up where that tutorial leaves off by showing how to write a ppx that does code generation.

The problem treated here is one posed in Whitequark's blog : "Implement a syntax extension that would accept type declarations of the form `type t = A [@id 1] | B of int [@id 4] [@@id_of]`

to generate a function mapping a value of type `t`

to its integer representation."

## Implementing the "`id_of`

" ppx

### The basic strategy

In the OCaml parse tree, structures are lists of structure items. Type declarations are structure items as are let-bindings to functions.

In this program, analysis of an inductive type declaration `t`

may result in the production of a new structure item, the AST of an `of_id`

function to be appended to the structure containing `t`

.

Now the general strategy in writing a ppx is to provide a record of type `Ast_mapper.mapper`

. That record is based on the `Ast_mapper.default_mapper`

record but selectively overriding those fields for those sytactic categories that the ppx is intending to transform.

Now, as we determined above, the effect of the ppx is to provide a function from a structure to a new structure. Accordingly, at a minimum then we'll want to override the `structure`

field of the default mapper. Schematically then our ppx code will take on the following shape.

`open Ast_mapper`

open Ast_helper

open Asttypes

open Parsetree

open Longident

let structure_mapper mapper structure =

...

let id_of_mapper = {

default_mapper with structure = structure_mapper

}

let () = register "id_of" id_of_mapper

This program goes just a little bit further though. Any `@id`

or `@@id_of`

attributes that get as far as the OCaml compiler would be ignored. So, it's not neccessary that they be removed by our ppx once they've been acted upon but it seems tidy to do so. Accordingly, there are two more syntactic constructs that this ppx operates on.

`open Ast_mapper`

open Ast_helper

open Asttypes

open Parsetree

open Longident

let structure_mapper mapper structure =

...

let type_declaration_mapper mapper decl =

...

let constructor_declaration_mapper mapper decl =

...

let id_of_mapper argv = {

default_mapper with

structure = structure_mapper;

type_declaration = type_declaration_mapper;

constructor_declaration = constructor_declaration_mapper

}

### Implementing the mappings

To warm up, lets start with the easy mappers.

The role of `type_declaration_mapper`

is a function from a `type_declaration`

argument to a `type_declaration`

result that is the argument in all but that any `@@id_of`

attribute has been removed.

`let type_declaration_mapper`

(mapper : mapper)

(decl : type_declaration) : type_declaration =

match decl with

(*Case of an inductive type "t"*)

| {ptype_name = {txt = "t"; _};

ptype_kind = Ptype_variant constructor_declarations;

ptype_attributes;_} ->

let (_, attrs) =

List.partition (fun ({txt;_},_) ->txt="id_of") ptype_attributes in

{(default_mapper.type_declaration mapper decl)

with ptype_attributes=attrs}

(*Not an inductive type named "t"*)

| _ -> default_mapper.type_declaration mapper decl

`constructor_declaration_mapper`

is analogous to `type_declaration_mapper`

above but this time its `@id`

attributes that are removed.

`let constructor_declaration_mapper`

(mapper : mapper)

(decl : constructor_declaration) : constructor_declaration =

match decl with

| {pcd_name={loc; _}; pcd_attributes; _} ->

let (_, attrs) =

List.partition (fun ({txt;_}, _) -> txt="id") pcd_attributes in

{(default_mapper.constructor_declaration mapper decl)

with pcd_attributes=attrs}

Now to the raison d'etre of the ppx, `structure_mapper`

.

First, a utility function that computes from a `constructor_declaration`

with an `@id`

attribute, a (function) `case`

for it. For example, suppose "`Bar of int [@id 4]`

" is the constructor declaration, then the `case`

to be computed is the AST corresponding to the code "`| Bar _ -> 4`

".

` let case_of_constructor_declaration :`

constructor_declaration -> case = function

| {pcd_name={txt;loc};pcd_args;pcd_attributes; _} ->

match List.filter (fun ({txt;_}, _) -> txt="id") pcd_attributes with

(*No "@id"*)

| [] ->

raise (Location.Error (Location.error ~loc "[@id] : Missing"))

(*Single "@id"*)

| [(_, payload)] ->

begin match payload with

| PStr [{pstr_desc=Pstr_eval ({pexp_desc=

Pexp_constant (Pconst_integer (id, None)); _}, _)

}] ->

Exp.case

(Pat.construct

{txt=Lident txt; loc=(!default_loc)}

(match pcd_args with

| Pcstr_tuple [] -> None | _ -> Some (Pat.any ())))

(Exp.constant (Pconst_integer (id, None)))

| _ ->

raise (Location.Error (Location.error ~loc

"[@id] : Bad (or missing) argument (should be int e.g. [@id 4])"))

end

(*Many "@id"s*)

| (_ :: _) ->

raise (Location.Error (Location.error ~loc

"[@id] : Multiple occurences"))

One more utility function is required.

`eval_structure_item item acc`

computes structure items to push on the front of `acc`

. If `item`

is a single declaration of an inductive type `t`

attributed with `@@id_of`

, then two structure items will be produced : one for `t`

and one synthesized for `t`

's `of_id`

function. In all other cases, just one structure item will be pushed onto `acc`

.

`let eval_structure_item`

(mapper : mapper)

(item : structure_item)

(acc : structure) : structure =

match item with

(*Case of a single inductive type declaration*)

| { pstr_desc = Pstr_type (_, [type_decl]); pstr_loc} ->

begin

match type_decl with

(*Case where the type identifer is [t]*)

| {ptype_name = {txt = "t"; _};

ptype_kind = Ptype_variant constructor_declarations;

ptype_attributes;

_} ->

begin

match List.filter (fun ({txt;_},_) ->txt="id_of")

ptype_attributes

with

(*No [@@id_of]*)

| [] -> default_mapper.structure_item mapper item :: acc

(*At least one [@@id_of] (treat multiple occurences as if

one)*)

| _ ->

(*Cases of an [id_of] function for [t], one for each

of its constructors*)

let cases=

List.fold_right

(fun x acc ->

case_of_constructor_declaration x :: acc)

constructor_declarations [] in

(*The [id_of] function itself*)

let id_of : structure_item =

Str.value Nonrecursive [

Vb.mk

(Pat.var {txt="id_of"; loc=(!default_loc)})

(Exp.function_ cases)] in

default_mapper.structure_item mapper item :: id_of :: acc

end

(*Case the type identifier is something other than [t]*)

| _ -> default_mapper.structure_item mapper item :: acc

end

(*Case this structure item is something other than a single type

declaration*)

| _ -> default_mapper.structure_item mapper item :: acc

Finally we can write `structure_mapper`

itself as a simple fold over a structure.

`let structure_mapper`

(mapper : mapper)

(structure : structure) : structure =

List.fold_right (eval_structure_item mapper)structure []

### Building and testing

So that's it, this preprocessor extension is complete. Assuming the code is contained in a file called `ppx_id_of.ml`

it can be compiled with a command along the lines of the following.

ocamlc -o ppx_id_of.exe -I +compiler-libs ocamlcommon.cma ppx_id_of.mlWhen built, it can be tested with a command like

` ocamlc -dsource -ppx ppx_id_of.exe test.ml`

. For example, when invoked on the following program,

`type t =`

| A [@id 2]

| B of int [@id 4] [@@id_of]

module M = struct

type t =

| Foo of int [@id 42]

| Bar [@id 43] [@@id_of]

module N = struct

type t =

| Baz [@id 8]

| Quux of string * int [@id 7] [@@id_of]

module Q = struct

type t =

| U [@id 0] [@@id_of]

end

end

end

the resulting output is, `type t =`

| A

| B of int

let id_of = function | A -> 2 | B _ -> 4

module M =

struct

type t =

| Foo of int

| Bar

let id_of = function | Foo _ -> 42 | Bar -> 43

module N =

struct

type t =

| Baz

| Quux of string * int

let id_of = function | Baz -> 8 | Quux _ -> 7

module Q = struct type t =

| U

let id_of = function | U -> 0 end

end

end

References:

[1] "A Guide to Extension Points in OCaml" -- Whitequark (blog post 2014)

# New opam features: “opam install DIR” — OCamlPro, May 04, 2017

After the opam build feature was announced followed a lot of discussions, mainly having to do with its interface, and misleading name. The base features it offered, though, were still widely asked for:

- a way to work directly with the project in the current directory, assuming it contains definitions for one or more packages
- a way to copy the installed files of a package below a specified
`destdir`

- an easier way to get started hacking on a project, even without an initialised opam

### Status of `opam …`

Read more...After the opam build feature was announced followed a lot of discussions, mainly having to do with its interface, and misleading name. The base features it offered, though, were still widely asked for:

- a way to work directly with the project in the current directory, assuming it contains definitions for one or more packages
- a way to copy the installed files of a package below a specified
`destdir`

- an easier way to get started hacking on a project, even without an initialised opam

### Status of `opam build`

`opam build`

, as described in a previous post has been dropped. It will be absent from the next Beta, where the following replaces it.

### Handling a local project

Consistently with what was done with local switches, it was decided, where meaningful, to overload the `<packages>`

arguments of the commands, allowing directory names instead, and meaning “all packages defined there”, with some side-effects.

For example, the following command is now allowed, and I believe it will be extra convenient to many:

opam install . --deps-only

What this does is find `opam`

(or `<pkgname>.opam`

) files in the current directory (`.`

), resolve their installations, and install all required packages. That should be the single step before running the source build by hand.

The following is a little bit more complex:

opam install .

This also retrieves the packages defined at `.`

, **pins them** to the current source (using version-control if present), and installs them. Note that subsequent runs actually synchronise the pinnings, so that packages removed or renamed in the source tree are tracked properly (*i.e.* removed ones are unpinned, new ones pinned, the other ones upgraded as necessary).

`opam upgrade`

, `opam reinstall`

, and `opam remove`

have also been updated to handle directories as arguments, and will work on “all packages pinned to that target”, *i.e.* the packages pinned by the previous call to `opam install <dir>`

. In addition, `opam remove <dir>`

unpins the packages, consistently reverting the converse `install`

operation.

`opam show`

already had a `--file`

option, but has also been extended in the same way, for consistency and convenience.

This all, of course, works well with a local switch at `./`

, but the two features can be used completely independently. Note also that the directory name must be made unambiguous with a possible package name, so make sure to use `./foo`

rather than just `foo`

for a local project in subdirectory `foo`

.

### Specifying a destdir

This relies on installed files tracking, but was actually independent from the other `opam build`

features. It is now simply a new option to `opam install`

:

opam install foo --destdir ~/local/

will install `foo`

normally (if it isn’t installed already) and copy all its installed files, following the same hierarchy, into `~/local`

. `opam remove --destdir`

is also supported, to remove these files.

### Initialising

Automatic initialisation has been dropped for the moment. It was only saving one command (`opam init`

, that opam will kindly print out for you if you forget it), and had two drawbacks:

- some important details (like shell setup for opam) were skipped
- the initialisation options were much reduced, so you would often have to go back to
`opam init`

anyway. The other possibility being to duplicate`init`

options to all commands, adding lots of noise. Keeping things separate has its merits.

Granted, another command, `opam switch create .`

, was made implicit. But using a local switch is a user choice, and worse, in contradiction with the previous de facto opam default, so not creating one automatically seems safer: having to specify `--no-autoinit`

to `opam build`

in order to get the more simple behaviour was inconvenient and error-prone.

One thing is provided to help with initialisation, though: `opam switch create <dir>`

has been improved to handle package definitions at `<dir>`

, and will use them to choose a compatible compiler, as `opam build`

did. This avoids the frustration of creating a switch, then finding out that the package wasn’t compatible with the chosen compiler version, and having to start over with an explicit choice of a different compiler.

If you would really like automatic initialisation, and have a better interface to propose, your feedback is welcome!

### More related options

A few other new options have been added to `opam install`

and related commands, to improve the project-local workflows:

`opam install --keep-build-dir`

is now complemented with`--reuse-build-dir`

, for incremental builds within opam (assuming your build-system supports it correctly). At the moment, you should specify both on every upgrade of the concerned packages, or you could set the`OPAMKEEPBUILDDIR`

and`OPAMREUSEBUILDDIR`

environment variables.`opam install --inplace-build`

runs the scripts directly within the source dir instead of a dedicated copy. If multiple packages are pinned to the same directory, this disables parallel builds of these packages.`opam install --working-dir`

uses the working directory state of your project, instead of the state registered in the version control system. Don’t worry, opam will warn you if you have uncommitted changes and forgot to specify`--working-dir`

.

HideNOTE: this article is cross-posted on opam.ocaml.org and ocamlpro.com. Please head to the latter for the comments!

# Weekly News — OCaml Weekly News, May 02, 2017

# Looking for a technical writer — Jane Street (Yaron Minsky), May 01, 2017

Jane Street is looking to hire a technical writer. If you're interested, or know someone who you think would be a good match, here's the application link.

We've always believed that developers should spend time and effort documenting their own code, but at the same time, a great writer with a feel for the technology can raise the level of quality in a way that few developers can. And as we've grown, having someone dedicated to writing makes a ton of sense.

Here are the kinds of things we'd like …

Read more...Jane Street is looking to hire a technical writer. If you're interested, or know someone who you think would be a good match, here's the application link.

We've always believed that developers should spend time and effort documenting their own code, but at the same time, a great writer with a feel for the technology can raise the level of quality in a way that few developers can. And as we've grown, having someone dedicated to writing makes a ton of sense.

Here are the kinds of things we'd like to have a technical writer work on:

**Training material.**We have a training program that many new hires go through, including most new developers and all new traders. In that program, they learn about OCaml, our base libraries, our build system, the UNIX shell, Emacs, and our dev tools. Part of the job would be to help make the course better, both by improving what we have, and by adding new material.**Improving library documentation.**While we expect developers to do a reasonable job of documenting their code, our most important libraries deserve the time and care to make them really shine. This is aimed both internally and externally, since a lot of these libraries, like Async, Core and Incremental, are open source.**Writing longer pieces.**We need more tutorials and overviews on a variety of topics. Part of the work would be to create great new documentation, and part of it is to serve as an example for others as to what good documentation looks like. And where possible, we want to do this so that the documentation effectively compiles against our current APIs, preventing it from just drifting out of date.

In terms of skills, we want someone who is both a clear and effective written communicator, and who is good enough at programming to navigate our codebase, work through our tutorials, and write up examples. An interest in functional programming and expressive type systems is a plus, but you don't need to know any OCaml (the language we use). That's something we're happy to teach you here.

Hide# What do you mean ExceptT doesn't Compose? — Erik de Castro Lopo, Apr 30, 2017

Disclaimer: I work at Ambiata (our
Github
presence) probably the biggest Haskell shop in the southern hemisphere.
Although I mention some of Ambiata's coding practices, in this blog post I am
speaking for myself and not for Ambiata.
However, the way I'm using ** ExceptT** and handling exceptions in
this post is something I learned from my colleagues at Ambiata.

At work, I've been spending some time tracking down exceptions in some of our Haskell code that have been bubbling up to the top level…

Read more...
Disclaimer: I work at Ambiata (our
Github
presence) probably the biggest Haskell shop in the southern hemisphere.
Although I mention some of Ambiata's coding practices, in this blog post I am
speaking for myself and not for Ambiata.
However, the way I'm using ** ExceptT** and handling exceptions in
this post is something I learned from my colleagues at Ambiata.

At work, I've been spending some time tracking down exceptions in some of our Haskell code that have been bubbling up to the top level an killing a complex multi-threaded program. On Friday I posted a somewhat flippant comment to Google Plus:

Using exceptions for control flow is the root of many evils in software.ï»¿

Lennart Kolmodin who I remember from my very earliest days of using Haskell in 2008 and who I met for the first time at ICFP in Copenhagen in 2011 responded:

Yet what to do if you want composable code? Currently I have

type Rpc a = ExceptT RpcError IO a

which is terrible

But what do we mean by "composable"? I like the wikipedia definition:

ï»¿Composability is a system design principle that deals with the inter-relationships of components. A highly composable system provides recombinant components that can be selected and assembled in various combinations to satisfy specific user requirements.

The ensuing discussion, which also included Sean Leather, suggested that these
two experienced Haskellers were not aware that with the help of some combinator
functions, ** ExceptT** composes very nicely and results in more
readable and more reliable code.

At Ambiata, our coding guidelines strongly discourage the use of partial
functions.
Since the type signature of a function doesn't include information about the
exceptions it might throw, the use of exceptions is strongly discouraged.
When using library functions that may throw exceptions, we try to catch those
exceptions as close as possible to their source and turn them into
errors that are explicit in the type signatures of the code we write.
Finally, we avoid using ** String** to hold errors.
Instead we construct data types to carry error messages and render functions
to convert them to

**.**

`Text`In order to properly demonstrate the ideas, I've written some demo code and made it available in this GitHub repo. It compiles and even runs (providing you give it the required number of command line arguments) and hopefully does a good job demonstrating how the bits fit together.

So lets look at the naive version of a program that doesn't do any exception handling at all.

import Data.ByteString.Char8 (readFile, writeFile) import Naive.Cat (Cat, parseCat) import Naive.Db (Result, processWithDb, renderResult, withDatabaseConnection) import Naive.Dog (Dog, parseDog) import Prelude hiding (readFile, writeFile) import System.Environment (getArgs) import System.Exit (exitFailure) main :: IO () main = do args <- getArgs case args of [inFile1, infile2, outFile] -> processFiles inFile1 infile2 outFile _ -> putStrLn "Expected three file names." >> exitFailure readCatFile :: FilePath -> IO Cat readCatFile fpath = do putStrLn "Reading Cat file." parseCat <$> readFile fpath readDogFile :: FilePath -> IO Dog readDogFile fpath = do putStrLn "Reading Dog file." parseDog <$> readFile fpath writeResultFile :: FilePath -> Result -> IO () writeResultFile fpath result = do putStrLn "Writing Result file." writeFile fpath $ renderResult result processFiles :: FilePath -> FilePath -> FilePath -> IO () processFiles infile1 infile2 outfile = do cat <- readCatFile infile1 dog <- readDogFile infile2 result <- withDatabaseConnection $ \ db -> processWithDb db cat dog writeResultFile outfile result

Once built as per the instructions in the repo, it can be run with:

dist/build/improved/improved Naive/Cat.hs Naive/Dog.hs /dev/null Reading Cat file 'Naive/Cat.hs' Reading Dog file 'Naive/Dog.hs'. Writing Result file '/dev/null'.

The above code is pretty naive and there is zero indication of what can and cannot fail or how it can fail. Here's a list of some of the obvious failures that may result in an exception being thrown:

- Either of the two
calls.`readFile` - The
call.`writeFile` - The parsing functions
and`parseCat`.`parseDog` - Opening the database connection.
- The database connection could terminate during the processing stage.

So lets see how the use of the standard ** Either** type,

**from the**

`ExceptT`**package and combinators from Gabriel Gonzales'**

`transformers`**package can improve things.**

`errors`
Firstly the types of ** parseCat** and

**were ridiculous. Parsers can fail with parse errors, so these should both return an**

`parseDog`**type. Just about everything else should be in the**

`Either`**monad. Lets see what that looks like:**

`ExceptT e IO`{-# LANGUAGE OverloadedStrings #-} import Control.Exception (SomeException) import Control.Monad.IO.Class (liftIO) import Control.Error (ExceptT, fmapL, fmapLT, handleExceptT , hoistEither, runExceptT) import Data.ByteString.Char8 (readFile, writeFile) import Data.Monoid ((<>)) import Data.Text (Text) import qualified Data.Text as T import qualified Data.Text.IO as T import Improved.Cat (Cat, CatParseError, parseCat, renderCatParseError) import Improved.Db (DbError, Result, processWithDb, renderDbError , renderResult, withDatabaseConnection) import Improved.Dog (Dog, DogParseError, parseDog, renderDogParseError) import Prelude hiding (readFile, writeFile) import System.Environment (getArgs) import System.Exit (exitFailure) data ProcessError = ECat CatParseError | EDog DogParseError | EReadFile FilePath Text | EWriteFile FilePath Text | EDb DbError main :: IO () main = do args <- getArgs case args of [inFile1, infile2, outFile] -> report =<< runExceptT (processFiles inFile1 infile2 outFile) _ -> do putStrLn "Expected three file names, the first two are input, the last output." exitFailure report :: Either ProcessError () -> IO () report (Right _) = pure () report (Left e) = T.putStrLn $ renderProcessError e renderProcessError :: ProcessError -> Text renderProcessError pe = case pe of ECat ec -> renderCatParseError ec EDog ed -> renderDogParseError ed EReadFile fpath msg -> "Error reading '" <> T.pack fpath <> "' : " <> msg EWriteFile fpath msg -> "Error writing '" <> T.pack fpath <> "' : " <> msg EDb dbe -> renderDbError dbe readCatFile :: FilePath -> ExceptT ProcessError IO Cat readCatFile fpath = do liftIO $ putStrLn "Reading Cat file." bs <- handleExceptT handler $ readFile fpath hoistEither . fmapL ECat $ parseCat bs where handler :: SomeException -> ProcessError handler e = EReadFile fpath (T.pack $ show e) readDogFile :: FilePath -> ExceptT ProcessError IO Dog readDogFile fpath = do liftIO $ putStrLn "Reading Dog file." bs <- handleExceptT handler $ readFile fpath hoistEither . fmapL EDog $ parseDog bs where handler :: SomeException -> ProcessError handler e = EReadFile fpath (T.pack $ show e) writeResultFile :: FilePath -> Result -> ExceptT ProcessError IO () writeResultFile fpath result = do liftIO $ putStrLn "Writing Result file." handleExceptT handler . writeFile fpath $ renderResult result where handler :: SomeException -> ProcessError handler e = EWriteFile fpath (T.pack $ show e) processFiles :: FilePath -> FilePath -> FilePath -> ExceptT ProcessError IO () processFiles infile1 infile2 outfile = do cat <- readCatFile infile1 dog <- readDogFile infile2 result <- fmapLT EDb . withDatabaseConnection $ \ db -> processWithDb db cat dog writeResultFile outfile result

The first thing to notice is that changes to the structure of the main
processing function ** processFiles** are minor but

*all*errors are now handled explicitly. In addition, all possible exceptions are caught as close as possible to the source and turned into errors that are explicit in the function return types. Sceptical? Try replacing one of the

**calls with an**

`readFile`**call or a**

`error`**and see it get caught and turned into an error as specified by the type of the function.**

`throw`
We also see that despite having many different error types (which happens when
code is split up into many packages and modules), a constructor for an error
type higher in the stack can encapsulate error types lower in the stack.
For example, this value of type ** ProcessError**:

EDb (DbError3 ResultError1)

contains a ** DbError** which in turn contains a

**. Nesting error types like this aids composition, as does the separation of error rendering (turning an error data type into text to be printed) from printing.**

`ResultError`
We also see that with the use of combinators like
** fmapLT**,
and the nested error types of the previous paragraph, means that

**monad transformers do compose.**

`ExceptT`
Using ** ExceptT** with the combinators from the

**package to catch exceptions as close as possible to their source and converting them to errors has numerous benefits including:**

`errors`- Errors are explicit in the types of the functions, making the code easier to reason about.
- Its easier to provide better error messages and more context than what
is normally provided by the
instance of most exceptions.`Show` - The programmer spends less time chasing the source of exceptions in large complex code bases.
- More robust code, because the programmer is forced to think about and write code to handle errors instead of error handling being and optional afterthought.

Want to discuss this? Try reddit.

Hide# New opam features: local switches — OCamlPro, Apr 27, 2017

Among the areas we wanted to improve on for opam 2.0 was the handling of *switches*. In opam 1.2, they are simply accessed by a name (the OCaml version by default), and are always stored into `~/.opam/<name>`

. This is fine, but can get a bit cumbersome when many switches are in presence, as there is no way to sort them or associate them with a given project.

Read more...## A reminder about

switchesFor those unfamiliar with it, switches, in opam, are independent prefixes with their own compiler and set of i…

Among the areas we wanted to improve on for opam 2.0 was the handling of *switches*. In opam 1.2, they are simply accessed by a name (the OCaml version by default), and are always stored into `~/.opam/<name>`

. This is fine, but can get a bit cumbersome when many switches are in presence, as there is no way to sort them or associate them with a given project.

## A reminder about

switchesFor those unfamiliar with it, switches, in opam, are independent prefixes with their own compiler and set of installed packages. The

`opam switch`

command allows to create and remove switches, as well as select the currently active one, where operations like`opam install`

will operate.Their uses include easily juggling between versions of OCaml, or of a library, having incompatible packages installed separately but at the same time, running tests without damaging your “main” environment, and, quite often, separation of environment for working on different projects.

You can also select a specific switch for a single command, with

opam install foo --switch otheror even for a single shell session, with

eval $(opam env --switch other)

What opam 2.0 adds to this is the possibility to create so-called *local switches*, stored below a directory of your choice. This gets users back in control of how switches are organised, and wiping the directory is a safe way to get rid of the switch.

### Using within projects

This is the main intended use: the user can define a switch within the source of a project, for use specifically in that project. One nice side-effect to help with this is that, if a “local switch” is detected in the current directory or a parent, opam will select it automatically. Just don’t forget to run `eval $(opam env)`

to make the environment up-to-date before running `make`

.

### Interface

The interface simply overloads the `switch-name`

arguments, wherever they were present, allowing directory names instead. So for example:

cd ~/src/project opam switch create ./

will create a local switch in the directory `~/src/project`

. Then, it is for example equivalent to run `opam list`

from that directory, or `opam list --switch=~/src/project`

from anywhere.

Note that you can bypass the automatic local-switch selection if needed by using the `--switch`

argument, by defining the variable `OPAMSWITCH`

or by using `eval $(opam env --switch <name>)`

### Implementation

In practice, the switch contents are placed in a `_opam/`

subdirectory. So if you create the switch `~/src/project`

, you can browse its contents at `~/src/project/_opam`

. This is the direct prefix for the switch, so e.g. binaries can be found directly at `_opam/bin/`

: easier than searching the opam root! The opam metadata is placed below that directory, in a `.opam-switch/`

subdirectory.

Local switches still share the opam root, and in particular depend on the repositories defined and cached there. It is now possible, however, to select different repositories for different switches, but that is a subject for another post.

Finally, note that removing that `_opam`

directory is handled transparently by opam, and that if you want to share a local switch between projects, symlinking the `_opam`

directory is allowed.

### Current status

This feature has been present in our dev builds for a while, and you can already use it in the current beta.

### Limitations and future extensions

It is not, at the moment, possible to move a local switch directory around, mainly due to issues related to relocating the OCaml compiler.

Creating a new switch still implies to recompile all the packages, and even the compiler itself (unless you rely on a system installation). The projected solution is to add a build cache, avoiding the need to recompile the same package with the same dependencies. This should actually be possible with the current opam 2.0 code, by leveraging the new hooks that are made available. Note that relocation of OCaml is also an issue for this, though.

Editing tools like `ocp-indent`

or `merlin`

can also become an annoyance with the multiplication of switches, because they are not automatically found if not installed in the current switch. But the `user-setup`

plugin (run `opam user-setup install`

) already handles this well, and will access `ocp-indent`

or `tuareg`

from their initial switch, if not found in the current one. You will still need to install tools that are tightly bound to a compiler version, like `merlin`

and `ocp-index`

, in the switches where you need them, though.

HideNOTE: this article is cross-posted on opam.ocaml.org and ocamlpro.com. Please head to the latter for the comments!

# Crowbar Your Favorite Library for Fun and Bugfixes — Mindy Preston, Apr 26, 2017

# Caveat Configurator: how to replace configs with code, and why you might not want to — Jane Street (Yaron Minsky), Apr 25, 2017

We have a new tech talk coming up on May 17th, from our very own Dominick LoBraico. This one is about how to represent configurations with programs. In some sense, this is an obvious idea. Lots of programmers have experienced the dysphoria that comes from watching your elegant little configuration format metamorphize into a badly constructed programming language with miserable tools. This happens because, as you try to make your configs clearer and more concise, you often end up walking down the…

Read more...We have a new tech talk coming up on May 17th, from our very own Dominick LoBraico. This one is about how to represent configurations with programs. In some sense, this is an obvious idea. Lots of programmers have experienced the dysphoria that comes from watching your elegant little configuration format metamorphize into a badly constructed programming language with miserable tools. This happens because, as you try to make your configs clearer and more concise, you often end up walking down the primrose path of making your config format ever more language-like. But you never really have the time to make it into a proper language.

The obvious alternative is to just use a real language, one that comes with decent tooling and well-designed abstractions. (And ideally, a functional language, because they tend to be better at writing clear, declarative code.)

This talk discusses what happens when you try to put this obvious idea into practice, which is less, well, obvious. I like this kind of topic because it represents the kind of hard-won knowledge you can only get by trying something and screwing it up a few times.

So please join us! You can register here.

Hide# Weekly News — OCaml Weekly News, Apr 25, 2017

- error messages in multiple languages ?
- support for OCaml on unusual platforms (ia64-hpux, etc.)
- OCaml jobs at genomics company in New York City
- Ocaml 4.04.1 released
- release of batteries-2.6.0
- New release of Menhir (20170418)
- Lwt 3.0.0 – monadic promises and concurrent I/O
- PPX is harmful to our community in the long term
- BuckleScript 1.7
- CUFP 2017 Call for Tutorials
- Ocaml Github Pull Requests
- Other OCaml News

# Announcing the upcoming Frama-C & SPARK Day 2017. — Frama-C, Apr 20, 2017

# Seventeenth OCaml compiler hacking evening at Pembroke — OCaml Labs compiler hacking, Apr 18, 2017

Our next OCaml Compiler Hacking event will be on Tuesday 16th May in The Old Library at Pembroke College, Cambridge.

If you're planning to come along, it'd be helpful if you could indicate interest via Doodle and sign up to the mailing list to receive updates.

* Where*: The Old Library, Pembroke College, Cambridge CB2 1RF

The Old Library is the first building on the left straight after the Porters Lodge.

* When*: 6:30pm, Tuesday 16th May

* Who*: anyone interested in impr…

Our next OCaml Compiler Hacking event will be on Tuesday 16th May in The Old Library at Pembroke College, Cambridge.

If you're planning to come along, it'd be helpful if you could indicate interest via Doodle and sign up to the mailing list to receive updates.

* Where*: The Old Library, Pembroke College, Cambridge CB2 1RF

The Old Library is the first building on the left straight after the Porters Lodge.

* When*: 6:30pm, Tuesday 16th May

* Who*: anyone interested in improving OCaml. Knowledge of OCaml programming will obviously be helpful, but prior experience of working on OCaml internals isn't necessary.

* Refreshments*: either the Pembroke buttery between 5:45-6:45pm (cash only) or there will be a finger buffet in The Old Library itself.

* What*: fixing bugs, implementing new features, learning about OCaml internals

* Wiki*: https://github.com/ocamllabs/compiler-hacking/wiki

We're defining "compiler" pretty broadly, to include anything that's part of the standard distribution, which means at least the standard library, runtime, tools (ocamldep, ocamllex, ocamlyacc, etc.), the debugger, the documentation, and the compiler itself. We'll have suggestions for mini-projects for various levels of experience, but feel free to come along and work on whatever you fancy.

Hide# News about Tyre | Drup's thingies — Gabriel Radanne, Apr 17, 2017

Here are some news about Tyre, along with release of version 0.3.

# EzSudoku — OCamlPro, Apr 11, 2017

As you may have noticed, on the begining of April I have some urge to write something technical about some deeply specific point of OCaml. This time I’d like to tackle that through sudoku.

It appearch that Sudoku is of great importance considering the number of posts explaining how to write a solver. Following that trend I will explain how to write one in OCaml. But with a twist.

We will try to optimize it. I won’t show you anything as obvious as how to micro-optimize your code or so…

Read more...As you may have noticed, on the begining of April I have some urge to write something technical about some deeply specific point of OCaml. This time I’d like to tackle that through sudoku.

It appearch that Sudoku is of great importance considering the number of posts explaining how to write a solver. Following that trend I will explain how to write one in OCaml. But with a twist.

We will try to optimize it. I won’t show you anything as obvious as how to micro-optimize your code or some smart heuristc. No we are not aiming for being merely algorithmically good. We will try to make something serious, we are want it to be solved even before the program starts.

Yes really. Before. And I will show you how to use a feature of OCaml 4.03 that is sadly not well known.

—

First of all, as we do like type and safe programs, we will define what a well formed sudoku solution looks like. And by defining of course I mean declaring some GADTs with enough constraints to ensure that only well correct solutions are valid.

I assume tha you know the rules of Sudoku and will refrain from infuriating you by explaining it. But we will still need some vocabulary.

So the aim of sudoku is to fill a ‘grid’ with ‘symbols’ satisfying some ‘row’ ‘column’ and ‘square’ constraints.

To make the code examples readable we will stick to 4*4 sudokus. It’s the smallest size that behaves the same way as 9*9 ones (I considered going for 1*1 ones, but the article ended up being a bit short). Of course everything would still apply to any n^2*n^2 sized one.

So let’s start digging in some types. As we will refine them along the way, I will leave some parts to be filled later. This is represented by ‘…’ .

First there are symbols, just 4 of them befause we reduced the size. Nothing special about that right now.

type ... symbol = | A : ... | B : ... | C : ... | D : ...

And a grid is 16 symbols. To avoid too much visual clutter in the type I just put them linearly. The comment show how it is supposed to be seen in the 2d representation of the grid:

(* a b c d e f g h i j k l m n o p *) type grid = Grid : ... symbol * (* a *) ... symbol * (* b *) ... symbol * (* c *) ... symbol * (* d *) ... symbol * (* e *) ... symbol * (* f *) ... symbol * (* g *) ... symbol * (* h *) ... symbol * (* i *) ... symbol * (* j *) ... symbol * (* k *) ... symbol * (* l *) ... symbol * (* m *) ... symbol * (* n *) ... symbol * (* o *) ... symbol (* p *) -> solution

Right now grid is a simple 16-uple of symbols, but we will soon start filling those ‘…’ to forbid any set of symbols that is not a valid solution.

Each constraint looks like, ‘among those 4 positions neither 2 symbols are the same’. To express that (in fact something equivalent but a bit simpler to state with our types), we will need to name positions. So let’s introduce some names:

type r1 (* the first position among a row constraint *) type r2 (* the second position among a row constraint *) type r3 type r4 type c1 (* the first position among a column constraint *) type c2 type c3 type c4 type s1 type s2 type s3 type s4 type ('row, 'column, 'square) position

On the 2d grid this is how the various positions will be mapped.

r1 r2 r3 r4 r1 r2 r3 r4 r1 r2 r3 r4 r1 r2 r3 r4 c1 c1 c1 c1 c2 c2 c2 c2 c3 c3 c3 c3 c4 c4 c4 c4 s1 s2 s1 s2 s3 s4 s3 s4 s1 s2 s1 s2 s3 s4 s4 s4

For instance, the position g, in the 2nd row, 3rd column, will at the 3rd position in its row constraint, 2nd in its column constraint, and 3rd in its square constraint:

type g = (r3, c2, s3) position

We could have declare a single constraint position type, but this is slightly more readable. than:

type g = (p3, p2, p3) position

The position type is phantom, we could have provided a representation, but since no value of this type will ever be created, it’s less confusing to state it that way.

type a = (r1, c1, s1) position type b = (r2, c1, s2) position type c = (r3, c1, s1) position type d = (r4, c1, s2) position type e = (r1, c2, s3) position type f = (r2, c2, s4) position type g = (r3, c2, s3) position type h = (r4, c2, s4) position type i = (r1, c3, s1) position type j = (r2, c3, s2) position type k = (r3, c3, s1) position type r = (r4, c3, s2) position type m = (r1, c4, s3) position type n = (r2, c4, s4) position type o = (r3, c4, s3) position type p = (r4, c4, s4) position

It is now possible to state for each symbol in which position it is, so we will start filling a bit those types.

type ('position, ...) symbol = | A : (('r, 'c, 's) position, ...) symbol | B : (('r, 'c, 's) position, ...) symbol | C : (('r, 'c, 's) position, ...) symbol | D : (('r, 'c, 's) position, ...) symbol

This means that a symbol value is then associated to a single position in each constraint. We will need to state that in the grid type too:

type grid = Grid : (a, ...) symbol * (* a *) (b, ...) symbol * (* b *) (c, ...) symbol * (* c *) (d, ...) symbol * (* d *) (e, ...) symbol * (* e *) (f, ...) symbol * (* f *) (g, ...) symbol * (* g *) (h, ...) symbol * (* h *) (i, ...) symbol * (* i *) (j, ...) symbol * (* j *) (k, ...) symbol * (* k *) (l, ...) symbol * (* l *) (m, ...) symbol * (* m *) (n, ...) symbol * (* n *) (o, ...) symbol * (* o *) (p, ...) symbol (* p *) -> solution

We just need to forbid a symbol to appear in two different positions of a given row/column/square to prevent invalid solutions.

type 'fields row constraint 'fields = < a : 'a; b : 'b; c : 'c; d : 'd > type 'fields column constraint 'fields = < a : 'a; b : 'b; c : 'c; d : 'd > type 'fields square constraint 'fields = < a : 'a; b : 'b; c : 'c; d : 'd >

Those types represent the statement ‘in this line/column/square, the symbol a is at the position ‘a, the symbol b is at the position ‘b, …’

For instance, the row ‘A D B C’ will be represented by

< a : l1; b : l3; c : l4; d : l2 > row

Which reads: ‘The symbol A is in first position, B in third position, C in fourth, and D in second’

The object type is used to make things a bit lighter later and allow to state names.

Now the symbols can be a bit more annotated:

type ('position, 'row, 'column, 'square) symbol = | A : (('r, 'c, 's) position, < a : 'r; .. > row, < a : 'c; .. > column, < a : 's; .. > square) symbol | B : (('r, 'c, 's) position, < b : 'r; .. > row, < b : 'c; .. > column, < b : 's; .. > square) symbol | C : (('r, 'c, 's) position, < c : 'r; .. > row, < c : 'c; .. > column, < c : 's; .. > square) symbol | D : (('r, 'c, 's) position, < d : 'r; .. > row, < d : 'c; .. > column, < d : 's; .. > square) symbol

Notice that ‘..’ is not ‘…’. Those dots are really part of the OCaml syntax: it means ‘put whatever you want here, I don’t care’. There is nothing more to add to this type.

This type declaration reports the position information. Using the same variable name ‘r in the position and in the row constraint parameter for instance means that both fields will have the same type.

For instance, a symbol ‘B’ in position ‘g’ would be in the 3rd position of its row, 2nd position of its column , and 3rd position of its square:

# let v : (g, _, _, _) symbol = B;; val v : (g, < b : r3 > row, < b : c2 > column, < b : s3 > square) symbol = B

Those types constraints ensure that this is correctly reported.

The real output of the type checker is a bit more verbose, but I remove the irrelevant part:

val v : (g, < a : 'a; b : r3; c : 'b; d : 'c > row, < a : 'd; b : c2; c : 'e; d : 'f > column, < a : 'g; b : s3; c : 'h; d : 'i > square) symbol = B

We are now quite close from a completely constrained type. We just need to say that the various symbols from the same row/line/column constraint have the same type:

type grid = Grid : (a, 'row1, 'column1, 'square1) symbol * (b, 'row1, 'column2, 'square1) symbol * (c, 'row1, 'column3, 'square2) symbol * (d, 'row1, 'column4, 'square2) symbol * (e, 'row2, 'column1, 'square1) symbol * (f, 'row2, 'column2, 'square1) symbol * (g, 'row2, 'column3, 'square2) symbol * (h, 'row2, 'column4, 'square2) symbol * (i, 'row3, 'column1, 'square3) symbol * (j, 'row3, 'column2, 'square3) symbol * (k, 'row3, 'column3, 'square4) symbol * (l, 'row3, 'column4, 'square4) symbol * (m, 'row4, 'column1, 'square3) symbol * (n, 'row4, 'column2, 'square3) symbol * (o, 'row4, 'column3, 'square4) symbol * (p, 'row4, 'column4, 'square4) symbol *

That is two symbols in the same row/column/square will share the same ‘row/’symbol/’square type. For any couple of symbols in say, a row, they must agree on that type, hence, on the position of every symbol.

Let’s look at the ‘A’ symbol for the ‘a’ and ‘c’ position for instance. Both share the same ‘row1 type variable. There are two cases. Either both are ‘A’s ore one is not.

* If one symbol is not a ‘A’, let’s say those are ‘C’ and ‘A’ symbols. Their row type (pun almost intended) will be respectively `< c : r1; .. >`

and `< a : r3; .. >`

. Meaning that ‘C’ does not care about the position of ‘A’ and conversly. Those types are compatible. No problem here.

* If both are ‘A’s then something else happens. Their row types will be `< a : r1; .. >`

and `< a : r3; .. >`

which is certainly not compatible since r1 and r3 are not compatible. This will be rejected.

Now we have a grid type that checks the sudoku constraints !

Let’s try it.

let ok = Grid (A, B, C, D, C, D, A, B, D, A, B, C, B, C, D, A) val ok : grid = Grid (A, B, C, D, C, D, A, B, D, A, B, C, B, C, D, A) let not_ok = Grid (A, B, C, D, C, D, A, B, D, A, B, C, B, C, A, D) B, C, A, D);; ^ Error: This expression has type (o, < a : r3; b : r1; c : r2; d : 'a > row, < a : c4; b : 'b; c : 'c; d : 'd > column, < a : s3; b : 'e; c : 'f; d : 'g > square) symbol but an expression was expected of type (o, < a : r3; b : r1; c : r2; d : 'a > row, < a : c2; b : c3; c : c1; d : 'h > column, < a : 'i; b : s1; c : s2; d : 'j > square) symbol Types for method a are incompatible

What it is trying to say is that ‘A’ is both at position ‘2’ and ‘4’ of its column. Well it seems to work.

### Solving it

But we are not only interested in checking that a solution is correct, we want to find them !

But with ‘one weird trick’ we will magically transform it into a solver, namely the `-> .`

syntax. It was introduced in OCaml 4.03 for some other purpose. But we will now use its hidden power !

This is the right hand side of a pattern. It explicitely states that a pattern is unreachable. For instance

type _ t = | Int : int -> int t | Float : float -> float t let add (type v) (a : v t) (b : v t) : v t = match a, b with | Int a, Int b -> Int (a + b) | Float a, Float b -> Float (a +. b) | _ -> .

By writing it here you state that you don’t expect any other pattern to verify the type constraints. This is effectively the case here. In general you won’t need this as the exhaustivity checker will see it. But in some intricate situations it will need some hints to work a bit more. For more information see Jacques Garrigue / Le Normand article

This may be a bit obscure, but this is what we now need. Indeed, we can ask the exhaustivity checker if there exist a value verifying the pattern and the type constraints. For instance to solve a problem, we ask the compiler to check if there is any value verifying a partial solution encoded as a pattern.

A _ C _ _ D _ B _ A D _ D _ B _

let test x = match x with | Grid (A, _, C, _, _, D, _, B, _, A, D, _, D, _, B, _) -> . | _ -> () Error: This match case could not be refuted. Here is an example of a value that would reach it: Grid (A, B, C, D, C, D, A, B, B, A, D, C, D, C, B, A)

The checker tells us that there is a solution verifying those constraints, and provides it.

If there were no solution, there would have been no error.

let test x = match x with | Grid (A, B, C, _, _, _, _, D, _, _, _, _, _, _, _, _) -> . | _ -> () val test : grid -> unit =

And that’s it !

### Wrapping it up

Of course that’s a bit cheating since the program is not executable, but who cares really ?

If you want to use it, I made a small (ugly) script generating those types. You can try it on bigger problems, but in fact it is a bit exponential. So you shouldn’t really expect an answer too soon.

View older blog posts.

### Syndications

- Alex Leighton
- Amir Chaudhry
- Andrej Bauer
- Andy Ray
- Anil Madhavapeddy
- Ashish Agarwal
- CUFP
- Cameleon news
- Caml INRIA
- Caml Spotting
- Cedeela
- Coherent Graphics
- Coq
- Cranial Burnout
- Cryptosense
- Daniel Bünzli
- Daniel Bünzli (log)
- Dario Teixeira
- David Baelde
- David Mentré
- David Teller
- Eray Özkural
- Erik de Castro Lopo
- Etienne Millon
- Frama-C
- Functional Jobs
- GaGallium
- Gabriel Radanne
- Gaius Hammond
- Gerd Stolpmann
- GitHub Jobs
- Grant Rettke
- Hannes Mehnert
- Hong bo Zhang
- Incubaid Research
- Jake Donham
- Jane Street
- KC Sivaramakrishnan
- Leo White
- LexiFi
- Mads Hartmann
- Magnus Skjegstad
- Marc Simpson
- Matthias Puech
- Matías Giovannini
- Mike Lin
- Mike McClurg
- Mindy Preston
- MirageOS
- OCaml Book
- OCaml Labs
- OCaml Labs compiler hacking
- OCaml Platform
- OCaml Weekly News
- OCaml-Java
- OCamlCore Forge News
- OCamlCore Forge Projects
- OCamlCore.com
- OCamlPro
- ODNS project
- Ocaml XMPP project
- Ocsigen blog
- Ocsigen project
- Opa
- Orbitz
- Paolo Donadeo
- Perpetually Curious
- Peter Zotov
- Phil Tomson
- Pietro Abate
- Psellos
- Richard Jones
- Rudenoise
- Rudi Grinberg
- Sebastien Mondet
- Shayne Fletcher
- Simon Grondin
- Stefano Zacchiroli
- Sylvain Le Gall
- Thomas Leonard
- Till Varoquaux
- WODI
- Xinuo Chen
- Yan Shvartzshnaider