acb's technical journal

Posts matching tags 'monads'

2016/1/18

Futures/Promises in Swift, draft 1.1

With the recent open-sourcing of the Swift language and its availability (albeit piecemeal, and not quite as we know it) on Linux, I have been spending some time playing with Swift on Linux. In my opinion, it holds promise for implementing the sorts of server-side code that often runs on Linux instances; one example would be web applications. With its LLVM-based optimising compiler, strong type system and the ability to minimise the amount of mutable state (more so than, say, Python or JavaScript), it should lend itself to performant server-side code quite well.

In any case, here is the first result of my experiments in Swift on Linux: a proof of concept of Futures/Promises. It's modelled somewhat on Scala's Futures, in that Futures are monadic containers which may be transformed with map, chained with flatMap, and, should you need to go synchronous at some point, awaited.

(For those not familiar with Futures/Promises, they're a different way of organising callbacks. With callbacks, as we know them from, say, JavaScript, Objective C or Swift, if you have a possibly time-consuming process to run, you pass it a function for it to call; it returns nothing immediately, but if all goes well, your callback function gets called with the value it was waiting for. Of course, the downside of this is the building up of a “Pyramid Of Doom”, a monstrous ziggurat of curly braces, like so:

doSomething { (a) -> () in 
   doSomethingElse(a) { (b) -> () in 
     andSomethingElse(b) { (c) -> () in 
        // now handle the value here
   }
}
With Futures/Promises, you don't pass callbacks, but instead receive an opaque container type that is, at some future time, redeemable for the value of whatever computation it represents. While you don't have that value, you can do other things with it, like chain other operations on it, to be completed asynchronously. And so, our pyramid is transformed into something like;
doSomething()
  .flatMap { doSomethingElse($0) }
  .flatMap { andSomethingElse($0) }
  .onCompletion {
    // now handle the value here
  }
Which, for one, looks a bit tidier; it also allows complex chains of interdependent operations to be reasoned about more easily.)

This code is currently only a rough sketch (which is why it is a gist, rather than a repository); for one, Swift on Linux's concurrency handling still leaves a bit to be desired (Apple's libdispatch is still not available, and so this uses NSLinux, which fakes Grand Central Dispatch in a somewhat basic way, spawning a new thread for each block, and having no option of running things on the main thread; needless to say, don't use this in your financial trading app just yet.) Secondly, there is not yet a concept of a failed Promise; they may be either incomplete or successfully completed. (Whether to use a Haskell-style Either/Result value or to somehow eschew that in favour of Swift's throws mechanism is a decision to be considered when implementing the possibility of failed Promises. Also, some way of sequencing/traversing multiple Futures would be useful for nontrivial applications. Finally, there is the small matter that this code defines only a Promise type and has it do double-duty as a Future as well; which makes for simpler code, though doesn't separate the twin concerns quite as elegantly. Update: I have now updated the code to split Futures (the ones you fire off with a block to run in the background) from Promises (the ones you create and fill in yourself, giving a Future to whatever needs the result).

In any case, the typical usage would look something like the following:

// Map over a Future, then do something with its result asynchronously
var f1 = Future<Int>( future: { calculateValue(...) })
var f2 = f1.map { $0 * 2 }
f2.onComplete { doSomethingWith($0) }

// two futures chained with flatMap
var f3 = Future<String>( future: { getUserName() })
    .flatMap { Future<Int>( future: { getShoeSizeOfUser($0) } }
if let value = f3.await(3.0) {
    print("The user's shoe size is \(value)")
}

And if you want to use Promises and do the computation yourself:

func asynchronouslyComputeAFuture() -> Future<Something> {
    // create an empty Promise...
    let p = Promise<Something>()

    // start a background process which will fill the Promise in...
    dispatch_async( myQueue, {
        let result: Something = computeTheResult() // this may take a while...
        p.complete(result)
    })

    // return the Promise's Future
    return p.future()
}

This is not the only implementation of Futures/Promises for Swift, nor even one of the more complete ones. There are two others which look more complete (BrightFutures and FutureKit), though both are only available for iOS and OSX at the moment.

concurrency functional programming futures linux monads promises swift 1

2015/5/12

Towards a more functional Swift

Swift came into the world as an interesting chimera; fully formed, with a list of interesting and innovative language features not seen before in the Objective C world, borrowed from other languages. Refreshingly, a few of these borrowings were from the world of functional programming. This is not entirely new to Objective C; since the arrival of the block syntax, some basic functional programming has been part of Objective C, at least with add-ons like BlocksKit; Swift, however, took it half a step further; borrowing from the likes of Haskell and Scala, it introduced concepts such as Optional types and pattern-matching. And then, as if not to scare the horses imperative-OO programmers, it stopped short, leaving the minority of seasoned monad-wranglers a little frustrated.

In a sense, one could see the rationale behind this; the iOS and OSX developer ecosystem is an overwhelmingly Objective C-based one, i.e., one grounded in Smalltalk-style object-oriented programming underpinned by the veritable C language (a language developed in the 1970s as a more portable, and higher-level, alternative to assembly language). Functional concepts have made it in slowly, in the form of blocks and closures; filtering into the Cocoa developer mind-set, at first as a variant of that old warhorse, the C callback function, with moderately functional semantics gradually seeping in from JavaScript (i.e., variable-capturing closures) and Python (map, filter and reduce). Then came along Swift, introduced at WWDC 2014, with its own learning curve, and alongside the usual raft of new iOS and OSX technologies. This was a lot to digest in one go, and throwing in category theory would have only confused things.

Gradually, though, awareness of functional programming techniques has spread throughout the Swift community; at developer meetups and in blogs, the denials of the necessity of such new-fangled ideas, and defences of perfectly good object-oriented techniques have given way to exploration of functional ways of doing things. The language has moved forward as well; when 1.2 came out a few months ago, for example, it brought with it the flatMap function, a key building block of various kinds of chainable operations. However, there is still some way to go. Which is why I have written this post as a plausible, and somewhat subjective, roadmap for some of the ways in which Swift could (and, in my opinion, should) develop.

The ideas here are influenced by languages I have worked with; in particular, there is a fair amount of Scala influence here (as Scala's treatment of functional concepts maps reasonably cleanly onto Swift's way of doing things in many cases) and, to a lesser extent, Python.

if let ... as a comprehension

Optionals (i.e., typed containers containing either nothing or one value of a type) are a key part of the Swift way of doing things. Being containers, they may, of course, be mapped over, and Swift provides ways of chaining optionals, following a sequence of operations, each of which may or may not return a non-empty value, and breaking the sequence at the first empty operation. One of these is the if let sequence; i.e.,

func maybeDoSomething(maybeA: Int?, maybeB: String?) -> String? {
  if let a = maybeA, 
    b = maybeB {
      return doSomething(a,b) // returns a String
  }
}

Given that the two Optionals, maybeA and maybeB, are containers which may be mapped (and flatMapped) over, this looks like it ought to be equivalent to the following:

func maybeDoSomething(maybeA: Int?, maybeB: String?) -> String? {
  return maybeA.flatMap { (a:Int) -> String? in 
    return maybeB.map { (b:String)->String in 
      doSomething(a, b) 
    }
  }
}

Seeing it written out this way, though, raises the tantalising possibility of applying it to other mon containers one can map over, such as Arrays; were the two forms equivalent, one could do something like this:

let arr1: [Int] = [1,2,3]
let arr2: [Int] = [5,6]

if let a = arr1, b = arr2 {
  println("\(a*b)")
}
/* prints 5, 6, 10, 12, 15, 18 */

Though one cannot; this is not valid Swift syntax. (And even if it were, may be argued that if let value = array would be rather odd syntax.)

Of course, there is a similar syntax for arrays and sequences with generators; the for _ in _ syntax, familiar from Objective C; which would look slightly less weird if extended to Optionals; we can already do things like:

func doSomeThings(arr: [Int], opt: Int?) {
  for a in arr {
    if let b = opt {
      doSomething(a, b)
    }
  }
}

By extending Generator semantics to Optionals and expanding the for...in statement, one could unify this into:

func doSomeThings(arr: [Int], opt: Int?) {
  for a in arr, b in opt {
    doSomething(a, b)
  }
}

Given that, in this hypothetical parallel-universe Swift, the enhanced, unified version of for..in has usurped a lot of the functionality of if let, it would make sense to go the whole hog and add the where clause to its syntax, allowing arrays to be filtered upon iteration, like so:

func doSomeThings(arr: [Int], opt: Int?) {
  for a in arr where a%2==0, b in opt {
    doSomething(a, b)
  }
}

(Of course, there is no reason why this syntax should work only on Optionals and Arrays; technically, it would apply to anything that's a monad, which, given a well-crafted library, would allow it to be used on, for example, values representing deferred computations (i.e., futures/promises).)

The missing piece

Eagle-eyed readers will have noticed a particular ugliness in the examples above: the inner block in the loop is hideously imperative; in each example, it either calls a hypothetical function (presumably with a side-effect) or printlns the output to the console. This is because Swift's if let and for...in are imperative statements, rather than functional expressions.

Of course, one can do things in a purely functional way if one dispenses with the pseudo-comprehension syntactic sugar of if let and/or for..in and rewrites everything in terms of map, filter and flatMap:

let arr:[Int] = ...
let opt: Int? = ...
  
let result = arr.flatMap { (a:Int)->Int? in 
  return opt.map { (b:Int)->Int in return a+b } 
}

It would be nice to not have to do this; to have a comprehension-style syntax which would let us specify the arrays and options we wish to go through and would assemble the result for us; perhaps it would look something like:

let result = for a in arr, b in opt { 
  return a+b 
}

(The use of the keyword return may be somewhat contentious, as (especially coming from a C background), one might expect it to return from whatever function contains the enclosing code. An alternative, as used in both Python and Scala, may be the keyword yield. But for now, in the interests of diverging as little as possible from Swift as it is, let's stick to return.)

Statements as expressions

Of course, by the time we have gotten here, we not only have functional for-comprehensions à la Scala, but we have, along the way, violated the implicit taboo against turning statements (such as for) into value-returning expressions. Once this is permissible, a wealth of possibilities are opened up. The pattern-matching switch statement, for example, starts to feel more powerful:

let description = switch(object) {
  case .User(let name): return "User '\(name)'"
  case .Group(let name, let members): return "Group '\(name) with \(members.count) members'"
}

Specifically, this would let us get rid of one ugly wart in the Swift language, i.e., initially undefined immutable values of this sort:

let description:String
switch(object) {
  case .User(let name): description = "User '\(name)'"
  case .Group(let name, let members): description = "Group '\(name) with \(members.count) members'"
}

An ugly workaround which, whilst comprehensible on a small scale, has the potential to become unwieldy.

Meanwhile, the C-style for loop could be pressed into service to generate arrays (or sequence types of some sort) on demand:

let squares: [Int] = for var i = 1; i < 5; i += 1 { 
  return i*i 
}

(Were one to omit the [Int] in the return value declaration, the result could be a lazy generator, which would evaluate the loop once for each value that is desired, which would lend itself to all kinds of lazy functional algorithms.)

And, of course, there is if, which would be merely a more verbose of the old C ? : operator:

let v1 = if a == 1 then "foo" else "bar"
let v2 = (a==1) ? "foo" : "bar"

In short, Swift as it stands (at version 1.2) is a few pieces of syntactic sugar away from being a much more elegant (and functional) language.

functional programming monads swift 2

2015/3/15

Swift snippets: flatMap and layout constraints

Since version 6, iOS has had a constraint-based layout engine for laying out views The constraint-based layout engine in iOS is considerably more powerful than the old system of auto-layout hints, allowing reasonably sophisticated flexible layouts to be specified purely as systems of constraints. However, it can be cumbersome to set up if creating all constraints individually; any reasonably complicated layout will soon have dozens of NSLayoutConstraint(item:attribute:relatedBy:toItem:attribute:multiplier:constant:) lines padding out its construction code, making one wonder why not just cut the Gordian knot and write code to manually lay out the view, as in the old days?

Fortunately, Apple provide a shortcut: the NSLayoutConstraint.withVisualFormat method; which takes a string describing the relationships between elements in an ASCII-art-style syntax known as the Visual Format Language, a few options and a dictionary of elements and emits a list of NSLayoutConstraints, as so:

let viewsDict:[NSObject:AnyObject] = [
    "lBtn" : leftButton,
    "rBtn" : rightBtn,
    "title" : titleLabel
]
let constraints = NSLayoutConstraint.constraintsWithVisualFormat("H:|-12-[lBtn(30)]-6-[title]-6-[rBtn(30)]-12-|", 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict)
myView.addConstraints(constraints)

As implied, each constraintsWithVisualFormat call takes a line of visual format language and produces an array of zero or more constraints; the line above, for example, would produce six; four distance constraints and two size constraints. However, one such line is rarely enough to unambiguously specify the constraints for a view and its contents; most layouts would require more than one line of visual format language to specify their constraints. The above, for example, covers only horizontal constraints; adding vertical ones to the mix would involve a second line, like so:

let constraints = NSLayoutConstraint.constraintsWithVisualFormat("H:|-12-[lBtn(30)]-6-[title]-6-[rBtn(30)]-|", 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict) + 
    NSLayoutConstraint.constraintsWithVisualFormat("V:|-10-[title(20)]", 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict)
myView.addConstraints(constraints)
Which gives two more constraints on the title label view: a distance from the top edge of the superview and a height. But what about the buttons?
let constraints = NSLayoutConstraint.constraintsWithVisualFormat("H:|-12-[lBtn(30)]-6-[title]-6-[rBtn(30)]-|", 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict) + 
    NSLayoutConstraint.constraintsWithVisualFormat("V:|-10-[title(20)]", 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict) +
    NSLayoutConstraint.constraintsWithVisualFormat("V:|-5-[lBtn(30)]", 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict) +
    NSLayoutConstraint.constraintsWithVisualFormat("V:|-5-[rBtn(30)]", 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict)
myView.addConstraints(constraints)
All of which soon starts to get somewhat unwieldy; there's a lot of repeated boilerplate there, which suggests that one could refactor it.

We could minimise the boilerplate by putting the visual format strings in an array of strings and mapping over them with constraintsWithVisualFormat. That would give us an array of arrays of constraints, which we could then flatten using reduce, like so:

let visualConstraints = [
  "H:|-12-[lBtn(30)]-6-[title]-6-[rBtn(30)]-|",
  "V:|-10-[title(20)]", ...
]
let constraints = visualConstraints.map { 
  NSLayoutConstraint.constraintsWithVisualFormat($0, 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict)
}.reduce([], { $0 + $1 })
myView.addConstraints(constraints)
Which is somewhat better, though it can be improved. As of Xcode 6.3, arrays (and optionals) in Swift will have a new operation named flatMap, which combines the map and flatten steps. In short, where a map takes a container of some values of type A and a function that converts an A to a B and returns a container of the same number of values of type B, flatMap takes the same array and a function that converts an A to a container of zero or more Bs, and returns a container of some number of Bs. In any case, with flatMap, the above code reduces to:
let visualConstraints = [
  "H:|-12-[lBtn(30)]-6-[title]-6-[rBtn(30)]-|",
  "V:|-10-[title(20)]", ...
]
let constraints = visualConstraints.flatMap { 
  NSLayoutConstraint.constraintsWithVisualFormat($0, 
        options:NSLayoutFormatOptions(0), metrics:nil, views:viewsDict)
}
myView.addConstraints(constraints)
flatMap is a useful operation, and one whose uses one can see in many places. In general, whenever a process produces zero or more items of output for each input, one wants to use a flatMap to handle them. Swift is also introducing flatMap on Optionals (which, of course, may be seen as a container holding zero or one items of a type), where it can be used for chaining a number of functions which may or may not yield a value:
func getCurrentUserIcon(session: Session?) -> UIImage? {
  return getUser(session).flatMap { getIconForUser($0) }
}
This is a little like Swift's optional chaining, with the key difference that, while optional chaining is limited to calling the underlying objects' methods, flatMap can apply any expression yielding an Optional; a move away from the object-oriented paradigm of objects and methods towards more functional techniques.

Unsurprisingly, flatMap is much more common in functional programming. The presence of a flatMap operation is one of the defining criteria of a pattern known as the monad, which, in a functional paradigm, can be used to define everything from container types to asynchronous operations to ways of compartmentalising state in functions without side-effects, in a way that follows consistent laws. Languages like Haskell and Scala use monads extensively, defining the relevant types in a consistently monadic fashion. And while Swift is not a functional language per se, it has been speculated for a while that it may be moving in an increasingly functional direction (albeit perhaps sufficiently gradually as not to alienate old Objective C hands); the arrival of flatMap could be more grist to this mill.

autolayout functional programming ios monads swift 0

This will be the comment popup.
Post a reply
Display name:

Your comment:


Please enter the text in the image above here: