bend/fun/
term_to_net.rs

1use crate::{
2  diagnostics::Diagnostics,
3  fun::{num_to_name, Book, FanKind, Name, Op, Pattern, Term},
4  hvm::{net_trees, tree_children},
5  maybe_grow,
6  net::CtrKind::{self, *},
7};
8use hvm::ast::{Net, Tree};
9use loaned::LoanedMut;
10use std::{
11  collections::{hash_map::Entry, HashMap},
12  ops::{Index, IndexMut},
13};
14
15#[derive(Debug, Clone)]
16pub struct ViciousCycleErr;
17
18pub fn book_to_hvm(book: &Book, diags: &mut Diagnostics) -> Result<(hvm::ast::Book, Labels), Diagnostics> {
19  let mut hvm_book = hvm::ast::Book { defs: Default::default() };
20  let mut labels = Labels::default();
21
22  let main = book.entrypoint.as_ref();
23
24  for def in book.defs.values() {
25    for rule in def.rules.iter() {
26      let net = term_to_hvm(&rule.body, &mut labels);
27
28      let name = if main.is_some_and(|m| &def.name == m) {
29        book.hvm_entrypoint().to_string()
30      } else {
31        def.name.0.to_string()
32      };
33
34      match net {
35        Ok(net) => {
36          hvm_book.defs.insert(name, net);
37        }
38        Err(err) => diags.add_inet_error(err, name),
39      }
40    }
41  }
42
43  // TODO: native hvm nets ignore labels
44  for def in book.hvm_defs.values() {
45    hvm_book.defs.insert(def.name.to_string(), def.body.clone());
46  }
47
48  labels.con.finish();
49  labels.dup.finish();
50
51  diags.fatal((hvm_book, labels))
52}
53
54/// Converts an LC term into an IC net.
55pub fn term_to_hvm(term: &Term, labels: &mut Labels) -> Result<Net, String> {
56  let mut net = Net { root: Tree::Era, rbag: Default::default() };
57
58  let mut state = EncodeTermState {
59    lets: Default::default(),
60    vars: Default::default(),
61    wires: Default::default(),
62    redexes: Default::default(),
63    name_idx: 0,
64    created_nodes: 0,
65    labels,
66  };
67
68  state.encode_term(term, Place::Hole(&mut net.root));
69  LoanedMut::from(std::mem::take(&mut state.redexes)).place(&mut net.rbag);
70
71  let EncodeTermState { created_nodes, .. } = { state };
72
73  let found_nodes = net_trees(&net).map(count_nodes).sum::<usize>();
74  if created_nodes != found_nodes {
75    return Err("Found term that compiles into an inet with a vicious cycle".into());
76  }
77
78  Ok(net)
79}
80
81#[derive(Debug)]
82struct EncodeTermState<'t, 'l> {
83  lets: Vec<(&'t Pattern, &'t Term)>,
84  vars: HashMap<(bool, Name), Place<'t>>,
85  wires: Vec<Option<Place<'t>>>,
86  redexes: Vec<LoanedMut<'t, (bool, Tree, Tree)>>,
87  name_idx: u64,
88  created_nodes: usize,
89  labels: &'l mut Labels,
90}
91
92fn count_nodes(tree: &Tree) -> usize {
93  maybe_grow(|| {
94    usize::from(tree_children(tree).next().is_some()) + tree_children(tree).map(count_nodes).sum::<usize>()
95  })
96}
97
98#[derive(Debug)]
99enum Place<'t> {
100  Tree(LoanedMut<'t, Tree>),
101  Hole(&'t mut Tree),
102  Wire(usize),
103}
104
105impl<'t> EncodeTermState<'t, '_> {
106  /// Adds a subterm connected to `up` to the `inet`.
107  /// `scope` has the current variable scope.
108  /// `vars` has the information of which ports the variables are declared and used in.
109  /// `global_vars` has the same information for global lambdas. Must be linked outside this function.
110  /// Expects variables to be linear, refs to be stored as Refs and all names to be bound.
111  fn encode_term(&mut self, term: &'t Term, up: Place<'t>) {
112    maybe_grow(|| {
113      match term {
114        Term::Era => self.link(up, Place::Tree(LoanedMut::new(Tree::Era))),
115        Term::Var { nam } => self.link_var(false, nam, up),
116        Term::Link { nam } => self.link_var(true, nam, up),
117        Term::Ref { nam } => self.link(up, Place::Tree(LoanedMut::new(Tree::Ref { nam: nam.to_string() }))),
118        Term::Num { val } => {
119          let val = hvm::ast::Numb(val.to_bits());
120          self.link(up, Place::Tree(LoanedMut::new(Tree::Num { val })))
121        }
122        // A lambda becomes to a con node. Ports:
123        // - 0: points to where the lambda occurs.
124        // - 1: points to the lambda variable.
125        // - 2: points to the lambda body.
126        // core: (var_use bod)
127        Term::Lam { tag, pat, bod } => {
128          let kind = Con(self.labels.con.generate(tag));
129          let node = self.new_ctr(kind);
130          self.link(up, node.0);
131          self.encode_pat(pat, node.1);
132          self.encode_term(bod, node.2);
133        }
134        // An application becomes to a con node too. Ports:
135        // - 0: points to the function being applied.
136        // - 1: points to the function's argument.
137        // - 2: points to where the application occurs.
138        // core: & fun ~ (arg ret) (fun not necessarily main port)
139        Term::App { tag, fun, arg } => {
140          let kind = Con(self.labels.con.generate(tag));
141          let node = self.new_ctr(kind);
142          self.encode_term(fun, node.0);
143          self.encode_term(arg, node.1);
144          self.link(up, node.2);
145        }
146        // core: & arg ~ ?<(zero succ) ret>
147        Term::Swt { arg, bnd, with_bnd, with_arg, pred, arms,  } => {
148          // At this point should be only num matches of 0 and succ.
149          assert!(bnd.is_none());
150          assert!(with_bnd.is_empty());
151          assert!(with_arg.is_empty());
152          assert!(pred.is_none());
153          assert!(arms.len() == 2);
154
155          self.created_nodes += 2;
156          let loaned = Tree::Swi { fst: Box::new(Tree::Con{fst: Box::new(Tree::Era), snd: Box::new(Tree::Era)}), snd: Box::new(Tree::Era)};
157          let ((zero, succ, out), node) =
158            LoanedMut::loan_with(loaned, |t, l| {
159              let Tree::Swi { fst, snd: out } = t else { unreachable!() };
160              let Tree::Con { fst:zero, snd: succ } = fst.as_mut() else { unreachable!() };
161              (l.loan_mut(zero), l.loan_mut(succ), l.loan_mut(out))
162            });
163
164          self.encode_term(arg, Place::Tree(node));
165          self.encode_term(&arms[0], Place::Hole(zero));
166          self.encode_term(&arms[1], Place::Hole(succ));
167          self.link(up, Place::Hole(out));
168        }
169        Term::Let { pat, val, nxt } => {
170          // Dups/tup eliminators are not actually scoped like other terms.
171          // They are depended on
172          self.lets.push((pat, val));
173          self.encode_term(nxt, up);
174        }
175        Term::Fan { fan, tag, els } => {
176          let kind = self.fan_kind(fan, tag);
177          self.make_node_list(kind, up, els.iter().map(|el| |slf: &mut Self, up| slf.encode_term(el, up)));
178        }
179        // core: & [opr] ~ $(fst $(snd ret))
180        Term::Oper { opr, fst, snd } => {
181          match (fst.as_ref(), snd.as_ref()) {
182            // Partially apply with fst
183            (Term::Num { val }, snd) => {
184              let val = val.to_bits();
185              let val = hvm::ast::Numb((val & !0x1F) | opr.to_native_tag() as u32);
186              let fst = Place::Tree(LoanedMut::new(Tree::Num { val }));
187              let node = self.new_opr();
188              self.link(fst, node.0);
189              self.encode_term(snd, node.1);
190              self.encode_le_ge_opers(opr, up, node.2);
191            }
192            // Partially apply with snd, flip
193            (fst, Term::Num { val }) => {
194              if let Op::POW = opr {
195                // POW shares tags with AND, so don't flip or results will be wrong
196                let opr_val = hvm::ast::Numb(hvm::hvm::Numb::new_sym(opr.to_native_tag()).0);
197                let oper = Place::Tree(LoanedMut::new(Tree::Num { val: opr_val }));
198                let node1 = self.new_opr();
199                self.encode_term(fst, node1.0);
200                self.link(oper, node1.1);
201                let node2 = self.new_opr();
202                self.link(node1.2, node2.0);
203                self.encode_term(snd, node2.1);
204                self.encode_le_ge_opers(opr, up, node2.2);
205              } else {
206                // flip
207                let val = val.to_bits();
208                let val = hvm::ast::Numb((val & !0x1F) | flip_sym(opr.to_native_tag()) as u32);
209                let snd = Place::Tree(LoanedMut::new(Tree::Num { val }));
210                let node = self.new_opr();
211                self.encode_term(fst, node.0);
212                self.link(snd, node.1);
213                self.encode_le_ge_opers(opr, up, node.2);
214              }
215            }
216            // Don't partially apply
217            (fst, snd) => {
218              let opr_val = hvm::ast::Numb(hvm::hvm::Numb::new_sym(opr.to_native_tag()).0);
219              let oper = Place::Tree(LoanedMut::new(Tree::Num { val: opr_val }));
220              let node1 = self.new_opr();
221              self.encode_term(fst, node1.0);
222              self.link(oper, node1.1);
223              let node2 = self.new_opr();
224              self.link(node1.2, node2.0);
225              self.encode_term(snd, node2.1);
226              self.encode_le_ge_opers(opr, up, node2.2);
227            }
228          }
229        }
230        Term::Use { .. }  // Removed in earlier pass
231        | Term::With { .. } // Removed in earlier pass
232        | Term::Ask { .. } // Removed in earlier pass
233        | Term::Mat { .. } // Removed in earlier pass
234        | Term::Bend { .. } // Removed in desugar_bend
235        | Term::Fold { .. } // Removed in desugar_fold
236        | Term::Open { .. } // Removed in desugar_open
237        | Term::Nat { .. } // Removed in encode_nat
238        | Term::Str { .. } // Removed in encode_str
239        | Term::List { .. } // Removed in encode_list
240        | Term::Def { .. } // Removed in earlier pass
241        | Term::Err => unreachable!(),
242      }
243      while let Some((pat, val)) = self.lets.pop() {
244        let wire = self.new_wire();
245        self.encode_term(val, Place::Wire(wire));
246        self.encode_pat(pat, Place::Wire(wire));
247      }
248    })
249  }
250
251  fn encode_le_ge_opers(&mut self, opr: &Op, up: Place<'t>, node: Place<'t>) {
252    match opr {
253      Op::LE | Op::GE => {
254        let node_eq = self.new_opr();
255        let eq_val =
256          Place::Tree(LoanedMut::new(Tree::Num { val: hvm::ast::Numb(Op::EQ.to_native_tag() as u32) }));
257        self.link(eq_val, node_eq.0);
258        self.link(node_eq.1, node);
259        self.link(up, node_eq.2);
260      }
261      _ => self.link(up, node),
262    }
263  }
264
265  fn encode_pat(&mut self, pat: &Pattern, up: Place<'t>) {
266    maybe_grow(|| match pat {
267      Pattern::Var(None) => self.link(up, Place::Tree(LoanedMut::new(Tree::Era))),
268      Pattern::Var(Some(name)) => self.link_var(false, name, up),
269      Pattern::Chn(name) => self.link_var(true, name, up),
270      Pattern::Fan(fan, tag, els) => {
271        let kind = self.fan_kind(fan, tag);
272        self.make_node_list(kind, up, els.iter().map(|el| |slf: &mut Self, up| slf.encode_pat(el, up)));
273      }
274      Pattern::Ctr(_, _) | Pattern::Num(_) | Pattern::Lst(_) | Pattern::Str(_) => unreachable!(),
275    })
276  }
277
278  fn link(&mut self, a: Place<'t>, b: Place<'t>) {
279    match (a, b) {
280      (Place::Tree(a), Place::Tree(b)) => {
281        self.redexes.push(LoanedMut::merge((false, Tree::Era, Tree::Era), |r, m| {
282          m.place(b, &mut r.1);
283          m.place(a, &mut r.2);
284        }))
285      }
286      (Place::Tree(t), Place::Hole(h)) | (Place::Hole(h), Place::Tree(t)) => {
287        t.place(h);
288      }
289      (Place::Hole(a), Place::Hole(b)) => {
290        let var = Tree::Var { nam: num_to_name(self.name_idx) };
291        self.name_idx += 1;
292        *a = var.clone();
293        *b = var;
294      }
295      (Place::Wire(v), p) | (p, Place::Wire(v)) => {
296        let v = &mut self.wires[v];
297        match v.take() {
298          Some(q) => self.link(p, q),
299          None => *v = Some(p),
300        }
301      }
302    }
303  }
304
305  fn new_ctr(&mut self, kind: CtrKind) -> (Place<'t>, Place<'t>, Place<'t>) {
306    self.created_nodes += 1;
307    let node = match kind {
308      CtrKind::Con(None) => Tree::Con { fst: Box::new(Tree::Era), snd: Box::new(Tree::Era) },
309      CtrKind::Dup(0) => Tree::Dup { fst: Box::new(Tree::Era), snd: Box::new(Tree::Era) },
310      CtrKind::Tup(None) => Tree::Con { fst: Box::new(Tree::Era), snd: Box::new(Tree::Era) },
311      _ => unreachable!(),
312    };
313    let ((a, b), node) = LoanedMut::loan_with(node, |t, l| match t {
314      Tree::Con { fst, snd } => (l.loan_mut(fst), l.loan_mut(snd)),
315      Tree::Dup { fst, snd } => (l.loan_mut(fst), l.loan_mut(snd)),
316      _ => unreachable!(),
317    });
318    (Place::Tree(node), Place::Hole(a), Place::Hole(b))
319  }
320
321  fn new_opr(&mut self) -> (Place<'t>, Place<'t>, Place<'t>) {
322    self.created_nodes += 1;
323    let ((fst, snd), node) =
324      LoanedMut::loan_with(Tree::Opr { fst: Box::new(Tree::Era), snd: Box::new(Tree::Era) }, |t, l| {
325        let Tree::Opr { fst, snd } = t else { unreachable!() };
326        (l.loan_mut(fst), l.loan_mut(snd))
327      });
328    (Place::Tree(node), Place::Hole(fst), Place::Hole(snd))
329  }
330
331  /// Adds a list-like tree of nodes of the same kind to the inet.
332  fn make_node_list(
333    &mut self,
334    kind: CtrKind,
335    mut up: Place<'t>,
336    mut els: impl DoubleEndedIterator<Item = impl FnOnce(&mut Self, Place<'t>)>,
337  ) {
338    let last = els.next_back().unwrap();
339    for item in els {
340      let node = self.new_ctr(kind);
341      self.link(up, node.0);
342      item(self, node.1);
343      up = node.2;
344    }
345    last(self, up);
346  }
347
348  fn new_wire(&mut self) -> usize {
349    let i = self.wires.len();
350    self.wires.push(None);
351    i
352  }
353
354  fn fan_kind(&mut self, fan: &FanKind, tag: &crate::fun::Tag) -> CtrKind {
355    let lab = self.labels[*fan].generate(tag);
356    if *fan == FanKind::Tup {
357      Tup(lab)
358    } else {
359      Dup(lab.unwrap())
360    }
361  }
362
363  fn link_var(&mut self, global: bool, name: &Name, place: Place<'t>) {
364    match self.vars.entry((global, name.clone())) {
365      Entry::Occupied(e) => {
366        let other = e.remove();
367        self.link(place, other);
368      }
369      Entry::Vacant(e) => {
370        e.insert(place);
371      }
372    }
373  }
374}
375
376#[derive(Debug, Default, Clone)]
377pub struct Labels {
378  pub con: LabelGenerator,
379  pub dup: LabelGenerator,
380  pub tup: LabelGenerator,
381}
382
383#[derive(Debug, Default, Clone)]
384pub struct LabelGenerator {
385  pub next: u16,
386  pub name_to_label: HashMap<Name, u16>,
387  pub label_to_name: HashMap<u16, Name>,
388}
389
390impl Index<FanKind> for Labels {
391  type Output = LabelGenerator;
392
393  fn index(&self, fan: FanKind) -> &Self::Output {
394    match fan {
395      FanKind::Tup => &self.tup,
396      FanKind::Dup => &self.dup,
397    }
398  }
399}
400
401impl IndexMut<FanKind> for Labels {
402  fn index_mut(&mut self, fan: FanKind) -> &mut Self::Output {
403    match fan {
404      FanKind::Tup => &mut self.tup,
405      FanKind::Dup => &mut self.dup,
406    }
407  }
408}
409
410impl LabelGenerator {
411  // If some tag and new generate a new label, otherwise return the generated label.
412  // If none use the implicit label counter.
413  fn generate(&mut self, tag: &crate::fun::Tag) -> Option<u16> {
414    use crate::fun::Tag;
415    match tag {
416      Tag::Named(_name) => {
417        todo!("Named tags not implemented for hvm32");
418        /* match self.name_to_label.entry(name.clone()) {
419          Entry::Occupied(e) => Some(*e.get()),
420          Entry::Vacant(e) => {
421            let lab = unique();
422            self.label_to_name.insert(lab, name.clone());
423            Some(*e.insert(lab))
424          }
425        } */
426      }
427      Tag::Numeric(lab) => Some(*lab),
428      Tag::Auto => Some(0),
429      Tag::Static => None,
430    }
431  }
432
433  pub fn to_tag(&self, label: Option<u16>) -> crate::fun::Tag {
434    use crate::fun::Tag;
435    match label {
436      Some(label) => match self.label_to_name.get(&label) {
437        Some(name) => Tag::Named(name.clone()),
438        None => {
439          if label == 0 {
440            Tag::Auto
441          } else {
442            Tag::Numeric(label)
443          }
444        }
445      },
446      None => Tag::Static,
447    }
448  }
449
450  fn finish(&mut self) {
451    self.next = u16::MAX;
452    self.name_to_label.clear();
453  }
454}
455
456impl Op {
457  fn to_native_tag(self) -> hvm::hvm::Tag {
458    match self {
459      Op::ADD => hvm::hvm::OP_ADD,
460      Op::SUB => hvm::hvm::OP_SUB,
461      Op::MUL => hvm::hvm::OP_MUL,
462      Op::DIV => hvm::hvm::OP_DIV,
463      Op::REM => hvm::hvm::OP_REM,
464      Op::EQ => hvm::hvm::OP_EQ,
465      Op::NEQ => hvm::hvm::OP_NEQ,
466      Op::LT => hvm::hvm::OP_LT,
467      Op::GT => hvm::hvm::OP_GT,
468      Op::AND => hvm::hvm::OP_AND,
469      Op::OR => hvm::hvm::OP_OR,
470      Op::XOR => hvm::hvm::OP_XOR,
471      Op::SHL => hvm::hvm::OP_SHL,
472      Op::SHR => hvm::hvm::OP_SHR,
473
474      Op::POW => hvm::hvm::OP_XOR,
475
476      Op::LE => hvm::hvm::OP_GT,
477      Op::GE => hvm::hvm::OP_LT,
478    }
479  }
480}
481
482fn flip_sym(tag: hvm::hvm::Tag) -> hvm::hvm::Tag {
483  match tag {
484    hvm::hvm::OP_SUB => hvm::hvm::FP_SUB,
485    hvm::hvm::FP_SUB => hvm::hvm::OP_SUB,
486    hvm::hvm::OP_DIV => hvm::hvm::FP_DIV,
487    hvm::hvm::FP_DIV => hvm::hvm::OP_DIV,
488    hvm::hvm::OP_REM => hvm::hvm::FP_REM,
489    hvm::hvm::FP_REM => hvm::hvm::OP_REM,
490    hvm::hvm::OP_LT => hvm::hvm::OP_GT,
491    hvm::hvm::OP_GT => hvm::hvm::OP_LT,
492    hvm::hvm::OP_SHL => hvm::hvm::FP_SHL,
493    hvm::hvm::FP_SHL => hvm::hvm::OP_SHL,
494    hvm::hvm::OP_SHR => hvm::hvm::FP_SHR,
495    hvm::hvm::FP_SHR => hvm::hvm::OP_SHR,
496    _ => tag,
497  }
498}
bend/fun/term_to_net.rs

bend/fun/
term_to_net.rs
