Making Swift even more functional
Understanding how Swift works under the hood is crucial for identifying improvements to the language.
Hey everyone, it's great to be here. We're talking about making Swift even more functional. I'll skip the introduction since that already happened. So Swift was released to the world last year, June 2, 2014. Swift is still very young and fast moving and as we can see from huge releases like Python 3 and Perl 6, it's difficult to make major changes to a language after it's been around for a while. The Recurse Center is a free educational retreat for programmers, and they have this great user's manual that talks about how to be a great programmer and how to learn programming most efficiently. And I admire their philosophy, but I wasn't always rigorous. I used to think it was more important to know lots of APIs, languages, frameworks. I wanted to build things and I wanted to show them off.
We'll see that understanding how Swift works under the hood is crucial for identifying improvements to the language.
01:28: We'll see that understanding how Swift works under the hood is crucial for identifying improvements to the language. So what is functional programming? I'm going to quote Chris' book, "Functional Programming in Swift". So “Functional programmers emphasize that each program can be repeatedly broken into smaller and smaller pieces; and these pieces can be assembled using function application to define a complete program”. So what makes this possible? Well, “Functional programming… emphasizes the importance of programming with values, free of mutable state or other side effects”. We can see exactly what Chris was showing with class versus struct.
So why is functional programming awesome? I have three main reasons here. I will not go into detail, but there's other great talks going into detail on each of these reasons. So- it helps write clear and concise code. It makes concurrency, which is very hard, easier to reason about. And it reduces complexity in our code bases. So this is an example from Natasha The Robots Blog, showing the value of flatMap which was introduced in Swift 1.2. So one example of how functional programming makes our code less complex and more clear. I think Swift is simple, but simplicity is very hard to define. So simplicity's important, but how do we even define it? How do we even say that Swift is simple?
03:22: Well, I'm going to compare it to Scala, which is a language I've had about two years of professional experience with. Even after those two years, I found the language too complex. There were two main things; too many custom operators and it's not opinionated enough. We've heard yesterday and previously, how Swift is very opinionated. It has an opinionated compiler, for example, with initialization. And also, lots of things around making the language safer. And with languages that are not so opinionated, there's lots of different ways to do the same thing. This makes it hard for people to read existing code and make decisions about new code to write.
So the two main functional programming features I would like to add to Swift are list comprehensions and tail call optimization.
So the two main functional programming features I would like to add to Swift are list comprehensions and tail call optimization. And I'm going to go through each of those, explain the current state of these features, and also what it would take to add them to Swift. List comprehensions are already found in Python and other languages. They provide a concise way to create lists. Common applications are making new lists where each element is the result of some operations applied to each member of another list. Or to create a sub-sequence of those elements that satisfy a certain condition. So looking at simple examples of list comprehensions, it's hard to know what the real value is.
05:08: List comprehensions, however, are very powerful. Here's one example of a list comprehension in Python that takes two lists as input. But we're going to stick to some simple examples here so I can show what the key importance of list comprehensions are, and that's conciseness and generating faster byte code. So this is a simple list comprehension in Python. And I used dis, which is a disassembler that's built right into the Python standard library to check out the byte code. So we're not all looking at byte code every day, I'm certainly not. Really, the most important thing to notice about this byte code is how long it is, how many instructions.
So there's about 14 instructions in this byte code. This is a Python For-Loop. It does the same thing as that previous list comprehension. I couldn't even fit the byte code on this slide. It's about double the number of instructions. So there's definitely a lot of optimizations happening here. What can we do in Swift? We can make use of great high order functions like map to recreate list comprehensions, and here's a good example. The top is using map. The bottom produces the same result using a for Loop. Using the Hopper disassembler for iOS, I checked out the byte code. Unfortunately, the byte code is exactly the same, and that isn't very surprising. List comprehensions aren't built into Swift, and we're just recreating it using some high order functions. So we're getting the conciseness. Our code is clearer, but we're not getting these low level optimizations.
So if conciseness is the main value we're getting, what is so great about conciseness?
07:15: One awesome application of list comprehensions I found was a spelling corrector. Peter Norvig, who's the director of research at Google, wrote a great spelling corrector, not quite production-ready, but very accurate and only 23 lines of Python, and it made extensive use of list comprehensions. Airspeed Velocity ported it to Swift, and we can see here, using this list comprehension like operations, using this map here, we can find the splits, we can find the deletes. I edited some of the code out for clarity, but you can find the set of all the deletes transposes, replaces and inserts. So for example, a delete would be going from Swift to sift. So if conciseness is the main value we're getting, what is so great about conciseness? I'm sure many of you have read code that was too concise, it was opaque, it was hard to reason about. So there's definitely a sweet spot that these list comprehension like operations fit in. And the best long-form defence of conciseness I found, was "Succinctness is Power" by Paul Graham. It's a great essay and it quotes this study from Ericsson. So Ulf Wiger did a study at Ericsson that concluded that Erlang was four to ten times more succinct than C++ and proportionately faster to develop software in.
So we don't necessarily write many more lines of code per day. But if we use more succinct languages, more succinct language features, we can produce more in a given day. So that is the real power of conciseness. So you think these are awesome, you wanna add them to Swift. What would that take? Well, in my research, I didn't find any compelling reasons why it would be impossible or difficult. The syntax would be similar to Python. And if you are an expert in language design and you wanna talk to me about this, feel free to tell me if I'm right or wrong, if it would be easy or impossible. But I think it would be very straightforward to add to Swift.
Next is tail call optimization. So to understand why tail call optimization is really important to functional programming, we need to understand why recursion is really important to functional programming. So if we're in a pure functional language like Haskell, where we wanna avoid all side effects, that means we can't have loop counters. So the most iterative a pure functional language can get, is to iterate over a list using for each or map. Recursion is a natural match with pure functional programming. No state is needed to recurse except read-only function arguments and write-only return value. A tail call is a method or function call that is the last instruction inside of another method or function.
A tail call is a method of function call that is the last instruction inside of another method or function.
10:28: So to understand this, let's look at an example. This has a tail recursive call. That's the return fact at the bottom. So that's a tail call subroutine that is recursive. So, the important thing to look at is the stack trace. We only need to keep track of the same amount of data for every call because we're just returning the value we get right through to the top. This means that if we code factorial of a billion, it would only take the same amount of space as factorial three. That is awesome. So what about if we're writing code that's not tail recursive? So, this isn't tail recursive because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns. It has a very different stack trace, which is very scary. As we can see, it kind of fans out here. So large values get larger and larger, have to do it larger, more and more operations. So large values as input that factorial of a billion, it may cause a stack overflow. Tail call optimization to the rescue. So this is the compiler optimization where the compiler replaces the recursive code with a loop.
We avoid allocating a new stack frame for a function, because the calling function just returns the value that it gets from the called function. Unfortunately, in Swift, it's not guaranteed. So here's some Swift code, and how would we know if the tail call optimization happens here? Well, we can check out the byte code. So we know tail code optimization happens because of the jump, if not equal, to the label containing the conditional jump. So this is a very popular answer on Stack Overflow, and it kind of might imply that tail call optimization always happens. So I found a counterexample. In the dev forums, someone posted about this binary search where they were running into lots of retain and release ARC cycles. Performance was bad compared to C and even compared to Java.
12:58: So, Chris Lattner commented on this post in the dev forums. He said that the tail call optimization didn't happen in that case because of an optimizer deficiency relating to the self-release that implicitly happens after the call, but before the return, blocking the tail recursion. He said this optimizer issue was a serious bug that needs to be fixed in any case. So this was September 2014, and I haven't found any updates.
...I'm looking for an approach where I could write Swift code that changes the byte code.
If you haven't found a life philosophy yet, I encourage you to try this one out. So what if we could change the byte code? What if we could do it ourselves? Well, it's possible to do this in Python. I know my talk is starting to sound like an advertisement for Python, but really, Python's cool. So you can manipulate the byte code at runtime in Python, because you can swap out the code object for a function in Python. This is definitely an implementation detail. Unfortunately, it's not really possible in Swift. On iOS, any page of memory that can be written to can no longer be executed. So on OS X, you could shell out to swiftc, dynamically load the resulting binary, but it would be pretty painful. Python has a simplification of not being compiled down into assembly ahead of time like Swift. And I'm looking for an approach where I could write Swift code that changes the byte code. I'm an application level engineer and it's just not really possible to do that in Swift. So is this a big deal? I care about this. Why should you care about this? Well, it really matters what kind of applications you're writing.
So here's a conversation on Twitter between two Robs I really admire. So first Rob says, "For moderately-size data structs, recursion builds incredibly robust code." Hey, I wanna write robust code. The other Rob is like, "Well, my experience thus far, recursion kills. More precisely, lack of tail call optimization." So it really matters what your data structures are but if you're running into stack overflow issues when doing recursion, this is the issue. So here's a radar that was filed earlier this year for implementing tail call optimisation in Swift, just like it's implemented in Scala. And I really like this. So the Scala compiler will automatically optimise any truly tail recursive method. If you annotate a method that you believe is tail recursive, the compiler will even warn you if the method is actually not tail recursive.
So you're really jazzed about this functional programming, this byte code, Scala perhaps, you want to learn more. Well, I have resources galore for you. So, how many of you all went to the Functional Swift Conference last year? This was actually before I even started coding Swift, but I watched the videos online and Justin Spahr-Summers' talk "Enemy of the State" is really great for explaining why you should avoid mutable state in your code. I also spend a lot of time on Open Radar since Radar's not publicly searchable or open in any other way.
16:42: My only issue is that it's still hard to know from Open Radar if Apple's actually working on a radar. It's rare to see any comments or follow-up on Open Radar that people post. I also searched through the developer forums to see what features Apple developers are talking about. It's a good way to see if there's any interest in a new feature. Of course, I love Twitter, because I can overhear conversations that are over my head and I learn a lot by reading them and trying to understand what people are talking about. I also have to plug "Natasha the Robot's" blog. She writes about a wide variety of interesting topics, including functional programming and Swift. What I really love about her blog is that she incorporates feedback and comments from her readers. So she wrote a blog post where someone responded and said, "Hey, tail call optimization isn't guaranteed in Swift." And she incorporated that feedback into her blog and that's how I learned that tail call optimization wasn't guaranteed in Swift. So as you know from what I said on the panel yesterday, I care a lot about what happens when Swift goes open source and I really hope we'll be more involved in the process of how the language evolves and we'll be more aware of what Apple's working on. Thank you.
...I care a lot about what happens when Swift goes open source and I really hope we'll be more involved in the process...