package lambdapi

  1. Overview
  2. Docs
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Export.HrsSource

This module provides a function to translate a signature to the HRS format used in the confluence competition.

  • Lambdapi terms are translated to the following HRS term algebra with a unique type t:

A : t -> t -> t // for application

L : t -> (t -> t) -> t // for λ

B : t -> t -> (t -> t) -> t // for let

P : t -> (t -> t) -> t // for Π

Function symbols and variables are translated as symbols of type t.

Pattern variables of arity n are translated as variables of type t -> ... -> t with n times ->.

  • In the hrs format, variable names must be distinct from function symbol names. So bound variables are translated into positive integers and pattern variables are prefixed by "$".
  • There is no clash between function symbol names and A, B, L, P because function symbol names are fully qualified.
  • Function symbol names are fully qualified but "." is replaced by "_" because "." cannot be used in identifiers ("." is used in lambda abstractions).
  • Two occurrences of the same pattern variable name may have two different arities (in two different rules). So pattern variable names are prefixed by the rule number.

TO DO:

  • HRS does not accept unicode characters.
  • Optim: output only the symbols used in the rules.
Sourceval syms : string Core.Term.SymMap.t ref

syms maps every symbol to a name.

bvars is the set of abstracted variables.

Sourceval nb_rules : int ref

nb_rules is the number of rewrite rules.

Sourcemodule V : sig ... end

pvars map every pattern variable name to its arity.

Sourcemodule VMap : sig ... end
Sourceval pvars : int VMap.t ref

sym_name s translates the symbol name of s.

Sourceval add_sym : Core.Term.sym -> unit

add_sym declares a Lambdapi symbol.

sym ppf s translates the Lambdapi symbol s.

Sourceval add_bvar : Core.Term.tvar -> unit

add_bvar v declares an abstracted Lambdapi variable.

bvar v translates the Lambdapi variable v.

Sourceval pvar : int Lplib.Base.pp

pvar i translates the pattern variable index i.

Sourceval add_pvar : int -> int -> unit

add_pvar i k declares a pvar of index i and arity k.

term ppf t translates the term t.

rule ppf r translates the pair of terms r as a rule.

sym_rule ppf s r increases the number of rules and translates the sym_rule r.

Translate the rules of symbol s.

Sourceval rules_of_sign : Core.Sign.t Lplib.Base.pp

Translate the rules of a dependency except if it is a ghost signature.

sign ppf s translates the Lambdapi signature s.

OCaml

Innovation. Community. Security.