λ Tony’s blog λ

Ben,
You have left two comments here, the second of which asked where your previous comment went. They were both caught by a spam filter and I am certain I pressed Approve on the first one and I definitely did on the second, but alas, they disappeared (WTF?).

Sorry about that, but if you could repost them, I will endeavour to ensure that they appear, since if I remember rightly, your original comment was a question of curiosity. Maybe the Wordpress guys can tell me why this is happening.

Once upon a time, I tried to write some Scala 2.7.1 for Functional Java and Reductio, but the compiler broke. So I filed the bug and waited for a fix. Thanks to Odersky et. al., the fix came promptly, so I started using one of the Scala 2.7.1->2.7.2 nightly builds and then I could compile my Scala code, yay! But that didn’t stop users complaining about crashes when using Scala 2.7.1 due its bad class file parser. Some users even stopped using Reductio because they don’t trust non-release builds. Oh well.

So I try out this new code snippet, nothing complicated:

class Foo[F[_]]
 
object Foo {
  def foo(n: Int)(implicit f: Foo[IN] forSome { type IN[_] }) = "foo"
 
  implicit val z: Foo[List] = new Foo[List]
 
  val t = foo(7)
}

But Scala 2.7.1 falls over. So does the 2.7.1->2.7.2 nightly build that I was using. Ugh! So I try out Scala 2.7.2-RC1, yay it compiles my legitimate source file. But does it compile all my other source?

Er no, Scala 2.7.2-RC1 produces bad class files when compiling code that is otherwise fine with previous Scala versions. In an attempt to obtain one bug fix I have also had to adopt another — one that makes its use non-viable. I am stuck with dealing with the former bug, which is also somewhat non-viable but only slightly more so than the latter. Give me a friggin’ break!

Ugh, this is not the first occurrence of this silliness. Flippin’ Scala, does this shit ever stop?

We use logic every day. No, I don’t mean just us programmers; I mean all of us. Here is an observation about propositional logic:

I have three propositions P, Q and R.

It doesn’t matter what these three propositions actually are, it will always hold that, “if P then Q implies that if Q then R implies that if P then R”.

I’ve subverted that a little to try to make it read a little better, but perhaps look it at it a bit more formally:

forall P Q R. (P → Q) → (Q → R) → (P → R)

You might like to try it out on paper using some example propositions, such as:

• P = Today is Tuesday
• Q = I am going swimming
• R = I have hairy armpits

I won’t bastardise it with English again However, I will give you a hint. Here is the truth table for → (logical implication):

A | B | A → B
0 | 0 | 1
0 | 1 | 1
1 | 0 | 0
1 | 1 | 1

Here is where it gets a little interesting. This same logical statement forall P Q R. (P → Q) → (Q → R) → (P → R) can also be expressed in most programming languages. Here it is in Java as the z method:

interface F<A, B> { B f(A a); }
static <P, Q, R> F<P, R> z(F<P, Q> f, F<Q, R> g) { ...

It gets more interesting; there is only one implementation of this function if we assume a terminating subset of the language (for Java, no null or throwing an exception). If you add in a side-effect such as writing to a file or the network, then you have perverted the function signature. Java allows us to do that, so we also have to assume a subset of the language that disallows this unfortunate anomaly. This notion of a type signature having only one implementation is called once inhabited.

Let’s write out the truth table for this. Notice the consistent 1 values in the final column. The statement is a tautology.

P | Q | R | P → R | Q → R | P → R | (Q → R) → P → R | (P → Q) → (Q → R) → P → R
0 | 0 | 0 | 1     | 1     | 1     | 1               | 1
0 | 0 | 1 | 1     | 1     | 1     | 1               | 1
0 | 1 | 0 | 1     | 0     | 1     | 1               | 1
0 | 1 | 1 | 1     | 1     | 1     | 1               | 1
1 | 0 | 0 | 0     | 1     | 0     | 0               | 1
1 | 0 | 1 | 0     | 1     | 1     | 1               | 1
1 | 1 | 0 | 1     | 0     | 0     | 1               | 1
1 | 1 | 1 | 1     | 1     | 1     | 1               | 1

Under the Curry-Howard Isomorphism, logical implication is represented by a function or in the example above using Java, by the F interface. The z function is called function composition. It takes the two give functions/propositions and composes them.

In Haskell, function composition is not called z as we called it with Java, but instead (.). That’s a full-stop character in parentheses. We can ask for the type of (.) in the GHC interpreter:

Prelude> :type (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

We might even call it by passing in function instances (similar to instances of the Java F interface):

Prelude> ((+1) . (*7)) 20
141
 
Prelude> (reverse . map Char.toUpper) "hello there"
"EREHT OLLEH"

You could do the same using Java, but it’s a little more verbose, so I’ll omit that

Here is a simple quiz. If we suppose the same F interface earlier, how many implementations of this function are there:

static <A> F<A, A> t() { ...

What about this one?

static <A, B> F<A, B> u() { ...

There are a few possibilities for improvement on this Scala Swing Example.

• Removed unnecessary semi-colons
• Inlined import
• Removed = in main declaration (strongly advised on functions returning Unit and especially more for main)
• Removed a few unnecessary parentheses

import javax.swing._
import java.awt.event.{ActionEvent, ActionListener}
 
object HelloWorld extends JFrame("Hello Swing") {
  def showButtonMessage(msg: String)  =
    JOptionPane.showMessageDialog(null, String.format("""<html>Hello from <b>Scala</b>. Button %s pressed""", Array(msg)));
 
  def main(args: Array[String]) {
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE)
    val button = new JButton("Click Me")
    button.addActionListener((e:ActionEvent) => showButtonMessage(e.getActionCommand.toString))
    getContentPane add button
    pack
    setVisible(true)
  }
 
  implicit def actionPerformedWrapper(func: (ActionEvent) => Unit) = new ActionListener {
    def actionPerformed(e:ActionEvent) = func(e)
  }
}

Patient: I have 6 potentially failing methods (a, b, c, d, e, f) and if one of those fails, I want to cease execution and return that failure, otherwise continue execution.

Doctor: What do they return if they succeed?

Patient: Nothing, they side-effect

Doctor: eek! OK, let’s see what we can do? What happens after you’ve completed this computation?

Patient: Well, it gets a bit hairier you see. Then I have 3 more potentially failing computations (g, h, i) and if any of those fail (or the original failed), then I also want to fail, however, I want to keep the errors in these last three computations.

Doctor: So let’s get this right, you perform all of the latter three computations regardless of their outcome and you only succeed if all nine computations succeed and you fail otherwise?

Patient: Yes, that’s right and…

Doctor: And for whatever silly reason, you’re using Java.

Patient: cowers; er yeah.

Doctor: Well, I’ve told you about that, haven’t I?

Patient: cowers more; yes you have but…

Doctor: So, if any of the first six computations fail, then you check the latter three for failures as well. These latter three are side-effecting, void return type, as well aren’t they?

Patient: Yes…

Doctor: If the first six succeed, you perform the latter three computations anyway, accumulating potential failures.

Patient: Right, exactly

Doctor: And just as an interesting observation, you will have at most, four errors and possibly none in the event of all nine succeeding.

Patient: Umm yeah, I hadn’t thought of it that way.

Doctor: smiles

  Validation<Throwable, Unit> a;
  Validation<Throwable, Unit> b;
  Validation<Throwable, Unit> c;
  Validation<Throwable, Unit> d;
  Validation<Throwable, Unit> e;
  Validation<Throwable, Unit> f;
  ////
  Validation<Throwable, Unit> g;
  Validation<Throwable, Unit> h;
  Validation<Throwable, Unit> i;
 
  Validation<Throwable, Unit> first() {
    return a.sequence(b).
            sequence(c).
            sequence(d).
            sequence(e).
            sequence(f);
  }
 
  Option<NonEmptyList<Throwable>> second() {
    return first().nel().accumulate(Semigroup.<Throwable>nonEmptyListSemigroup(),
            g.nel(),
            h.nel(),
            i.nel());
  }

Doctor: Now, this is the best that Java can do at solving this very popular request of yours, but come and see me when you’re ready to upgrade your tools…

Patient: Thanks Doc! I will!

Doctor: outward smile, inward scepticism; In the meantime, I will prescribe you with Functional Java 2.9 which is only going to work if you exercise at least some amount of intellectual discipline. You will need it for the solution above.

Doctor: On your way then.

Update: Functional Java 2.10 includes Validation.sequence.

July 2007

• Right ankle sprain
• Fifth life-time occurrence
• X-Ray reveals no fracture (Royal Brisbane Hospital)
• Zero weight bearing for 6 days

January 2008

• Certain movements cause swelling and discomfort
• Movement is restricted in bending the knee with the foot flat on the ground (name?) — can get the knee vertical with the tip of the foot, but no further
• MRI ordered by local GP (see below)
• Radiography report is unremarkable and states no anterolateral abnormality (even though the pain is posteromedial?)

February 2008

• Local GP administers cortico-steroid injection. Due to the swelling, the exact site of the pain cannot be accurately located. Since swelling has stopped (I have ceased rigorous activity), I estimate that the injection missed by about 2cm.
• Improvement over the following 3 weeks and flexibility increases, just a little (I can get my knee 3cm passed the tip of my foot vertically)

May 2008

• Ceased all sporting activity, in particular squash (3 times per week, including A1 grade competition)
• This was due to this injury and one other; scapholunate ligament tear resulting in instability

June 2008

• Subcutaneous atrophy from steroid injection begins to subside
• Further injections are advised against by local GP
• Arthroscopy of the wrist for scapholunate ligament repair (Dr. Peter Rowan, BOSMC)

July 2008

• Wrist Arthroscopy has failed (reconstruction pending?)
• HELP!

04 August 2008 (update)

• Appointment with Greg Sterling on 30 September
• YAY! 57 sleeps to go

Photos

• Taken 2 August 2008
• Red mark denotes site of impingement
• Note atrophy below the mark

MRI

Radiographer Report (Transcribed)

Images (DICOM)

All DICOM images (tar.gz) 71MB

MR000000 MR000000 MR000000 MR000000 MR000000
MR000001 MR000001 MR000001 MR000001 MR000001
MR000002 MR000002 MR000002 MR000002 MR000002
MR000003 MR000003 MR000003 MR000003 MR000003
MR000004 MR000004 MR000004 MR000004 MR000004
MR000005 MR000005 MR000005 MR000005 MR000005
MR000006 MR000006 MR000006 MR000006 MR000006
MR000007 MR000007 MR000007 MR000007 MR000007
MR000008 MR000008 MR000008 MR000008 MR000008
MR000009 MR000009 MR000009 MR000009 MR000009
MR000010 MR000010 MR000010 MR000010 MR000010
MR000011 MR000011 MR000011 MR000011 MR000011
MR000012 MR000012 MR000012 MR000012 MR000012
MR000013 MR000013 MR000013 MR000013 MR000013
MR000014 MR000014 MR000014 MR000014 MR000014
MR000015 MR000015 MR000015 MR000015 MR000015
MR000016 MR000016 MR000016 MR000016 MR000016
MR000017 MR000017 MR000017 MR000017 MR000017
MR000018 MR000018 MR000018 MR000018 MR000018
MR000019 MR000019 MR000019 MR000019 MR000019
MR000020 MR000020 MR000020 MR000020 MR000020
MR000021 MR000021 MR000021 MR000021 MR000021
MR000022 MR000022 MR000022 MR000022 MR000022
MR000023 MR000023 MR000023 MR000023 MR000023

Images (PNG)

All PNG images (tar.gz) 23MB

MR000000 MR000000 MR000000 MR000000 MR000000
MR000001 MR000001 MR000001 MR000001 MR000001
MR000002 MR000002 MR000002 MR000002 MR000002
MR000003 MR000003 MR000003 MR000003 MR000003
MR000004 MR000004 MR000004 MR000004 MR000004
MR000005 MR000005 MR000005 MR000005 MR000005
MR000006 MR000006 MR000006 MR000006 MR000006
MR000007 MR000007 MR000007 MR000007 MR000007
MR000008 MR000008 MR000008 MR000008 MR000008
MR000009 MR000009 MR000009 MR000009 MR000009
MR000010 MR000010 MR000010 MR000010 MR000010
MR000011 MR000011 MR000011 MR000011 MR000011
MR000012 MR000012 MR000012 MR000012 MR000012
MR000013 MR000013 MR000013 MR000013 MR000013
MR000014 MR000014 MR000014 MR000014 MR000014
MR000015 MR000015 MR000015 MR000015 MR000015
MR000016 MR000016 MR000016 MR000016 MR000016
MR000017 MR000017 MR000017 MR000017 MR000017
MR000018 MR000018 MR000018 MR000018 MR000018
MR000019 MR000019 MR000019 MR000019 MR000019
MR000020 MR000020 MR000020 MR000020 MR000020
MR000021 MR000021 MR000021 MR000021 MR000021
MR000022 MR000022 MR000022 MR000022 MR000022
MR000023 MR000023 MR000023 MR000023 MR000023

Without the rules as per last time, I have rewritten the Scala exercises to be closer to the Haskell revision. Enjoy

(And yes, I will get around to giving you all feedback (you should also see my email inbox) — just hang in there!).

sealed trait List[+A] {
  override def toString = {
    def toScalaList(t: List[A]): scala.List[A] = t match {
      case Empty => Nil
      case Cons(h, t) => h :: toScalaList(t)
    }
    toScalaList(this).toString
  }
}
final case object Empty extends List[Nothing]
final case class Cons[A](h: A, t: List[A]) extends List[A]
 
object List {
  def foldRight[A, B](as: List[A], b: B, f: (A, B) => B): B = as match {
    case Empty => b
    case Cons(h, t) => f(h, foldRight(t, b, f))
  }
 
  def foldLeft[A, B](as: List[A], b: B, f: (B, A) => B): B = as match {
    case Empty => b
    case Cons(h, t) => foldLeft(t, f(b, h), f)
  }
 
  def reduceRight[A](as: List[A], f: (A, A) => A): A = as match {
    case Empty => error("bzzt. reduceRight on empty list")
    case Cons(h, t) => foldRight(t, h, f)
  }
 
  def reduceLeft[A](as: List[A], f: (A, A) => A): A = as match {
    case Empty => error("bzzt. reduceLeft on empty list")
    case Cons(h, t) => foldLeft(t, h, f)
  }
 
  def unfold[A, B](b: B, f: B => Option[(A, B)]): List[A] = f(b) match {
    case Some((a, b)) => Cons(a, unfold(b, f))
    case scala.None => Empty
  }
}
 
sealed trait Natural {
  override def toString = {
    def toInt(n: Natural): Int = n match {
      case Zero => 0
      case Succ(x) => 1 + toInt(x)
    }
    toInt(this).toString
  }
}
final case object Zero extends Natural
final case class Succ(c: Natural) extends Natural
 
object Exercises {
 
// Exercise 1
// Relative Difficulty: 1
// Correctness: 2.0 marks
// Performance: 0.5 mark
// Elegance: 0.5 marks
// Total: 3
def add(x: Natural, y: Natural): Natural = error("todo")
 
// Exercise 2
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def sum(is: List[Int]): Int = error("todo")
 
// Exercise 3
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def length[A](as: List[A]): Int = error("todo")
 
// Exercise 4
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.0 mark
// Elegance: 1.5 marks
// Total: 7
def map[A, B](as: List[A], f: A => B): List[B] = error("todo")
 
// Exercise 5
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def filter[A](as: List[A], f: A => Boolean): List[A] = error("todo")
 
// Exercise 6
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def append[A](x: List[A], y: List[A]): List[A] = error("todo")
 
// Exercise 7
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def flatten[A](as: List[List[A]]): List[A] = error("todo")
 
// Exercise 8
// Relative Difficulty: 7
// Correctness: 5.0 marks
// Performance: 1.5 marks
// Elegance: 1.5 mark
// Total: 8
def flatMap[A, B](as: List[A], f: A => List[B]): List[B] = error("todo")
 
// Exercise 9
// Relative Difficulty: 8
// Correctness: 3.5 marks
// Performance: 3.0 marks
// Elegance: 2.5 marks
// Total: 9
def maximum(is: List[Int]): Int = error("todo")
 
// Exercise 10
// Relative Difficulty: 10
// Correctness: 5.0 marks
// Performance: 2.5 marks
// Elegance: 2.5 marks
// Total: 10
def reverse[A](as: List[A]): List[A] = error("todo")
}

It is better not to believe in God, since if he does not exist, you lose nothing, but if he does exist, you are going to hell, where it is nice and warm. Winter sucks.

Functional Java 2.8 contains a concurrency API that implements Actors as seen in Erlang and Scala. This allows a user to take advantage of multiple core machines in their Java code.

Runar has written articles explain how to use the API — it’s pretty darn easy for a client — just don’t look under the hood

• Higher-Order Java Parallelism, Part 1: Parallel Strategies and the Callable Monad
• Higher-Order Java Parallelism, Part 2: Parallel List Transformations

Here is an example of a parallel fibonacci that uses a few hundred virtual threads (unlike the ping/pong example that uses… wait for it… millions of virtual threads!). On my quad-core machine, the fibonacci computation speeds up by about 6 times (45 seconds serially to about 7 seconds when using actors).

The example uses Java 7 BGGA syntax (imports ommited) and after compilation, runs fine on any 1.5 JVM. This example is also available with Java 1.5 source code in the Functional Java release.

/**
 * Parallel Fibonacci numbers.
 * Based on a Haskell example by Don Stewart.
 * Author: Runar
 */
public class Fibs {
 
  private static final int CUTOFF = 35;
 
  public static void main(final String[] args) throws Exception {
    if (args.length < 1)
      throw error("This program takes an argument: number_of_threads");
 
    final int threads = Integer.parseInt(args[0]);
    final ExecutorService pool = Executors.newFixedThreadPool(threads);
    final Strategy<Unit> su = Strategy.executorStrategy(pool);
    final Strategy<Promise<Integer>> spi = Strategy.executorStrategy(pool);
 
    final Actor<List<Integer>> out = actor(su, { List<Integer> fs => {
      int i = 0;
      for (List<Integer> ns = fs; ns.isNotEmpty(); ns = ns.tail()) {
        System.out.println(MessageFormat.format("n={0}=>{1}", i, ns.head()));
        i++;
      }
      pool.shutdown();
    }});
 
    System.out.println("Calculating Fibonacci sequence in parallel...");
 
    final F<Integer, Promise<Integer>> fib = { Integer n => (n < CUTOFF) ?
        promise(su, P.p(serialFib(n))) :
        fib.f(n - 1).bind(join(su, P1.curry(fib).f(n - 2)), { int a => { int b => a + b }} ) };
 
    join(su, fmap(Promise.<Integer>sequence(su)).f(spi.parMap(fib).f(range(0, 46)))).to(out);
  }
 
  public static int serialFib(final int n) {
    if (n < 2)
      return n;
    else return serialFib(n - 1) + serialFib(n - 2);
  }
}

The exercises below are similar to my previous ‘Scala exercises for beginners’, except the rules a little clearer. For those of who have emailed me or submitted responses here on the blog, I will get around to providing you feedback, however, I’d prefer to do so on the revised version of the Exercises since then I can maintain a bit of clarity in explaining the solutions; specifically, why one may be preferred over another. I hope you don’t mind.

If you have not used Haskell before, download and install GHC, start up the interpreter (ghci) and load the source file. e.g. :load Exercises.hs If you are on Debian, you can install GHC and start the interpreter with: apt-get install ghc6 && ghci.

The source file below can be found here.

{-
The 'Scala exercises for beginners' set rules about what you were not permitted to use.
This is because you were permitted to use some functions, but not others. This led to
some amount of confusion (sorry). Instead, this time, I will define my own data types.
One is equivalent to Haskell's list [], although without the syntactic support and the
other is the set of natural numbers (0 onward). I will also predefine some useful
functions that you might consider using to solve each problem. That way, I needn't set
any rules; you are very much free to do what you want (Although, converting between
this type and [] is considered cheating, as you might expect ;).
 
I will consider converting the Scala exercises to use a similar strategy in a second
revision to prevent this confusion.
 
TOTAL marks:    /66
-}
 
module Exercises where
 
import Prelude hiding (sum, length, map, filter, maximum, reverse, succ, pred)
 
-- The custom list type
data List t = Nil | Cons t (List t)
 
instance (Show t) => Show (List t) where
  show = show . toList
    where
    -- unfoldr, but let's not import Data.List
    toList Nil = []
    toList (Cons h t) = h : toList t
 
-- the custom numeric type
data Natural = Zero | Succ Natural
one = Succ Zero
two = Succ one
 
instance Show Natural where
  show = show . toInt
    where
    toInt Zero = 0
    toInt (Succ x) = 1 + toInt x
 
-- functions over Natural that you may consider using
succ :: Natural -> Natural
succ = Succ
 
pred :: Natural -> Natural
pred Zero = error "bzzt. Zero has no predecessor in naturals"
pred (Succ x) = x
 
-- functions over List that you may consider using
foldRight :: (a -> b -> b) -> b -> List a -> b
foldRight _ b Nil = b
foldRight f b (Cons h t) = f h (foldRight f b t)
 
foldLeft :: (b -> a -> b) -> b -> List a -> b
foldLeft _ b Nil = b
foldLeft f b (Cons h t) = let b' = f b h in b' `seq` foldLeft f b' t
 
reduceRight :: (a -> a -> a) -> List a -> a
reduceRight _ Nil = error "bzzt. reduceRight on empty list"
reduceRight f (Cons h t) = foldRight f h t
 
reduceLeft :: (a -> a -> a) -> List a -> a
reduceLeft _ Nil = error "bzzt. reduceLeft on empty list"
reduceLeft f (Cons h t) = foldLeft f h t
 
unfold :: (b -> Maybe (a, b)) -> b -> List a
unfold f b = case f b of Just (a, b') -> a `Cons` unfold f b'
                         Nothing -> Nil
 
-- Exercises
 
-- Exercise 1
-- Relative Difficulty: 1
-- Correctness: 2.0 marks
-- Performance: 0.5 mark
-- Elegance: 0.5 marks
-- Total: 3
add :: Natural -> Natural -> Natural
add = error "todo"
 
-- Exercise 2
-- Relative Difficulty: 2
-- Correctness: 2.5 marks
-- Performance: 1 mark
-- Elegance: 0.5 marks
-- Total: 4
sum :: List Int -> Int
sum = error "todo"
 
-- Exercise 3
-- Relative Difficulty: 2
-- Correctness: 2.5 marks
-- Performance: 1 mark
-- Elegance: 0.5 marks
-- Total: 4
length :: List a -> Int
length = error "todo"
 
-- Exercise 4
-- Relative Difficulty: 5
-- Correctness: 4.5 marks
-- Performance: 1.0 mark
-- Elegance: 1.5 marks
-- Total: 7
map :: (a -> b) -> List a -> List b
map = error "todo"
 
-- Exercise 5
-- Relative Difficulty: 5
-- Correctness: 4.5 marks
-- Performance: 1.5 marks
-- Elegance: 1 mark
-- Total: 7
filter :: (a -> Bool) -> List a -> List a
filter = error "todo"
 
-- Exercise 6
-- Relative Difficulty: 5