code Subtyping, deductive programming, language design

Contents

Tasks

There are 3 tasks.

  • The first task practices subtyping concepts.
  • The second task explores the (very) basics of logic programming with Prolog.
  • The third task asks you to reflect briefly on a video about language design.

You are especially encouraged to pursue the Prolog tutorial and view/discuss the language design video with others.

1. Subtyping Practice (20 points)

This part includes conceptual questions to test your understanding of subtyping issues. Note:

  • The slides and reference on subtyping may be useful in answering these questions.
  • While it is not required to answer the questions, you are also free to write, compile, and run Java programs if you wish to experiment with real behavior and check your answers. To do this on the lab machines, use Emacs to edit a file like Something.java, javac Something.java to compile, then java Something to run the static void main(String[] args) method in the Something class.

Write your answers to this part in the file subtype.txt.

  1. Consider the following Java code extracted from our in-class Java examples about function/method subtyping.

    class Point {
    protected int x;
    protected int y; 
    public Point(int x, int y) {
        this.x = y;
        this.y = y;
    }
    public int getX() { return x; }
    public int getY() { return y; }
}

class ColorPoint extends Point {
    protected String color;
    public ColorPoint(int x, int y, String color) {
        super(x, y);
        this.color = color;
    }
    public String getColor() { return color; }
}

class A {
    Point shift(Point p) {
        return new Point(p.getX() - 10, p.getY() + 10);
    }
}

class B {
    ColorPoint shift(ColorPoint cp) {
        if (cp.getColor().equals("red")) {
            return new ColorPoint(cp.getX(), cp.getY() + 10, "blue");
        } else {
            return cp;
        }
    }
}

class C {
    Point shift(ColorPoint cp) {
        if (cp.getColor().equals("red")) {
            return new Point(cp.getX(), cp.getY() + 10);
        } else {
            return cp;
        }
    }
}

class D {
    ColorPoint shift(Point p) {
        return new ColorPoint(p.getX() - 10, p.getY(), "blue");
    }
}

    For each of the following, indicate whether the Java type system should allow the stated relationship between two classes by marking “safe” or “unsafe” and explain briefly why or why not as it relates to overriding of the shift method. To simplify your explanations, refer to earlier explanations wherever possible, e.g., “like A extends C” or “argument like A extends C, return like B extends A”.

    1. A extends B
    2. A extends C
    3. A extends D
    4. B extends A
    5. B extends C
    6. B extends D
    7. C extends A
    8. C extends B
    9. C extends D
    10. D extends A
    11. D extends B
    12. D extends C

  2. Now consider the following definition for a shiftAll method, which mutates the given Point or ColorPoint array to replace each element by a shifted version, using the shift method of one of the A, B, C, or D classes from above.

    void shiftAll(PointType[] points) {
    ShifterType shifter = new ShifterType();
    for (int i = 0; i < points.length; i++) {
        points[i] = shifter.shift(points[i]);
    }
}

    For a pair of classes X and Y, consider replacing PointType by X and ShifterType by Y. For example, “Point shifted by A” means this code:

    void shiftAll(Point[] points) {
    A shifter = new A();
    for (int i = 0; i < points.length; i++) {
        points[i] = shifter.shift(points[i]);
    }
}

    For each of the following pairs, indicate both (1) whether the Java type system accepts the given code and (2) whether running the given code could ever result in exceptions being raised. (Assume the points argument is a non-null array of non-null elements.) No explanation is required.

    1. Point shifted by A.
    2. Point shifted by B.
    3. Point shifted by C.
    4. Point shifted by D.
    5. ColorPoint shifted by A.
    6. ColorPoint shifted by B.
    7. ColorPoint shifted by C.
    8. ColorPoint shifted by D.

2. Prolog Exploration (20 points)

The goal of this task is to practice learning the basics of a (small but unfamiliar) new language quickly.

This task asks you to learn the basics of Prolog, a logic programming language that takes a rather different shape than any algorithmic programming language you have encountered. We will briefly survey basics in class (mainly in order to learn about one particular feature), but the core learning is up to you. Fortunately, the (core part of the) language is small and simple. You will need only its most basic features to complete the programming task. Approach this with an open mind. The language is simple, but it is very different than languages you have studied.

Tutorial

Follow the Learn Prolog Now! online book until you are able to complete the programming task below. Chapters 1-3 should probably suffice, but you may also find chapters 4, 6, and 10 interesting if you wish to extend the task further.

Alternatively, you may prefer Adventure in Prolog, where chapters 1-5 and 8 should suffice. (Chapters 10, 11, and 13 may be of interest for extensions.)

Even the Wikipedia article on Prolog may be enough for you to learn the basics required for the programming task.

Of course you are welcome to explore as much as you want or to take a demand-driven approach to learn just what is needed for the task at hand.

Using Prolog on the Lab Machines

SWI-Prolog is installed on the lab machines. To run a Prolog REPL, run swipl. To first load definitions from file.pl and then enter a REPL, run swipl file.pl. To exit the session, type Control-D.

When editing Prolog files, you may wish to use Emacs. Since Prolog and the better known Perl language share a common file extension (.pl), Emacs assumes .pl files are Perl files. To get syntax highlighting for Prolog, run M-x prolog-mode after opening a Prolog file. (See Emacs Basics for more.)

Programming Task

Below is a knowledge base of facts indicating edges in a directed acyclic graph (DAG) of buildings on the Wellesley campus. If you wish, feel free to extend this knowledge base with more edge facts, but be sure to preserve the DAG property to keep your later task simple.

edge(sci, green).
edge(green, founders).
edge(lulu, ksc).
edge(green, pendleton).
edge(founders, jewett).
edge(pendleton, jewett).
edge(jewett, davis).
edge(davis, lulu).
edge(sci, pendleton).
edge(obs, pendleton).
edge(mods, obs).
edge(mods, sci).
edge(sci, clapp).
edge(clapp, founders).
edge(clapp, jewett).

For example, thre is a route from SCI to Green Hall, there is a route from Green Hall to Founders Hall, etc.

Using this knowledge base, complete the following programming steps:

  1. Write one or more Prolog rules to define a relation path(Start, Finish) that gives all Start/Finish pairs such that one can begin at the Start, follow one or more edges in the maze DAG, and reach the Finish.

    More concretely, after defining your rule(s), we should be able to run a range for interesting queries. For example, we could query whether routes between certain buildings exist (hit return/enter after a true response):

    ?- path(sci, lulu).
true .

?- path(jewett, mods).
false.

    We could query for all possible routes through the maze. (Type ; after each result to get the next.)

    ?- path(X, Y).
X = sci,
Y = green ;
X = green,
Y = founders ;
...
X = sci,
Y = ksc ;
...

    We could also query what buildings are reachable from Clapp:

    ?- path(clapp, X).

    or from what buildings we could reach from Lulu:

    ?- path(X, lulu).

    Hint: you’ll need recursion. Think carefully about your base clause and recursive clause, as well as their order.

  2. Add new facts to define an isopen/1 predicate over buildings. For example, we might indicate that SCI and Clapp are open:

    isopen(sci).
isopen(clapp).

    You will want to define several more (but not all the buildings). Now, write pathopen/2, an updated version of path/2, that allows us to find all paths that visit only open buildings. (It’s winter and you might want to warm up as you go?)

  3. Optional extension: write rules for a pathlist(Start, Finish, Route) relation that is identical to path(Start, Finish), except that the new Route element of the triple is an ordered list representing the individual buildings that could be visited along one route from Start to Finish. This will require learning about Prolog lists.

3. Language Design (10 points)

Watch the video of Guy Steele’s 1998 talk on Growing a Language. The video is a little under an hour (at 1x speed). Follow along on the paper (included in the starter repository as steele.pdf), as the video (converted from late-90s VHS, complete with trippy intro music) unfortunately has occasional skips that lose a few words. You can read the paper without the video, but a key feature of the talk is better observed through the video (mainly the audio). You are especially encouraged to do this (and discuss) together with others.

Note while watching/reading

  • It may take a while (several minutes) to understand why the talk starts in an awkward and simplistic style. Be patient.
  • Recall the talk dates from the late 1990s. The introduction of “man,” “woman,” “person”, and accompanying pronouns at the opening of the talk may not match your understanding of these terms or their relation. Please bear with this to continue to the rest of the talk. It will become clear why these particular terms (and many others unrelated) were used (sometimes narrowly) as the talk progresses.

Response

Write a short paragraph in the file growing.txt reflecting on the reading and addressing the following questions:

  • What does Steele see as the main obstacle to effective programming in small core languages (like Lisp)? Large languages (like C++)?
  • How does Steele demonstrate his thesis in his delivery of the talk itself?
  • What overarching design goal does Steele put forth for the Java language?
  • Do you think this goal is applicable (or worth applying) only to Java, also to other object-oriented languages, or more broadly to many languages?

There is no help available in responding to these questions. Reflect briefly for yourself. There is a wide range of useful and interesting responses here. Find one of your own.

Optional extra reading (not required): What Orientation Should Ada Objects Take?

Read What Orientation Should Ada Objects Take? J. P. Rosen. Communications of the ACM, November 1992, Vol. 35, No. 11. (Included in the starter repository as rosen.pdf.)

This article discusses the Ada programming language, a programming language with a strong static type system and module system similar in some respects to the module system of ML. Ada was originally developed for high-consequence coding projects in the U.S. Department of Defense. No previous understanding of Ada is necessary to read this article. It mentions a couple Ada features, but you can get the core ideas from the article alone.

What is the essence of Rosen’s argument about the tensions between composition (with true abstract data types) and classification (via inheritance and encapsulation)? Do you see one as more important or useful than the other? Does your answer change depending on the kind of software you consider?

Submission

Submit: The course staff will collect your work directly from your hosted repository. To submit your work:

  1. Make sure you have committed your latest changes.

    $ git add ...
$ git commit ...

  2. Run the command cs251 sign to sign your work and respond to any assignment survey questions.

    $ cs251 sign

  3. Push your signature and your latest local commits to the hosted repository.

    $ git push

Confirm: All local changes have been submitted if the output of git status shows both:

  • Your branch is up to date with 'origin/master', meaning all local commits have been pushed
  • nothing to commit, meaning all local changes have been committed

Resubmit: If you realize you need to change something later, just repeat this process.