lambdas/domains/
prim_lists.rs

1// The primitive list domain from Josh Rule's thesis, p.170.
2
3use crate::*;
4use std::collections::HashMap;
5
6#[derive(Clone,Debug, PartialEq, Eq, Hash)]
7pub enum ListVal {
8    Int(i32),
9    // Nan,  // TODO to model NAN or not...(josh rule dsl does it for things outside of 0-99)
10    Bool(bool),
11    List(Vec<Val>),
12}
13
14// In this domain, we limit how many times "fix" can be invoked.
15// This is a crude way of finding infinitely looping programs.
16const MAX_FIX_INVOCATIONS: u32 = 20;
17
18type Val = crate::eval::Val<ListVal>;
19type LazyVal = crate::eval::LazyVal<ListVal>;
20type Evaluator<'a> = crate::eval::Evaluator<'a,ListVal>;
21type VResult = crate::eval::VResult<ListVal>;
22type DSLFn = crate::dsl::DSLFn<ListVal>;
23
24use ListVal::*;
25use crate::eval::Val::*;
26// use domain::Type::*;
27
28// this macro generates two global lazy_static constants: PRIM and FUNCS
29// which get used by `val_of_prim` and `fn_of_prim` below. In short they simply
30// associate the strings on the left with the rust function and arity on the right.
31define_semantics! {
32    ListVal;
33    "cons" = (cons, "t0 -> list t0 -> list t0"),
34    "+" = (add, "int -> int -> int"),
35    "-" = (sub,  "int -> int -> int"),
36    ">" = (gt, "int -> int -> bool"),
37    "if" = (branch, "bool -> t0 -> t0 -> t0"),
38    "==" = (eq, "t0 -> t0 -> bool"),
39    "is_empty" = (is_empty, "list t0 -> bool"),
40    "head" = (head, "list t0 -> t0"),
41    "tail" = (tail, "list t0 -> list t0"),
42    // fix f x = f(fix f)(x)
43    // note in historical origami logs dreamcoder actually uses the signature: t0 -> ((t0 -> t1) -> t0 -> t1) -> t1    fix1
44    "fix_flip" = (fix_flip, "t0 -> ((t0 -> t1) -> t0 -> t1) -> t1"),
45    "fix" = (fix, "((t0 -> t1) -> t0 -> t1) -> t0 -> t1"),
46    "0" = "int",
47    "1" = "int",
48    "[]" = "list t0",
49}
50
51
52
53// From<Val> impls are needed for unwrapping values. We can assume the program
54// has been type checked so it's okay to panic if the type is wrong. Each val variant
55// must map to exactly one unwrapped type (though it doesnt need to be one to one in the
56// other direction)
57impl FromVal<ListVal> for i32 {
58    fn from_val(v: Val) -> Result<Self, VError> {
59        match v {
60            Dom(Int(i)) => Ok(i),
61            _ => Err("from_val_to_list: not an int".into())
62        }
63    }
64}
65impl FromVal<ListVal> for bool {
66    fn from_val(v: Val) -> Result<Self, VError> {
67        match v {
68            Dom(Bool(b)) => Ok(b),
69            _ => Err("from_val_to_bool: not a bool".into())
70        }
71    }
72}
73impl<T: FromVal<ListVal>> FromVal<ListVal> for Vec<T>
74{
75    fn from_val(v: Val) -> Result<Self, VError> {
76        match v {
77            Dom(List(v)) => v.into_iter().map(|v| T::from_val(v)).collect(),
78            _ => Err("from_val_to_vec: not a list".into())
79        }
80    }
81}
82
83// These Into<Val>s are convenience functions. It's okay if theres not a one to one mapping
84// like this in all domains - it just makes .into() save us a lot of work if there is.
85impl From<i32> for Val {
86    fn from(i: i32) -> Val {
87        Dom(Int(i))
88    }
89}
90impl From<bool> for Val {
91    fn from(b: bool) -> Val {
92        Dom(Bool(b))
93    }
94}
95impl<T: Into<Val>> From<Vec<T>> for Val {
96    fn from(vec: Vec<T>) -> Val {
97        Dom(List(vec.into_iter().map(|v| v.into()).collect()))
98    }
99}
100
101fn parse_vec(vec: &[serde_json::value::Value]) -> Vec<Val> {
102    let valvec: Vec<Val> = vec.iter().map(|v| {
103        if let Some(i) = v.as_i64() {
104            Dom(Int(i as i32))
105        } else if let Some(b) = v.as_bool() {
106            Dom(Bool(b))
107        } else {
108            // not int, not bool -> must be array. If not, we error.
109            // TODO make this spit out a more useful error than panic
110            let arr = v.as_array().unwrap();
111            Dom(List(parse_vec(arr)))
112        }
113    }).collect();
114    valvec
115}
116
117#[derive(Default,Debug)]
118pub struct ListData {
119    fix_counter: u32,
120}
121
122impl Domain for ListVal {
123
124    type Data = ListData;  // Use Data as fix-point invocation counter
125
126    // val_of_prim takes a symbol like "+" or "0" and returns the corresponding Val.
127    // Note that it can largely just be a call to the global hashmap PRIMS that define_semantics generated
128    // however you're also free to do any sort of generic parsing you want, allowing for domains with
129    // infinite sets of values or dynamically generated values. For example here we support all integers
130    // and all integer lists.
131    fn val_of_prim_fallback(p: Symbol) -> Option<Val> {
132        // starts with digit or negative sign -> Int
133        if p.as_str().chars().next().unwrap().is_ascii_digit() || p.as_str().starts_with('-') {
134            let i: i32 = p.as_str().parse().ok()?;
135            Some(Int(i).into())
136        }
137        // starts with "f" or "t" -> must be a bool (if not found in PRIMS)
138        else if p.as_str().starts_with('f') || p.as_str().starts_with('t') {
139            let s: String = p.as_str().parse().ok()?;
140            if s == "false" {
141                Some(Dom(Bool(false)))
142            } else if s == "true" {
143                Some(Dom(Bool(true)))
144            } else {
145                None
146            }
147        }
148        // starts with `[` -> List
149        // Note lists may contain ints, bools, or other lists in this domain
150        else if p.as_str().starts_with('[') {
151            let elems: Vec<serde_json::value::Value> = serde_json::from_str(p.as_str()).ok()?;
152            let valvec: Vec<Val> = parse_vec(&elems);
153            Some(List(valvec).into())
154        } else {
155            None
156        }
157    }
158
159    dsl_entries_lookup_gen!();
160
161    fn type_of_dom_val(&self) -> Type {
162        match self {
163            Int(_) => Type::base("int".into()),
164            Bool(_) =>  Type::base("bool".into()),
165            List(xs) => {
166                let elem_tp = if xs.is_empty() {
167                    Type::Var(0) // (list t0)
168                } else {
169                    // todo here we just use the type of the first entry as the type
170                    Self::type_of_dom_val(&xs.first().unwrap().clone().dom().unwrap())
171                    // assert!(xs.iter().all(|v| Self::type_of_dom_val(v.clone().dom().unwrap())))
172                };
173                Type::Term("list".into(),vec![elem_tp])
174            },
175        }
176    }
177
178}
179
180
181// *** DSL FUNCTIONS ***
182
183fn cons(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
184    load_args!(handle, args, x:Val, xs:Vec<Val>); 
185    let mut rxs = xs;
186    rxs.insert(0, x);
187    // println!("{:?}", rxs);
188    ok(rxs)
189}
190
191fn add(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
192    load_args!(handle, args, x:i32, y:i32); 
193    ok(x+y)
194}
195
196fn sub(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
197    load_args!(handle, args, x:i32, y:i32); 
198    ok(x-y)
199}
200
201fn gt(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
202    load_args!(handle, args, x:i32, y:i32); 
203    ok(x>y)
204}
205
206fn branch(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
207    load_args!(handle, args, b: bool);
208    load_args_lazy!(args, tbranch: LazyVal, fbranch: LazyVal); 
209    if b { 
210        tbranch.eval(handle)
211    } else { 
212        fbranch.eval(handle)
213    }
214}
215
216fn eq(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
217    load_args!(handle, args, x:Val, y:Val); 
218    ok(x == y) // since Vals have Eq implemented already in the way that we want
219}
220
221fn is_empty(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
222    load_args!(handle, args, xs: Vec<Val>);
223    ok(xs.is_empty())
224}
225
226fn head(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
227    load_args!(handle, args, xs: Vec<Val>);
228    if xs.is_empty() {
229        Err(String::from("head called on empty list"))
230    } else {
231        ok(xs[0].clone())
232    }
233}
234
235fn tail(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
236    load_args!(handle, args, xs: Vec<Val>);
237    if xs.is_empty() {
238        Err(String::from("tail called on empty list"))
239    } else {
240        ok(xs[1..].to_vec())
241    }
242}
243
244
245/// fix f x = f(fix f)(x)
246/// type i think: ((t0 -> t1) -> t0 -> t1) -> t0 -> t1 
247fn fix(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
248    handle.data.borrow_mut().fix_counter += 1;
249    if handle.data.borrow().fix_counter > MAX_FIX_INVOCATIONS {
250        return Err(format!("Exceeded max number of fix invocations. Max was {}", MAX_FIX_INVOCATIONS));
251    }
252    load_args!(handle, args, fn_val: Val, x: Val);
253
254    // fix f x = f(fix f)(x)
255    let fixf = PrimFun(CurriedFn::new_with_args(Symbol::from("fix"), 2, vec![LazyVal::new_strict(fn_val.clone())]));
256    let res = if let VResult::Ok(ffixf) = handle.apply(&fn_val, fixf) {
257        handle.apply(&ffixf, x)
258    } else {
259        Err("Could not apply fixf to f".into())
260    };
261    handle.data.borrow_mut().fix_counter -= 1;
262    res
263}
264
265
266/// fix x f = f(fix f)(x)
267/// type i think: t0 -> ((t0 -> t1) -> t0 -> t1) -> t1 
268/// This is to match dreamcoder.
269fn fix_flip(mut args: Vec<LazyVal>, handle: &Evaluator) -> VResult {
270    args.reverse();
271    fix(args, handle)
272}
273
274#[cfg(test)]
275mod tests {
276    use super::*;
277
278    #[test]
279    fn test_eval_prim_lists() {
280
281        let arg = ListVal::val_of_prim("[]".into()).unwrap();
282        assert_execution::<ListVal, Vec<Val>>("(if (is_empty $0) $0 (tail $0))", &[arg], vec![]);
283
284        // test cons
285        let arg = ListVal::val_of_prim("[1,2,3]".into()).unwrap();
286        assert_execution("(cons 0 $0)", &[arg], vec![0,1,2,3]);
287
288        // test +
289        assert_execution::<ListVal, i32>("(+ 1 2)", &[], 3);
290
291        // test -
292        assert_execution::<ListVal, i32>("(- 22 1)", &[], 21);
293
294        // test >
295        assert_execution::<ListVal, bool>("(> 22 1)", &[], true);
296        assert_execution::<ListVal, bool>("(> 2 11)", &[], false);
297
298        // test if
299        assert_execution::<ListVal, i32>("(if true 5 50)", &[], 5);
300        assert_execution::<ListVal, i32>("(if false 5 50)", &[], 50);
301
302        // test ==
303        assert_execution::<ListVal, bool>("(== 5 5)", &[], true);
304        assert_execution::<ListVal, bool>("(== 5 50)", &[], false);
305        let arg1 = ListVal::val_of_prim("[[],[3],[4,5]]".into()).unwrap();
306        let arg2 = ListVal::val_of_prim("[[],[3],[4,5]]".into()).unwrap();
307        assert_execution::<ListVal, bool>("(== $0 $1)", &[arg1, arg2], true);
308        let arg1 = ListVal::val_of_prim("[[],[3],[4,5]]".into()).unwrap();
309        let arg2 = ListVal::val_of_prim("[[3],[4,5]]".into()).unwrap();
310        assert_execution::<ListVal, bool>("(== $0 $1)", &[arg1, arg2], false);
311        let arg1 = ListVal::val_of_prim("[[]]".into()).unwrap();
312        let arg2 = ListVal::val_of_prim("[]".into()).unwrap();
313        assert_execution::<ListVal, bool>("(== $0 $1)", &[arg1, arg2], false);
314        let arg1 = ListVal::val_of_prim("[]".into()).unwrap();
315        let arg2 = ListVal::val_of_prim("[]".into()).unwrap();
316        assert_execution::<ListVal, bool>("(== $0 $1)", &[arg1, arg2], true);
317
318        // test is_empty
319        let arg = ListVal::val_of_prim("[[],[3],[4,5]]".into()).unwrap();
320        assert_execution("(is_empty $0)", &[arg], false);
321        let arg = ListVal::val_of_prim("[]".into()).unwrap();
322        assert_execution("(is_empty $0)", &[arg], true);
323
324        // test head
325        let arg = ListVal::val_of_prim("[[1,2],[3],[4,5]]".into()).unwrap();
326        assert_execution("(head $0)", &[arg], vec![1,2]);
327
328        // test tail
329        let arg = ListVal::val_of_prim("[[1,2],[3],[4,5]]".into()).unwrap();
330        assert_execution("(tail $0)", &[arg], vec![vec![3], vec![4, 5]]);
331        let arg = ListVal::val_of_prim("[[1,2]]".into()).unwrap();
332        assert_execution::<ListVal, Vec<Val>>("(tail $0)", &[arg], vec![]);
333
334        // test fix
335        let arg = ListVal::val_of_prim("[]".into()).unwrap();
336        assert_execution("(fix_flip $0 (lam (lam (if (is_empty $0) 0 (+ 1 ($1 (tail $0)))))))", &[arg], 0);
337        let arg = ListVal::val_of_prim("[1,2,3,2,1]".into()).unwrap();
338        assert_execution("(fix_flip $0 (lam (lam (if (is_empty $0) 0 (+ 1 ($1 (tail $0)))))))", &[arg], 5);
339        let arg = ListVal::val_of_prim("[1,2,3,4,5]".into()).unwrap();
340        assert_execution("(fix_flip $0 (lam (lam (if (is_empty $0) $0 (cons (+ 1 (head $0)) ($1 (tail $0)))))))", &[arg], vec![2, 3, 4, 5, 6]);
341        let arg = ListVal::val_of_prim("[1,2,3,4,5]".into()).unwrap();
342        assert_error::<ListVal, Val>(
343            "(fix_flip $0 (lam (lam (if (is_empty $0) $0 (cons (+ 1 (head $0)) ($1 $0))))))",
344            &[arg],
345            format!("Exceeded max number of fix invocations. Max was {}", MAX_FIX_INVOCATIONS));
346    }
347}
lambdas/domains/prim_lists.rs

lambdas/domains/
prim_lists.rs
