Created
January 5, 2018 06:02
-
-
Save bkase/ffe8c0a38efce4e36cecb28a8415ded6 to your computer and use it in GitHub Desktop.
Hashconsing and Sklansky (ported from Swift Sandbox)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// An exploration of http://okmij.org/ftp/tagless-final/sharing/sharing.pdf | |
// Specifically focusing on Hashconsing and Sklansky | |
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 | |
}) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment