JDK 8 - Part 2 (Lambdas 1)

JDK 8 brings a couple of interesting - and obviously polarizing - new language elements. Probably the most interesting one is the adoption of JSR 335, colloquially know as "Project Lambda" openjdk.java.net/projects/lambda/. Technically, Project Lambda has a couple of consequences for the language core, but also for APIs:

The core provides notations for lambdas, an integration into the Java type system and means to secure backwards compatibility, especially for the collection classes. Of course, it will provide semantics for lambdas and their types.

On the side of APIs, it will provide ways to use lambdas for (say!) event handling and also provide higher-order functionals (map, filter, reduce, ...) to complement the standard iterator infrastructure of Java.

To keep these blog entries short, I'll break it down into several independent sections - the first here deals with topics of syntax and use of lambdas. It will also hint at issues related to typing of lambdas. Some strange phenomena in the handling of scopes for "lambda local" variables should be next, followed by higher order functionals and the problem of "Virtual Extension Methods" or "Public Defender Methods".

All the examples given here have been created with the JDK 8/NetBeans setup described in the previous delivery (http://berndok.blogspot.com/2013/10/jdk-8-under-ubuntu-part-1.html).

A personal remark first - I'll probably sound overly critical about a lot of things in JDK 8. This comes from two sources:

A) I have to teach this to students and I really like to have good (!) answers to questions, such as "What's the difference between abstract classes and Interfaces?" - I used to say something like "Interfaces cannot contain method implementations." and rant away about the difference between "interface inheritance" and "behavior inheritance" but that train just left the station!

B) From a software development standpoint I prefer to understand the language I'm working in - I like to be able to predict what my code is going to do when I'm writing it and not have to wait until the compiler or JUnit convince me otherwise. For secure software a predictable and consistent language core is essential and so is a clear semantics that any JVM (or other run-time system) has to implement. Too many exceptions from my expectations make me nervous - I have to rely on my memory to predict the effects of something I consider harmless and with my memory issues it's just too risky :-)

Lambdas - why?

Project Lambda states (http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-4.html):

"Given the increasing relevance of callbacks and other functional-style idioms, it is important that modeling code as data in Java be as lightweight as possible. In this respect, anonymous inner classes are imperfect for a number of reasons..."

Right now I'm not quite sure about the "increasing relevance of ... other functional-style idioms", but I'm buying the callback argument. This should illustrate the issue:

JButton myButton = new JButton("Button");
       
myButton.addActionListener(new ActionListener() {
      public void actionPerformed(ActionEvent ae) {
            System.out.println(ae + ": Button clicked");
      }});


In addition to serious questions about e. g. the use of "this" in an inner class, it's just not pretty! But of course, it's consistent with the semantics of instances and methods in the rest of Java.

The lightweight solution (as in COMMON LISP or JavaScript) involves functional objects - in JDK 8 it looks like this and it works just fine:

myButton.addActionListener(ae -> {
      System.out.println(ae + ": Button clicked");
      });

I'm sold. So, let's see what's behind lambdas in a little more depth.


Lambdas - Syntax and a first look at types

public class RunnableTest {
    public static void main(String[] args) {
        Runnable r = () -> {
            System.out.println("Hello world!");
        };
        r.run();
    }
}

This is the lambda solution to the Hello World problem. One thing becomes apparent immediately: the activation of the lambda is bound to its type (in this case Runnable). I don't know of a general function application in Java comparable to COMMON LISPs apply or funcall. Let's check that quickly:

public interface Workable {
    void work();
}
public class WorkableTest {
    public static void main(String[] args) {
        Workable r = () -> {
            System.out.println("Hello world!");
        };
        r.work();
    }
}

Works! Confirmed: To activate a lambda you need to know the Interface type! The type of a lambda is the Interface it implements.

Since casting Interface types doesn't work even if they have identical signatures, it's not even worth trying to cast lambda types. The remarkable issue here is that the expression  

() -> {System.out.println("Hello world!"); 

doesn't have a type by itself! Function literals don't have a type and hence cannot be called. But casting the literal to an Interface type works:

 ((Runnable)(() -> {System.out.println("Hello, world!");})).run();


It looks like that we have already three way to force a type on a lambda literal:

1. Cast it to the Interface type.
2. Assign it to a variable of the Interface type.
3. Pass it down as a parameter of the Interface type - else the ActionListener example wouldn't work (in slang downward funarg typing).

Does upward funarg typing (typing a lambda over a return type) work? Yep!

public class Upward {
    public static Runnable something()
    {
        return () -> { System.out.println("Hello, world!"); };
    }   
    public static void main(String[] args) {
        Upward.something().run();
    }
}

So the next method of typing a lambda is:

4. Return it as a value of the Interface type.

We need to look into these Interface types a little closer - next time!

JDK 8 under Ubuntu - Part 1

Ok, here's what seems work to set up JDK 8 and NetBeans under linux (ubuntu).

1. Install JDK 7 (there are problems running NetBeans under JDK 8, so we need to have 7 as the default JDK) - sudo apt-get install openjdk-7-jdk After that it appears under /usr/lib/jvm (we'll need to know where it is, really!).

2. Download NetBeans 7.4 from this address http://bertram2.netbeans.org:8080/job/jdk8lambda/1691/artifact/nbbuild/NetBeans-jdk8lambda-basic.zip. Extract the netbeans folder it somewhere (I put it into my home directory)

3. Read through the documentation - it's stand-alone and needs to be started over a terminal, like for me it then start as ~/netbeans/bin/netbeans. Start it, see if it works, close it.

4. Install the Oracle JDK 8 - I found this a little easier than installing the current JDK 8 OpenJDK preview:

sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer

Thanks to http://www.liberiangeek.net/2012/09/install-oracle-java-8-jdk-jre-in-ubuntu-12-04/ for that!

You will find the JDK also under /usr/lib/jvm as java-8-oracle.

5. Use javac -version and java -version to see what version is the current default - it's something like 1.8.0-ea and not what you want!

6. Use sudo update-alternatives --config java and
sudo update-alternatives --config javac to change the defaults for VM and compiler to JDK 7. Convince yourself that it worked (see 5).

7. Start NetBeans up again, create a new Java project.

8. Under Tools --> Java Platforms add JDK 8 by Add Platform, navigating to /usr/lib/jvm and selecting the java-8-oracle folder.

9. Open the Properties of your Java project, select JDK 1.8 under Libraries/Java Platform. Under Sources select JDK 8 as Source/Binary Format.

10. The next step might save you some frustration: Still under Properties/Build/Compiling deselect Compile on Save. At least today that's just not working! You have to manually compile! Ok the Properties dialog.

11. Create a class RunnableTest:

public class RunnableTest {

    public static void main(String[] args) {

        Runnable r = () -> {
            System.out.println("Hello world!");
        };
        r.run();
    }
}

Compile with F9 (or the context menu, of course) - then run it!

Good luck!

What's wrong with P mode?

Ok - just a short rant!

Since we all went off "Full Auto" mode on our DSLRs some years ago, it's now all the rage and a sign of professionalism to shoot in "Full Manual" mode, right?

So, you can either guess the proper exposure - I grew up with that and I'm still pretty good at it, then take a shot and check the exposure (preferably via histogram), correct and shoot again. Works perfectly for e.g. dragonfly pictures with no dragonflies in them!

Or you can use the little wheel(s) to adjust f-stop and exposure time and turn it/them until the bar is somewhere in the center - selecting which of the two to change requires some good "finger memory", and yes! it's (more or less) always in the center when you have your camera in "Auto ISO" anyway, because it compensates for a change of EV by adjusting the ISO value, just dreadful!

So, message 1: Get off "Auto ISO" - I loved for 10 days and now I'm back to selecting ISO first: sunny: 100, not so sunny: 200, not really sunny: 400, pretty dark: 640 etc. If all goes wrong, the 60D lets you adjust ISO without even taking the camera down - I love this little "nubby" on the ISO selector button!

Now in "M" I'm adjusting f-stop and exposure time manually, until the little exposure bar is centered (unless I have a weird lighting situation in which that doesn't work). I'm looking at different combinations estimating depth of field and moving speed, then I see that it's underexposed or overexposed, correct and then the shot is lost (unless it's a building or mountain both of which luckily have the pleasant habit of moving quite slowly or not at all).

Well, message 2: If it's moving fast, why not get a decent ISO preset, switch into "Tv" mode, select 1/1000 sec and see what the display says? Actually, I still think that 1/250 is fast enough for everything - some of my butterfly and horse photos are proof to the contrary :-)

Or, message 3: If I need some decent DOF why not switch into "Av" and select f/11?

Or. message 4 -and that's what I'm doing right now, if I have more than 5 seconds to take a shot: Use "P" mode and then turn the (one!) wheel until it comes up with a combination of f-stop and exposure time that seems usable?

And what about weird lighting situations? I see the point, of course! In these cases Exposure Compensation and/or Spot Measuring work perfectly if you can predict the effect.

Sorry, "M" aficionados - I'm back in "P", "Av" and "Tv"!

RawTherapee

Here's a nice one: RawTherapee - something that can make life a little easier under Linux (works quite nicely under Windows, too).

When you use GIMP and UFRaw, you might have had some issues, but RawTherapee helps a lot. It's not really a Adobe LR or Digikam replacer, but once you got it installed, it's really easy to use and the RAW processing capabilites are among the best available.

Once you got it installed, yes! While getting it to run under Windows is a no-brainer, under Ubuntu Linux it's just a little - difficult. Amazing, since it's a native Linux app.

So here's what I did do get 3.0 set up under Ubuntu 11.04

sudo add-apt-repository ppa:rawtherapee/ppa

sudo apt-get update

sudo apt-get install rawtherapee

And that took some time to figure out!

Why use Turing Machines when there's Haskell

Predicates and algorithms in Haskell

The nice thing about using Haskell (or lambda calculus) against using Turing machines is the possibility to talk about signatures of predicates and/or algorithms in a more natural manner. It is even easier to describe languages in terms of partial predicates rather than grammars or TMs.

So, let's do that:

A one-place predicate (1pp) P is defined by a Haskell expression of the form

P :: String -> Bool
P = \x -> ...

returning either True or False. Since Haskell allows for Type Synonyms, we define as an abbreviation:

type OnePP = String -> Bool

The extension or language of the predicate P - denoted as L(P) - is given by those values for which P returns True. If P returns True or False for every argument, it is called total and can be regarded as a decision procedure for L(P), else it called partial and can be regarded as an acceptor, recognizer, semi-decider or enumeration procedure for L(P).

If a language L = L(P) for a 1pp P, we refer to P as a representation of L.

Note that when we will talk about decision problems regarding languages, we assume the language in question is given by a representation. Another representation could be a Turing Machine, Type-0 grammar or another equivalent formalism.


Examples

The Acceptance Problem A_TM can now be stated and proved like this:

Problem: Is there a total predicate

H :: OnePP -> String -> Bool

such that (H A w) returns True, iff A returns True for w and False, if not (i. e. A returns False or no value at all)

Answer: No.

Proof: Assume H exists as specified. Then consider the following Haskell program:

D :: OnePP -> Bool
D = \A -> not (H A A)

Then the program

main = (D D)

shows the desired contradiction.

The fact that A_TM is recursively enumerated is neatly shown by

Acc :: OnePP -> String -> Bool
Acc = \A w -> (A w)

That should work nicely - more about that when Rice's Theorem comes up in some days...

More Cassandra

There's a lot written about the Cassandra data model, here's a good one: http://javamaster.wordpress.com/2010/03/22/apache-cassandra-quick-tour/

Let's set up a small system to work together with one little web app I did some years ago (at that time with MySql). Prepare a glossary for the Distributed Software Architecture Course for the fall. The data model should support two operations:

* List all terms/explanations in alphabetic order (over the term of course)
* List all terms/explanations in alphabetic order in a given interval

Shouldn't be too difficult, once you forget about ACID. Actually, in this case, with the small amount of "use cases", it seems I can just copy the basic SQL idea, equating a table with a column family. How did the SQL look like?

CREATE DATABASE IF NOT EXISTS DSAGlossary;
USE DSAGlossary;
DROP TABLE IF EXISTS Reference;

CREATE TABLE DSAGlossary.Reference (
 refID INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
 term VARCHAR(50) NOT NULL,
 description VARCHAR(250) NOT NULL,
 PRIMARY KEY (refID)
)

That doesn't look too difficult - the problems may arise with more cases. Here it's more or less the same structure - apart from the missing artificial primary key.

create keyspace DSAGlossary;
use DSAGlossary;

create column family Reference with
  comparator = UTF8Type and
  column_metadata =
  [
      {column_name: term, validation_class: UTF8Type,
                          index_type: KEYS},
      {column_name: expl, validation_class: UTF8Type}
  ];

We need this KEYS in order to have access to a column over the term. Feed this into the Cassandra implementation - in the Cassandra home directory:

1. Start it with bin/cassandra start&
2. Use the CLI to feed the script in:

bin/cassandra-cli -host localhost -port 9160 -f glossary.txt
Connected to: "Test Cluster" on localhost/9160
1361c18a-7b18-11e0-b561-e700f669bcfc
Waiting for schema agreement...
... schemas agree across the cluster
Authenticated to keyspace: DSAGlossary
13eb63eb-7b18-11e0-b561-e700f669bcfc
Waiting for schema agreement...
... schemas agree across the cluster

Sounds like a success (you're never completely sure); so add one entry:

bin/cassandra-cli -host localhost -port 9160
Connected to: "Test Cluster" on localhost/9160
Welcome to cassandra CLI.

Type 'help;' or '?' for help. Type 'quit;' or 'exit;' to quit.
[default@unknown] use DSAGlossary;
Authenticated to keyspace: DSAGlossary
[default@DSAGlossary] set Reference['Cassandra']['term']
                     = 'Cassandra';
Value inserted.
[default@DSAGlossary] set Reference['Cassandra']['expl']
                     = 'http://en.wikipedia.org/wiki/Apache_Cassandra';
Value inserted.

Still fine! Get it back, maybe?

[default@DSAGlossary] get Reference where term
                     = 'Cassandra';
-------------------
RowKey: Cassandra
=> (column=expl, value=http://en.wikipedia.org/wiki/Apache_Cassandra,  
     timestamp=1305041351336000)
=> (column=term, value=Cassandra,
     timestamp=1305041338862000)

1 Row Returned.

Ok! Next time: Get access from Java (or any other language).

Chess Search Algorithms 1: Minimax Search

Here's a series of little things I wrote around 10 years ago. Maybe it's time to resurrect them. You probably would have guessed that from the Pascal-ish pseudocode anyway.

It's all about basic Chess Search Algorithms - I wrote that mainly because I never felt too comfortable with the way they're coded in text books. Here "ref" before a parameter means that it should be passed by reference making it an out or in-out parameter; everything else is a value parameter.

1. MiniMax

Minimax search embodies two almost identical routines for the maximizing and minimizing player. It's usually less useful than NegaMax search (next issue), since you have two pieces of code to maintain. Watch out, to make sure it works always evaluate from the max player's side - this will change with NegaMax!

bestVal: best value for max/min player
bestMove: best move leading to this value

Maximizing level

procedure maxSearch(ref bestVal,
                   ref bestMove)
if atLeaf then
 // leaf: static evaluation
 // from maxPlayer's side
 bestVal := evalu8(maxPlayer)
else
 // generate successor moves...
 generate(moves,nMoves)
 // ...and preset return value
 bestVal := -infinity

// loop over all moves
for i := 1 to nMoves do
  // execute move and call min player
  makeMove(moves[i])
  minSearch(succVal,reply)
  // take back before continuing
  retractMove(moves[i])

// compare returned value: update value/move
if succVal > bestVal then
  bestVal  := succVal
  bestMove := moves[i]

Minimizing level

procedure minSearch(ref bestVal,
                 ref bestMove)
// really (almost) identical
if atLeaf then
  // always evaluate from maxPlayer's side
  bestVal := evalu8(maxPlayer)
else
  generate(moves,nMoves)
  bestVal := infinity

for i := 1 to nMoves do
  makeMove(moves[i])
  // now call the max player
  maxSearch(succVal,reply)
 retractMove(moves[i])

if succVal <  bestVal then
  bestVal  := succVal
  bestMove := moves[i]