Notes about Coursera "Programming Languages": https://www.coursera.org/course/proglang - part 3 (Ruby)

proglang.rb

Part 3

Introduction to Ruby {

	Our focus {
		Pure Object-Oriented
			no primitives (even numbers)

		Class-based
			Every object has a class that determines behavior (like Java)

		Mixins
			"enhanced interfaces"

		Dynamically-typed (like Racket)
		
		Reflection

		Has closures

		A good scripting language
			(because of syntax, semantics and scoping rules)
	}

	NOT out focus {
		
		string manipulation and regular expressions

		web framework (Ruby On Rails)		
	}

	Note: we could have used Smalltalk (many similaritie, less modern), Racket (which has classes)

	Basics:
		# this is a comment
		class MyClass ... end # class definition
		def my_method(x,y) ... end # method definition
		myObject = MyClass.new # object creation
		myObject.my_method(3,4) # method call, parens are optional (but recommended)
		self.my_method # call method on current object (like 'this' in Java) / self is implicit (optional)
		x=3 # local mutable variable
		new lines # either end-of-line or semi-colon ';''

		We ll use 'irb' (REPL) / 'ruby' (interpreter)
}

Classes and Objects {

	Rules of class-based OOP:
	 all values are objects
	 objects communicate via method calls aka messages
	 all objects have a class and a private state

	 Code {
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Classes and Objects

		class A
		  def m1
		    34
		  end

		  def m2 (x,y)
		    z = 7
		    if x > y 
		      false
		    else
		      x + y * z
		    end
		  end

		end

		class B
		  def m1
		    4
		  end

		  def m3 x
		    x.abs * 2 + self.m1
		  end
		end

		# returning self is convenient for "stringing method calls" (chaining calls)
		class C
		  def m1
		    print "hi "
		    self
		  end
		  def m2
		    print "bye "
		    self
		  end
		  def m3
		    print "\n"
		    self
		  end
		end

		# example uses (can type into irb)
		# here in a multiline comment, which is not well-known
		=begin
		a = A.new
		thirty_four = a.m1
		b = B.new
		four = b.m1
		forty_seven = B.new.m3 -17
		thirty_one = a.m2(3,four)

		c = C.new
		c.m1.m2.m3.m1.m1.m3
		=end
	}
}

Object state {

	method calls access / update object state (variables)

	Instance variables
	- are accessed via prefix '@'
	- contain nil if not initialized
	- can be set via 'initialize' method (that can have default argument) which is called after call to 'new'

	NB: it s a good style to initialize instance variables in 'initialize'

	Aliasing:
		x=y # creates an alias => aliases refer to the same object with same state

	Class variables:
		shared by all class instances
		syntax: prefixed by '@@'

	Class constants:
		public, should not be mutated
		syntax:
			- name start with capital letter
			- outer access: MyClass::MyConstant


	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Object State

		class A
		  def m1
		    @foo = 0
		  end

		  def m2 x
		    @foo += x
		  end

		  def foo
		    @foo
		  end

		end

		class B 
		  # uses initialize method, which is better than m1
		  # initialize can take arguments too (here providing defaults)
		  def initialize(f=0)
		    @foo = f
		  end

		  def m2 x
		    @foo += x
		  end

		  def foo
		    @foo
		  end

		end

		class C
		  # we now add in a class-variable, class-constant, and class-method

		  Dans_Age = 38

		  def self.reset_bar
		    @@bar = 0
		  end

		  def initialize(f=0)
		    @foo = f
		  end

		  def m2 x
		    @foo += x
		    @@bar += 1
		  end

		  def foo
		    @foo
		  end
		  
		  def bar
		    @@bar
		  end
		end

		# example uses 
		=begin
		x = A.new
		y = A.new # different object than x
		z = x # alias to x
		x.foo # get back nil because instance variable not initialized
		x.m2 3 # error because try to add with nil object
		x.m1 # creates @foo in object x refers to
		z.foo # remember, x and z are aliases
		z.m2 3
		x.foo
		y.m1
		y.m2 4
		y.foo
		x.foo

		w = B.new 3
		v = B.new
		w.foo + v.foo

		d = C.new 17
		d.m2 5
		e = C.new
		e.m2 6
		d.bar
		forty = C::Dans_Age + d.bar

		=end
}

Visibility {

	Visibility of instance variables:

		Hiding things is essential for modularity and abstraction
		- implementation can change later without external impact
		- allows "duck typing"

		Object state is always private
			(cannot write 'instance.@foo')
	
		Getters/setters:
			Name convention:
				# convention: getter has the same name as instance variable   
				def foo
					@foo
				end
				# convention: setter has the same name as instance variable + '=' suffix
				def foo= x
					@foo = x
				end

			Shorthand:
			 	# generate 'foo' getter   
				attr_reader :foo
				# generate 'bar' getter and setter
				attr_accessor :bar

	Visibility of methods:

		 3 visibilities:
		 - 'private'
		 - 'protected': for current class ans sub-classes
		 - 'public': anyone (= default visiblity)

		 It applies to subsequent method definitions.
		 example:
		 	def foo # public
		 	protected def bar ... # protected
		 	def baz ... # protected
		 	public def hello ... # public
}

A longer example {

	# Programming Languages, Dan Grossman, Jan-Mar 2013 
	# Section 7: A Longer Example

	# Note: Ruby 1.9 has its built-in rational ("Rational"), let's build our own
	class MyRational

	  def initialize(num,den=1) # second argument has a default
	    if den == 0
	      raise "MyRational received an inappropriate argument"
	    elsif den < 0 # notice non-english word elsif
	      @num = - num # fields created when you assign to them
	      @den = - den
	    else
	      @num = num # semicolons optional to separate expressions on different lines
	      @den = den
	    end
	    reduce # i.e., self.reduce() but private so must write reduce or reduce()
	  end

	  # first implementation of "to string"
	  def to_s 
	    ans = @num.to_s
	    if @den != 1 # everything true except false _and_ nil objects
	      ans += "/"
	      ans += @den.to_s 
	    end
	    ans
	  end

	  # second implementation of "to string" (with funny method + if syntax)
	  def to_s2 # using some unimportant syntax and a slightly different algorithm
	    dens = ""
	    dens = "/" + @den.to_s if @den != 1
	    @num.to_s + dens
	  end

	  # third implementation of "to string" (using '${}' aka interpolation)
	  def to_s3 # using things like Racket's quasiquote and unquote
	    "#{@num}#{if @den==1 then "" else "/" + @den.to_s end}"
	  end

	  # bang suffix is a conventional way to indicate mutating methods
	  def add! r # mutate self in-place
	    a = r.num # only works b/c of protected methods below
	    b = r.den # only works b/c of protected methods below
	    c = @num
	    d = @den
	    @num = (a * d) + (b * c)
	    @den = b * d
	    reduce
	    self # convenient for stringing calls
	  end

	  # a functional addition, so we can write r1.+ r2 to make a new rational
	  # and built-in syntactic sugar will work: can write r1 + r2
	  def + r
	    ans = MyRational.new(@num,@den)
	    ans.add! r
	    ans
	  end
	    
	protected  
	  # there is very common sugar for this (attr_reader)
	  # the better way:
	  # attr_reader :num, :den
	  # protected :num, :den
	  # we do not want these methods public, but we cannot make them private
	  # because of the add! method above
	  def num
	    @num
	  end
	  def den
	    @den
	  end

	private
	  def gcd(x,y) # recursive method calls work as expected
	    if x == y
	      x
	    elsif x < y
	      gcd(x,y-x)
	    else
	      gcd(y,x)
	    end
	  end

	  def reduce
	    if @num == 0
	      @den = 1
	    else
	      d = gcd(@num.abs, @den) # notice method call on number
	      @num = @num / d
	      @den = @den / d
	    end
	  end
	end

	# can have a top-level method (just part of Object class) for testing, etc.
	def use_rationals
	  r1 = MyRational.new(3,4)
	  r2 = r1 + r1 + MyRational.new(-5,2)
	  puts r2.to_s
	  (r2.add! r1).add! (MyRational.new(1,-4))
	  puts r2.to_s
	  puts r2.to_s2
	  puts r2.to_s3
	end
}

Everything is an Object {

	Everything is an object (even 'nil')
	All code are methods  (top-level methods are in 'Object' class which is inherited from all classes)
	Can call method on any object: will fail at runtime if not exists (dynamic "undefine error")

	Examples:
		3 + 4 # i.e. 3.+(4)
		-5.abs # => 5
		1.nonzero? # => 1
		0.nonzero? # => nil
		0.nil? # => false
		nil.nil? # => true
		nil == false # => true

	Reflection:
		Is often useful in REPL (and sometimes in production code)

		Examples:
		
		# list int methods:
		3.methods # [:to_s, ... :even ...]
		3.methods - nil.methods # list int methods that do not exist in 'nil'
		
		# class of instance/class:
		3.class # => Fixnum
		MyRational.class # => Class
}

Class Definitions are Dynamic {

	Classes can change while the program is running!
		=> can break abstractions / make programs hard to analyze
		=> can be useful for scripting / small programs (examples: modify default "to_s" for everything, add double method on integers)

	Note: adding/updating/deleting a method to a class immediately adds/updates/deletes it to all existing instances!

	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Class Definitions are Dynamic

		require_relative './127_example' # similar to ML's use

		# above line defines the MyRational class, but now we can change it

		class MyRational
		  def double
		     self + self 
		   end
		end

		class Fixnum
		  def double # add double to all integers
		    self + self
		  end
		end

		def m
		  42
		end

		class Object
		  def m 
		    43
		  end
		end

		# this one will crash irb
		# class Fixnum
		#   def + x
		#     42
		#   end
		# end
}

Duck Typing {

	"If it walks like a duck and quacks like a dug, it's a duck!"
	(or don't worry, it's like a duck)

	=> assume that object has method X, not that its class is Y
	+: more code reuse
	-: no code equivalence, callers may asume a lot about how callees are implemented

	examples:
		# update coordinates for mirror effect (not a very good usage of duck typing)
		# It can be applied to any object that has 'x=' and 'x' methods where result of 'x' has a '*' method
		# note: documentation does not matter, only code does! 
		def mirror_update pt 
			pt.x = pt.x *  (-1)
		end

		# a better example that can be applied to numbers, strings or our rationals
		def double x
			x + x
		end
}

Arrays {
	More flexible but less performant than in other languages
	cf. Array class
	
	a = [1,2,3,4]
	a[2] # get element at index i
	a[1] = 42 # set element at index to value
	a[1000] # => nil (does not fail!)
	a.size # => 4
	a[-1] # => 4 (negative index => start from the end)
	a[6] = 666 # a is now [1,2,3,4,nil,nil,666] pno problem! increment array size / set nil values if necessary
	a[7] + [true, false] # concatenate arrays
	a[7] | [true, false, 666] # concatenate arrays and remove duplicates

	# Array size can be dynamic
	s = if ... then 10 else 20 end
	Array.new(s) # size is dynamic, default value is nil
	Array.new(s) { 1 } # size is dynamic, default value is 1

	# Arrays can be used as stacks / queues via push/pop + shift/unshift
	a.push "foo" # [1,2,3,4,"foo"]
	a.pop # => "foo"

	# Aliases
	e = a + [] # a is different from e

	#  Slicing
	a[1,2] # => [2,3]

	# map
	a.each { |i| puts (i*i)}
}

Blocks {
	Almost like closures (the strangest Ruby feature, but a very convenient one!)

	Like closures, blocks:
	 - easy way to pass anonymous functions
	 - can take 0 or more arguments
	 - use lexical scope (block uses environement where it was defined)
	But, they have strange things:
	 - any method call can have 0 or 1 block (callee might ignore it / return a error / use it...)

	 Syntax:
	   { e } # block with no param
	   do e end # alternative (equivalent)
	   { |x| e } # block with 1 param
	   { |x,y| e } # block with 2 params

    Usage:
     used everywhere since standard lib use them intensivelly
     ex.:
     	Array.new, Arrays.each, Array.map (equivalent to Array.collect), Array.any?, Array.all?, Arrray.inject ("reduce"), Array.select ("filter") etc...
 	('for' loops are rarly used, BTW)
 		sequences: (0..4).each

	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Passing Blocks

		3.times { puts "hello" }

		[4,6,8].each { puts "hi" }

		i = 7
		[4,6,8].each {|x| if i > x then puts (x+1) end }

		a = Array.new(5) {|i| 4*(i+1)}
		a.each { puts "hi" }
		a.each {|x| puts (x * 2) }
		a.map  {|x| x * 2 } #synonym: collect
		a.any? {|x| x > 7 } 
		a.all? {|x| x > 7 } 
		a.all? # implicit are elements "true" (i.e., neither false nor nil)
		a.inject(0) {|acc,elt| acc+elt }
		a.select {|x| x > 7 } #non-synonym: filter

		def t i
		  (0..i).each do |j|
		    print "  " * j
		    (j..i).each {|k| print k; print " "}
		    print "\n"
		  end
		end

		t 9
}

Using blocks {
	Let s implement our function that use blocks

	Syntax:
	 'yield' / 'yield(arg)' # call block (fails if block is missing)
	 'block_given?' # check if block exists


	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Using Blocks

		class Foo
		  def initialize(max)
		    @max = max
		  end

		  def silly
		    yield(4,5) + yield(@max,@max)
		  end

		  def count base
		    if base > @max
		      raise "reached max"
		    elsif yield base
		      1
		    else
		      1 + (count(base+1) {|i| yield i}) # passing block requires re-wrapping it within {} 
		    end
		  end
		end

		f = Foo.new(1000)

		f.silly {|a,b| 2*a - b}

		f.count(10) {|i| (i * i) == (34 * i)}
}

Procs {
	Objects similar to blocks

	Blocks are second-class expression (you cannot return them) => limited, but very convenient
	Procs are first-class expression (full closure) => full power, but less easy to use (and not alwways needed)

	2 ways to make Procs objects:
	- (Object.)lambda
	Use 'call' method to call lambdas


	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Procs

		a = [3,5,7,9]

		# no need for Procs here
		b = a.map {|x| x + 1}

		i = b.count {|x| x >= 6}

		# need Procs here: want an array of functions
		c = a.map {|x| lambda {|y| x >= y} }

		# elements of c are Proc objects with a call method

		c[2].call 17

		j = c.count {|x| x.call(5) }
}

Hashes and ranges {

	Similar to arrays, very common.

	Hashes:
		Like arrays, but:
		- have keys
	  	- no natural ordering
	  	We often use a hash arguement instead of several arguments

   	 	h = { "key1" => "hello", false => 42 }
   	 	h["key1"] # "hello"
   	 	h["not-exists"] # nil
   	 	h.keys # ["key1",false]
   	 	h.values # ["hello",42]
   	 	h.each { |k,v| ... }

 	Ranges:
 	Like arrays, for continuous numbers
 		0..1000 # lazy sequence
 		(0..1000) # [0,1,2...,1000]

 	Good style to:
 	 - use ranges when possible
 	 - use hashes if non-numeric keys better represent data

	Similar methods:
		- Many methods exist only for one class (e.h. 'keys' only exists for hashes) => great for duck typing
		- Some methods are similar (e.g 'each', 'count', etc...)

	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Hashes and Ranges


		h1 = {}
		h1["a"] = "Found A"
		h1[false] = "Found false"
		h1["a"]
		h1[false]
		h1[42]
		h1.keys
		h1.values
		h1.delete("a")

		h2 = {"SML"=>1, "Racket"=>2, "Ruby"=>3}
		h2["SML"]

		# Symbols are like strings, but cheaper.  Often used with hashes.
		h3 = {:sml => 1, :racket => 2, :ruby => 3}

		# each for hashes best with 2-argument block

		h2.each {|k,v| print k; print ": "; puts v}

		# ranges
		(1..100).inject {|acc,elt| acc + elt}

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

		# duck typing in foo
		foo [3,5,7,9]
		foo (3..9)
}

Subclassing {
	Subclasses, inheritance and overriding

	Subclassing:
		syntax:
			class ColorPoint < Point
			super(...) # call superclass' initialize

		subclass
		 - inherits from all methods from superclass
		 - can override (part of or all of) them
		 - does not "inherit" fields (like in Java)

	 	warning: subclassing has nothing to do with "type inheritance", in Ruby

	 	reflection:
	 		Foo.class.superclass # returns superclass
	 		foo.is_a? Clazz # returns true if foo is an instance of Clazz (or a subclass)
	 		foo.instance_of? Clazz # returns true if foo is an exact instance of Clazz (and not of a subclass of Clazz)

	 		Beware: using class/is_a/instance_of is not very OOP / "duck-typing"-oriented

	 Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Subclassing

		class Point
		  attr_accessor :x, :y

		  def initialize(x,y)
		    @x = x
		    @y = y
		  end
		  def distFromOrigin
		    Math.sqrt(@x * @x  + @y * @y) # Uses instance variables. why a module method? Less OOP :-(
		  end
		  def distFromOrigin2
		    Math.sqrt(x * x + y * y) # uses getter methods
		  end

		end

		class ColorPoint < Point
		  attr_accessor :color

		  # replace initialiazer of superclass
		  def initialize(x,y,c="clear") # or could skip this and color starts unset
		    super(x,y) # keyword super calls same method in superclass
		    @color = c
		  end
		end

		# example uses with reflection
		p  = Point.new(0,0)
		cp = ColorPoint.new(0,0,"red")
		p.class                         # Point
		p.class.superclass              # Object
		cp.class                        # ColorPoint
		cp.class.superclass             # Point
		cp.class.superclass.superclass  # Object
		cp.is_a? Point                  # true
		cp.instance_of? Point           # false
		cp.is_a? ColorPoint             # true
		cp.instance_of? ColorPoint      # true

	Sometimes, subclassing is overused

	alternatives:
	1. add method in base class with a default value in constructor (e.g. directly add 'color' field to 'Point')
	 	OK, but not modular: impacts all callers (it s a problem for a lib)
	2. copy/paste base class implem (e.g. copy 'Point' methods into 'ColorPoint')
	 	+: seperation, -: no code reuse
 	3. use delegation (e.g. 'ColorPint' has a 'Color' field)
 	 	+: encapsulation, code reuse, -: not very convenient, coupling
}

Overriding and Dynamic Dispatch {

	Overriding can make a method defined in superclass call a method in the subclass 
	e.g. PolarPoint.distFromOrigin2() -> ThreeDPoint.distFromOrigin2 -> ThreeDPoint.z

	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 7: Overriding and Dynamic Dispatch

		class Point
		  attr_accessor :x, :y

		  def initialize(x,y)
		    @x = x
		    @y = y
		  end
		  def distFromOrigin
		    Math.sqrt(@x * @x  + @y * @y) # uses instance variables directly (poor OOP style)
		  end
		  def distFromOrigin2
		    Math.sqrt(x * x + y * y) # uses getter methods (better OOP style)
		  end

		end

		# design question: "Is a 3D-point a 2D-point?" 
		# [arguably poor style here, especially in statically typed OOP languages]
		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

		class PolarPoint < Point
		  # Interesting: by not calling super constructor, no x and y instance vars
		  # In Java/C#/Smalltalk would just have unused x and y fields
		  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 # avoids multiple calls to y method
		    @theta = Math.atan2(b, a)
		    @r = Math.sqrt(a*a + b*b)
		    self
		  end
		  def y= b
		    a = x # avoid multiple calls to y method
		    @theta = Math.atan2(b, a)
		    @r = Math.sqrt(a*a + b*b)
		    self
		  end
		  def distFromOrigin # must override since inherited method does wrong thing
		    @r
		  end
		  # inherited distFromOrigin2 already works!!
		end

		# the key example
		pp = PolarPoint.new(4,Math::PI/4)
		pp.x
		pp.y
		pp.distFromOrigin2
}

Method-Lookup Rules, Precisely {

	Dynamic dispatch:
		(aka virtual methods)
		= call self.method can call a method defined in subclass
		Most unique characterisitic of OOP

	Variable lookup:
		in ML: cf. lexical scope for closures
		in Racket: like ML + let/letrec
		in Ruby:
			similiar for local variables
			but different for instance variables / class variables / methods => louk up in term of 'self'

	'self' lookup:
		For Ruby instance variables / methods / classes
		'self' maps to current object

		Lookup for instance variable '@x' => lookup to self
		Lookup for class variable '@@x' => lookup to self.class
		Lookup for method => dynamic dispatch

	Dynamic dispatch for methods:

		Rules for evaluation of e0.m(e1,...en)
		 1. evaluate args e0,...en to objects obj0,...,objn (e0 is special, it s called the "receiver")
		 2. let C be the class of obj0
		 3. if m is defined in C => FOUND
		    else recur with superclasses of C (until class Object)
		    else call 'method_missing' (default one in Object raises an error)
		 4. evaluate body of method
		  with arguments bound to obj1,...,objn
		  with 'self' bound to obj0 => DYNAMIC 'DYNAMIC DISPATCH'

		 Similar in Java, C# etc...
}

Dynamic dispatch vs closures {

	In Ruby, we can use dynamic dispatch to change external libs => more flexible / can be dangerous! (double edged sword) :)

	Example: override badly implemented 'even' function.

	ML Code:
		(* Dan Grossman, Programming Languages, Jan-Mar 2013 *)
		(* Section 7: Dynamic Dispatch Versus Closures *)

		(* ML functions do not use use late binding: simple example: *)

		fun even x = (print "in even\n" ; if x=0 then true else odd (x-1))
		and odd x = (print "in odd\n" ; if x=0 then false else even (x-1))

		val a1 = odd 7
		val _ = print "\n"

		(* does not change behavior of odd -- which is too bad *)
		fun even x = (x mod 2) = 0

		val a2 = odd 7
		val _ = print "\n"

		(* does not change behavior of odd -- which is good *)
		fun even x = false

		val a3 = odd 7
		val _ = print "\n"

		Ruby code:
			#  Dan Grossman, Programming Languages, Jan-Mar 2013 
			#  Section 7: Dynamic Dispatch Versus Closures 

			# Ruby methods use late binding: simple example:

			class A
			  def even x
			    puts "in even A"
			    if x==0 then true else odd(x-1) end
			  end
			  def odd x
			    puts "in odd A"
			    if x==0 then false else even(x-1) end
			  end
			end

			a1 = A.new.odd 7
			puts "a1 is " + a1.to_s + "\n\n"

			class B < A
			  def even x # changes B's odd too! (helps)
			    puts "in even B"
			    x % 2 == 0
			  end
			end

			a2 = B.new.odd 7
			puts "a2 is " + a2.to_s + "\n\n"

			class C < A
			  def even x
			    puts "in even C" # changes C's odd too! (hurts)
			    false
			  end
			end

			a3 = C.new.odd 7
			puts "a3 is " + a3.to_s + "\n\n"


	OOP with dynamic dispatch:
		- makes it easy to change behavior, without copying code
		- harder to reason about code
}

OOP vs Functional Decomposition {

	2 forms of decompositions:
		In FP, we break down programs into functions
		In OOP, we break down programs into classes that give behavior to some kind of data
		Both forms of decomposition are opposite
		Which is better? depend on personal taste + on how we expect to change/extend

	The expression example:
		different variants of expressions: ints, additions, negations...
		different operations: eval, toString, hasZero...

		Matrix of variants and expressions:
					eval 	toString 	hasZero		...
					---		--- 		---
		Int 	|
		Add 	|
		Negate 	|
		...

		Standard approach in FP (ex: ML):
			define a datatype with one constructor for each variant
			define one function per expression: each function has one branch for each variant (branches can be combined via wildcard patterns, for example)
			=> program organized "by columns"

		Standard approach in OOP:
			One abstract class with one abstract method for each operation
			Define a subclass for each variant
			=> program organized "by rows"


	Ruby code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 8: OOP vs. Functional Decomposition 

		# Note: If Exp and Value are empty classes, we do not need them in a
		# dynamically typed language, but they help show the structure and they
		# can be useful places for code that applies to multiple subclasses.

		class Exp
		  # could put default implementations or helper methods here
		end

		class Value < Exp
		  # this is overkill here, but is useful if you have multiple kinds of
		  # /values/ in your language that can share methods that do not make sense 
		  # for non-value expressions
		end

		class Int < Value
		  attr_reader :i
		  def initialize i
		    @i = i
		  end
		  def eval # no argument because no environment
		    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
		  end
		  def toString
		    "-(" + e.toString + ")"
		  end
		  def hasZero
		    e.hasZero
		  end
		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) # error if e1.eval or e2.eval has no i method
		  end
		  def toString
		    "(" + e1.toString + " + " + e2.toString + ")"
		  end
		  def hasZero
		    e1.hasZero || e2.hasZero
		  end
		end

	ML code:
		(* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
		(* Section 8: OOP vs. Functional Decomposition *)

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

		exception BadResult of string

		(* this helper function is overkill here but will provide a more 
		   direct contrast with more complicated examples soon *)
		fun add_values (v1,v2) =
		    case (v1,v2) of
			(Int i, Int j) => Int (i+j)
		      | _ => raise BadResult "non-values passed to add_values"

		fun eval e = (* no environment because we don't have variables *)
		    case e of
			Int _       => e
		      | Negate e1   => (case eval e1 of 
					    Int i => Int (~i)
					  | _ => raise BadResult "non-int in negation")
		      | Add(e1,e2)  => add_values (eval e1, eval e2)

		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)
}

Adding Operations or Variants {
	About extensibility

	In our "expression example", what if we add a new operation (e.g. "noNegConstants")?
	 - in FP: easier, just write a new function
	 - in OOP: less easy, write n methods
	And what if we add a new variant (e.g. "Mult")?
	 - in FP: less easy, update n functions
	 - in OOP: easier, create a new class
	Note: type checker (in ML, Java...) helps us to find unimplemented methods

	The other way:
		FP allows "plan ahead" (make datatypes extensible / operations take function arguments to give result)
		OOP has "visitor pattern"

	Sum up:
	 expecting new operations? use FP
	 expecting new variants? use OOP
	 beware: extensibility is a double-edged sword (code is harder to reason about)

 	Ruby code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 8: Adding Operations or Variants 

		# Note: If Exp and Value are empty classes, we do not need them in a
		# dynamically typed language, but they help show the structure and they
		# can be useful places for code that applies to multiple subclasses.

		class Exp
		  # could put default implementations or helper methods here
		end

		class Value < Exp
		  # this is overkill here, but is useful if you have multiple kinds of
		  # /values/ in your language that can share methods that do not make sense 
		  # for non-value expressions
		end

		class Int < Value
		  attr_reader :i
		  def initialize i
		    @i = i
		  end
		  def eval # no argument because no environment
		    self
		  end
		  def toString
		    @i.to_s
		  end
		  def hasZero
		    i==0
		  end
		  def noNegConstants
		    if i < 0
		      Negate.new(Int.new(-i))
		    else
		      self
		    end
		  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
		  end
		  def toString
		    "-(" + e.toString + ")"
		  end
		  def hasZero
		    e.hasZero
		  end
		  def noNegConstants
		    Negate.new(e.noNegConstants)
		  end
		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) # error if e1.eval or e2.eval has no i method
		  end
		  def toString
		    "(" + e1.toString + " + " + e2.toString + ")"
		  end
		  def hasZero
		    e1.hasZero || e2.hasZero
		  end
		  def noNegConstants
		    Add.new(e1.noNegConstants,e2.noNegConstants)
		  end
		end

		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) # error if e1.eval or e2.eval has no i method
		  end
		  def toString
		    "(" + e1.toString + " * " + e2.toString + ")"
		  end
		  def hasZero
		    e1.hasZero || e2.hasZero
		  end
		  def noNegConstants
		    Mult.new(e1.noNegConstants,e2.noNegConstants)
		  end
		end

	ML code:
		(* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
		(* Section 8: Adding Operations or Variants *)

		(* we take our previous version and add noNegConstants without changing
		   old code and a Mult constructor, which requires changing all previous code,
		   with a nice to-do list due to inexhaustive pattern-matches. *)

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

		exception BadResult of string

		(* this helper function is overkill here but will provide a more 
		   direct contrast with more complicated examples soon *)
		fun add_values (v1,v2) =
		    case (v1,v2) of
			(Int i, Int j) => Int (i+j)
		      | _ => raise BadResult "non-values passed to add_values"

		fun eval e = (* no environment because we don't have variables *)
		    case e of
			Int _       => e
		      | Negate e1   => (case eval e1 of 
					    Int i => Int (~i)
					  | _ => raise BadResult "non-int in negation")
		      | Add(e1,e2)  => add_values (eval e1, eval e2)
		      | Mult(e1,e2) => (case (eval e1, eval e2) of
					    (Int i, Int j) => Int (i*j)
					  | _ => raise BadResult "non-ints in multiply")

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

		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)
		      | Mult(e1,e2) => Mult(noNegConstants e1, noNegConstants e2)
}

Binary Methods with Functional Decomposition {
	
	What if operations have multiple arguments of different variants?
	ex:
	 - include variants "String" and "Rational"
	 - update "Add" to work on any pair of Int, String , Rational: concatenation if either math or string concat

 	=> another 3x3 grid:
 				Int 	String 		Rational
 	Int
 	String
 	Rational

 	In ML: 'add_values' will be a helper function with 9 cases

 	ML code:
		(* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
		(* Section 8: Binary Methods With Functional Decomposition *)

		datatype exp = 
		    Int    of int 
		  | Negate of exp 
		  | Add    of exp * exp 
		  | Mult   of exp * exp
		  | String of string  
		  | Rational of int * int

		exception BadResult of string

		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) (* not commutative *)
		      | (String s1, String s2)  => String(s1 ^ s2)
		      | (String s,  Rational(i,j)) => String(s ^ Int.toString i ^ "/" ^ Int.toString j)
		      | (Rational _,    Int _)    => add_values(v2,v1) (* commutative: avoid duplication *)
		      | (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"

		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)  => add_values (eval e1, eval e2)
		      | Mult(e1,e2) => (case (eval e1, eval e2) of
					    (Int i, Int j) => Int (i*j)
					  | _ => raise BadResult "non-ints in multiply")
		      | String _    => e
		      | Rational _  => e

		fun toString e =
		    case e of
			Int i       => Int.toString i
		      | Negate e1   => "-(" ^ (toString e1) ^ ")"
		      | Add(e1,e2)  => "("  ^ (toString e1) ^ " + " ^ (toString e2) ^ ")"
		      | Mult(e1,e2) => "("  ^ (toString e1) ^ " * " ^ (toString e2) ^ ")"
		      | String s    => s
		      | Rational(i,j) => Int.toString i ^ "/" ^ Int.toString j

		fun hasZero e =
		    case e of
			Int i       => i=0 
		      | Negate e1   => hasZero e1
		      | Add(e1,e2)  => (hasZero e1) orelse (hasZero e2)
		      | Mult(e1,e2) => (hasZero e1) orelse (hasZero e2)
		      | String _    => false
		      | Rational(i,j) => i=0

		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)
		      | Mult(e1,e2) => Mult(noNegConstants e1, noNegConstants e2)
		      | String _    => e
		      | Rational(i,j) => if i < 0 andalso j < 0
					 then Rational(~i,~j)
					 else if j < 0
					 then Negate(Rational(i,~j))
					 else if i < 0
					 then Negate(Rational(~i,j))
					 else e
}

Binary Methods with Double Dispatch {

	Double dispatch:
		- each class implements 'add_values' and 3 functions: addInt(v), addString(v) and addRational(v)
		- Add.eval(e1, e2) calls e1.eval.add_values e2.eval

	Warning: testing type (e.g. 'v.is_a? Rational') is not really OOP 

	Ruby code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 8: Binary Methods with OOP: Double Dispatch

		# Note: If Exp and Value are empty classes, we do not need them in a
		# dynamically typed language, but they help show the structure and they
		# can be useful places for code that applies to multiple subclasses.

		class Exp
		  # could put default implementations or helper methods here
		end

		class Value < Exp
		  # this is overkill here, but is useful if you have multiple kinds of
		  # /values/ in your language that can share methods that do not make sense 
		  # for non-value expressions
		end

		class Int < Value
		  attr_reader :i
		  def initialize i
		    @i = i
		  end
		  def eval # no argument because no environment
		    self
		  end
		  def toString
		    @i.to_s
		  end
		  def hasZero
		    i==0
		  end
		  def noNegConstants
		    if i < 0
		      Negate.new(Int.new(-i))
		    else
		      self
		    end
		  end
		  # double-dispatch for adding values
		  def add_values v # first dispatch
		    v.addInt self
		  end
		  def addInt v # second dispatch: other is Int
		    Int.new(v.i + i)
		  end
		  def addString v # second dispatch: other is MyString (notice order flipped)
		    MyString.new(v.s + i.to_s)
		  end
		  def addRational v # second dispatch: other is MyRational
		    MyRational.new(v.i+v.j*i,v.j)
		  end
		end

		# new value classes -- avoiding name-conflict with built-in String, Rational
		class MyString < Value
		  attr_reader :s
		  def initialize s
		    @s = s
		  end
		  def eval
		    self
		  end
		  def toString
		    s
		  end
		  def hasZero
		    false
		  end
		  def noNegConstants
		    self
		  end

		  # double-dispatch for adding values
		  def add_values v # first dispatch
		    v.addString self
		  end
		  def addInt v # second dispatch: other is Int (notice order is flipped)
		    MyString.new(v.i.to_s + s)
		  end
		  def addString v # second dispatch: other is MyString (notice order flipped)
		    MyString.new(v.s + s)
		  end
		  def addRational v # second dispatch: other is MyRational (notice order flipped)
		    MyString.new(v.i.to_s + "/" + v.j.to_s + s)
		  end
		end

		class MyRational < Value
		  attr_reader :i, :j
		  def initialize(i,j)
		    @i = i
		    @j = j
		  end
		  def eval
		    self
		  end
		  def toString
		    i.to_s + "/" + j.to_s
		  end
		  def hasZero
		    i==0
		  end
		  def noNegConstants
		    if i < 0 && j < 0
		      MyRational.new(-i,-j)
		    elsif j < 0
		      Negate.new(MyRational.new(i,-j))
		    elsif i < 0
		      Negate.new(MyRational.new(-i,j))
		    else
		      self
		    end
		  end

		  # double-dispatch for adding 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: other is MyString (notice order flipped)
		    MyString.new(v.s + i.to_s + "/" + j.to_s)
		  end
		  def addRational v # second dispatch: other is MyRational (notice order flipped)
		    a,b,c,d = i,j,v.i,v.j
		    MyRational.new(a*d+b*c,b*d)
		  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
		  end
		  def toString
		    "-(" + e.toString + ")"
		  end
		  def hasZero
		    e.hasZero
		  end
		  def noNegConstants
		    Negate.new(e.noNegConstants)
		  end
		end

		class Add < Exp
		  attr_reader :e1, :e2
		  def initialize(e1,e2)
		    @e1 = e1
		    @e2 = e2
		  end
		  def eval
		    e1.eval.add_values e2.eval
		  end
		  def toString
		    "(" + e1.toString + " + " + e2.toString + ")"
		  end
		  def hasZero
		    e1.hasZero || e2.hasZero
		  end
		  def noNegConstants
		    Add.new(e1.noNegConstants,e2.noNegConstants)
		  end
		end

		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) # error if e1.eval or e2.eval has no i method
		  end
		  def toString
		    "(" + e1.toString + " * " + e2.toString + ")"
		  end
		  def hasZero
		    e1.hasZero || e2.hasZero
		  end
		  def noNegConstants
		    Mult.new(e1.noNegConstants,e2.noNegConstants)
		  end
		end
}

Multiple inheritance {

	= if a class can have > 1 superclass

	C++ has 'multiple inheritance' (but some problems).
	Ruby has 'mixins' (a bit less powerful).
	Java/Csharp have 'interfaces' (less powerful)

	Useful? yes, prevents pasting code (ex: Point / ColorPoint / Point3D / ColorPoint3D, etc...) but it s hard!

	Vocabulary:
		'immediate' subclass/superclass
		'transitive' subclass/superclass
		'class hierarchy':
			- a tree for single inheritance
			- a 'Directed-Acyclic Graph' for multiple inheritance

	What s wrong?
	 - what does 'super' means if class hierarchy is a graph? => more complicated
	 - what if C inherits from A and B, and both have method m?
	 - what if C inherits from A, which overrides m and B, which does not overrides m?
	 - what if C inherits from A and B that have field F? Has C one or two copies of F?

 	Ruby:
 		Person(pocket), Artist < Person, Cowboy < Person: cowboys and artists have a distinct pocket

	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 8: Multiple Inheritance

		class Pt
		  attr_accessor :x, :y
		  def distToOrigin
		    Math.sqrt(x * x  + y * y)
		  end
		end

		class ColorPt < Pt
		  attr_accessor :color
		  def darken # error if @color not already set
		    self.color = "dark " + self.color
		  end
		end

		class Pt3D < Pt
		  attr_accessor :z
		  def distToOrigin
		    Math.sqrt(x * x  + y * y + z * z)
		  end
		end


		# This does not exist in Ruby (or Java/C#, it does in C++)

		# class ColorPt3D_3 < ColorPt, Pt3D
		# end

		# two ways we could actually make 3D Color Points:

		class ColorPt3D_1 < ColorPt
		  attr_accessor :z
		  def distToOrigin
		    Math.sqrt(x * x  + y * y + z * z)
		  end
		end

		class ColorPt3D_2 < Pt3D
		  attr_accessor :color
		  def darken # error if @color not already set
		    self.color = "dark " + self.color
		  end
		end
}

Mixins {

	= Ruby s alternative to multiple inheritance (like Scala traits)

	mixin = a collections of methods, not a class
	In Ruby, a class cannot extend more that one class but can include several mixins

	Syntax:
		module MyMixin
			def myMethod1
				self + self # here we assume that any class that includes this mixin has 'x' method
			end
		end
		class MyInt include MyMixin

	Lookup rules:
		1. in class 2. in mixins 3. in superclass 4. in superclass mixins

	It s often bad style to use fields in mixins (avoid the 'pocket' problems)
	Widely used mixins:
		'Comparable' which assumes '<=>' exists (aka 'spaceship operator')
		'Enumerable' which assumes 'each' exists

	Mixins limitation (vs multiple inheritance):
		works well for our ColorPoint/Point3D example but not for the cowboy/artist


	Code:
		# Programming Languages, Dan Grossman, Jan-Mar 2013 
		# Section 8: Mixins

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

		class Pt
		  attr_accessor :x, :y
		  include Doubler
		  def + other
		    ans = Pt.new
		    ans.x = self.x + other.x
		    ans.y = self.y + other.y
		    ans
		  end
		end

		class String
		  include Doubler
		end

		# these are probably the two most common uses in the Ruby library:
		#  Comparable and Enumerable

		# you define <=> and you get ==, >, <, >=, <= from the mixin
		# (overrides Object's ==, adds the others)
		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

		# Note ranges are built in and very common
		# you define each and you get map, any?, etc.
		# (note map returns an array though)
		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

		# here is how module Enumerable could implement map:
		# (but notice Enumerable's map returns an array,
		#  *not* another instance of the class :( )
		# def map
		#   arr = []
		#   each {|x| arr.push x }
		#   arr
		# end

		# this is more questionable style because the mixin is using an
		# instance variable that could clash with classes and has to be initialized
		module Color 
		  def color
		    @color
		  end
		  def color= c
		    @color = c
		  end
		  def darken
		    self.color = "dark " + self.color
		  end
		end

		class Pt3D < Pt
		  attr_accessor :z
		  # rest of definition omitted (not so relevant)
		end

		class ColorPt < Pt
		  include Color
		end

		class ColorPt3D < Pt3D
		  include Color
		end
}

Interfaces {
	How to deal with 'multiple inheritance' in statically-typed langs which do not have 'multiple inheritance'? 

	Statically-typed OOP has interfaces (cf. Java, Csharp, etc... but not Ruby)
	If C is a transitive subclass of D, then C is a subtype of D
	Interfaces:
	 - are a type, but not a class (interfaces cannot be instanciated).
	 - only contain method signatures (no definitions like in Ruby)
	 - classes can implement several interfaces 
}

Subtyping from the beginning {
	Let s study Subtyping in pseudo-code

	Imagine a tiny statically typed language that has records with mutable fields (ML has records but no subtyping nor mutable fields ; Racket and Ruby have no static typing):
	 - record creation: { f1 = e1, f2 = e2, ..., fn = en}
	 - record field access: e.f
  	 - record field update: e1.f = e2
  	 - basic type system for records:
  	 	if e1, e2, ..., en have type t1, t2, ..., tn
  	 		record has type { f1: t1, f2: t2, ..., fn = tn }
  	 		e.f has type t
  	 		e.f = e2 is only valid if e2 has same type than e.f

	Example:
		fun distToOrigin (p: {x: real, y: real}) =
			Math.sqrt(p.x*p.x + p.y*p.y)
		val pythag : {x: real, y: real} = {x=3.0, y=4.0}
		val five : real = distToOrigin(pythag) # OK
		val c = {x: real, y: real, color: string} = {x=3.0, y=4.0, color="green"} # Oops, would not type check:
		distToOrigin(c)

	So we also want to allow extra fields:
		distToOrigin({x=3.0, y=4.0, color="green"}) # It's fine
}

The subtype relation {
	Add more flexibility to our type system, with 2 things:

	1. add notion of subtyping
		t1 <: t2 # means t1 is a subtype of t2
	2. add one rule:
		if e has type t1 and t1 <: t2, then e also has t2

	principle of substitutability:
		if t1 <: t2, then any value of type t1 must be usable in every way a t2 is
	
	4 rules:
	rule 1: "width" subtyping: a supertype can has a subset of fields with the same type
	rule 2: "permutation" subtyping: a supertype can have the same fields in different order
	rule 3: transitivity: if t1 <: t2 and t2 <: t3 then t1 <: t3
	rule 4: reflexibility: every type is a subtype of itself

}

Depth subtyping {

	We cannot add "depth" subtyping (nested) like
	{ center: {x: real, y: real, z :real}, radius: real }
	 						<:
	{ center: {x: real, y: real}, radius: real }

	Rule we would like to add:
		if ta <: tb, then { f1: t1, ..., f: ta, ..., fn: tn } <: { f1: t1, ..., f: tb, ..., fn: tn }

	But it is unsound because of mutation (sphere could be transformed into circle)
	(note: it would be OK if our language was immutable)
}

Function Subtyping {
	subtyping for functions!

	When a function type is a subtype of another...

 	Example:
 		(* distance between a point and f(point) *)
 		fun distMoved(
 			f : {x: real, y: real} -> { x: real, y: real },
 			point: { x: real, y: real}) =
 			let val p2 : { x: real, y: real } = f p
 				val dx : real = p2.x - p.x
 				val dy : real = p2.y - p.y
			in 
				Math.sqrt(dx*dx + dy*dy)
			end

		fun flip p = { x = ~p.x, y=~p.y }
		val d = distMoved(flip, {x=3.0, y=4.0}) (* it s OK, no subtyping here *)


	If ta <: tb, then t->ta <: t->tb
	"return types are covariant" i.e. a function can return "more than it needs" to
	Example:
		fun flipGreen p = { x = ~p.x, y=~p.y, color="green" }
		val d = distMoved(flipGreen, {x=3.0, y=4.0})
		(* OK *)

	ta <: tb does NOT allow ta->t <: tb->t 
	Example:
		fun flipIfGreen p =
			if p.color = "green" (* kaboom! *)
			then { x = ~p.x, y=~p.y }
			else { x = p.x, y=p.y }
		val d = distMoved(flipIfGreen, {x=3.0, y=4.0})
		(* not OK, unsound! *)

	If tb <: ta, then ta->t <: tb->t
	"Argument types are contravariant" i.e. a function can assume "less that it needs to" about arguments
	Example:
		fun flipX_Y0 = { x = ~p.x, y=0.0 }
		val d = distMoved(flipX_Y0, {x=3.0, y=4.0})

	You can do both:
		Example:
		fun flipXMakeGreen p = { x=~p.x, y=0.0, color="green"} (* {x:real} -> {x:real, y:real, c:string} *)
		val d = distMoved(flipXMakeGreen, {x=.3.0, y=4.0}) 


	General rule:
		if t3 <: t1 and t2 <: t4, then t1->t2 <: t3->t4

	"function subtyping" is contravariant in arguments and covariant in results
}

Subtyping for OOP {

	Like in Java, C#, etc...

	Recall:
	 - classes are types
	 - subclasses are subtypes
	 - substitution principle: instance of subclass should be usable on place of instance of superclass

	 Objects are like records
	 - with mutable fieds (generally)
	 - with methods which are immutable functions that have access to 'self'

	 In theory:
	 - Subtypes could have extra fields and methods
	 - Overriding methods could have contravariant arguments and covariant results (compared to overridden methods)

	 In practice, in Java:
	 - subtyping are explicit subclasses
	 - a subclass can add fields and methods
	 - a subclass can override a method with a covariant return type
	 - a subclass CANNOT override a method with contravariant arguments

	Classes vs Types
		class: defines object s behaviour
		type: defines object s fields/methods
		Both are often confused! :)

	Self/this is a special argument!
		It is covariant, not like other arguments
}

Generics Versus Subtyping {

	Generics are good at:
	- types for functions that compose (i.e. 'compose(g,h)')
	- types for functions that operate over generic collections (i.e. 'length', 'map' etc...)
	(when types can be anything but multiple things need to be in the same type)

	Subtyping is NOT good:
	- for containers (we would need to downcast => can fail, run-time cost...)

	Subtyping is good:
	- code that "needs a Foo but have more than a Foo" (i.e. geometry points for colored points, GUI widgets...)

	ML has no subtyping (alternative: pass getter functions)
}

Bounded Polymorphism {
	When to combine generics and subtyping

	Some langs have both generics and subtyping (i.e. Java)
	"bounded polymorphism": combining generics and subtyping

	Example:
		// Filter points that are inside a circle (cannot send / get back List<ColorPoint>)
		List<Point> inCircle(List<Point> pts, Point circleCenter, double circleRadius)

		// With generics, we could now send / get back List<ColorPoint> but we cannot implement inCircle() for any type:
		List<T> inCircle(List<T> pts, Point circleCenter, double circleRadius)

		// With generics, we could now send / get back List<ColorPoint> but we cannot implement inCircle() for any type:
		List<T> inCircle(List<T> pts, Point circleCenter, double circleRadius)

		// Correct syntax for bounded polymorphism in Java:
		List<T extends Point> inCircle(List<T> pts, Point circleCenter, double circleRadius)
}