More ML, and object-oriented programming

April 6, 2016

Continuing with ML

Coming back from last time. Note that ML statements with dashes (-) in front and semicolons (;) at the end are copypasted from a REPL, with return values following.

Revisiting tuples

Remember that tuples can’t be indexed with a runtime value, because the compiler needs to know what the type of the indexed field will be at compile time.

And you can use tuples in patterns, to extract values from it:

fun first (a,b,c) = a

Note that the function above takes a single parameter: the tuple (a,b,c). The type, as with before, is polymorphic: 'a * 'b * 'c -> 'a.

You can also use tuple syntax to introduce multiple new variables at once:

val (a, b) = ([1, 2, 3] @ [4, 5, 6], 92 * 21)

Results in:

val a = [1,2,3,4,5,6] : int list
val b = 1932 : int

Binary operators

Binary operators in ML are just functions that take in a tuple of two elements and produce some output. And use these operators as functions by writing something like (op +). For example, 3 + 4 and (op +) (3, 4) are identical.

What this means is that if you want to pass + as a function parameter to another function, you can do that with (op +). For example:

- map (op +) [(1, 2), (3, 4), (5, 6), (7, 8)];
val it = [3,7,11,15] : int list

You can also declare a function to use a parameter as an infix operator:

fun islessthan (op <) x y = if x < y then "Yes" else "No"

Whatever function you then pass as the first argument can then be used as an infix operator in the function body, as shown above. You can use any operator you like:

fun islessthan (op +) x y = if x + y then "Yes" else "No"
(* This is identical *)

And you can pass in any function you want:

- islessthan (fn (a, b) => length a > length b) [1, 2, 3] [4, 5, 6, 7];
val it = "No" : string

Note that the type of the above function is ('a * 'b -> bool) -> 'a -> 'b -> string. Since we use the function in an if statement, it knows that operator has to return a bool.

You can also define your own infix operators:

- infix +-+-; 
infix +-+-
- fun selfify (op +-+-) a = a +-+- a;
val selfify = fn : ('a * 'a -> 'b) -> 'a -> 'b
- val square = selfify (op * );
val square = fn : int -> int
- square 5;
val it = 25 : int

Once you’ve declared something as infix, you can also add it to the global scope:

- fun a +-+- b = a * b;
val +-+- = fn : int * int -> int
- 3 +-+- 4;
val it = 12 : int

Defining new types

You can alias existing types in ML:

type myTuple = int * bool * string;

Now every time you refer to a myTuple the compiler recognizes you’re talking about an int * bool * string.

But this isn’t really creating a new type, it’s renaming an existing one.

Remember that a type is a set of values. We need a way to define what that set of values is.

Enter datatype.

datatype stoplight = red | green | yellow;

This is kind of like an enumeration in something like C, but these values have no underlying integer value. And now you can use the names of the type values as patterns for pattern matching.

fun drive red = "stop"
 |  drive green = "go"
 |  drive yellow = "go faster"

The type is stoplight -> string.

But this goes even further: you can associate additional values with each element of a datatype.

- (* Status of vehicle, int is speed. *)
- datatype status = stopped | moving of int
datatype status = moving of int | stopped
- stopped;
val it = stopped : status
- moving 60;
val it = moving 60 : status
- fun legal stopped = true
=  |  legal (moving speed) = if speed > 55 then false else true;
val legal = fn : status -> bool
- legal stopped;
val it = true : bool
- legal (moving 30);
val it = true : bool
- legal (moving 100);
val it = false : bool

Think that’s cool? It gets cooler. Datatypes can be recursive:

datatype tree = leaf of int | node of tree * tree

This tree type can be a leaf node, which contains an integer, or an interior node, which contains a tuple of two trees. Example:

val myTree = node (leaf 3, node (leaf 4, leaf 5));

This represents this tree:

You can then use these recursive types in pattern matching:

fun fringe (leaf n) = [n]
 |  fringe (node (left, right)) = fringe left @ fringe right

This prints out all leaf nodes left to right:

- fringe myTree;
val it = [3,4,5] : int list

What if you wanted a tree type that could have any data type in its leaves? Lists, strings, whatever? You can make a polymorphic datatype:

datatype 'a tree = leaf of 'a | node of 'a tree * 'a tree

You use this in the same way that you use the list type: use int tree or string tree. tree is now a type constructor.

Note that same as list, you can’t mix types in a tree. All 'as have to be consistent.

But this allows the fringe function to work on all types of trees. Instead of being of type tree -> int list, it’s of type 'a tree -> 'a list. Very flexible.

Object-oriented languages

Prof is not going to be teaching us how to program in an OO language, because experience with an OO language is a prerequisite. We’re going to tackle it from a PL point of view.

What makes a programming language object-oriented?

The prof has three criteria for this:

You have to be able to encapsulate data and code into a single data structure. In Java and C++, this are your classes: aggregate types where fields can be either data (member variables) or functions (methods). For example:

class Vehicle {
    public int speed; // data
    public int longitude;
    public int latitude;
    public void accelerate (int delta) { // functions
        speed += delta;
    }
};
   
// ... later ...
   
Vehicle v = new Vehicle();
v.speed = 50;
v.accelerate(10);

You have to have inheritance: the ability to define a new type using the code of an existing type.

class Airplane : public Vehicle {
    public int altitude;
    public void ascend (int delta) {
        altitude += delta;
    }
};
   
// ... later ...
   
Airplane a = new Airplane();
a.altitude = 1000;
a.ascend(500);
a.speed = 50;
a.accelerate(10);

You have to have subtyping with dynamic dispatch. Subtyping is treating one type as if it were another type, and dynamic dispatch means calling methods based on the actual type of an object, rather than the one it appears to be (the one it’s declared as). Here’s an example of subtyping in Java:

Vehicle v = new Airplane();
   
Airplane a = new Airplane();
   
void f (Vehicle v) {
    // ...
}
   
f(a); // Works fine.

And dynamic dispatch means that methods that you override in subclasses fall through to the subclass.

class Airplane : public Vehicle {
    public int altitude;
    public void ascend (int delta) {
        altitude += delta;
    }
    public override void accelerate (int delta) {
        speed += delta * 0.9; // Call it wind resistance
    }
};
   
// ... later ...
   
Vehicle v = new Airplane();
v.speed = 50;
v.accelerate(10); // Calls Airplane's accelerate function.
// Resulting speed is 59.

Note that this means that if you have a function like this:

void f(Vehicle v) {
    v.accelerate(10); 
}

You don’t know which function you’re calling here. It depends on whether you’re calling it with a Vehicle or an Airplane at runtime.

People often confuse inheritance with subtyping, because Java and C++ confuse them as well. Especially in Java, when you reuse the code from one type to create another type, suddenly you can treat every Airplane as if it were a Vehicle. You use inheritance, and get subtyping. C++ lets you use private inheritance to have inheritance without subtyping, but it’s less common.

Subset interpretation of subtyping

Think back to Ada: we could create a subtype through defining a subset of values, like a subtype of Integer that only took numbers 1 through 1000. This is true in object-oriented languages as well: a subtype defines a subset of the values of the parent type. For example, we have Vehicle which represents all vehicles imaginable, and we have Airplane, which represents only those vehicles that are airplanes. These are the “parent type” and “child type/subtype” respectively.

So here’s a question. Airplane has more data in it, more members, etc. This implies more degrees of freedom. How can it be that the set of values denoted by the airplane type are a subset of the Vehicle type?

We’ll answer that next time.