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.2.0.tbz
sha256=920de48ec6c2c3223b6b93879bb65d07ea24aa27f7f7176b3de16e5e467b9939
sha512=135f132730825adeb084669222e68bc999de97b12378fae6abcd9f91ae13093eab29fa49c854adb28d064d52c9890c0f5c8ff9d47a9916f66fe5e0fba3479759

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=?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.

Sourceval eta_equality : bool Timed.ref

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

Sourcetype rw_tag = [
  1. | `NoBeta
    (*

    If true, no beta-reduction is performed.

    *)
  2. | `NoRw
    (*

    If true, no user-defined rewrite rule is used.

    *)
  3. | `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.

Sourceval whnf : ?problem:Term.problem -> ?tags:rw_tag list -> Term.ctxt -> Term.term -> Term.term

whnf ?problem ?tags c t computes a whnf of the term t in context c.

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.

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.

Sourceval snf : ?problem:Term.problem -> ?tags:rw_tag list -> Term.ctxt -> Term.term -> Term.term

snf ?problem ?tags c t computes the strong normal form of the term t in the context c.

Sourceval hnf : ?problem:Term.problem -> ?tags:rw_tag list -> Term.ctxt -> Term.term -> Term.term

hnf ?problem ?tags c t computes a head-normal form of the term t in 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.