package dedukti
Install
Dune Dependency
Authors
Maintainers
Sources
sha512=97171b48dd96043d84587581d72edb442f63e7b5ac1695771aa1c3c9074739e15bc7d17678fedb7062acbf403a0bf323d97485c31b92376b80c63b5c2300ee3c
sha256=5e1b6a859dfa1eb2098947a99c7d11ee450f750d96da1720f4834e1505d1096c
doc/dedukti.kernel/Kernel/Reduction/module-type-S/index.html
Module type Reduction.SSource
include ConvChecker
val are_convertible : 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 ->
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 : 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.