Deriving Stack Effects

stack_effects.py

from functools import cmp_to_key

class StackItem:    pass

class Row(StackItem):
    def __init__(self, name=''):
        self.name = name
        
    def __repr__(self):
        return '..' + self.name
        
class Item(StackItem): 
    def __init__(self, name):
        self.name = name
        
    def __repr__(self):
        return self.name

class Quot(StackItem): 
    def __init__(self, name, inputs, outputs):
        self.name = name
        self.inputs = Sequence(inputs)
        self.outputs = Sequence(outputs)
        
    def __repr__(self):
        return '{}({} -- {})'.format(self.name, self.inputs, self.outputs)
    
    def substitute(self, a, b):
        self.inputs.substitute(a, b)
        self.inputs.flatten()
        self.outputs.substitute(a, b)
        self.outputs.flatten()
                
    def match(self, other):
        substitutions = []
        substitutions += self.inputs.match(other.inputs)
        substitutions += self.outputs.match(other.outputs)
        return substitutions
    
    
class Sequence:
    def __init__(self, values=None):
        if values is None:
            self.values = []
        elif isinstance(values, Sequence):
            self.values = values.values
        else:
            self.values = list(values)
        
    def len(self):
        return len(self.values)
    
    def contains(self, item):
        return item in self.values
    
    def top(self):
        return self.values[-1]
    
    def pop(self):
        return self.values.pop()
    
    def insert(self, i, x):
        assert isinstance(x, StackItem)
        self.values.insert(i, x)
        
    def grow(self, item_or_items):
        try:
            assert all(isinstance(x, StackItem) for x in item_or_items.values)
            self.values.extend(item_or_items.values)
            return
        except AttributeError:
            pass
        
        try:
            assert all(isinstance(x, StackItem) for x in item_or_items)
            self.values.extend(item_or_items)
        except TypeError:
            pass
        
        assert isinstance(item_or_items, StackItem)
        self.values.append(item_or_items)
        
    
    def substitute(self, a, b):
        for i in range(len(self.values)):
            if self.values[i] == a:
                self.values[i] = b
            elif isinstance(self.values[i], Quot):
                self.values[i].substitute(a, b)
        self.flatten()

    def match(self, other):
        substitutions = []
        for i, j in zip(range(self.len())[::-1], range(other.len())[::-1]):
            a, b = self.values[i], other.values[j]
            if isinstance(a, Item) and isinstance(b, Item):
                substitutions += [(a, b)]
            elif isinstance(a, Row):
                substitutions += [(a, Sequence(other.values[:j+1]))]
                break
            elif isinstance(b, Row):
                substitutions += [(b, Sequence(self.values[:i+1]))]
                break
            else:
                raise NotImplementedError('match {} with {}'.format(type(a).__name__, type(b).__name__))
        return substitutions
    
    def flatten(self):
        flat = []
        for x in self.values:
            try:
                flat.extend(x.values)
            except AttributeError:
                flat.append(x)
        self.values = flat
        
    def cmp(self, other):
        for i, j in zip(range(self.len())[::-1], range(other.len())[::-1]):
            a, b = self.values[i], other.values[j]
            if isinstance(a, Item) and isinstance(b, Item):
                continue
            elif isinstance(a, Row) and isinstance(b, Row):
                return 0
            elif isinstance(a, Row):
                return -1
            elif isinstance(b, Row):
                return 1
            else:
                raise NotImplementedError('compare {} with {}'.format(type(a).__name__, type(b).__name__))
        
    def __repr__(self):
        return ' '.join(str(i) for i in self.values)


def cmp_items(a, b):
    if isinstance(a, Row) and isinstance(b, Row):
        return 0
    
    if isinstance(a, Item) and isinstance(b, Item):
        return 0
    
    if isinstance(a, Quot) and isinstance(b, Quot):
        a.inputs.cmp(b.inputs)
        a.outputs.cmp(b.outputs)
        return 0
    
    if isinstance(a, Item) and isinstance(b, Quot):
        return -1
    
    if isinstance(a, Sequence) and isinstance(b, Row):
        return 1
    
    if isinstance(a, Sequence) and isinstance(b, Sequence):
        return a.cmp(b)
    
    raise NotImplementedError('compare {} with {}'.format(type(a).__name__, type(b).__name__))


class AbstractStack:
    def __init__(self):
        r = Row('a')
        self.inputs = Sequence([r])
        self.values = Sequence([r])
        self.substitutions = Substitutions()
        
    def __repr__(self):
        return '{} -- {}   ... with {}'.format(self.inputs, self.values, self.substitutions)
    
    def pop(self, targets):
        #targets = self.substitutions.check(targets)
        try:
            iter(targets)
        except TypeError:
            target = targets
            return self._pop(target)
        return [self._pop(t) for t in targets[::-1]][::-1]
    
    def _pop(self, target):
        top = self.values.top()       
        if isinstance(target, Row):
            x, self.values = self.values, Sequence()
            self.substitute(target, x)
            return x
        elif isinstance(top, Item):
            self.substitute(target, top)
            self.values.pop()
            return target
        elif isinstance(top, Row):
            self.add_input(target)
            return target
        elif isinstance(top, Quot) and isinstance(target, Quot):
            for a, b in top.match(target):
                self.substitute(a, b)
                target.substitute(a, b)
            self.values.pop()
            self.substitute(target, top)
            return target
        else:
            raise NotImplementedError('pop {} from {}'.format(type(target).__name__, type(top).__name__))
            
    def add_input(self, x):
        self.inputs.insert(1, x)
    
    def push(self, item):
        item = self.substitutions.check(item)
        self.values.grow(item)
            
    def substitute(self, a, b):
        for a, b in self.substitutions.add(a, b):
            self.inputs.substitute(a, b)
            self.values.substitute(a, b)
        self.inputs.flatten()
        self.values.flatten()
                
class Substitutions:
    def __init__(self):
        self.subs = {}
        
    def add(self, a, b):            
        items = [a, b]
        if a in self.subs:
            items.append(self.subs[a])
        if b in self.subs:
            items.append(self.subs[b])
        
        items.sort(key=cmp_to_key(cmp_items))
        
        b = items[-1]        
        try:
            iter(b)
            b = Sequence(b)
        except TypeError:
            if a == b: []
            b = Sequence([b])
        b.flatten()
        
        resubs = []    
        for a in items[:-1]:
            if isinstance(a, Sequence):
                if a.len() > 1:
                    raise TypeError("cannot substitute for sequence")
                a = a.values[0]
            
            if b.contains(a):
                raise RuntimeError("Invalid Substitution")
                
            
            self.subs[a] = b
            resubs.append((a, b))
            
        return resubs
    
    def check(self, x):
        try:
            try:
                return Sequence([self.subs[i] for i in x.values])
            except AttributeError:
                return self.subs[x]
        except KeyError:
            return x
    
    def __repr__(self):
        return str(self.subs)
    

def test4():    
    astack = AbstractStack()
    
    # [ + ] (..b -- ..b g(..e x -- ..e z))
    e = Row('e')
    g = astack.push(Quot('g', [e, Item('x')], [e, Item('z')]))
    
    # (..c f(..d i j -- ..d k) - ..c)  
    try:  
        d = Row('d')
        f = astack.pop(Quot('f', [d, Item('i'), Item('j')], [d, Item('k')]))
        c = astack.pop(Row('c'))   
        astack.push(c)
        
        print("Should have failed:", astack)
    except RuntimeError:
        print("OK")
    

def test3():    
    astack = AbstractStack()
    
    # [ + ] (..b -- ..b g(..e x y -- ..e z))
    e = Row('e')
    g = astack.push(Quot('g', [e, Item('x'), Item('y')], [e, Item('z')]))
    
    # CALL (..c f(..c -- ..d) - ..d)    
    c = Row('c')
    d = Row('d')    
    f = astack.pop(Quot('f', [c], [d]))    
    c = astack.pop(c)   
    astack.push(d)
    
    print(astack)
    
    
def test2():    
    astack = AbstractStack()
    
    # SWAP (..a x y -- ..a y x)    
    y = astack.pop(Item('y'))
    x = astack.pop(Item('x'))
    r = astack.pop(Row('a'))
    astack.push(r)
    astack.push(y)
    astack.push(x)
    
    # CALL (..a f(..a -- ..b) - ..b)    
    a = Row('a')
    b = Row('b')    
    f = astack.pop(Quot('f', [a], [b]))
    a = astack.pop(a)    
    astack.push(b)
    
    print(astack)
    
    
def test1():    
    astack = AbstractStack()
    
    # SWAP (..a x y -- ..a y x)    
    y = astack.pop(Item('y'))
    x = astack.pop(Item('x'))
    r = astack.pop(Row('a'))
    astack.push(r)
    astack.push(y)
    astack.push(x)
    
    # DROP (..b z -- ..b)
    z = astack.pop(Item('z'))
    r = astack.pop(Row('b'))
    astack.push(r)
    
    # DROP (..b z -- ..b)
    z = astack.pop(Item('z'))
    r = astack.pop(Row('b'))
    astack.push(r)
    
    # DROP (..b z -- ..b)
    z = astack.pop(Item('z'))
    r = astack.pop(Row('b'))
    astack.push(r)
    
    print(astack)

test1()
test2()
test3()
test4()

stack_effects.rs

use std::cell::RefCell;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::iter::FromIterator;
use std::rc::Rc;
use std::mem::replace;

type ItemRef = RefHash<StackItem>;

enum StackItem {
    Row(String),
    Item(String),
    Quotation(String, RefCell<Sequence>, RefCell<Sequence>),
}

impl StackItem {
    fn anonymous_row() -> ItemRef {
        RefHash::new(Rc::new(StackItem::Row(String::new())))
    }
    
    fn item(name: &str) -> ItemRef {
        RefHash::new(Rc::new(StackItem::Item(name.to_string())))
    }
    
    fn row(name: &str) -> ItemRef {
        RefHash::new(Rc::new(StackItem::Row(name.to_string())))
    }
    
    fn quot(name: &str, inputs: &[ItemRef], outputs: &[ItemRef]) -> ItemRef {
        RefHash::new(Rc::new(StackItem::Quotation(name.to_string(), 
            RefCell::new(inputs.iter().cloned().collect()), 
            RefCell::new(outputs.iter().cloned().collect()))))
    }
    
    fn compare(&self, other: &Self) -> ItemOrd {
        use StackItem::*;
        use ItemOrd::*;
        
        match (self, other) {
            (Row(_), Row(_)) => Equivalent,
            (Item(_), Item(_)) => Equivalent,
            (Quotation(_, ia, oa), Quotation(_, ib, ob)) => {
                // try to catch incompatible quotations
                if let Invalid = ia.borrow().compare(&ib.borrow()) { return Invalid }
                if let Invalid = oa.borrow().compare(&ob.borrow()) { return Invalid }
                // but consider them equivalent in general.
                Equivalent
            }
            (Item(_), Quotation(_, _, _)) => MoreGeneral,
            (Quotation(_, _, _), Item(_)) => MoreSpecific,
            (Row(_), _) => MoreGeneral,
            (_, Row(_)) => MoreSpecific,
        }
    }
    
    fn substitute(&self, a: &ItemRef, b: &Sequence) {
        match self {
            StackItem::Row(_) => {},
            StackItem::Item(_) => {}
            StackItem::Quotation(_, inps, outs) => {
                inps.borrow_mut().substitute(a, b);
                outs.borrow_mut().substitute(a, b);
            }
        }
    }
}

enum ItemOrd {
    MoreGeneral,
    Equivalent,
    MoreSpecific,
    Invalid,
}

impl From<ItemOrd> for std::cmp::Ordering {
    fn from(io: ItemOrd) -> Self {
        match io {
            ItemOrd::MoreGeneral => std::cmp::Ordering::Less,
            ItemOrd::Equivalent => std::cmp::Ordering::Equal,
            ItemOrd::MoreSpecific => std::cmp::Ordering::Greater,
            ItemOrd::Invalid => panic!("Invalid something somewhere"),
        }
    }
}

#[derive(Default, Clone)]
struct Sequence {
    values: Vec<ItemRef>,
}

impl Sequence {
    fn new() -> Self {
        Sequence::default()
    }
    
    fn single(item: ItemRef) -> Self {
        Sequence {
            values: vec![item],
        }
    }
    
    fn len(&self) -> usize {
        self.values.len()
    }
    
    fn contains(&self, item: &ItemRef) -> bool {
        self.values.contains(item)
    }
    
    fn extend(&mut self, other: Sequence) {
        self.values.extend(other.values)
    }
    
    fn insert(&mut self, idx: usize, item: ItemRef) {
        self.values.insert(idx, item)
    }
    
    fn pop(&mut self) -> Option<ItemRef> {
        self.values.pop()
    }
    
    fn into_item(self) -> ItemRef {
        assert_eq!(self.len(), 1);
        self.values.into_iter().next().unwrap()
    }
    
    fn substitute(&mut self, a: &ItemRef, b: &Sequence) {
        let mut i = 0;
        while i < self.len() {
            if &self.values[i] == a {
                let mut tmp = Vec::from(&self.values[..i]);
                tmp.extend(b.values.clone());
                tmp.extend(self.values[i+1..].iter().cloned());
                self.values = tmp;
                i += b.len();
            } else {
                self.values[i].substitute(a, b);
                i += 1;
            }
        }
    }
    
    fn compare(&self, other: &Sequence) -> ItemOrd {
        use ItemOrd::*;
        
        let av = self.values.iter().rev();
        let bv = other.values.iter().rev();
        
        for (a, b) in av.zip(bv) {
            match a.compare(b) {
                Equivalent => {},
                other => return other
            }
        }
        
        if self.len() == other.len() {
            Equivalent 
        } else {
            Invalid
        }
    }
    
    fn match_effects(&self, other: &Sequence) -> Vec<(ItemRef, Sequence)> {
        use StackItem::*;
        let mut subs = vec![];
        for (i, j) in (0..self.len()).rev().zip((0..other.len()).rev()) {
            let a = &self.values[i];
            let b = &other.values[j];
            match (&**a, &**b) {
                (Item(_), Item(_)) => subs.push((a.clone(), Sequence::single(b.clone()))),
                (Item(_), Quotation(_, _, _)) => subs.push((a.clone(), Sequence::single(b.clone()))),
                (Quotation(_, _, _), Item(_)) => subs.push((b.clone(), Sequence::single(a.clone()))),
                (Quotation(_, ref ia, ref oa), Quotation(_, ref ib, ref ob)) => {
                    subs.extend(ia.borrow().match_effects(&ib.borrow()));
                    subs.extend(oa.borrow().match_effects(&ob.borrow()));
                },
                (Row(_), _) => {
                    subs.push((a.clone(), Sequence::from_iter(&other.values[..=j])));
                    break
                }
                (_, Row(_)) => {
                    subs.push((b.clone(), Sequence::from_iter(&self.values[..=i])));
                    break
                }
            }
        }
        subs
    }
}

impl std::iter::FromIterator<ItemRef> for Sequence {
    fn from_iter<I: IntoIterator<Item=ItemRef>>(input: I) -> Self {
        Sequence {
            values: input.into_iter().collect(),
        }
    }
}

impl<'a> std::iter::FromIterator<&'a ItemRef> for Sequence {
    fn from_iter<I: IntoIterator<Item=&'a ItemRef>>(input: I) -> Self {
        Sequence {
            values: input.into_iter().cloned().collect(),
        }
    }
}

impl From<ItemRef> for Sequence {
    fn from(item: ItemRef) -> Self {
        Sequence {
            values: vec![item]
        }
    }
}

struct Substitutions {
    subs: HashMap<ItemRef, Sequence>,
}

impl Substitutions {
    fn new() -> Self {
        Substitutions {
            subs: HashMap::new(),
        }
    }
    
    fn find(&self, item: ItemRef) -> Sequence {
        self.subs.get(&item).cloned().unwrap_or(Sequence::single(item))
    }
    
    fn add_sequence(&mut self, a: ItemRef, b: Sequence) -> Vec<(ItemRef, Sequence)> {
        let mut items = vec![];
        
        if let Some(item) = self.subs.get(&a) {
            items.push(item.clone());
        }
        
        items.push(Sequence::single(a));
        items.push(b);
        
        items.sort_unstable_by(|x, y|{
            x.compare(y).into()
        });
        
        let b = items.pop().unwrap();
        
        let mut subs = vec![];
        for a in items.into_iter().map(Sequence::into_item) {
            if b.contains(&a) {
                panic!("Invalid Substitution")
            }
            
            self.subs.insert(a.clone(), b.clone());
            subs.push((a, b.clone()));
        }
        
        subs
    }
}

struct AbstractStack {
    inputs: Sequence,
    values: Sequence,
    subs: Substitutions,
}

impl AbstractStack {
    fn new() -> Self {
        let r = [StackItem::anonymous_row()];
        AbstractStack {
            inputs: Sequence::from_iter(&r),
            values: Sequence::from_iter(&r),
            subs: Substitutions::new(),
        }
    }
    
    fn pop<T: Into<Sequence>>(&mut self, x: T) -> Sequence {
        self.pop_sequence(x.into())
    }
    
    fn push<T: Into<Sequence>>(&mut self, x: T) {
        self.push_sequence(x.into())
    }
    
    fn pop_sequence(&mut self, mut targets: Sequence) -> Sequence {
        let mut result = Sequence::new();
        while let Some(target) = targets.pop() {
            result.extend(self.pop_item(target));
        }
        result
    }
    
    fn pop_item(&mut self, target: ItemRef) -> Sequence {
        if let StackItem::Row(_) = *target {
            let x = replace(&mut self.values, Sequence::new());
            self.substitute(&target, &x);
            return x
        }
        
        match self.values.pop() {
            None => panic!("Abstract Stack Underflow"),
            Some(top) => match *top {
                StackItem::Item(_) => {
                    self.substitute(&target, &Sequence::single(top.clone()));
                    return Sequence::single(top)
                }
                StackItem::Row(_) => {
                    self.add_input(target.clone());
                    self.push_item(top);
                    return Sequence::single(target);
                }
                StackItem::Quotation(_, ref ia, ref oa) => {
                    if let StackItem::Quotation(_, ref ib, ref ob) = *target {
                        let mut subs = vec![];
                        subs.extend(ia.borrow().match_effects(&ib.borrow()));
                        subs.extend(oa.borrow().match_effects(&ob.borrow()));
                        
                        for (a, b) in subs {
                            self.substitute(&a, &b);
                            target.substitute(&a, &b);
                        }
                        
                        return Sequence::single(target)
                    } else {
                        unimplemented!()
                    }
                }
            }
        }
    }
    
    fn push_item(&mut self, item: ItemRef) {
        self.values.extend(self.subs.find(item));
    }
    
    fn push_sequence(&mut self, items: Sequence) {
        if items.len() == 1 {
            self.push_item(items.into_item());
        } else {
            self.values.extend(items);
        }
    }
    
    fn add_input(&mut self, item: ItemRef) {
        self.inputs.insert(1, item);
    }
    
    fn substitute(&mut self, a: &ItemRef, b: &Sequence) {
        for (a, b) in self.subs.add_sequence(a.clone(), b.clone()) {
            self.inputs.substitute(&a, &b);
            self.values.substitute(&a, &b);
        }
    }
}

impl std::fmt::Debug for AbstractStack {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{:?} -- {:?}     ...with {:?}", self.inputs, self.values, self.subs)
    }
}

impl std::fmt::Debug for Sequence {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        let names: Vec<_> = self.values.iter().map(|x| format!("{:?}", x)).collect();
        write!(f, "{}", names.join(" "))
    }
}

impl std::fmt::Debug for Substitutions {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{:?}", self.subs)
    }
}

impl std::fmt::Debug for StackItem {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            StackItem::Row(name) => write!(f, "..{}", name),
            StackItem::Item(name) => write!(f, "{}", name),
            StackItem::Quotation(name, a, b) => write!(f, "{}({:?} -- {:?})", name, a.borrow(), b.borrow()),
        }
    }
}


/// Helper for hashing by Rc identity
pub struct RefHash<T>{
    inner: Rc<T>,
}

impl<T> RefHash<T>{
    pub fn new(inner: Rc<T>) -> Self{
        return RefHash{inner}
    }
}

impl<T> Hash for RefHash<T> {
  fn hash<H: Hasher>(&self, state: &mut H) {
      let ptr = Rc::into_raw(self.inner.clone());
      ptr.hash(state);
      let _ = unsafe{ Rc::from_raw(ptr) };
  }
}

impl<T> PartialEq for RefHash<T> {
    fn eq(&self, other: &Self) -> bool {
        return Rc::ptr_eq(&self.inner, &other.inner);
    }
}
impl<T> Eq for RefHash<T> {}

impl<T> Clone for RefHash<T> {
    fn clone(&self) -> Self {
        RefHash {
            inner: self.inner.clone()
        }
    }
}

impl<T> std::ops::Deref for RefHash<T> {
    type Target = T;
    fn deref(&self) -> &T {
        &*self.inner
    }
}

impl<T: std::fmt::Debug> std::fmt::Debug for RefHash<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{:?}", self.inner)
    }
}


fn main() {
    ////////////////////////////////////////////////////////////////////////////
    let mut astack = AbstractStack::new();
    println!("{:?}", astack);
    
    // SWAP (..a x y -- ..a y x)    
    let y = astack.pop(StackItem::item("y"));
    let x = astack.pop(StackItem::item("x"));
    let r = astack.pop(StackItem::row("a"));
    astack.push(r);
    astack.push(y);
    astack.push(x);
    println!("{:?}", astack);
    
    // DROP (..b z -- ..b)
    astack.pop(StackItem::item("z"));
    let b = astack.pop(StackItem::row("b"));
    astack.push(b);
    
    // DROP (z -- )
    astack.pop(StackItem::item("z"));
    
    // DROP (z -- )
    astack.pop(StackItem::item("z"));
    println!("{:?}", astack);
    
    ////////////////////////////////////////////////////////////////////////////
    println!("--------------------------------------------------------");
    let mut astack = AbstractStack::new();
    
    // SWAP (x y -- y x)    
    let y = astack.pop(StackItem::item("y"));
    let x = astack.pop(StackItem::item("x"));
    astack.push(y);
    astack.push(x);
    println!("{:?}", astack);
    
    // CALL (..a f(..a -- ..b) - ..b)    
    let a = StackItem::row("a");
    let b = StackItem::row("b");
    astack.pop(StackItem::quot("f", &[a.clone()], &[b.clone()]));
    astack.pop(a);
    astack.push(b);
    
    println!("{:?}", astack);
    
    ////////////////////////////////////////////////////////////////////////////
    println!("--------------------------------------------------------");
    let mut astack = AbstractStack::new();
    
    // [ + ] (-- g(..e x y -- ..e z))
    let e = StackItem::row("e");
    astack.push(StackItem::quot("g", &[e.clone(), StackItem::item("x"), StackItem::item("y")], &[e, StackItem::item("z")]));
    
    // CALL (..c f(..c -- ..d) - ..d)      
    let c = StackItem::row("c");    
    let d = StackItem::row("d");
    astack.pop(StackItem::quot("f", &[c.clone()], &[d.clone()]));
    astack.pop(c);
    astack.push(d);
    
    println!("{:?}", astack);
    
    ////////////////////////////////////////////////////////////////////////////
    println!("--------------------------------------------------------");
    let mut astack = AbstractStack::new();
    
    // [ + ] (-- g(..e y -- ..e z))
    let e = StackItem::row("e");
    astack.push(StackItem::quot("g", &[e.clone(), StackItem::item("y")], &[e, StackItem::item("z")]));
    
    // CALL (..c f(..c i j -- ..d k) - ..d)      
    let c = StackItem::row("c");  
    astack.pop(StackItem::quot("f", &[c.clone(), StackItem::item("i"), StackItem::item("j")], &[c.clone(), StackItem::item("k")]));
    let c = astack.pop(c);
    astack.push(c);
    
    println!("{:?}", astack);
}