Geometry Language Assignment

Credit

All credit for this assignment goes to Prof. Grossman and his team at UW.

Instructions

Set-up

For this assignment, you will complete and extend two implementations of an interpreter for a small “language” for two-dimensional geometry objects. An implementation in SML is mostly completed for you. An implementation in Ruby is mostly not completed. The SML implementation is structured with functions and pattern-matching. The Ruby implemented is structured with subclasses and methods, including some mind-bending double dispatch and other dynamic dispatch to stick with an OOP style even where your instructor thinks the functional style is easier to understand.

Language Semantics

Our “language” has five kinds of values and four other kinds of expressions. The representation of expressions depends on the metalanguage (SML or Ruby), with this same semantics:

• A NoPoints represents the empty set of two-dimensional points.
• A Point represents a two-dimensional point with an x-coordinate and a y-coordinate. Both coordinates are floating-point numbers.
• A Line is a non-vertical infinite line in the plane, represented by a slope and an intercept (as in y = mx + b where m is the slope and b is the intercept), both floating-point numbers.
• 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 (so four total floating-point numbers).
• An Intersect expression is not a value. It has two subexpressions. The semantics is to evaluate the subexpressions (in the same environment) and then return the value that is the intersection (in the geometric sense) of the two subresults. For example, the intersection of two lines could be one of:
  • NoPoints, if the lines are parallel
  • a Point, if the lines intersect
  • a Line, if the lines have the same slope and intercept (see the note below about what “the same” means for floating-point numbers)
• A Let expression 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 environment for evaluating the second subexpression.
• A Var expression is not a value. It is for using variables in the environment: We look up a string in the environment to get a geometric value.
• A Shift expression is not a value. It has a deltaX (a floating-point number), a deltaY (a floating-point number), and a subexpression. The semantics is to evaluate the subexpression and then shift the result by deltaX (in the x-direction; positive is “to the right”) and deltaY (in the y-direction; positive is “up”). More specifically, shifting for each form of value is as follows:
  • NoPoints remains NoPoints.
  • A Point representing (x, y) becomes a Point representing (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

Note on Floating-Point Numbers

Because arithmetic with floating-point numbers can introduce small rounding errors, it is rarely appropriate to use equality to decide if two floating-point numbers are “the same.” Instead, the provided code uses a helper function/method to decide if two floating-point numbers are “real close” (for our purposes, within .00001) and all your code should follow this approach as needed. For example, two points are the same if their x-coordinates are within .00001 and their y-coordinates are within .00001.

Expression Preprocessing

To simplify the interpreter, we first preprocess expressions. Preprocessing takes an expression and produces a new, equivalent expression with the following invariants:

• No LineSegment anywhere in the expression has endpoints that are the same as (i.e., real close to) each other. Such a line-segment should be replaced with the appropriate Point. For example in ML syntax, LineSegment(3.2,4.1,3.2,4.1) should be replaced with Point(3.2,4.1).
• Every LineSegment has its first endpoint (the first two real values in SML) to the left (lower x-value) of the second endpoint. If the x-coordinates of the two endpoints are the same (real close), then the LineSegment has its first endpoint below (lower y-value) the second endpoint. For any LineSegment not meeting this requirement, replace it with a LineSegment with the same endpoints reordered.

The SML Code

Most of the SML solution is given to you. All you have to do is add preprocessing (problem 1) and Shift expressions (problem 2). The sample solution added much less than 50 lines of code. As always, line counts are just a rough guide.

Notice 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 (so with 5 kinds of values there are 25 cases though some are handled together via pattern-matching). The surprisingly complicated part is the algorithm for intersecting two line segments.

The Ruby Code

Much of the Ruby solution is not given to you. To get you started in the desired way, we have defined classes for each kind of expression in our language, as well as appropriate superclasses. We have implemented parts of each class and left comments with what you need to do to complete the implementation as described in more detail in problems 3 and 4. The sample solution added about 200 lines of Ruby code, many of which were end. As always, line counts are just a rough guide.

Notice the Ruby code is organized around classes where each class has methods for various operations. All kinds of expressions need methods for preprocessing and evaluation. They are subclasses of GeometryExpression just like all ML constructors are part of the geom_exp datatype (though the GeometryExpression class turns out not to be so useful). The value subclasses also need methods for shifting and intersection and they subclass GeometryValue so that some shared methods can be inherited (in analogy with some uses of wildcard patterns and helper functions in ML).

Your Ruby code should follow these general guidelines:

• All your geometry-expression objects should be immutable: assign to instance variables only when constructing an object. To “change” a field, create a new object.
• The geometry-expression objects have public getter methods: like in the SML code, the entire program can assume the expressions have various coordinates, subexpressions, etc.
• Unlike in SML, you do not need to define exceptions since without a type-checker we can just “assume” the right objects are used in the right places. You can also use raise with just a string as appropriate.
• Follow OOP-style. In particular, operations should be instance methods and you should not use methods like is_a?, instance_of?, class, etc. This makes problem 4 much more difficult, which is the purpose of the problem.