Lenses are Static Selectors

So I don’t really know what KVC is, or much about performSelector functions. This blogpost, from Brent Simmons, let me know a little bit about why I would want to use them.

It centred around removing code repetition of this type:

if localObject.foo != serverObject.foo {
  localObject.foo = serverObject.foo
}

if localObject.bar != serverObject.bar {
  localObject.bar = serverObject.bar // There was an (intentional)
}                                    // bug here in the original post

To clean up the code, Brent used selector methods. At first, I was a little uncomfortable with the solution. As far as I could tell, the basis of a lot of this machinery used functions with types like this:

func get(fromSelector: String) -> AnyObject?
func set(forSelector: String) -> ()

Which seems to be extremely dynamic. Stringly-typed and all that. Except that there are two different things going on here. One is the dynamic stuff; the ability to get rid of types when you need to. The other, though, has nothing to do with types. The other idea is being able to pass around something which can access the property (or method) of an object.

Let’s look at the code that was being repeated:

if localObject.foo != serverObject.foo {
  localObject.foo = serverObject.foo
}

if localObject.bar != serverObject.bar {
  localObject.bar = serverObject.bar
}

The logical, obvious thing to do here is try refactor out the common elements. In fact, the only things that differ between the two actions above are the foo and bar. It would be great to be able to write a function like this:

func checkThenUpdate(selector) {
  if localObject.selector != serverObject.selector {
    localObject.selector = serverObject.selector
  }
}

And then maybe a single line like this:

[foo, bar, baz].forEach(checkThenUpdate)

That’s pretty obviously better. It’s just good programming: when faced with repetition, find the repeated part, and abstract it out. Is it more dynamic than the repetition, though? I don’t think so. All you have to figure out is an appropriate type for the selector, and you can keep all of your static checking. To me, it seems a lot like a lens:

struct Lens<Whole, Part> {
  let get: Whole -> Part
  let set: (Whole, Part) -> Whole
}

(This is a lens similar to the ones used in the data-lens library, in contrast to van Laarhoven lenses, or LensFamilies. LensFamilies are used in the lens package, and they allow you to change the type of the Part. They’re also just normal functions, rather than a separate type, so you can manipulate them in a pretty standard way. Swift’s type system isn’t able to model those lenses, though, unfortunately.)

It has two things: a getter and a setter. The getter is pretty obvious: it takes the object, and returns the property. The setter is a little more confusing. It’s taking an object, and the new property you want to stick in to the object, and returns the object with that property updated.

For instance, if we were to make a Person:

struct LocalPerson {
  var age: Int
  var name: String
}

We could then have a lens for the name field like this:

let localName: Lens<LocalPerson,String> = Lens(
  get: { p in p.name },
  set: { (oldPerson,newName) in
    var newPerson = oldPerson
    newPerson.name = newName
    return newPerson
  }
)

And you’d use it like this:

let caoimhe = LocalPerson(age: 46, name: "caoimhe")
localName.get(caoimhe) // 46
localName.set(caoimhe, "breifne") // LocalPerson(age: 46, name: "breifne")

Straight away, we’re able to do (something) like the checkThenUpdate function:

func checkThenUpdate
  <A: Equatable>
  (localLens: Lens<LocalPerson,A>, serverLens: Lens<ServerPerson,A>) {
  let serverProp = serverLens.get(serverObject)
  if localLens.get(localObject) != serverProp {
    localObject = localLens.set(localObject,serverProp)
  }
}

And it could be called pretty tersely:

checkThenUpdate(localName, serverLens: serverName)

The biggest problem with this approach, obviously, is the boilerplate. In Haskell, that’s solved with Template Haskell, so the lens code is generated for you. (I’d love to see something like that in Swift)

There’s a protocol-oriented spin on lenses, also. One of the variants on lenses in Haskell are called "classy-lenses". That’s where, instead of just generating a lens with the same name as the field it looks into, you generate a typeclass (protocol) for anything with that lens. In Swift, it might work something like this:

struct Place {
  var name: String
}

// Instead of just having a lens for the name field, have a whole protocol
// for things with a name field:

protocol HasName {
  associatedtype Name
  static var name: Lens<Self,Name> { get }
  var name: Name { get set }
}

// Because the mutable property is included in the protocol, you can rely on
// it in extensions:

extension HasName {
  static var name: Lens<Self,Name> {
    return Lens(
      get: {$0.name},
      set: { (w,p) in 
        var n = w
        n.name = p
        return n
      }
    )
  }
  var name: Name {
    get { return Self.name.get(self) }
    set { self = Self.name.set(self,newValue) }
  }
}

// This way, you can provide either the lens or the property, and you get the
// other for free.

extension Place: HasName {}

// Then, you can rely on that protocol, and all of the types:

func checkEqualOnNames
  <A,B where A: HasName, B: HasName, A.Name: Equatable, A.Name == B.Name>
  (x: A, _ y: B) -> Bool {
    return x.name == y.name
}

This protocol lets you do a kind of static respondsToSelector, with all of the types intact.

Other people have spoken about the other things you can do with lenses in Swift (Brandon Williams – Lenses in Swift), like composing them together, chaining operations, etc. (One other thing they can emulate is method cascading) Unfortunately, in current Swift, the boilerplate makes all of this a little unpleasant. Still, they’re an interesting idea, and they show how a good type system needn’t always get in the way.

Monty Hall

The Monty Hall problem is a great example of how counter-intuitive probability can sometimes be. It goes something like this: say you’re on a gameshow, with the chance to win a car. You’re shown three doors, and the car is behind one, goats behind the other two. You pick a door, say the leftmost, but then the host of the gameshow stops you before it’s opened. He opens one of the two doors you didn’t pick, revealing a goat. He then asks you if you’d like to change your decision. So? Do you?

Read More

In which I Misunderstand Dependent Types

All of this available as a shiny, fancy playground here.

So there was a blog post the other day about dependent types:

Why Dependent Types Matter

Most blog posts that deal with the more mathematical/category theory side of programming go over my head when I read them, only to become suddenly clear a few weeks down the line. I have not reached this such sudden clarity with this post, but I’m starting to see a glimmer.

Read More

Tile_al-Qazwini_Louvre_MAO1194

Using Protocols to Build a (very) Generic Deque

Check out this blog post as a cool fancy markdown-tastic playground here. Look! It’s the future!

This post is an update on a previous implementation of a Deque. A full implementation of this Deque is available here.

A Deque is a data structure comprised of two stacks, facing opposite directions. In this way, operations at either end of the Deque have the same complexity as operations on one end of the underlying stack. This implementation uses two arrays, with the front reversed: appending, prepending, and removal of the first and last elements are all (amortized) O(1).

The standard library has three Array structs: Array, ArraySlice, and ContiguousArray. They all have the same interface, with different underlying implementations. An Array is a standard vector-like structure, which allows O(1) amortized appending, fast iteration, etc. A ContiguousArray has stricter rules about contiguity, but it’s not bridged to Objective-C.

let cArray: ContiguousArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

An ArraySlice is a reference into an Array or ContiguousArray, for more efficient slicing. All the information an ArraySlice contains is the beginning and end points of the slice (as well as any changes made to the slice separate from the array)

let slice = array[0..<6]

To replicate these semantics in a Deque requires three separate structs: one with an Array as the stack, another with an ArraySlice as the stack, and a third with a ContiguousArray. The standard library seems to duplicate the structs, along with their methods and properties.

It would be much nicer to just define a protocol that represented the difference between the deque types: then you could just write the methods and properties once, on top of it. Something like this:

protocol DequeType {
  typealias Container : RangeReplaceableCollectionType, MutableSliceable
  var front: Container { get set }
  var back : Container { get set }
  init()
}

There’s one problem with this: both stacks need to be made public. It would be much nicer to hide the stacks (especially since an invariant needs to be checked and maintained on every mutation). If anyone has an idea of how to transformations that, tweet me.

The first method to implement is a subscript. Indexing is difficult, because the front stack will be reversed, so the index used to get in to the Deque will need to be translated into an equivalent index in the array.

Any (valid) index will point into either the front or back queue, and the transformation applied to it in each case is different. If it’s in the front, the end result will look like front[front.endIndex - 1 - i], whereas if it’s in the back, it should be back[i - front.endIndex]. There’s nothing specified about the Containers except that they’re RangeReplaceableCollectionType and MutableSliceable, so the index types will have to be as generic as possible. (you could specify where Index == Int, but that’s more specific than needed, and not very extensible.)

Both of those transformations are subtractions, an operation that’s possible on RandomAccessIndexTypes with the advancedBy method. advancedBy takes the associated Distance type of the RandomAccessIndexType. That’s enough information to figure out that the Deque’s index type must be the same as the Distance of the Index of the Container.

extension DequeType {
  typealias Index = Container.Index.Distance
}

The method that will translate an index into the relevant index in the stacks will return an enum:

public enum IndexLocation<I> {
  case Front(I), Back(I)
}

Then, the translate method itself:

extension DequeType where
  Container.Index : RandomAccessIndexType,
  Container.Index.Distance : ForwardIndexType {
  
  private func translate(i: Container.Index.Distance)
    -> IndexLocation<Container.Index> {
    return i < front.count ?
      .Front(front.endIndex.predecessor().advancedBy(-i)) :
      .Back(back.startIndex.advancedBy(i - front.count))
  }
}

This performs two steps:
1. Check which stack it’s in.
2. Subtract in the appropriate order

let d: Deque = [1, 2, 3, 4, 5, 6] // [1, 2, 3 | 4, 5, 6]

d.translate(0) // Front: 2
d.translate(4) // Back: 1

This means that the logic for converting distance to index is separated from the logic for actual indexing. Great! Here’s the indexing:

extension DequeType where
  Container.Index : RandomAccessIndexType,
  Container.Index.Distance : ForwardIndexType {
  var startIndex: Container.Index.Distance { return 0 }
  var endIndex  : Container.Index.Distance { return front.count + back.count }
  subscript(i: Container.Index.Distance) -> Container.Generator.Element {
    get {
      switch translate(i) {
      case let .Front(i): return front[i]
      case let .Back(i): return back[i]
      }
    } set {
      switch translate(i) {
      case let .Front(i): front[i] = newValue
      case let .Back(i): back[i] = newValue
      }
    }
  }
}

This makes things much easier to test and debug.

Here’s where the power of protocols becomes obvious. If you go back to the original definition of DequeType, you can add Indexable. It may seem like now only indexable things can conform, but what happens in practice is that when Indexable looks for its requirements, it can use the implementations in DequeType. That means that we’ve just made anything that can conform to DequeType indexable. That’s awesome.

Next job is ranged indices. This is a good bit more complicated than the individual indices, so it definitely will benefit from being separated into a translate method:

extension DequeType where
  Container.Index : RandomAccessIndexType,
  Container.Index.Distance : BidirectionalIndexType {
  
  private func translate
    (i: Range<Container.Index.Distance>)
    -> IndexRangeLocation<Container.Index> {
      if i.endIndex <= front.count {
        let s = front.endIndex.advancedBy(-i.endIndex)
        if s == front.startIndex && i.isEmpty { return .Between }
        let e = front.endIndex.advancedBy(-i.startIndex)
        return .Front(s..<e)
      }
      if i.startIndex >= front.count {
        let s = back.startIndex.advancedBy(i.startIndex - front.count)
        let e = back.startIndex.advancedBy(i.endIndex - front.count)
        return .Back(s..<e)
      }
      let f = front.startIndex..<front.endIndex.advancedBy(-i.startIndex)
      let b = back.startIndex..<back.startIndex.advancedBy(i.endIndex - front.count)
      return .Over(f, b)
  }
}

let otherDeque: Deque = [0, 1, 2, 3, 4, 5] // [0, 1, 2 | 3, 4, 5]

otherDeque.translate(0...2) // Front: 0..<3
otherDeque.translate(4...5) // Back: 1..<3
otherDeque.translate(2...5) // Over: 0..<1, 0..<3
otherDeque.translate(3..<3) // Between

The invariant that must be maintained in the deque is this: if either stack has more than one element, the other cannot be empty. If the invariant is violated, the longer stack is reversed, and put in place of the shorter.

public enum Balance {
  case FrontEmpty, BackEmpty, Balanced
}

extension DequeType {
  
  public var balance: Balance {
    let (f, b) = (front.count, back.count)
    if f == 0 {
      if b > 1 {
        return .FrontEmpty
      }
    } else if b == 0 {
      if f > 1 {
        return .BackEmpty
      }
    }
    return .Balanced
  }
  
  public var isBalanced: Bool {
    return balance == .Balanced
  }
}

A deque is a good data structure for certain uses, especially those that require popping and appending from either end. popFirst() and popLast() aren’t included in the standard RangeReplaceableCollectionType, though, so we’ll have to add our own.

extension RangeReplaceableCollectionType where Index : BidirectionalIndexType {
  private mutating func popLast() -> Generator.Element? {
    return isEmpty ? nil : removeLast()
  }
}

var mutableDeque: Deque = [0, 1, 2, 3, 4, 5]
mutableDeque.popLast() // 5
mutableDeque           // [0, 1, 2 | 3, 4]

extension DequeType where Container.Index : BidirectionalIndexType {
  public mutating func popLast() -> Container.Generator.Element? {
    return back.popLast()
  }
}

The method needs to include check(), which we can do with defer:

mutating func popLast() -> Container.Generator.Element? {
  defer { check() }
  return back.popLast()
}

mutableDeque.popLast() // 4
mutableDeque           // [0, 1, 2 | 3]
mutableDeque.popLast() // 3
mutableDeque           // [0 | 1, 2]

You also can’t just pop from the back queue in popLast(), because it may be the case that the front stack has one element left

//mutating func popLast() -> Container.Generator.Element? {
//  defer { check() }
//  return back.popLast() ?? front.popLast()
//}

mutableDeque.popLast() // 2
mutableDeque.popLast() // 1
mutableDeque           // [0|]
mutableDeque.popLast() // 0
mutableDeque           // [|]
mutableDeque.popLast() // nil

The rest of the Deque was easy, with little to no repetition. Using protocols in this way was really surprisingly powerful: now, you can define a DequeType, with full access to all of the collection methods, all the way up to RangeReplaceableCollectionType, in five lines:

public struct Deque<Element> : DequeType {
  public var front, back: [Element]
  public typealias SubSequence = DequeSlice<Element>
  public init() { (front, back) = ([], []) }
}

public struct DequeSlice<Element> : DequeType {
  public var front, back: ArraySlice<Element>
  public typealias SubSequence = DequeSlice
  public init() { (front, back) = ([], []) }
}

There’s no performance hit, there’s no safety problems. I only have one version of code to test, one version to change, one version to read. It’s completely extensible: you could use any kind of stack for the front and back. Even another Deque, if you were so inclined:

struct DequeDeque<Element> : DequeType {
  var front, back: Deque<Element>
  typealias SubSequence = DequeDequeSlice<Element>
  init() { front = Deque(); back = Deque() }
}

struct DequeDequeSlice<Element> : DequeType {
  var front, back: DequeSlice<Element>
  typealias SubSequence = DequeDequeSlice
  init() { front = DequeSlice(); back = DequeSlice() }
}

let dd: DequeDeque = [1, 2, 3, 4, 5, 6, 7, 8]
dd.front // [4 | 3, 2, 1]
dd.back  // [5 | 6, 7, 8]

Woo protocols!