λ Tony’s blog λ

http://www.news.com.au/couriermail/story/0,23739,22427799-5007200,00.html

PHILIP Lamattina’s spectacular effort at Willowbank near Ipswich on Saturday night has already assumed legend status among Australia’s drag racing fraternity.

He miraculously escaped unscathed from the 500km/h smash that destroyed his $250,000 Top Fuel dragster.

The publisher(s) of this story oughtta be ashamed of themselves. Everyone knows (note: I am exempt from accusations of argumentum ad populum fallacies because I am (and circular reasoning too, got it?)) that SPEED KILLS! Here these journalists are implicitly refuting the known established perversion… er… correction, of the laws of Physics and our understanding of space and time! This is nothing short of failure of reason and I now expect deaths on our roads to increase substantially. All because of some irresponsible journalist(s)!

Actually, I take it back. You see, it was a miracle. Yes, notice the use of the adverb, ‘miraculous’ in the second paragraph. Instead of contradicting our government’s established scientimplistic (yes, I made that up :)) understanding, the article exonerates itself by attributing the whole affair to a miracle. This is permitted under the laws of illogic, which any person is free to invent for themselves, right? Of course.

So you see, that makes sense now. Phew!

On page 85 of Scala By Example, the last paragraph states the following in reference to generalising sequence (aka for) comprehensions:

It would be attractive to enforce these types statically in the Scala compiler, for instance by requiring that any type supporting for-comprehensions implements a standard trait with these methods 1 . The problem is that such a standard trait would have to abstract over the identity of the class C, for instance by taking C as a type parameter. Note that this parameter would be a type constructor, which gets applied to several different types in the signatures of methods map and flatMap. Unfortunately, the Scala type system is too weak to express this construct, since it can handle only type parameters which are fully applied types.

This type system feature being described is called higher-kinded types. Sadly, none of the mainstream, statically-typed languages offer this feature, which leads to enormous amounts of repetition.

In fact, many of the arguments in favour of dynamic languages that I have seen, are refuted simply with the introduction of this very key, but relatively simple (to other type system features) feature. In other words, I only have to batter an eyelid before I have refuted those arguments, which brings me great suspicion of any underlying plausibility. Perhaps there are other arguments that are more plausible, but I have yet to hear any. I digress…

Higher-kinded types would be available in Java/C# if you could write something like this:

static <C<_>, A, B> C<B> map(Convert<A, B> c, C<A> container) {
  ...

Again, sadly, you cannot. But in Scala you can! In other words, the paragraph quoted above is, at least from how I interpret it, false. However, do understand that at the time the paragraph was written, it may have been true (I can neither confirm nor deny this), but my reckoning is that this piece of documentation needs updating at the least.

Without further ado, I introduce the my refutation:

trait Functor[f[_], a] {
  def map[b](f: a => b)(ft: => f[a]): f[b]
}

trait Monad[m[_], a] {
  def flatMap[b](ma: => m[a])(f: a => m[b]): m[b]
}

trait Filter[c[_], a] {
  def filter(f: a => Boolean)(c: => c[a]): c[a]
}

My assertion now, is that a Scala sequence comprehension could indeed be written to be type-safe if it only accepted types that adhered to the above interfaces. Am I wrong and if so, what have I misunderstood?

Here are some example (incomplete) implementations of foreach:

object Comprehension {
  type Comprehension[c[_], a] = Functor[c[a], a] with Monad[c[a], a] with Filter[c[a], a]
  def foreach[c[_], a](c: c[a], e: a => Unit, p: a => Boolean)(implicit ca: Comprehension[c[a], a]): Unit = ca.map(a => if(p(a)) e(a))(c)
  def foreach[c[_], a](c: c[a], e: a => Unit)(implicit ca: Comprehension[c[a], a]): Unit = foreach[c[a], a](c, e, (a: a) => true)
  def foreach[c[_], a, b](c: c[a], f: a => b, p: a => Boolean)(implicit ca: Comprehension[c[a], a]): c[b] = ca.map(a => f(a))(ca.filter(p)(c))
  def foreach[c[_], a, b](c: c[a], f: a => b)(implicit ca: Comprehension[c[a], a]): c[b] = ca.map(a => f(a))(c)
}

I await an explanation for what I think is the unwarranted undermining of Scala’s value by Scala’s own documentation!

Kathy Griffin goes from being annoying at worst to an international hero overnight!

a lot of people come up here and thank Jesus for this award. I want you to know that no one had less to do with this award than Jesus.

Check it out!

Kathy, you have redeemed yourself of any debt that you may have owed the community. I take my hat off to you for your courage. Well done.

On a lighter and hilarious note, check this comment out:

The comedian’s remarks were condemned Monday by Catholic League President Bill Donohue, who called them a “vulgar, in-your-face brand of hate speech.”

OK, you can stop laughing at the irony now, STOP!

Lazy evaluation is a core topic in computer programming that is also widely misunderstood and often, erroneously trivialised. Here, I will attempt to demonstrate some of the attributes of many common mainstream programming languages; namely strict programming languages. I will also attempt to distinguish intrinsically strict languages from optionally lazy languages by focusing on what intrinsically strict means. As a note, strict evaluation (or strictness) is what lazy evaluation (or laziness) is not.

Some languages are optionally lazy, including one that I use quite a lot in my work called Scala. This means I have the option of laziness, however, the default in all cases is strictness. I have to explicitly annotate laziness (=> in Scala). Some languages are optionally strict; one that I use a lot is Haskell. Laziness is the default, while strictness is explicitly annotated (seq or ! in Haskell). There are many debates about which is the correct default, but whatever the outcome of such a debate, the issue I describe next is one that demands much more attention.

Some languages are forcibly strict. It is these languages that I intend to focus on for the remainder of this post. I assume that my reader either understands or is at least open to just how debilitating a language is that does not support user-defined lazy evaluation in any form whatsoever. I will explicitly discuss the Java programming language, though what I describe is equally applicable to C, C# and many other languages.

In Java, the only lazy constructs are:

• if/else
• while
• for
• ? : (ternary operator)
• &&
• ||

This is extremely limiting. To make the case clear, I will focus on a particular example of this. Consider the && function of type (Boolean x Boolean) -> Boolean. Here is a profound assertion:

It is impossible to write && in Java yourself.

Some of you might be quick to rebut:

// Sure I can!
boolean and(boolean b, boolean c) {
  return b && c;
}

This is a very crucial and amateur mistake as you will soon see.

Since the domain of the && function is so small, there is room enough to enumerate it below:

a   b   a && b
t   t   t
t   f   f
f   t   f
f   f   f
t   ⊥   ⊥
⊥   t   ⊥
f   ⊥   f
⊥   f   ⊥

Wait just a minute!! What are those last 4 entries in the table and just WTF is that upside-down T doing!? That upside-down T represents what is called the bottom element, sometimes also written as _|_ when only ASCII is available. It is an extremely important part of the && function (and all functions in fact!). In Java, the bottom element is typically represented by throwing an exception (or sometimes, with null).

Remember, two functions are equivalent if for every element of the domain, the result of function application to that element on either function is equivalent. Here is a more formal definition for function equivalence:

Two functions, f and g, are equivalent if the following property holds:

∀ x. f x ⇔ g x

We could rewrite the + function for int as follows:

int sum(int a, int b) {
  return a + b;
}

I won’t list out the table for each element in the domain of +, since it is so long, so you’ll either have to do it yourself, or take my word for it that the sum function above is equivalent to +

However, why can’t we rewrite &&? If we look at the table for && above and select the penultimate entry, we note the following:

false && ⊥ == false

It is this entry that disallows us from rewriting &&. Look at the following function:

boolean bottom() {
  throw new Error();
}

What is the result of false && bottom()? It is false of course! This is because && is lazy in its second argument (sometimes; specifically, when the first argument is false). This is impossible to emulate in your own Java function. If we take the earlier function that attempted (but failed) to rewrite && and call:

and(false, bottom())

The result of this function is ⊥ and not false, like it is with &&. Therefore, this function is not equivalent to &&. Further, I restate that it is not possible to write such a function in these languages. Unlike +. which is strict in both of its arguments, && is not and this makes it impossible to write a user-defined version of && and therefore, ||, if/else and ?: and importantly, many other potential functions that many Java programmers are probably not even aware of (Dynamic Programming Algorithms anyone?).

If you are ever forced to use these severely limited programming languages, you could be thankful that you have some primitive lazy constructs for doing very primitive operations (oppression), or you could be resentful for not having the expressive power of other, lazy languages (resistance against oppression)

Below is a session with my Scala interpreter to demonstrate that it is indeed possible to write && in Scala (lazyAnd), but not Java. Note that the functions (def declarations) and final variables (val declarations) below are Java functions and final variables all running in a JVM (invoked by the Scala interpreter):

scala> val x = false && error("bottom")
x: Boolean = false

scala> def and(a: Boolean, b: Boolean) = a && b
and: (Boolean,Boolean)Boolean

scala> val y = and(false, error("bottom"))
java.lang.Error: bottom

scala> def lazyAnd(a: Boolean, b: => Boolean) = a && b // can't do this in Java, C#, C, etc.
lazyAnd: (Boolean,=> Boolean)Boolean

scala> val z = lazyAnd(false, error("bottom"))
z: Boolean = false