Creating ASCII art in functional Swift

This article explores an iOS app, written in a functional Swift style, that converts an image to ASCII art. For example, when given the famous Lenna photograph…

…it creates a string that, when printed, looks something like this…

Zooming into her lovely face reveals that the image is actually text!

The Xcode project is available at https://github.com/ijoshsmith/swift-ascii-art

The big picture

Each pixel in an image is mapped to an ASCII value, referred to here as a symbol.

An image’s pixels are first transformed to an intermediary value, as seen below:

Let’s take this step-by-step.

First a pixel’s color is converted to a grayscale color. The grayscale color’s intensity (i.e. brightness) is normalized to a value between 0 and 1, where black is 0 and white is 1.

The next step is, to me, the most interesting part of the algorithm. Each color intensity value is translated to an ASCII symbol. Later we will visit the AsciiPalette class, which supports that.

Lastly, rows of ASCII symbols are joined to form a giant, multi-line string: the ASCII art.

Algorithm implementation

AsciiArtist implements the three steps outlined above; as seen on lines 31 to 33.

An AsciiArtist object relies on Pixel and AsciiPalette, which we’ll look at next.

Transforming pixels to intensities

Pixel represents the color at a specific image coordinate. A color consists of four bytes; one byte per channel (red, green, blue, and alpha). AsciiArtist asks a Pixel to determine its color intensity, which, as previously mentioned, is calculated by normalizing the pixel’s grayscale value to a percentage. Let’s see how that works…

In case you’re wondering about those weight values on lines 47 to 49, they are industry-standard numbers used for grayscale conversion, as explained here.

Transforming intensities to symbols

The symbolFromIntensity function in AsciiArtist transforms a color intensity to an ASCII symbol, by converting a normalized intensity value to an array index. That array is provided by AsciiPalette. The first symbol in the array is used for very dark pixels and the last symbol is for very bright pixels. Here is that AsciiArtist function again, for easy reference:

symbol_from_intensity

The question is: which ASCII symbols should be in the array, and in what order?

A poorly designed symbol palette yields improperly shaded ASCII art:

A better symbol palette produces a vastly superior result:

My approach to designing a good symbol palette is to let the computer figure it out. The AsciiPalette class renders each symbol to a separate image, with black text on a white background. It then sorts the symbols by the number of white pixels in their images. The more white pixels in the image, the higher the symbol’s intensity. The blank space character (‘ ‘) has the highest intensity value since it contains only white pixels, and would therefore be the last symbol in the array.

The AsciiPalette designated initializer requires a UIFont argument because the choice of font affects how a character is rendered, impacting the number of white pixels around it.

The code in this article is available at https://github.com/ijoshsmith/swift-ascii-art

Posted in Swift | Tagged , | 5 Comments

Zipping two lists in Haskell

Studying a pure functional programming, such as Haskell, can be an eye-opening experience. The standard library in Haskell provides a zip function, which combines the elements of two lists into a single list of tuples. I decided to implement my own version, named zip prime (actually, zip’ since Haskell allows a function name to include the prime (symbol). The simplicity amazes me:

The first line is the function declaration.  It states that zip’ takes two lists of possibly different element types (types a and b) and returns a list of tuples of those element types.

The next line explains what should happen when the second list is empty; return an empty list. Similarly, the line after that explains that an empty list should be returned if the first list is empty.

The fourth and last line of that function covers the case when neither list is empty. It creates a tuple from the first element in each list. That tuple then becomes the list element which precedes the result of zipping together what’s left of the two lists (i.e. zipping their tails).

What could be simpler?! I wish that Swift had this kind of  powerful pattern matching at the function definition level.

Posted in Uncategorized | Tagged ,

Caesar cipher in Swift

I posted a Swift project to GitHub that implements the Caesar cipher, which was the encryption technique used to protect Julius Caesar’s personal correspondence. It’s a straightforward algorithm that maps each letter in the alphabet to another letter.

The code also shows how to break, or “crack”, an enciphered message using basic statistical analysis.

Repository: https://github.com/ijoshsmith/swift-caesar-cipher

ENCIPHER -> FODJQIFS

Here are a couple of the unit tests in the CaesarCipherTests class, showing the expected output based on the input string and shift-by argument:

Here is how the encipher method in CaesarCipher works:

The Letters type seen in that code example is a trivial utility struct that simplifies working with an individual letter as its numeric character code. Unfortunately working with individual characters like this in Swift is cumbersome, because of the way Swift supports Unicode text. To treat an individual letter as its character code requires using the UnicodeScalar type, whose value property returns 65 for A, 66 for B, etc.

EFDJQIFS -> DECIPHER

The decipher method is more complicated than its encipher counterpart. It uses statistical analysis to search for the letter mapping that, when applied to the enciphered text, best matches the expected letter frequencies in a written language’s words (English words, in my case). The statistical tool used to calculate the degree of difference between the observed (O) and expected (E) distributions is known as Pearson’s chi-squared test.

The core idea in the decipher method is to try all 26 possible character mappings and find the one whose relative letter frequencies most closely match the expected letter frequencies. The expected frequencies are calculated on-the-fly, by analyzing a list of English words included in OS X. The LetterFrequency class is responsible for that.

These unit tests from CaesarCipherTests show what to expect from the decipher method, including the fact that it cannot decrypt all messages (especially very short ones).

Here’s how the decipher method in CaesarCipher works…

Happy coding!

Posted in Swift | Tagged , | 2 Comments

Functional parallel programming in Elixir

This article reviews a program that implements a parallelized algorithm, using a functional programming style made possible by a fantastic new language named Elixir. Along the way I very briefly introduce Elixir, review the relevance of functional programming in modern computing, and explain what parallel programming is all about. There’s a lot of ground to cover, so let’s get started!

The program

This programming exercise is based on finding what I refer to as a wordset. A wordset is a list of words that, when written on separate lines, read the same both horizontally and vertically. For example:

wordsets

You can run the program from a command prompt, such as Terminal in OS X. Type in a word and it will find all wordsets starting with that word. The program uses a list of words included with OS X, though a different word list could easily be used instead.

The source code, along with instructions on how to run the program, is available on GitHub at https://github.com/ijoshsmith/elixir_wordsets

Why Elixir?

Over the past few months I studied various functional programming languages, as well as the concurrency and parallel programming models their practitioners espouse. While certainly seeing value in each language I studied, only Elixir jumped out at me as elegant and expressive yet simple. It is a so-called impure functional language, meaning that it is built to support a functional programming style but also allows for symbols that can change value (a.k.a. variables).

Elixir code runs on top of Erlang’s virtual machine, commonly known as BEAM, just like Erlang code has for decades. Elixir code is compiled down to BEAM bytecode, just like Erlang code. Elixir is a modern language that enables today’s mainstream developers to harness the highly concurrent, fault-tolerant, distributed, bulletproof Erlang virtual machine that undergirds much of the telecommunication infrastructure on which our society depends.

After a few days of writing Elixir code, I was impressed. Once I saw firsthand how Elixir and the Erlang VM simplify multi-core computing, I was sold. I don’t expect to write Elixir code for a living any time soon, if ever, but the lessons I learn from the language and platform can be adopted in my daily software development practices. I wrote this article to share those lessons with others.

To learn more about Elixir visit its homepage:
http://elixir-lang.org

Watch José Valim, the creator of Elixir, discuss the history and future of the language:
https://www.youtube.com/watch?v=aZXc11eOEpI

Watch a thought-provoking talk by Dave Thomas about the mental shift Elixir enables:
https://www.youtube.com/watch?v=5hDVftaPQwY

For a more in-depth introduction to the Elixir way of programming, I highly recommend the ‘Programming Elixir’ book by Dave Thomas:
https://pragprog.com/book/elixir/programming-elixir

Functional programming

For many years mainstream software developers considered object-oriented programming an oddball curiosity that only the academic computer science crowd seemed to take seriously. Procedural programming was the mainstay of professional software development; where functions were functions, data were data, and real men wrote in assembler. ;-)

Once computing hardware became powerful and cheap enough to support the extra overhead object-oriented software requires, that approach to programming began influencing the design of languages used by mainstream developers, such as C++ and Java. This initiated a cultural shift and the Object-Oriented Era began. All hail the Great Superclass in the sky!

welcome_overlords

The story is essentially the same with functional programming. Granted, there have been functional programming languages used in production systems for a long time, such as Erlang and Haskell, just as there were languages that supported object-orientation before it became mainstream. But generally speaking, functional programming has been an uncomfortably weird way of thinking about software development, something most developers have probably heard of but never actually tried, like pole dancing.

pole_dance

Now that the free lunch is over and we must write programs that can effectively put multiple CPU cores to work at the same time in order to leverage hardware advancements, the functional programming style is moving from the incubator to the real world. Functional programming guides us toward writing code that can flourish in a multi-core world.

Instead of hiding variables in objects, functional programming avoids mutable state as much as possible. Rather than modeling software as a community of law abiding citizens who interact via socially acceptable protocols in public, but whose private lives are full of sins and secrets, functional programming is all about setting up pipelines that transform data from one shape to another. The focus shifts away from using objects to model a problem domain, and toward setting up data transformation pipelines. The developer’s time is not spent writing a detailed list of steps needed to make something happen; it’s spent describing at a high level how that thing should happen and letting the runtime worry about the nuts and bolts.

If you find this intriguing (I sure do!) be sure to watch the presentation I mentioned above by Dave Thomas.

Parallel programming

Now we’re getting into some really exotic and exciting territory. I first learned about parallel programming when studying General Purpose GPU programming, also known as GPGPU, while doing some CUDA programming. This article does not cover how to write code that runs on a graphics processing unit (GPU), though it’s a very interesting topic worth investigating.

Much of the parallel programming literature on the Web is either for computer scientists doing academic research, or it’s about using a GPU to crunch a ton of numbers at the same time for things like physics simulations and artificial intelligence. Very, very heady stuff. But don’t let the extreme nerd factor scare you off!

chalkboard

At it’s heart, parallel programming is just about doing a lot of stuff at the same time by running your code on multiple processor cores. The more work that can be done at the same time, the faster the overall task will complete (in theory). Not every task lends itself to being parallelized, so it’s not a silver bullet to solve all of your performance woes. Many people refer to problems that can and should be parallelized as “embarrassingly parallel.” I’m not sure what there is to be embarrassed about, but that’s the expression.

Functional and parallel programming are BFF’s

Functional programming and parallel programming go together like peanut butter and jelly. Mutable state is concurrent software’s kryptonite. If multiple instances of your code are running at the same time on several of a CPU’s cores, any changes made to shared memory must be done with extreme care and caution. Ideally you wouldn’t do it at all!

Many of today’s most popular languages and platforms equip developers with hardly more than threads and locks to cope with multi-core computing. That’s like giving someone a musket and bayonet before parachuting them into a modern battlefield. Functional languages encourage immutability and, in the case of Elixir, provide a battle-tested virtual machine whose concurrency model effortlessly scales across cores and machines.

The parallelized algorithm

I’m not going to walk through every line of code in the Elixir program that I wrote. If you want to see the whole thing, it’s on GitHub here. Instead, let’s focus on the most interesting part: the parallelized algorithm that finds all wordsets beginning with the same word. That code is in the Engine module, which you can see below or view in GitHub here.

the_code

The search function on line 8 is passed three parameters:

  • word – the word for which wordsets are found
  • find_words – a function that the engine calls to get all available words of a certain length that have a specified prefix
  • publish – a function that the engine calls when it finds a complete wordset that should be remembered for later

By Elixir convention, the search function has a helper function named do_search. It might look as if there are two do_search functions, on lines 11 and 15, but in Elixir one function can have multiple “heads” that specify different parameter states and conditions. The Erlang virtual machine evaluates these function heads at run-time to determine which one to invoke based on the parameters it will pass. In this example, the function on line 11 is called only if the number of strings in the words list is equal to the size parameter, which means the wordset is complete. The function on line 15 is called when the wordset is missing at least one word. And that’s where the magic happens.

Let’s review that function line by line. Here it is again, for quick reference:

the_function

Line 15: The parameters are the same as we saw for the search function above, but there is also a size parameter now. That represents the number of words in a complete wordset.

Line 16: This is called a guard clause. It contains conditions that must be true at run-time for this function to be called. In this case, it expresses that this function is called when a complete wordset is not yet available to publish.

Line 17: Call the make_prefix function to determine the sequence of letters with which the next word in the wordset must start.

Line 18: Call the find_words closure (i.e. function) to get a list of all available words that start with the prefix and are the right length for the wordset being built.

Line 19: Use the |> pipe operator to pass the word list retrieved on line 18 into a utility function I wrote in an EnumEx module called to_lists, which splits the list into N sub-lists of equal size. This enables me to break up the list of words into as many sub-lists as my computer has available processors. Note that the @sublist_count module attribute is used to determine how many sub-lists to create. I set that attribute to the number of “logical processors” available on the host computer, as reported by the Erlang runtime:

sublist_count

Line 20: This is where the magic happens! Pipe the list of sub-lists of words into the Parallel module’s each function, which is a simple utility function I wrote based on some code in the ‘Programming Elixir’ book by Dave Thomas. The standard Enum.each in Elixir executes a function for every item in a collection, one at a time. My Parallel.each executes a function for every item in a collection at the same time, by farming the calls out to the CPU’s available processors. The function call on line 20 does not complete until all of the parallel function calls it spawns off are complete.

Line 21: Get ready to pass the current sub-list of words through a pipeline…

Line 22: Filter out the words in the sub-list that cannot possibly be part of a valid wordset (refer to the “adaptive tail-sniffing optimization” area of Engine.ex to see how that works).

Line 23: Recurse into another do_search function call but this time put the current word from the sub-list into the words list. This is how the algorithm progresses through the available words. The &1 symbol refers to the current word, which is the first parameter of the function called by Enum.each. This is standard Elixir syntax.

Line 24: The end of the closure passed into Parallel.each on line 20.

Line 25: The end of the do_search function.

Parting thoughts

Regardless of whatever languages and platforms you might currently identify with, or are paid to write software for, it’s important to investigate and learn from what other technologies have to offer. The overall shape of software development’s future is the same for all of us, whether we write mobile apps or Web sites or desktop programs, etc. We must learn to embrace and utilize multi-core processors. Many of our beloved technologies, and the mindsets they engender, are simply insufficient for what’s coming next. I hope that this brief excursion into functional and parallel programming has helped sparked an interest in preparing yourself for the future of software development. Or, at least I hope you liked the Simpsons pictures!

Posted in Uncategorized

Getting into functional programming with Swift

This article examines two implementations of a logic puzzle written in Swift. The first example uses an imperative programming style, which is the style familiar to most iOS developers. Then we see the same small program written in a functional style, which is facilitated by several Swift language features.

Get the source code at https://github.com/ijoshsmith/break-a-dollar

The logic puzzle

A few days ago my friend mentioned over beers that there are 293 ways to break an American dollar. In other words, if someone hands you a one dollar bill, there are exactly 293 distinct coin combinations you can give them back to make it an equal exchange. The next day I started working out how to write code that counts the number of ways to break any amount of money. This article reviews two implementations of this logic puzzle.

If you are looking for an interesting puzzle to solve, consider putting this article aside until after you’ve written your own solution. I found this puzzle to be a very enjoyable challenge.

American coins

For readers unfamiliar with American coins, here is a quick overview of the coins and their values. Note, a one dollar bill and a one dollar coin are both worth 100 cents.

American coin values

Algorithm overview

After quite a bit of pondering, making odd hand gestures, and mumbling to myself about nickels and pennies, I eventually figured out a very simple way to solve this puzzle. I knew it would be easy to write a quick and dirty solution, but why settle for less? I wanted to find an elegant solution, so I kept attacking the problem from different angles until I found exactly that.

The key to the algorithm is to recursively subdivide the problem space. Determining how many ways you can break a dollar using all available types of coin is just a specific instance of the more general problem of determining how many ways you can break any amount of money using any subset of coins.

For example, suppose you wanted to find all possible ways to break a quarter. What this really means is finding all combinations of dimes, nickels, and pennies whose sum is 25 cents. If you were to start with a dime, then the problem becomes finding how many ways you can create 15 cents using dimes, nickels, and pennies. If you then add another dime, the problem is then to determine how many ways you can create 5 cents using nickels and pennies (of which there are only two: 1 nickel or 5 pennies).

Click here to read a more detailed review of the algorithm, in a text file included with the Xcode project.

Representing a coin

The algorithm I invented manipulates “coins.” A coin is simply an integer value that represents how many cents it is worth. I wrote an enum to define all available coin types, which also includes a static method that returns all coins in descending value order.

Imperative solution

A significant aspect of the imperative programming style is that variables change state. An imperative program is something like a micro-manager; it tells the computer exactly how to do its job. The following Swift code should look pretty familiar to most iOS developers, because Objective-C is an imperative language.

imperative

This code creates an array to hold the coins of smaller value than the current coin of interest. It appends items to the array in a loop, using a familiar loop-with-index construct. Then it uses a variable named ‘sum’ to count the number of ways to break some amount of money using an increasing number of the current coin of interest.

Code like this is the bread and butter of imperative programs. Now let’s venture into the weird world of functional programming to see how this same problem can be solved in a new way.

Functional solution

The functional programming style is heavy on functions and light on mutable state. By not having shared values change there are fewer ways for things to go wrong and less need for synchronization. Having functions as first-class entities in the language makes it possible to support higher-order functions, which allows functions to be composed out of other functions. iOS development has been heading in this direction for years with the introduction of blocks in Objective-C, and the host of APIs that started taking completion handler block arguments.

Here is my functional style solution:

This method’s second parameter is a Slice<Coin> instead of a Coin array because it does not need to copy coins into a new array. A “slice” of an array makes a portion of the array available, without creating a new array. The first line of the method creates a slice of the array, named ‘smallerCoins,’ which contains what functional programmers often call the array’s “tail.” The first item in a list is called the head, and the rest is called the tail. It’s worth noting that slicing an array will not cause an error if the specified range is out of bounds. In this example, when the array only contains one Coin (a Penny) the ‘smallerCoins’ slice is empty.

I created  ‘coin’ and ‘smallerCoins’ on the same line, using tuple syntax, because taking the head and tail of an array is arguably really just one task. Instead of writing separate lines of code to explain how to take the head, and then take the tail, we can instead be more descriptive and express the “take the head and tail” semantic in one fell swoop.

Instead of writing a loop and mutating a local variable to count the number of ways to break an amount of money, we can instead leverage the higher-order function named reduce. If you need a brief overview of what reduce is all about, check out my article about it here. This code reduces a list of integers, such as [0, 1, 2, 3, 4], where each value represents the number of a certain type of coin, such as 3 Quarters. The first argument passed to reduce is zero, which is the initial value of the sum parameter used by the closure/function that contains the reduction logic.

Parting thoughts

I’m excited by Swift’s support for a functional programming style. It can be a challenge to think in different ways, but in this case it’s worth the effort. A couple of years ago I taught myself enough Haskell to be dangerous. I was pleasantly surprised to find myself thinking of new ways to solve problems in my iOS development work because of my exposure to functional thinking.

Get the source code at https://github.com/ijoshsmith/break-a-dollar

If you’re interesting in seeing an Elixir implementation of this puzzle, click here.

Posted in Swift | Tagged , | 12 Comments

Maximizing the Preview Assistant Editor in Xcode 6

While working through a coding tutorial in the excellent iOS 8 by Tutorials book by the Ray Wenderlich crew, I learned about the new Preview Assistant Editor in Xcode 6. This is a feature that you can enable in an assistant editor while editing a view file (e.g. a storyboard or XIB). It shows what that view looks like on the ever-growing plethora of screen sizes, vastly reducing the time spent testing out UI changes on device simulators. It can also be used to see how a view will look when using strings from different languages, such as infamously long German words.

Rechtsschutzversicherungsgesellschaften!

Having this very useful feature relegated to an assistant editor is a shame. An assistant editor must share a window with its primary editor. I would prefer to open the preview in a new window, which would live on my second monitor, enabling me to see many different previews at the same time without needing to scroll around the assistant editor. I am not aware of a way to do this, but I found the next best thing. Here’s what my setup looks like:

The lefthand screen has the main Xcode window, in which I edit a view. The righthand screen has a maximized window with a nearly fullscreen preview of the view I’m editing on the left. As you can see in the photo, I can fit a preview of all four iPhone sizes into the screen at the same time. When I edit the view on the left, the changes are immediately reflected in the previews on the right. It’s pretty sweet!

Here’s how you can set this up…

  1. In the Project Navigator pane, single-click a storyboard/XIB file to open it in the main Xcode window.
  2. Now double-click that same file to open it in a new window.
  3. Move the new window to another monitor and maximize it.
  4. Click on the new window to make sure it has input focus, then type Option+Command+Enter to open an assistant editor in that window.
  5. In the assistant editor’s jump bar click on ‘Automatic‘ to open the drop-down menu (see the screenshot below if you don’t know what this means).
  6. Click on the ‘Preview‘ menu item to open the preview editor.
  7. Click and hold next to the assistant editor’s jump bar, then drag up or left (depending on which editor layout you prefer; vertical or horizontal), to maximize the preview’s screen real estate.

In case you didn’t understand the step involving the assistant editor’s jump bar, here’s a screenshot for reference:

Have fun!

Posted in iOS8 | Tagged , | 3 Comments

A Swift App that Calls JSON Web Services

In this article I introduce a small iOS 8 app written in Swift, named SwiftPlaces. I wrote the app in order to get more experience with the language and try out some new features in iOS 8, such as Adaptive Layout.

The source code is available on GitHub.
https://github.com/ijoshsmith/swift-places

SwiftPlaces allows the user to search for places by postal code and then view details about a place, including its current weather. It is a universal app, meaning it runs on the iPad…

…and on the iPhone…

iPhone

I made use of the new support in iOS 8 for using UISplitViewController on the iPhone, as well as the iPad. Due to the Adaptive Layout features in iOS 8 it was only necessary to create one storyboard to cover both device types, which is great news!

There are too many bits and pieces I find interesting to review here, so I suggest you download the code from GitHub and check it out in Xcode 6. Here are a few things to keep an eye out for…

Web services

The app calls two Web services from www.geonames.org, namely postalCodeSearchJSON and findNearByWeatherJSON. I wrote a simple class that fetches JSON from a server, named JSONService. Both of the Web services listed above are consumed via that class, which provides closure-based completion handling and the ability to specify which NSOperationQueue the closures run on. Here is an example of fetching a list of places with a given postal code, taken from SearchViewController.

postal-code-search

The success closure uses my custom marshal operator function (~>) to move between a background thread and the main thread, as explained here. This allows the app to create data model objects out of JSON, eliminate duplicate entities, and sort them by name on a background thread, leaving the main thread to only display those objects in a UITableView.

Note: I realize that some postal codes include letters, but it seems that the geonames Web service that I’m using doesn’t support them. I didn’t investigate the matter more than a few failed attempts at using Canadian postal codes. A happy side effect of this is the fun way I show an error message if the user tries to search for something other than a number. Check out UISearchBar+ErrorMessage.swift for details.

JSON processing

I decided to write the JSON-to-model conversion code in Objective-C, because Swift’s type safety is at odds with such an inherently “type unsafe” task. There has been quite a lot of activity and debate around JSON processing in Swift, but I found it was just plain easier to write that code in Objective-C. The following code is from Model Builders.m:

There is quite a bit more to explore in the project, so I encourage you to grab the code and check it out. If you know of a better way to use Swift or iOS 8 features than what I’m doing, please tell me about it in a comment.

Posted in iOS8, Swift | 8 Comments