# match-compiler.api
#
# A simple pattern matching compiler.
# This one uses Mikael Pettersson's algorithm.
#
# NOTE: This module is completely detached
# from the rest of the infrastructure, so
# that it can be reused.
# Compiled by:
# src/lib/compiler/back/low/tools/match-compiler.lib### "There are always alternatives."
###
### -- Spock, "The Galileo Seven," "Star Trek"
api Match_Compiler {
# These are client defined types
package guard: api { Guard;
to_string: Guard -> String;
};
package expression: api { Expression;
to_string: Expression -> String;
};
package action: api { Action; };
package con: api { Con; compare: (Con, Con) -> Order; };
package literal: api { Literal;
compare: (Literal, Literal) -> Order;
};
package variable: api { Var; };
# These are new types
Index = INT Int | LABEL variable::Var;
Path = PATH List( Index );
package path
:
api { compare: (Path, Path) -> Order;
to_string: Path -> String;
to_ident: Path -> String;
dot: (Path, Index) -> Path;
package map: Map # Map is from src/lib/src/map.api where key::Key == Path;
};
Name = VAR variable::Var | PVAR Path;
package subst
:
Map # Map is from src/lib/src/map.api where
key::Key == variable::Var;
Pattern;
Subst = subst::Map( Name );
Decon
= CON con::Con # Match a user constructor.
| LIT literal::Literal; # Match a user literal.
exception MATCH_COMPILER String;
Compiled_Dfa; # Compiled pattern matching dfa
Compiled_Rule;
Rule_Number = Int;
Compiled_Pat;
# Compile a user pattern into internal pattern form;
# This function abstracts out the computation of paths and namings.
rename
:
( { id_pattern: variable::Var -> Compiled_Pat,
as_pattern: (variable::Var, A_pattern) -> Compiled_Pat,
wild_pattern: Void -> Compiled_Pat,
cons_pattern: (con::Con, List( A_pattern )) -> Compiled_Pat,
tuple_pattern: List( A_pattern ) -> Compiled_Pat,
record_pattern: List( (variable::Var, A_pattern) ) -> Compiled_Pat,
lit_pattern: literal::Literal -> Compiled_Pat,
# logical connectives and other extensions to the standard
or_pattern: List( A_pattern ) -> Compiled_Pat,
and_pattern: List( A_pattern ) -> Compiled_Pat,
not_pattern: A_pattern -> Compiled_Pat,
where_pattern: (A_pattern, guard::Guard) -> Compiled_Pat,
nested_pattern: (A_pattern, ((Int, expression::Expression)), A_pattern) -> Compiled_Pat
}
-> A_pattern
-> Compiled_Pat
)
->
{ number: Rule_Number, # rule number
patterns: List( A_pattern ), # the pattern
guard: Null_Or( guard::Guard ), # optional guard
action: action::Action, # Action
match_fail_exception: Null_Or( variable::Var ) # Currently ignored. See comments for MATCH_FAIL_EXCEPTION_IN_EXPRESSION in src/lib/compiler/back/low/tools/adl-syntax/adl-raw-syntax-form.api }
->
Compiled_Rule;
# Compile a set of canonical rules into a dfa
compile
:
{ compiled_rules: List( Compiled_Rule ),
compress: Bool
}
->
Compiled_Dfa;
exhaustive: Compiled_Dfa -> Bool;
redundant: Compiled_Dfa -> int_list_set::Set;
# For debugging
to_string: Compiled_Dfa -> String;
# Generate code for a compiled dfa.
# Assumes an ML-like language:
code_gen
:
{ gen_fail: Void -> expression::Expression,
gen_ok: action::Action -> expression::Expression,
gen_path: Path -> expression::Expression,
gen_bind: List ((variable::Var, expression::Expression)) -> List( A_decl ),
gen_case: (variable::Var, List ((Decon, List( Null_Or( Path ) ), expression::Expression)),
Null_Or( expression::Expression )) -> expression::Expression,
gen_if: (guard::Guard, expression::Expression, expression::Expression) -> expression::Expression,
gen_goto: (Int, List( variable::Var )) -> expression::Expression, # Call a function
gen_fun: (Int, List( variable::Var ), expression::Expression) -> A_decl, # function def
gen_cont: (variable::Var, Int, List( variable::Var )) -> A_decl,
gen_let: (List( A_decl ), expression::Expression) -> expression::Expression,
gen_variable: Path -> variable::Var,
gen_val: (variable::Var, expression::Expression) -> A_decl,
gen_proj: (Path, List( (Null_Or( Path ), Index))) -> A_decl
}
->
((expression::Expression, Compiled_Dfa))
->
expression::Expression;
};