The AST of the type expressions

A very simple type-expression language.

This (at the moment) just to implement the type-checker of chapter 9 of ‘The Implementation of Functional Programming Languages’.

Note

We should see if the types in stdlib’s typing module are appropriate.

xotl.fl.ast.types.find_tvars(t: xotl.fl.ast.types.Type) → List[xotl.fl.ast.types.TypeVariable]

Get all type variables (possibly repeated) in type t.

Example:

>>> find_tvars_names(Type.from_str('a -> b -> c -> a'))
['a', 'c', 'b', 'a']

If t is (or contains a TypeScheme) its generics variables will be excluded (unless they’re repeated and appear outside the scope of type scheme):

>>> find_tvars_names(Type.from_str('a -> [forall b. b] -> a'))
['a', 'a']

>>> find_tvars_names(Type.from_str('[forall a. a] -> b -> a'))
['a', 'b']

class xotl.fl.ast.types.Type

classmethod from_str(source: str) → xotl.fl.ast.types.Type

Parse a single type expression.

Example:

>>> Type.from_str('a -> b -> a')
TypeCons('->', (TypeVariable('a'), TypeCons('->', (...))))

class xotl.fl.ast.types.TypeVariable(name: str, *, check=True)

Bases: xotl.fl.ast.types.Type

A type variable, which may stand for any type.

class xotl.fl.ast.types.TypeCons(constructor: str, subtypes: Iterable[xotl.fl.ast.types.Type] = None, *, binary=False)

Bases: xotl.fl.ast.types.Type

The syntax for a type constructor expression.

class xotl.fl.ast.types.TypeScheme(generics: Sequence[str], t: xotl.fl.ast.types.Type)

A type scheme with generic (schematics) type variables.

Example:

>>> from xotl.fl.parsers.types import parse as parse_type
>>> map_type = TypeScheme(['a', 'b'],
...                       parse_type('(a -> b) -> List a -> List b'))

>>> map_type
<TypeScheme: forall a b. (a -> b) -> ((List a) -> (List b))>

classmethod from_str(source: str, *, generics: Sequence[str] = None) → xotl.fl.ast.types.TypeScheme

Create a type scheme from a type expression assuming all type variables are generic.

Example:

>>> TypeScheme.from_str('a -> b -> a')
<TypeScheme: forall a b. a -> (b -> a)>

classmethod from_typeexpr(type_: xotl.fl.ast.types.Type, *, generics: Sequence[str] = None) → xotl.fl.ast.types.TypeScheme

Create a type scheme from a type expression assuming all type variables are generic.

If type_ is already a TypeScheme, return it unchanged.

If generics is not None, use those instead of finding the free variables. You may pass the empty list or tuple, to create a TypeScheme without any generic variables.

xotl.fl.ast.types.FunctionTypeCons(a, b)

Shortcut to create function types

xotl.fl.ast.types.ListTypeCons(t: xotl.fl.ast.types.Type) → None

The syntax for a type constructor expression.

xotl.fl.ast.types.TupleTypeCons(*ts) → None

The syntax for a type constructor expression.

xotl.fl.ast.types.TypeEnvironment

A type object defined as Mapping[str ,TypeScheme]. When type-checking you do so in such an environment.

xotl.fl.ast.types.EMPTY_TYPE_ENV

The empty TypeEnvironment.