sig
  type t = Lang.ps
  val to_string : Lang.ps -> string
  val marker : Lang.ps -> Lang.var * Lang.expr
  val free_vars : Lang.ps -> Lang.var list
  val make : (Lang.var * Lang.expr) list -> Lang.PS.t
  val height : Lang.ps -> int
  val dim : Lang.ps -> int
  val source : int -> Lang.ps -> Lang.ps
  val target : int -> Lang.ps -> Lang.ps
  val exists : (Lang.var * Lang.expr -> bool) -> Lang.ps -> bool
  val map :
    (Lang.var * Lang.expr -> Lang.var * Lang.expr) -> Lang.ps -> Lang.ps
  val fold_left : ('a -> Lang.var * Lang.expr -> 'a) -> 'a -> Lang.ps -> 'a
  val fold_left2 :
    ('a -> Lang.var * Lang.expr -> Lang.var * Lang.expr -> 'a) ->
    'a -> Lang.ps -> Lang.ps -> 'a
  val fold_right : (Lang.var * Lang.expr -> 'a -> 'a) -> Lang.ps -> 'a -> 'a
end