Module Fang_tiger

The Tiger language.

The language is encoded in the tagless-final style.

Source file locations

type source_span

A span in a Tiger source file.

Spans are defined by a start point (the "origin") and an end point (the "terminus").

The origin and terminus must define a contiguous span in the file. If they don't, the span is invalid.

module Source_span : sig ... end

Language specification

type expr = private
| Expr_tag
type target = private
| Target_tag
type decl = private
| Decl_tag
type fn = private
| Fn_tag
type param = private
| Param_tag
type typ = private
| Typ_tag
type oper = [
| `Add
| `Subtract
| `Multiply
| `Divide
| `And
| `Or
]
type rel = [
| `Equal
| `Not_equal
| `Less
| `Less_or_equal
| `Greater
| `Greater_or_equal
]
type tag = source_span
module type TIGER = sig ... end

The Tiger language.

Validation (type-checking)

type validation_error = unit Fmt.t
module Validation : functor (L : TIGER) -> sig ... end

Semantic analysis and type-checking of Tiger fragments.

Pretty-printing

module Pretty : sig ... end

Pretty-printing Tiger fragments.

Parsing

type parsing_error = [
| `Syntax_error
| `Invalid_string_character of char
| `Unterminated_string
| `Invalid_token of string
]
val pp_parsing_error : parsing_error Fmt.t
module Parsing : functor (L : TIGER) -> sig ... end

Parsing Tiger fragments.

Static analysis

type analysis

Accumulated knowledge about a Tiger fragment based on static analysis.

type _ property

A specific property of interest about elements of Tiger fragments.

Values of type 'a property are mappings from tags to values of type 'a.

If an int property is only applicable to variables, for example, the tag of every TIGER.var will have a corresponding int value.

val escaping : analysis -> [ `Local | `Escapes ] property

A variable or parameter is said to "escape" if it is referenced at a static function depth greater than the depth of its definition.

A variable or parameter is "local" if it does not escape.

Knowing whether variables and parameters escape or not is important for translation into the intermediate representation, because storage locations with local scope can fit in efficient registers instead of memory.

For example, consider this Tiger fragment:

let
  var x := 10
  function add(y: int): int = x + y
in
  x + 1
end

In this example:

  • x escapes because it is referenced in the body of add.
  • y is local because it is not referenced outside the function where it's defined.
val mutability : analysis -> [ `Constant | `Mutates ] property

A variable assigned to after its initial definition is said to "mutate".

This information is useful during translation to the intermediate representation because it determines whether statically-inferred facts about variables apply.

For example, consider this Tiger snippet:

let
  type numbers = array of int
  var xs := numbers[5] of 10
  var ys := xs
in
  ys[3] := 100
end

The size of xs is statically known to be 5. Since ys is initialized to xs and both xs and ys are constant, we know the size of ys is also 5.

Knowing this, bounds-checks for the assignment to ys[3] can be elided.

val leaves : analysis -> [ `Branch | `Leaf ] property

Functions which don't call other user-defined Tiger functions are called "leaves".

Knowing which functions are leaves is useful for translation into the intermediate representation because leaf functions don't need to store their static link in memory.

module Analysis : functor (L : TIGER) -> sig ... end
module Property : sig ... end

No-op interpreter

module Nop : TIGER with type _ t = unit

The no-op interpreter, which can be useful for testing.