Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
package dedukti
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
include Reduction.ConvChecker
val are_convertible : Reduction.convertibility_testare_convertible sg t1 t2 checks whether t1 and t2 are convertible or not in the signature sg.
val constraint_convertibility :
Rule.constr ->
Rule.rule_name ->
Reduction.convertibility_testconstraint_convertibility cstr r sg [t1] [t2] checks wehther the [cstr] of the rule [r]
is satisfiable. Because constraints are checked once a term has matched the pattern,
satisfying a constraint comes back to check that two terms are convertible
val reduction : Reduction.red_cfg -> Signature.t -> Term.term -> Term.termreduction cfg sg te reduces the term te following the configuration cfg and using the signature sg.
val whnf : Signature.t -> Term.term -> Term.termwhnf sg t returns the Weak Head Normal Form of t.
Definition: a term is in weak-head-normal form if there is a reduction strategy such that all its reducts following this strategy (including itself) have the same 'shape' at the root.
The shape of a term could be computed like this:
let rec shape = function | Type -> Type | Kind -> Kind | Pi _ -> Pi | Lam _ -> Lam | DB (_,_,n) -> DB n | Const (_,m,v) -> Const m v | App(f,a0,args) -> App (shape f,List.length (a0::args))
Property: A (strongly normalizing) non weak-head-normal term can only have the form:
- (x:A => b) a c_1..c_n, this is a beta-redex potentially with extra arguments.
- or c a_1 .. a_n b_1 ..b_n with c a constant and c a'_1 .. a'_n is a gamma-redex where the (a'_i)s are reducts of (a_i)s.
val snf : Signature.t -> Term.term -> Term.termsng sg t returns the Strong Normal Form of t. This may loop whenever t is not strongly normalizing.