Typeclasses in Swift, Haskell and Scala

What is a typeclass?

Typeclass is a Haskell way of creating the type composition in the world without inheritance. It allows to define a desired behavior in a form of function signatures. The concrete implementation is provided separately for all the required types. In other words, it splits the familiar object-oriented encapsulation (data and functionality together) in two separate parts: data and functionality. At the same time typeclass defines a contract that we can build upon. It’s like defining the same function multiple times – each time the only thing that differs is the type in the signature – and making it possible to use this function in some other place without specifying which one of its variants should be used. The compiler guesses it for us.

Doesn’t it sound like Swift or Objective-C protocols? Well, it does. It’s no surprise, because they’re all fueled by same basic idea. This is the first and arguably the most important thing to know about typeclasses – although they do have a word class in their name, they are more similar to protocols. Actually, they are far enough from classes so they can independently coexist with them, orthogonal to each other.

Typeclasses, being protocol cousins, are used in similar fashion: to express a feature that spreads across multiple types. In Haskell there are typeclasses like Eq, expressing that things are equatable, or Ord, expressing that they are sortable, or Functor, expressing that they can be mapped over.

If you’ve seen WWDC 2015 session “Protocol-Oriented Programming in Swift”, you’re gonna feel at home (or run away screaming, depending on how you liked it). One thing to notice: while in a more strict functional language, namely Haskell, typeclass is a part of its type semantics, in Swift or Scala typeclass is more of a design pattern. We’re using their native type semantics to achieve similar effects.

Enough with introduction. Let’s define a typeclass so we can more easily grasp what’s going on.

Things that can be encoded in Ceasar cipher

Have you heard of Caesar cipher? It is a very basic cryptography method: we express anything as a string and than we shift each letter by a fixed number of places in the alphabet. So, for 3-letter Ceasar cipher we write D instead of A, E instead of B, F instead of C and so on.

Our typeclass is gonna describe the ability to be expressed in a Ceasar cipher form. It’s gonna be based on position of particular character in the ASCII table. For the sake of simplicity I’ll ignore the fact that in the ASCII table there are some special characters after the last letters of the alphabet. No one is actually sending messages to Roman legions anymore, so no one is gonna get surprised by some %$#.

Here is the Ceasarable typeclass defined in Haskell:

class Ceasarable c where 
    toCeasar :: c -> String

Just to mess with object-oriented minds, it uses keyword class to kick off its definition. Then it declares one function signature: toCeasar. The function takes one argument of any type and returns a string, presumably with the cipher shift applied. This is our desired behavior. It must be implemented (with the actual type instead of c) by the typeclass instances.

How does it gonna look like in Scala? We’re gonna use Scala’s type semantics. The most obvious way is to use trait:

trait Ceasarable[T] {
    def toCeasar(input: T): String
}

The translation is straightforward. Any type in Haskell becomes a generic parameter in Scala. The signature is the same.

In Swift the closest thing to traits/interfaces are protocols, so let’s search no further:

protocol Ceasarable { 
    typealias T static func toCeasar(input: T) -> String 
}

Apart from minor syntax differences, like associated type instead of generic parameter, it’s the same as in Scala. Not surprising, as those two languages share a lot of similarities (and I mean like, a lot). One thing to notice is the use of static method. Why is it static? Because we want to emulate the split between the data and behavior. If the method is not static, than it can use the instance data and there is (in our simple case) no need to pass input at all. An instance method declaration would make the typeclass a little more object-oriented, and there’s nothing wrong with that, but for now let’s stick to the original idea. We’re providing the implementation for a type, not for an instance.

When I grow up I wanna be a typeclass!

Once we’ve defined what we expect, it’d be nice to provide some actual implementations for chosen types. This way we’d be able to use the behavior. Let’s choose two simple types to work with: strings and integers. In Haskell, the implementation is provided by defining the concrete typeclass instance:

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}
    
instance Ceasarable String where
    toCeasar x = [toEnum $ fromEnum c + 3 | c <- x]
    
instance Ceasarable Integer where
    toCeasar x = [toEnum $ fromEnum c + 3 | c <- show x]

Keyword instance means that the implementation is coming. For String, we map over characters, get their ASCII numbers with fromEnum, add three and than encode again with toEnum. For Integer we just express it as String using show and we do exactly the same.

In Scala things get a little weird, so feel free to skip over the details. The Ceasarable behavior is enclosed in the object and marked as implicit. This way it can be implicitly passed to the place we want to use it:

object Ceasarable {
    implicit object CeasarableInt extends Ceasarable[Int] {
        override def toCeasar(input: Int): String = {
            s"$input".map(_ + 3).map(_.toChar).mkString
        }
    }
   
    implicit object CeasarableString extends Ceasarable[String] {
        override def toCeasar(input: String): String = {
            input.map(_ + 3).map(_.toChar).mkString
        }
    }
}

The object scope and implicit passing are part of Scala peculiarities, no need to dive deeper in them. If you really want to, look here. What matters is that we’ve created separated objects with Ceasarable implementations for String and Int types and we enclosed them in static-like objects (object is as close as you can get to static in Scala). Those types know nothing about their ability to be expressed in Ceasar cipher.

Let’s try the same approach in Swift:

struct CeasarableInt : Ceasarable {
    typealias T = Int
    static func toCeasar(input: Int) -> String {
        return "(input)".unicodeScalars.reduce("") { 
            (acc, char) in
            return acc + String(UnicodeScalar(char.value + 3))
        }
    }
}

struct CeasarableString : Ceasarable {
    typealias T = String
    static func toCeasar(input: String) -> String {
        return input.unicodeScalars.reduce("") { 
            (acc, char) in
            return acc + String(UnicodeScalar(char.value + 3))
        }
    }
}

Looks valid. This way we’ve defined the ability to be encoded in Ceasar cipher for strings and integers in each language we consider.

Now we can work with Ceasarable objects just as with any other group of objects sharing common characteristics, i.e. type. We can declare that we expect it as function parameter, we can return it in a function result and so on. Let’s see the example usages. In Haskell:

encodeInCeasar :: (Ceasarable c) => c -> String
encodeInCeasar = toCeasar
    
encodeInCeasar 1234 -- "4567"
    
encodeInCeasar "ABCabc" -- "DEFdef"

We are using the typeclass just like we’d use the protocol – to define a contract without explicitly defining what object are gonna conform to this contract.

How about Scala?

def encodeInCeasar[T: Ceasarable](c: T) = {
    val encoded = implicitly[Ceasarable[T]].toCeasar(c)
    println(encoded)
}

encodeInCeasar(1234) // "4567"

    encodeInCeasar("ABCabc") // "DEFdef"

The sky, once again, gets a little bit cloudy. Instead of requiring the protocol confirmation, we’re explicitly asking for the proper implementation using implicitly. Implicitly needs to have the implementations passed inside the function, and the enclosing scope is passed via a mechanism called context bound. T: Ceasarable is a syntax for context bound. It might sound confusing, but it’s fine, actually. This way we can easily see that we’re using a typeclass. In Swift, however, we encounter a problem:

func encodeInCeasar<C : Ceasarable>(c: C.T) -> String {
    return C.toCeasar(c)
}

encodeInCeasar(c: 1234) // Compiler error: Cannot invoke 'encodeInCeasar' with an argument list of type '(Int)'

Swift compiler cannot infer the generic parameter. There is a struct that does exactly what we want: conforms to Ceasarable and defines Int as its associated type. However, it cannot be found automatically. Swift doesn’t have semantics for Scala-like context bound. However, we’ve got the second best thing… Wait! It’s actually the first best thing, only Swift is 2.0. Protocol extensions.

Swift typeclasses defined with protocol extensions

In Swift we can use the extension keyword to provide implementations for already existing types. The beauty of extension lays in its two properties: universality and ability to be constraint. By universality I mean that you can extend all the Swift types: protocols, classes, structs and enums. The ability to be constraint let us express what we want to extend in a great detail – greater than allowed by protocol confirmation or class inheritance alone.

Did I mention that if you’ve watched “Protocol-Oriented Programming in Swift” you’ll feel at home? Our better implementation of typeclasses starts with a slight change to the Ceasarable definition:

protocol Ceasarable {
        static func toCeasar(input: Self) -> String
}

Instead of requiring the associated type in protocol, we can add a Self requirement. This way we’re expressing that for whatever type we’re providing the typeclass implementation, it requires the value of that type as the parameter. It stays closer to the original Haskell definition, because the typeclass doesn’t need to be generic. It is just like a template for multiple function definitions that differ only by the type in signature. Self expresses exactly that. There is also another way of expressing the same idea: see this article on how to do it using Swift 1.2 (spoiler alert: <C: Ceasarable where C.T == C>), but for Swift 2.0 the most straightforward way is with Self. The actual implementations become easier to write and more readable:

extension Int : Ceasarable {
    static func toCeasar(input: Int) -> String {
        return "(input)".unicodeScalars.reduce("") { 
            (acc, char) in
            return acc + String(UnicodeScalar(char.value + 3))
        }
    }
}

extension String : Ceasarable {
    static func toCeasar(input: String) -> String {
        return input.unicodeScalars.reduce("") { 
            (acc, char) in
            return acc + String(UnicodeScalar(char.value + 3))
        }
    }
}

It looks like a straightforward protocol confirmation and it’s just what we need. Having that, the usage get simpler as well:

func encodeInCeasar<T : Ceasarable>(c: T) -> String {
    return T.toCeasar(c)
}

encodeInCeasar(1234) // "4567"

encodeInCeasar("ABCabc") // "DEFdef"

This is what we tried to achieve. At the same time we’re providing behavior separate from data (since it’s static method of T) and expressing the common functionality (since T must be Ceasarable). By using protocol extensions, we’ve enabled the second dimension, somewhat orthogonal to inheritance, in which we can compose our functionalities.

What are Swift typeclasses, then?

A typeclass in Swift is a pattern build using the protocols and extensions. It’s simple and there’s nothing new, really, as we’ve been already using those concepts extensively. As a side note, the process of learning functional programming is very often like that: concepts we used for a long time, but differently named, generalized and ready to build upon.

Typeclasses are a way of providing a behavior for the type separately from the type and at the same time defining a contract that the type conforms to. It might be used to add functionalities and build composition without inheritance.

You May Also Like

Super Confitura Man

How Super Confitura Man came to be :)

Recently at TouK we had a one-day hackathon. There was no main theme for it, you just could post a project idea, gather people around it and hack on that idea for a whole day - drinks and pizza included.

My main idea was to create something that could be fun to build and be useful somehow to others. I’d figured out that since Confitura was just around a corner I could make a game, that would be playable at TouK’s booth at the conference venue. This idea seemed good enough to attract Rafał Nowak @RNowak3 and Marcin Jasion @marcinjasion - two TouK employees, that with me formed a team for the hackathon.

Confitura 01

The initial plan was to develop a simple mario-style game, with preceduraly generated levels, random collectible items and enemies. One of the ideas was to introduce Confitura Man as the main character, but due to time constraints, this fall through. We’ve decided to just choose a random available sprite for a character - hence the onion man :)

Confitura 02

How the game is played?

Since we wanted to have a scoreboard and have unique users, we’ve printed out QR codes. A person that would like to play the game could pick up a QR code, show it against a camera attached to the play booth. The start page scanned the QR code and launched the game with username read from paper code.

The rest of the game was playable with gamepad or keyboard.

Confitura game screen

Technicalities

Writing a game takes a lot of time and effort. We wanted to deliver, so we’ve decided to spend some time in the days before the hackathon just to bootstrap the technology stack of our enterprise.

We’ve decided that the game would be written in some Javascript based engine, with Google Chrome as a web platform. There are a lot of HTML5 game engines - list of html5 game engines and you could easily create a game with each and every of them. We’ve decided to use Phaser IO which handles a lot of difficult, game-related stuff on its own. So, we didn’t have to worry about physics, loading and storing assets, animations, object collisions, controls input/output. Go see for yourself, it is really nice and easy to use.

Scoreboard would be a rip-off from JIRA Survivor with stats being served from some web server app. To make things harder, the backend server was written in Clojure. With no experience in that language in the team, it was a bit risky, but the tasks of the server were trivial, so if all that clojure effort failed, it could be rewritten in something we know.

Statistics

During the whole Confitura day there were 69 unique players (69 QR codes were used), and 1237 games were played. The final score looked like this:

  1. Barister Lingerie 158 - 1450 points
  2. Boilerdang Custardbath 386 - 1060 points
  3. Benadryl Clarytin 306 - 870 points

And the obligatory scoreboard screenshot:

Confitura 03

Obstacles

The game, being created in just one day, had to have problems :) It wasn’t play tested enough, there were some rough edges. During the day we had to make a few fixes:

  • the server did not respect the highest score by specific user, it was just overwritting a user’s score with it’s latest one,
  • there was one feature not supported on keyboard, that was available on gamepad - turbo button
  • server was opening a database connection each time it got a request, so after around 5 minutes it would exhaust open file limit for MongoDB (backend database), this was easily fixed - thou the fix is a bit hackish :)

These were easily identified and fixed. Unfortunately there were issues that we were unable to fix while the event was on:

  • google chrome kept asking for the permission to use webcam - this was very annoying, and all the info found on the web did not work - StackOverflow thread
  • it was hard to start the game with QR code - either the codes were too small, or the lighting around that area was inappropriate - I think this issue could be fixed by printing larger codes,

Technology evaluation

All in all we were pretty happy with the chosen stack. Phaser was easy to use and left us with just the fun parts of the game creation process. Finding the right graphics with appropriate licensing was rather hard. We didn’t have enough time to polish all the visual aspects of the game before Confitura.

Writing a server in clojure was the most challenging part, with all the new syntax and new libraries. There were tasks, trivial in java/scala, but hard in Clojure - at least for a whimpy beginners :) Nevertheless Clojure seems like a really handy tool and I’d like to dive deeper into its ecosystem.

Source code

All of the sources for the game can be found here TouK/confitura-man.

The repository is split into two parts:

  • game - HTML5 game
  • server - clojure based backend server

To run the server you need to have a local MongoDB installation. Than in server’s directory run: $ lein ring server-headless This will start a server on http://localhost:3000

To run the game you need to install dependencies with bower and than run $ grunt from game’s directory.

To launch the QR reading part of the game, you enter http://localhost:9000/start.html. After scanning the code you’ll be redirected to http://localhost:9000/index.html - and the game starts.

Conclusion

Summing up, it was a great experience creating the game. It was fun to watch people playing the game. And even with all those glitches and stupid graphics, there were people vigorously playing it, which was awesome.

Thanks to Rafał and Michał for great coding experience, and thanks to all the players of our stupid little game. If you’d like to ask me about anything - feel free to contact me by mail or twitter @zygm0nt

Recently at TouK we had a one-day hackathon. There was no main theme for it, you just could post a project idea, gather people around it and hack on that idea for a whole day - drinks and pizza included.

My main idea was to create something that could be fun to build and be useful somehow to others. I’d figured out that since Confitura was just around a corner I could make a game, that would be playable at TouK’s booth at the conference venue. This idea seemed good enough to attract >Conclusion

JBoss Envers and Spring transaction managers

I've stumbled upon a bug with my configuration for JBoss Envers today, despite having integration tests all over the application. I have to admit, it casted a dark shadow of doubt about the value of all the tests for a moment. I've been practicing TDD since 2005, and frankly speaking, I should have been smarter than that.

My fault was simple. I've started using Envers the right way, with exploratory tests and a prototype. Then I've deleted the prototype and created some integration tests using in-memory H2 that looked more or less like this example:

@Test
public void savingAndUpdatingPersonShouldCreateTwoHistoricalVersions() {
    //given
    Person person = createAndSavePerson();
    String oldFirstName = person.getFirstName();
    String newFirstName = oldFirstName + "NEW";

    //when
    updatePersonWithNewName(person, newFirstName);

    //then
    verifyTwoHistoricalVersionsWereSaved(oldFirstName, newFirstName);
}

private Person createAndSavePerson() {
    Transaction transaction = session.beginTransaction();
    Person person = PersonFactory.createPerson();
    session.save(person);
    transaction.commit();
    return person;
}    

private void updatePersonWithNewName(Person person, String newName) {
    Transaction transaction = session.beginTransaction();
    person.setFirstName(newName);
    session.update(person);
    transaction.commit();
}

private void verifyTwoHistoricalVersionsWereSaved(String oldFirstName, String newFirstName) {
    List<Object[]> personRevisions = getPersonRevisions();
    assertEquals(2, personRevisions.size());
    assertEquals(oldFirstName, ((Person)personRevisions.get(0)[0]).getFirstName());
    assertEquals(newFirstName, ((Person)personRevisions.get(1)[0]).getFirstName());
}

private List<Object[]> getPersonRevisions() {
    Transaction transaction = session.beginTransaction();
    AuditReader auditReader = AuditReaderFactory.get(session);
    List<Object[]> personRevisions = auditReader.createQuery()
            .forRevisionsOfEntity(Person.class, false, true)
            .getResultList();
    transaction.commit();
    return personRevisions;
}

Because Envers inserts audit data when the transaction is commited (in a new temporary session), I thought I have to create and commit the transaction manually. And that is true to some point.

My fault was that I didn't have an end-to-end integration/acceptance test, that would call to entry point of the application (in this case a service which is called by GWT via RPC), because then I'd notice, that the Spring @Transactional annotation, and calling transaction.commit() are two, very different things.

Spring @Transactional annotation will use a transaction manager configured for the application. Envers on the other hand is used by subscribing a listener to hibernate's SessionFactory like this:

<bean id="sessionFactory" class="org.springframework.orm.hibernate3.annotation.AnnotationSessionFactoryBean" >        
...
 <property name="eventListeners">
     <map key-type="java.lang.String" value-type="org.hibernate.event.EventListeners">
         <entry key="post-insert" value-ref="auditEventListener"/>
         <entry key="post-update" value-ref="auditEventListener"/>
         <entry key="post-delete" value-ref="auditEventListener"/>
         <entry key="pre-collection-update" value-ref="auditEventListener"/>
         <entry key="pre-collection-remove" value-ref="auditEventListener"/>
         <entry key="post-collection-recreate" value-ref="auditEventListener"/>
     </map>
 </property>
</bean>

<bean id="auditEventListener" class="org.hibernate.envers.event.AuditEventListener" />

Envers creates and collects something called AuditWorkUnits whenever you update/delete/insert audited entities, but audit tables are not populated until something calls AuditProcess.beforeCompletion, which makes sense. If you are using org.hibernate.transaction.JDBCTransaction manually, this is called on commit() when notifying all subscribed javax.transaction.Synchronization objects (and enver's AuditProcess is one of them).

The problem was, that I used a wrong transaction manager.

<bean id="transactionManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager" >
    <property name="dataSource" ref="dataSource"/>
</bean>

This transaction manager doesn't know anything about hibernate and doesn't use org.hibernate.transaction.JDBCTransaction. While Synchronization is an interface from javax.transaction package, DataSourceTransactionManager doesn't use it (maybe because of simplicity, I didn't dig deep enough in org.springframework.jdbc.datasource), and thus Envers works fine except not pushing the data to the database.

Which is the whole point of using Envers.

Use right tools for the task, they say. The whole problem is solved by using a transaction manager that is well aware of hibernate underneath.

<bean id="transactionManager" class="org.springframework.orm.hibernate3.HibernateTransactionManager" >
    <property name="sessionFactory" ref="sessionFactory"/>
</bean>

Lesson learned: always make sure your acceptance tests are testing the right thing. If there is a doubt about the value of your tests, you just don't have enough of them,