Skip to content

Instantly share code, notes, and snippets.

@bkase
Created June 14, 2017 04:38
Show Gist options
  • Save bkase/1cd8ed42b8fd41a4033d367b15b88f3c to your computer and use it in GitHub Desktop.
Save bkase/1cd8ed42b8fd41a4033d367b15b88f3c to your computer and use it in GitHub Desktop.
An exploration of Sharing (Oleg) focusing on Hashconsing and Sklansky
// 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
})
@bkase
Copy link
Author

bkase commented Jun 14, 2017

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment