Hexbyte  Hacker News  Computers In-Depth: Static Code Analysis

Hexbyte Hacker News Computers In-Depth: Static Code Analysis

Hexbyte Hacker News Computers

Hexbyte  Hacker News  Computers In-Depth: Static Code Analysis

December 27, 2011 | By

John Carmack
















Related Jobs

Hexbyte  Hacker News  Computers The Behemoth

The Behemoth —
San Diego,
California,
United States



[09.29.18]



Experienced Generalist Programmer

Hexbyte  Hacker News  Computers Poleaxe Games LLC

Poleaxe Games LLC —
SAINT JOHNS,
Florida,
United States



[09.29.18]



Contract: Graphics programmer for surface effect system

Hexbyte  Hacker News  Computers Skydance Interactive

Skydance Interactive —
Marina Del Rey,
California,
United States



[09.28.18]



AI Gameplay Engineer

Hexbyte  Hacker News  Computers Skydance Interactive

Skydance Interactive —
Marina Del Rey,
California,
United States



[09.28.18]



Jr. Platform Engineer


128836
newswire
/view/news/128836/InDepth_Static_Code_Analysis.php
Loading Comments



Hexbyte  Hacker News  Computers loader image

Read More

HOWTO: Static access control using phantom types

HOWTO: Static access control using phantom types

We thought that phantom types would be an appropriate topic for our first real
post because they are a good example of a powerful and useful feature of OCaml
that is little used in practice.

In this post, I’ll cover a fairly simple use of phantom types: enforcing a
capability-style access-control policy. In particular, I’ll describe how you can
create easy to use read-only handles to a mutable data structure. We’ll explore
this using the example of an int ref. The int ref is a toy example, but the
same approach can be used for more realistic cases, such as a string library or
a database interface.

We’ll start by implementing an int ref module on top of OCaml’s built-in ref.

module Ref : sig
  type t
  val create : int -> t
  val set : t -> int -> unit
  val get : t -> int
end
 =
struct
  type t = int ref
  let create x = ref x
  let set t x = t := x
  let get t = !t
end

The simplest way of getting a read-only handle is to create another module with
a different, more constrained signature.

module RORef : sig
  type t
  val import : Ref.t -> t
  val get : t-> int
end
 =
struct
  type t = Ref.t
  let import x = x
  let get = Ref.get
end

An RORef.t is just a Ref.t underneath, but the signature hides that fact by
making the RORef.t abstract. Note that there is a function for converting
Ref.t’s to RORef.t’s (import), but not the other way around. This gives
you a way to create the read-only handle, but prevents someone with such a
handle from recovering the underlying read-write handle. The downside to this
approach is that it is impossible to write code that is polymorphic over
Ref.t’s and RORef.t’s, even if that code only uses the functionality common
to both, i.e., if it only reads.

A better solution is to use a phantom type to encode the access control rights
associated with a particular value. But what is a phantom type? The definition
unfortunately makes it sound more complicated than it is. A phantom type is a
type that is used as a parameter to another type (like the int in int list),
but which is unused in the actual definition (as in type 'a t = int). The fact
that the phantom parameter is unused gives you the freedom to use it to encode
additional information about your types, which you can then convince the type
checker to keep track of for you. Since the phantom type isn’t really part of
the definition of the type, it has no effect on code-generation and so is
completely free at runtime. The way in which you convince the type-checker to
track the information you’re interested in is by constraining the appearance of
the phantom types using a signature.

It’s easier to understand once you look at an example.

type readonly
type readwrite

module PRef : sig
  type 'a t
  val create : int -> readwrite t
  val set : readwrite t -> int -> unit
  val get : 'a t -> int
  val readonly : 'a t -> readonly t
end
 =
struct
  type 'a t = Ref.t
  let create = Ref.create
  let set = Ref.set
  let get = Ref.get
  let readonly x = x
end

In the above code, the phantom type tells you what your permissions are. A
readwrite PRef.t can read and write, and a readonly PRef.t can only read.
Note that the get function doesn’t pay any attention to the phantom type,
which is why get can be used with both readwrite and readonly PRef.t’s.
The only function that can modify a ref is get, and that requires a
readwrite PRef.t.

Note that the types readonly and readwrite have no definitions. They look
like the declaration of an abstract type, except that these definitions are not
in a signature. They’re actually examples of uninhabited types, i.e., types
without associated values. The lack of values presents no problems here, since
we’re using the types only as tags.

The great thing about this approach is how seamlessly it works in practice. The
user of the library can write things in a natural style, and the type system
propagates the access-control constraints as you would expect. For example, the
following definitions

let sumrefs reflist =
  List.fold_left (+) 0 (List.map PRef.get reflist)

let increfs reflist =
  List.iter (fun r -> PRef.set r (PRef.get r + 1)) reflist

will be given the following inferred types

val sumrefs : 'a PRef.t list -> int
val increfs : readwrite PRef.t list -> unit

In other words, the first function, which only reads, can operate on any kind of
ref, and the second, which mutates the refs, requires a readwrite ref.

There is one problem with the access control policy we implemented above, which
is that there is no clean way of guaranteeing that a given value is immutable.
In particular, even if a given value is readonly, it doesn’t preclude the
existence of another readwrite handle to the same object somewhere else in the
program. (Obviously, immutable int refs are not a particularly compelling
application, but having both mutable and immutable versions makes sense for more
complicated data types, such as string or arrays).

But we can get immutable values as well by making the phantom types just
slightly more complicated.

type readonly
type readwrite
type immutable

module IRef : sig
  type 'a t
  val create_immutable : int -> immutable t
  val create_readwrite : int -> readwrite t
  val readonly : 'a t -> readonly t
  val set : readwrite t -> int -> unit
  val get : 'a t -> int
end
 =
struct
  type 'a t = Ref.t
  let create_immutable = Ref.create
  let create_readwrite = Ref.create
  let readonly x = x
  let set = Ref.set
  let get = Ref.get
end

Importantly, there’s no way for an IRef.t to become immutable. It must be
immutable from birth.

One thing that’s notable about the IRef signature is that there is no way of
creating an actual polymorphic IRef.t. The two creation functions both create
values with specific tags, immutable or readwrite. These specialized create
functions aren’t strictly necessary, though. We could have instead written
IRef with the following signature.

sig
  type 'a t
  val create : int -> 'a t
  val set : readwrite t -> int -> unit
  val get : 'a t -> int
  val readonly : 'a t -> readonly t
end

The user can force the creation of an immutable or readwrite Ref by adding a
constraint. So, you could get the effect of

let r = IRef.create_immutable 3

by instead writing

let r = (IRef.create 3 : immutable IRef.t)

The advantage of the polymorphic create function is straightforward: it allows
you to write functions that are more polymorphic, and therefore more flexible.
For instance, you could write a single function that could create, depending on
context, an array of readwrite refs, an array of readonly refs, or an array of
immutable refs.

The downside is that it may require more type annotations when you do want to be
explicit about the permissions, and it also allows some weird types to come up.
In particular, you can create an IRef.t with any phantom parameter you want!
Nothing stops you from creating a string IRef.t, even though string doesn’t
make any sense as an access-control tag. Interestingly, the signature doesn’t
actually make any reference to the immutable type, and in fact, using any
phantom parameter other than readonly and readwrite makes the ref immutable.
The access control restrictions still work in roughly the way you would expect,
but it is still a bit harder to think about than the original signature.