Lecture:EML and Multimethods15-312: Foundations of Programming LanguagesJason Reed ([email protected])November 4, 20041 Object-Oriented ProgrammingThere are several aspects of the object-oriented programming style that a pro-ponent of it might point to as centrally important. It advocates achievingmodularity of programs through bundling all of the data and behavior ofsomething that can be thought of as an object; it encourages reuse of codethrough inheritance; it makes claims on abstraction by use of dynamic dis-patch. The way a message sent to an object is handled need not be knownby the outside world: the object itself ‘knows’ how to handle it.Programmers used to programming in a functional style in type sys-tems that support ML-style modules may well have different ideas aboutwhat constitutes a natural organization of code and data, and how best toreuse code. But even without getting into arguments about what ‘natural’means, we can at least point to one (somewhat) less controversial idiomthat many OO languages easily support, which is not as easily (or at leastnot in the same way) codable in a language like ML.2 Extensibility2.1The idea in question is data extensibility. In, for example, Java, suppose youdeclare an abstract class and some number of concrete classes.1abstract class Exp {// return result of substituting v// for x in this expressionExp subst(Exp v, Int x);}...class Apply extends Exp {Apply(Exp e1, Exp e2);... // implement subst}...class Fn extends Exp {Fn(Exp e);... // implement subst}... // more kinds of ExpHere Exp is the abstract class that sits at the top of a part of the class hi-erarchy that describes the syntax of some language of, perhaps a compiler.It declares methods for operations that the client of this code wants to per-form — substitution, for example. To describe the various possible waysof making an Exp, we create concrete subclasses of Exp, and implement itsmethods.That the language supports data extensibility is just the fact that if, at alater time, we decide that we want to expand the old datatype with a newconstruct, say IsHalting, then the changes we need to make to the oldcode consist of simply adding a new class, with new method implementa-tions:class IsHalting extends Exp {IsHalting(Exp e);... // implement subst}... // more kinds of ExpThe important things to notice here are that (a) the modifications are ‘alltogether’ in one place, in one file, and (b) they are not changes to existinglibrary code. As a client of library code that defines the datatype Exp, wemay extend it by adding new kinds of Exps in our own code.2In contrast, ML (with the exception of the exn type) requires that vari-ant datatypes give all of their branches at once, and does not permit exten-sion. Were we to implement the example above in ML, we would start withsomething likestructure Syntax :> SYNTAX =structdatatype exp = Apply of exp * exp| Fn of exp| ...val subst (e : exp, v : exp, x : int) = ...endTo add IsHalting, we would have to go in and actually change theoriginal datatype declaration:structure Syntax :> SYNTAX =structdatatype exp = Apply of exp * exp| Fn of exp| IsHalting| ...val subst (e : exp, v : exp, x : int) = ...endMoreover we would have to add another case to the function subst,and to any other functions that Syntax might define. Even worse, theremight be functions that take arguments of type exp outside the Syntaxstructure as well! The changes required to our code could be wildly discon-tiguous, spanning many files. Depending on how much attention the pro-grammer (or her coworkers) pay to eliminating all nonexhaustive matchwarnings from a programming project, it may be quite difficult to makesure all functions have been extended appropriately.2.2Java programmers can take data extensibility for granted, while ML pro-grammers find workarounds, or else just tolerate changing datatype decla-rations when they must, and hunting down function cases to extend. But3there is a sort of extensibility that ML hackers take for granted that Javahackers symmetrically must go to some pains to acheive: functional exten-sibility. If instead of adding new sorts of data to an existing program whatwe want to do is add new behavior to existing datatypes, then the difficultyof the task depends on what tools the languages gives us.Suppose for definiteness that we want to take our compiler above andadd an interpreter to it. In the ML case, we’re perfectly capable of writinga separate module with a function eval like so:structure Eval :> EVAL = structval eval (e : exp) = case e of(Apply(e1,e2)) => ...| (...) => ...endNote again the advantages we have here: (a) the modifications are ‘alltogether’ in one place, in one file, and (b) they are not changes to existinglibrary code. If we write a case for every branch of the type exp, then thefunction works on any exp that comes its way. The compiler can provideaccurate warnings as to whether our case analysis is nonexhaustive, redun-dant, or correct.If we want to do the same thing in Java, then we have at least two obvi-ous options, neither necessarily pleasant. One works only if we have accessto the original library, or to its authors. We can add ourselves, or beg theauthors to add, a new method to the superclass Exp, and implement it inall of the subclasses. This means making many changes in many scatteredplaces, and it is vulnerable to certain kinds of errors. We may implementthe method for a subclass C of Exp and forget to implement it for a subclassD of C: if the inherited code is not appropriate for D, then we have failedto make enough changes, but there is no way the compiler can tell us. If alibrary’s API changes because at one of its users’ behest, other users may besuddenly stuck with broken code because they don’t implement the newlyadded methods to the abstract superclass.The other apparent option is writing a static function which contains abig if-elseif-else full of instanceOf tests. Here we are again capa-ble of leaving out cases in ways the compiler can’t detect and sentencingourselves to unexpected runtime errors. Also, in the pursuit of functionalextensibility, we’ve thrown out convenient data extensibility, at least for thepurpose of this one new function. For if we create a new class later, we can-not implement its eval case as a method (nor will the compiler know that4we should implement eval for it all!) but instead we must hunt down themass of instanceOf tests in the static eval