Monday, January 2, 2017

Ruby, Metaprogramming, and LinearEquation Solver

In Mivo, Every Friday at 5 PM, someone from the developer team has to be sacrificed.
During the ritual, those who sacrificed, must share their knowledge (most of the time technical) to the audience. And fortunately or not, this week (the first week in January 2017) is my turn.  And in this occasion, I'll share about metaprogramming.

Metaprogramming is a programming technique in which computer programs have the ability to treat programs as their data. It means that a program could be designed to read, generate, analyse or transform other programs, and even modify itself while running. ~ Wikipedia.
In Ruby, there's an enormous amount of function, that would help you writing a program, that could dynamically modify itself.

Most common example is:
  • define_method(methodname, &block)

    define_method is a method that take two argument, a symbol or string as the methodname, and the block process of what it should do.

    for example, if I have a class, that refer to a user table in mysql with field name, email, and password, i can define 3 new method dynamically, namely find_by_name, find_by_email, and find_by_password with the following code: (not accurate, but you get the point)

  • method_missing?(methodname)

    method missing is a method that just accept a string or symbol argument, this is a method that allows you to handle any arbitrary method when it is called.
    Suppose your User have a field name, email, and password, and then there's user info where we put his address, facebook_id, phone_number, and so on. Now you might want to write your program so that a User object may receive any method in UserInfo, well, it'll probably be written like:

Alright, so we've seen how we can write a program that could modify itself mid-runtime, or defining what is not defined. Since we've seen how we write a program that "write" itself, it's also possible for our program to read its own source-code.

Meet the "source-code".

In the next example, We'll look how we implement a linear-equation solver using metaprogramming, (not really useful since then, our equation is hardcoded, but why not?).

Look at the following example of how we define our equation:

Guess what, there's no variable x, y, or z in program, we also didn't create new behavior for Fixnum instance by defining .x, .y, or .z method, and of course we doesn't use method_missing? as well.
Would it then throw error? well, no, not until it's evaluated.

If the codes will be an error when it's evaluated, then just don't evaluate it ~ Ramadoka:2017 

 Which is exactly what I'll do.

Let's take a look at what it does

what magic did we found there?

you might guessed it correctly, it's the @eq.source 

that magic, allows us to read the source-code of our function, and since ruby is dynamic-typed interpreted language, it doesn't know whether an object would respond to a method or not, until it is evaluated, so yeah, there won't be a compile time error, as long as our-code passed the lexical analysis.

Now, that we have done it, we basically just said:

"ruby, kindly, don't parse my code, let me handle that part myself."

Which is pretty meta for my taste...

That marks the end of our topic about metaprogramming, but if you're curious about how the code of LinearEquation works, please feel free to continue along.

Linear Equation Solver

The first step is defining the requirement (can be adjusted later), how do we want to say 3x + 2y + z = 10
since apparently 3x + 2y + z = 10 doesn't pass the lexical analysis (or in other words, ruby know it's not a valid program even without running it).

In this example I'm defining my requirement would be:
3.x => 3x
- x => - x
+ 2 = 10 => not valid (too lazy to reduce to minimum state)
+ z = 10 => + z = 10
+ -x => apparently work as intended
- -x => not working correctly.

If the code doesn't match the requirement, you can either
a) change the code so it meet the requirement
b) change the requirement so it match the code

So Yeah, since this is just a proof of concept, I'm picking the 2nd option.

How do we handle the parsing?

Regex, Regex is always the answer, as anonymous programmer said:

A programmer has a problem, and then he said, I know, I'll use regex.
Now he has 2 problem.

Ok, as you've seen regex is not the silver bullet to handle parsing, we probably need a full-blown parser, but implementing a parser might take 10x time longer than it is, so let's live with the bug now.

as buggy as it is, this regex handles the filtering of a parameter for our basic necessity:
/[+-]* *(?:\d+\.){0,1}[a-zA-Z]+/
by using string.scan using this regex, a 3.x + y + 2.z
will become ["3.x", "+ y", "+2.z"]

and then, there's two other regex to parse our parameters, it can be either:
if it start with the multiplier (e.g: 2.x)

or, it can also be:
if it doesn't have multiplier (e.g: y)

once we have parsed 3.x - 2.y + z = 10 into
[3x, -2y, 1z] and [10]

We will use Matrix Multiplication to solve the equation:

as it turns out, our equation can be rewritten as Matrix Multiplication as: 

Aaaand, that's it, I'm out of material. Thanks for reading this scientific nonsense.

For the full version of the LinearEquation Implementation you can see it here.

Does this post lacking madokaism?, No Longer!
lahirnya juru selamat

No comments:

Post a Comment