The AST of the expressions language

The AST of the enriched lambda calculus.

xotl.fl.ast.expressions.find_free_names(expr: xotl.fl.ast.base.AST, *, exclude: Sequence[str] = None) → List[Union[str, xotl.fl.meta.Symbol]]

Find all names that appear free in expr.

Example:

>>> set(find_free_names(parse('let id x = x in map id xs')))  # doctest: +LITERAL_EVAL
{'map', 'xs'}

Names can be repeated:

>>> find_free_names(parse('twice x x')).count('x')
2

If exclude is None, we exclude all special identifiers used internally after pattern matching translation. If you want to expose them, pass the empty tuple:

>>> program = """
...     let length [] = 0
...         length x:xs = 1 + length xs
...     in length
... """
>>> set(find_free_names(parse(program).compile(), exclude=()))  # doctest: +LITERAL_EVAL
{'+', ':NO_MATCH_ERROR:', ':OR:'}

xotl.fl.ast.expressions.replace_free_occurrences(self: xotl.fl.ast.base.AST, substitutions: Mapping[Union[str, xotl.fl.meta.Symbol], str]) → xotl.fl.ast.base.AST

Create a new expression replacing free occurrences of variables.

You are responsible to avoid the name capture problem:

>>> replace_free_occurrences(parse_expression('\id -> id x'), {'x': 'id'})
Lambda('id', Application(Identifier('id'), Identifier('id')))

xotl.fl.ast.expressions.build_lambda(params: Reversible[str], body: xotl.fl.ast.base.AST) → xotl.fl.ast.expressions.Lambda

Create a Lambda from several parameters.

Example:

>>> build_lambda(['a', 'b'], Identifier('a'))
Lambda('a', Lambda('b', Identifier('a')))

Core objects of the abstract syntax

class xotl.fl.ast.expressions.Identifier(name: Union[str, xotl.fl.meta.Symbol])

A name (variable if you like).

class xotl.fl.ast.expressions.Literal(value: Any, type_: xotl.fl.ast.types.Type, annotation: Any = None)

A literal value with its type.

The parser only recognizes strings, chars, and numbers (integers and floats are represented by a single type).

class xotl.fl.ast.expressions.Lambda(varname: str, body: xotl.fl.ast.base.AST)

class xotl.fl.ast.expressions.Application(e1: xotl.fl.ast.base.AST, e2: xotl.fl.ast.base.AST)

class xotl.fl.ast.expressions.Let(bindings: Mapping[str, xotl.fl.ast.base.AST], body: xotl.fl.ast.base.AST, localenv: Mapping[Union[str, xotl.fl.meta.Symbol], xotl.fl.ast.types.TypeScheme] = None)

class xotl.fl.ast.expressions.Letrec(bindings: Mapping[str, xotl.fl.ast.base.AST], body: xotl.fl.ast.base.AST, localenv: Mapping[Union[str, xotl.fl.meta.Symbol], xotl.fl.ast.types.TypeScheme] = None)

Pattern matching and value definitions

The parser does not parse directly to Let or Letrec, because those AST nodes does not support constructions for pattern matching.

class xotl.fl.ast.pattern.ConcreteLet(definitions: Sequence[Union[xotl.fl.ast.pattern.Equation, Mapping[Union[str, xotl.fl.meta.Symbol], xotl.fl.ast.types.TypeScheme]]], body: xotl.fl.ast.base.AST)

The concrete representation of a let/where expression.

class xotl.fl.ast.pattern.Equation(name: str, patterns: Sequence[Union[str, xotl.fl.ast.expressions.Literal, ConsPattern, NamedPattern]], body: xotl.fl.ast.base.AST)

The syntactical notion of an equation.

class xotl.fl.ast.pattern.ConsPattern(cons: str, params: Sequence[Union[str, xotl.fl.ast.expressions.Literal, ConsPattern, NamedPattern]] = None)

The syntactical notion of a pattern.

Data types

The following objects are used in the parser while recognizing the program.

class xotl.fl.ast.adt.DataType(name: str, type_: xotl.fl.ast.types.TypeCons, defs: Sequence[xotl.fl.ast.adt.DataCons], derivations: Sequence[str] = None)

A data type definition.

A data type defines both a type and several values of that type.

You should note that DataCons is NOT a value. Therefore these are not actual objects carrying values in the running program; but imply the compiler (or interpreter) must produce those values and match the type.

full_typeenv

Both pattern_matching_env and implied_env together.

implied_env

The implied type environment by the data type.

Each data constructor is a function (or value) of type of the data type.

A simple example is the Bool data type:

>>> from xotl.fl import parse
>>> datatype = parse('data Bool = True | False')[0]
>>> datatype.implied_env
{'True': <TypeScheme: Bool>, 'False': <TypeScheme: Bool>}

Both True and False are just values of type Bool.

The Either data type shows data constructors with parameters:

 >>> datatype = parse('data Either a b = Left a | Right b')[0]
 >>> datatype.implied_env
 {'Left': <TypeScheme: forall a b. a -> (Either a b)>,
  'Right': <TypeScheme: forall a b. b -> (Either a b)>}

Right takes any value of type a and returns a value of type Either a b (for any type b).

pattern_matching_env

The type environment needed to pattern-match the data constructors.

A program like:

data List a = Nil | Cons a (List a)

count Nil = 0
count (Cons x xs) = 1 + (count xs)

Is transformed to the equivalent (I take some liberties to ease reading, this program cannot be parsed):

data List a = Nil | Cons a (List a)

count arg1 = let eq1 eqarg1 = (\x1 -> 0) (:match:Nil: eqarg1)
                 eq2 eqarg1 = (\x -> \xs -> 1 + (count xs))
                              (:extract:Cons:1: eqarg1)
                              (:extract:Cons:2: eqarg1)
        in (eq1 arg1) `:OR:` (eq2 arg1) `:OR:` NO_MATCH

The operator :OR returns the first argument if it is not a pattern-match error; otherwise it returns the second argument. This is a special operator. The :match:Nil:, :extract:Cons:1:, and :extract:Cons:2: match its argument with the expected data constructor and, possibly, extract one of the components.

The pattern_matching_evn returns the type environment of those functions:

 >>> datatype = parse('data List a = Nil | Cons a (List a)')[0]

 >>> datatype.pattern_matching_env
 {<Match: Nil>: <TypeScheme: forall a. List a>,
  <Extract: 1 from Cons>: <TypeScheme: forall a. (List a) -> a>,
  <Extract: 2 from Cons>: <TypeScheme: forall a. (List a) -> (List a)>}

 >>> datatype = parse('data Pair a b = Pair a b')[0]

 >>> datatype.pattern_matching_env
 {<Extract: 1 from Pair>: <TypeScheme: forall a b. (Pair a b) -> a>,
  <Extract: 2 from Pair>: <TypeScheme: forall a b. (Pair a b) -> b>}

 >>> datatype = parse('data Unit = Unit')[0]

 >>> datatype.pattern_matching_env
 {<Match: Unit>: <TypeScheme: Unit>}

Note

The names of those special functions are not strings.

class xotl.fl.ast.adt.DataCons(cons: str, args: Sequence[xotl.fl.ast.types.Type])

The syntactical notion a data constructor in the type language.

Type classes and instances

class xotl.fl.ast.typeclasses.TypeClass(superclasses: Sequence[xotl.fl.ast.types.TypeConstraint], newclass: xotl.fl.ast.types.TypeConstraint, definitions: Sequence[Union[xotl.fl.ast.pattern.Equation, Mapping[Union[str, xotl.fl.meta.Symbol], xotl.fl.ast.types.TypeScheme]]])

class xotl.fl.ast.typeclasses.Instance(constraints: Sequence[xotl.fl.ast.types.TypeConstraint], typeclass_name: str, type_: Union[xotl.fl.ast.types.TypeVariable, xotl.fl.ast.types.TypeCons], definitions: Sequence[Union[xotl.fl.ast.pattern.Equation, Mapping[Union[str, xotl.fl.meta.Symbol], xotl.fl.ast.types.TypeScheme]]])