CSE341, Fall 2011, Lecture 23 SummaryStandard Disclaimer: This lecture summary is not necessarily a complete substitute for attending class,reading the associated code, etc. It is designed to be a useful resource for students who attended class andare later reviewing the material.This lecture compares procedural (functional) decomposition and object-oriented decomposition using theclassic example of implementing operations for a small expression language. It shows that the two approacheslargely lay out the same ideas in exactly opposite ways, and which way is “better” is either a matter of tasteor depends on how software might be changed or extended in the future. We then consider how bothapproaches deal with operations over multiple arguments, which in many object-oriented languages requiresa technique called double (multiple) dispatch in order to stick with an object-oriented style.The Basic Set-UpThe following problem is the canonical example of a common programming pattern, and, not coincidentally,is a problem we have already considered a couple times in the course. Suppose we have:• Expressions for a small “language” such as for arithmetic• Different variants of expressions, such as integer values, negation expressions, and addition expressions• Different operations over expressions, such as evaluating them, converting them to strings, or deter-mining if they contain the constant zero in themThis problem leads to a conceptual matrix (two-dimensional grid) with one entry for each combination ofvariant and operation:eval toString hasZeroIntAddNegateNo matter what programming language you use or how you approach solving this programming problem,you need to indicate what the proper behavior is for each entry in the grid. Certain approaches or languagesmight make it easier to specify defaults, but you are still deciding something for every entry.The Functional ApproachIn functional languages, the standard style is to do the following:• Define a datatype for expressions, with one constructor for each variant. (In a dynamically typedlanguage, we might not give the datatype a name in our program, but we are still thinking in terms ofthe concept. Similarly, in a language without direct support for constructors, we might use somethinglike lists, but we are still thinking in terms of defining a way to construct each variant of data.)• Define a function for each operation.• In each function, have a branch (e.g., via pattern-matching) for each variant of data. If there is adefault for many variants, we can use something like a wildcard pattern to avoid enumerating all thebranches.Note this approach is really just procedural decomposition: breaking the problem down into procedurescorresponding to each operation.1This ML code shows the approach for our example: Notice how we define all the kinds of data in one placeand then the nine entries in the table are implemented “by column” with one function for each column:exception BadResult of stringdatatype exp =Int of int| Negate of exp| Add of exp * expfun eval e = (* no environment because we don’t have variables *)case e ofInt _ => e| Negate e1 => (case eval e1 ofInt i => Int (~i)| _ => raise BadResult "non-int in negation")| Add(e1,e2) => (case (eval e1, eval e2) of(Int i, Int j) => Int (i+j)| _ => raise BadResult "non-ints in addition")fun toString e =case e ofInt i => Int.toString i| Negate e1 => "-(" ^ (toString e1) ^ ")"| Add(e1,e2) => "(" ^ (toString e1) ^ " + " ^ (toString e2) ^ ")"fun hasZero e =case e ofInt i => i=0| Negate e1 => hasZero e1| Add(e1,e2) => (hasZero e1) orelse (hasZero e2)The Object-Oriented ApproachIn object-oriented languages, the standard style is to do the following:• Define a class for expressions, with one abstract method for each operation. (In a dynamically typedlanguage, we might not actually list the abstract methods in our program, but we are still thinking interms of the concept. Similarly, in a language with duck typing, we might not actually use a superclass,but we are still thinking in terms of defining what operations we need to support.)• Define a subclass for each variant of data.• In each subclass, have a method definition for each operation. If there is a default for many variants,we can use a method definition in the superclass so that via inheritance we can avoid enumerating allthe branches.Note this approach is a data-oriented decomposition: breaking the problem down into classes correspondingto each data variant.This Java code1shows the approach for our example: Notice how we define all the operations in one place1We use the name toStrng instead of toString to avoid overriding the toString method in class Object.2(the abstract class) and then the nine entries in the table are implemented “by row” with one class for eachrow.abstract class Exp {abstract Value eval();abstract String toStrng();abstract boolean hasZero();}class Int extends Exp {public int i;Int(int i) {this.i = i;}Value eval() {return this;}String toStrng() {return "" + i;}boolean hasZero() {return i==0;}}class Negate extends Exp {public Exp e;Negate(Exp e) {this.e = e;}Value eval() {// we downcast from Exp to Int, which will raise a run-time error// if the subexpression does not evaluate to an Intreturn new Int(- ((Int)(e.eval())).i);}String toStrng() {return "-(" + e.toStrng() + ")";}boolean hasZero() {return e.hasZero();}}class Add extends Exp {Exp e1;Exp e2;Add(Exp e1, Exp e2) {this.e1 = e1;this.e2 = e2;}Value eval() {// we downcast from Exp to Int, which will raise a run-time error// if either subexpression does not evaluate to an Intreturn new Int(((Int)(e1.eval())).i + ((Int)(e2.eval())).i);3}String toStrng() {return "(" + e1.toStrng() + " + " + e2.toStrng() + ")";}boolean hasZero() {return e1.hasZero() || e2.hasZero();}}This Ruby code is similar, though we do not need to define abstract methods or insert type casts. (Even thesuperclass is unnecessary, but we leave it in for clarity and since in more complicated examples it is a goodplace to put helper methods.)class Exp# could put default implementations or helper methods hereendclass Int < Expattr_reader :idef initialize i@i = ienddef evalselfenddef [email protected]_senddef hasZeroi==0endendclass Negate < Expattr_reader :edef initialize e@e = eenddef evalInt.new(-e.eval.i) # error if e.eval has no i method (not an Int)enddef toString"-(" + e.toString + ")"enddef hasZeroe.hasZeroendendclass Add < Expattr_reader :e1, :e2def
View Full Document
Unlocking...