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}
82
83impl Default for Settings {
84    fn default() -> Settings {
85        Settings {
86            mode: Mode::Auto,
87            mode_span: None,
88            epsilon: 1e-12,
89            max_iterations: 10_000_000,
90            max_worlds: 10_000_000,
91            on_error: None,
92        }
93    }
94}
95
96/// What a fault in one world does to the others (docs/semantics.md,
97/// section 11). The world that fails always stops there.
98#[derive(Clone, Copy, Debug, PartialEq, Eq)]
99pub enum FailureMode {
100    /// The whole run fails, as it does for any other error.
101    Total,
102    /// The other worlds finish, and the result says what failed.
103    Partial,
104}
105
106impl FailureMode {
107    pub fn name(self) -> &'static str {
108        match self {
109            FailureMode::Total => "total",
110            FailureMode::Partial => "partial",
111        }
112    }
113}
114
115#[derive(Clone, Debug, PartialEq)]
116pub enum Mode {
117    Auto,
118    Enumerate,
119    Beam { worlds: u64 },
120    Sample { runs: u64, seed: u64 },
121    Particles { runs: u64, seed: u64 },
122}
123
124impl Mode {
125    pub fn name(&self) -> &'static str {
126        match self {
127            Mode::Auto => "auto",
128            Mode::Enumerate => "enumerate",
129            Mode::Beam { .. } => "beam",
130            Mode::Sample { .. } => "sample",
131            Mode::Particles { .. } => "particles",
132        }
133    }
134}
135
136#[derive(Clone, Debug)]
137pub struct ReportSite {
138    pub label: String,
139    /// Source text of the `by` expression.
140    pub key_label: Option<String>,
141    pub kind: ReportKind,
142    pub span: Span,
143}
144
145/// How often one world can reach a report (see docs/semantics.md, section 9).
146#[derive(Clone, Copy, Debug, PartialEq, Eq)]
147pub enum ReportKind {
148    /// Outside loops: at most once per world.
149    Once,
150    /// In a single loop with proven unique iteration keys: at most once per
151    /// world and key, using the loop binding itself.
152    PerKey,
153    /// In a loop with any other key: every visit counts.
154    PerVisit,
155}
156
157#[derive(Clone, Debug)]
158pub struct RecordType {
159    pub name: String,
160    /// In declaration order.
161    pub fields: Vec<RecordField>,
162    pub span: Span,
163}
164
165#[derive(Clone, Debug)]
166pub struct RecordField {
167    pub name: String,
168    pub ty: TypeSpec,
169    pub span: Span,
170}
171
172#[derive(Clone, Debug)]
173pub struct EnumType {
174    pub name: String,
175    pub variants: Vec<String>,
176}
177
178#[derive(Clone, Copy, Debug, PartialEq, Eq)]
179pub enum FnKind {
180    Main,
181    Named,
182    Lambda,
183    Simulate,
184}
185
186#[derive(Clone, Debug)]
187pub struct Function {
188    pub name: String,
189    pub kind: FnKind,
190    pub span: Span,
191    /// Parameters occupy slots `0..n_params`.
192    pub n_params: u32,
193    /// Values copied into the frame on entry, after the parameters.
194    pub captures: Vec<Capture>,
195    pub slots: Vec<SlotInfo>,
196    pub body: Block,
197    pub effects: Effects,
198}
199
200/// What running a function can do besides computing its result, including
201/// through the functions it calls.
202#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
203pub struct Effects {
204    /// Runs `observe` (outside any `simulate` block).
205    pub observes: bool,
206    /// Calls `print`. Such functions aren't memoized.
207    pub prints: bool,
208}
209
210impl Function {
211    pub fn n_slots(&self) -> usize {
212        self.slots.len()
213    }
214}
215
216#[derive(Clone, Copy, Debug, PartialEq, Eq)]
217pub struct Capture {
218    /// Where the value goes in this function's frame.
219    pub slot: SlotId,
220    pub source: CaptureSource,
221}
222
223#[derive(Clone, Copy, Debug, PartialEq, Eq)]
224pub enum CaptureSource {
225    /// A top-level variable (a slot of the main frame).
226    Global(SlotId),
227    /// A variable of the enclosing function (for lambdas and `simulate`).
228    Parent(SlotId),
229}
230
231#[derive(Clone, Debug)]
232pub struct SlotInfo {
233    pub name: String,
234    pub span: Span,
235}
236
237#[derive(Clone, Debug, Default)]
238pub struct Block {
239    pub stmts: Vec<Stmt>,
240}
241
242#[derive(Clone, Debug)]
243pub struct Stmt {
244    pub id: StmtId,
245    pub span: Span,
246    pub kind: StmtKind,
247}
248
249#[derive(Clone, Debug)]
250pub enum StmtKind {
251    /// `place = value`.
252    Set {
253        place: Place,
254        value: Expr,
255    },
256    /// `place ~ dist`: one world per outcome.
257    Draw {
258        place: Place,
259        dist: Expr,
260    },
261    /// `place = bag.take()`: select an item unchanged and remove one copy.
262    Take {
263        place: Place,
264        bag: Place,
265    },
266    /// Call a user function or closure; may split worlds.
267    Call {
268        dest: Place,
269        callee: Callee,
270        args: Vec<Expr>,
271    },
272    If {
273        cond: Expr,
274        then: Block,
275        otherwise: Block,
276    },
277    /// Weighted branches. Without `otherwise`, the remaining weight either
278    /// continues past the statement (`exhaustive: false`) or is an error.
279    Chance {
280        arms: Vec<(Expr, Block)>,
281        otherwise: Option<Block>,
282        exhaustive: bool,
283    },
284    /// Repeats until every world has left through `break` or `return`.
285    /// Unbounded loops (`while`, `loop`) stop early once the weight still
286    /// inside is negligible; bounded ones (`for`, `repeat`) never do.
287    Loop {
288        body: Block,
289        bounded: bool,
290    },
291    Break,
292    Continue,
293    Return(Expr),
294    Observe {
295        value: Expr,
296        from: Option<Expr>,
297    },
298    Report {
299        site: u32,
300        value: Expr,
301        key: Option<Expr>,
302    },
303    /// A runtime error in every world that reaches it.
304    Fail {
305        message: String,
306    },
307    /// Check that a variable's value matches its declared type.
308    Check {
309        slot: SlotId,
310        ty: TypeSpec,
311    },
312    /// `try { body } catch F { … } catch { … }`: a world whose body faults
313    /// goes on in the first catch that names its fault, or that names none
314    /// (docs/semantics.md, section 11).
315    Try {
316        body: Block,
317        catches: Vec<Catch>,
318    },
319}
320
321/// One `catch` of a `try`.
322#[derive(Clone, Debug)]
323pub struct Catch {
324    /// The fault it catches; `None` catches every fault.
325    pub fault: Option<Fault>,
326    pub body: Block,
327}
328
329impl Catch {
330    pub fn catches(&self, fault: Option<Fault>) -> bool {
331        fault.is_some() && (self.fault.is_none() || self.fault == fault)
332    }
333}
334
335/// A language error that depends on the values a world computes with, not
336/// on the program being wrong: dividing by zero, an index past the end. A
337/// `catch` can name one; in partial mode, one that isn't caught ends only
338/// its world (docs/semantics.md, section 11). Errors that aren't faults
339/// always stop the run.
340#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
341pub enum Fault {
342    /// Division or remainder by zero.
343    DivisionByZero,
344    /// A value outside what an operation is defined for: `sqrt(-1)`,
345    /// `logit(0%)`, a distribution's parameter.
346    DomainError,
347    /// An index past the end.
348    IndexOutOfBounds,
349    /// A key that isn't in a map, or an item that isn't in a bag.
350    MissingKey,
351    /// A collection or a bag with nothing in it, where an element is needed.
352    EmptyCollection,
353    /// An explicit conversion that can't represent the value: `prob(1.5)`.
354    ConversionError,
355    /// A result too large to represent: a float that isn't finite, a date
356    /// out of range.
357    NumericOverflow,
358}
359
360impl Fault {
361    pub const ALL: [Fault; 7] = [
362        Fault::DivisionByZero,
363        Fault::DomainError,
364        Fault::IndexOutOfBounds,
365        Fault::MissingKey,
366        Fault::EmptyCollection,
367        Fault::ConversionError,
368        Fault::NumericOverflow,
369    ];
370
371    /// As a `catch` names it.
372    pub fn name(self) -> &'static str {
373        match self {
374            Fault::DivisionByZero => "DivisionByZero",
375            Fault::DomainError => "DomainError",
376            Fault::IndexOutOfBounds => "IndexOutOfBounds",
377            Fault::MissingKey => "MissingKey",
378            Fault::EmptyCollection => "EmptyCollection",
379            Fault::ConversionError => "ConversionError",
380            Fault::NumericOverflow => "NumericOverflow",
381        }
382    }
383
384    pub fn from_name(name: &str) -> Option<Fault> {
385        Fault::ALL.into_iter().find(|f| f.name() == name)
386    }
387}
388
389/// A declared type, checked when a value is stored.
390#[derive(Clone, Debug, PartialEq)]
391pub enum TypeSpec {
392    Int,
393    Float,
394    Complex,
395    Prob,
396    Bool,
397    Str,
398    Date,
399    Unit,
400    Function,
401    List(Box<TypeSpec>),
402    Map(Box<TypeSpec>, Box<TypeSpec>),
403    Bag(Box<TypeSpec>),
404    Dist(Box<TypeSpec>),
405    Record(u32),
406    Enum(u32),
407    AnonRecord(Vec<(String, TypeSpec)>),
408}
409
410impl TypeSpec {
411    /// How the type is written in source.
412    pub fn describe(&self, program: &Program) -> String {
413        self.describe_in(&program.records, &program.enums)
414    }
415
416    /// How the type is written in source, given the program's types.
417    pub fn describe_in(&self, records: &[RecordType], enums: &[EnumType]) -> String {
418        let describe = |t: &TypeSpec| t.describe_in(records, enums);
419        match self {
420            TypeSpec::Int => "int".into(),
421            TypeSpec::Float => "float".into(),
422            TypeSpec::Complex => "complex".into(),
423            TypeSpec::Prob => "prob".into(),
424            TypeSpec::Bool => "bool".into(),
425            TypeSpec::Str => "str".into(),
426            TypeSpec::Date => "date".into(),
427            TypeSpec::Unit => "()".into(),
428            TypeSpec::Function => "fn".into(),
429            TypeSpec::List(t) => format!("list[{}]", describe(t)),
430            TypeSpec::Map(k, v) => format!("map[{}, {}]", describe(k), describe(v)),
431            TypeSpec::Bag(t) => format!("bag[{}]", describe(t)),
432            TypeSpec::Dist(t) => format!("dist[{}]", describe(t)),
433            TypeSpec::Record(r) => records[*r as usize].name.clone(),
434            TypeSpec::Enum(e) => enums[*e as usize].name.clone(),
435            TypeSpec::AnonRecord(fields) => {
436                let fields: Vec<String> = fields.iter().map(|(n, t)| format!("{n}: {}", describe(t))).collect();
437                format!("{{ {} }}", fields.join(", "))
438            }
439        }
440    }
441}
442
443/// A variable, optionally followed by fields and indices: `a.b[i]`.
444#[derive(Clone, Debug)]
445pub struct Place {
446    pub slot: SlotId,
447    pub path: Vec<PathElem>,
448}
449
450impl Place {
451    pub fn slot(slot: SlotId) -> Place {
452        Place { slot, path: Vec::new() }
453    }
454}
455
456#[derive(Clone, Debug)]
457pub enum PathElem {
458    Field(String),
459    Index(Expr),
460}
461
462#[derive(Clone, Debug)]
463pub enum Callee {
464    /// A named function; `capture_args[i]` is the caller's slot supplying the
465    /// callee's `captures[i]`.
466    Fn { func: FnId, capture_args: Vec<SlotId> },
467    /// A function value; names correspond to the final call arguments.
468    Value(Expr, Vec<String>),
469}
470
471#[derive(Clone, Debug)]
472pub struct Expr {
473    pub kind: ExprKind,
474    pub span: Span,
475}
476
477#[derive(Clone, Debug)]
478pub enum ExprKind {
479    Lit(Lit),
480    Slot(SlotId),
481    Unary(UnOp, Box<Expr>),
482    /// All binary operators, including `and` and `or` (whose right side never
483    /// contains hoisted statements, so it can be evaluated lazily).
484    Binary(BinOp, Box<Expr>, Box<Expr>),
485    List(Vec<Expr>),
486    Map(Vec<(Expr, Expr)>),
487    Record {
488        ty: Option<u32>,
489        fields: Vec<(String, Expr)>,
490    },
491    Field(Box<Expr>, String),
492    Index(Box<Expr>, Box<Expr>),
493    With(Box<Expr>, Vec<(String, Expr)>),
494    Builtin {
495        func: Builtin,
496        args: Vec<Expr>,
497        named: Vec<(String, Expr)>,
498    },
499    /// Create a closure; `capture_args` align with the lambda's captures.
500    Closure {
501        func: FnId,
502        capture_args: Vec<SlotId>,
503    },
504    /// Run a `simulate` block and return its distribution.
505    Simulate {
506        func: FnId,
507        capture_args: Vec<SlotId>,
508    },
509    Interp(Vec<InterpPart>),
510    /// The value of the program's input with this number (`read`).
511    Input(u32),
512}
513
514#[derive(Clone, Debug)]
515pub enum InterpPart {
516    Lit(String),
517    Expr(Expr),
518}
519
520#[derive(Clone, Debug, PartialEq)]
521pub enum Lit {
522    Builtin(Builtin),
523    Unit,
524    Bool(bool),
525    Int(probl_number::Integer),
526    Float(f64),
527    /// A named mathematical constant: numeric, but not a source literal
528    /// eligible for contextual conversion to `prob`.
529    FloatConstant(f64),
530    Prob(f64),
531    Str(String),
532    Dice {
533        count: u32,
534        sides: u32,
535    },
536    Enum {
537        ty: u32,
538        variant: u32,
539    },
540}
probl_sema/ir.rs

probl_sema/
ir.rs
