Programming Languages C - Week 1

Ruby Features most interesting for a PL Course

Ruby is purely object-oriented, i.e. all values are objects.
Ruby is class-based; every object is an instance of a class. Not all oo languages are class-based, e.g. Java.
Ruby has mixins; which strike a compromise between multiple inheritance (like in C++) and interfaces (Java). Every Ruby class has one superclass but can include any number of mixins, which can define methods.
Ruby is dynamically typed.
Ruby has many dynamic features
Ruby has convenient reflection: Built-in methods make it easy to discover at run-time properties about objects.
Ruby has blocks and closures: It is rare in Ruby to use an explicit loop since collection classes like ‘ARRAY’ define so many useful iterators.
Ruby is a scripting language: It means the language is engineered towar making it easy to write short programs, providing convenient access to manipulating files and strings with less concern for performance. Ruby does not require you to declare variables before using them.
Ruby is popular for web applications; particularly with the Ruby on Rails framework.

Rules of Class-Based OOP

All values are references to objects
Given an object, code “communicates with it” by calling its methods (or “sending a message”)
Each object has its own private state. Only an object’s methods can directly access or update this state.
Every object is an instance of a class
An object’s class determinces the object’s behaviour
Class and method definitions Since every object has a class, we need to define classes and then create instances of them:
```
class Foo
  def m1
      ...
  end

  def m2 (x,y)
         ...
  end

  def mn z
         ...
  end
end
```
Class names must be capitalized; they include method definitions. A method can take any number of args, including 0 and we have a variable for each argument. In the above example, m1 takes 0 args, m2 two and mn takes 1 arg. A method implicitly returns its last expression. Method definitions can also have defaults in which cas a caller can pass fewer actual arguments:
```
def myMethod (x,y,z=0,w="hi")
             ...
end
```
Calling methods The method call e0.m(e1, …, en) evaluates to e0,e1, …, en to objects. It then calls the method m in the result of e0, passing the results of e1, …, en as arguments. The parentheses ares options. To call another method on the same object as the currently executing method, you can write self.m(…). In OOP another common name for a method call is a message send. So we can say e0.m e1 sends the reult of e0 the message m with the argument that is the result of e1.
Instance variables An object has a class, which defines its methods; it also has instance variables which hold values (i.e. objects). Many languages use the term fields instead of instance variables for the same concept. To add an instance variable to an object, you just assign to it: if the instance variable does not already exist, it is created. All instance variables start with an @, e.g. @foo to distinguish them from local variables. Each object has its own instance variables, they are mutable. They are read from with @foo and written to with @foo = value. They are private to an object. Ruby also has class variables which are not private, but shared by all instances of the class, but still not accessible directly from objects of different classes. Class variables are written @@foo.
Constructing an object To create a new instance of class Foo, you write
```
Foo.new(...)
```
The call to Foo.new will create a new instance of Foo and calls the new object’s initialize method with all the args passed to Foo.new.
Expressions and local variables Most expressions in Ruby are actually method calls. Even e1 + e2 is just syntactic sugar for e1.+ e2. Another example is puts e. puts is a method in all objects, so this is just self.puts e. Not all expressions are method calls, i.e. conditions. Variables local to a method do not have to be declared: The first time you assign to x in a method will create the variable with the entire body as its scope. To use a local variable not yet defined throws a runtime error. But calling an instance variable not yet defined just returns the nil object.
Class Constants and Class Methods A class constant is a lot like a class variable, except that it starts with a capital letter instead of @@ and you should not mutate it and it is publicly visible. Outside of an instance of class C you can accessa constnat Foo of C with the Syntax C::Foo.
A class method is lika an ordinary method except it does not have access to any of the instance variables or methods, you can call it from outside the class c where it is defined with C.method_name args. The most common way to define a class method is this:
```
def self.method_name args
                     ...
end
```

Visibility and Getters/Setters

Methods can have different visibilities. The default is public, which means any object can all the method. There is also private allowing only the object itself to call the method. In-between is protected: a protected method can be called by any object that is an instance of the same class or any subclass.

You can specify the visibility of a method by putting the keywork between method definitions. Reading top-down, the most recend visibility holds for all methods until the next one is specified. To make the content of an instance variable available and/or mutable we can define getter and setter methods:

def foo
  @foo
end

def foo= x
  @foo = x
end

If the methods are public, any code can now access @foo indirectly. e.foo= bar is equivalent to e.foo = bar. The advantage here is that the underlying implementation of the method remains hidden and could change without clients ever knowing. You can also omit the setter to make sure that the instance variable is not mutated outside of the object. Because getters and setters are so common, there is a shorter syntax:

attr_reader :y, :z #getters
attr_accessor :x #getters and setters

If a method is private you can only call it as m or m(args). A call like x.m or x.m(args) would break visibility rules.

Syntax, Semantics and Scoping

Ruby has a fair number of quirks:

There are several forms of conditional expressions, including e1 if e2, which evaluates e1 only if e2 is true.

newlines are often significant:

if e1
  e2
else
  e3
end

would be

if e1 then e2 else e3 end

on one line.

Conditionals can operate on any object and treat every object as true with 2 exceptions: false and nil.
You can define a method with a name ending in =:
```
def foo= x
  @blah = x * 2
end
```
As expected you can wirte e.foo=(17) to change @blah to 34. You can also write e.foo = 17. This is syntactic sugar.
Everything in ruby is an object, including nil and the toplevel environment.

Duck Typing

“If it walks like a duck and quacks like a duck, then it’s a duck”. The class of an object passed to a method is not important so long as the object can respond to all the messages it is excpected to. E.g. consider this method:

def mirror_update pt
  pt.x = pt.x * -1
end

It is natural to view this as a method that must take an instance of a particular class Point. But it is not necessary for pt to be an instance of point provided it has methods x and x=. These need not even be getters and setters for @x. The x method just has to return some object that can respond to the * message with arg -1.

Duck typing can make code more reusable, allowing clients to make “fake ducks” and still use your code. It also has disadvantages.

Arrays

The Array class is very commonly used in ruby. In general an array is a mapping from numbers (indices) to objects. The syntax [e1, e2, e3, e4] creates a new array with 4 objects in it: the result of e1 is in index 0 and so on. There are other ways to create arrays: Array.new(x) creates an array of length x with each index mapped to nil. We can also pass blocks to the Array.new method: Array.new(5) {|i| -i} creates the array [0, -1, -2, -3, -4].

The syntax for getting and setting array elements is similar to many other languages. a[i] gets the ith element and a[i] = e sets the index to e. However, ruby arrays are even more flexible than in other languages:

An array can hold objects of different classes, e.g. [14, ‘hi’, false, 34]
Negative array indices are interpreted from the end of the array.
There are no array-bounds errors. For a[i], if a holds fewer than i+1 objects, the result will just be nil. Setting such an index can also be done: a[i]=e will grow a dynamically to hold i+1 objects, the last of which will be the result of e with nil objects filling up the array.
There are many methods for arrays, in fact loops are seldomly used in ruby.

For stacks, the Array class defines push and pop. The former takes an argument, grows the array by one index and places the arg there. The latter shrinks the array by one and returns the element at the last index. (last-in-first-out). The shift method removes the element at index 0, returns it and shifts all other values down one index. unshift puts an element at index 0 pushing all elements up one bit.

Passing Blocks

Ruby has while and for loops, but most Ruby code does not use them. Instead, many classes have methods that take blocks. These are almost like closures. E.g. integers have a times method that takes a block and executes it athe number of times given.

x = 3
x.times {puts "hi"}

This will print “hi” 3 times. Blocks refer to variables in scope where the block is defined. E.g., after the folllowing executes, y is bound to 10:

y = 7
[4,6,8].each {y += 1}

The each method takes a block and executes it for each element in an array. Typically, we would want the block to be passed each array element:

sum = 0
[4,6,8].each { |x|
  sum += x
  puts sum
}

Blocks are not objects. You cannot pass them as “regular” args to a method. Rather, any method can be passed either 0 or 1 blocks, separate from other args. The block is put to the right of the method call after any other argument. E.g. the inject method is like fold in ML and we can pass it the initial accumulator as a regular arg.

sum = [4,6,8].inject(0) { |acc,elt| acc + elt }

In addition to the braces syntax, you can write a block using do and end. This is generally considered better style for longer blocks. When calling a method that takes a block you should know how many args will be passed to the block when called. For the each method in Array, the answer is 1, but as the first exampe showed, you can ignore args.

Many collections have a variety of block-taking methods that look familiar to functional programmers, including map, select and filter. Other useful iterators include any?, all? and others.

While many use of blocks involve calling methods in the standard library, you can also define your own methods that take blocks. You can pass a block to any method. The method body calls the block using the yield keyword. E.g. this code prints “hi” 3 times.

def foo x
  if x
    yield
  else
    yield
    yield
  end
end
foo (true) {puts "hi"}
foo (false) {puts "hi"}

To pass args to a block, you put the arguments after the yield, e.g. yield 7 or yield(8, “str”).

An error will result if yield is used and no block was passed. Method can use the block_given? primitive to see if the caller provided a block. This is not used too often. Here is a recursive method that counts how many times it calls the block before the block returns a true result:

def count i
  if yield i
    1
  else 1 + (count(i+1) {|x| yield x})
  end
end

The odd thing is that there is no direct way to pass the caller’s block as the callee’s block arg. But we can create a new block {|x| yield x} and the lexical scope of the yield in its body will do the right thing.

The Proc Class

Block are not quite closures because they are not objects. We cannot store them, pass them as regular args, assign them to a variable, etc. Hence blocks are not “first-class values”.

However, ruby has also “real” closures: Proc has instances that are closures. The method call in Proc is how you apply the closure to args. for example x.call or x.call(3,4).

To make a Proc out of a block, you can write lamdba {…} where {…} is any block. Lambda is a method in class Object that creates a Proc out of a block it is passed.

Usually all we need are blocks, e.g.:

a = [3,5,7,9]
b = a.map {|x| x + 1}
i = b.count {|x| x >= 6}

But suppose we wanted to create an array of blocks, this would create an error:

c = a.map {|x| {|y| x >= y}} #syntax error

But we can use lambda to create an array of instances of Proc:

c = a.map {|x| lambda {|y| x >= y}}

Now we can send the call message to elements of the c array:

c[2].call 17
j = {|x| x.call(5)}

Hashes and Ranges

are two standard-library classes that are also very common, but a bit less common than arrays. A hash is like an array except the mapping is not from numeric indices to objects. Instead the mapping from (any) objects to objects. If a maps to b, we call a a key and b a value. Hashes can be created like this:

{"SML" => 7, "cRacket" => 12, "Ruby" => 42}
{:sml => 7, :cracket => 12, :ruby => 42}

We can get and set values in a hash using the same syntax as for arrays, where again the key can be anything, such as:

h1["a"] = "Found A"
h1[false] = "Found false"
h1["a"]
h1[false]
h1[42]

There are many methods defined on hashes. Useful ones include keys (return array of all keys), values (same for values) and delete (given a key remove it and its value from the hash. Hashes support many of the same iterators as arrays such as each and inject, but some take the keys and values as args.

A range represents a contiguous sequence of numbers, e.g. 1..100 represents integers 1,2,3, …, 100. We could use an array like Array.new(100) {|i| i} but ranges are more efficiently represented and as seen with 1..100 there is more convenient syntax.

Duck typing lets us use ranges in many places where we might naturally expect arrays. E.g:

def foo a
  a.count {|x| x*x < 50}
end

We might naturally expect foo to take arrays and calls like foo [3,5,6,7] work as expected. But we can pass to foo any object with a count method that expects a block taking one argument. so we can also do foo (2..10) which evaluates to 6.

Subclassing and Inheritance

Basic Idea and Terminology

If class C is a subclass of D, then every instance of C is also an instance of

C inherits the methods of D, i.e. they are part of C’s definition too. C can

extend by defining new methods that C has and D does not. And it can override methods by changing their definition. In Ruby this is much like in Java.

Every class in Ruby expect Object has one superclass. The classes form a tree where each node is a class and the parent is its superclass. Object is the root of the tree. This is called the class hierarchy. By the definition of subclassing, a class has all the method of all its ancestors in the tree.

Ruby Specifics:

A ruby class definition specifies a superclass with class `C < D … end` to define a new class C with superclass D. Omitting the D implies < Object.
Every object has a class method. A class is itself an object in Ruby. The class of a class is Class. This class defines a method superclass that returns the superclass
Every object also has methods is_a? and instance_of?. The method is_a? takes a class and returns true if the receiver is an instance of the given class or any subclass of it. The method instance_of? is similar but returns true only if the receiver is an instance exactly.

Example

Two-dimensional points and a subclass that adds a color:

class Point
  attr_accessor :x, :y
  def initialize(x,y)
    @x = x
    @y = y
  end
  def distFromOrigin
    Math.sqrt(@x * @x + @y * @y)
  end
  def distFromOrigin2
    Math.sqrt(x*x + y*y)
  end
end

class ColorPoint < Point
  attr_accessor :color
  def initialize (x,y,c="clear")
    super(x,y)
    @color = c
  end
end

Why subclassing?

Using subclassing in the way above is considered good style because it allows us to reuse much of our work. But subclassing is often overused in object-oriented programs. In Ruby, we can extend and modify classes with new methods. So we could simply change the Point class by replacing its initialize mehotd and adding getters/setters for @color. This would be appropriate only if every Point object, including instances of all other subclasses of Point should have a color or at least having a color would not mess up anything else in our program.

Second, we could just define ColorPoint “from scratch”, copying over or retyping the code from Point. In a dynamically typed language, the differene in semantics is small: is_a? with argument Poin will now return false for ColorPoint, otherwise they will work the same.

Third, we could have ColorPoint be a subclass of Object but have it contain an instance variable, call it @pt holding an instance of Point. Then it would need to define all of the methods defined in Point to forward the message to the object in @pt. Here are 2 examples, omitting all the other methods (x=, y, y=, distFromOrigin, distFromOrigin2):

def initialize(x,y,c="clear")
  @pt = Point.new(x,y)
  @color = c
end
def x
  @pt.x #forward the message to the object in @pt
end

This approach is bad style since again subclassing is shorter and we want to treat a ColorPoint as though it is a Point. In situations where you are making a new kind of data that includes a pre-existing kind of data as a separate sub-part of it this instance-variable approach is better style.

Overriding and Dynamic Dispatch

Now let’s consider a different subclass of Point which is for 3d points:

class ThreeDPoint < Point
  attr_accessor :z
  def initialize(x,y,z)
    super(x,y)
    @z = z
  end

  def distFromOrigin
    d = super
    Math.sqrt(d * d + @z * @z)
  end

  def distFromOrigin2
    d = super
    Math.sqrt(d * d + z * z)
  end
end

Here, the code-reuse advantage is limited to inheriting methods x, x=, y and y= as as using other methods in Point via super. We used overriding for distFromOrigin 1 & 2. It is not quite clear if this subclassing is good style. On the one hand, quite a bit of code can be reused. On the other hand, we could argue that a 3DPoint is not really a 2DPoint.

The argument against subclassing is made stronger if we have a method in Point like distance that takes another Point and computes the distance between the argument and self. If ThreeDPoint wants to override this method with one that takes another ThreeDPoint, then ThreeDPoint instances will not act like Point instances: their distance method will fail when passed an instance of Point.

Consider a much more interesting subclass of Point. Instances of this class PolarPoint behave equivalently to instances of Point except for the arguments to initialize, but instances use an internal representation in terms of polar coordinates (radius and angle):

class PolarPoint < Point
  def initialize(r,theta)
    @r = r
    @theta = theta
  end

  def x
    @r * Math.cos(@theta)
  end

  def y
    @r * Math.sin(@theta)
  end

  def x= a
    b = y
    @theta = math.atan(b/a)
    @r = Math.sqrt(a*a + b*b)
    self
  end

  def y= b
    a = y
    @theta = Math.atan(b/a)
    @r = Math.sqrt(a*a + b*b)
    self
  end

  def distFromOrigin
    @r
  end
end

Instances of PolarPoint do not have instance variables @x and @y; we override x, x=, y and y= so that clients cannot tell the iplementation is different: they can use instances of Point and PolarPoint interchangeably. The key point of this example is that the subclass does not override distFromOrigin2 but the inherited method works correctly. To see why, consider the definition in the superclass:

def distFromOrigin2
  Math.sqrt(x*x + y*y)
end

unlike the definition of distFromOrigin the method uses other method calls for the args to the multiplications. This will call the methods defined in PolarPoint and not the methods defined in Point.

This semantics goes by many names, including dynamic dispatch, late binding and virtual method calls.

Precise Definition of Method Lookup

The key distinguishing feature of OOP language constructs is what self is bound to in the environment when a method is called. The correct definition is what we call dynamic dispatch.

The essential question is given a call e0.m(e1, e2, …, en) what are the rules for “looking " up what method definition m we call. In Ruby the variable-lookup rules for local variables in methods and blocks are not too different from ML and cRacket. But we also have to consider how to look up instance variables, class variables and methdos. In all cases the answer depends on the object bound to self - and self is treated specially.

In any environment, self maps to some object which we think of as the current object. To look up an instance variable @x, we use the object bound to self. To look up a class variable @@x, we just use the state of the object bound to self.class instead.

In class-based OOP languages like Ruby, the rule for evaluating a method call like e0.m(e1,…,en) is:

Evaluate e0,e1,…en to values, i.e. objects obj0, …
Get the class of obj0. Every object knows its class at run-time.
Suppose obj0 has class A. If m is defined in A, call that method. Otherwise recur with the superclass of A to see if it defines m. Raise “method missing” error if neither A nor any of its superclasses define m.
We have now found the method to call. If the method has formal arguments (i.e. arg names or parameters, x1, x2, …, xn then the environment for evaluating the body will map x1 to obj1 x2 to obj2. But there is one more thing that is the essence of OOP and has no real analogy in fp: we always have self in the environment. While evaluating the method body, self is bound to obj0, the object that is the receiver of the message.

The binding of self in the callee as described is called “late-binding”, “dynamic dispatch” and “virtual method calls”. It is central to the semantics of Ruby and other OOP languages. It means that when the body of m calls a method on self (e.g. self.someMethod 34 or just someMethod 34) we use the class of obj0 to resolve someMethod and not necessarily the class of the method we are executing

Several points about this semantics:

Ruby’s mixins complicate the lookup rules a bit more
The semantics is quite a bit more complicated than ML/Racket calls. We have to treat the notion of self differently from everything else in the language.
Java and C# have static overloading on top of dynamic dispatch. In this case classes can have methods with the same name but taking different types (or numbers) of arguments. Here, one method overrides another only if its args have the same type and number.

Dynamic Dispatch vs. Closures

Consider this ML code that defines two mutually recursive functions:

fun even x = if x=0 then true else odd (x-1)
and odd x = if x=0 then false else even (x-1)

This creates two closures that both have the other in their environment. If we later shadow the even closure with sth. else:

fun even x = false

this will not change how odd behaves. When odd looks up even in the environment where odd was defined it will get the first function above. On the other hand suppose we wrote a better version of even like:

fun even x = (x mod 2) = 0

Now our odd is not benefiting from this implementation. In OOP we can use subclassing, overriding and dynamic dispatch to change the behaviour of odd by overriding even:

class A
  def even x
    if x==0 then true else odd(x-1) end
  end
  def odd x
    if x==0 then false else even(x-1) end
  end
end
class B < A
  def even x #changes B's odd too!
    x % 2 == 0
  end
end

Now (b.new.odd 17) will execute faster.

DONE HW 6

Overview

Four Ruby files are involved in setting up Tetris:

hw6provided.rb implements a simple but fully functioning Tetris game
In hw6assignment.rb, create a second game that is Tetris with some enhancements, described below.
Main starting point is the code in hw6runner.rb.
The code in hw6graphics.rb provides a simple graphics library. It is used by the game in hw6provided.rb. Your code can also use the classes and methods in hw6graphics.rb, except for the methods marked with comments as not to be called by student code. Your code cannot use the TK graphics library directly.

Your solution cannot modify any of the provided code. Use subclassing instead to reuse as much of the code as possible. Some copying will be necessary. The solution should not change any of the provided classes. Define subclasses that behave differently; the provided Tetris game should run wihtout change.

Enhancements

The player can press ‘u’ to make a falling piece rotate 180 degrees.
Add 3 pieces. (see pdf)
The player can press ‘c’ to cheat: If the score is less than 100, nothing happens. Else the player loses 100 points and the next piece that appears will be a single square. The piece after is again chosen randomly. Hitting ‘c’ multiple times should behave no differently than hitting it once.

Requirements

The game should have all the original features plus enhancements
The subclasses created must start with My followed by the name of the original class. Tetris would be MyTetris.
Do not add to or modify any classes defined in other files or the standard library.
Your board MyBoard must have a next_piece method that provides the same functionality that Board’s next_piece provides which is that it sets @current_block to the next piece that will fall, which might or might not be the cheat piece.
You must have a MyPiece class and it must define a class constance All_My_Pieces that contains exactly the ten “normal” pieces. It must not contain the cheat piece. It must be in the same format as the All_Pieces array in the provided code.
All the new pieces (incl. the cheat piece) must use the same format as the provided pieces. Hint: Be careful to have enough nesting in your arrays or the game might be almost imperceptibly incorrect.
Do not use the TK library directly in any way.

Advice

Work through the code methodically.
Sample solution is approx. 85 lines of code.
Some code copying will be necessary. The original code may not have functionality broken down into overridable methods the way we would want. That is fairly realistic.