(* * Env library * Copyright (C) 2006 Julien SIGNOLES * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public * License version 2, as published by the Free Software Foundation. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * * See the GNU Library General Public License version 2 for more details *) (** This library defines generic environments used to deal with symbolic manipulation. An environment contain a stack of tables (often 1 or 2) mapping keys (usually identifiers) to values. Each table is whether a persistent (i.e. immutable) suited to represent local context or an imperative (i.e. mutable) datastructure suited to represent global context. For example, in a simplified caml language, there is global (let) and local (let in) definitions. Typing requires an environment mapping identifier to types. This environnement contains an imperative table for the global context and, for each declaration, a persistent table (on the top of the stack) for the local context: if you search a value, first check the local context and, if the value is not found, check the global one. *) (** Signature of keys: input signature of the functor [Make]. *) module type COMPARABLE = sig type t val compare: t -> t -> int val equal: t -> t -> bool val hash: t -> int end (** Signature of an environment: output signature of the functor [Make]. *) module type S = sig (** {1 Datatypes} *) (** Type of keys. *) type key (** A table in an environment may be wether persistent (i.e. immutable) or imperative (i.e. mutable). An imperative table is more efficient but a persistent one is useful for backtracking. *) type kind = Persistent | Imperative (** Type of an environment containing values of type ['a]. *) type 'a t (** {1 Global operations} *) (** Create a new environment containing one table of the specified kind. *) val create: kind -> 'a t (** Check emptyness of an environment. *) val is_empty: 'a t -> bool (** Copy of an environment. No sharing between the environment and its copy. *) val copy: 'a t -> 'a t (** {1 Operations on keys} *) (** [add key data env] maps [key] to [data] in the table [t] on the top of [env]. The previous binding of [key] in [t] disappears and the current binding of [key] in [env], if any, is simply hidden. That is, after performing [remove key env] or [pop env], this binding is restored (it is again visible). Raise [Empty] if [env] contains no table. *) val add: key -> 'a -> 'a t -> 'a t (** [remove key env] removes the current binding of [key] in [env], restoring the previous binding of [key], if it exists. It does nothing if [key] is unbound in [env]. *) val remove: key -> 'a t -> 'a t (** [find key env] returns the current binding of [key] in [env]. Raise [Not_found] if no such binding exists. *) val find: key -> 'a t -> 'a (** [find_all key env] returns the list of all data associated with [key] in [env]. The current binding is returned first, then the previous bindings, in reverse order of introduction in the environment. *) val find_all: key -> 'a t -> 'a list (** [mem key env] checks if [key] is bound in [env]. *) val mem: key -> 'a t -> bool (** {1 Iterators} *) (** [iter f env] applies f to all current bindings in [env]. [f] receives the key as first argument, and the associated value as second argument. Each binding is presented exactly once to f. The order in which the bindings are passed to [f] is unspecified. *) val iter: (key -> 'a -> unit) -> 'a t -> unit (** [iter_all f env] is similar to [iter f env] but applies [f] to all bindings in [env] (and not only to the current bindings). Morever, if the environment contains several bindings for the same key, they are passed to [f] in reverse order of introduction, that is, the most recent binding is passed first. *) val iter_all: (key -> 'a -> unit) -> 'a t -> unit (** [fold f env init] computes [f kN dN ... (f k1 d1 init) ...], where [k1 ... kN] are the keys of all current bindings in [env], and [d1 ... dN] are the associated values. Each binding is presented exactly once to [f]. The order in which the bindings are passed to [f] is unspecified. *) val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b (** [fold_all f env init] is similar to [fold f env] but applies [f] to all bindings in [env] (and not only to the current bindings). Morever, if the environment contains several bindings for the same key, they are passed to [f] in reverse order of introduction, that is, the most recent binding is passed first. *) val fold_all: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b (** {1 Operations on tables} *) exception Empty (** [push k env] returns a new environment with a new table of the specified kind on the top of [env]. *) val push: kind -> 'a t -> 'a t (** [pop env] returns a new environment which is [env] without the top table. The bindings hidde by the popped table are restored. Raise [Empty] if [env] contains no table. Be aware of sharing if you use imperative tables. *) val pop: 'a t -> 'a t (** [top env] returns an environment containing only the table on the top of [env]. Raise [Empty] if [env] contains no table. Be aware of sharing if you use imperative tables. *) val top: 'a t -> 'a t end (** Build an implementation of an environment given an ordered and hashable type. *) module Make(Key : COMPARABLE) : S with type key = Key.t (** {1 Generic version} *) (** This version may be used if you have optimised data structures dealing with your keys, e.g. patricia trees. *) (** Signature of maps of keys (subtype of Map.S) *) module type MAP = sig type key type 'a t val empty: 'a t val is_empty: 'a t -> bool val add: key -> 'a -> 'a t -> 'a t val remove: key -> 'a t -> 'a t val find: key -> 'a t -> 'a val mem: key -> 'a t -> bool val iter: (key -> 'a -> unit) -> 'a t -> unit val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b end (** Signature of hashtbl of keys (subtype of Hashtbl.S) *) module type HASHTBL = sig type key type 'a t val create: int -> 'a t val length: 'a t -> int val add: 'a t -> key -> 'a -> unit val remove: 'a t -> key -> unit val find: 'a t -> key -> 'a val find_all: 'a t -> key -> 'a list val mem: 'a t -> key -> bool val iter: (key -> 'a -> unit) -> 'a t -> unit val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b end (** Build an implementation of an environment given an implementation of maps and hashtables. *) module Build(Map : MAP)(Hashtbl : HASHTBL with type key = Map.key) : S with type key = Map.key

*This document was generated using
caml2html*