Square root by Newton's method

This well known method to calculate square roots by successive approximations is one of the first examples that Martin Odersky uses in its Scala by example booklet freely available online. You'll find it in section 4 of chapter 4.

The idea of this method is that we guess what could be the result, and then iteratively improve our guess, until we reach a good enough approximation.

It doesn't matter much which is our initial guess, we could simply default it to one, more interesting is deciding when we should stop to iterate. In some way it should be dependent on the input value itself. Here we are going to consider ourself happy when the difference between our guess squared and the input, divided by the input itself is less than one thousandth:

def isGoodEnough(guess: Double, x: Double) = math.abs(guess * guess - x) / x < 0.001

So, we are going to accept 8.003 as approximation for the 64 square root, but we'll reject 8.004. To improve our guess we'll apply this algorithm:

def improve(guess: Double, x: Double) = (guess + x / guess ) / 2

Now we are ready to write the requested function:

def sqrtIter(guess: Double, x: Double): Double =
  if (isGoodEnough(guess, x)) guess
  else sqrtIter(improve(guess, x), x)

If the guess is good enough, we are done. Otherwise iterate again with an improved guess. Likely we don't want the user having the nuisance of providing an initial guess:

def sqrt(x: Double) = sqrtIter(1.0, x)

We can compare the result to call to the Scala library function:

println(sqrt(2) - math.sqrt(2))
println(sqrt(4) - math.sqrt(4))
println(sqrt(1e-6) - math.sqrt(1e-6))
println(sqrt(1e60) - math.sqrt(1e60))

We can, and usually want to, hide the implementation details, making them local to our function. A side effect is that we don't need anymore to pass around the x value, being that visible to all the local functions, too.

def sqrt(x: Double) = {
  def isGoodEnough(guess: Double) = math.abs(guess * guess - x) / x < 0.001
  def improve(guess: Double) = (guess + x / guess ) / 2
  def sqrtIter(guess: Double): Double =
    if (isGoodEnough(guess)) guess
    else sqrtIter(improve(guess))
  
  sqrtIter(1.0, x)
}

Go to the full post

AND and OR as functions

Let's create a couple of Scala functions that would provide an alternative implementation for the AND and OR logical operators. The point of this exercise is seeing how the well known if-else conditional expression works in Scala, and seeing again the difference between by-value and by-name parameter evaluation strategy.

We want to define two functions, and() and or(), behaving like && and ||. Remember that they are so called short-circuit operators. We don't need to check the && second operand when the first is false. Similarly the for ||, when the first operand is true.

Let's express our requirements with assertions:

assert(and(false, false) == (false && false))
assert(and(false, true) == (false && true))
assert(and(true, false) == (true && false))
assert(and(true, true) == (true && true))

assert(or(false, false) == (false || false))
assert(or(false, true) == (false || true))
assert(or(true, false) == (true || false))
assert(or(true, true) == (true || true))

Here is how I have implemented the two functions:

def and(a: Boolean, b: => Boolean) = if(a) b else false
def or(a: Boolean, b: => Boolean) = if(a) a else b

AND is implemented checking the first parameter. If it is true I need to check the second one, otherwise the resulting value is false. Dually for OR, if the first parameter is true, that is the result, otherwise it depends on the second one.

Notice that in both function I have specified that the second parameter is subject to a by-name evaluation. This follows from the short-circuit property of the logical expressions. We can see how this is useful when the second parameter is expensive to evaluate. Or even an infinite loop, as here below:

def silly() : Boolean = silly

assert(and(false, silly) == (false && silly))
assert(or(true, silly) == (true || silly))

The short-circuit logic is implemented also from my functions, so no need of evaluating silly().

Obviously, if I pass silly() as first parameter to either and() or or(), I enter in an infinite loop, and I should kill my Scala application.

Go to the full post

By-value vs. by-name

A pure functional programming language typically uses a by-need evaluation strategy for the arguments of function calls. Scala is a multi-paradigm programming language that also supports the imperative, in an object-oriented way, paradigm. This rules-out by-need, but would let think that the by-name approach would be followed. Still, reasons of efficiency pushed Martin Odersky to chose a by-value approach by default, and leaving the by-name as an alternative.

A trivial example should help clarify the difference about the two approaches.

Let's consider a useless function that gets as parameters a couple of integers and always returns zero.

def zero(a: Int, b: => Int) = 0

Notice that the first parameter is passed to the function by-value, while the second, as specified by the arrow "=>" notation, is passed by-name.

Function zero() looks pretty harmless. However, we could have big troubles if we use it in conjunction with something like this:

def silly() : Int = silly

Function silly() just resolves in an infinitive loop, that would let our program running forever without giving the user any satisfaction.

If I pass silly() to zero() as its second parameter, I'll have no problem at all:

println(zero(42, silly))

Being passed by-name, and not being actually used in zero(), silly() won't be evaluated.

On the contrary, you want to avoid this:

println(zero(silly, 42)) // !!!

Here silly() is passed by-value, this means that Scala tries to calculate its value to pass it to zero(), even if it has no use at all for it. And this would let the user waiting forever for its feedback.

Go to the full post

Functional Programming is here to stay

Martin Odersky talk at OSCON Java 2011, "Working Hard to Keep It Simple". A nice comparison between imperative and functional programming paradigm, and a very fast introduction to Scala. Even if a bit dated, still very interesting.

Go to the full post

Learning Apache Maven 3

I have just finished watching to this Pack video course about Maven, on youtube there is a preview that shows what you can expect from it.

It is designed to follow a Java programmer who knows nothing about Maven from the absolute beginning to writing a multi module project.

The major emphasis is on Maven for Windows plus Eclipse, just at the beginning it is shown how to install Maven on Linux and Mac, and how to integrate it also in Intellij and NetBeans. This is not a big issue, since we are in the Java world, and the platform differences are usually not too harsh.

The course is structured in four parts. After the installation/integration done in the introduction, we are guided to write a first "hello world" application. The third block is about creating a Web App by Maven that uses features from Struts2, Hibernate, and Spring. The last part shows how to develop a client/sever multi module project.

I found the standard price for this course a bit excessive, but in this bargains season, at less than five bucks, I wouldn't see how to complain.

It works fine as an introduction to the matter, in a couple of hours you can't expect to become a Maven master, but I'd say it succeeds in giving a good overview.

It has a few weak spots, too. Mainly, the audio comment is not lively at all, and there is a curious alternation in voices that I found distracting. Hear this, for instance, at around 1.30:

Go to the full post

Maven 3 video course

I have got a pointer to this video course on Apache Maven 3, you could also find a preview on YouTube that gives the gist of it.

It is a couple of hours long, it looks to be designed as an introduction to Maven for a Java developer who has no (or little) previous knowledge of it.

Since I use Maven in an unstructured way, it would probably good for me to find the way to spend time watching it. I plan to do it in the near future, and writing something more about it.

Go to the full post

Hello Android Studio

I have installed Android Studio, and I have made a Nexus 7 ready to be used as target device. Now I am ready to develop a first "Hello world" application.

Android Studio make it very easy.

Just select New Project from the file menu (or from the welcome dialog) and specified which properties you want to change from the default schema. I modified just three of them:

- Application name: Hello Android
- Module name: HelloAndroid
- Package name: dd.HelloAndroid

Then was just a matter of compiling and, after ensuring the target device was connected and available to my developer unit, ran it.

After confirming on Nexus that I wanted to debug that app, I saw it appearing. It doesn't say much. It just have the "Hello Android" name on the title bar and, wait a moment, an "Hello world!" message below it? Where does it come from?

We should remember that among the properties we were asked to confirm to create a new project, there was also something about the layout to be used by the application. Let's check it.

I opened the Project View, I clicked on my HelloAndroid project, src, main, res, layout, and I finally see it, activity_main.xml.

In it I see that the TextView property is filled with an @string/hello_world. So I opened the res, values, strings.xml, and I saw that a hello_world string resource was set for me to the value "Hello world!"

I don't want any message on my app, so I cut that line, went back to activity_main.xml, and remove from the "text" property the reference to that string. Re-launching HelloAndroid I can now enjoy its beautiful emptiness.

Go to the full post