λ Tony’s blog λ

<<< Insert thoughtless commentary about Scala here. Be sure not to forget that emphatic display of spectacular ignorance of the subject at hand. Click here to solicit peer support in the event that you begin to consider the possibility that you do not understand elementary topics of computer programming. Keep that hyperbole hyperbolin’! >>>

I often hear people complain to me that they cannot use some superior programming language in their environment. Is it the right programming language to use? You sure? Great, now toughen up and use it.

You’re being told that you cannot? What is the reason given? Because “blah blah fucking said so blah blah.” There’s your problem — you subscribe to the illusion of authority and attribute it to the claimant. Abandon the illusion. No; actually abandon it to the extent of total non-existence. “Yeah but blah blah blah…” — I totally didn’t hear what you just said, intentionally. The consequences are not what you think they are.

“Oh but how come you get to use Haskell in your job?” Because I refuse to be bullied by fools proclaiming their authority with disregard for the common goal of getting the job done. Don’t give them the leverage — by way of believing it even exists — it doesn’t. I use whatever is appropriate and Haskell is often appropriate. It’s as simple as that.

HTFU and just do it properly. Unicorns do not exist. Deal with it accordingly. HTH.

Manuel M T Chakravarty — University of New South Wales

Brisbane Functional Programming Group

01 September 2011

Data Parallelism in Haskell from Rob Manthey on Vimeo.

A follow-on from Lifting. A port of the Scala code to Haskell follows.

class Lift f where
  lift0 ::
    a -> f a
 
  lift1 ::
    (a -> b) -> f a -> f b
  lift1 =
    ap . lift0
 
  lift2 ::
    (a -> b -> c) -> f a -> f b -> f c
  lift2 f =
    ap . lift1 f
 
  lift3 ::
    (a -> b -> c -> d) -> f a -> f b -> f c -> f d
  lift3 f a =
    ap . lift2 f a
 
  ap ::
    f (a -> b) -> f a -> f b
 
-- scala.List
instance Lift [] where
  lift0 =
    error "todo"
 
  ap = 
    error "todo"
 
-- scala.Option
instance Lift Maybe where
  lift0 =
    error "todo"
 
  ap = 
    error "todo"
 
-- scala.Either[R, _]
instance Lift (Either r) where
  lift0 =
    error "todo"
 
  ap = 
    error "todo"
 
-- scala.Functior1[R, _]
instance Lift ((->) r) where
  lift0 =
    error "todo"
 
  ap = 
    error "todo"

Java 7 has proposed syntax for what Scala calls two methods:

1. Option.flatMap
   In Scala where we would normally write:

   (a, b, c, d) => for {
     aa <- a(argsa)
     bb <- b(argsb)
     cc <- c(argsc)
     dd <- d(argsd)
   } yield f(aa, bb, cc, dd)

   While in Java we write:

   // ceremony in the absence of closures
   // has been omitted (and altered slightly) for brevity
   a(argsa)?.b(argsb)?.c(argsc)?.d(argsd).f();

   This syntax denotes the bind operation of Option monad, while Scala’s for-comprehension works for any monad. A pedantic point of note is that, from a particular perspective, Java’s syntax is slightly weaker than monad syntax, in that it is in fact, an applicative functor comprehension (not monad), since subsequent computations do not have access to previously computed values along the chain (if this is confuzzling, never mind — it’s important point otherwise, but not so much here). Scala’s for-comprehensions allow this, but it hasn’t been demonstrated above.

2. Option.getOrElse

Java calls this ?:, so while in Scala we might write value getOrElse k, or if you prefer Scalaz, value | k, in Java we’d write value ?: k. The Java version maintains the usual lack of safety of null, while Scala uses an algebraic data type.

Among many differences between Scala and Java here, one is that Scala does not introduce syntax for these two specific functions — after all, why would you? Further, what about the zillions of other useful functions? Java has no user-defined call-by-need unification, which means it is not possible to write ?: yourself (even with a different valid Java identifier as a name). I wrote about this once before. I expect this is the reason for introduction of syntax for representing individual functions.

Scala’s representation is also safer, in that it uses a data structure to denote a list with a maximum length of one, rather than a value with type T, oh wait, just kidding, it might be null!

My favourite part of Java’s proposed introduction of syntax for two very specific functions (among hundreds of others), watered down to be not-quite-as-useful, is the assurance that I am still going to hear about how Scala is complex, while Java is not. Fun times.

Edit: Proposed Java syntax.

Below is a compileable Scala source file. If you read it from top to bottom, it may help with some insights regarding applicative functors. It was partially inspired by Eric’s rendition of The Essence of the Iterator Pattern.

trait Lift[F[_]] {
  // Spot the pattern in these type signatures
  // of increasing arity.
 
  def lift0[A]:
    A => F[A]
 
  def lift1[A, B]:
    (A => B) => (F[A] => F[B])
 
  def lift2[A, B, C]:
    (A => B => C) => (F[A] => F[B] => F[C])
 
  def lift3[A, B, C, D]:
    (A => B => C => D) => (F[A] => F[B] => F[C] => F[D])
 
  // ... and so on
 
  // The relationship between lift<N> and lift<N-1>
  // can be given by a function,
 
  def ap[A, B]:
    F[A => B] => (F[A] => F[B])
}
 
trait LiftImpl[F[_]] extends Lift[F] {
  // Each lift function uses
  // the previous lift function and ap.
 
  def lift1[A, B]:
    (A => B) => (F[A] => F[B])
    = ap compose lift0
 
  def lift2[A, B, C]:
    (A => B => C) => (F[A] => F[B] => F[C])
    = f => ap compose lift1(f)
 
  def lift3[A, B, C, D]:
    (A => B => C => D) => (F[A] => F[B] => F[C] => F[D])
    = f => a => ap compose lift2(f)(a)
}
 
// Notes
// * lift0 is often called: unit, return, pure, point, η
// * lift1 is often called: fmap, map, ∘
// * lift<N> is often called: liftA<N>, liftM<N>

All that is left to do is to implement the LiftImpl trait! You can do this by implementing the ap and lift0 functions.

Examples of implementations that I know will work out if you try to implement them:

Those last couple are a bit funky, but a lot of that is syntax noise rather than anything too complicated. Fill out the body of those classes!

This post also incidentally attempts to justify my answer to a question that I regularly encounter, what is your favourite programming language?

It’s not possible to write bug-free programs.

This particular myth is quite popular, and its recent inclusion in a discussion I had has prompted me to write this post. The profound fact of this matter is that this statement is “as false as you can get.” In other words, there exists a formal proof of its negation, and subsequent counter-examples. It has also been my experience that belief in this myth has degenerative practical implications.

To emphasise the point, there exist programming languages for which it is impossible to write an incorrect program. What does it mean for a program to be correct? It means the program terminates. Such languages include (in order of my decreasing experience with them): Coq, Agda, Epigram, Isabelle.

Some people like to think “correctness” includes the thoughts of one or more persons in order to make the assessment. For example, one might proclaim, “sure you have a proof of program termination, but that is not the program that I asked for!” I think this is a poor use of the term “correctness” and I am not considering it any further here.

There is a problem with the aforementioned programming languages. A big one. While you always have correct programs in these languages, you cannot have all general programs. This is a well-documented contention. So you might say that these languages set out to achieve the objective of emphasising correctness, but at the expense of generality — in other words, they are exploring the question: “just how general and practical can we get, without sacrificing absolute correctness?” In my opinion, this is a very important question and worthy of further research.

Other programming languages sacrifice correctness for generality. In my typical work (I work for a product company), this includes languages such as Haskell, Scala and even Scala’s type system (which can be used as an embedded language). I expect most of my readers fall into this category of usage of languages. That is, we are all using languages that explore the question: “just how correct and practical can we get, without sacrificing generality?” In my opinion, this is a very important question too.

In the pursuit of answering both of the above questions, there are a number of contentions that arise. This means that there is not a holy grail programming language. It also means that there is a lot to understand before even starting to talk about the merits of correctness (aka static typing). This is unfortunate given the strong compulsion for, and quality of, popular commentary — we spend too much time clearing up myths. I digress.

However, this issue of contentions and trade-offs does not preclude the existence of questions of dismissal of programming languages. That is, it is possible to ask, and even answer, the question of whether or not there are programming languages that offer nothing toward resolving all of these (meaningful) contentions with respect to peer programming languages. These programming languages may be dismissed as offering nothing toward the goals of computability. It may be said that they are “universally impractical” with respect to the goals of computability (I am explicitly distinguishing here from social objectives). This may seem pessimistic, but it’s just a fact of the matter.

I hope that helps.

I see this a lot, especially in programming forums.

• Using the word simple, natural, pragmatic, real world or intuitive to mean “I am able to understand this.”
• Conversely, using the word complex, unnatural, academic, “your world” or unintuitive to mean “I am not able nor am I willing to invest the effort to come to understand this.”

If someone does this, I will politely request that it stops, since it crushes any potential useful discussion.

–By request from Viktor. You don’t wanna mess with Viktor.

…an introduction to the reader monad

• Video
• Slides

…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!