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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
use std::rc::Rc;
use super::Context;
#[derive(Debug)]
pub struct Lambda(pub Rc<Tree>, pub Rc<Tree>);
#[derive(Debug)]
pub enum Tree {
Epsilon,
Bottom,
Identity,
Literal(String),
Variable,
Cat(Rc<Tree>, Rc<Tree>),
Alt(Rc<Tree>, Rc<Tree>),
Fix(Rc<Tree>),
Call(Rc<Tree>, Rc<Tree>),
Lambda(Lambda),
Let(Rc<Tree>, Rc<Tree>, Rc<Tree>),
}
impl Tree {
pub fn try_as_lambda(&self) -> Option<&Lambda> {
if let Self::Lambda(v) = self {
Some(v)
} else {
None
}
}
}
#[derive(Clone, Debug)]
pub enum TranslateError {
CallFunNotLambda(Rc<Tree>),
}
pub(crate) fn substitute(
ctx: &mut Context,
tree: &Rc<Tree>,
from: &Rc<Tree>,
into: &Rc<Tree>,
) -> Option<Rc<Tree>> {
if Rc::ptr_eq(tree, from) {
return Some(into.clone());
}
match tree.as_ref() {
Tree::Epsilon | Tree::Bottom | Tree::Identity | Tree::Literal(_) | Tree::Variable => None,
Tree::Cat(front, back) => {
let new_front = ctx.substitute(front, from, into);
let new_back = ctx.substitute(back, from, into);
let (front, back) = match (new_front, new_back) {
(None, None) => return None,
(None, Some(back)) => (front.clone(), back),
(Some(front), None) => (front, back.clone()),
(Some(front), Some(back)) => (front, back),
};
Some(ctx.tree_interner.cat(front, back))
}
Tree::Alt(left, right) => {
let new_left = ctx.substitute(left, from, into);
let new_right = ctx.substitute(right, from, into);
let (left, right) = match (new_left, new_right) {
(None, None) => return None,
(None, Some(right)) => (left.clone(), right),
(Some(left), None) => (left, right.clone()),
(Some(left), Some(right)) => (left, right),
};
Some(ctx.tree_interner.alt(left, right))
}
Tree::Fix(inner) => {
let inner = ctx.substitute(inner, from, into)?;
Some(ctx.tree_interner.fix(inner))
}
Tree::Call(fun, arg) => {
let new_fun = ctx.substitute(fun, from, into);
let new_arg = ctx.substitute(arg, from, into);
let (fun, arg) = match (new_fun, new_arg) {
(None, None) => return None,
(None, Some(arg)) => (fun.clone(), arg),
(Some(fun), None) => (fun, arg.clone()),
(Some(fun), Some(arg)) => (fun, arg),
};
Some(ctx.tree_interner.call(fun, arg))
}
Tree::Lambda(Lambda(arg, inner)) => {
let inner = ctx.substitute(inner, from, into)?;
Some(Rc::new(Tree::Lambda(Lambda(arg.clone(), inner))))
}
Tree::Let(bind, arg, inner) => {
let new_bind = ctx.substitute(bind, from, into);
let new_inner = ctx.substitute(inner, from, into);
let (bind, inner) = match (new_bind, new_inner) {
(None, None) => return None,
(None, Some(inner)) => (bind.clone(), inner),
(Some(bind), None) => (bind, inner.clone()),
(Some(bind), Some(inner)) => (bind, inner),
};
Some(Rc::new(Tree::Let(bind, arg.clone(), inner)))
}
}
}
pub(crate) fn translate(
ctx: &mut Context,
tree: &Rc<Tree>,
) -> Result<Option<Rc<Tree>>, TranslateError> {
match tree.as_ref() {
Tree::Epsilon
| Tree::Bottom
| Tree::Identity
| Tree::Literal(_)
| Tree::Variable
| Tree::Cat(_, _)
| Tree::Alt(_, _)
| Tree::Fix(_)
| Tree::Lambda(_) => Ok(None),
Tree::Call(fun, arg) => {
let fun = ctx.translate(fun)?.unwrap_or_else(|| fun.clone());
let lambda = fun
.try_as_lambda()
.ok_or_else(|| TranslateError::CallFunNotLambda(fun.clone()))?;
let mut out = ctx
.substitute(&lambda.1, &lambda.0, arg)
.unwrap_or_else(|| lambda.1.clone());
loop {
match ctx.translate(&out)? {
Some(tree) => out = tree,
None => return Ok(Some(out)),
}
}
}
Tree::Let(bind, arg, inner) => {
let mut out = ctx
.substitute(inner, arg, bind)
.unwrap_or_else(|| inner.clone());
loop {
match ctx.translate(&out)? {
Some(tree) => out = tree,
None => return Ok(Some(out)),
}
}
}
}
}
|
