cucapra / packet-scheduling

MIT License
3 stars 0 forks source link

Add Union Operator; Update AST #69

Closed KabirSamsi closed 2 weeks ago

KabirSamsi commented 3 weeks ago

Background

55 discusses a need for a modified AST that distinguishes between set-to-stream and stream-to-stream policies, and furthermore distinguishes between sets and streams. Within that, we discuss the need for a Union operator, which effectively 'merges several classes into one'. This is critical in the construction of Set-to-Stream transformers, to allow such polices to arbitrate independent of queue distinctions.

Overview

My work on the type system in #63 allowed us to realize that we could turn typechecking into essentially an abstraction, and have our set and stream types inferred at parsing-time itself – that is to say, with a tweak to the AST and extending it to the parser as well. That's the first part part of the PR, which entails adding in the Union constructor to the AST, and partitioning it into the set and stream types.

Caveat And Explanation

@polybeandip and I discussed how far we thought this change should extend. On one hand, modifying Ast.t contractually requires us to modify Policy.t. An alternative, though, is to simply establish a correspondence Ast.t -> Policy.t. For simplicity and to preserve the work done in control, we have kept Policy.t in its original form, and adapted that correspondence.

In turn, this required modifying almost all of our programs such that they would be syntactically correct w.rt. the new AST structure and parsing mechanisms. In addition, a few extra 'reversions' to allow for parsed programs to be correctly evaluated in control.

KabirSamsi commented 2 weeks ago

@polybeandip Can you approve?