5 Inheritance
5.1 Introduction
In this assignment you will explore the vagaries of inheritance. We separate inheritance from Objects because while there is widespread agreement on basic objects, there is significant disagreement about inheritance. Here you will explore one specific design, which is an amalgam of features from widely-used languages like Java, C++, Smalltalk (not SMoLtalk!), JavaScript, and Python. (It is not, however, any of those languages exactly, because they all contradict each other in key ways.)
5.2 Assignment
Traditionally, when there are many design alternatives, we use Mystery Languages: many implementations, and you use tests to tell them apart. However, we want you to do more than the minimal effort of distinguishing them. We also wan to emphasize the importance of testing programming languages implementations.
Therefore, in this assignment you will not be writing an interpreter. You will instead only write tests. We have provided a wheat and several chaffs, corresponding to standard mistakes one might make when implementing the language.Full disclosure: Many of the chaffs are based on mistakes we made when writing the wheat! For this assignment, therefore, we have especially high expectations of your testing quality. You may not catch every chaff, but you have to catch almost all of them. (As a rule-of-thumb: if you spend a half hour on the last chaff, it’s fine to give up.)
5.3 New Language Features
Objects can now extend (“inherit” from) other classes. When looking up a method in an object, when it is not found in that object, the lookup continues to the super-object, unless there is none (which results in an error).
We have added a primitive form of classes. A class is an object-maker. It takes zero or more initialization parameters (those given to a class constructor), which are in scope for of the class’s methods. When instantiating a class, we must supply that exact number of parameters (otherwise it’s an error). The class then makes an object with the methods declared in its body. These classes have no inheritance.
Finally, we have added classes with inheritance. When instantiating a class, it must in turn instantiate its superclass (which creates an object), which instantiates its superclass (which also creates an object) which… Thus, instanting classes-with-inheritance creates objects-with-inheritance.
For simplicity, unlike in languages like C++ and Python, we will have only single-inheritance.Why simple? Here’s Guido van Rossum explaining Python’s multiple inheritance design, which has even changed from version to version. Even he calls it “remarkably subtle”!
Also for simplicity, unlike in languages like Java, classes will be values. Therefore, we don’t have to create a separate way of naming and writing classes; they are just expressions in the language.
It is easy to miss that making classes expressions creates expressive power. We can, for instance, have a lam that takes a parameter, and returns a class whose superclass is that parameter: something you cannot do in Java. This functionality is sometimes called a mixin, and leads to more flexible program designs and more reusable class abstractions.
5.4 Testing Advice
A class with inheritance? It’s one construct, Michael. How long could it take, 10 minutes?Know your memes.
Passing the wheat should be easy. These constructs ought to work pretty much exactly as you expect.
Catching the wheats is where the fun is. Almost everything comes down to: In which scope should this expression be evaluated? There are a lot of expressions, and every one of them needs to be evaluated in some scope; and there are a lot of scopes. And if you’re not careful, you’ll evaluate them in the wrong scope.
Unfortunately, languages are notorious for not being very clear in their specification. After all, it’s obvious to the language’s designer what should happen, so they often don’t think to document it. Worse, in some (many?) languages, what should happen wasn’t decided with a lot of forethought; rather, what happened is whatever the first implementation did, and over time that just becomes the language’s definition.
In our case, we have thought very hard about the right scopes. We have embedded this into the reference implementation (the wheat). So, when in doubt, pose your question in the form of a test case to the wheat.
5.5 Grammar
<expr> ::= ... |
| (object/ext <expr> [<symbol> (<var> <var> ...) <expr>] ...) |
| (class [extends <expr>] |
{inits <name> ...} |
[{super <expr> ...}] |
{methods {<name> (<var> <var> ...) <expr>} ...}) |
| (new <expr> <expr> ...) |
5.6 Abstract Syntax
Since you have been given a parser that implements the concrete syntax, you shouldn’t need to work directly with the abstract syntax. Nevertheless, we provide it here for your convenience.
Note that between objects and classes, there are four different surface syntax terms, each with and without inheritance. This is to make it easier to catch syntax errors (which will greatly reduce frustrating debugging time). But at the abstract syntax level there are only two constructs; they use an Optionof to indicate whether or not there is inheritance. This reduces the number of concepts in the implementation, and the type system helps keep us straight.
(define-type Expr |
(e-num [value : Number]) |
(e-str [value : String]) |
(e-bool [value : Boolean]) |
(e-op [op : Operator] [left : Expr] [right : Expr]) |
(e-if [condition : Expr] [consq : Expr] [altern : Expr]) |
(e-lam [params : (Listof Symbol)] [body : Expr]) |
(e-app [func : Expr] [args : (Listof Expr)]) |
(e-var [name : Symbol]) |
(e-obj [parent : (Optionof Expr)] [methods : (Hashof Symbol Method)]) |
(e-call [obj : Expr] [method : Symbol] [args : (Listof Expr)]) |
(e-class [parent : (Optionof Expr)] |
[init : (Listof Symbol)] |
[super-args : (Optionof (Listof Expr))] |
[methods : (Hashof Symbol Method)]) |
(e-new [class : Expr] [args : (Listof Expr)])) |
5.7 Starter Code
See GitHub Classroom.