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