Understanding Practical API Design, Static Typing and Functional Programming

…and how a marriage to a particular programming language is only indirectly and barely relevant

I was really tempted to title this post, “What to Solve Before Expecting Me to Take Your Opinions of Static Typing Seriously”, however, I figured this would be a bit too controversial and might detract from the points I wish to make. Nevertheless, I just want to make note, I think it is a very appropriate title.

The reason I think it’s a very appropriate title, is because of certain events that have happened recently. I teach advanced programming techniques to programmers. I do this voluntarily for the most part, and I occasionally deliver guest lectures to universities and other sporadic occurrences. I also teach at my place of employment, where I use these techniques for product development. I used to do university lecturing, until I came to the conclusion that the tertiary institution is in direct contention with the goal of education; the latter of which is important to me.

I have constructed the course material myself, predicting what would be useful, too difficult or too easy and so on and revising over time as these predictions fell out of place. Recently I set a task, predicted how difficult it would be, then was astonished to find that it appears to be significantly more difficult than I had originally predicted. I’m still not sure what is going on here, however, I think there are some lessons to be taken. One of which is a lesson about approaches to teaching advanced concepts of programming — something I am constantly learning about (and yearning for more solid research and experimental results!).

I asked students to write an API for the game tic-tac-toe. No need for the computer to tactically play tic-tac-toe — just an API that you can use to model the game itself. You can use any programming language you like, however, I think you will find certain environments to be lacking in the available tools, so I will guide you so that you’re not off somewhere “shaving yaks” so to speak.

If I’d left the requirement there, I can predict what I would have ended up with. Probably something similar to the API that I used to support at L3 for IBM where the number of bugs coming in was at a rate faster than I could fix them — and we don’t want that. Worse still, every time I fixed one bug gave rise to several new ones, no matter what I did! The whole point of this exercise is to avoid this scenario, once and for all, and without all that nonsense that gives false promise to deliver on this objective (Agile, XP, Scrum and all that silliness).

So I set some rules, but without further explanation of why these rules existed:

  • If you write a function, I must be able to call it with the same arguments and always get the same results, forever.
  • If I, as a client of your API, call one of your functions, I should always get a sensible result. Not null or an exception or other backdoors that cause the death of millions of kittens worldwide.
  • If I call move on a tic-tac-toe board, but the game has finished, I should get a compile-time type-error. In other words, calling move on inappropriate game states (i.e. move doesn’t make sense) is disallowed by the types.
  • If I call takeMoveBack on a tic-tac-toe board, but no moves have yet been made, I get a compile-time type-error.
  • If I call whoWonOrDraw on a tic-tac-toe board, but the game hasn’t yet finished, I get a compile-time type-error.
  • I should be able to call various functions on a game board that is in any state of play e.g. isPositionOccupied works for in-play and completed games.
  • It is not possible to play out of turn.

Now, why these rules? Well, because if you can achieve the goal of enforcing these rules, then the next phone call that I get in L3 support from an upset client, I can be guaranteed that one of the following are true:

  • I have a bug in my code, in which case, the sooner the call, the better! …unless of course, fixing the bug results in only more bugs — but we have avoided that possibility — hopefully you can see why.
  • The client has misused the API and circumvented the type system. The client has used null, thrown an exception or performed a side-effect within the API or perhaps even used such things as Java reflection or even type-casting or type-casing. Unfortunately, in some environments, there’s not much I can do about enforcing that except impose a de facto rule where you assume non-existence of these possibilities (Just don’t do that!). Hopefully you haven’t yet jumped to the conclusion that any of these things are necessary or even useful — they aren’t.
  • The client is simply mistaken about the merits of their complaint.

That’s it. There is nothing more to add to the list. Importantly, this list is significantly shorter than the list that I once had when supporting a typical Java application in IBM L3 support. How did I achieve this narrow list of possibilities before the phone even rang?

I have actually solved this problem using various programming languages:

  • Haskell
  • Scala
  • C#
  • Java

In order to take the emphasis off programming-language-centric issues, I will focus now on the Java solution (the most challenging environment in which to achieve the goal) and then I am going to invite you to conduct a thought experiment.

Let’s take a look at the javadoc for the Java solution. Ignore the Main class for now, which simply gives you a 2-player console application that uses the API (feel free to run it!) — it depends on the rest of the API and so could be deleted without breaking anything.

If I asked you to be the most malicious user you can be, so long as you followed the rules (which I will assume you have done from here on), I want you to get an instance of the FinishedBoard class. If you rang me up in L3 support, even hiding your malicious intent from me, and said you had such an instance, then I am absolutely guaranteed that you obtained that instance by playing a legitimate game of tic-tac-toe and ended up with a game that is in the position of a player winning or a draw. Consider the implications of this for a moment.

For another example, suppose you rang and said that you called the move function and when you ran it, something-or-rather happened at run-time, I can be guaranteed that you called that function on a game that was in-play and so had the ability to move, since otherwise it would not have compiled, let alone run.

There are many more examples of these types of guarantees — invariants that I am certain have been met before I even start listening to you on the phone. I think this is an enormous advantage to real-world software tasks, don’t you? And all this done with Java and its overwhelmingly impractical type system. How about that!?

Now, producing an API of this nature seems to be more difficult for programmers than I originally predicted. Why is this? I can only conjecture and given my already-disproportionate prediction, I am hesitant to do so. Nevertheless, what you are looking at is an extremely robust API for a relatively trivial problem. This API robustness was achieved by exploiting techniques available from static typing and functional programming.

So let’s summarise. A robust API for a trivial game was written using several programming languages in such a way that appears to be difficult for many programmers to reproduce and using techniques such as exploiting static typing and functional programming. This was even done with a popular programming language that is not particularly amenable to achieving this degree of robustness.

In other words, many programmers have difficulty solving a trivial problem using techniques that many programmers are compelled to offer their comment on — no wonder there is a lot of outrageous hype! On the topic of why I expect you to be able to solve this problem before I take you seriously — it’s not because I have high standards, they’re incredibly low — it’s just that while these standards are very low, they are rarely satisfied. This is not a high-horse-motivated rant (as many insecure people might hastily conclude), the point I am making here is that I think it’s important to set standards of scepticism — maybe you should too!

It’s not just support issues where you will see an advantage to this programming technique. You might be writing an API for the guy sitting next to you. Those types are machine-checked documentation — he won’t have to keep bothering you about which function to call when — it’s obvious, since it’s specified in the type! You might even be your own client — suppose you hit a bug in your own code — you can rule out a huge number of possibilities of where that bug is, before you even start looking for it.

All these advantages of robust API design for less expense than the contrary and yet robust API design seems to be overwhelmingly rare. I am left only with questions, aren’t you? Come on guys, we can do a whole lot better. It’s an invitation!

It’s possible to take this particular API problem further using a language such as Agda or Coq and enforce the invariant that it’s not possible to make a move to a position on a board if that position has already been moved to. I know of one person who is attempting to achieve this. Godspeed.

I haven’t shown you the source to any of these solutions because I figure you might want to take a crack at it yourself. Give it a go! If you really want the source let me know and I’ll send you a link.

Hopefully this helps!

70 Responses to “Understanding Practical API Design, Static Typing and Functional Programming”

  1. Jonathan Says:

    Those are good rules and a very nice API.

    My only small gripe is the API of (say) MoveResult seems a bit cryptic to someone unfamiliar with FunctionalJava. Maybe in Scala it would be simpler.

    FWIW I would have dispensed with BoardLike and merged it into Board instead, unless there’s some objection. And I’d have simply named the inner classes Board.Finished and Board.Empty. I find myself doing that a lot, e.g. MyList with subclasses MyList.Mutable and MyList.Immutable.

  2. Hossam Karim Says:

    When you say:
    If you write a function, I must be able to call it with the same arguments and always get the same results, forever
    You literally mean a “function” not a “method”, is that correct?

  3. Tony Morris Says:

    Jonathan,
    MoveResult is a church-encoding of an algebraic data type, which Java does not have. It is only as “cryptic” as it should be and no more. Even in Scala and sometimes Haskell, I encode the data type like this, since it is *easier to read*. Board is not the only instance of BoardLike. Names don’t mean very much to me.

    Hossam,
    I literally mean a function, in that it returns the same result for its given arguments. I don’t care about how you model this in the language.

  4. Kav Latiolais Says:

    Excellent insight. Alas even at Major software companies we have a lot of trouble with this. I always thought it was due to the amazingly long cycle between API creation and customer bug reporting but it sounds like it’s a fundamental educational issue to some extent.

    Thanks for writing it up,
    Kav

  5. Jonathan Says:

    > Board is not the only instance of BoardLike.

    Unless I’m missing something, is there any need for the distinction between Board and BoardLike? Can’t it all go in an abstract Board class (though no doubt with some concrete methods and fields) with (Board)Finished and (Board)Empty as the only subclasses?

  6. Chris Heller Says:

    Interesting restrictions, interesting results.

    As someone who sees the elegance in your result, but would likely have some difficulty reproducing the results, what areas of study would you suggest to pursue in order to improve my ability to produce APIs like this?

  7. Tony Morris Says:

    Hi Jonathan, the Board class has a move method. It’s important that a (Board)Finished does not have this method, so subclassing will not work. It’s great to see you work through these issues in your mind :) Hope these sort of exercise are helpful for you!

  8. Tony Morris Says:

    Hi Chris,
    In my time teaching these sort of techniques, I have found it very difficult to simply pile a bunch of articles on a person and expect a useful result. Instead, I recommend practice, coupled with knowledge acquisition and doing this iteratively. For example, you might set yourself a similar goal and model say, the game of chess. In doing so, you will likely hit some barriers then ask how to best overcome them — this is when you will likely have to read about some concept or something. However, it is very common for there to be a disconnection between this concept and how it will help a student overcome the barrier. In times like these, I use several methods of explanation that will help the student to make this connection in such a way that they feel confident in exploiting it. It’s very tough for me to hand you a bunch of keywords and expect you to be able to head off on your own and learn it all for yourself. Nevertheless, I have seen this happen on one or two occasions!

    The key techniques here that were exploited are static typing and software correctness verification in general, which is an incredibly deep topic and also widely misunderstood (and you are surely aware that this doesn’t stop the proliferation of opinion!) and the functional programming thesis.

    In terms of understanding static typing, there are some “easy bite-offs” so to speak — topics that you may read and learn about, probably understand quite easily and have a good return on this investment of effort. However, I do not have a “formula” that I can confidently give you to help you understand the topic more deeply. Such topics as the Curry-Howard Isomorphism and perhaps the Free Theorems (Wadler) paper are great places to start, since even if you were just a casual programmer (and not an interested one like you are), these would still be beneficial.

    As for learning functional programming and why it is important, I recommend, in this order of high to low importance: practice, become very sceptical of the vast amounts of misinformation that may throw you off-track, Why Functional Programming Matters (Hughes), The Essence of Functional Programming (Wadler).

    I have also given a presentation about learning functional programming, but I don’t think it was video-recorded (can anyone find a recording? I can’t). Here are the slides:

    http://projects.tmorris.net/public/how-to-learn-fp/artifacts/0.1/chunk-html/index.html
    http://projects.tmorris.net/public/what-does-fp-mean/artifacts/0.4/chunk-html/index.html

    Also, I’m happy to answer any questions you might have on your learning journey. I can also refer you to others who can help answer questions too — some people have different approaches to teaching these topics that can be complementary and helpful to various students.

    Good luck!

  9. Pedro Says:

    Hi,

    I did not understand yet how to get a FinishedBoard.

    Starting from,

    EmptyBoard a = Board.EmptyBoard.empty()
    Board b = a.move(E)
    MoveResult r = b.move()

    I have no idea how to proceed.

  10. Tony Morris Says:

    Hi Pedro, Once you have a MoveResult, you might a FinishedBoard, but you also might not. This is determined by which function is called as the argument when you call MoveResult.fold.

  11. Pedro Says:

    Ah! So is the fold just a replacement for pattern matching?

  12. Tony Morris Says:

    Pedro, Precisely.

    You are probably familiar with scala.Option. It can be rewritten like so:

    trait Option[A] {
      def fold[X](none: => X, some: A => X): X
    }
    

    This data structure is exactly equivalent (isomorphic) to scala.Option

  13. Adam Webber Says:

    Hi Tony,

    Thanks for the thought provoking post.

    I have been trying to move to a more fp style in the code I write, but this application of compile-time type-errors to what is seemingly run-time state change (urgh, state!) is an eye opener.

    MoveResult.Fold seems to be the key, I’ve gone away and read about Scala.Option, but was hoping you could expand on exactly how this method operates?

    - Are we passing in a predicate and two functions, if the predicate is true we execute (or return?) the first function, false we execute (or return?) the second function?

    I’m going to try and write a c# version, could you post a link to source in a few days? :)

    Cheers,

    Adam Webber

  14. bapt Says:

    Hi,

    thanks for this post, this is really interesting. I am also interested in a C# solution and would be happy to see the source in some days.

  15. Tony Morris Says:

    Hi Adam,
    You might think of the MoveResult.fold function as a switch that can act on arguments. One of those functions will be executed to produce a result — which one is executed depends on what the result of the move actually is. If you are familiar with algebraic data types (as in Haskell, ML or Scala), there is another explanation regarding switch between the church encoding of that type and the type itself.

  16. Joel Says:

    Thank you Tony for the best sales pitch I have ever seen for functional programming. I believe that these are exactly the points needed to be made to make some IT department, lost in the alternate reality of “object orientation” and “software development methodologies”, aware of the benefits of correct methods.

    To trick the object oriented mind into understanding your MoveResult class you could let the catamorphism masquerade as a visitor:
    public interface MoveResultVisitor {
    public X positionAlreadyOccupied();
    public X keepPlaying(Board board);
    public X gameOver(Board.FinishedBoard board);
    }

    Cheers,
    Joel

  17. Michael Says:

    Hi Tony

    Thank you for the interesting exercise !
    If the MoveResult.fold function is a switch, can we use pattern matching instead if we use Scala ?

    For example: moveResult.board match { case b:Board => keepPlaying(b); case bf:Board.Finished => finishGame(bf) }

    Does it make sense ?

  18. Tony Morris Says:

    Hi Joel,
    Thanks for the feedback.

    Your visitor will not work because it is conjunctive rather than disjunctive. Remember that MoveResult denotes one (and only one) of a position already occupied, keep playing with a board or game over with a finished board.

    Otherwise yes, the visitor pattern is just a fancy name for what is essentially (without the useless ceremony) catamorphism. Most design patterns are quite silly like this,

  19. Tony Morris Says:

    Michael, yes it certainly does make sense. However, you shouldn’t be type-casing in your pattern-match. Rather you should be delineating with your own type (as in MoveResult) with multiple constructors. It is unfortunate that Scala permits type-casing like this.

  20. Michael Says:

    Tony, thanks ! Can you help to get rid of type-casting in my example with the Scala pattern matching ?

  21. Tom Says:

    Is the actual implementation of the Java available? I think I understand what’s going on, but I want to check. In particular I want to answer the question: “Are keepPlaying, keepPlayingOr and tryMove just utility functions?”.

  22. Joel Says:

    Hi Tony,

    The generic parameter was lost in translation:

    public interface MoveResultVisitor<X> {
        public X positionAlreadyOccupied();
        public X keepPlaying(Board board);
        public X gameOver(Board.FinishedBoard board);
    }

    The visitor is equivalent to
    P3<X, F<Board,X>, F<Board.FinishedBoard,X>>
    Implementing the visitor pattern would be a matter of simply changing the type of MoveResult.fold to
    public abstract <X> X fold(MoveResultVisitor<X> visitor);

    I can see one reason not to do that though: The visitor pattern as preached by GoF relies on mutable state and to a FP newbie this may seem like an invitation to keep up the bad work.

  23. Tony Morris Says:

    Tom,
    Here is the Java source https://bitbucket.org/dibblego/haskell-course/src/57a00f8bebda/TicTacToe/java/src/tictactoe/

    I don’t know if you would call those functions, utility functions.

  24. Steve Says:

    Is this pro-functional, anti-object-oriented, or both? Or neither? I ask because the premise of Scala - which you mention having an implementation of this in - is that OO and FP are complimentary.

    As I think about it, I think that this post illustrates that FP is a mindset, not a language feature. You can do functional in just about any language. I suppose that’s the only way for it to make sense that you didn’t go into your Haskell and Scala implementations. I presume that many would have read such a thing as a anti-Java/pro-Scala rant and the world isn’t exactly lacking for those.

    Anyway, very interesting and thought provoking.

  25. Tony Morris Says:

    Steve,
    It is neither, they are not in contention, nor are they dichotomous. What you refer to as the premise of Scala, is not the premise of Scala, but the stated premise of Scala. That stated premise of Scala is, in my opinion, total rubbish, and a useless distraction at best.

    Functional Programming is not a mindset — it’s a thesis. This thesis exists independently to all of our minds. However, Functional Programming is not a dichotomy, rather a continuum, and yes, all languages allow you to adhere to this thesis to some extent, along that continuum. Java is one of those — moreover, it is a language that explicitly goes out of its way to make adherence to this thesis extremely difficult, so raises the question of just how far you can take it. Nevertheless, it can be overcome to a greater extent than I predicted when we wrote Functional Java.

    I am writing Scala at this moment for work. In the kindest words, I am not feeling particularly “pro-Scala” at the moment. I use lots of languages. Stop marrying them and open your mind.

    If I was to write a “anti-Java” rant, I’d fucking destroy it.

  26. Joe Says:

    Tony,
    I’ve just came across your site as I’m starting to learn fp (learning w/ scala) and I’m really impressed with the quality and intellectual level of the posts you write. I’m always of the opinion software devs can aim higher and I completely agree with you on that. I look forward to more articles and more witty jabs and sarcasm. Thanks

  27. Jo Says:

    Tony,

    Funny to hear you exhort people to “open their mind” when according to you, except for Haskell, any programming language is a useless pile of garbage.

  28. Tony Morris Says:

    Jo, Opening your mind will prevent you from creating then attacking straw man positions. You should try it. It’s way more exciting than your dull sarcasm. Promise.

  29. GBH Says:

    Uhh, so you return a union type? This is not a difficult problem, but the way you explain it makes it seem like it is…

  30. Tony Morris Says:

    GBH, I didn’t say anything about the difficulty, except to the extent that some people find it difficult. In fact, I thought it was easier that it seems to have turned out to be.

  31. Mark Wotton Says:

    A ten minute exercise in Haskell.
    My day job is Ruby: I have _no_ idea how I’d enforce those constraints. Maybe a preprocessor, so you can scrounge a compile-time step? Freedom is slavery…

  32. Kamil Says:

    “If call move on a tic-tac-toe board, but the game has finished, I should get a compile-time type-error.”

    Your Java solution lacks any of the “compile time” guarantees you listed. I do believe it can be done in Haskell or other language with advanced type system, seeing it Java would be impressive though.

    Programmers do think of proofs writing code, encoding them in type systems is not necessary. It would be nice if the machine checked the proof, but encoding proofs in type systems is a lot of effort for little gain. Perhaps the cost is worth when working on mission critical software, say some primary space shuttle systems. Static type system are a mid point between no verification at all and full blown theorem prover. They provide some guarantees imposing minimum hassle on the user.

  33. Tony Morris Says:

    Kamil,
    No, the Java solution provides exactly those guarantees. This is a fact that is easy to disprove were it not to be true. Luckily, it is true, so you won’t be able to disprove it. Perhaps you mean, “the Java solution to the extent that my imagination can conceive”, not the API solution that was given.

    There is no cost to writing an API properly. There are people attempting this problem using theorem provers, such as Coq and Agda.

    PS: You don’t know what a static type system is. I recommend changing this.

  34. Eric Says:

    Interesting post. Will you post the Haskell code as well? It would be very interesting for comparison.

  35. Martin Says:

    Thanks for the excellent post! My Java understanding is not quite good enough to grasp exactly what that fold is doing, but just seeing that an API like this is possible in Java is amazing. Can you sketch how the Haskell solution would look like? Would that require GADTs?

  36. Matthew Lesko Says:

    For me at least, I unit tests demonstrating client API usage would be instructive.

  37. Kamil Says:

    Tony,

    “If I call move on a tic-tac-toe board, but the game has finished, I should get a compile-time type-error.”

    Here is a counter example. I break the Board.moveTo method so that it alway returns MoveResult.keepPlaing. After a couple of moves it is bound to get to a finishing state, where no moves are possible but the system will attempt to because I introduced a bug. The type system is happy despite the code being wrong. There is no compile-time type-error.

    I hope you see that you did not achieve static verification of that property. You can convince yourself of the correctness of the code by doing proofs in your head, but you did not encode them into the type system.

  38. Keith Braithwaite Says:

    Dammit, should know better than to post from an iPhone in a hurry at the airport. Try again…

    I’d be interested to see your approach applied to what I’d call the “distributed calendar” problem: I have a variable number if colleagues, each of us in a different location with unreliable network access. At any time I can grant or revoke permission to any of them to schedule a meeting with me. Those with permission can request a meeting at any time and I can accept or reject that request. If I accept the request the meeting is added to my calendar and theirs. I am automatically notified of an imminent meeting a number of minutes before the meeting, a number which I can choose, and change at any time before the meeting. My calendar always shows my meeting schedule using the timezone of my current location.

    I am genuinely interested to see the advantages of your approach when applied to a “software engineering” problem like this, as opposed to a ”computer science homework” problem.

  39. Andrew Gwozdziewycz Says:

    Kamil,

    Assuming the API is written bug free, which is the assumption he’s making to ensure that these properties hold, a consumer of the API *would* get a compile-time error if he/she misused it. That’s the guarantee he’s after, and that’s the guarantee that’s desirable when writing a public API.

  40. Tony Morris Says:

    Kamil,
    You are missing the point. On the assumption that you do not have access to the code, which you do not, then yes this property holds — I just haven’t proven that property. I’m quite certain I stated this above.

    To restate, I could give you this API and you would be forced to accept these code properties. It is as possible to do this in Java as it is in Haskell, so regardless of your misunderstanding, whichever way you decide to look at it (including the way you currently are, which is beside the point), you cannot say there is a difference between Haskell and Java.

    If I gave you the library, and asked you to give me the chain of function calls that breaks the invariant, then you win a prize. I am very very confident that you are unable to do this.

    I hope this is clear.

  41. Tony Morris Says:

    Keith,
    There is nothing about this problem that makes it not a “software engineering” and “computer science homework.” I expect this false dichotomy makes it difficult for you to see that you can apply the exact same techniques, because it is exactly the same problem-solving approach. Much of what you said about “notification” can be dismissed as trivial. If I understood the essence of your problem, rather than the trivial/irrelevant parts, maybe I could go further.

  42. Tony Morris Says:

    Here is the code https://bitbucket.org/dibblego/haskell-course/src/tip/TicTacToe/

  43. Keith Braithwaite Says:

    You can dismiss a problem as trivial, or you can show how trivial it is to solve. Only

  44. Keith Braithwaite Says:

    For one thing, the tic-tac-toe API doesn’t have to deal with any messy operational issues.

    The essence of my question is: how do you cost-effectively build a system out if pure functions when its semantics depend on handling multiple overlapping sequences of asynchronous requests made over unreliable channels?

  45. Tony Morris Says:

    Keith,
    When you say “messy operational issues”, what do you mean? Try to be precise here. You allude to I/O as if it somehow makes the problem more difficult — it doesn’t — quite the contrary. This is the entire point of this approach to programming. I don’t “dismiss it as trivial”, any more than you over-estimate the triviality.

    Indeed, the given tic-tac-toe API has a console application implemented just to demonstrate the outer layer — it’s not a stretch to imagine other forms of I/O. The point is that any I/O (whatever it may be) is clearly delineated from the algebraic representation of the problem at hand (which happens to be the hard bit). I could well have written a game server and so on — since I have this API very clear, then this outer layer will become extremely simple. There is no intertwining of the essence of the problem (representing a game API) with “messy operational issues.” Yes indeed, your given problem is very trivial.

    As soon as you let go of the idea that you have somehow made the problem more difficult by introducing “messy operational issues”, the sooner you will attain your desired insight.

  46. Luke Randall Says:

    Hi Tony

    Having just started out learning Haskell, I’d be interested in seeing the Haskell version.

  47. Keith Braithwaite Says:

    Tony,
    I don’t think I agree that implementing an algebra of meetings on calendars would help much with the distributed calendar problem. It takes away one seat of latent defects, true, but not the major one, I think.

    This problem isn’t about managing a priority queue correctly. It’s about correct temporal ordering of side-effects in the world in response to events in the world, some of which change the parameterization of the rules about that ordering, and about maintaining consistant state over many agents connected by an unreliable transport. Those are the hard parts.

    Separating what I would call the essential domain of the system from the interaction domains isn’t a new idea, and isn’t unique to statically-typed functional programming. It does mean that the interaction domains can be treated separately, true. But then what? How does statically-typed functional programming help us get those interaction domains right?

  48. Chris K Says:

    An window manager for an X11 system has many client and X11 calls to interweave correctly and a great deal of state to manage. The user may be typing and clicking and the applications will be issuing sizing requests and more. The XMonad program, written in Haskell, is a powerful window manager. Its code is slim but with many tests and is very solid because of static techniques.

  49. Tony Morris Says:

    Keith, The best way to manage those issues is with type-system level effect-tracking. I prefer Haskell’s, though there are others. I still don’t agree that it is all that difficult. I expect this is because I would insist on using effect-tracking before I considered solving it — anything else is just too impractical.

  50. Keith Braithwaite Says:

    Tony,
    Unfortunately, googling “haskell effect-tracking” leads to a tweet citing a stackoverflow answer…by yourself. What would be a (non-circular :) reference for this language feature?

  51. Tony Morris Says:

    Keith, try this:

    http://www.haskell.org/ghc/docs/latest/html/libraries/base-4.3.1.0/Prelude.html#t:IO

  52. Keith Braithwaite Says:

    Tony,
    I see. So your answer boils down to “use the IO Monad and it’ll be super easy”. OK then.

  53. Tony Morris Says:

    Keith,
    No not the IO monad. The monad implementation is irrelevant. I wish to emphasise this, since I see it a lot — totally, absolutely irrelevant — as relevant as any other arbitrary programming concept.

    Rather, use a type system that delineates between values of the type (#RealWorld -> (#RealWorld, t)) and t. It won’t be super-easy; it will be much easier than you are making it out to be.

  54. Colin Adams Says:

    Oh dear, oh dear, oh dear. I’m too old.

    I wish had read this article 8 1/2 years ago.

  55. Tony Morris Says:

    Colin, Why 8 1/2 specifically?

  56. JK Says:

    Tony, would you mind to provide an example of how to use this API for a full game? I still fail to see the right way to do so. As `fold` seems to be very important here, and is called internally AFAIK, are some methods like `MoveResult.gameOver` even meant to be called by the client?

  57. Tony Morris Says:

    JK,
    Here is a console application that uses the API https://bitbucket.org/dibblego/haskell-course/src/57a00f8bebda/TicTacToe/java/src/tictactoe/Main.java

    By the way, you use “fold” all the time — it’s just called something else and probably on a different algebraic data type. e.g. if/else is the fold for the boolean algebraic type.

  58. Andreas S. Says:

    Hi Tony!
    I started the exercise myself in java but I now wonder how painful that will be, so I may restart using scala. To put something useful into my wining post ( :D ) Here is a nice scala solution to this exercise including some explanations: http://vasilrem.com/blog/software-development/tic-tac-toe-api-with-phantom-types/

  59. Martin Says:

    Hi Tony!

    When I first read your blog, I was thinking, “How can one statically ensure something that will only be known at run time?”, and I still don’t quite get it. Your saying that your API will throw a compile-time error when one applies “move” to a board in a finished state. So shouldn’t I get a compile time error in a (Haskell) program like this:

    module Main where

    import Board
    import Position

    b1 = Position.NW –> empty
    Just b2 = keepPlaying $ Position.SW –> b1
    Just b3 = keepPlaying $ Position.N –> b2
    Just b4 = keepPlaying $ Position.S –> b3
    Just b5 = keepPlaying $ Position.NE –> b4
    Just b6 = keepPlaying $ Position.SE –> b5

    main = return ()

    Is your point mainly that in a good API, “–>” should lead to a “Either Board | FinishedBoard” kind of data type (in Haskell terms) instead of a “Board” type, so that one can use the more detailed type information for type checking?

  60. Tony Morris Says:

    Hello Martin, the answer to your final question is yes.

  61. Type safe data structures with “invalid” states | Dev Portal Says:

    [...] read the delightful article on a type safe tic-tac-toe API recently. It got me thinking how one might do this for an application with a complex GUI and data [...]

  62. Malvolio Says:

    The part I’m trying to wrap my head around (since your code seems to have disappeared) is this: in an imperative system, you’d have a board called the CurrentBoard. Each move would either (depending on the design) mutate that board or alternatively (more functionally) create a new board. But even if you chose the latter style, you would still have to update the CurrentBoard variable to point to the newly created board, a big FP no-no. In fact, as I understand it, the only FP no-no.

    And here’s the thing FP I don’t get: every system has state. Unlike functions, no (or nearly no) system exists solely to make calculations on its input. Every system I have ever worked on takes input, stores it for some time, and then later regurgitates it back in some form. I just don’t see how you do that just by composing referentially transparent functions. I asked the same question on StackOverflow; didn’t get a satisfactory answer.

  63. Tony Morris Says:

    Malvolio,
    I don’t use stackoverflow, since as you allude to, you receive answers that are worse than nothing and I agree in your case, you received precisely that. I’m happy to help of course — perhaps on IRC?

  64. Dénes Harmath Says:

    Your post excellently conveys the paradigm of FP and its practical benefits in developing robust software by showing a concrete example. However, I think it could be made more instructional:
    1. For FP newbies like me who don’t grok everything the first time, it would be great to see at least the usage of the API (e.g. the implementation of the Main class), or even better, more detailed JavaDocs or the implementation. Unfortunately, the link does not work. On github, I only find https://github.com/tonymorris/course/blob/master/TicTacToe/TicTacToe.md. Please provide us with a working link!
    2. I presume it is the point of your course, but could you show the “algorithm”, the patterns of designing such stateless APIs?
    Thank you very much!

  65. Tony Morris Says:

    Hi Dénes,
    Included in that link you gave is a usage of the API in Java, Scala and Haskell to implement a basic console–based interactive game. I apologise for the link not working — I changed its location.

    Here are some answers:
    https://github.com/tonymorris/course/tree/answers/TicTacToe

  66. Miguel Negrão Says:

    In the scala example, I don’t understand what is the inheritance: B => BoardLike in the gameloop function used for. It is only called twice with v=>v . Is it some type conversion trick ?

    thanks
    Miguel Negrão

  67. Tony Morris Says:

    Hi Miguel, Which code are you referring to exactly?

  68. Dominic Morneau Says:

    Interesting, thought-provoking post. I am wondering if it’s possible to provide such strong guarantees in most “real world” applications, though. Image processing is a big part of my work, and I can’t have a drawing function return a new copy on every call - that would be very slow. The usual solution would be to use a handle/pointer, which breaks this rule:

    » If you write a function, I must be able to call it with the same arguments and always get the same results, forever.

    In Haskell I think it would be possible to use a function ala `withMVar’ or `withFile’ and a monad to allow a user to do stuff like:

    withImage :: Image -> (ImagePtr -> IO ()) -> IO Image

    test :: Image -> IO Image

    test img = withImage img $ do drawCircle (0, 20) 5; drawLine (4,4) (8,8);

    But drawCircle and drawLine are still opaque. Using a data structure like difference lists also sounds impossible, since it would drastically affect performance (and prevent using optimized C libraries in the implementation). How is it possible to have a robust API under this kind of constraints?

  69. Just a Question Says:

    I wanted the Java source. The links are broken (even the last one).

    I would be delighted to know how can you produce a compiler error in Java for something that would be verified only in runtime. That’s what really got me.

  70. Glenview Jeff Says:

    The answers are here as of Feb 2012: https://github.com/tonymorris/course-answers/tree/master/src/TicTacToe/java/src/tictactoe

    Poke around the site for more implementations in other languages and other problems/solutions.

Leave a Reply