package lambdapi

  1. Overview
  2. Docs
Proof assistant for the λΠ-calculus modulo rewriting

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (12)

Authors

  1. D
    Deducteam

Maintainers

  1. D
    dedukti-dev@inria.fr

Sources

lambdapi-2.0.0.tbz
sha256=66d7d29f7a0d10493b8178c4c3aeb247971e24fab3eba1c54887e1b9a82fe005
sha512=69ecf2406e4c7225ab7f8ebe11624db5d2ab989c8f30f5b6e5d426fd8ef9102f142a2840af16fb9103bb712ebcf7d314635f8b413a05df66e7b7a38548867032

doc/lambdapi.core/Core/Eval/index.html

Module Core.EvalSource

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=?Mt1,..,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 abstration 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.

Sourceval eta_equality : bool Timed.ref

Flag indicating whether eta-reduction should be used or not.

Sourcetype stack = Term.term list

Abstract machine stack.

Sourceval tree_walk : Term.problem -> Term.ctxt -> Term.dtree -> stack -> (Term.term * stack) option

tree_walk p tr ctx stk tries to apply a rewrite rule by matching the stack stk against the decision tree tr in context ctx. The resulting state of the abstract machine is returned in case of success. Even if matching fails, the stack stk may be imperatively updated since a reduction step taken in elements of the stack is preserved (this is done using TRef). Fresh metavariables generated by unification rules with extra pattern variables are added in p.

Sourceval whnf : ?rewrite:bool -> Term.ctxt -> Term.term -> Term.term

whnf ~rewrite c t computes a whnf of the term t in context c. User-defined rewrite rules are used only if ~rewrite = true.

Sourceval eq_modulo : Term.ctxt -> Term.term -> Term.term -> bool

eq_modulo c a b tests the convertibility of a and b in context c. WARNING: may have side effects in TRef's introduced by whnf.

Sourceval pure_eq_modulo : Term.ctxt -> Term.term -> Term.term -> bool

pure_eq_modulo c a b tests the convertibility of a and b in context c with no side effects.

snf c t computes the strong normal form of the term t in the context c. It unfolds variables defined in the context c.

hnf t computes a head-normal form of the term t wrt beta-reduction, user-defined rewrite rules and variables defined in the context c.

Sourceval simplify : Term.term -> Term.term

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.
Sourceval unfold_sym : Term.sym -> Term.term -> Term.term

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.

Sourcetype strategy =
  1. | WHNF
    (*

    Reduce to weak head-normal form.

    *)
  2. | HNF
    (*

    Reduce to head-normal form.

    *)
  3. | SNF
    (*

    Reduce to strong normal form.

    *)
  4. | NONE
    (*

    Do nothing.

    *)

Dedukti evaluation strategies.

Sourcetype strat = {
  1. strategy : strategy;
    (*

    Evaluation strategy.

    *)
  2. steps : int option;
    (*

    Max number of steps if given.

    *)
}

eval s c t evaluates the term t in the context c according to strategy s.