[DSL] Incorporating assignments in the AST

Our DSL is coming along nicely (see #25) but I have requested @csziklai to drop the assignment operator from there. I think it's a little subtle, so here's a little discussion of how it may need to be done.

The Issue

The existing attempt is:

type clss = string
type var = string

type declare =
  | DeclareClasses of clss list

type policy =
  | Class of clss
  | Fifo of policy list
  | Fair of policy list
  | Strict of policy list
  | Assn of var * policy (* I have my doubts *)
  | Return of policy
  | Seq of policy * policy

And I presume the grand finale will be

type program = Prog of declare * policy

This looks close, but I think assignments cannot be a policy-constructor in quite that way. Here's the issue. We want the user to be able to write:

p = Strict(A,B);
return RR(p, C)

but I think the AST above will force the user to write:

p = Strict(A,B);
return RR(p = Strict(A,B), C)

or something like that. This is because assignments are trying to hang around as policies, and simply stating a variable's name (like we'd need to do, to get return RR(p, C) to work) is not currently a legal policy.

The Fix

I actually think that policy needs a constructor that is just a variable, like so:

type policy =
  | Class of clss
  | Fifo of policy list
  | Fair of policy list
  | Strict of policy list
  (*  | Assn of var * policy *) (* removed *)
  | Var of var   (* new *)
  (* return and seq removed; explanation below *)

and we need a separate type for assignments:

type assignment = Assn of var * policy

Now we need a slightly higher-order thing that lets these two things intermix. I define a statement to be either an assignment, or a sequence, or a return. The return constructor will return a policy.

type statement = 
  | Assignment of assignment 
  | Seq of statement * statement 
  | Return of policy

Note, putting sequences and returns into policy will again pose an issue I think! I think those need to operate on statements so that they can intermix policies and assignments.

And finally a program is:

type program = Prog of declare * statement

Usage

Now the user needs to use this AST correctly. If they have:

classes A, B, C;
p = Strict(A, B);
return RR(q, C)

then we should give up because q is undefined.

But I think this is no different than other forms of checking that the user behaved correctly. For instance, we also need to give up in case the user did not end with a return statement.

I'm kinda down to the wire with this comment before we meet synchronously, but I just wanted to write that this is exactly right! That is, the "normal" way to do this (and the clearly correct one, IMO) is to have assignments be a "top-level" construct that cannot appear in more deeply nested expressions.

@anshumanmohan's proposal is:

type program = Prog of declare * statement

Which is 100% cool. But another way to flatten it out is:

type program = Prog of declare * (statement list) * return

That is, eliminating the Seq constructor in favor of a flat list, and making sure that there is exactly one return (it does not make sense for there to be more than one). But this is a small difference and either can work.

cucapra / packet-scheduling