Time Info

In Fall 2019, students self-reported spending a median of 6.0 hours on this assignment.

That version of the assignment shared 2 tasks with this one, but included a different 3rd task on subtyping, a topic that is not covered in Spring 2020.

Tasks

1. 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 a wide range of useful and interesting responses here. Find one of your own. The course staff will not provide assistance with this task.

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?

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. Fortunately, the (core part of the) language is small and simple. You will need only basic features to complete the programming tasks. 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 tasks below. Start with chapters 1-3. Chapters 4, 6, and 10 are also interesting and relevant depending on how far you take the tasks.

Alternatively, you may prefer Adventure in Prolog. Start with chapters 1-5 and 8. Chapters 10, 11, and 13 are also interesting and relevant depending on how far you take the tasks.

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

Using Prolog

SWI-Prolog is pre-installed in the course computing environments. To run a Prolog REPL, run swipl. To first load definitions from file.pl and then enter a REPL, use the command 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 Tasks

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:

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.
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 start at end at open buildings and visit only open buildings.
Write rules for a pathlist(Start, Finish, Route) relation (pathlist/3) 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.

Submission

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

Test your source code files one last time. Make sure that, at a minimum, submitted source code is free of syntax errors and any other static errors (such as static type errors or name/scope errors). In other words: the code does not need to complete the correct computation when invoked, but it must be a valid program. We will not grade files that do not pass this bar.
Make sure you have committed your latest changes.
```
$ git add ...
$ git commit ...
```
Run the command cs251 sign to sign your work and respond to any assignment survey questions.
```
$ cs251 sign
```
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.

Prolog Epilogue

Contents