Upstreaming middlend passes

[zilinc]

I'm trying to sync with upstream, but running into some merge conflicts in the middle-end. Would it be reasonable to merge some of the major changes to the middle-end to the upstream repo? For example, the middle-end passes in this repo have moved to a generic transformer style (#212), whereas in the spec repo, it's still defining its own AST traversals in each individual pass. There've been a lot more passes here, and it's okay if we want to hold back on those. For the other changes that have happened in the passes that are also used in the spec repo (i.e. sideconditions, unthe, sub, and totalize), are they supposed to work with the spec repo, or are there anything that are specific to this repo?

@rossberg @DCupello1 any opinions?

[rossberg]

The less difference between the two repos the better. I had trouble downstreaming some middlend changes before. If somebody volunteers to create a PR to upstream some stuff, I'm all for it.

As an aside, I'm not super happy with the schism in traversal modules — I think walk.ml and iter.ml should be combined into one module with a more unified interface for the different traversals.

[DCupello1]

I don't mind me syncing to upstream some of the middlend changes, especially since I should have done it earlier. If it makes everyone's life easier, it should be done.

Agree with the sentiment on iter and walk, but how should the unified interface be?

[rossberg]

Agree with the sentiment on iter and walk, but how should the unified interface be?

I'd prefer a functorised interface over big function records, since that's more idiomatic for Ocaml. My suggestion would be for them to share a common parameter signature derived from iter/Arg:

module type Visitor =
sig
  type 'a t
  type scope

  val visit_atom : atom t
  val visit_mixop : mixop t
  val visit_typid : id t
  val visit_relid : id t
  val visit_ruleid : id t
  val visit_varid : id t
  val visit_defid : id t
  val visit_gramid : id t

  val visit_typ : typ t
  val visit_deftyp : deftyp t
  val visit_exp : exp t
  val visit_path : path t
  val visit_sym : sym t
  val visit_prem : prem t
  val visit_def : def t

  val visit_hint : hint t

  val scope_enter : id -> typ -> scope
  val scope_exit : id -> scope -> unit
end

where 'a t is instantiated accordingly for each traversal, e.g.:

module type IterVisitor = Visitor with type 'a t = 'a -> unit
module type MapVisitor = Visitor with type 'a t = 'a -> 'a       (* what's called transform right now *)
module type CollectVisitor =
sig
  type collection
  val combine : collection -> collection -> collection
  include Visitor with type 'a t = 'a -> collection * bool
end

We could also consider generalising Collect to a proper Fold with type 'a t = collection * 'a -> collection * bool. That would have the advantage that it's more general and at the same time the combine function isn't needed.

(The traversal signatures could be shared in a similar manner, in case we want to make them explicit.)