Friday, June 13, 2014

First experience with Swift: primes

When Apple first announced Swift, I downloaded Xcode 6 beta, went through the tutorial/manual, and built a trivial Cocoa app…

But really, building GUI bindings tells you very little about how easy and fun it is to use a language (unless it's just really, really bad); the more interesting thing is to try to code some algorithms and see whether you can think the way you would in a higher-level language, or whether you have to think in more C-like terms.

So, let's generate some primes.

The code for these examples is all at

Sidebar: emacs

A quick google for "emacs swift mode" turned up, which requires emacs 24. Apple's built-in emacs is 22.1.1, and Aquamacs 2.4 is 23.4.1, but the Aquamacs 3 alpha is, and so far it seems to be working great. So, I'd recommend downloading Aquamacs 3.0a.

Building a command-line app from the command line

First, of course, you have to get swift ready to go. Install Xcode 6.0b1 or later, xcode-select it, then you can use "xcrun swift", both to start an interactive session or to compile a program. You may want to create an alias or shell script so that you can just use "swift" instead.

One interesting thing about the swift compiler is that the default name of a program is the (suffix-stripped) name of the first source file, rather than a.out. So, the Makefile to build a bunch of single-file swift programs can look like this:
    all: foo bar baz

    %: %.swift
    xcrun swift $<
But what about the code? It was a bit hard to find documentation on this. Google told me that C_ARGC is an Int and C_ARGV an UnsafePointer<Cstring> that hold exactly what you'd expect.

An UnsafePointer is how a C pointer (which can, of course, be a pointer to an array) is represented in Swift. So, maybe C_ARGV[1] is a CString? optional string? Nope, it's a CString. So you need to check C_ARGC before accessing C_ARGV. OK, that's fair... but can you put a normal bool expression and an optional-value binding into a single if statement, or do I need a mess of nested if statements here? It seems like the latter.

Well, the mess shouldn't be too bad. String.fromCString(C_ARGV[1]) gives me a String, and String.toInt returns an Int?, so I just need if let limit = String.fromCString(C_ARGV[1]).toInt(), right? No, that gives me an error--first "partial application of a struct method is not allowed" on the ".toInt", and then "bound value in a conditional binding must be of Optional type". Why? I don't know. Splitting everything into three lines works, but at this point, it seems worth wrapping it all up as a function... which is sad, but I'm sure I'll find a better way later. Anyway:
    func intifyarg1() -> Int? {
        if C_ARGC == 2 {
            let limitstr = String.fromCString(C_ARGV[1])
            if let limit = limitstr.toInt() {
         return limit
        return nil

    if let limit = initifyarg1() {
    } else {
        println("\(C_ARGV[0]) LIMIT")

By comparison, the Python equivalent is:
        limit = int(sys.argv[1])
        print("{} LIMIT".format(sys.argv[0]))
But again, hopefully there's a better way to do this.

A simple sieve

One way to generate primes up to some limit is to create an array of LIMIT bools (initially all set to true), then iterate through them, updating all multiples of each from true to false. The easiest implementation relies on being able to mutate the values (but not the shape) of the array as you iterate it. Here's a simple Python implementation, borrowed from
    def primes(limit):
        prime = [True] * (limit+1)
        prime[0:2] = False, False
        primes = []
        for (i, isprime) in enumerate(prime):
            if isprime:
                for n in range(i*i, limit+1, i):
                    prime[n] = False
        return primes
So, how hard is this same algorithm to implement in Swift? Pretty easy. I couldn't find any trivial way to create a range with non-unity step so I had to use a C-style for loop, but otherwise, I got it right on my first try, and it looks pretty readable to me:
    func primes(limit: Int) -> Int[] {
        var prime = Array(count: limit+1, repeatedValue: true)
        prime[0...1] = [false, false]
        var primes = Int[]()
        for (i, isprime) in enumerate(prime) {
            if isprime {
                for var n=i*i; n<=limit; n+=i {
                    prime[n] = false
        return primes

Printing the output

In Python, given a list of primes, the obvious way to print it out is:
    print(*primes, sep=' ')
But I wouldn't expect another language to have anything quite that nice. Even Python 2 doesn't have anything that nice. Instead, I'd expect to convert the primes to strings and join them with spaces, then print the result. Like this:
    print(' '.join(map(str, primes)))
There are a few problems trying to do the equivalent in Swift.

First, as cool as string interpolation is, it occasionally gets in the way where a simple duck-typed print function and/or str.format method doesn't. In particular, you can't throw a string literal in the middle of something you want to interpolate. But that's easy to fix; just let space = " " and use that.

Next, there is no str function. The equivalent is a description property on (I think) AnyObject. But I don't know how you map a property (or even an unbound method); just a function. If we wanted to do this generally, we'd want a generic function to convert a Sequence<AnyObject> to a String by joining the description of each object, but that doesn't seem to be as easy as it should be. (This is the first place I've found where C++ has better type inference than Swift...) So let's forget about being generic and just cram an inline function into the map call (using the somewhat-Ruby-blocks-like syntax that allows you to define a function inline as the last argument to another function, without putting it inside the parentheses):
    let result = " ".join(map(primes(limit)) { 
            (var number) -> String in return number.description
I'm not sure of the idiomatic way to indent that (and neither is swift-mode...), but it's not too terrible. Also, I'm not sure having the inline function outside the parens is very helpful when it's inside another function call anyway. Either way, it looks like this may lead to a lot of JavaScript-style }))})})) endings…

Fortunately, Swift has a concise way of writing inline functions that makes things like this a lot simpler, although it's more than a little ugly and perlish:
    let result = " ".join(map(primes(limit)) { $0.description })
Finally, even with the space constant, the string interpolation still fails. And I have no idea why. Apparently the expression is too complicated to fit into an interpolated expression in some way that the compiler can't diagnose for me. Hopefully this is just 1.0 teething troubles.


What if we wanted to generate a potentially-infinite sequence of primes? We could do that by filtering a sequence of integers with an isprime function. The function needs to store (memoization) state between calls. Python has a few different ways to cram that into the function itself for generality, let's use a closure, because any decent language should be able to handle the equivalent. So:
    def make_isprime():
        memo = []
        def isprime(n):
            for prime in memo:
                if not n % prime: return False
            return True
        return isprime
This is just as natural in Swift as in Python; no stumbling blocks at all writing this on my first try:
    func make_isprime() -> (Int -> Bool) {
        var memo = Int[]()
        func isprime(n: Int) -> Bool {
            for prime in memo {
                if n % prime == 0 { return false }
            return true
        return isprime

Finite generators

Now, how do we use this to find all primes up to LIMIT? Well, we could just filter the closed range from 2 to LIMIT:
    primes = filter(make_isprime(), range(2, limit+1))
What does this look like in Swift? Easy!
    let primes = filter(2...limit, make_isprime())

Infinite generators

But what if we instead wanted to filter an infinite sequence, then truncate it, like this:
    primes = filter(make_isprime(), count(2))
    limited_primes = takewhile(lambda prime: prime <= limit, primes)

(Why would you want to do that? Well, let's say you wanted the first 100 primes, rather than the primes up to 100. You have no way of knowing in advance what input sequence to pass to filter.)

I have no idea how to do this. I think you'd have to write the equivalent of the itertools functions (count and takewhile) yourself. As far as I can tell from a quick check, Swift has nothing like Python's yield-based generator functions, or generator expressions; the only way to do it is to create explicit classes that implement the Sequence and Generator Protocols. Honestly, if that were the only way to create iterators in Python, I don't think the idea would have taken off. That being said, it may be that the answer is a lot more (itertools-like) higher-order functions and a lot fewer explicit generators. Until I actually try it out, it's hard to know how usable it will be. All I can say is that it's nowhere near as simple to do this right out of the box as it is in Python, Ruby, or Haskell.

Printing, again

I tried to print this out using the same code as last time, but whether I put the filter inline, or use a variable, it doesn't seem to work. If you iterate over the filter result, you get all the right value, but if you pass it to map, you get nothing! I have no idea why. So I fell back to using an explicit loop. Ick.
    for prime in filter(2...limit, make_isprime()) {
        print("\(prime) ")


Some of the stuff I ran into here is probably based on my lack of knowledge, and some of it probably based on this being the first version of the language. For a compiled, statically-typed language, Swift seems pretty good, but it's not quite as magically Python-/Ruby-like as it at first appears.

Also, I didn't look at all into how powerful the type system is (except for my brief foray into trying to write up a generic joinup function). A statically-typed language with a sufficiently-powerful type system (like Haskell) is every bit as usable as a dynamically-typed language, but with a weak type system (like Java), you end up with horrible casts and checks all over the place, giving you the worst of everything—inflexibility, verbosity, and lack of safety. So, that's a pretty important question, but I'll get to it later.

No comments:

Post a Comment