Lab 6: Meta-programming Pattern

Objectives

During this lab session:

Students will write and test Ruby code that implements the Meta-programming design pattern.

This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.

Introduction: Finite differences method

Given a series of numbers, it is possible to generate a polynomial formula that allows you to calculate any element of the given series. The algorithm will be described using an example.

Assume that you have the following series of numbers: 1, 8, 16, 28, 47 and 76.

You need to build an inverted pyramid starting from the base and going downwards. The first layer of the pyramid consists of all the numbers from the original series. Each number of the following layers is obtained by subtracting the two numbers found in the layer immediately above. This same process is repeated until we have a layer in which all numbers are equal (a layer with one element also fits this description). See the following illustration:

1   8   16   28   47   76		

  7    8   12   19   29		
  
    1    4    7   10		

       3    3    3

In order to construct the desired formula, we need all the numbers found at the very left of each layer. In our example, those would be: 1, 7, 1, and 3. These correspond to the coefficients c0, c1, c2 and c3 respectively from the following general formula:

S(x) =	c0/0! + 
        c1(x - 1)/1! + 
        c2(x - 1)(x - 2)/2! + 
        c3(x - 1)(x - 2)(x - 3)/3! + 
        ... +
        cn(x - 1)(x - 2)(x - 3) ... (x - n)/n!

Replacing the coefficient values from our example, we would obtain the following formula:

S(x) = 1 + 
       7(x - 1) + 
       1(x - 1)(x - 2)/2 + 
       3(x - 1)(x - 2)(x - 3)/6

We can now verify that this formula works as expected for every value in the original series:

S(1) = 1			S(4) = 28
S(2) = 8			S(5) = 47
S(3) = 16			S(6) = 76

But it also works for previously unknown values:

S(7) = 118			S(8) = 176

Activity Description

This lab can be developed individually or in pairs.

Create a folder called metaprogramming. Inside this folder, create two files called: finite_differences.rb and test_finite_differences.rb.

All Ruby source files must start with a comment containing the lab's title, date, and the authors' personal information. For example:
```
# Lab 6: Meta-programming Pattern
# Date: 22-Oct-2009
# Authors:
# 456654  Anthony Stark 
# 1160611 Thursday Rubinstein
```

Write a class called FiniteDifferences that implements the following methods (you may add additional auxiliary private methods if you wish):

Method Signature	Description
`initialize(*args)`	Initializes the current instance with the series of numbers given as variable arguments.
`formula`	Returns a string that represents a valid Ruby expression of the finite differences formula for this instance.
`call(x)`	Evaluates this instance's formula for a given value of `x`. To do this, you should use the `eval` method from the `Kernel` module.

You will also need to define the fact function, that computes the factorial of a given number.

Place your code in the finite_differences.rb source file.

Check your solution using the following test case (place the test in the source file test_finite_differences.rb):

require 'test/unit'
require 'finite_differences'

class FiniteDifferencesTest < Test::Unit::TestCase
    
  def test_one
    fd = FiniteDifferences.new(1, 8, 16, 28, 47, 76)
    assert_equal("1+"                    \
                 "7*(x-1)+"              \
                 "1*(x-1)*(x-2)/2+"      \
                 "3*(x-1)*(x-2)*(x-3)/6", 
                 fd.formula)
    assert_equal(1, fd.call(1))
    assert_equal(8, fd.call(2))
    assert_equal(16, fd.call(3))
    assert_equal(28, fd.call(4))
    assert_equal(47, fd.call(5))
    assert_equal(76, fd.call(6))
    assert_equal(118, fd.call(7))
    assert_equal(176, fd.call(8))
  end
  
  def test_two
    fd = FiniteDifferences.new(3, 5, 7, 9)
    assert_equal("3+2*(x-1)", fd.formula)
    assert_equal(3, fd.call(1))
    assert_equal(5, fd.call(2))
    assert_equal(7, fd.call(3))
    assert_equal(9, fd.call(4))
    assert_equal(11, fd.call(5))
    assert_equal(13, fd.call(6))    
  end
  
  def test_three
    fd = FiniteDifferences.new(42)
    assert_equal("42", fd.formula)
    assert_equal(42, fd.call(1))
    assert_equal(42, fd.call(2))
    assert_equal(42, fd.call(3))
    assert_equal(42, fd.call(4))
  end
  
  def test_four
    fd = FiniteDifferences.new(4, 8, 15, 16, 23, 42)
    assert_equal("4+"                                    \
                 "4*(x-1)+"                              \
                 "3*(x-1)*(x-2)/2+"                      \
                 "-9*(x-1)*(x-2)*(x-3)/6+"               \
                 "21*(x-1)*(x-2)*(x-3)*(x-4)/24+"        \
                 "-27*(x-1)*(x-2)*(x-3)*(x-4)*(x-5)/120", 
                 fd.formula)
    assert_equal(4, fd.call(1))
    assert_equal(8, fd.call(2))
    assert_equal(15, fd.call(3))
    assert_equal(16, fd.call(4))
    assert_equal(23, fd.call(5))
    assert_equal(42, fd.call(6))
    assert_equal(46, fd.call(7))
    assert_equal(-52, fd.call(8))
    assert_equal(-426, fd.call(9))
    assert_equal(-1364, fd.call(10))
  end
end

Deliverables

To hand in your lab work, follow these instructions:

Create a ZIP file with the full contents of the metaprogramming directory. Call this file metaprogramming.zip.
Using the Online Assignment Delivery System (SETA), deliver the ZIP file. Due date is Friday, October 23.

Evaluation

This activity will be evaluated using the following criteria:

100	The code works as requested.
60-90	The code works, but has some flaws.
20-50	The code doesn't work, but it seams that some amount of time was spent on it.
DA	The program was plagiarized.

Software Design and Architecture