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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
225pub struct Capture {
226    /// Where the value goes in this function's frame.
227    pub slot: SlotId,
228    pub source: CaptureSource,
229}
230
231#[derive(Clone, Copy, Debug, PartialEq, Eq)]
232pub enum CaptureSource {
233    /// A top-level variable (a slot of the main frame).
234    Global(SlotId),
235    /// A variable of the enclosing function (for lambdas and `simulate`).
236    Parent(SlotId),
237}
238
239#[derive(Clone, Debug)]
240pub struct SlotInfo {
241    pub name: String,
242    pub span: Span,
243}
244
245#[derive(Clone, Debug, Default)]
246pub struct Block {
247    pub stmts: Vec<Stmt>,
248}
249
250#[derive(Clone, Debug)]
251pub struct Stmt {
252    pub id: StmtId,
253    pub span: Span,
254    pub kind: StmtKind,
255}
256
257#[derive(Clone, Debug)]
258pub enum StmtKind {
259    /// `place = value`.
260    Set {
261        place: Place,
262        value: Expr,
263    },
264    /// `place ~ dist`: one world per outcome.
265    Draw {
266        place: Place,
267        dist: Expr,
268    },
269    /// `place = bag.take()`: select an item unchanged and remove one copy.
270    Take {
271        place: Place,
272        bag: Place,
273    },
274    /// Call a user function or closure; may split worlds.
275    Call {
276        dest: Place,
277        callee: Callee,
278        args: Vec<Expr>,
279    },
280    If {
281        cond: Expr,
282        then: Block,
283        otherwise: Block,
284    },
285    /// Weighted branches. Without `otherwise`, the remaining weight either
286    /// continues past the statement (`exhaustive: false`) or is an error.
287    Chance {
288        arms: Vec<(Expr, Block)>,
289        otherwise: Option<Block>,
290        exhaustive: bool,
291    },
292    /// Repeats until every world has left through `break` or `return`.
293    /// Unbounded loops (`while`, `loop`) stop early once the weight still
294    /// inside is negligible; bounded ones (`for`, `repeat`) never do.
295    Loop {
296        body: Block,
297        bounded: bool,
298    },
299    Break,
300    Continue,
301    Return(Expr),
302    Observe {
303        value: Expr,
304        from: Option<Expr>,
305    },
306    Report {
307        site: u32,
308        value: Expr,
309        key: Option<Expr>,
310    },
311    /// A runtime error in every world that reaches it.
312    Fail {
313        message: String,
314    },
315    /// Check that a variable's value matches its declared type.
316    Check {
317        slot: SlotId,
318        ty: TypeSpec,
319    },
320    /// `try { body } catch F { … } catch { … }`: a world whose body faults
321    /// goes on in the first catch that names its fault, or that names none
322    /// (docs/semantics.md, section 11).
323    Try {
324        body: Block,
325        catches: Vec<Catch>,
326    },
327}
328
329/// One `catch` of a `try`.
330#[derive(Clone, Debug)]
331pub struct Catch {
332    /// The fault it catches; `None` catches every fault.
333    pub fault: Option<Fault>,
334    pub body: Block,
335}
336
337impl Catch {
338    pub fn catches(&self, fault: Option<Fault>) -> bool {
339        fault.is_some() && (self.fault.is_none() || self.fault == fault)
340    }
341}
342
343/// A language error that depends on the values a world computes with, not
344/// on the program being wrong: dividing by zero, an index past the end. A
345/// `catch` can name one; in partial mode, one that isn't caught ends only
346/// its world (docs/semantics.md, section 11). Errors that aren't faults
347/// always stop the run.
348#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
349pub enum Fault {
350    /// Division or remainder by zero.
351    DivisionByZero,
352    /// A value outside what an operation is defined for: `sqrt(-1)`,
353    /// `logit(0%)`, a distribution's parameter.
354    DomainError,
355    /// An index past the end.
356    IndexOutOfBounds,
357    /// A key that isn't in a map, or an item that isn't in a bag.
358    MissingKey,
359    /// A collection or a bag with nothing in it, where an element is needed.
360    EmptyCollection,
361    /// An explicit conversion that can't represent the value: `prob(1.5)`.
362    ConversionError,
363    /// A result too large to represent: a float that isn't finite, a date
364    /// out of range.
365    NumericOverflow,
366}
367
368impl Fault {
369    pub const ALL: [Fault; 7] = [
370        Fault::DivisionByZero,
371        Fault::DomainError,
372        Fault::IndexOutOfBounds,
373        Fault::MissingKey,
374        Fault::EmptyCollection,
375        Fault::ConversionError,
376        Fault::NumericOverflow,
377    ];
378
379    /// As a `catch` names it.
380    pub fn name(self) -> &'static str {
381        match self {
382            Fault::DivisionByZero => "DivisionByZero",
383            Fault::DomainError => "DomainError",
384            Fault::IndexOutOfBounds => "IndexOutOfBounds",
385            Fault::MissingKey => "MissingKey",
386            Fault::EmptyCollection => "EmptyCollection",
387            Fault::ConversionError => "ConversionError",
388            Fault::NumericOverflow => "NumericOverflow",
389        }
390    }
391
392    pub fn from_name(name: &str) -> Option<Fault> {
393        Fault::ALL.into_iter().find(|f| f.name() == name)
394    }
395}
396
397/// A declared type, checked when a value is stored.
398#[derive(Clone, Debug, PartialEq)]
399pub enum TypeSpec {
400    Int,
401    Float,
402    Complex,
403    Prob,
404    Bool,
405    Str,
406    Date,
407    Unit,
408    Function,
409    List(Box<TypeSpec>),
410    Map(Box<TypeSpec>, Box<TypeSpec>),
411    Bag(Box<TypeSpec>),
412    Dist(Box<TypeSpec>),
413    Record(u32),
414    Enum(u32),
415    AnonRecord(Vec<(String, TypeSpec)>),
416}
417
418impl TypeSpec {
419    /// How the type is written in source.
420    pub fn describe(&self, program: &Program) -> String {
421        self.describe_in(&program.records, &program.enums)
422    }
423
424    /// How the type is written in source, given the program's types.
425    pub fn describe_in(&self, records: &[RecordType], enums: &[EnumType]) -> String {
426        let describe = |t: &TypeSpec| t.describe_in(records, enums);
427        match self {
428            TypeSpec::Int => "int".into(),
429            TypeSpec::Float => "float".into(),
430            TypeSpec::Complex => "complex".into(),
431            TypeSpec::Prob => "prob".into(),
432            TypeSpec::Bool => "bool".into(),
433            TypeSpec::Str => "str".into(),
434            TypeSpec::Date => "date".into(),
435            TypeSpec::Unit => "()".into(),
436            TypeSpec::Function => "fn".into(),
437            TypeSpec::List(t) => format!("list[{}]", describe(t)),
438            TypeSpec::Map(k, v) => format!("map[{}, {}]", describe(k), describe(v)),
439            TypeSpec::Bag(t) => format!("bag[{}]", describe(t)),
440            TypeSpec::Dist(t) => format!("dist[{}]", describe(t)),
441            TypeSpec::Record(r) => records[*r as usize].name.clone(),
442            TypeSpec::Enum(e) => enums[*e as usize].name.clone(),
443            TypeSpec::AnonRecord(fields) => {
444                let fields: Vec<String> = fields.iter().map(|(n, t)| format!("{n}: {}", describe(t))).collect();
445                format!("{{ {} }}", fields.join(", "))
446            }
447        }
448    }
449}
450
451/// A variable, optionally followed by fields and indices: `a.b[i]`.
452#[derive(Clone, Debug)]
453pub struct Place {
454    pub slot: SlotId,
455    pub path: Vec<PathElem>,
456}
457
458impl Place {
459    pub fn slot(slot: SlotId) -> Place {
460        Place { slot, path: Vec::new() }
461    }
462}
463
464#[derive(Clone, Debug)]
465pub enum PathElem {
466    Field(String),
467    Index(Expr),
468}
469
470#[derive(Clone, Debug)]
471pub enum Callee {
472    /// A named function; `capture_args[i]` is the caller's slot supplying the
473    /// callee's `captures[i]`.
474    Fn { func: FnId, capture_args: Vec<SlotId> },
475    /// A function value; names correspond to the final call arguments.
476    Value(Expr, Vec<String>),
477}
478
479#[derive(Clone, Debug)]
480pub struct Expr {
481    pub kind: ExprKind,
482    pub span: Span,
483}
484
485#[derive(Clone, Debug)]
486pub enum ExprKind {
487    Lit(Lit),
488    Slot(SlotId),
489    Unary(UnOp, Box<Expr>),
490    /// All binary operators, including `and` and `or` (whose right side never
491    /// contains hoisted statements, so it can be evaluated lazily).
492    Binary(BinOp, Box<Expr>, Box<Expr>),
493    List(Vec<Expr>),
494    Map(Vec<(Expr, Expr)>),
495    Record {
496        ty: Option<u32>,
497        fields: Vec<(String, Expr)>,
498    },
499    Field(Box<Expr>, String),
500    Index(Box<Expr>, Box<Expr>),
501    With(Box<Expr>, Vec<(String, Expr)>),
502    Builtin {
503        func: Builtin,
504        args: Vec<Expr>,
505        named: Vec<(String, Expr)>,
506    },
507    /// Create a closure; `capture_args` align with the lambda's captures.
508    Closure {
509        func: FnId,
510        capture_args: Vec<SlotId>,
511    },
512    /// Run a `simulate` block and return its distribution.
513    Simulate {
514        func: FnId,
515        capture_args: Vec<SlotId>,
516    },
517    Interp(Vec<InterpPart>),
518    /// The value of the program's input with this number (`read`).
519    Input(u32),
520}
521
522#[derive(Clone, Debug)]
523pub enum InterpPart {
524    Lit(String),
525    Expr(Expr),
526}
527
528#[derive(Clone, Debug, PartialEq)]
529pub enum Lit {
530    Builtin(Builtin),
531    Unit,
532    Bool(bool),
533    Int(probl_number::Integer),
534    Float(f64),
535    /// A named mathematical constant: numeric, but not a source literal
536    /// eligible for contextual conversion to `prob`.
537    FloatConstant(f64),
538    Prob(f64),
539    Str(String),
540    Dice {
541        count: u32,
542        sides: u32,
543    },
544    Enum {
545        ty: u32,
546        variant: u32,
547    },
548}
probl_sema/ir.rs

probl_sema/
ir.rs
