CSE341 Notes for Wednesday, 4/19/24

I spent some time discussing the next programming assignment, but I won't repeat that here because everything is in the assignment writeup.

I spent some time discussing modules. I mentioned that the languages that are most familiar to us today come from Algol, which was created in the late 1950s. Algol had many great features (what was generally called "structured programming") many of which could be described as "modular" programming. The key ideas behind modularity are:

Decomposition: You can break up a program into sub-programs (functions, procedures, methods)
Information hiding: Details can be localized so that they aren't visible outside (e.g., local variables)
Careful interfaces that specify how the pieces fit together (e.g., parameters and return types).

Even though Algol had these great ideas of modularity, it only had one level of modularity. The concept of a module is to have a collection of variables, types, and subprograms that constitute a module. That means grouping them together in some way, providing information hiding, and having a way to specify interfaces. Algol did not have modules.

From Algol we got Pascal, C, and C++, none of which had a good module capability initially (C++ has been changing over the years and C++20 seems to have a module construct). We got Ada as well, which did have a robust module construct, but it was unpopular because it had been invented by the Department of Defense.

In the late 1980s we started seeing languages like Modula 2, which was invented by the same researcher who invented Pascal. The main difference was that Modula 2 had modules. When Java came along soon afterwards, they included something like modules, although in a funny way.

Java has packages, which are collections of classes and interfaces. There are also mechanisms for information hiding within a package, which is good. But we normally think of a module as including functions and variables as well. In Java we collect those things together by putting them in a class. What would normally be free-standing functions and variables in a module become static elements of a class. The Math class in Java is a classic example. It has static variables Math.PI and Math.E and static methods like Math.sin, Math.cos, and Math.abs.

We briefly discussed some of the benefits of modules:

They allow you to control your namespace. Different programmers can use the same names for functions and variables as long as they appear in different modules. We can use the dot notation or something similar to refer to the different versions of the same name.
We can use information hiding to limit what we expose to clients.
We can guarantee data invariants for our underlying representation.
We have the ability to reimplement the type without changing any client code.
We have more flexibility in the implementation. For example, we could use an eager approach or a lazy approach and ensure that the client will never notice the difference (see the example below).

I said that in the next two lectures we would discuss two important concepts from OCaml known as structures and signatures. I started with structures.

When you write a large amount of code you find yourself having trouble managing the name space. For example, what if you load two different OCaml files that each have a function with a particular name? The second file loaded wipes out the definition from the first file. And what if you have a utility like to_string that you want to implement for many different types? A structure provides a way to establish independent namespaces. For example, OCaml has a function called List.length that is included in a module called List and also a function called Array.length that is included in a module called Array.

The basic form of a structure is:

module <name> = struct <definitions> end The definitions can include the various elements we have been discussing:

function definitions
variable definitions
exception definitions
type definitions

I said that we would be looking at an example that I got from Dan Grossman. We will define a module called Rational that provides a datatype and functions for manipulating rational numbers. We are going to go through several different versions to better understand the details of structures and signatures.

So our overall structure will look like this:

        module Rational =
        struct
            (* we'll fill in definitions here *)
        end

We began with a type definition. Rational numbers are numbers that can be expressed as a ratio of two integers, so it would make sense to store them as a tuple of two ints. But most of us don't think of integers like 23 as a tuple. We know that 23 is a rational number, but we don't like to think of it as being "23 divided by 1". So we included two different cases, one for whole numbers and one for rationals that we need to express as a fraction:

        module Rational =
        struct
            type rational = Whole of int | Fraction of int * int
        end

If we were providing a full-blown implementation, we'd include functions for adding, subtracting, multiplying and dividing such numbers. For our purposes, we'll implement just an add method as a way to explore these issues.

The signature for the add function is that it takes a tuple of rationals (rational * rational) and it returns a rational. Because there are two forms for a rational, we end up with four total cases for add:

    let add(r1, r2) =
        match (r1, r2) with
        | (Whole i, Whole j)                   -> ??
        | (Whole i, Fraction(a, b))            -> ??
        | (Fraction(a, b), Whole i)            -> ??
        | (Fraction(a1, b1), Fraction(a2, b2)) -> ??

It took us a while to work out the math, but together we filled in the following definitions:

    let add(r1, r2) =
        match (r1, r2) with
        match (r1, r2) with
        | (Whole i, Whole j)                   -> Whole(i + j)
        | (Whole i, Fraction(a, b))            -> Fraction(i * b + a, b)
        | (Fraction(a, b), Whole(i))           -> Fraction(i * b + a, b)
        | (Fraction(a1, b1), Fraction(a2, b2)) ->
            Fraction(a1 * b2 + a2 * b1, b1 * b2)

We then added a to_string function:

   let to_string(r) =
       match r with
       | Whole i        -> string_of_int(i)
       | Fraction(a, b) -> string_of_int(a) ^ "/" ^ string_of_int(b)

This gives us our first version of the Rational structure:

(* initial version of the Rational structure that shows how we can group
   a type, its constructors, and some functions into a single unit. *)

module Rational =
struct
    type rational = Whole of int | Fraction of int * int

    let add(r1, r2) =
        match (r1, r2) with
        | (Whole i, Whole j)                   -> Whole(i + j)
        | (Whole i, Fraction(a, b))            -> Fraction(i * b + a, b)
        | (Fraction(a, b), Whole(i))           -> Fraction(i * b + a, b)
        | (Fraction(a1, b1), Fraction(a2, b2)) ->
            Fraction(a1 * b2 + a2 * b1, b1 * b2)

   let to_string(r) =
       match r with
       | Whole i        -> string_of_int(i)
       | Fraction(a, b) -> string_of_int(a) ^ "/" ^ string_of_int(b)
end

We were able to test this in the OCaml interpreter:

        # let r1 = Rational.Fraction(2, 3);;
        val r1 : Rational.rational = Rational.Fraction (2, 3)
        # let r2 = Rational.Fraction(7, 8);;
        val r2 : Rational.rational = Rational.Fraction (7, 8)
        # let r3 = Rational.add(r1, r2);;
        val r3 : Rational.rational = Rational.Fraction (37, 24)

In the interpreter, we can give the open command to add all of the defitions from the Rational module to the current environment, which is like giving an import command in Java:

        # open Rational;;
        # let r4 = add(r1, r3);;
        val r4 : Rational.rational = Fraction (159, 72)

Someone pointed out that we should be reducing the result we get when we add two fractional numbers together. For example, if you were to add the rational numbers 1/8 with 1/4, our function will produce the rational number 12/32. Really this should be reduced to its lowest terms of 3/8.

How do we reduce a rational number? We find the greatest common divisor of the numerator and the denominator. We can compute the gcd as follows:

    let rec gcd(x, y) =
        if x < 0 || y < 0 then gcd(abs(x), abs(y))
        else if y = 0 then x
        else gcd(y, x mod y)

Using gcd, we were able to write a function to reduce a rational to its simplest form:

    let rec reduce_rational(r) =
        match r with
        | Whole(i) -> Whole(i)
        | Fraction(a, b) ->
            let d = gcd(a, b)
            in Fraction(a/d, b/d)

At that point we ran out of time, but I said we'd continue the discussion in the next lecture.

Stuart Reges

Last modified: Fri Apr 19 14:45:10 PDT 2024