bend/fun/transform/
resugar_list.rs

1use crate::{
2  fun::{builtins, Pattern, Tag, Term},
3  maybe_grow, AdtEncoding,
4};
5
6impl Term {
7  /// Converts lambda-encoded lists ending with List/Nil to list literals.
8  pub fn resugar_lists(&mut self, adt_encoding: AdtEncoding) {
9    match adt_encoding {
10      AdtEncoding::Scott => self.resugar_lists_scott(),
11      AdtEncoding::NumScott => self.resugar_lists_num_scott(),
12    }
13  }
14
15  /// Converts num-scott-encoded lists ending with List/Nil to list literals.
16  fn resugar_lists_num_scott(&mut self) {
17    maybe_grow(|| {
18      // Search for a List/Cons pattern in the term and try to build a list from that point on.
19      // If successful, replace the term with the list.
20      // If not, keep as-is.
21
22      // Nil: List/nil
23      if let Term::Ref { nam } = self {
24        if nam == builtins::LNIL {
25          *self = Term::List { els: vec![] };
26        }
27      }
28      // Cons: @x (x CONS_TAG <term> <term>)
29      if let Term::Lam { tag: Tag::Static, pat, bod } = self {
30        if let Pattern::Var(Some(var_lam)) = pat.as_mut() {
31          if let Term::App { tag: Tag::Static, fun, arg: tail } = bod.as_mut() {
32            if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
33              if let Term::App { tag: Tag::Static, fun, arg } = fun.as_mut() {
34                if let Term::Var { nam: var_app } = fun.as_mut() {
35                  if let Term::Ref { nam } = arg.as_mut() {
36                    if var_lam == var_app && nam == builtins::LCONS_TAG_REF {
37                      let l = build_list_num_scott(tail.as_mut(), vec![std::mem::take(head)]);
38                      match l {
39                        Ok(l) => *self = Term::List { els: l.into_iter().map(|x| *x).collect() },
40                        // Was not a list term, keep as-is.
41                        Err(mut l) => {
42                          *head = l.pop().unwrap();
43                          assert!(l.is_empty())
44                        }
45                      }
46                    }
47                  }
48                }
49              }
50            }
51          }
52        }
53      }
54      // Cons: (List/Cons <term> <term>)
55      if let Term::App { tag: Tag::Static, fun, arg: tail } = self {
56        if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
57          if let Term::Ref { nam } = fun.as_mut() {
58            if nam == builtins::LCONS {
59              let l = build_list_num_scott(tail.as_mut(), vec![std::mem::take(head)]);
60              match l {
61                Ok(l) => *self = Term::List { els: l.into_iter().map(|x| *x).collect() },
62                // Was not a list term, keep as-is.
63                Err(mut l) => {
64                  *head = l.pop().unwrap();
65                  assert!(l.is_empty())
66                }
67              }
68            }
69          }
70        }
71      }
72
73      for child in self.children_mut() {
74        child.resugar_lists_num_scott();
75      }
76    })
77  }
78
79  /// Converts scott-encoded lists ending with List/Nil to list literals.
80  fn resugar_lists_scott(&mut self) {
81    maybe_grow(|| {
82      // Search for a List/Cons pattern in the term and try to build a list from that point on.
83      // If successful, replace the term with the list.
84      // If not, keep as-is.
85
86      // Nil: List/nil
87      if let Term::Ref { nam } = self {
88        if nam == builtins::LNIL {
89          *self = Term::List { els: vec![] };
90        }
91      }
92      // Cons: @* @c (c <term> <term>)
93      if let Term::Lam { tag: Tag::Static, pat, bod } = self {
94        if let Pattern::Var(None) = pat.as_mut() {
95          if let Term::Lam { tag: Tag::Static, pat, bod } = bod.as_mut() {
96            if let Pattern::Var(Some(var_lam)) = pat.as_mut() {
97              if let Term::App { tag: Tag::Static, fun, arg: tail } = bod.as_mut() {
98                if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
99                  if let Term::Var { nam: var_app } = fun.as_mut() {
100                    if var_lam == var_app {
101                      let l = build_list_scott(tail.as_mut(), vec![std::mem::take(head)]);
102                      match l {
103                        Ok(l) => *self = Term::List { els: l.into_iter().map(|x| *x).collect() },
104                        // Was not a list term, keep as-is.
105                        Err(mut l) => {
106                          *head = l.pop().unwrap();
107                          assert!(l.is_empty())
108                        }
109                      }
110                    }
111                  }
112                }
113              }
114            }
115          }
116        }
117      }
118      // Cons: (List/Cons <term> <term>)
119      if let Term::App { tag: Tag::Static, fun, arg: tail } = self {
120        if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
121          if let Term::Ref { nam } = fun.as_mut() {
122            if nam == builtins::LCONS {
123              let l = build_list_scott(tail.as_mut(), vec![std::mem::take(head)]);
124              match l {
125                Ok(l) => *self = Term::List { els: l.into_iter().map(|x| *x).collect() },
126                // Was not a list term, keep as-is.
127                Err(mut l) => {
128                  *head = l.pop().unwrap();
129                  assert!(l.is_empty())
130                }
131              }
132            }
133          }
134        }
135      }
136
137      for child in self.children_mut() {
138        child.resugar_lists_scott();
139      }
140    })
141  }
142}
143
144// TODO: We have to do weird manipulations with Box<Term> because of the borrow checker.
145// When we used use box patterns this was a way simpler match statement.
146#[allow(clippy::vec_box)]
147fn build_list_num_scott(term: &mut Term, mut l: Vec<Box<Term>>) -> Result<Vec<Box<Term>>, Vec<Box<Term>>> {
148  maybe_grow(|| {
149    // Nil: List/nil
150    if let Term::Ref { nam } = term {
151      if nam == builtins::LNIL {
152        return Ok(l);
153      }
154    }
155    // Cons: @x (x CONS_TAG <term> <term>)
156    if let Term::Lam { tag: Tag::Static, pat, bod } = term {
157      if let Pattern::Var(Some(var_lam)) = pat.as_mut() {
158        if let Term::App { tag: Tag::Static, fun, arg: tail } = bod.as_mut() {
159          if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
160            if let Term::App { tag: Tag::Static, fun, arg } = fun.as_mut() {
161              if let Term::Var { nam: var_app } = fun.as_mut() {
162                if let Term::Ref { nam } = arg.as_mut() {
163                  if var_lam == var_app && nam == builtins::LCONS_TAG_REF {
164                    // New list element, append and recurse
165                    l.push(std::mem::take(head));
166                    let l = build_list_num_scott(tail, l);
167                    match l {
168                      Ok(l) => return Ok(l),
169                      Err(mut l) => {
170                        // If it wasn't a list, we have to put it back.
171                        *head = l.pop().unwrap();
172                        return Err(l);
173                      }
174                    }
175                  }
176                }
177              }
178            }
179          }
180        }
181      }
182    }
183    // Cons: (List/Cons <term> <term>)
184    if let Term::App { tag: Tag::Static, fun, arg: tail } = term {
185      if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
186        if let Term::Ref { nam } = fun.as_mut() {
187          if nam == builtins::LCONS {
188            // New list element, append and recurse
189            l.push(std::mem::take(head));
190            let l = build_list_num_scott(tail, l);
191            match l {
192              Ok(l) => return Ok(l),
193              Err(mut l) => {
194                // If it wasn't a list, we have to put it back.
195                *head = l.pop().unwrap();
196                return Err(l);
197              }
198            }
199          }
200        }
201      }
202    }
203    // Not a list term, stop
204    Err(l)
205  })
206}
207
208#[allow(clippy::vec_box)]
209fn build_list_scott(term: &mut Term, mut l: Vec<Box<Term>>) -> Result<Vec<Box<Term>>, Vec<Box<Term>>> {
210  maybe_grow(|| {
211    // Nil: List/nil
212    if let Term::Ref { nam } = term {
213      if nam == builtins::LNIL {
214        return Ok(l);
215      }
216    }
217    // Cons: @* @c (c <term> <term>)
218    if let Term::Lam { tag: Tag::Static, pat, bod } = term {
219      if let Pattern::Var(None) = pat.as_mut() {
220        if let Term::Lam { tag: Tag::Static, pat, bod } = bod.as_mut() {
221          if let Pattern::Var(Some(var_lam)) = pat.as_mut() {
222            if let Term::App { tag: Tag::Static, fun, arg: tail } = bod.as_mut() {
223              if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
224                if let Term::Var { nam: var_app } = fun.as_mut() {
225                  if var_lam == var_app {
226                    // New list element, append and recurse
227                    l.push(std::mem::take(head));
228                    let l = build_list_scott(tail, l);
229                    match l {
230                      Ok(l) => return Ok(l),
231                      Err(mut l) => {
232                        // If it wasn't a list, we have to put it back.
233                        *head = l.pop().unwrap();
234                        return Err(l);
235                      }
236                    }
237                  }
238                }
239              }
240            }
241          }
242        }
243      }
244    }
245    // Cons: (List/Cons <term> <term>)
246    if let Term::App { tag: Tag::Static, fun, arg: tail } = term {
247      if let Term::App { tag: Tag::Static, fun, arg: head } = fun.as_mut() {
248        if let Term::Ref { nam } = fun.as_mut() {
249          if nam == builtins::LCONS {
250            // New list element, append and recurse
251            l.push(std::mem::take(head));
252            let l = build_list_scott(tail, l);
253            match l {
254              Ok(l) => return Ok(l),
255              Err(mut l) => {
256                // If it wasn't a list, we have to put it back.
257                *head = l.pop().unwrap();
258                return Err(l);
259              }
260            }
261          }
262        }
263      }
264    }
265    // Not a list term, stop
266    Err(l)
267  })
268}
bend/fun/transform/resugar_list.rs

bend/fun/transform/
resugar_list.rs
