Introduction

This document describes the programming language Fram, and is divided into the following parts.

Part I is intended to be a general introduction to the language.
Part II serves as a reference manual as well as the informal specification of Fram.
Part III documents the standard library.
Part IV describes programming conventions.

Installation

The most complete implementation of Fram currently available is the interpreter called DBL, written in OCaml and built using dune.

Getting Started

Named Parameters

Data Types

User can define custom data types using the data keyword. Fram supports so called algebraic data types (ADTs), where a type can be defined as a list of its constructors. In the simplest case, when constructors do not take any parameters, the data type definition is just an enumeration of the constructors. Names of types and their constructors must start with a capital letter.

data Direction = North | South | East | West

However, constructors can also take parameters. In this case, the constructor is followed by of keyword and a comma separated list of types of the parameters. The bar before the first constructor is optional.

data Shape =
  | Arrow     of Direction
  | Circle    of Int
  | Rectangle of Int, Int

Constructors of data types can be used as regular values. Constructors with parameters can be used as functions, and in particular, they can be partially applied.

let westArrow = Arrow West
let r13 = Rectangle 13

Data types can be parametrized by other types.

data OptPair X Y =
  | OnlyLeft  of X
  | OnlyRight of Y
  | Both      of X, Y

Pattern Matching

Elements of data types can be deconstructed and analyzed using pattern matching. Pattern matching is done using the match ... with construct, followed by the list of pattern matching clauses and the end keyword. Each clause consists of a pattern and an expression (body of the clause). The pattern can be built from constructors and binds variables that can be used in the body of the clause.

let swapOptPair p =
  match p with
  | OnlyLeft  x => OnlyRight x
  | OnlyRight y => OnlyLeft  y
  | Both x y    => Both y x
  end

Fram supports deep pattern matching, i.e. matching on nested constructors. Additionally, the wildcard pattern _ can be used to match any value without binding any variables. Because regular variables start with a lowercase letter, it is always clear when a pattern binds a variable or matches a constructor without parameters.

let rotate shape =
  match shape with
  | Arrow North   => Arrow East
  | Arrow South   => Arrow West
  | Arrow East    => Arrow South
  | Arrow West    => Arrow North
  | Rectangle w h => Rectangle h w
  | Circle _      => shape
  end

Patterns of different clauses within the same match construct may overlap. In this case, the first matching clause is used. Provided patterns must be exhaustive, i.e. each of possible values of the matched expression must be covered by at least one pattern.

Fram allows to use pattern in almost any place where a variable binder can be used. For example, patterns can be used in let bindings or as function parameters. Such patterns must obey the exhaustiveness condition.

data Triple = Triple of Int, Int, Int

let sum1 (Triple x y z) =
  x + y + z

let sum2 t =
  let (Triple x y z) = t in
  x + y + z

Recursive Data Types

In Fram, data types can be recursive. This means that a data type can contain constructors that refer to the same data type. For example, a binary tree can be defined as follows.

data Tree X =
  | Leaf
  | Node of Tree, X, Tree

Note that recursive data types must be explicitly marked using the rec keyword. Mutually recursive data types can be defined using a rec ... end block. The same block can be shared with mutually recursive functions.

rec
  data RoseTree X = Node of X, RoseTreeList X

  data RoseTreeList X =
    | Nil
    | Cons of RoseTree X, RoseTreeList X

  let map f (Node x ts) =
    Node (f x) (mapList f ts)

  let mapList f ts =
    match ts with
    | Nil       => Nil
    | Cons t ts => Cons (map f t) (mapList f ts)
    end
end

Constructors with Named Parameters

Constructors can also have named parameters. This is useful when the meaning of the parameter is not clear from its type nor the position.

data Color =
  | RGB  of { red : Int, green : Int, blue : Int }
  | CMYK of { cyan : Int, magenta : Int, yellow : Int, black : Int }

Named parameters of the constructor become part of its type scheme. Similarly to named parameters of functions, they must be always provided, but their order does not matter.

let orange = RGB { red = 255, green = 127, blue = 0 }
let black  = CMYK { black = 100, cyan = 0, magenta = 0, yellow = 0 }

Similarly, parameters of the data are attached to the constructor's scheme. This means that these parameters might be explicitly provided when the constructor is used.

let emptyIntTree = Leaf {X=Int}

To enforce type parameters to become anonymous, the type keyword can be used at the place of binding.

data Box (type X) = Box of { value : X }

Named parameters of the constructor can be used in pattern matching. The syntax is similar to the one used in explicit binding of named parameters of functions: after the name of the parameter, the = sign is used to provide the pattern for the parameter. For convenience, the = sign can be omitted if the pattern is a variable of the same name as the parameter. It is also possible to omit some of the named parameters.

let unboxGetRed c =
  match c with
  | Box { value = RGB { red } } => red
  | _ => 0
  end

Records

In Fram, records are just syntactic sugar for data types with only one constructor which has only named parameters. To define a record, the name of the constructor and the of keyword are omitted.

data Vec3D T =
  { x : T
  , y : T
  , z : T
  }

For record definitions, methods for accessing the fields are generated automatically. The above definition is equivalent to the following sequence of definitions.

data Vec3D T = Vec3D of { x : T, y : T, z : T }

method x (Vec2D { x }) = x
method y (Vec2D { y }) = y
method z (Vec2D { z }) = z

Therefore, records can be used in a similar way as records in other languages, but in fact, all operations on records are just combination of named parameters, methods, and constructors of ADTs.

let cross (v1 : Vec3D Int) (v2 : Vec3D Int) =
  Vec3D
    { x = v1.y * v2.z - v1.z * v2.y
    , y = v1.z * v2.x - v1.x * v2.z
    , z = v1.x * v2.y - v1.y * v2.x
    }

Existential Types

In Fram, each kind of named parameter can be a parameter of the constructor. In particular, constructors can have type parameters. Such parameters behave like existential types, i.e., their actual definition is not accessible when the data type is deconstructed. In the next chapter, we will see the most common use of existential types in Fram, but first let's start with a simple toy example. Here we define a Church encoding of an infinite stream, i.e., the stream is defined by its own unfold.

data Stream X =
  Stream of {St, state : St, elem : St ->[] X, next : St ->[] St}

The stream has a private state state of some type St, which can be different for each stream. The elem function computes the first element of the stream and the next function computes the next state of the tail of the stream. Note that the stream is not defined as a record. This is because the type St is not visible outside the constructor. In general, Fram forbids to use existential types in the record definition.

Existential types are just type parameters to the constructor, and as with other forms of type parameters, the user can provide them explicitly, or rely on the type inference.

let natStream =
  Stream
    { St    = Int
    , state = 0
    , elem  = fn n => n
    , next  = fn n => n + 1
    }

let tail (Stream {state, elem, next}) =
  Stream { state = next state, elem, next }

Name existential types can be explicitly bound in the pattern matching.

let cons x (Stream {St, state, elem, next}) =
  Stream
    { St    = Option St
    , state = None
    , elem  = fn s =>
        match s with
        | None   => x
        | Some s => elem s
        end
    , next  = fn s =>
        match s with
        | None   => Some state
        | Some s => Some (next s)
        end
    }

Empty Data Types

Data types can have empty list of constructors.

data Empty =

Pattern matching on empty data types is possible, but the type of the matched expression must be known from the context.

let ofEmpty (x : Empty) =
  match x with
  end

Modules

Overview

Member Visibility

Packing Named Parameters

Effect Handlers

Case Study: Implementation of Prolog

Notational Conventions

This reference manual will often present the grammars of various elements of Fram's syntax. We use a variant of the BNF notation to specify the grammars. Non-terminal symbols have no special formatting, while the terminals are enclosed in quotation marks. Alternatives are separated by |, and grouping is achieved with parentheses: (E). We also use {E} to denote repetition, and [E] to denote the optional inclusion of E. See the following grammar for a simple example (not specifically related to Fram).

digit       ::= "0"..."9"
letter      ::= "a"..."z" | "A"..."Z"
lower-ident ::= ( "a"..."z" | "_" ) { letter | digit | "_" | "'" }
integer     ::= "0" | [ "-" ] "1"..."9" { digit }

Lexical Structure

Whitespace

The following characters are considered as whitespace (blanks): horizontal tab (0x09), new line (0x10), vertical tab (0x11), form feed (0x12), carriage return (0x13), and space (0x20). Whitespace characters are ignored by the lexer, but they separate tokens, e.g., identifiers or literals.

Comments

Fram supports two kinds of comments: single-line and block comments. Comments are treated similarly to whitespace: they are ignored by the lexer, but they always separate tokens.

Single-line comments start with the # character and end with a new line or the end of file.

Block comments are introduced by the sequence {# followed by any, possibly empty, sequence name of any characters except control characters (0x00-0x1f, 0x7f), space, and curly braces ({ and }). Such a block comment is terminated by the first occurrence of name that is immediately followed by #}. More precisely, it can be described by the following grammar.

block-comment-name  ::= { "!"..."z" | "|" | "~" | non-ascii-character }
block-comment-start ::= "{#" block-comment-name
block-comment-end   ::= block-comment-name "#}"

At the comment opening, the longest consecutive sequence described by block-comment-name is taken as the comment name. This name should be a suffix of the name provided at comment closing. Comments using the same name cannot be nested. This is not an issue in practice, since the programmer can always choose a unique name to accomplish nesting.

By convention, single-line comments starting with ## and block comments with a name starting with # are used as documentation comments, and can be recognized by some external tools.

Examples

The following code contains some valid comments.

# This is a single-line comment.
{# This is a block comment. #}
{# Block comments
  may span multiple lines.
#}
let id x = x # A single-line comment may appear at the end of a line.

let n {# A block comment may span a part of a single line. #} = 42
{#aaa
Comments cannot be nested,
{# but the programmer may choose the comment delimiters. #}
aaa#}

{#!a! Comment names may contain operators. !a!#}

{#abc
This comment is ended by `abc` immediately followed by `#}`,
even if the closing sequence is preceded by other characters.
zzabc#}

let {#
# This is not a single-line comment,
# because comments are not nested.
# This comment can be ended #} here = 13

## This is a documentation comment.
let foo x = x

{## This is another documentation comment. ##}
let bar = foo

{###
Documentation comments can contain some code
```
{## with another documentation comment (with a different name). ##}
let some_code = 42
```
###}
let baz = bar

Literals

digit        ::= "0"..."9"
lower-char   ::= "a"..."z" | "_"
upper-char   ::= "A"..."Z"
ident-char   ::= lower-char | upper-char | digit | "'"

op-char ::= "<" | ">" | "&" | "$" | "?" | "!" | "@" | "^" | "+" | "-"
          | "~" | "*" | "%" | ";" | "," | "=" | "|" | ":" | "." | "/"

Prelude

The Prelude module is automatically imported and opened in all programs.

The Fram Language

Introduction

Installation

Getting Started

Named Parameters

Type Parameters

Regular Named Parameters

Optional Parameters

Implicit Parameters

Sections