An exploration of Sharing (Oleg) focusing on Hashconsing and Sklansky

OlegSharing.swift

// An exploration of http://okmij.org/ftp/tagless-final/sharing/sharing.pdf
// Specifically focusing on Hashconsing and Sklansky

// See http://swift.sandbox.bluemix.net/#/repl/5940bd55698d8d064dec2b22 for this snippet in a playground

typealias NodeId = Int
enum Node: Equatable, Hashable {
    case nconst(Int)
    case nvar(String)
    case nadd(NodeId, NodeId)
    
    var hashValue: Int {
        switch self {
        case let .nconst(x): return x.hashValue
        case let .nvar(x): return x.hashValue
        case let .nadd(a, b): return a.hashValue ^ b.hashValue
        }
    }
    
    static func == (lhs: Node, rhs: Node) -> Bool {
        switch (lhs, rhs) {
        case let (.nconst(x), .nconst(y)):
            return x == y
        case let (.nvar(x), .nvar(y)):
            return x == y
        case let (.nadd(a, b), .nadd(a_, b_)):
            return a == a_ && b == b_
        case (.nconst(_), _): return false
        case (.nvar(_), _): return false
        case (.nadd(_, _), _): return false
        }
    }
}

struct Bimap<T: Equatable & Hashable> {
    private var forwards: [T: Int] = [:]
    private var backwards: [Int: T] = [:]
    private var count = 0
    
    func lookup(key: T) -> Int? {
        return forwards[key]
    }
    
    func lookup(val: Int) -> T? {
        return backwards[val]
    }
    
    mutating func insert(_ t: T) -> Int {
        forwards[t] = count
        backwards[count] = t
        count += 1
        return count-1
    }
}

struct Dag {
    var run: Bimap<Node>
}

// Instead of using a "State Monad" I attempted to use mutable struct state.
// Since structs are value types, I expected that this may actually be a nice
// representation in Swift. I was wrong.
struct ExprN {
    var nodeId: NodeId
    var state = Dag(run: Bimap<Node>())
    
    init(nodeId: NodeId) {
        self.nodeId = nodeId
    }
    
	@discardableResult
    mutating func hashcons(_ n: Node) -> NodeId {
        nodeId = state.run.lookup(key: n) ?? state.run.insert(n)
        return nodeId
    }
	
    @discardableResult
    mutating func constant(_ x: Int) -> NodeId {
        return hashcons(.nconst(x))
    }
	
	@discardableResult
    mutating func variable(_ x: String) -> NodeId {
        return hashcons(.nvar(x))
    }
	
	@discardableResult
    mutating func add(_ e1: ExprN, _ e2: ExprN) -> NodeId {
        return hashcons(.nadd(e1.nodeId, e2.nodeId))
    }
}

extension ExprN {
	// This already seems a little strange since we're running some of the
	// operations just for their side-effects
	@discardableResult
    mutating func multiplied(by n: Int) -> NodeId {
        switch (n, self) {
        case (0, _):
            return constant(0)
        case let (1, x): return x.nodeId
        case let (_, x) where n % 2 == 0:
            add(x, x)
            return multiplied(by: n / 2)
        case let (_, x):
            var y = x
            y.multiplied(by: n-1)
            return add(x, y)
        }
    }
}

print("\n*** Multiply ***")
var expr1 = ExprN(nodeId: 0)
expr1.constant(5)
expr1.multiplied(by: 4)
// Even though it's a little strange, this implementation seems to work
print(expr1)

extension Array {
	// This function fascinates me
	// It's a scan that seems to depend on f being associative
    func sklansky(_ f: (Element, Element) -> Element) -> [Element] {
        if self.count == 0 {
            return self
        }
        if self.count == 1 {
            return self
        }
        
        let (left, right) = (Array(self[0..<self.count/2]), Array(self[self.count/2..<self.count]))
        let left_ = left.sklansky(f)
        let right_ = right.sklansky(f)
        return left_ + right_.map{ f(left_.last!, $0) }
    }
}

print("\n\n*** Sklansky ***")
// Sklansky seems to work
print(["a","b","c","d"].sklansky{ "(" + $0 + "+" + $1 + ")"})

// Here is where this "stateful" Expr implementation falls apart
var expr2 = ExprN(nodeId: 0)
print([1,2,3,4]
	  .map{ (x: Int) in
		   var e = expr2
		   expr2.variable("v" + "\(x)")
		   return e
	  }
	  .sklansky{ (x: ExprN, y: ExprN) -> ExprN in
           var e = expr2
           e.add(x, y)
           return e
	  })

Also, I realize the paper makes a point that the tagless final representation admits several implementations, and I totally ignored that part in this implementation (I didn't realize Swift even supported polymorphic return types until I read @chriseidhof 's implementation), but I wanted to play with Hashconsing and Sklansky in particular