Lazy Stack Based Programming Implementation of a Calculator

Lazy Stack Programming.swift

// Inspired by this article: http://blogs.msdn.com/b/oldnewthing/archive/2008/01/10/7047497.aspx
// which explains the weird behavior of the percent key on calculators

// We will demonstrate using the stack like a calculator
// to calculate (150 + 1000) - 10% = (150 + 1000) * (1 - 10/100) = 1035
var stack = Stack()   // []
stack.push(150)       // [150]
stack.push(1000)      // [150, 1000]
stack.push(add)       // [150, 1000, add]
stack.push(10)        // [150, 1000, add, 10]
stack.push(sub)       // [150, 1000, add, 10, sub]
stack.push(percent)   // [150, 1000, add, 10, sub, percent]

println(stack.peek()) /* [150, 1000, add, 1, 100, 10, div, sub, mul]
                       * [150, 1000, add, 1, 0.1, sub, mul]
                       * [150, 1000, add, 0.9, mul]
                       * [1150, 0.9, mul]
                       * [1035]
                       */

// Note that operators compute dependencies of their calculation first!!
// This enables this lazy sort of behavior that allows us to define subtraction
// in terms of negative addition and still be able to match the sub operation via
// our percent operator.

// Boring Implementation above
// Interesting Operation definitions at the bottom

typealias RawType = Float

enum Value : Printable, Equatable {
    case Raw(RawType)
    case Operator((inout Stack) -> (), String, Bool)
    
    var RawTypeValue: RawType {
        get {
            switch self {
            case .Raw(let x): return x
            default: fatalError("Cannot get the RawTypeValue of an operator.")
            }
        }
    }
    
    var description: String {
        get {
            switch self {
            case .Raw(let x): return x.description
            case .Operator(_, let desc, _): return desc
            }
        }
    }

}

func DerivedOperator(f:(inout Stack) -> (), desc:String) -> Value {
    return .Operator(f,desc,true)
}

func RawOperator(f:(inout Stack) -> (), desc:String) -> Value {
    return .Operator(f,desc,false)
}

func ==(lhs: Value, rhs: Value) -> Bool {
    return lhs.description == rhs.description // Janky!!
}

class StackNode {
    let value: Value
    var below: StackNode? = nil
    
    init(_ value: Value){
        self.value = value
    }
}

struct Stack : Printable {
    var top: StackNode? {
        didSet {
            above?.below = top
        }
    }
    var above: StackNode?
    
    var substack: Stack {
        get {
            var belowStack = Stack()
            belowStack.top = top?.below
            belowStack.above = self.top
            return belowStack
        }
    }
    
    mutating func pop() -> RawType {
        while true {
            switch removeLast() {
            case .Raw(let x): return x
            case .Operator(let op, _, _): evaluateOperation(op)
            }
        }
    }
    
    mutating func peek() -> RawType? {
        evaluate()
        if let value = top?.value {
            switch value {
            case .Raw(let x): return x
            default: return nil
            }
        }
        else {
            return nil
        }
    }
    
    mutating func push(x: RawType) {
        push(Value.Raw(x))
    }
    
    mutating func push(x: Value) {
        let node = StackNode(x)
        node.below = top
        
        top = node
    }
    
    mutating func removeLast() -> Value {
        if let oldTop = top {
            let value = oldTop.value
            top = oldTop.below
            return value
        }
        else {
            fatalError("Cannot pop the empty stack.")
        }
    }

    mutating func apply(x: Value) {
        push(x)
        switch x {
            case .Operator(_,_,let derived): if derived { evaluateStep() }
            default: break
        }
    }
    
    mutating func evaluateOperation(op: (inout Stack) -> ()) {
        op(&self)
    }
    
    mutating func evaluate() {
        while top?.below != nil {
            evaluateStep()
        }
    }
    
    mutating func evaluateStep() {
        switch removeLast() {
        case .Raw: fatalError("Cannot evaluate a raw value")
        case .Operator(let op, _, _): evaluateOperation(op)
        }
    }
    
    var description: String {
        get {
            var value = [Value]()
            
            var node = top
            while let n = node {
                value.insert(n.value, atIndex: 0)
                node = node?.below
            }
            
            return value.description
        }
    }
}

let id = RawOperator({ (inout x: Stack) in  }, "id")
let add = RawOperator({ (inout x: Stack) in x.push(x.pop() + x.pop()) }, "add")
let mul = RawOperator({ (inout x: Stack) in x.push(x.pop() * x.pop()) }, "mul")
let neg = RawOperator({ (inout x: Stack) in x.push(-x.pop()) }, "neg")
let sub = DerivedOperator({ (inout x: Stack) in
    let top = x.removeLast()
    x.push(neg)
    x.push(top)
    x.push(add) }, "sub")
let div = RawOperator({ (inout x: Stack) in x.push(x.pop() / x.pop()) }, "div")
let mod = RawOperator({ (inout x: Stack) in x.push(x.pop() % x.pop()) }, "mod")

// Definition of percent only makes sense if you use push, not apply
let percent = DerivedOperator({ (inout x: Stack) in
    let op = x.removeLast()
    let val = x.pop()

    x.push(1)
    x.push(100)
    x.push(val)
    x.push(div)

    assert(op == add || op == sub, "Invalid stack for percentage calculation")
    x.push(op)
    
    x.push(mul)
    
    },"percent")