probl_sema/
ir.rs

1//! The intermediate representation run by the engine.
2//!
3//! Control flow stays structured (blocks, `if`, `chance`, loops). The key
4//! property is that **expressions never split worlds**: everything that can
5//! (draws, calls to user functions, `if`/`chance`/`match` used as values) has
6//! been moved into a statement of its own by the lowering pass. Expressions
7//! can therefore be evaluated independently in each world.
8
9use crate::builtins::Builtin;
10use probl_syntax::Span;
11use probl_syntax::ast::{BinOp, UnOp};
12
13pub type SlotId = u32;
14pub type FnId = u32;
15pub type StmtId = u32;
16
17/// The function holding the top-level statements.
18pub const MAIN: FnId = 0;
19
20/// The name of compiler-generated variables. Each is assigned once per path
21/// and never changed afterwards.
22pub const TEMP: &str = "(temporary)";
23
24#[derive(Debug)]
25pub struct Program {
26    /// `functions[MAIN]` is the top level; its slots include the globals.
27    pub functions: Vec<Function>,
28    pub reports: Vec<ReportSite>,
29    pub records: Vec<RecordType>,
30    pub enums: Vec<EnumType>,
31    /// The data the program reads: whoever runs it loads these first.
32    pub inputs: Vec<Input>,
33    pub settings: Settings,
34    /// Number of statements; statement ids are `0..stmt_count`.
35    pub stmt_count: u32,
36}
37
38/// Data a program reads, `let name: T = read("path")` (docs/data-input.md).
39/// The program's list of these is its manifest: whoever runs the program
40/// loads each input before running it, and the engine only sees the values.
41#[derive(Clone, Debug, PartialEq)]
42pub struct Input {
43    /// The variable it's bound to, which identifies it.
44    pub name: String,
45    /// As written: relative to the program's file, or `-` for standard
46    /// input. What it means is up to whoever loads it.
47    pub path: String,
48    pub format: DataFormat,
49    /// What the data is read as.
50    pub ty: TypeSpec,
51    /// The `read(…)` call.
52    pub span: Span,
53}
54
55#[derive(Clone, Copy, Debug, PartialEq, Eq)]
56pub enum DataFormat {
57    Csv,
58    Json,
59    Lines,
60}
61
62impl Program {
63    pub fn main(&self) -> &Function {
64        &self.functions[MAIN as usize]
65    }
66}
67
68#[derive(Clone, Debug, PartialEq)]
69pub struct Settings {
70    pub mode: Mode,
71    /// Where `@mode` was set, for error messages.
72    pub mode_span: Option<Span>,
73    /// Unbounded loops stop once the weight still inside is less than this
74    /// fraction of the weight that entered.
75    pub epsilon: f64,
76    pub max_iterations: u64,
77    pub max_worlds: usize,
78    /// `@on_error`: what a fault in one world does to the others. `None`
79    /// leaves it to the mode (docs/semantics.md, section 11).
80    pub on_error: Option<FailureMode>,
81    /// `@integrate`: when enumerating, compute what has no formula by
82    /// numerical integration, to this relative tolerance (docs/semantics.md,
83    /// section 13). `None` without it.
84    pub integrate: Option<f64>,
85}
86
87/// `@integrate`'s tolerance when it doesn't give one.
88pub const DEFAULT_TOLERANCE: f64 = 1e-9;
89
90impl Default for Settings {
91    fn default() -> Settings {
92        Settings {
93            mode: Mode::Auto,
94            mode_span: None,
95            epsilon: 1e-12,
96            max_iterations: 10_000_000,
97            max_worlds: 10_000_000,
98            on_error: None,
99            integrate: None,
100        }
101    }
102}
103
104/// What a fault in one world does to the others (docs/semantics.md,
105/// section 11). The world that fails always stops there.
106#[derive(Clone, Copy, Debug, PartialEq, Eq)]
107pub enum FailureMode {
108    /// The whole run fails, as it does for any other error.
109    Total,
110    /// The other worlds finish, and the result says what failed.
111    Partial,
112}
113
114impl FailureMode {
115    pub fn name(self) -> &'static str {
116        match self {
117            FailureMode::Total => "total",
118            FailureMode::Partial => "partial",
119        }
120    }
121}
122
123#[derive(Clone, Debug, PartialEq)]
124pub enum Mode {
125    Auto,
126    Enumerate,
127    Beam { worlds: u64 },
128    Sample { runs: u64, seed: u64 },
129    Particles { runs: u64, seed: u64 },
130}
131
132impl Mode {
133    pub fn name(&self) -> &'static str {
134        match self {
135            Mode::Auto => "auto",
136            Mode::Enumerate => "enumerate",
137            Mode::Beam { .. } => "beam",
138            Mode::Sample { .. } => "sample",
139            Mode::Particles { .. } => "particles",
140        }
141    }
142}
143
144#[derive(Clone, Debug)]
145pub struct ReportSite {
146    pub label: String,
147    /// Source text of the `by` expression.
148    pub key_label: Option<String>,
149    pub kind: ReportKind,
150    pub span: Span,
151}
152
153/// How often one world can reach a report (see docs/semantics.md, section 9).
154#[derive(Clone, Copy, Debug, PartialEq, Eq)]
155pub enum ReportKind {
156    /// Outside loops: at most once per world.
157    Once,
158    /// In a single loop with proven unique iteration keys: at most once per
159    /// world and key, using the loop binding itself.
160    PerKey,
161    /// In a loop with any other key: every visit counts.
162    PerVisit,
163}
164
165#[derive(Clone, Debug)]
166pub struct RecordType {
167    pub name: String,
168    /// In declaration order.
169    pub fields: Vec<RecordField>,
170    pub span: Span,
171}
172
173#[derive(Clone, Debug)]
174pub struct RecordField {
175    pub name: String,
176    pub ty: TypeSpec,
177    pub span: Span,
178}
179
180#[derive(Clone, Debug)]
181pub struct EnumType {
182    pub name: String,
183    pub variants: Vec<String>,
184}
185
186#[derive(Clone, Copy, Debug, PartialEq, Eq)]
187pub enum FnKind {
188    Main,
189    Named,
190    Lambda,
191    Simulate,
192}
193
194#[derive(Clone, Debug)]
195pub struct Function {
196    pub name: String,
197    pub kind: FnKind,
198    pub span: Span,
199    /// Parameters occupy slots `0..n_params`.
200    pub n_params: u32,
201    /// Values copied into the frame on entry, after the parameters.
202    pub captures: Vec<Capture>,
203    pub slots: Vec<SlotInfo>,
204    pub body: Block,
205    pub effects: Effects,
206}
207
208/// What running a function can do besides computing its result, including
209/// through the functions it calls.
210#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
211pub struct Effects {
212    /// Runs `observe` (outside any `simulate` block).
213    pub observes: bool,
214    /// Calls `print`. Such functions aren't memoized.
215    pub prints: bool,
216}
217
218impl Function {
219    pub fn n_slots(&self) -> usize {
220        self.slots.len()
221    }
222}
223
224/// What an `Update` checks when `place` is in a variable with a declared
225/// type.
226#[derive(Clone, Debug)]
227pub struct UpdateCheck {
228    /// The variable's declared type, which the whole variable is checked
229    /// against after an assignment.
230    pub ty: TypeSpec,
231    /// The declared types of the method's arguments after the collection,
232    /// when the collection's type is known. Changed in place, checking what
233    /// goes into it is enough.
234    pub args: Option<Vec<Option<TypeSpec>>>,
235}
236
237#[derive(Clone, Copy, Debug, PartialEq, Eq)]
238pub struct Capture {
239    /// Where the value goes in this function's frame.
240    pub slot: SlotId,
241    pub source: CaptureSource,
242    /// A global held only for the named functions this function may call
243    /// as values. It may have no value yet; that's an error only if a
244    /// function that reads it is called.
245    pub for_values: bool,
246}
247
248#[derive(Clone, Copy, Debug, PartialEq, Eq)]
249pub enum CaptureSource {
250    /// A top-level variable (a slot of the main frame).
251    Global(SlotId),
252    /// A variable of the enclosing function (for lambdas and `simulate`).
253    Parent(SlotId),
254}
255
256#[derive(Clone, Debug)]
257pub struct SlotInfo {
258    pub name: String,
259    pub span: Span,
260}
261
262#[derive(Clone, Debug, Default)]
263pub struct Block {
264    pub stmts: Vec<Stmt>,
265}
266
267#[derive(Clone, Debug)]
268pub struct Stmt {
269    pub id: StmtId,
270    pub span: Span,
271    pub kind: StmtKind,
272}
273
274#[derive(Clone, Debug)]
275pub enum StmtKind {
276    /// `place = value`.
277    Set {
278        place: Place,
279        value: Expr,
280    },
281    /// `place = value`, where `value` applies a method that changes a
282    /// collection, like `push`, to `place`. Its meaning is the assignment's;
283    /// the engine changes the collection in place when it can, rather than
284    /// copying it.
285    Update {
286        place: Place,
287        value: Expr,
288        check: Option<UpdateCheck>,
289    },
290    /// `place ~ dist`: one world per outcome.
291    Draw {
292        place: Place,
293        dist: Expr,
294    },
295    /// `place = bag.take()`: select an item unchanged and remove one copy.
296    Take {
297        place: Place,
298        bag: Place,
299    },
300    /// Call a user function or closure; may split worlds.
301    Call {
302        dest: Place,
303        callee: Callee,
304        args: Vec<Expr>,
305    },
306    If {
307        cond: Expr,
308        then: Block,
309        otherwise: Block,
310    },
311    /// Weighted branches. Without `otherwise`, the remaining weight either
312    /// continues past the statement (`exhaustive: false`) or is an error.
313    Chance {
314        arms: Vec<(Expr, Block)>,
315        otherwise: Option<Block>,
316        exhaustive: bool,
317    },
318    /// Repeats until every world has left through `break` or `return`.
319    /// Unbounded loops (`while`, `loop`) stop early once the weight still
320    /// inside is negligible; bounded ones (`for`, `repeat`) never do.
321    Loop {
322        body: Block,
323        bounded: bool,
324    },
325    Break,
326    Continue,
327    Return(Expr),
328    Observe {
329        value: Expr,
330        from: Option<Expr>,
331    },
332    Report {
333        site: u32,
334        value: Expr,
335        key: Option<Expr>,
336    },
337    /// A runtime error in every world that reaches it.
338    Fail {
339        message: String,
340    },
341    /// Check that a variable's value matches its declared type.
342    Check {
343        slot: SlotId,
344        ty: TypeSpec,
345    },
346    /// `try { body } catch F { … } catch { … }`: a world whose body faults
347    /// goes on in the first catch that names its fault, or that names none
348    /// (docs/semantics.md, section 11).
349    Try {
350        body: Block,
351        catches: Vec<Catch>,
352    },
353}
354
355/// One `catch` of a `try`.
356#[derive(Clone, Debug)]
357pub struct Catch {
358    /// The fault it catches; `None` catches every fault.
359    pub fault: Option<Fault>,
360    pub body: Block,
361}
362
363impl Catch {
364    pub fn catches(&self, fault: Option<Fault>) -> bool {
365        fault.is_some() && (self.fault.is_none() || self.fault == fault)
366    }
367}
368
369/// A language error that depends on the values a world computes with, not
370/// on the program being wrong: dividing by zero, an index past the end. A
371/// `catch` can name one; in partial mode, one that isn't caught ends only
372/// its world (docs/semantics.md, section 11). Errors that aren't faults
373/// always stop the run.
374#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
375pub enum Fault {
376    /// Division or remainder by zero.
377    DivisionByZero,
378    /// A value outside what an operation is defined for: `sqrt(-1)`,
379    /// `logit(0%)`, a distribution's parameter.
380    DomainError,
381    /// An index past the end.
382    IndexOutOfBounds,
383    /// A key that isn't in a map, or an item that isn't in a bag.
384    MissingKey,
385    /// A collection or a bag with nothing in it, where an element is needed.
386    EmptyCollection,
387    /// An explicit conversion that can't represent the value: `prob(1.5)`.
388    ConversionError,
389    /// A result too large to represent: a float that isn't finite, a date
390    /// out of range.
391    NumericOverflow,
392}
393
394impl Fault {
395    pub const ALL: [Fault; 7] = [
396        Fault::DivisionByZero,
397        Fault::DomainError,
398        Fault::IndexOutOfBounds,
399        Fault::MissingKey,
400        Fault::EmptyCollection,
401        Fault::ConversionError,
402        Fault::NumericOverflow,
403    ];
404
405    /// As a `catch` names it.
406    pub fn name(self) -> &'static str {
407        match self {
408            Fault::DivisionByZero => "DivisionByZero",
409            Fault::DomainError => "DomainError",
410            Fault::IndexOutOfBounds => "IndexOutOfBounds",
411            Fault::MissingKey => "MissingKey",
412            Fault::EmptyCollection => "EmptyCollection",
413            Fault::ConversionError => "ConversionError",
414            Fault::NumericOverflow => "NumericOverflow",
415        }
416    }
417
418    pub fn from_name(name: &str) -> Option<Fault> {
419        Fault::ALL.into_iter().find(|f| f.name() == name)
420    }
421}
422
423/// A declared type, checked when a value is stored.
424#[derive(Clone, Debug, PartialEq)]
425pub enum TypeSpec {
426    Int,
427    Float,
428    Complex,
429    Prob,
430    Bool,
431    Str,
432    Date,
433    Unit,
434    Function,
435    List(Box<TypeSpec>),
436    Map(Box<TypeSpec>, Box<TypeSpec>),
437    Bag(Box<TypeSpec>),
438    Dist(Box<TypeSpec>),
439    Record(u32),
440    Enum(u32),
441    AnonRecord(Vec<(String, TypeSpec)>),
442}
443
444impl TypeSpec {
445    /// How the type is written in source.
446    pub fn describe(&self, program: &Program) -> String {
447        self.describe_in(&program.records, &program.enums)
448    }
449
450    /// How the type is written in source, given the program's types.
451    pub fn describe_in(&self, records: &[RecordType], enums: &[EnumType]) -> String {
452        let describe = |t: &TypeSpec| t.describe_in(records, enums);
453        match self {
454            TypeSpec::Int => "int".into(),
455            TypeSpec::Float => "float".into(),
456            TypeSpec::Complex => "complex".into(),
457            TypeSpec::Prob => "prob".into(),
458            TypeSpec::Bool => "bool".into(),
459            TypeSpec::Str => "str".into(),
460            TypeSpec::Date => "date".into(),
461            TypeSpec::Unit => "()".into(),
462            TypeSpec::Function => "fn".into(),
463            TypeSpec::List(t) => format!("list[{}]", describe(t)),
464            TypeSpec::Map(k, v) => format!("map[{}, {}]", describe(k), describe(v)),
465            TypeSpec::Bag(t) => format!("bag[{}]", describe(t)),
466            TypeSpec::Dist(t) => format!("dist[{}]", describe(t)),
467            TypeSpec::Record(r) => records[*r as usize].name.clone(),
468            TypeSpec::Enum(e) => enums[*e as usize].name.clone(),
469            TypeSpec::AnonRecord(fields) => {
470                let fields: Vec<String> = fields.iter().map(|(n, t)| format!("{n}: {}", describe(t))).collect();
471                format!("{{ {} }}", fields.join(", "))
472            }
473        }
474    }
475}
476
477/// A variable, optionally followed by fields and indices: `a.b[i]`.
478#[derive(Clone, Debug)]
479pub struct Place {
480    pub slot: SlotId,
481    pub path: Vec<PathElem>,
482}
483
484impl Place {
485    pub fn slot(slot: SlotId) -> Place {
486        Place { slot, path: Vec::new() }
487    }
488}
489
490#[derive(Clone, Debug)]
491pub enum PathElem {
492    Field(String),
493    Index(Expr),
494}
495
496#[derive(Clone, Debug)]
497pub enum Callee {
498    /// A named function; `capture_args[i]` is the caller's slot supplying the
499    /// callee's `captures[i]`.
500    Fn { func: FnId, capture_args: Vec<SlotId> },
501    /// A function value; names correspond to the final call arguments.
502    Value(Expr, Vec<String>),
503}
504
505#[derive(Clone, Debug)]
506pub struct Expr {
507    pub kind: ExprKind,
508    pub span: Span,
509}
510
511#[derive(Clone, Debug)]
512pub enum ExprKind {
513    Lit(Lit),
514    Slot(SlotId),
515    Unary(UnOp, Box<Expr>),
516    /// All binary operators, including `and` and `or` (whose right side never
517    /// contains hoisted statements, so it can be evaluated lazily).
518    Binary(BinOp, Box<Expr>, Box<Expr>),
519    List(Vec<Expr>),
520    Map(Vec<(Expr, Expr)>),
521    Record {
522        ty: Option<u32>,
523        fields: Vec<(String, Expr)>,
524    },
525    Field(Box<Expr>, String),
526    Index(Box<Expr>, Box<Expr>),
527    With(Box<Expr>, Vec<(String, Expr)>),
528    Builtin {
529        func: Builtin,
530        args: Vec<Expr>,
531        named: Vec<(String, Expr)>,
532    },
533    /// Create a closure; `capture_args` align with the lambda's captures.
534    Closure {
535        func: FnId,
536        capture_args: Vec<SlotId>,
537    },
538    /// Run a `simulate` block and return its distribution.
539    Simulate {
540        func: FnId,
541        capture_args: Vec<SlotId>,
542    },
543    /// `value`, about to be called, or passed to a built-in that calls it.
544    /// If it's a named function, it reads the globals it uses now, as a
545    /// call by name does, rather than when it was referred to: `globals`
546    /// pairs each global (a slot of the main frame), in order, with the slot
547    /// of this frame that holds it.
548    Bind {
549        value: Box<Expr>,
550        globals: Vec<(SlotId, SlotId)>,
551    },
552    Interp(Vec<InterpPart>),
553    /// The value of the program's input with this number (`read`).
554    Input(u32),
555}
556
557#[derive(Clone, Debug)]
558pub enum InterpPart {
559    Lit(String),
560    Expr(Expr),
561}
562
563#[derive(Clone, Debug, PartialEq)]
564pub enum Lit {
565    Builtin(Builtin),
566    Unit,
567    Bool(bool),
568    Int(probl_number::Integer),
569    Float(f64),
570    /// A named mathematical constant: numeric, but not a source literal
571    /// eligible for contextual conversion to `prob`.
572    FloatConstant(f64),
573    Prob(f64),
574    Str(String),
575    Dice {
576        count: u32,
577        sides: u32,
578    },
579    Enum {
580        ty: u32,
581        variant: u32,
582    },
583}
probl_sema/ir.rs

probl_sema/
ir.rs
