Programming Languages C - Week 2

OOP vs. Functional Decomposition

When implementing operations for a small expression language, we can compare OOP vs. functional decomposition. In functional programming, we typically break programs down into functions that perform some operation. in OOP we typically break programs down into classes that give behavior to some kind of data. Consider the following 2D matrix for a small expression language:

Functional Approach

In functional languages, the standard style is do to the following:

• Define a datatype for expressions with one constructor for each variant (in a dynamically typed language, we might not give the datatype a name in our program, but are still thinking in terms of the concept. Similarly, in a language w/o direct support for constructors, we might use sth. like lists).
• 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 a default for many variants, we can use wildcards.

This approach is really just procedural decomposition: breaking the problem down into procedures corresponding to each operation. This ML code shows the approach for our example:

exception BadResult of string

datatype exp =
         Int of int
         | Negate of exp
         | Add of exp * exp

fun eval e =
    case e of
        Int _ => e
      | Negate e1 => (case eval e1 of
                          Int 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 of
        Int i => Int.toString i
      | Negate e1 => "-(" ^ (toString e1) ^ ")"
      | Add(e1,e2) => "(" ^ (toString e1) ^ " + " ^ (toString e2) ^ ")"

fun hasZero e =
    case e of
        Int i => i=0
      | Negate e1 => hasZero e1
      | Add(e1,e2) => (hasZero e1) orelse (hasZero e2)

The Object-Oriented Approach

In object-oriented language, the standard style is the following:

• Define a class for expressions, with one abstract method for each operation. (in a dynamically typed language, we might not actually list the abstract mehtods in our program. 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 mthod definition in the superclass so that via inheritance we can avoid enumerating all the branches.

Note this approach is a data-oriented decomposition: breaking the problem down into classes corresponding to each data variant.

class Exp
  #could put default implementations or helper methods here
end
class Int < Exp
  attr_reader :i
  def initialize i
    @i = i
  end
  def eval

    self
  end
  def toString
    @i.to_s
  end
  def hasZero
    i==0
  end
end
class Negate < Exp
  attr_reader :e
  def initialize e
    @e = e
  end
  def eval
    Int.new(-e.eval.i) #error if e.eval has no i method (is not an Int)
  end
  def toString
    "-(" + e.toString + ")"
  end
  def hasZero
    e.hasZero
    en d
  end
  class Add<Exp
    attr_reader :e1, :e2
    def initialize(e1,e2)
      @e1 = e1
      @e2 = e2
    end
    def eval
      Int.new(e1.eval.i + e2.eval.i)
    end
    def toString
      "(" + e1.toString + " + " + e2.toString + ")"
    end
    def hasZero
      e1.hasZero || e2.hasZero
    end
  end

The Punch-Line

Functional decomposition breaks programs down into functions that perform some operation and oo decomposition breaks programs down into classes that give behaviour to some kind of data, basically deciding whether to lay out your program by “column” or “row”. It is often a matter of personal preference which style seems more natural to you. It also depends on what the software is about. For the example used here, functional style seems more natural, for problems like implementing graphical UIs, OOP is probably more natural (it is “more natural” to have operations for a kind of data (e.g. MenuBar) together rather than have the cases for doIfMouseIsClicked together (for MenuBar, TextBox, SliderBar, etc.).

Extending the Code with New Operations or Variants

If we later extend our program by adding new data variants or operations, the choice becomes less subjective. Consider the functional approach: Adding a new operation is easy: we can implement a new function w/o editing any existing code. E.g. this function creates a new expression that evaluates to the same result as its argument but has no negative constants:

fun noNegConstants e =
    case e of
        Int i => if i < 0 then Negate (Int(~i)) else e
      | Negate e1 => Negate(noNegConstants e1)
      | Add(e1,e2) => Add(noNegConstants e1, noNegConstants e2)

On the other hand, adding a new data variant, such as ‘Mult’ of exp * exp is less pleasant. We need to go back and change all our functions to add a new case. In a statically typed language, some help comes: after adding the Mult constructor, if our original code did not use wildcard patterns, then the type-checker will give a non-exhaustive pattern-match warning everywhere we need to add a case for Mult. Again the oo approach is exactly the opposite. Adding a new variant is easy: we can implement a new subclass withou editing any existing code. e.g. this ruby class adds multiplication expressions to our language:

class Mult < Exp
  attr_reader :e1, :e2
  def initialize(e1,e2)
    @e1 = e1
    @e2 = e2
  end
  def eval
    Int.new(e1.eval.i * e2.eval.i)
  end
  def toString
    "(" + e1.toString + " * " + e2.toString + ")"
  end
  def hasZero
    e1.hasZero || e2.hasZero
  end
end

On the other hand, adding a new operation is less pleasant. We need to go back and change all the classes. Again, we get some help through static type-checking.

Planning for extensibility

As seen above, functional decomposition allows new operations and oo decomposition allows new variants without modifying existing code and w/o explicitly planning for it. It is possible for both variants to support new operations when planning ahead and use (somewhat awkward) programming techniques.

For OOP, the “visitor pattern” is a common approach. This is often implemented using double dispatch, covered for other purposes below. For functional programming, we can define our datatypes to have an “other” possibility and our operations to take in a function that can process the “other data”. Here’s the idea:

datatype 'a ext_exp =
         Int of int
         | Negate of 'a ext_exp
         | Add of 'a ext_exp * 'a ext_exp
         | OtherExtExp of 'a

fun eval_ext (f,e) = (* notice we pass a function to handle extensions *)
    case e of
        Int i => i
      | Negate e1 => 0 - (eval_ext (f,e1))
      | Add(e1,e2) => (eval_ext (f,e1)) + (eval_ext (f,e2))
      | OtherExtExp e => f e

With this approach, we could create an extension supporting multiplications by instantiating ‘a with exp * exp, passing eval_ext the function (fn (x,y) => eval_ext(f,e1) * eval_ext(f,e2)) and using OtherExtExp(e1,e2) for multiplying e1 and e2. Notice that is does not work to wrap the original datatype in a new datatype like this:

datatype myexp_wrong =
         OldExp of exp
         | MyMult of myexp_wrong * myexp_wrong

This approach does not allow, for example, a subexpression of an Add to be a MyMult.

Binary Methods with Functional Decomposition

With operations taking two (binary) or more (n-ary) variants as arguments, we often have many many cases. With functional decomposition all these cases are still covered in a function; OOP is a bit more cumbersome.

Suppose we add string values and rational-number values to our expression language. Change the meaning of ADD expressions to the following:

• If args are ints or rationals, do the arithmetic.
• If either arg is a string, convert the other arg to a string and return concat of strings.

So it is an error to have a subexpression of Negate or Mult evaluate to a String or Rational, but the subexpressions of Add can be any kind of value in our language: int, string or rational.

The interesting change is the Add case of eval. We now have to consider 9 (3*3) subcases, one for each combination of values produced by evaluating the subexpressions.

fun eval e =
    case e of
      (*...*)
      | Add(e1,e2) => add_values (eval e1, eval e2)
(*...*)

fun add_values (v1,v2) =
    case (v1,v2) of
        (Int i, Int j) => Int (i+j)
      | (Int i, String s) => String(Int.toString i ^ s)
      | (Int i, Rational(j,k)) => Rational(i*k+j,k)
      | (String s, Int i) => String(s ^ Int.toString i)
      | (String s1, String s2) => String(s1 ^ s2)
      | (String s, Int i) => String(s ^ Int.toString i ^ "/" ^ Int.toString j)
      | (Rational _, Int _) => add_values(v2,v1)
      | (Rational(i,j), String s) => String(Int.toString i ^ "/" ^ Int.toString j ^ s)
      | (Rational (a,b), Rational(c,d)) => Rational (a*d+b*c,b*d)
      | _ => raise BadResult "non-values passed to add_values"

Notice add_values is defining all 9 entries in this 2-D grid for how to add values in our language. One common source of redundancy is commutativity, i.e. the order of values does not matter. In the above, there is only one such case: adding an int and a rational is the same as adding a rational and an int.

Binary Methods in OOP: Double Dispatch

The first step in OOP is adding classes (MyString and MyRational) and have them implement all the existing methods, just like with adding Mult previously. That leaves revising the eval method of the Add class.

def eval
  Int.new(e1.eval.i + e2.eval.i)
end

We could replace this method body with code like our add_values helper function in ML, but helper functions like this are not OOP style. We expect add_values to be a method in the classes that represent values in our language. An Int, MyRational or MyString should know how to add itself to another value. So in Add we write:

def eval
  e1.eval.add_values e2.eval
end

This is a good start and obligates us to have add_values methods in the classes Int, MyRational and MyString. By doing this, we nicely divide our work into three pieces using dynamic dispatch depending on the class of the object taht e1.eval returns, i.e. the receiver of the add_values call in the eval method in Add. But each of these 3 needs to handle three of the nine cases, based on the second arg. One approach would be to use run-time tests of the classes to include the three cases:

class Int
      ...
      def add_values v
        if v.is_a? Int
                   ...
        elsif v.is_a? MyRational
                      ...
        else
        ...
        end
      end
end
class MyRational
      ...
      def add_values v
        if v.is_a? Int
                   ...
        elsif v.is_a? MyRational
                      ...
        else
        ...
        end
      end
end
class MyString
      ...
      def add_values v
        if v.is_a? Int
                   ...
        elsif v.is_a? MyRational
                      ...
        else
        ...
        end
      end
end

While this approach works, it is really not OOP. It is a mix of oo decomposition (dynamic dispatch) and functional decomposition (is_a?). There is nothing wrong with that, but it is not fully OOP.

Here is how we go about a full OOP approach: Inside our 3 add_values w eneed to know the class of the arg v. The strategy is to replace the “need to know” with calling a method on v instead. So we should tell v to do the addition passing self. This technique is called double dispatch:

class Int
      ...
      def add_values v #first dispatch
        v.addInt self
      end
  def addInt v # second dispatch: v is Int
    Int.new(v.i + i)
  end
  def addString v #second dipsatch: v is MyString
    MyString.new(v.s + i.to_s)
  end
  def addRational v
    MyRational.new(v.i+v.j*i,v.j)
  end
end
class MyString
  def add_values v # first dispatch
    v.addString self
  end
  def addInt v # second dispatch: v is Int
    MyString.new(v.i.to_s + s)
  end
  def addString v # second dispatch: v is MyString
    MyString.new(v.s + s)
  end
  def addRational v # second dispatch: v is MyRational
    MyString.new(v.i.to_s + "/" + v.j.to_s + s)
  end
end
class MyRational
      ... # other methods not related to add_values
      def add_values v # first dispatch
        v.addRational self
      end
  def addInt v # second dispatch
    v.addRational self # reuse computation of commutative operation
  end
  def addString v # second dispatch: v is MyString
    MyString.new(v.s + i.to_s + "/" + j.to_s)
  end
  def addRational v # second dispatch: v is MyRational
    a,b,c,d = i,j,v.i,v.j
    MyRational.new(a*d+b*c,b*d)
  end

We now have our 9 cases for addition in 9 different methods:

• The addInt method in Int is for when the left operand to addition is an Int (in v) and the right operand is an Int (in self)
• The addString method in Int is for when the left operand to addition is a MyString (in v) and the right operand is an Int (in self)

And so on…

Optional Notes:

• OOP Languages with multimethods do not require the manual double dispatch.
• Statically typed languages like Java do not get in the way of the double-dispatch idiom. In fact needing to declare method argument and return types as well as indicating in the superclass the methods that all subclasses implement can make it easier to understand what is going on.

Optional: Multimethods

Not all OOP languages require the double-dispatch pattern to implement binary operation in a OOP style. multimethods or multipe dispatch to the rescue. Here, the classes Int, MyString and MyRational could each define three methods all named add_values (so we would have 9 methods called add_values). Each method would indicate the class it expects for its arg. Then e1.eval.add_values e2.eval would pick the right one of the 9 at run-time.

Multiple Inheritance

THe essence of OOP is inheritance, overriding and dynamic dispatch. Let us now discuss 3 related but distinct ideas:

• Multiple inheritance: Languages with multiple inheritance let one class extend multiple other classes. It is the most powreful option, however, some semantic problems arise. Java and Ruby do not have multiple inheritance, C++ does.
• Mixins: Ruby allows a class to have one immediate superclass but any number of mixins. Becuase a mixin is “just a pile methods”, many of the semantic problems go away. Mixins do not help with all situations where you want multiple inheritance, but they have some excellent uses. In particular, elegant uses of mixins typically involve mixin methods calling methods that they assume are defined in all classes that include the mixin.
• Java and C#-style interfaces: Java and C# classes have one immediate superclass but can “implement” any numbre of interfaces. Interfaces do not provide behaviour - they only require that certain methods exist; they are fundamentally about type-checking, so there is very little reason for them in a language like Ruby. C++ does not have interfaces because inheriting a class with all “abstract” methods accomplishes the same thing.

Consider 2 examples where multiple inheritance is potentially useful:

• Consider a Point2D class with subclasses Point3D and ColorPoint. To create a ColorPoint3D class, it would semem natural to have two immediate superclasses.
• Consider a Person class with subclasses Artist and Cowboy. To create an ArtistCowboy, it would seem natural again to have two immediate superclasses. Note, however, that both the Artist class and the Cowboy class have a method “draw” that have very different behaviours.

W/o multiple inheritance, you end up copying code here. With multiple inheritance, we have to decide what it means. What does it mean, if two of the immediate superclasses have the same fields or methods. With multiple inheritance, our class hierarchies can transform from trees into diamonds.

This can lead to conflicts, consider the draw example: at the very least we need expressions using super to indicate which superclass is intended. But this is not necessarily the only conflict. Suppose the Person class has a pocket field that artists and cowboys use for different things. Then perhaps an ArtistCowboy should have two pockets.

But if you look at our ColorPoint3D example you would reach the opposite conclusion. Here both Point3D and ColorPoint inherit the notion of x and y from a common ancestor, but we certainly do not want a ColorPoint3D to have two x methods or @x fields.

Mixins

GGMixins are somewhere between multiple inheritance and interfaces. They provide actual code to classes that include them, but they are not classes themselves, so you cannot create instances of them.

To define a Ruby mixin, we use the keyword module instead of class, e.g.:

module Color
  attr_accessor :color
  def darken
    self.color = "dark" + self.color
  end
end

This mixin defines 3 methods, color, color= and darken. A class definition can include these methods by using the include keyword and the name of the mixin. E.g.:

class ColorPt < Pt
  include Color
end

This defines a subclass of Pt that also has the three methods defined by Color. This is not necessarily good style. First, our initialize does not create the @color field, so we are relying on clients to call color= before they call color or they will get nil back. So overriding initialize is probably a good idea. Second, mixins that use instance variables are stylistically questionable. As you might expect in Ruby, the instance variables they use will be part of the object the mixin is included in. So if there is a name conflict with some intended-to-be separate instance variabl defined by the class the two separate pieces of code will mutate the same data.

Now that we have mixins, we also have to reconsider our method lookup rules. We have to choose something and this is what Ruby chooses: If obj is an instance of class C and we send message m to obj:

• First look in the class C for a definition of m

• Next look in mixins included in C

• Next look in C’s superclass

• Next look in C’s superclass’ mixins

• Next look in C’s super-superclass

• etc.

  Many of the elegant uses of mixins do the following strange-sounding thing: They define methods that call other methods on self that are not defined by the mixin. Instead the mixin assumes that all classes that include the mixin define this method. E.g. consider this mixin that lets us “double” instances of any class that has + defined:

  module Doubler
    def double
      self + self #uses self's +message, not defined in Doubler
    end
  end

  If we include Doubler in some class C and call double on an instance of the class, we will call the + method on the instance, getting an error ifit is not defined .BUt if + is defined, everything works out. So now we can ieasily get the convenience of doubling just by defining + and including the Doubler mixin. E.g.:

  class AnotherPt
    attr_accessor :x, :y
    include Doubler
    def + other #add two points
      ans = AnotherPt.new
      ans.x = self.x + other.x
      ans.y = self.y + other.y
      ans
    end
  end

  Now instance of AnotherPt have double methods that do what we wnat. We could even add double to classes that already exist:

class String
  include Doubler
end

The same idea is used a lot in Ruby with Enumerable and Comparable. Comparable provides methods , !, >, >=, < and <=, all of which assume the class defines <=>. What <=> needs to do is return a negative number if its left arg is less than its right, 0 if equal and a positive number if the left arg is greater than the right. So now a class does not have to dfeine all these comparisons - if just defines <=> and includes Comparable:

class Name
  attr_accessor :first, :middle, :last
  include Comparable
  def initialize(first,last,middle="")
    @first = first
    @last = last
    @middle = middle
  end
  def <=> other
    l = @last <=> other.last # <=> defined on strings
    return l if l != 0
    f = @first <=> other.first
    return f if f != 0
    @middle <=> other.middle
  end
end

Defining methods in Comparable is easy, but we certainly would not want to repeat the work for every class that wants comparisons, e.g. the > method is just:

def > other
  (self <=> other) > 0
end

The Enumerable module is where many of the useful block-taking methods that iterate over some data structure are defined. Examples are any?, map, count and inject. They are all written assuming the class has the method each defined. So a class can define each include the Enumerable mixin and have all these methods.

class MyRange
  include Enumerable
  def initialize(low,high)
    @low = low
    @high = high
  end
  def each
    i = @low
    while i <= @high
      yield i
      i = i+1
    end
  end
end

Now we can write code like MyRange.new(4,8).inject {|x,y| x+y} or MyRange.new(5,12).count {|i| i.odd?}. Note that the map method in Enumerable always returns and instance of Array. After all it does not know how to produce in instance of any class, but it does know how to produce an array containing one element for everything produced by each. We could define it in the Enumerable mixin like this:

def map
  arr = []
  each {|x| arr.push x}
  arr
end

Java and C# Style Interfaces

An interface is just a list of methods and each method’s argument types and return type. A class type-checks only if it actually provides all the methods of all the interfaces it claims to implement. An interface is a type, so if a class C implements interface I, then we can pass an instance of C to a method expecting an argument of type I, for example. Interfaces are close to the idea of duck typing than just using classes as types, but a class has some interface type only if the class definition explicitly says it implements the interface.

Because interfaces do not actually define methods, less problems occur. If two interfaces have a method-name conflict, it does not matter - a class can still implement them both. If two interfaces disagree on a method’s type, then no class can possibly implement them both but the type-checker will catch that.

In a dynamically typed language, there is really little reason to have interfaces. We can already pass any object to any method and call any method on any object. It is up to us to keep track in our hea what objects can respond to what messages. The essence of dynamic typing is not writing down this stuff.

Bottom line: Implementing interfaces does not inherit code; it is purely related to type-checking in statically typed languages like Jave and C#. Ruby does not need interfaces.

Optional: Abstract Methods

Often a class definition has methods that call other methods that are not actually defined in the class. It would be an error to create instances of such a class and use the methods such that “method missing” errors occur. So why define such a class? Because its entire point is to be subclassed and have different subclasses define the missing methods in different ways, relying on dynamic dispatch for the code in the superclass to call the code in the subclass. This much works just fine in Ruby - you can have comments indicating that certain classes are there only for the purpose of subclassing.

The situation is more interesting in statically typed languages. In these languages, the purpose of type-checking is to prevent “method missing” errors, so when using this technique we need to indicate that instances of the superclass must not be created. In Java/C# such classes are called abstract classes. We also need to give the type of any methods that (non-abstract) subclasses must provide. Theser are “abstract methods”. Thanks to subtyping in these languages, we can expressions with the type of the superclass and know that at run-time the object will acutally be one of the subclasses. Furthermore, stype-checking ensures the object’s class has implemented all the abstract methods, so it is safe to call these methods. in C++, abstract methods are called “pure virtual methods” and serve much the same purpose.

There is an interesting parallel between abstract methods and higher-order functions. In both cases the language supports a programming pattern where some code is passed other code in a flexible and resuable way. In OOP different subclasses can implement an abstract method in different ways and code in the superclass via dynamic dispatch, can then uses these different implementations. With higher-order functions, if a function takes another as an argument, different callers can provide different implementations that are then used in the function body.

Languages with abstract methods and multiple inheritance (e.g. C++) do not need interfaces. Instead we can just use classes that have only abstract methods in them like they are interfaces and have classes implementing these “interfaces” just subclass the classes. This subclassing is not inheriting any code exactly because abstract ethods do not define methods. With multiple inheritance, we are not “wasting” our one superclass with this pattern.

DONE HW 7

Complete and extend two implementations of an interpreter for a small “language” for 2D geometry objects. An implementation in SML is mostly completed, an implementation in Ruby mostly not. SML is structured with functions and pattern-matching. Ruby is structured with subclasses and methods, including some mind-bending double dispatch and other dynamic dispatch to stick with an OOP style.

Language Semantics

Our “language” has five kinds of values and four other kinds of expressions. The representation of expressions depends on the metalanguage with the same semantics:

• A NoPOints represents the empty set of 2D points

• A Point represents a 2D point with an x- and y-coordinate. Both are floats.

• A Line is a non-vertical infinite line in the plane, represented by a slope and an intercept (as in y = mx +b), both floats.

• A VerticalLine is an infinite vertical line in the plane, represented by its x-coordinate.

• A LineSegment is a (finite) line segment, represented by the x- and y-coordinates of its endpoints.

• An Intersect expression is not a value. It has two subexpressions. The semantics is to evaluate the subexpressions (in the same env) and then return the value that is intersection of the two subresults. E.g. the intersection of two lines could be one of:

  • NoPoints if lines are parallel
  • A Point if the lines intersect
  • a Line, if the lines have the same slope and intercept

• A Let expressions is not a value. It is like let-expressions in other languages we have studied: The first subexpression is evaluated and the result bound to a variable that is added to the env for evaluating the second subexpression.

• A Var expression is not a value. It is for using variables in the env: we look up a string in the env t oget a geometric value.

• A Shift expression is not a value. It has a deltaX, a deltaY and a subexpression. The semantics is to evaluate the subexpression and then shift the result by deltaX and deltaY as follows:

  • NoPoints remains NoPoints
  • A Point representing (x,y) becomes a Point (x + deltaX, y + deltaY)
  • A Line with slope m and intercept b becomes a Line with slope m and an intercept of b + deltaY − m · deltaX .

  – A VerticalLine becomes a VerticalLine shifted by deltaX ; the deltaY is irrelevant. – A LineSegment has its endpoints shift by deltaX and deltaY .

A Point on Floats

Arithmetics with floats can introduce small rounding errors, so the provided code uses a helper function to decide if two floats are “really close” (within .00001) and all code should follow this approach. Two points are the same if their x-coordinates are within 0.00001 and their y-coordinates are within .00001

Expression Preprocessing

To simplify the interpreter, expressions are preprocessed:

• No LineSegment anywhere in the expression has endpoints that are the same as each other. Such a line-segment should be replaced with the appropriate Point. For example, LineSegment (3.2,4.1,3.2,4.1) should be replaced with Point(3.2,4.1)
• Every LineSegment has its first endpoint to the left (lower x-value) of the second one. If the x-coordinates are the same (real close), then the LineSegment has its first endpoint below (lower y-value) the second endpoint. For any LineSegement not satisfying these requirements, replace with a LineSegment with the same endpoints reordered.

SML Code

Most of the sml code is given to you. All you have to do is add preprocessing and Shift expressions. This could be done in less than 50 lines of code. The SML code is organized around a datatype-definition for expressions, functions for the different operations and pattern-matching to identify different cases. The interpreter eval_prog uses a helper function intersect with cases for every combination of geometric value (e.g. with 5 kinds of values there are 25 cases). The surprisingly complicated part is the algorithm for intersecting two line segments.

Ruby Code

Much of the ruby solution is not given. Sample solution is about 200 lines of code, many of which are end. The ruby code is organized around classes where each has methods for various operations. All kinds of expressoins need methods for preprocessing and evalutaion. They are subclasses of GeometryExpression just like all ML constructors are part of the geom_exp datatype. The value subclasses also need methods for shifting and intersection and they subclass GeometryValue so that some shared methods can be inherited. Your Ruby code should follow these general guidelines:

• All your geometry-expression objects should be immuatble: assign to instance variables only when constructin an object. To “change” a field, create a new object.
• The geometry-espression objects have public getter methods: like in the SML code, the entire program can assume the expression have various coordinates, subexpressions, etc.
• Unlike in SML, you do not need to define exceptions. You can use raise with just a string as appropriate
• Follow OOP. In particular you should not use methods like is_a?, instance_of?, class etc.

DONE The Problems

• Implement an SML function preprocess_prog of type geom_exp -> geom_exp to implement expression preprocessing as defined above. The idea is that evaluating program e would be done with eval_prog (preprocess_prog e, []) where [] is the empty list for the emtpy environment.
• Add shift expression as defined above to the SML implementation by adding the constructor Shift of real * real * geom_exp to the definition of geom_exp and adding appropriate branches to eval_prog and preprocess_prog. Do not change other functions. In particular, there is no need to change intersect because this function is used only for values in our geometry language and shift expressions are not geometry values.
• Complete the ruby implementation except for intersection which means skip for now additions to the Intersect class and, more importantl, methods related to intersection in other classes. Do not modify the code given to you. Follow this approach:

  • Every subclass of GeometryExpression should have a preprocess_prog method that takes on args and returns the geometry object that is the result of preprocessing self. To avoid mutation, return a new instance.

  • Every subclass of GeometryExpression should have an eval_prog method that takes one argument, the invironment (as an array whose elemets are two-elements arrays: a Ruby string (variable name) in index 0 and an object that is a value in our language in index 1). An in any interpreter, pass the appropriate environment when evaluating subexpressions. To make sure you handle both scope and shadowing correctly:

    • Do not ever mutate an environment. Create a new one as neede instead. Be careful what methods you use on arrays to avoid mutations.
    • The eval_prog method in Var is given to you. Make sure the environments you create work correctly with this definition.

    The result of eval_prog is the result of “evalutating the expression represented by self” so as we expect with OOP that cases of ML’s eval_prog are spread among our classes.

  • Every subclass of GeometryValue should have a shift method that takes 2 args dx and dy and returns the result of shifting self by dx and dy. In other words, all values in the language know how to shift themselves to create new objects. Hence the eval_prog method in the Shift class should be very short.

  • Analogous to SML, an overall program e would be evaluated via e.preprocess_prog.eval_prog []

• Implement intersection in your Ruby solution following the directions here with double dispatch and a separate use of dynamic dispatch for the line-segemnt case. All the different cases in ML will appear somewhere in the Ruby solution, just arranged differently.
  • Implement preprocess_prog and eval_prog in the Intersect class. This is not difficult. This is because every subclass of GeometryValue will have an intersect method that knows how to intersect itself with another geometry value passed as an argument.
  • Every subclass of GeometryValue needs an intersect method, but these will be short. The arg is another geometry-value, but we do not know what kind. So we use double dispatch and call the appropriate method on the arg passing self to the method. For example the Point class has an intersect* method that calls intersectPoint with self.
  • So methods intersectNoPoints, intersectPoint, intersectLine, intersectVerticalLine, and intersectLineSegment defined in each of our 5 subclasses GeometryValue handle the 25 possible intersection combinations:

    • The 9 cases involving NoPoints are done for you. See the GeometryValue class.

    • Next to the 9 remaining cases involving combinations that do not involve LineSegment. Use double dispatch. 3 of these 9 cases can just use one of the other cases because intersection is commutative.

    • 7 cases remain where one value is a LineSegment and the other is not NoPoints. These cases are all “done” for you because all subclasses of GeometryValue inherit an intersectLineSegment method that will be correct. But is calls intersectWithSegmentAsLineResult which you need to implement for each subclass of GeometryValue:

      • It takes one arg, which is a line segment (in ML the var was a real*real*real*real, but here it will be an instance of LineSegment and you can use the getter methods as needed.)
      • It assumes that self is the intersection of (1) some not-provided geometry-value and (2) the line containing the segment given as an agr.
      • It returns the intersection of the not-provided geometry-value and the segment given as an arg.

      Together the 5 intersectWithSegmentAsLineResult methods you write will the implement the same algorithm as on lines 110-169 of the ML code

• Lack of Challenge Problem: Implement in Jave or C#.

Files

SML Code Ruby Code