timi/
machine.rs

1// Machine that performs interpretation. 
2//! The machine state is formed out of 4 components: `(Stack, Heap, Dump, Globals)`
3extern crate ansi_term;
4
5use std::fmt;
6use std::collections::HashMap;
7use std::collections::HashSet;
8
9use std;
10
11use ir::*;
12use pretty_print::format_addr_string;
13use frontend;
14
15
16use self::ansi_term::Style;
17
18
19
20/// Primitive operations that are implemented directly in the machine
21#[derive(Clone, PartialEq, Eq)]
22pub enum MachinePrimOp {
23    /// Add two machine integers
24    Add,
25    /// Subtract two machine integers
26    Sub,
27    /// Multiply two machine integers
28    Mul,
29    /// Divide two machine integers
30    Div,
31    /// Negate a machine integer
32    Negate,
33    /// Compare two integers and return if LHS > RHS
34    G,
35    /// Compare two integers and return if LHS >= RHS
36    GEQ,
37    /// Compare two integers and return if LHS < RHS
38    L,
39    /// Compare two integers and return if LHS >= RHS
40    LEQ,
41    /// Compare two integers and return if LHS == RHS
42    EQ,
43    /// Compare two integers and return if LHS != RHS
44    NEQ,
45    /// Construct a complex object which is tagged with `DataTag`
46    /// and takes `arity` number of components.
47    Construct {
48        /// Tag used to disambiguate between different data objects
49        tag: DataTag,
50        /// number of components that the complex object has.
51        arity: u32
52    },
53    /// Check a predicate and run the `then` or `else` clause
54    If,
55    /// Explode a tuple and pass the `left` and `right` components of a tuple to a function
56    CasePair,
57    /// Perform case analysis on a list.
58    CaseList,
59    /// Undefined. Machine will quit on reaching this address. Useful for testing code that
60    /// should never run
61    Undef,
62}
63
64impl fmt::Debug for MachinePrimOp {
65    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
66        match self {
67            &MachinePrimOp::Negate => write!(fmt, "Negate"),
68            &MachinePrimOp::Add => write!(fmt, "+"),
69            &MachinePrimOp::Sub => write!(fmt, "-"),
70            &MachinePrimOp::Mul => write!(fmt, "*"),
71            &MachinePrimOp::Div => write!(fmt, "/"),
72            &MachinePrimOp::G => write!(fmt, ">"),
73            &MachinePrimOp::L => write!(fmt, "<"),
74            &MachinePrimOp::GEQ => write!(fmt, ">="),
75            &MachinePrimOp::LEQ => write!(fmt, "<="),
76            &MachinePrimOp::EQ => write!(fmt, "=="),
77            &MachinePrimOp::NEQ => write!(fmt, "!="),
78            &MachinePrimOp::If => write!(fmt, "if"),
79            &MachinePrimOp::CasePair => write!(fmt, "casePair"),
80            &MachinePrimOp::CaseList => write!(fmt, "caseList"),
81            &MachinePrimOp::Undef => write!(fmt, "undef"),
82            &MachinePrimOp::Construct{ref tag, ref arity} => {
83                write!(fmt, "Construct(tag:{:#?} | arity: {})", tag, arity)
84            }
85        }
86    }
87}
88
89
90#[derive(Clone,PartialEq,Eq,Debug)]
91/// Used to tag data in `HeapNode::Data`.
92pub enum DataTag {
93    TagFalse = 0,
94    TagTrue = 1,
95    TagPair = 2,
96    TagListNil = 3,
97    TagListCons = 4,
98}
99
100/// convert an integer data tag that is obtained from a [`CoreExpr::Pack.tag`](../ir/enum.CoreExpr.html)
101/// into a [`DataTag`](enum.DataTag.html)
102fn raw_tag_to_data_tag (raw_tag: u32) -> Result<DataTag, MachineError> {
103    match raw_tag {
104        0 => Ok(DataTag::TagFalse),
105        1 => Ok(DataTag::TagTrue),
106        2 => Ok(DataTag::TagPair),
107        3 => Ok(DataTag::TagListNil),
108        4 => Ok(DataTag::TagListCons),
109        other @ _ => Err(format!(
110                "expected False(0), \
111                 True(1), or Pair(2). \
112                 found: {}",
113                 other))
114    }
115} 
116
117
118#[derive(Clone, PartialEq, Eq)]
119/// an element on the [`Heap`](struct.HeapNode) of the machine.
120pub enum HeapNode {
121    /// Function application of function at `fn_addr` to function at `arg_addr`
122    Application {
123        fn_addr: Addr,
124        arg_addr: Addr
125    },
126    /// a Supercombinator (top level function) that is created on the heap
127    Supercombinator(SupercombDefn),
128    /// Raw integer
129    Num(i32),
130    /// An indirection from the current heap address to another heap address.
131    /// Used to reduce work done by machine by preventing re-computation.
132    Indirection(Addr),
133    /// A primitive that needs to be executed.
134    Primitive(MachinePrimOp),
135    /// Complex data on the Heap with tag `tag`. Components are at the
136    /// `component_addrs`.
137    Data{tag: DataTag, component_addrs: Vec<Addr>}
138}
139
140
141/// makes the heap tag bold
142fn format_heap_tag(s: &str) -> String {
143    format!("{}", Style::new().bold().paint(s))
144}
145
146impl fmt::Debug for HeapNode {
147    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
148
149
150        match self {
151            &HeapNode::Application{ref fn_addr, ref arg_addr} => {
152                write!(fmt, "{}({} $ {})", 
153                       format_heap_tag("H-Ap"),
154                       format_addr_string(fn_addr),
155                       format_addr_string(arg_addr))
156            }
157            &HeapNode::Supercombinator(ref sc_defn) => {
158                write!(fmt, "{}({:#?})", 
159                       format_heap_tag("H-Supercombinator"),
160                       sc_defn)
161            },
162            &HeapNode::Num(ref num)  => {
163                write!(fmt, "{}({})", 
164                       format_heap_tag("H-Num"),
165                       num)
166            }
167            &HeapNode::Indirection(ref addr)  => {
168                write!(fmt, "{}({})",
169                format_heap_tag("H-Indirection"),
170                format_addr_string(addr))
171            }
172            &HeapNode::Primitive(ref primop)  => {
173                write!(fmt, "{}({:#?})",
174                format_heap_tag("H-Primitive"),
175                primop)
176            },
177            &HeapNode::Data{ref tag, ref component_addrs} => {
178                try!(write!(fmt, "{}(tag: {:#?}",
179                            format_heap_tag("H-Data"),
180                            tag));
181
182                if component_addrs.len() == 0 {
183                    try!(write!(fmt, ")"))
184                }
185                else {
186                    try!(write!(fmt, " | data: "));
187                    for addr in component_addrs.iter() {
188                        try!(write!(fmt, "{} ", format_addr_string(addr)));
189                    }
190                    try!(write!(fmt, ")"));
191                }
192                Ok(())
193
194            }
195        }
196    }
197}
198
199impl HeapNode {
200    fn is_data_node(&self) -> bool {
201        match self {
202            &HeapNode::Num(_) => true,
203            &HeapNode::Data{..} => true,
204            _ => false
205        }
206    }
207}
208
209
210/// Tries to unwrap a heap node to an application node,
211/// fails if the heap node is not application.
212///
213/// # Use Case
214/// unwrapping application nodes is a very common process
215/// when implementing primitives. This abstracts out the process
216/// and reduces code duplication
217fn unwrap_heap_node_to_ap(node: HeapNode) -> 
218Result<(Addr, Addr), MachineError> {
219
220    match node {
221        HeapNode::Application{fn_addr, arg_addr} => 
222            Ok((fn_addr, arg_addr)),
223            other @ _ => Err(format!(
224                    "expected application node, \
225                                         found: {:#?}", other))
226    }
227}
228
229/// Dump is a stack of [machine `Stack`](struct.Stack.html).
230///
231/// # Use Case
232/// It is used to store intermediate execution of primitives.
233/// That way, a complex computation can be stored on a dump. 
234/// A sub computation can be run, after which the complex computation can be
235/// brought back into scope.
236pub type Dump = Vec<Stack>;
237
238/// Stack is a stack of [`Addr`](../ir/type.Addr.html).
239/// 
240/// # Use Case
241/// Function application is "unwound" on the stack.
242#[derive(Clone,PartialEq,Eq,Debug)]
243pub struct Stack {
244    stack: Vec<Addr>
245}
246
247impl Stack {
248    pub fn new() -> Stack {
249        Stack {
250            stack: Vec::new(),
251        }
252    }
253
254    /// return number of elements on the stack.
255    pub fn len(&self) -> usize {
256        self.stack.len()
257    }
258
259    /// push an address on top of the stack.
260    pub fn push(&mut self, addr: Addr) {
261        self.stack.push(addr)
262    }
263
264    /// pops the top of the stack.
265    ///
266    /// # Errors
267    /// returns an error if the stack is empty
268    pub fn pop(&mut self) -> Result<Addr, MachineError> {
269        self.stack.pop().ok_or("top of stack is empty".to_string())
270    }
271
272    /// peeks the top of the stack.
273    ///
274    /// *NOTE:*  does _not_ remove the element on the top of the stack.
275    pub fn peek(&self) -> Result<Addr, MachineError> {
276        self.stack.last().cloned().ok_or("top of stack is empty to peek".to_string())
277    }
278
279    /// returns an iterator to the stack elements. 
280    ///
281    /// *NOTE:* top of the stack is returned first, bottom of the stack
282    /// is returned last.
283    pub fn iter(&self) -> std::iter::Rev<std::slice::Iter<Addr>> {
284        self.stack.iter().rev()
285    }
286
287}
288
289/// Mapping from [variable names](../ir/type.Name.html) to
290/// [addresses](type.Addr.html).
291pub type Environment = HashMap<Name, Addr>;
292
293#[derive(Clone)]
294/// maps Address to Heap nodes. 
295pub struct Heap {
296    heap: HashMap<Addr, HeapNode>,
297    next_addr: Addr
298}
299
300impl fmt::Debug for Heap {
301    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
302        let mut keyvals : Vec<(&Addr, &HeapNode)> = self.heap.iter().collect();
303        keyvals.sort_by(|a, b| a.0.cmp(b.0));
304
305        for &(key, val) in keyvals.iter().rev() {
306            try!(write!(fmt, "\t{} => {:#?}\n", format_addr_string(key), val));
307        }
308
309        return Ok(())
310
311    }
312}
313
314impl Heap {
315    pub fn new()  -> Heap {
316        Heap {
317            heap: HashMap::new(),
318            next_addr: 0
319        }
320    }
321
322    /// Allocate the HeapNode on the heap. returns the address at which
323    /// the node was allocated.
324    pub fn alloc(&mut self, node: HeapNode) -> Addr {
325        let addr = self.next_addr;
326        self.next_addr += 1;
327
328        self.heap.insert(addr, node);
329        addr
330    }
331
332    /// returns the heap node at address Addr
333    ///
334    /// ### Panics
335    ///
336    /// `get` panics if the address does not exist on the heap. To check
337    /// if an address is on the heap, use [contains](struct.Heap.html#method.contains)
338    pub fn get(&self, addr: &Addr) -> HeapNode {
339        self.heap
340            .get(&addr)
341            .cloned()
342            .expect(&format!("expected heap node at addess: {}", addr))
343    }
344
345    /// rewrites the address `addr` with new heap node `node`
346    ///
347    /// ### Panics
348    /// if the heap node at `addr` does not exist, this function will panic
349    pub fn rewrite(&mut self, addr: &Addr, node: HeapNode) {
350        assert!(self.heap.contains_key(addr),
351        "asked to rewrite (address: {}) with \
352        (node: {:#?}) which does not exist on heap",
353        addr, node);
354        self.heap.insert(*addr, node);
355    }
356
357    /// returns the number of elements in the heap
358    pub fn len(&self) -> usize {
359        self.heap.len()
360    }
361
362    /// returns whether the heap contains an element at address `addr`.
363    pub fn contains(&self, addr: &Addr) -> bool {
364        match self.heap.get(&addr) {
365            Some(_) => true,
366            None => false
367        }
368    }
369
370}
371
372/// Options used to configure the machine
373#[derive(Clone)]
374pub struct MachineOptions {
375    /// controls whether a function application node should be rewritten
376    /// with the final value after evaluation.
377    ///
378    /// Enable this to see the use of `Indirection` nodes.
379    pub update_heap_on_sc_eval: bool,
380}
381
382#[derive(Clone)]
383/// the core machine that runs our program.
384pub struct Machine {
385    pub stack : Stack,
386    pub heap : Heap,
387    pub globals: Environment,
388    pub dump: Dump,
389    pub options: MachineOptions,
390}
391
392/// represents an error during the execution of the machine
393pub type MachineError = String;
394
395
396/// converts a boolean into a HeapNode for True and False
397fn bool_to_heap_node(b: bool) -> HeapNode {
398    if b {
399        HeapNode::Primitive(MachinePrimOp::Construct{tag: DataTag::TagTrue,
400            arity: 0})
401    }
402    else {
403        HeapNode::Primitive(MachinePrimOp::Construct{tag: DataTag::TagFalse,
404            arity: 0})
405    }
406}
407
408
409/// constructs the prelude program for the machine.
410fn get_prelude() -> CoreProgram {
411
412    let program_str = "I x = x;\n\
413                        K x y = x;\n\
414                        K1 x y = y;\n\
415                        S f g x = f x (g x);\n\
416                        compose f g x = f (g x);\n\
417                        twice f = compose f f;\n\
418                        False = Pack{0, 0};\n\
419                        True = Pack{1, 0};\n\
420                        MkPair = Pack{2, 2};\n\
421                        Nil = Pack{3, 0};\n\
422                        Cons = Pack{4, 2};\n\
423                        Y f = f (Y f);\n\
424                        facrec f n = if (n == 0) 1 (n * f (n - 1));\n\
425                        fac n = (Y facrec) n\n\
426                        ";
427    match frontend::string_to_program(program_str) {
428        Ok(program) => program,
429        Err(e) => panic!("prelude compilation failed:\n{}", e.pretty_print(program_str))
430    }
431}
432
433/// mapping between strings for primitives and the primitive operation
434fn get_primitives() -> Vec<(Name, MachinePrimOp)> {
435    [("+".to_string(), MachinePrimOp::Add),
436    ("-".to_string(), MachinePrimOp::Sub),
437    ("*".to_string(), MachinePrimOp::Mul),
438    ("/".to_string(), MachinePrimOp::Div),
439    (">".to_string(), MachinePrimOp::G),
440    ("<".to_string(), MachinePrimOp::L),
441    (">=".to_string(), MachinePrimOp::GEQ),
442    ("<=".to_string(), MachinePrimOp::LEQ),
443    ("!=".to_string(), MachinePrimOp::NEQ),
444    ("==".to_string(), MachinePrimOp::EQ),
445    ("negate".to_string(), MachinePrimOp::Negate),
446    ("if".to_string(), MachinePrimOp::If),
447    ("casePair".to_string(), MachinePrimOp::CasePair),
448    ("caseList".to_string(), MachinePrimOp::CaseList),
449    ("undef".to_string(), MachinePrimOp::Undef)
450    ].iter().cloned().collect()
451}
452
453
454/// builds the initial heap and environment corresponding to the
455/// program given.
456///
457/// This allocates heap nodes for supercombinators in `sc_defs` and
458/// primitives in `prims` and maps their names
459/// to the allocated addresses in `Environment`.
460fn build_heap_and_env_for_program(sc_defs: CoreProgram,
461                                  prims: Vec<(Name, MachinePrimOp)>) 
462    -> (Heap, Environment) {
463
464        let mut heap = Heap::new();
465        let mut globals = HashMap::new();
466
467        for sc_def in sc_defs.iter() {
468            //create a heap node for the Supercombinator definition
469            //and insert it
470            let node = HeapNode::Supercombinator(sc_def.clone());
471            let addr = heap.alloc(node);
472
473            //insert it into the globals, binding the name to the
474            //heap address
475            globals.insert(sc_def.name.clone(), addr);
476        }
477
478        for (name, prim_op) in prims.into_iter() {
479            let addr = heap.alloc(HeapNode::Primitive(prim_op));
480            globals.insert(name, addr);
481        }
482
483        (heap, globals)
484    }
485
486impl Machine {
487    /// Create a minimal machine that has the prelude and primitives instantiated,
488    /// but with an empty stack.
489    pub fn new_minimal() -> Machine {
490        let (initial_heap, globals) = build_heap_and_env_for_program(get_prelude(),
491        get_primitives());
492
493        Machine {
494            dump: Vec::new(),
495            stack:  Stack::new(),
496            globals: globals,
497            heap: initial_heap,
498            options: MachineOptions {
499                update_heap_on_sc_eval: true
500            }
501        }
502
503    }
504
505    /// Create a machine from `program`. Expects a `main` to be present
506    /// in the given program.
507    ///
508    /// ###Errors
509    /// returns an error if `main` was not found
510    pub fn new_from_program(program: CoreProgram) -> Result<Machine, MachineError> {
511        let mut m = Machine::new_minimal();
512
513        for sc in program.into_iter() {
514            m.add_supercombinator(sc);
515        }
516
517        try!(m.setup_supercombinator_execution("main"));
518
519        Result::Ok(m)
520
521    }
522
523    /// Add the supercombinator to the machine. 
524    ///
525    /// This will allocate the supercombinator on the heap and create a binding
526    /// in the environment to the name of the supercombinator.
527    /// 
528    /// Returns the address of allocation of the supercombinator
529    pub fn add_supercombinator(&mut self, sc_defn: SupercombDefn) -> Addr {
530        let name = sc_defn.name.clone();
531        let node = HeapNode::Supercombinator(sc_defn);
532        let addr = self.heap.alloc(node);
533
534        //insert it into the globals, binding the name to the
535        //heap address
536        self.globals.insert(name, addr);
537        addr
538    }
539
540    /// setup the execution of a registered supercombinator with name sc_name.
541    pub fn setup_supercombinator_execution(&mut self,
542                                           sc_name: &str) -> Result<(), MachineError> {
543
544        let main_addr = try!(self.globals
545                            .get(sc_name)
546                            .ok_or(format!("supercombinator with name: {} not found", sc_name)));
547        self.stack = Stack::new();
548        self.stack.push(*main_addr);
549
550        Ok(())
551    }
552
553    /// returns whether the machine is in final state or not.
554    ///
555    /// ### Errors
556    /// Returns `MachineError` if machine is in invalid state
557    pub fn is_final_state(&self) -> Result<bool, MachineError> {
558        if self.stack.len() == 0 {
559            return Err("expect stack to have at least 1 node".to_string())
560        }
561
562        if self.stack.len() > 1 {
563            Ok(false)
564        } else {
565            let dump_empty = self.dump.len() == 0;
566            //unwrap() is safe since we known that stack.len > 0
567            Ok(self.heap.get(&self.stack.peek().unwrap()).is_data_node() &&
568                dump_empty)
569        }
570    }
571
572    /// dump the current stack into the dump, and create a fresh stack
573    fn dump_stack(&mut self, stack: Stack) {
574        self.dump.push(stack);
575        self.stack = Stack::new();
576    }
577
578    /// inspect the top of the stack and take a step in interpretation if
579    /// we are not in the final state
580    pub fn step(&mut self) -> Result<(), MachineError> { 
581        //top of stack
582        let tos_addr : Addr = try!(self.stack.peek());
583        let heap_val = self.heap.get(&tos_addr);
584
585
586        //there is something on the dump that wants to use this
587        //data node, so pop it back.
588        if heap_val.is_data_node() && self.dump.len() > 0 {
589            self.stack = self.dump
590                .pop()
591                .expect("dump should have at least 1 element");
592            Ok(())
593        } else {
594            self.heap_node_step(&heap_val)
595        }
596    }
597
598    /// perform an interpretation step by case analysis of the given heap node
599    /// (which is the top of the stack)
600    fn heap_node_step(&mut self, tos_node: &HeapNode) -> Result<(), MachineError> {
601        match tos_node {
602            &HeapNode::Num(n) => {
603                return Err(format!("number applied as a function: {}", n));
604            }
605
606            data @ &HeapNode::Data{..} => {
607                return Err(format!(
608                        "data node applied as function: {:#?}", data));
609            }
610            &HeapNode::Application{fn_addr, ..} => {
611                //push function address over the function
612                self.stack.push(fn_addr);
613            }
614            &HeapNode::Indirection(ref addr) => {
615                //simply ignore an indirection during execution, and
616                //push the indirected value on the stack
617                try!(self.stack.pop());
618                self.stack.push(*addr);
619            }
620            //expand supercombinator
621            &HeapNode::Supercombinator(ref sc_defn) => {
622                try!(run_supercombinator(self, sc_defn));
623            }
624
625            &HeapNode::Primitive(MachinePrimOp::Negate) => {
626                try!(run_primitive_negate(self));
627            }
628            &HeapNode::Primitive(MachinePrimOp::Add) => {
629                try!(run_primitive_num_binop(self,
630                    |x, y| HeapNode::Num(x + y)));
631            }
632            &HeapNode::Primitive(MachinePrimOp::Sub) => {
633                try!(run_primitive_num_binop(self,
634                    |x, y| HeapNode::Num(x - y)));
635            }
636            &HeapNode::Primitive(MachinePrimOp::Mul) => {
637                try!(run_primitive_num_binop(self,
638                    |x, y| HeapNode::Num(x * y)));
639            }
640            &HeapNode::Primitive(MachinePrimOp::Div) => {
641                try!(run_primitive_num_binop(self,
642                    |x, y| HeapNode::Num(x / y)));
643            }
644            //construct a complex type
645            &HeapNode::Primitive(MachinePrimOp::Construct {ref tag, arity}) => {
646                try!(run_constructor(self, tag, arity));
647            }
648            //boolean ops
649            &HeapNode::Primitive(MachinePrimOp::G) => {
650                try!(run_primitive_num_binop(self,
651                    |x, y| bool_to_heap_node(x > y)));
652            }
653            &HeapNode::Primitive(MachinePrimOp::GEQ) => {
654                try!(run_primitive_num_binop(self,
655                        |x, y| bool_to_heap_node(x >= y)));
656            }
657            &HeapNode::Primitive(MachinePrimOp::L) => {
658                try!(run_primitive_num_binop(self,
659                    |x, y| bool_to_heap_node(x < y)));
660            }
661            &HeapNode::Primitive(MachinePrimOp::LEQ) => {
662                try!(run_primitive_num_binop(self,
663                    |x, y| bool_to_heap_node(x <= y)));
664            }
665            &HeapNode::Primitive(MachinePrimOp::EQ) => {
666                try!(run_primitive_num_binop(self,
667                    |x, y| bool_to_heap_node(x == y)));
668            }
669            &HeapNode::Primitive(MachinePrimOp::NEQ) => {
670                try!(run_primitive_num_binop(self,
671                    |x, y| bool_to_heap_node(x != y)));
672            }
673            //run if condition
674            &HeapNode::Primitive(MachinePrimOp::If) => {
675                try!(run_primitive_if(self));
676            }
677            &HeapNode::Primitive(MachinePrimOp::CasePair) => {
678                try!(run_primitive_case_pair(self));
679            }
680            &HeapNode::Primitive(MachinePrimOp::CaseList) => {
681                try!(run_primitive_case_list(self));
682            }
683            &HeapNode::Primitive(MachinePrimOp::Undef) => {
684                return Err("hit undefined operation".to_string())
685            }
686        };
687        Ok(())
688    }
689
690
691    /// given a supercombinator, realize it on the heap
692    /// by recursively instantiating its body, with respect to the environment `env.
693    /// The environment is used to find variable names.
694    fn instantiate(&mut self, expr: CoreExpr, env: &Environment) -> Result<Addr, MachineError> {
695        match expr {
696            CoreExpr::Let(CoreLet{expr: let_rhs, bindings, ..}) => {
697                let let_env = try!(instantiate_let_bindings(self, env, bindings));
698                self.instantiate(*let_rhs, &let_env)
699            }
700            CoreExpr::Num(x) => Ok(self.heap.alloc(HeapNode::Num(x))),
701            CoreExpr::Application(fn_expr, arg_expr) => {
702                let fn_addr = try!(self.instantiate(*fn_expr, env));
703                let arg_addr = try!(self.instantiate(*arg_expr, env));
704
705                Ok(self.heap.alloc(HeapNode::Application {
706                    fn_addr: fn_addr,
707                    arg_addr: arg_addr
708                }))
709
710            }
711            CoreExpr::Variable(vname) => {
712                match env.get(&vname) {
713                    Some(addr) => Ok(*addr),
714                    None => Err(format!("unable to find variable in heap: |{}|", vname))
715                }
716
717            }
718            CoreExpr::Pack{tag, arity} => {
719                let prim_for_pack = 
720                    HeapNode::Primitive(MachinePrimOp::Construct{
721                        tag: try!(raw_tag_to_data_tag(tag)),
722                        arity: arity
723                    });
724
725                Ok(self.heap.alloc(prim_for_pack))
726
727            } 
728        }
729    }
730}
731
732///this will return a node that the address is bound to on the heap.
733///if there is no instantiation (which is possible in cases like)
734///let y = x; x = y in 10
735///this will return no address.
736fn find_root_heap_node_for_addr(fake_addr: &Addr,
737                                fake_to_instantiated_addr: &HashMap<Addr, Addr>,
738                                heap: &Heap) -> Option<Addr> {
739    let mut visited : HashSet<Addr> = HashSet::new();
740    let mut cur_addr = *fake_addr;
741
742    loop {
743        if visited.contains(&cur_addr) {
744            return None;
745        }
746
747        visited.insert(cur_addr);
748
749        if heap.contains(&cur_addr) {
750            return Some(cur_addr)
751        } else {
752            cur_addr = *fake_to_instantiated_addr
753                        .get(&cur_addr)
754                        .expect(&format!("expected to find address
755                                that is not in heap as a 
756                                let-created address: {}", cur_addr));
757
758        }
759    }
760
761
762
763
764}
765
766/// let bindings first bind to "phantom" addresses, after which
767/// they relink addresses to their correct locations. This
768/// lets us check if an address is phantom to prevent us from trying to access
769/// these 
770/// TODO: create an alegbraic data type for Addr to represent this, and not
771/// just using negative numbers. This is a hack.
772pub fn is_addr_phantom(addr: &Addr) -> bool {
773    *addr < 0
774
775}
776
777/// instantiate let bindings
778///
779/// This tricky case needs to be handled:
780/// ```
781/// let y = x; x = 10 in y + y
782/// ```
783/// here, if we instantiate `y`, then `x`, and then continue
784/// replacing addresses, `y` will get the temporary address of `x`.
785/// so, we need to use the "real" addresses of values
786fn instantiate_let_bindings(m: &mut Machine,
787                            orig_env: &Environment,
788                            bindings: Vec<(Name, Box<CoreExpr>)>) 
789    -> Result<Environment, MachineError> {
790
791        let mut env : Environment = orig_env.clone();
792
793        for (&(ref name, _), addr) in bindings.iter().zip(1..(bindings.len()+2))  {
794            env.insert(name.clone(), -(addr as i32));
795        }
796
797        let mut fake_to_instantiated_addr: HashMap<Addr, Addr> = HashMap::new();
798        let mut fake_addr_to_name: HashMap<Addr, String> = HashMap::new();
799
800        //instantiate RHS, while storing legit LHS addresses
801        for (bind_name, bind_expr) in bindings.into_iter() {
802            let inst_addr = try!(m.instantiate(*bind_expr.clone(), &env));
803            let fake_addr = try!(env.get(&bind_name)
804                                .ok_or(format!("unable to find |{}| in env", bind_name))).clone();
805
806
807            fake_to_instantiated_addr.insert(fake_addr, inst_addr);
808            fake_addr_to_name.insert(fake_addr, bind_name);
809        }
810
811
812        for  (&fake_addr, _) in fake_to_instantiated_addr.iter() {
813            let name = fake_addr_to_name
814                                .get(&fake_addr)
815                                .expect("environment must have let-binding name")
816                                .clone();
817
818            let new_addr = match find_root_heap_node_for_addr(&fake_addr,
819                                                              &fake_to_instantiated_addr,
820                                                              &m.heap) {
821                Some(addr) => addr,
822                None => return Err(format!(
823                        "variable contains cyclic definition: {}",
824                         name))
825                        
826            };
827
828            //replace address in globals
829            env.insert(name, new_addr);
830            //change all the "instantiation addresses" to the actual
831            //root of the heap node
832            for &inst_addr in fake_to_instantiated_addr.values() {
833
834                //something was actually instantiated: that is, it wasn't a variable
835                //pointing to another variable
836                //TODO: make this an algebraic data type rather than using negatives
837                //let x = 10; y = x in y will work for this
838                if !is_addr_phantom(&inst_addr) {
839                    change_addr_in_heap_node(fake_addr,
840                                             new_addr,
841                                             inst_addr,
842                                             &mut HashSet::new(),
843                                             &mut m.heap)
844                }
845            }
846
847        }
848
849        Ok(env)
850
851    }
852
853
854///edits the address recursively in the given heap node to
855///replace the `fake_addr` with `new_addr` **at** `edit_addr` node.
856///edited_addrs is a bookkeeping device used to make sure we don't recursively
857///edit things ad infitum.
858///
859/// Example of recursively editing addresses:
860/// let x = y x; y = x y
861/// 0 -> Ap (1 $ 0)
862/// 1 -> Ap (0 $ 1)
863fn change_addr_in_heap_node(fake_addr: Addr,
864                            new_addr: Addr,
865                            edit_addr: Addr,
866                            mut edited_addrs: &mut HashSet<Addr>,
867                            mut heap: &mut Heap) {
868
869    if is_addr_phantom(&edit_addr) {
870        return;
871    }
872
873    if edited_addrs.contains(&edit_addr) {
874        return;
875    } else { 
876        edited_addrs.insert(edit_addr);
877    }
878
879    match heap.get(&edit_addr) {
880        HeapNode::Data{component_addrs, tag} => {
881
882            let mut new_addrs = Vec::new();
883            for i in 0..component_addrs.len() {
884                if component_addrs[i] == fake_addr {
885                    new_addrs[i] = new_addr;
886                }
887                else {
888                    new_addrs[i] = component_addrs[i];
889                    change_addr_in_heap_node(fake_addr,
890                                             new_addr,
891                                             new_addrs[i],
892                                             &mut edited_addrs,
893                                             heap);
894                }
895            };
896
897            heap.rewrite(&edit_addr, 
898                         HeapNode::Data{component_addrs: new_addrs,
899                         tag:tag})
900        },
901        HeapNode::Application{fn_addr, arg_addr} => {
902            let new_fn_addr = if fn_addr == fake_addr {
903                new_addr
904            } else {
905                fn_addr
906            };
907
908
909            let new_arg_addr = if arg_addr == fake_addr {
910                new_addr
911            } else {
912                arg_addr
913            };
914
915            heap.rewrite(&edit_addr,
916                         HeapNode::Application{
917                             fn_addr: new_fn_addr,
918                             arg_addr: new_arg_addr
919                         });
920
921            //if we have not replaced, then recurse
922            //into the application calls
923            if fn_addr != fake_addr {
924                change_addr_in_heap_node(fake_addr,
925                                         new_addr,
926                                         fn_addr,
927                                         &mut edited_addrs,
928                                         &mut heap);
929
930            };
931
932            if arg_addr != fake_addr {
933                change_addr_in_heap_node(fake_addr,
934                                         new_addr,
935                                         arg_addr,
936                                         &mut edited_addrs,
937                                         &mut heap);
938            };
939
940
941        },
942        HeapNode::Indirection(ref addr) =>
943            change_addr_in_heap_node(fake_addr,
944                                     new_addr,
945                                     *addr,
946                                     &mut edited_addrs,
947                                     &mut heap),
948
949                                     HeapNode::Primitive(_) => {}
950        HeapNode::Supercombinator(_) => {}
951        HeapNode::Num(_) => {},
952    }
953
954}
955
956
957
958
959
960//TODO: rewrite code to follow the new style of peeking all of them
961//and then popping off all of them
962fn run_primitive_negate(m: &mut Machine) -> Result<(), MachineError> {
963    //we need a copy of the stack to push into the dump
964    let stack_copy = m.stack.clone();
965
966    //pop the primitive off
967    try!(m.stack.pop());
968
969    //we rewrite this addres in case of
970    //a raw number
971    let neg_ap_addr = try!(m.stack.peek());
972
973    //Apply <negprim> <argument>
974    //look at what argument is and dispatch work
975    let to_negate_val = 
976        match try!(setup_heap_node_access(m,
977                                          stack_copy, 
978                                          neg_ap_addr,
979                                          heap_try_num_access)) {
980            HeapAccessValue::Found(val) => val,
981            HeapAccessValue::SetupExecution => return Ok(())
982        };
983
984    m.heap.rewrite(&neg_ap_addr, HeapNode::Num(-to_negate_val));
985    Ok(())
986}
987
988    //0: if 
989    //1: if $ <cond> <- if_ap_addr
990    //2: if <cond> $ <then>
991    //3: if <cond> <then> $ <else>
992    fn run_primitive_if(m: &mut Machine) -> Result<(), MachineError> {
993        let stack_copy = m.stack.clone();
994
995
996
997        let if_ap_addr = try!(m.stack
998                              .iter()
999                              .nth(1)
1000                              .cloned()
1001                              .ok_or("expected condition, was not found on stack"));
1002
1003        let then_ap_addr = try!(m.stack
1004                                .iter()
1005                                .nth(2)
1006                                .ok_or("expected then application, was not found on stack".to_string())).clone();
1007
1008        let else_ap_addr = try!(m.stack
1009                                .iter()
1010                                .nth(3)
1011                                .ok_or("expected else application, was not found on stack".to_string())).clone();
1012
1013        let cond : bool = {
1014            match try!(setup_heap_node_access(m,
1015                                              stack_copy,
1016                                              if_ap_addr,
1017                                              heap_try_bool_access)) {
1018                HeapAccessValue::Found(b) => b,
1019                HeapAccessValue::SetupExecution => {
1020                    return Ok(())
1021                }
1022            }
1023        };
1024
1025        //pop off 0:, 1:, 2:
1026        try!(m.stack.pop()); 
1027        try!(m.stack.pop()); 
1028        try!(m.stack.pop()); 
1029
1030        if cond {
1031            let (_, then_addr) = try!(unwrap_heap_node_to_ap(m.heap.get(&then_ap_addr)));
1032            let then_node = m.heap.get(&then_addr);
1033            m.heap.rewrite(&else_ap_addr, then_node);
1034        }
1035        else {
1036            let (_, else_addr) = try!(unwrap_heap_node_to_ap(m.heap.get(&else_ap_addr)));
1037            let else_node = m.heap.get(&else_addr);
1038            m.heap.rewrite(&else_ap_addr, else_node);
1039        }
1040        Ok(())
1041    }
1042
1043    //0: casePair
1044    //1: casePair $ (left, right)
1045    //2: casePair (left, right) $ <case_handler>
1046    //on rewrite
1047    //2: (<case_handler> $ left) $ right
1048    fn run_primitive_case_pair(m: &mut Machine) -> Result<(), MachineError> {
1049        let stack_copy = m.stack.clone();
1050
1051
1052        let pair_ap_addr = try!(m.stack
1053                                .iter()
1054                                .nth(1)
1055                                .cloned()
1056                                .ok_or("expected pair parameter, was not found on stack"));
1057
1058        let case_handler_ap_addr = try!(m.stack
1059                                        .iter()
1060                                        .nth(2)
1061                                        .cloned()
1062                                        .ok_or("expected handler parameter, was not found on stack"));
1063
1064        let (_, case_handler_addr) = try!(unwrap_heap_node_to_ap(m.heap.get(&case_handler_ap_addr)));
1065        let (left_addr, right_addr) =  
1066            match try!(setup_heap_node_access(m,
1067                                              stack_copy,
1068                                              pair_ap_addr,
1069                                              heap_try_pair_access)) {
1070                HeapAccessValue::Found(pair) => { 
1071                    pair
1072                },
1073                HeapAccessValue::SetupExecution => {
1074                    return Ok(())
1075                }
1076            };
1077
1078
1079        //(f left) $ right
1080
1081        //(f left)
1082        let ap_f_left = HeapNode::Application{
1083            fn_addr: case_handler_addr, 
1084            arg_addr: left_addr};
1085
1086        let ap_f_left_addr = m.heap.alloc(ap_f_left);
1087
1088        //(f left) $ right
1089        let ap_outer = HeapNode::Application{
1090            fn_addr: ap_f_left_addr,
1091            arg_addr: right_addr};
1092
1093        //pop out 0:, 1:
1094        try!(m.stack.pop());
1095        try!(m.stack.pop());
1096
1097        //rewrite 2: with value
1098        m.heap.rewrite(&case_handler_ap_addr, ap_outer);
1099        Ok(())
1100    }
1101
1102    //Calling Convention
1103    //==================
1104    //caseList <list-param> <nil-handler> <cons-handler>
1105    //
1106    //Reduction Rules
1107    //===============
1108    //
1109    //Rule 1. (for Cons)
1110    //0: caseList
1111    //1: caseList $ (Cons x xs)
1112    //2: caseList Cons x xs $ <nil-handler>
1113    //3: caseList Cons x xs $ <nil-handler> $ <cons-handler>
1114    //on rewrite
1115    //3: <cons-handler> x xs
1116
1117    //Rule 2. (for Nil)
1118    //0: caseList
1119    //1: caseList $ (Nil)
1120    //2: caseList Nil $ <nil-handler>
1121    //3: caseList Nil $ <nil-handler> $ <cons-handler>
1122    //on rewrite
1123    //3: <nil-handler>
1124    fn run_primitive_case_list(m: &mut Machine) -> Result<(), MachineError> {
1125        let stack_copy = m.stack.clone();
1126
1127
1128        //caseList $ <list-param>
1129        let param_ap_addr = try!(m.stack
1130                                 .iter()
1131                                 .nth(1)
1132                                 .cloned()
1133                                 .ok_or("expected list parameter, was not found on stack"));
1134
1135        let nil_handler_ap_addr = try!(m.stack
1136                                       .iter()
1137                                       .nth(2)
1138                                       .cloned()
1139                                       .ok_or("expected nil handler, was not found on stack"));
1140
1141        let cons_handler_ap_addr = try!(m.stack
1142                                        .iter()
1143                                        .nth(3)
1144                                        .cloned()
1145                                        .ok_or("expected cons handler, was not found on stack"));
1146
1147
1148        let list_data =  
1149            match try!(setup_heap_node_access(m,
1150                                              stack_copy,
1151                                              param_ap_addr,
1152                                              heap_try_list_access)) {
1153                HeapAccessValue::Found(list_data) => list_data, 
1154                HeapAccessValue::SetupExecution => return Ok(())
1155
1156            };
1157
1158        //pop off 0: 1:, 2:
1159        try!(m.stack.pop());
1160        try!(m.stack.pop());
1161        try!(m.stack.pop());
1162
1163        match list_data {
1164            ListAccess::Nil => {
1165                let (_, nil_handler_addr) = try!(unwrap_heap_node_to_ap(m.heap.get(&nil_handler_ap_addr)));
1166                let nil_handler = m.heap.get(&nil_handler_addr);
1167
1168                m.heap.rewrite(&cons_handler_ap_addr, nil_handler)
1169            } 
1170            ListAccess::Cons(x_addr, xs_addr) => {
1171                // (<cons_handler> $ x) $ xs
1172                let (_, cons_handler_addr) = try!(unwrap_heap_node_to_ap(m.heap.get(&cons_handler_ap_addr)));
1173                let ap_x = HeapNode::Application{fn_addr: cons_handler_addr,
1174                arg_addr: x_addr};
1175                let ap_x_addr = m.heap.alloc(ap_x);
1176
1177                let ap_xs = HeapNode::Application{fn_addr: ap_x_addr,
1178                arg_addr: xs_addr};
1179
1180                m.heap.rewrite(&cons_handler_ap_addr, ap_xs);
1181            }
1182        };
1183
1184        Ok(())
1185    }
1186
1187
1188
1189//extractor should return an error if a node cannot have data
1190//extracted from. It should return None
1191//0: +
1192//1: (+ a)
1193//2: (+ a) b
1194//bottom-^
1195fn run_primitive_num_binop<F>(m: &mut Machine, handler: F) -> Result<(), MachineError> 
1196where F: Fn(i32, i32) -> HeapNode {
1197
1198    let stack_copy = m.stack.clone();
1199
1200    try!(m.stack.pop());
1201
1202
1203    let left_value = {
1204        //pop off left value
1205        let left_ap_addr = try!(m.stack.pop());
1206        match try!(setup_heap_node_access(m,
1207                                          stack_copy.clone(),
1208                                          left_ap_addr,
1209                                          heap_try_num_access)) {
1210            HeapAccessValue::Found(val) => val,
1211            HeapAccessValue::SetupExecution => return Ok(())
1212        }
1213    };
1214
1215    //do the same process for right argument
1216    //peek (+ a) b
1217    //we peek, since in the case where (+ a) b can be reduced,
1218    //we simply rewrite the node (+ a b) with the final value
1219    //(instead of creating a fresh node)
1220    let binop_ap_addr = try!(m.stack.peek());
1221    let right_value = 
1222        match try!(setup_heap_node_access(m, 
1223                                          stack_copy,
1224                                          binop_ap_addr,
1225                                          heap_try_num_access)) {
1226            HeapAccessValue::Found(val) => val,
1227            HeapAccessValue::SetupExecution => return Ok(())
1228        };
1229
1230    m.heap.rewrite(&binop_ap_addr, handler(left_value,
1231                                           right_value));
1232
1233    Ok(())
1234}
1235
1236/// Runs the constructor corresponding to `tag` and `arity`.
1237//NOTE: rewrite_addr will point to the address of the full constructor call.
1238//That way, when we dump the stack and use it to run something more complex,
1239//it will point to the correct location
1240//eg:
1241
1242//I
1243//stack: if (<complex expr) 1 2
1244//dump: []
1245
1246//II
1247//stack: <complex_expr>
1248//dump: if (<complex_expr> 1 2
1249
1250//III
1251//stack:
1252//..
1253//...
1254//<complex_expr> <- rewrite rule
1255//dump: if (<complex_expr> 1 2
1256
1257//IV
1258//stack: <rewritten complex expr>
1259//dump: if <rewritten complex expr> 1 2
1260fn run_constructor(m: &mut Machine,
1261                   tag: &DataTag,
1262                   arity: u32) -> Result<(), MachineError> {
1263
1264    //pop out constructor
1265    let mut rewrite_addr = try!(m.stack.pop());
1266
1267    if m.stack.len() < arity as usize {
1268        return Err(format!("expected to have \
1269                                       {} arguments to {:#?} \
1270                                       constructor, found {}",
1271                                       arity, 
1272                                       tag,
1273                                       m.stack.len()));
1274    }
1275
1276    let mut arg_addrs : Vec<Addr> = Vec::new();
1277
1278    //This will be rewritten with the data
1279    //since the fn call would have been something like:
1280    //##top##
1281    //(Prim (Constructor tag arity))
1282    //(Prim (Constructor tag arity) $ a)
1283    //(Prim (Constructor tag arity) a $ b)
1284    //( Prim (Constructor tag arity) a b $ c) <- to rewrite
1285    //##bottom##
1286
1287    for _ in 0..arity {
1288        let arg_ap_addr = try!(m.stack.pop());
1289        rewrite_addr = arg_ap_addr;
1290        let (_, arg_addr) = try!(unwrap_heap_node_to_ap(m.heap.get(&arg_ap_addr)));
1291        arg_addrs.push(arg_addr);
1292
1293    };
1294
1295    m.heap.rewrite(&rewrite_addr, 
1296                   HeapNode::Data{
1297                       component_addrs: arg_addrs,
1298                       tag: tag.clone()
1299                   });
1300
1301    m.stack.push(rewrite_addr);
1302    Ok(())
1303}
1304
1305/// Runs the given supercombinator by instantiating it on top of the stack.
1306fn run_supercombinator(m: &mut Machine, sc_defn: &SupercombDefn) -> Result<(), MachineError> {
1307
1308    //pop the supercombinator
1309    let sc_addr = try!(m.stack.pop());
1310
1311    //the arguments are the stack
1312    //values below the supercombinator. There
1313    //are (n = arity of supercombinator) arguments
1314    let arg_addrs = {
1315        let mut addrs = Vec::new();
1316        for _ in 0..sc_defn.args.len() {
1317            addrs.push(try!(m.stack.pop()));
1318        }
1319        addrs
1320    };
1321
1322    let env = try!(make_supercombinator_env(&sc_defn,
1323                                            &m.heap,
1324                                            &arg_addrs,
1325                                            &m.globals));
1326
1327    let new_alloc_addr = try!(m.instantiate(sc_defn.body.clone(), &env));
1328
1329    m.stack.push(new_alloc_addr);
1330
1331    if m.options.update_heap_on_sc_eval {
1332        //if the function call was (f x y), the stack will be
1333        //f
1334        //f x
1335        //(f x) y  <- final address in arg_addrs
1336        //we need to rewrite this heap value
1337        let full_call_addr = {
1338            //if the SC has 0 parameters (a constant), then eval the SC
1339            //and replace the SC itself
1340            if sc_defn.args.len() == 0 {
1341                sc_addr
1342            }
1343            else {
1344                *arg_addrs.last()
1345                    .expect(concat!("arguments has no final value ",
1346                                    "even though the Supercombinator ",
1347                                    "has >= 1 parameter"))
1348            }
1349        };
1350        m.heap.rewrite(&full_call_addr, HeapNode::Indirection(new_alloc_addr));
1351    }
1352
1353    Ok(())
1354}
1355
1356
1357/// Make an environment for the execution of the Supercombinator.
1358/// let f a b c = <body>
1359///
1360/// if a function call of the form `(f x y z)` was made,
1361/// the stack will look like
1362/// ```haskell
1363/// ---top---
1364/// f
1365/// f $ x <- first parameter x
1366/// (f $ x) $ y <- second parameter y
1367/// ((f $ x) $ y) $ z <- third parameter z
1368/// --------
1369/// ```
1370fn make_supercombinator_env(sc_defn: &SupercombDefn,
1371                            heap: &Heap,
1372                            stack_args:&Vec<Addr>,
1373                            globals: &Environment) -> Result<Environment, MachineError> {
1374
1375    assert!(stack_args.len() == sc_defn.args.len());
1376
1377    let mut env = globals.clone();
1378
1379    for (arg_name, application_addr) in
1380        sc_defn.args.iter().zip(stack_args.iter()) {
1381
1382            let application = heap.get(application_addr);
1383            let (_, param_addr) = try!(unwrap_heap_node_to_ap(application));
1384            env.insert(arg_name.clone(), param_addr);
1385
1386        }
1387    Ok(env)
1388}
1389
1390
1391
1392/// Represents a successful heap node access from [`setup_heap_node_access`](fn.setup_heap_node_access.html).
1393///
1394/// Either the heap node was found, in which case `Found<T>` is returned.
1395/// Otherwise, a complex heap node (function application) was found, whose
1396/// simplification was setup. 
1397enum HeapAccessValue<T> {
1398    Found(T),
1399    SetupExecution
1400}
1401
1402/// Represents the result of trying to access the heap using [`setup_heap_node_access`](fn.setup_heap_node_access.html).
1403///
1404/// Returns [`HeapAccessValue`](enum.HeapAccessValue.html) if the access succeeded.
1405type HeapAccessResult<T> = Result<HeapAccessValue<T>, MachineError>;
1406
1407/// Get a heap node of the kind that handler wants to get,
1408/// otherwise setup the heap so that unevaluated code
1409/// is evaluated to get something of this type.
1410///
1411/// ###TODO
1412/// Check if we can change semantics so it does not need to take the
1413/// application node as the parameter that's a little awkward
1414fn setup_heap_node_access<F, T>(m: &mut Machine,
1415                                stack_to_dump: Stack,
1416                                ap_addr: Addr,
1417                                access_handler: F ) -> HeapAccessResult<T>
1418where F: Fn(HeapNode) -> Result<T, MachineError> {
1419
1420    let (fn_addr, arg_addr) = try!(unwrap_heap_node_to_ap(m.heap.get(&ap_addr))); 
1421    let arg = m.heap.get(&arg_addr);
1422
1423    //setup indirection
1424    if let HeapNode::Indirection(ind_addr) = arg {
1425        //rewrite the indirection node directly with the application node
1426        //application that does into the indirection address
1427        m.heap.rewrite(&ap_addr, 
1428                       HeapNode::Application {
1429                           fn_addr: fn_addr,
1430                           arg_addr: ind_addr
1431                       });
1432        return Ok(HeapAccessValue::SetupExecution)
1433    };
1434
1435
1436    //it's not a data node, so this is something we need to still execute
1437    if !arg.is_data_node() {
1438        m.dump_stack(stack_to_dump);
1439        m.stack.push(arg_addr);
1440        return Ok(HeapAccessValue::SetupExecution)
1441    }
1442
1443    //give the node the access handler. it will either return the value
1444    //or fail to do so
1445    let access_result = try!(access_handler(arg));
1446    Ok(HeapAccessValue::Found(access_result))
1447}
1448
1449
1450/// try to access the heap node as a number.
1451///
1452/// returns an error if the heap node is not a `Num` node
1453fn heap_try_num_access(h: HeapNode) -> Result<i32, MachineError> {
1454    match h {
1455        HeapNode::Num(i) => Ok(i),
1456        other @ _ => Err(format!(
1457                "expected number, found: {:#?}", other))
1458    }
1459}
1460
1461
1462/// try to access the heap node as a boolean
1463///
1464/// returns an error if the heap node is not data with `TagTrue` or `TagFalse`.
1465fn heap_try_bool_access(h: HeapNode) -> Result<bool, MachineError> {
1466    match h {
1467        HeapNode::Data{tag: DataTag::TagFalse, ..} => Ok(false),
1468        HeapNode::Data{tag: DataTag::TagTrue, ..} => Ok(true),
1469        other @ _ => Err(format!(
1470                "expected true / false, found: {:#?}", other))
1471    }
1472}
1473
1474/// try to access the heap node as a pair
1475fn heap_try_pair_access(h: HeapNode) -> Result<(Addr, Addr), MachineError> {
1476    match h {
1477        HeapNode::Data{tag: DataTag::TagPair, ref component_addrs} => {
1478            let left = try!(component_addrs.get(0).ok_or(format!(
1479                        "expected left component, of pair {:#?}, was not found", h)));
1480            let right = try!(component_addrs.get(1).ok_or(format!(
1481                        "expected right component, of pair {:#?}, was not found", h)));
1482
1483            Ok((*left, *right))
1484        }
1485        other @ _ => 
1486            Err(format!(
1487                    "expected Pair tag, found: {:#?}", other))
1488    }
1489}
1490
1491/// Represents the result of accessing a heap node as a list.
1492/// either a `Nil` is found, or a `Cons` of two addresses is found
1493enum ListAccess { Nil, Cons (Addr, Addr) }
1494
1495/// try to access the heap node as list.
1496fn heap_try_list_access(h: HeapNode) -> Result<ListAccess, MachineError> {
1497    match h {
1498        HeapNode::Data{tag: DataTag::TagListNil,..} => {
1499            Ok(ListAccess::Nil)
1500        }
1501        HeapNode::Data{tag: DataTag::TagListCons, ref component_addrs} => {
1502            let x_addr = try!(component_addrs.get(0).cloned().ok_or(format!(
1503                        "expected first component of list, found {:#?}", h)));
1504            let xs_addr = try!(component_addrs.get(1).cloned().ok_or(format!(
1505                        "expected second component of list, found {:#?}", h)));
1506
1507            Ok((ListAccess::Cons(x_addr, xs_addr)))
1508        }
1509        other @ _ => 
1510            Err(format!(
1511                    "expected Pair tag, found: {:#?}", other))
1512    }
1513}
timi/machine.rs

timi/
machine.rs
