OO log, Prolog, Epilogue
- Assign: Tuesday, 3 December
- Due: 11:59pm Tuesday, 10 December
- Policy: Pair graded synthesis assignment
- Partner search: Find a partner here.
-
Code:
cs251 start logic
- Submit:
git commit
,cs251 sign
, andgit push
your completed code. - Reference:
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, thenjava Something
to run thestatic void main(String[] args)
method in theSomething
class.
Write your answers to this part in the file subtype.txt
.
-
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”.A extends B
A extends C
A extends D
B extends A
B extends C
B extends D
C extends A
C extends B
C extends D
D extends A
D extends B
D extends C
-
Now consider the following definition for a
shiftAll
method, which mutates the givenPoint
orColorPoint
array to replace each element by a shifted version, using theshift
method of one of theA
,B
,C
, orD
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 andShifterType
by Y. For example, “Point
shifted byA
” 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.Point
shifted byA
.Point
shifted byB
.Point
shifted byC
.Point
shifted byD
.ColorPoint
shifted byA
.ColorPoint
shifted byB
.ColorPoint
shifted byC
.ColorPoint
shifted byD
.
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:
-
Write one or more Prolog rules to define a relation
path(Start, Finish)
that gives allStart
/Finish
pairs such that one can begin at theStart
, follow one or more edges in the maze DAG, and reach theFinish
.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 ofpath/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?) -
Optional extension: write rules for a
pathlist(Start, Finish, Route)
relation that is identical topath(Start, Finish)
, except that the newRoute
element of the triple is an ordered list representing the individual buildings that could be visited along one route fromStart
toFinish
. 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:
-
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 pushednothing to commit
, meaning all local changes have been committed
Resubmit: If you realize you need to change something later, just repeat this process.