Friday, September 25, 2009

Separating Java: Objects

Now, what about objects? Certainly Java, as an object-oriented language, provides many features for creating an using objects. Many of those those features, unfortunately, seem to obfuscate the essence of objects. In some ways the most important features of objects are that they implement an interface, and that we can treat them as merely their interface. Here is an interface, and means of constructing objects that implement it. Notes to follow.

public interface IntSet2 {
  public IntSet2 add(int i);
  public boolean contains(int i);
}

final public class IntSet2s {
  private static IntSet2 append(final int i, final IntSet2 set) {
    return new IntSet2() {
 
      public IntSet2 add(int i) {
        return append(i, this);
      }
 
      public boolean contains(int j) {
        return i == j || set.contains(j);
      }  
    };
  }
  public IntSet2 singleItemIntSet(final int i) {
    return new IntSet2() {
      public IntSet2 add(int i) {
        return append(i, this);
      }
 
      public boolean contains(int j) {
        return i == j;
      }
    };
  }
  public IntSet2 evenIntSet() {
        return new IntSet2() {
      public IntSet2 add(int i) {
        return append(i, this);
      }
 
      public boolean contains(int i) {
        return i % 2 == 0;
      }
    };
  }
  public IntSet2 emptyIntSet() {
    return new IntSet2(){
      public IntSet2 add(int i) {
        return singleItemIntSet(i);
      }
 
      public boolean contains(int i) {
        return false;
      }
    };
  }
}
 
Notes
  • All the objects created in this program are anonymous instances of the IntSet2 interface. Any code that want to can implement this interface! 
  • We have completely side-stepped classes. We use constructor functions to create instances of IntSet2.
  • Code cannot use an instanceof test to tell which implementation of the IntSet2 is being used. In fact, it has no way of telling the difference between the different implementations other than by observing their behavior through the interface.
  • Each implementation of interface can have a completely different representation, and it is impossible, even for instances of the same interface, to see the representation of an IntSet2.
  • Benefits: Programming to interfaces can give great flexibility by allowing any piece of code to implement it, so long as the implementation conforms to the documented behavior. 
  • Caveats: It can sometimes be hard to implement efficient code in some cases where this pure object style is used.
     

Separating Java: ADTs

In Java, Abstract Data Types and Objects are rather intertwined, often to the detriment of programmers. In this post and the next, I'll try to separate the two concepts as best as I understand. Note that most of these ideas, and the Set example specifically, come to me from William Cook's recent essay. The ideas are also well-covered in TAPL, without the Java code.

Here, I will use a subset of Java's features to express an ADT, such as one would have in a language like ML or Ada. It's a (not very efficient) set. Notes follow.

final public class IntSet {
 
  private int[] members;
  private IntSet() {
    this.members = new int[0];  
  }
  public static IntSet empty() {
    return new IntSet();
  }
  public static IntSet add(IntSet set, int i) {
    if( Arrays.binarySearch(set.members, i) != -1 ) {
      return set;
    }
    else {
      IntSet result = new IntSet();
      int old_length = set.members.length;
      result.members = Arrays.copyOf(set.members, old_length + 1);
      result.members[old_length] = i;
      Arrays.sort(result.members);
      return result;
    }
  }
  public static boolean contains(IntSet set, int i) {
    return Arrays.binarySearch(set.members, i) != -1;
  }

  public static IntSet union(IntSet s1, IntSet s2) { /* Performs merge sort. */ }
}

Notes:
  • The class Set is the abstract data type. It has been declared final, which tells the programmer that the representation is fixed and known completely inside of the class.
  • The members field is private to hide the representation. 
  • The constructor is private so that new Sets must be created through one of the existing introduction means, namely empty().
  • All methods are static. No dynamic dispatch is being used here. We do not want to send messages to objects that can handle that message in an arbitrary way, rather we want to perform some operation on a hidden representation by functions inside of the abstraction that are allowed to view the hidden representation.
  • Benefits: Functions inside the Set class can operate on sets with complete knowledge of a set's representation. This can occasionally be beneficial, particularly in cases where performance is important. Knowing that all sets are implemented as sorted arrays of ints can sometimes allow me to write better performing methods. (Binary methods in particular, but other methods as well.) For instance, in the union method above which is incomplete, can perform its task using merge sort if that is more efficient. Still, the representation is hidden from the rest of the program, so we can change things internally without affecting code as long as we don't change the public methods.
  • Caveats: No one else can define a Set that is compatible with this Set! If a certain method expects an IntSet of the sort we've just defined, then the IntSet can only be created through this class, and not through any other means. The representation for all IntSets is fixed (but hidden).

Tuesday, September 22, 2009

Talk: Concurrent Object Protocols Experience Report

Yesterday in SSSG (that class I have to take every semester until I graduate) I gave a talk entitled, "Case Studies in Concurrent Object Protocols." It was really an experience report describing the use of my approach on some open source programs. I used my tool Sync-or-Swim to verify some open source programs, and I encountered a couple of neat patterns which I describe. If you're intrested, check out the slides. I'm afraid you need something that can read PPTX, but if you're interested and you can't read that, let me know and I'll put it up in a different format. 

Thursday, September 17, 2009

Simply Typed Lambda Calculus vs. Untyped

Today I learned something new! At first it was startling, but in hindsight it makes perfect sense: The Simply Typed Lambda Calculus is not Turing complete. Any well-typed program will eventually terminate, and the intuition here is that your program can only have a finite number of arrow types, and evaluation will always reduce the number of arrow-typed things that you have around. The Untyped Lambda Calculus, however, allows programs that never terminiate. I guess the Y-combinator is a pretty good example here. I once learned that the Untyped Lambda Calculus can be embedded inside the Typed Lambda Calculus by having essentially one type, the everything type. So I guess this makes sense, since there are no arrow types that can decrease monotonically...

Now I have more questions: 
Does this mean the untyped lambda calculus is Turing complete?
How does the encoding of the untyped lambda calculus into the lambda calculus work? I mean, don't functions always have to have function type? Or is the everything type some kind of function type?

Wednesday, September 16, 2009

Urban Hike this weekend in Verona

There's going to be an Urban Hike this weekend in Verona, PA. I'll be there and I think it will be fun. Hope you can make it out. Full details below: 

Fall is coming, and Urban Hike is heading to fair Verona on Saturday September 19th at 10:30am. We'll meander along the river, get some aerobic exercise in search of great views, and we might even end the hike with some group "hugs." Alongthe way we'll learn about Celoron (no, not the vegetable, but an important part of Pittsburgh history). As usual there will be a local dinning option for those who want to stick around after the 3 hour (more or less) hike.

We'll meet at the parking area on E. Railroad Ave. between South Ave. and James St.

Wednesday, September 9, 2009

Chief's

highly recommend reading the Google Maps review of Chief's Bar. (You know, the one on Craig & Center with the fire helmet on the sign.) WOW. Sounds like a rough place...

Southwest

Remember when the old Southwest planes had face-to-face seats? I used to try to convince my mom that we should sit back there, because I thought it was so cool, and since Southwest never had assigned seats. Today I can't imagine a more horrible airline experience...