tm.swift

// MARK: - Tape
enum Value <T:Equatable>: Equatable { case value(T), unset }
typealias Step               = ()   -> ()
typealias Read<T:Equatable>  = ()   -> Value<T>
typealias Write<T:Equatable> = (T?) -> ()
typealias Tape<T:Equatable>  = (stepBack:Step, stepForward:Step, read:Read<T>, write:Write<T>, print:() -> ())

struct TapeState<T:Equatable> {
    enum Change {
        case cursor(Cursor)
        case set(T?)
        enum Cursor { case up, down }
    }
    init(with initial:[T]) { self.init(initial.map { .value($0) }, 0) }
    
    let cursor: Int
    let values: [Value<T>]
    
    func alter(_ change:Change) -> Self {
        switch change {
        case     .cursor(.up  ): return .init(values,cursor + 1)
        case     .cursor(.down): return .init(values,cursor - 1)
        case let .set   (value): return set(value: value)
        }
    }
    private func set(value:T?) -> Self {
        if (0 ..< values.count).contains(cursor) {
            return .init(  values.prefix(cursor) + [ wrapped(value) ] + values.suffix(values.count - 1 - cursor), cursor )
        } else {
            while cursor < 0             { return .init([ .unset ] + values,                                                 cursor + 1) }
            while cursor >= values.count { return .init(values + (cursor == values.count ? [ wrapped(value) ] : [ .unset ]), cursor    ) }
        }
        return self
    }
    private init(_ values:[Value<T>],_ cursor: Int) {
        self.values = values
        self.cursor = cursor
    }
    private func wrapped(_ value:T?) -> Value<T> { value != nil ? .value(value!) : .unset }
}

func createTape<T:Equatable>(with initial:[T]) -> Tape<T> {
    var tapeState = TapeState(with: initial)
    func read() -> Value<T>   { (tapeState.cursor > -1 && tapeState.cursor < tapeState.values.count) ? tapeState.values[tapeState.cursor] : .unset }
    func write(value:T?)      { tapeState = tapeState.alter(.set(value)) }
    func stateRep() -> String { tapeState.values.reduce("") { switch $1 { case .unset: return $0 + " _ "; case .value(let v): return $0 + " \(v) " } }}
    func _print()             { print(" tape" + ("(\(tapeState.cursor))\t:\t") + "\(stateRep())") }
    return Tape<T>(
        stepBack   : { tapeState = tapeState.alter(.cursor(.down)) },
        stepForward: { tapeState = tapeState.alter(.cursor(.up  )) },
        read       : read,
        write      : write(value:),
        print      : _print
    )
}
// MARK: - Turing Machine
enum Move { case back, forward }
enum NextState { case stop, failed, next(String) }
enum Execution<T:Equatable> { case tm(TM<T>) }

func execute<T:Equatable>(machine: TM<T>) { machine.execute(.tm(machine)) }
typealias Rule<T:Equatable> = (inState:String, read:Value<T>, write:Value<T>, move:Move, next:NextState)
typealias TM<T:Equatable>   = (tape:Tape<T>, rules:[Rule<T>], currentState:String, execute:(Execution<T>) -> ())
func createTuringMachine<T>(tape:Tape<T>, rules:[Rule<T>]) -> TM<T> {
    TM(tape:tape, rules:rules, currentState:rules.first?.inState ?? "-1") {
        if case let .tm(machine) = $0 {
            let tapeentry = machine.tape.read()
            let rule = machine.rules.first { $0.inState == machine.currentState && $0.read == tapeentry } ?? Rule<T>(inState:"failed", read:.unset,write:.unset,.forward,.failed)
            switch rule.next {
            case .stop   : print("stopped");machine.tape.print(); return
            case .failed : print("failed" );machine.tape.print(); return
            case .next(_): ()
            }
            switch (tapeentry,rule.read,rule.write,rule.move) {
            case let (vi,vj,.value(w),move):
                switch (vi, vj) {
                case let(i,j):
                    if i == j {
                        machine.tape.write(w)
                        switch move {
                        case .back   : machine.tape.stepBack()
                        case .forward: machine.tape.stepForward()
                        }
                        if case .next(let nextstate) = rule.next { machine.execute(.tm(TM(machine.tape,machine.rules,nextstate,machine.execute))) }
                    }
                }
            default: return
            }
        }
    }
}
// MARK: - Examples
let startsWith1234 = [
    Rule(inState:"s1",read:.value(1),write:.value(1),.forward,.next("s2")),
    Rule(inState:"s2",read:.value(2),write:.value(2),.forward,.next("s3")),
    Rule(inState:"s3",read:.value(3),write:.value(3),.forward,.next("s4")),
    Rule(inState:"s4",read:.value(4),write:.unset,   .forward,.stop      ) ]
execute(machine: createTuringMachine(tape:createTape(with:[1,2,3,4]), rules:startsWith1234))
execute(machine: createTuringMachine(tape:createTape(with:[1,2,  4]), rules:startsWith1234))
execute(machine: createTuringMachine(tape:createTape(with:[1,2,3  ]), rules:startsWith1234))

func binaryDoubling<T:Equatable>(a:T, b:T) -> [Rule<T>] { [
    Rule(inState:"s1",read:.value(a),write:.value(a),.forward,.next("s1")),
    Rule(inState:"s1",read:.value(b),write:.value(b),.forward,.next("s1")),
    Rule(inState:"s1",read:.unset,   write:.value(a),.forward,.next("s2")),
    Rule(inState:"s2",read:.unset,   write:.unset,   .forward,.stop      ) ]
}
execute(machine: createTuringMachine(tape: createTape(with:[ 1 , 1 , 1 ]), rules:binaryDoubling(a: 0,  b: 1 )))
execute(machine: createTuringMachine(tape: createTape(with:["1","0","1"]), rules:binaryDoubling(a:"0", b:"1")))

func inverting<T:Equatable>(a:T, b:T) -> [Rule<T>] { [
    Rule(inState:"s1",read:.value(a),write:.value(b),.forward,.next("s1")),
    Rule(inState:"s1",read:.value(b),write:.value(a),.forward,.next("s1")),
    Rule(inState:"s1",read:.unset,   write:.unset,   .forward,.stop      ) ]
}
execute(machine: createTuringMachine(tape: createTape(with:[ 1, 0, 1, 1, 0 ]), rules:inverting(a: 0,  b: 1 )))
execute(machine: createTuringMachine(tape: createTape(with:["a","b","b","a"]), rules:inverting(a:"a", b:"b")))

//: [Next](@next)