New theme and new host

Did not post anything last week, as I have been busy moving the site over to BlueHost and setting up a new theme. All because I wanted Swift code highlighting, and WordPress.com doesn’t support that. This of course took a lot longer than anticipated, but it’s finally done and if I do say so myself the new theme is simpler and easier to read. So all in all it was worth it. What that “it” is I’ll briefly enumerate in the next post.

Parser combinator operators in Swift

This is part of a series on FootlessParser, a parser combinator written in Swift.


Parser combinators must be one of the best things to come out of functional programming. They let you define intuitive parsers right in the code, without any need for pre-processors.

Like this:

where function1 and parser3 return the same type.

parser will pass the input to parser1 followed by parser2, pass their results to function1 and return its result. If that fails it will pass the original input to parser3 and return its result.

Definitions

Parser
a function which takes some input (a sequence of tokens) and returns either the output and the remaining unparsed part of the input, or an error description if it fails.
Token
a single item from the input. Like a character from a string, an element from an array or a string from a sequence of command line arguments.
Parser Input
most often text, but can also be an array or really any collection of anything, provided it conforms to CollectionType.

Parsers

The general idea is to combine very simple parsers into more complex ones. So char("a") creates a parser which checks if the next token from the input is an “a”. If it is it returns that “a”, otherwise it returns an error. We can then use operators and functions like zeroOrMore and optional to create ever more complex parsers. For more check out FootlessParser’s list of functions.

Operators

<^> (map)

creates a new parser which runs parser1. If it succeeds it passes the output to function and returns the result.

<*> (apply)

creates a new parser which first runs parser1. If it succeeds it runs parser2. If that also succeeds it passes both outputs to function and returns the result.

The <*> operator requires its left parser to return a function and is normally used together with <^>. function must take 2 parameters of the correct types, and it must be curried, like this:

This is because <*> returns the output of 2 parsers and it doesn't know what to do with them. If you want them returned in a tuple, an array or e.g. added together you can do so in the function before <^> .

If there are 3 parsers and 2 <*> the function must take 3 parameters, and so on.

<*

The same as the <*> above, except it discards the result of the parser to its right. Since it only returns one output it doesn't need to be used together with <^> . But you can of course if you want the output converted to something else.

*>

The same as <* , but discards the result of the parser to its left.

<|> (choice)

This operator tries all the parsers in order and returns the result of the first one that succeeds.

Example

FootlessParser: updated documentation and readme

The FootlessParser project is finally becoming usable and now has brand-new documentation generated by jazzy. The readme has also received some attention and is now actually useful:


FootlessParser is a simple and pretty naive implementation of a parser combinator in Swift. It enables infinite lookahead, non-ambiguous parsing with error reporting.

Also check out a series of blog posts about the development and documentation from the source code.

Read More

Making a Numeric Type in Swift

Fabián Cañas demonstrates something similar to mixins in Swift (for operators):

By defining types (and protocols) around capabilities, and writing functions that target those capabilities, we end up with cleaner and remarkably reusable code when compared to implementing functionality targeting a specific type. The bulk of our final implementation has nothing to do with distances, time intervals, apples, oranges, or anything else. It reads more like a set of statements of fact that any future programmer could adopt if they so chose.

Swift: Associated Types

Russ Bishop has a clarifying post about Swift protocols and generics:

Type parameters force everyone to know the types involved and specify them repeatedly (when you compose with them it can also lead to an explosion in the number of type parameters). They’re part of the public interface. The code that uses the concrete thing (class/struct/enum) makes the decision about what types to select.

By contrast an associated type is part of the implementation detail. It’s hidden, just like a class can hide its internal ivars. The abstract type member is for the concrete thing (class/struct/enum) to provide later. You select the actual type when you adopt the protocol, not when you instantiate the class/struct. It leaves control over which types to select in a different set of hands.

But I do think he is too harsh on the functional programming hipster kids.

Add Result type and operators

This is part of a series on FootlessParser, a parser combinator written in Swift.


Add Runes and LlamaKit using Carthage

https://github.com/kareman/FootlessParser/commit/6142452334dae45a5aae65e0f54264f1ea3f533d

Footlessparser is using operators for map ( <^> ), flatmap/bind ( >>- ) and apply ( <*> ). Luckily the Runes framework has already defined these, and implemented them for optionals and arrays.

Each parse returns a Result, which has either a tuple containing the output and the remaining unparsed part of the input, or an error description if parsing fails. The Result enum is in the Llamakit framework, later replaced by antitypical/Result.

Add Runes+Result.swift

https://github.com/kareman/FootlessParser/commit/c49709d9bb17291fac6b82a0fe136d6d10e1bd9f

To implement the operators mentioned above for parsers it is very helpful to first implement them for what parsers return, i.e. Result. Gordon Fontenot did just that in this pull request to Runes. It was never merged, so it’s included here.

Rename Runes+Result.swift to Result+Operators.swift

https://github.com/kareman/FootlessParser/commit/74230bb5148e827debf610c8f3c8259b8b4a77b9

I renamed the file later to make the name more descriptive and not so foreign for those who have not heard about the Runes framework.

Switch from LlamaKit/LlamaKit to antitypical/Result.

https://github.com/kareman/FootlessParser/commit/f527d9e0e8999479c4627dd4ffdd5871174b7edf

Later on the Llamakit project recommended switching to antitypical/Result. This lead to several changes:

  • the success and failure functions for making a Result moved to the Result type and became static instead of global. Which is good, functions only involved with one type should be defined in that type.

  • Result became a struct, not an enum. Which seems strange as it is either a success or a failure, never both. It was made back into an enum later.

  • the Result framework brought with it the micro frameworks robrix/Box, robrix/Prelude and robrix/Either. Especially Prelude has some basic functional programming functionality that will come in handy.

Set up an open source Xcode framework project

This is part of a series on FootlessParser, a parser combinator written in Swift.


I find these steps helpful when setting up any new open source framework project in Xcode.

Create project

https://github.com/kareman/FootlessParser/commit/414e3961d3bb2a2df8a257804534578bc7a06461

Create a new project in Xcode, and select OS X framework if it is for both iOS and OS X. The iOS framework target can be added later, besides OS X frameworks are more practical for unit testing. No simulators needed.

Do not select to add it to Git right away. Because of this.

And that’s it. I so do love a fresh project.

Create root folders “tests” and “source” and move stuff in place in Xcode

https://github.com/kareman/FootlessParser/commit/9e43f2f3d284c960c011aa2eecb646df4eb75d15

The file structure of Xcode projects looks better, especially on GitHub, if the code for the product itself is in “source” and the test code in “tests”. It’s better than just dumping all Xcode targets in the root folder. Especially for this project, as it will have test targets for both unit tests, speed tests and integration tests.

Share the only scheme.

https://github.com/kareman/FootlessParser/commit/4eac262ad46fdb846b968d2bb8d5936a3c26d941

Schemes are not shared by default in Xcode. It’s best to share this now since you’re bound to be making changes to it in the future, and if it’s not shared no one else will receive those changes. While you will be merrily coding along, assuming what you see everyone else sees too.

Add license.

https://github.com/kareman/FootlessParser/commit/4ee0dda754593e4355e348d43c7dce4869d00ac6

Which licence to release open source code under is of course entirely a matter of preference. Personally I agree most with the Eclipse licence because I would prefer anyone who make any changes to make them public and open source as well. But I also want my open source projects to be available to as many people as possible, and the MIT license is very popular and compatible with most other licences, including GPL. And it is used by all the open source frameworks this project uses. It is also very short, which is always a good thing for legalese text.

Upload to GitHub

After adding some actual code it’s time to share the work with the world. It is easiest to use GitHub for Mac as it both creates the project on GitHub and uploads the code.

Introduction to FootlessParser

This post is part of a series on FootlessParser, a parser combinator written in Swift.


The goal is to define parsers like this:

where parser will pass the input to parser1 followed by parser2, pass their results to function1 and return its result. If that fails it will pass the original input to parser3 and return its result.

Terms

Parser
a function which takes some input (a sequence of tokens) and returns either the output and the remaining unparsed part of the input, or an error description if it fails.
Token
a single item from the input. Like a character from a string, an element from an array or a string from a sequence of command line arguments.
Parser Input
most often text, but can also be an array or really any collection of anything, provided it conforms to CollectionType.

First version

Initially FootlessParser will be the simplest possible implementation of a parser combinator in Swift. It will:

  • have at least rudimentary error reporting, because it makes writing parsers so much easier.
  • not parse ambiguous grammars. Each parser will return at most one result, not a list of all possible results.
  • not handle left recursion. Like most parser combinators.
  • probably be slow. It’s going to be very interesting to see how slow.

Future improvements

  • Memoization, should help with speed.
  • Left recursion.
  • Ambiguous grammars (maybe).
  • SequenceType as input.

Writing a parser combinator in Swift

This post is part of a series on FootlessParser, a parser combinator written in Swift.


Before Swift my only contact with functional programming was a couple of half-hearted attempts at reading Erlang, all of them resulting in me running away screaming, clutching my aching head. But learning functional concepts in Swift proved far easier, probably because the syntax is closer to what I was used to. So I read Functional Programming in Swift and everything was well and good until one of the last chapters, “Parser Combinators”, and the headache was back. Luckily I managed to stay quiet and in place this time. I downloaded the code for the chapter, turned it into a framework and hacked away until I had implemented a CSV parser, but I still didn’t really understand it.

The parser library from the book has 6 swift files and more than 50 functions (including operators), all but 10 consisting of only one line. Stepping through the code in the debugger lead to a call stack a mile long which never seemed to reach a function that did some actual work and then returned, instead it appeared to be just functions all the way down. I don’t mean this as criticism of the chapter in particular or functional programming in general, it is more a description of my lack of understanding at that point. So to improve on that and understand functional programming and parser combinators better I am implementing one myself; FootlessParser.

The name comes from the scientific name for Swifts, “Apodidae”, from Greek “apous” meaning “without feet”. The word also has alternate meanings, depending on how the parser turns out it will either be apt or self-deprecating, in any case two of my favourite things.

I will write about the development here. There doesn’t seem to be any complete parser combinator frameworks in Swift out there, hopefully this will be useful to others as well.

BTW I really do recommend the book for anyone interested in functional programming and Swift, it is well written (and offers a real challenge in the last chapters).

Adding an XCode project to Git

When creating a new project in Xcode it is best to leave the “Create Git repository” box unchecked because it will immediately add all files to Git, including those that are specific to you and are of no interest to anyone else. Instead you can run this script from the project folder, which will add only the files that should be under version control:


#!/bin/bash -x

# create the ignore file
cat > .gitignore <<_EOF_
# Xcode
#
.DS_Store
build/
*.pbxuser
!default.pbxuser
*.mode1v3
!default.mode1v3
*.mode2v3
!default.mode2v3
*.perspectivev3
!default.perspectivev3
xcuserdata
*.xccheckout
*.moved-aside
DerivedData
*.hmap
*.ipa

# CocoaPods
#
# We recommend against adding the Pods directory to your .gitignore. However
# you should judge for yourself, the pros and cons are mentioned at:
# http://guides.cocoapods.org/using/using-cocoapods.html#should-i-ignore-the-pods-directory-in-source-control?
#
# Pods/
_EOF_

git init
git add .
git commit -m 'Initial commit'