evaltrees 0.1.0

A simple term-rewriting interpreter that displays intermediate expressions.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

use std::cmp::Ordering;
use std::collections::BTreeSet;
use std::iter::once;

use ast::{Decl, Expr, Literal, Op, Pattern};
use typeck::ty::Ty;

/// A constraint, which holds two types equal.
///
/// Eq and Ord here are opaque to flipping; i.e. if
/// `Constraint(a, b) > Constraint(c, d)`, then
/// `Constraint(b, a) > Constraint(c, d)` as well.
#[derive(Clone, Debug, Eq)]
pub struct Constraint(pub Ty, pub Ty);

impl PartialEq for Constraint {
    fn eq(&self, other: &Constraint) -> bool {
        (self.0 == other.0 && self.1 == other.1) || (self.0 == other.1 && self.1 == other.0)
    }
}

impl Ord for Constraint {
    fn cmp(&self, other: &Constraint) -> Ordering {
        let l = if self.0 <= self.1 {
            (&self.0, &self.1)
        } else {
            (&self.1, &self.0)
        };
        let r = if other.0 <= other.1 {
            (&other.0, &other.1)
        } else {
            (&other.1, &other.0)
        };
        l.cmp(&r)
    }
}

impl PartialOrd for Constraint {
    fn partial_cmp(&self, other: &Constraint) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Decl<Ty> {
    /// Collects type constraints.
    pub(in typeck) fn collect_constraints(&self) -> BTreeSet<Constraint> {
        let mut ty = self.body.aux();
        for arg in self.args.iter().rev() {
            ty = Ty::Func(Box::new(arg.aux()), Box::new(ty));
        }

        self.args
            .iter()
            .flat_map(|arg| arg.collect_constraints())
            .chain(self.body.collect_constraints())
            .chain(once(Constraint(self.aux.clone(), ty)))
            .collect()
    }
}

impl Expr<Ty> {
    /// Collects type constraints.
    pub(in typeck) fn collect_constraints(&self) -> BTreeSet<Constraint> {
        match *self {
            Expr::If(ref c, ref t, ref e, ref ty) => vec![
                Constraint(c.aux(), Ty::Bool),
                Constraint(t.aux(), ty.clone()),
                Constraint(e.aux(), ty.clone()),
            ].into_iter()
                .chain(c.collect_constraints())
                .chain(t.collect_constraints())
                .chain(e.collect_constraints())
                .collect(),
            Expr::Literal(lit, ref ty) => once(Constraint(ty.clone(), lit.ty())).collect(),
            Expr::Op(Op::App, ref l, ref r, ref ty) => once(Constraint(
                l.aux(),
                Ty::Func(Box::new(r.aux()), Box::new(ty.clone())),
            )).chain(l.collect_constraints())
                .chain(r.collect_constraints())
                .collect(),
            Expr::Op(Op::Cons, ref l, ref r, ref ty) => vec![
                Constraint(r.aux(), ty.clone()),
                Constraint(r.aux(), Ty::List(Box::new(l.aux()))),
            ].into_iter()
                .chain(l.collect_constraints())
                .chain(r.collect_constraints())
                .collect(),
            // All other ops are int->int->int
            Expr::Op(_, ref l, ref r, ref ty) => vec![
                Constraint(l.aux(), Ty::Int),
                Constraint(r.aux(), Ty::Int),
                Constraint(ty.clone(), Ty::Int),
            ].into_iter()
                .chain(l.collect_constraints())
                .chain(r.collect_constraints())
                .collect(),
            Expr::Variable(_, _) => BTreeSet::new(),
        }
    }
}

impl Literal {
    /// Returns the type of the literal.
    fn ty(&self) -> Ty {
        match *self {
            Literal::False | Literal::True => Ty::Bool,
            Literal::Int(_) => Ty::Int,
            Literal::Nil => Ty::List(Box::new(Ty::fresh())),
        }
    }
}

impl Pattern<Ty> {
    /// Collects type constraints.
    fn collect_constraints(&self) -> BTreeSet<Constraint> {
        let mut constraints = BTreeSet::new();
        match *self {
            Pattern::Binding(_, _) => {}
            Pattern::Cons(ref l, ref r, ref ty) => {
                constraints.insert(Constraint(ty.clone(), r.aux()));
                constraints.insert(Constraint(ty.clone(), Ty::List(Box::new(l.aux()))));
                constraints.extend(l.collect_constraints());
                constraints.extend(r.collect_constraints());
            }
            Pattern::Literal(lit, ref ty) => {
                constraints.insert(Constraint(ty.clone(), lit.ty()));
            }
        }
        constraints
    }
}