package lambdapi
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=2c251021b6fac40c05282ca183902da5b1008e69d9179d7a9543905c2c21a28a
sha512=69535f92766e6fedc2675fc214f0fb699bde2a06aa91d338c93c99756235a293cf16776f6328973dda07cf2ad402e58fe3104a08f1a896990c1778b42f7f9fcf
doc/lambdapi.core/Core/Eval/index.html
Module Core.Eval
Source
Evaluation and conversion.
Preliminary remarks. We define the head-structure of a term t as:
- λx:_,h if t=λx:a,u and h is the head-structure of u
- Π if t=Πx:a,u
- h _ if t=uv and h is the head-structure of u
- ? if t=?M.
t1;...;tn
(and ?M is not instantiated) - t itself otherwise (TYPE, KIND, x, f)
A term t is in head-normal form (hnf) if its head-structure is invariant by reduction.
A term t is in weak head-normal form (whnf) if it is an abstraction or if it is in hnf. In particular, a term in head-normal form is in weak head-normal form.
A term t is in strong normal form (snf) if it cannot be reduced further.
Flag indicating whether eta-reduction should be used or not.
type rw_tag = [
| `NoBeta
(*If true, no beta-reduction is performed.
*)| `NoRw
(*If true, no user-defined rewrite rule is used.
*)| `NoExpand
(*If true, definitions are not expanded.
*)
]
Tags for rewriting configuration.
Functions that use the rewriting engine and accept an optional argument tags
of type rw_tag list
have the following behaviour.
- If the argument is not given, then no tag is active and the rewrite engine is not constrained: it uses user defined reduction rules, it expands variable definitions (that are stored in the
ctxt
) and performs beta reductions. - Each tag if present disables some functionality of the rewrite engine. The descriptions of the functionalities are given in the documentation of
rw_tag
.
Reduction functions also accept an optional problem
that is used to store metavariables that may be created while rewriting. Such metavariables may be created by particular rewrite rules (such as unification rules), but not by rules declared with rule t ↪ u;
.
NOTE that all reduction functions, and eq_modulo
, may reduce in-place some subterms of the reduced term.
whnf ?tags c t
computes a whnf of the term t
in context c
.
eq_modulo c a b
tests the convertibility of a
and b
in context c
.
pure_eq_modulo c a b
tests the convertibility of a
and b
in context c
with no side effects.
val snf :
?dtree:(Term.sym -> Term.dtree) ->
?tags:rw_tag list ->
Term.ctxt ->
Term.term ->
Term.term
snf ~dtree c t
computes a snf of t
, unfolding the variables defined in the context c
. The function dtree
maps symbols to dtrees.
hnf ?tags c t
computes a head-normal form of the term t
in context c
.
simplify t
computes a beta whnf of t
belonging to the set S such that:
- terms of S are in beta whnf normal format
- if
t
is a product, then both its domain and codomain are in S.
If s
is a non-opaque symbol having a definition, unfold_sym s t
replaces in t
all the occurrences of s
by its definition.
Dedukti evaluation strategies.