Scala, a small example of Euclid's Algorithm

A small posting today, a simple example of Euclid's algorithm in Scala. This algorithm can be expressed very concisely and simply using recursion. This example demonstrates the use of tuples and map in the Scala language.

If you don't know, Euclid's algorithm is a ancient, simple algorithm for finding the greatest common divisor (GCD) for two integers, without factoring either of the two integers in question.

The algorithm can be expressed recursively thus:

function gcd(x, y)
  if (y == 0) x
  else gcd(y, x mod y)

The particular construction worth noting in this example is the use of tuples.

Tuples are like records, structures or groupings of variables that can be constructed using a (x, y, z) syntax when x, y and z are variables. A tuple can be decomposed by accessing its elements using the t _1 syntax, where t is the tuple and _1 is a method that accesses the first element in tuple. Tuple elements are therefore indexed using a base of 1.

The example defines numbers as a list of tuples, each tuple contains a pair of integers - the two integers to be applied to the GCD algorithm (Euclid's Algorithm).

The list of tuples is then "mapped" using the map function that takes each tuple and calls the function x => ((Int, Int), Int, Boolean), where x will be each tuple in the list in turn.

The tuple x is decomposed into its two integer component parts using the x _1 and x _2 syntax.

The returned tuple ((Int, Int), Int, Boolean) contains the original tuple of integers to be tested, the gcd values and a boolean indicating if the numbers are co-prime. The numbers are co-prime if the GCD is equal to 1.

I've included a few different ways to represent the function used by map, to use and decompose the tuple. The first solution using the tuple argument directly and accesses its members using the _1, _2 syntax directly. The second solution uses a function literal and the _ placeholder syntax on the map argument. The function literal uses the val (a, b) = x; sytax to decompose the tuple into and and b, but this is a bit clumsey/verbose. The 3rd solution is essentially the same as a the 2nd but the function is defined in-line.

The last solution is probably the nicest, it uses the case(a, b) syntax to decompose the tuple into a and b using pattern matching.


Example Code:

package test

object EuclidsAlgorithm {

 def main(arg : Array[String]) = {

   // define a list of tuples (Int, Int), pairs to test for coprimeness
   val numbers = (3, 6) :: (3, 7) :: (4, 8) :: (5, 45) :: (5, 43) :: (1071, 1029) :: (1071, 1023) :: (1071, 1021) :: Nil

   // #1. Working with the tuple directly, using the tuple _1, _2 syntax
   val res1 = numbers map ( x => ((x _1, x _2),  gcd(x _1, x _2), gcd(x _1, x _2) == 1 )  )

   // #2. Defining a function literal
   val f = (x : (Int, Int)) => { val (a, b) = x;  ((a, b), gcd(a, b), gcd(a, b) == 1) }

   // and using it with the _ placeholder syntax for the parameter representing each element of the list
   val res2 = numbers map ( f(_) )

   // #3. Using the #2 above but in-line
   val res3 = numbers map ( x => { val (a, b) = x; ((a, b), gcd(a, b), gcd(a, b) == 1) }  )

   // #3. Using a case match on the tuple to expose its components a and b. This is probably the nicest and most concise way
   val res4 = numbers map ( { case (a, b) => ((a, b), gcd(a, b), gcd(a, b) == 1) } )

   res4.foreach(println)
 }

 // Euclids algorithm, finds the GCD
 def gcd(a : Int, b : Int) : Int = {

   if (b == 0)
     a
   else
     gcd(b, a % b)
 }
}

Results:

((3,6),3,false)
((3,7),1,true)
((4,8),4,false)
((5,45),5,false)
((5,43),1,true)
((1071,1029),21,false)
((1071,1023),3,false)
((1071,1021),1,true)

.

Scala, insertion sort and pattern matching

This posting shows insertion sorting in Scala. Insertion sort is not a particularly efficient algorithm but this example code does demonstrate the use of pattern matching on lists using the match keyword and the case x :: y type expression.

val result = values match {

 case List() => List()

 case value :: valuesTail => insert(value, iSort(valuesTail))
}

The above code pattern matched the List values against 2 cases. The first being the empty list, in which case an empty list List() is returned. the second is the pattern value :: valuesTail, which puts the head of the list in value and the tail (the rest of the list) in valuesTail.


Example code:

package test

// Nb: This is not an efficient sorting algorithm but it domostrates
// some aspects of scala for representing algorithms, along with functions as first class objects and currying
object SortingTest {

   def main(args : Array[String]) {

       val list1 = 5 :: 2 :: 3 :: 1 :: 0 :: -1 :: 2 :: Nil

       val matcher = (x : Int, y : Int) => x < y

       val sortedList = insertionSort(list1, matcher)

       println("sortedList = " + sortedList.mkString(", "))

       val revMatcher = (x : Int, y : Int) => x >= y

       val revSortedList = insertionSort(list1, revMatcher)

       println("revSortedList = " + revSortedList.mkString(", "))
   }

   def insertionSort(values : List[Int], matcher : (Int, Int) => Boolean) : List[int] = {

       def iSort(values : List[Int]) : List[int] = {

           val result = values match {

               case List() => List()

               case value :: valuesTail => insert(value, iSort(valuesTail))
           }

           println("iSort called with " + values + ", result = " + result)

           result
       }

       def insert(value : Int, values : List[Int]) : List[Int] = {

           val result = values match {

               // if list is empty return new list with single element in it
               case List() => List(value)

               // otherwise insert into list in order, recursively
               case x :: xTail =>
                   if (matcher(value, x)) {
                       value :: values
                   }
                   else {
                       x :: insert(value, xTail)
                   }
           }
          
           println("insert called with " + value + ", values " + values + ", result = " + result)

           result
       }

       iSort(values)
   }
}

Results:

If you run the above example code the results are as follows:

iSort called with List(), result = List()
insert called with 2, values List(), result = List(2)
iSort called with List(2), result = List(2)
insert called with -1, values List(2), result = List(-1, 2)
iSort called with List(-1, 2), result = List(-1, 2)
insert called with 0, values List(2), result = List(0, 2)
insert called with 0, values List(-1, 2), result = List(-1, 0, 2)
iSort called with List(0, -1, 2), result = List(-1, 0, 2)
insert called with 1, values List(2), result = List(1, 2)
insert called with 1, values List(0, 2), result = List(0, 1, 2)
insert called with 1, values List(-1, 0, 2), result = List(-1, 0, 1, 2)
iSort called with List(1, 0, -1, 2), result = List(-1, 0, 1, 2)
insert called with 3, values List(), result = List(3)
insert called with 3, values List(2), result = List(2, 3)
insert called with 3, values List(1, 2), result = List(1, 2, 3)
insert called with 3, values List(0, 1, 2), result = List(0, 1, 2, 3)
insert called with 3, values List(-1, 0, 1, 2), result = List(-1, 0, 1, 2, 3)
iSort called with List(3, 1, 0, -1, 2), result = List(-1, 0, 1, 2, 3)
insert called with 2, values List(3), result = List(2, 3)
insert called with 2, values List(2, 3), result = List(2, 2, 3)
insert called with 2, values List(1, 2, 3), result = List(1, 2, 2, 3)
insert called with 2, values List(0, 1, 2, 3), result = List(0, 1, 2, 2, 3)
insert called with 2, values List(-1, 0, 1, 2, 3), result = List(-1, 0, 1, 2, 2, 3)
iSort called with List(2, 3, 1, 0, -1, 2), result = List(-1, 0, 1, 2, 2, 3)
insert called with 5, values List(), result = List(5)
insert called with 5, values List(3), result = List(3, 5)
insert called with 5, values List(2, 3), result = List(2, 3, 5)
insert called with 5, values List(2, 2, 3), result = List(2, 2, 3, 5)
insert called with 5, values List(1, 2, 2, 3), result = List(1, 2, 2, 3, 5)
insert called with 5, values List(0, 1, 2, 2, 3), result = List(0, 1, 2, 2, 3, 5)
insert called with 5, values List(-1, 0, 1, 2, 2, 3), result = List(-1, 0, 1, 2, 2, 3, 5)
iSort called with List(5, 2, 3, 1, 0, -1, 2), result = List(-1, 0, 1, 2, 2, 3, 5)
sortedList = -1, 0, 1, 2, 2, 3, 5
iSort called with List(), result = List()
insert called with 2, values List(), result = List(2)
iSort called with List(2), result = List(2)
insert called with -1, values List(), result = List(-1)
insert called with -1, values List(2), result = List(2, -1)
iSort called with List(-1, 2), result = List(2, -1)
insert called with 0, values List(-1), result = List(0, -1)
insert called with 0, values List(2, -1), result = List(2, 0, -1)
iSort called with List(0, -1, 2), result = List(2, 0, -1)
insert called with 1, values List(0, -1), result = List(1, 0, -1)
insert called with 1, values List(2, 0, -1), result = List(2, 1, 0, -1)
iSort called with List(1, 0, -1, 2), result = List(2, 1, 0, -1)
insert called with 3, values List(2, 1, 0, -1), result = List(3, 2, 1, 0, -1)
iSort called with List(3, 1, 0, -1, 2), result = List(3, 2, 1, 0, -1)
insert called with 2, values List(2, 1, 0, -1), result = List(2, 2, 1, 0, -1)
insert called with 2, values List(3, 2, 1, 0, -1), result = List(3, 2, 2, 1, 0, -1)
iSort called with List(2, 3, 1, 0, -1, 2), result = List(3, 2, 2, 1, 0, -1)
insert called with 5, values List(3, 2, 2, 1, 0, -1), result = List(5, 3, 2, 2, 1, 0, -1)
iSort called with List(5, 2, 3, 1, 0, -1, 2), result = List(5, 3, 2, 2, 1, 0, -1)
revSortedList = 5, 3, 2, 2, 1, 0, -1

.

Scala, example of Diffie-Hellman

Another in the sequence of postings on Scala by simple example, this one shows an example of Diffie-Hellman to establish a shared secret over a public communication channel without that secret being revealed. Diffie-Hellman itself is prone to man-in-the-middle attacks, this example does not attempt to deal with that problem (normally addressed with authentication of some type).

The example sets up the canonical Alice and Bob, with shared public parameters g (generator) = 5 and p (prime modulus) = a large 128 random prime number.

Alice and Bob each create their secret key [sk] (a large 128 random number) and generate:

y = g^sk mod p

Alice and Bob then swap the result of this calculation.

From this, Alice and Bob both perform y^sk mod p to create a new value, the shared secret key which will be the same for both Bob and Alice even though they start with different random secret keys.

This is because:

(g^x)^y is the same as (g^y)^x

From a Scala perspective, the interesting things to note are:

• Ease of use of large integers using the BigInt class as if it were a primitive type.
• Constructors to create immutable instances containing g, p and name.
• Companion object to provide helper function to wrap probable prime function.

Example code:

package test

import scala.util.Random;


object DiffieHellmanTest {

   val p = DiffieHellman.randomPrime(128)
   val g = 5

   def main(args : Array[String]) {

       // alice and bob initialise with the public parameters for DH, g and p
       val alice = new DiffieHellman(g, p, "Alice")
       val bob = new DiffieHellman(g, p, "Bob")

       // alice and bob generate their own secret keys and public keys
       alice.createSecretKey();
       bob.createSecretKey();

       val a1 = alice.getPublicKey();
       val b1 = bob.getPublicKey();

       println("a1 = " + a1)
       println("b1 = " + b1)

       // alice and bob exchange public keys
       bob.setPeerPublicKey(a1)
       alice.setPeerPublicKey(b1)

       // alice and bob compute their shared secret key
       val alicesk = alice.createSharedKey()
       val bobsk = bob.createSharedKey()

       println("Done, alice sk = " + alicesk + ", bob sk = " + bobsk)
   }
}

object DiffieHellman {

   def randomPrime(n : Int) : BigInt = { // return a random value with n digits

       val rnd = new Random();

       BigInt.probablePrime(n, rnd)
   }
}

class DiffieHellman(val g : Int, p : BigInt, name : String) {

   var secretKey : BigInt = 0
   var peerPublicKey : BigInt = 0


   def createSecretKey() {

       secretKey = random(128)

       println(name + " secretKey = " + secretKey)
   }

   def setPeerPublicKey(x : BigInt) {

       peerPublicKey = x
   }

   def getPublicKey() : BigInt = {

       doExpMod(g, secretKey, p)
   }

   def random(n : Int) : BigInt = { // return a random value with n digits

       val rnd = new Random();

       BigInt(n, rnd)
   }

   def createSharedKey() : BigInt = {

       doExpMod(peerPublicKey, secretKey, p)
   }

   private def doExpMod(x : BigInt) : BigInt = {

       println("doExpMod g = " + g + ", x = " + x + ", p = " + p)
       doExpMod(g, x, p)
   }

   private def doExpMod(g : BigInt, x : BigInt, m : BigInt) : BigInt = {

       g.modPow(x, m)
   }
}

Results:

(Numbers may vary between runs of course!)

Alice secretKey = 197977683133285508684427285955258922592
Bob secretKey = 54690551885126631242925351374829949140
a1 = 4317900055693480003952964194026338337
b1 = 58782279533775365647086521912939284670
Done, alice sk = 275531174494727646906973085281579443284, bob sk = 275531174494727646906973085281579443284

The secret keys for Alice and Bob normally wouldn't be revealed, but they've been output here for debug purposes.

Note that the final shared secret key is the same for both Alice and Bob, which could then be used to establish a secure communication channel using symmetric encryption.


.

Scala, Square roots, Netwon's method, closures and foldLeft

A simple Scala example. This one computes square roots by successive approximation using Newton's method, defined in a class SquareRoot. A companion object is also used to define the precision constant, the target tolerance we'll use to decide when to stop approximating.

There are two version of the function. squareRootSimple is a simple implementation. The method squareRoot improves on this by refactoring the code to use a closure to capture x, the value for which we are finding the square root. Also, the overloaded average function takes a List and uses list.foldLeft(0.0).(_ + _) which means apply x+y to list element pairs, starting with 0.0, running through all the elements in the list, thus summing all the elements.

Example of the use of foldLeft:

list.foldLeft(0.0).(_ + _)

Which could also be written as:

(start /: list)(_ + _)

• /: is the foldLeft operator, equivalent to the .foldLeft method on a list
• \: is the foldRight operator, equivalent to the .foldRight method on a list

The fold operator is like a pattern that crops up fairly often in imperative programming, it looks something like this:

B b = startItem

for(final T a : listOfT) {
 b = method(b, a);
}

return b;

Example code:

package test

object SquareRootsTest {

    def main(args : Array[String]) {

        val squareRoot = new SquareRoot()

        assert(((squareRoot.squareRoot(9) - 3) abs) < SquareRoot.precision)
        assert(((squareRoot.squareRoot(64) - 8) abs) < SquareRoot.precision)

        val res1 = squareRoot.squareRoot(842)
        println("square root of 842 = " + res1 + ", " + res1 + " squared = " + res1 * res1)
    }
}


object SquareRoot {

    val precision = 0.000001
}

class SquareRoot {

    def squareRootSimple(x : Double) : Double = (

        squareRootIter(1.0, x)
    )

    def squareRootIter(guess : Double, x : Double) : Double = {

        if (goodEnough(guess, x)) {
          guess
        }
        else {
          squareRootIter(improveGuess(guess, x), x)
        }
    }

    private def improveGuess(guess : Double, x : Double) : Double = {

        val newguess = average(guess, x / guess)
        println("guess for x " + x + " improved to = " + newguess)
        newguess
    }

    private def goodEnough(guess : Double, x : Double) = {

        (square(guess) - x).abs  < SquareRoot.precision
    }

    def squareRoot(x : Double) : Double = {

        def squareRootIter(guess : Double, x : Double) : Double = {

            if (goodEnough(guess)) {
              guess
            }
            else {
              squareRootIter(improveGuess(guess), x)
            }
        }

        def improveGuess(guess : Double) : Double = {

            val newguess = average(List(guess, x / guess))
            println("guess for x " + x + " improved to = " + newguess)
            newguess
        }

        def goodEnough(guess : Double) = {

            (square(guess) - x).abs  < SquareRoot.precision
        }

        squareRootIter(1.0, x)
    }

    private def average(x : Double, y : Double) : Double = {

        (x + y) / 2
    }

    private def average(list : List[Double]) : Double = {

        //println("value = " + list.mkString)
        //(0.0 /: list)(_ + _) / list.size
        list.foldLeft(0.0)(_ + _) / list.size
    }

    private def square(value : Double) : Double = {

        value * value
    }
}

Results:

guess for x 9.0 improved to = 5.0
guess for x 9.0 improved to = 3.4
guess for x 9.0 improved to = 3.023529411764706
guess for x 9.0 improved to = 3.00009155413138
guess for x 9.0 improved to = 3.000000001396984
guess for x 64.0 improved to = 32.5
guess for x 64.0 improved to = 17.234615384615385
guess for x 64.0 improved to = 10.474036101145005
guess for x 64.0 improved to = 8.292191785986859
guess for x 64.0 improved to = 8.005147977880979
guess for x 64.0 improved to = 8.000001655289593
guess for x 64.0 improved to = 8.00000000000017
guess for x 842.0 improved to = 421.5
guess for x 842.0 improved to = 211.7488137603796
guess for x 842.0 improved to = 107.86261164282149
guess for x 842.0 improved to = 57.83441917633403
guess for x 842.0 improved to = 36.19661181949908
guess for x 842.0 improved to = 29.729228773452704
guess for x 842.0 improved to = 29.025762097895374
guess for x 842.0 improved to = 29.017237509256656
guess for x 842.0 improved to = 29.017236257093842
square root of 842 = 29.017236257093842, 29.017236257093842 squared = 842.0000000000015

Source Scheme Code:

(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
A guess is improved by averaging it with the quotient of the radicand and the old guess:
(define (improve guess x)
(average guess (/ x guess)))
where
(define (average x y)
(/ (+ x y) 2))
We also have to say what we mean by ``good enough.'' The following will do for illustration, but it is not
really a very good test. (See exercise 1.7.) The idea is to improve the answer until it is close enough so that
its square differs from the radicand by less than a predetermined tolerance (here 0.001):22
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001)) 

References:

Blog about fold Left: http://blog.tmorris.net/scalalistfoldleft-for-java-programmers/


.

Scala, for comprehensions

This post contains some examples of Scala's for comprehension.

A for loop in Scala can be written in the imperative style and will behave rather much the same as a Java for loop, especially the enhanced Java for loop from Java 5.0.

However, this type of simple imperative looping doesn't touch on the power and flexibility of Scala's for comprehension, when used as used in a functional programming context.

In particular, some of the key differences are:

• A for comprehension can be a value itself. The value is a product of the yield statement used within the expression body. Since a for comprehension iterates over a list or sequence, the resulting value of a for comprehension is typically a list too.
• A for comprehension uses a generator, written in the form item <- listOfItems to define the items to be iterated over
• Multiple generators may be used, somewhat analogous to a nested for loop within a for loop in imperative programming
• In addition to generators, a guard can be used to filter or restrict the values
• The for syntax can use parenthesis with semicolon delimited generators and guards or braces - both are equivalent
• The iterations my differ when compared to a seeming equivalent imperative construct, because the implementation is fundamentally different. In particular the list of items to be used is determined using the generator(s) and guard(s) before the body is run, so for example flags used in guards that are modified in the body may not produce the expected result (from an imperative perspective).
• Generators can be "projected" using the .project function.

Examples of Scala for comprehension:

package test

object ForComprehensionTest {
    def main(args : Array[String]) {

        // create a couple of simple lists...
        val list1 = "Apples" :: "Oranges" :: "Bananas" :: "Avocados" :: Nil
        val list2 = 11 :: 22 :: 33 :: 44 :: 55 :: 66 :: Nil

        // simple comprehension with one generator and guard
        val res1 = for(item1 <- list1 if item1.startsWith("A"))
            yield item1

        assert(res1 == List("Apples", "Avocados"))
        res1.foreach(println);

        // more complex comprehension, two generators within {brace} syntax with two guards
        val res2 = for {
                item1 <- list1 if item1.startsWith("A")
                item2 <- list2 if item2 % 3 == 0
            }
            yield item2 + " " + item1

        assert(res2 == List("33 Apples", "66 Apples", "33 Avocados", "66 Avocados"))
        res2.foreach(println);

        // as above but using () parens and ; semi-colon syntax instead
        val res3 = for ( item1 <- list1 if item1.startsWith("A");
                        item2 <- list2 if item2 % 3 == 0 )
            yield item2 + " " + item1

        assert(res3 == List("33 Apples", "66 Apples", "33 Avocados", "66 Avocados"))
        res3.foreach(println);

        println("simple guard item == 22")
        for (item <- list2 if item == 22) println(item)

        println("simple comprehension mkString = " + (for (item <- list2 if item % 2 == 0) yield item).mkString)

        // from an imperative / Java perspective you might expect this to stop with item = 22
        // but it continues on because !found is evaluated as always true (irrefutable pattern) when determining what to iterate over
        var found = false
        for (item <- list2 if !found) {

            if (item == 22)
                found = true

            println("without projection, item == 22? item = " + item)
        }

        // with the .projection call, it works more like you might expect from an imperative perspective
        found = false
        for (item <- list2.projection if !found) {

            if (item == 22)
                found = true

            println("with .projection, item==22? item = " + item)
        }

        found = false
        for (item <- list2.projection.takeWhile(item => !found)) {

            if (item == 22)
                found = true

            println(".projection.takeWhile(item => ! found) = " + item)
        }
    }
}

Results:

Apples
Avocados
33 Apples
66 Apples
33 Avocados
66 Avocados
33 Apples
66 Apples
33 Avocados
66 Avocados
simple guard item == 22
22
simple comprehension mkString = 224466
without projection, item == 22? item = 11
without projection, item == 22? item = 22
without projection, item == 22? item = 33
without projection, item == 22? item = 44
without projection, item == 22? item = 55
without projection, item == 22? item = 66
with .projection, item==22? item = 11
with .projection, item==22? item = 22
.projection.takeWhile(item => ! found) = 11
.projection.takeWhile(item => ! found) = 22

Other useful things to know:

In a for comprehension if you want to iterate over a collection you can create a tuple of (element, index) pairs using syntax of the form:

for ((elem, index) <- iter.zipWithIndex) {
    // now we can access element of each iteration along with its associated numerical index!
}

Resources:

A good explanation of for comprehensions can be found here http://creativekarma.com/ee.php/weblog/comments/the_scala_for_comprehension_from_a_java_perspective/


.

OpenSolaris - ZFS and Zones

Today, just a quick note on setting up an OpenSolaris 10 system local zone.

Firstly, you need to ensure there's a suitable ZFS file system created for the zone, then you define and install the zone itself. The basic steps are quite simple, here's a basic example as a starter:

Note: Global zone means the default zone, the basic machine assuming no zones have been created yet. Local zone is a created zone within the global zone, as described here.


As root on the global zone:

Take a look at available pools:

global# rpool list

On my system, with one disk fully used, I have rpool already, but no other pools.

Creating a new ZFS filesystem under rpool as follows:

global# zfs create /rpool/zones

Now create a new zone configuration, here is a really basic minimal zone config with networking, taken from the zone FAQ.

global# zonecfg -z my-zone
global# zonecfg:my-zone> create
global# zonecfg:my-zone> set zonepath=/zones/zone_roots/my-zone
global# zonecfg:my-zone> add net
global# zonecfg:my-zone:net> set address=10.1.1.1
global# zonecfg:my-zone:net> set physical=hm0
global# zonecfg:my-zone:net> end
global# zonecfg:my-zone> commit
global# zonecfg:my-zone> exit

Install the zone (if this fails, check permissions, shown as *1 below)

global# zoneadm -z my-zone install

Boot the installation!

global# zoneadm -z my-zone boot

Login to the new zone:

global# zlogin -C my-zone

*1 change permissions on the dataset if necessary

global# chown root /rpool/zones/my-zone
global# chmod 700 /rpool/zones/my-zone


A more complete zone configuration, for reference:

create -b
set zonepath=/zones/dev1
set autoboot=true
add inherit-pkg-dir
set dir=/lib
end
add inherit-pkg-dir
set dir=/platform
end
add inherit-pkg-dir
set dir=/sbin
end
add inherit-pkg-dir
set dir=/usr
end
add inherit-pkg-dir
set dir=/opt/apache22
end
add inherit-pkg-dir
set dir=/opt/csw
end
add inherit-pkg-dir
set dir=/opt/mysql5
end
add inherit-pkg-dir
set dir=/opt/pgsql829
end
add inherit-pkg-dir
set dir=/opt/php5
end
add fs
set dir=/opt/SUNWspro
set special=/opt/SUNWspro
set type=lofs
add options ro
end
add net
set address=10.80.117.152
set physical=bge0
end


Resources:

ZFS: http://www.linuxdynasty.org/zfs-howto-howto-create-a-zfs-file-system.html

Zones: http://opensolaris.org/os/community/zones/faq/#sa_create


.

Scala, traits and mix-ins

Continuing on in the series of Scala blogs, showing Scala features by example, this post attempts to show the operation of Traits. Traits are rather like classes but designed to allow rich feature composition by allowing "mix-in" of required traits dynamically, at run time. Traits achieve what can look like multiple inheritance, without the pitfalls and limitations of multiple inheritance. Conversely then, you might think traits are equivalent to Java's interfaces. Whist similar, the key difference is that traits can (and usually do) contain implementations (method bodies). When a trait method implementation makes a call to super, it is dynamically resolved as the class is linearised.

When traits are combined with classes to create extended behaviour, this process is known as mixin and the traits are said to be mixed-in or mixins.

The example below shows the behaviour of the plain traits class using its putMsg method, and then its behaviour when mixed-in with TraitAddA, TraitAddA and TraitAddB and then with TraitAddA and TraitAddB reversed (ordering of the with parts is significant).

As well as mixin with the new keyword, class TraitABClass shows that traits can be used as mixins with normal classes too, at the point they are declared using the with keyword.


Example Scala file showing the operation of Traits:

package test

object TraitsTest {

  def main(args : Array[String]) {

    val traits : Traits = new Traits()

    traits.putMsg("Hello!")

    println("traits, value = " + traits.toString)

    val traitsA : Traits = new Traits() with TraitAddA

    traitsA.putMsg("Hello!")
    
    println("traitsA, value = " + traitsA.toString)

    val traitsAB : Traits = new Traits() with TraitAddA with TraitAddB

    traitsAB.putMsg("Hello!")

    println("traitsAB, value = " + traitsAB.toString)

    val traitsBA : Traits = new Traits() with TraitAddB with TraitAddA

    traitsBA.putMsg("Hello!")

    println("traitsBA, value = " + traitsBA.toString)

    val traitsABClass : TraitsABClass = new TraitsABClass

    traitsABClass.putMsg("Hello2")

    println("traitsABClass, value = " + traitsABClass.toString)
  }
}

class TraitsABClass extends Traits with TraitAddA with TraitAddB

class Traits {

  var msg : String = ""

  def putMsg(m : String) {

    msg = m
  }

  override def toString = {

    msg
  }
}

trait TraitAddA extends Traits {

  abstract override def putMsg(m : String) = {

    super.putMsg("A" + m)
  }
}

trait TraitAddB extends Traits {

  abstract override def putMsg(m : String) = {

    super.putMsg("B" + m)
  }
}

Program execution results:

traits, value = Hello!
traitsA, value = AHello!
traitsAB, value = ABHello!
traitsBA, value = BAHello!
traitsABClass, value = ABHello2

.

Modular exponentiation

For any inquisitive minds, the fast Modular exponentiation used in the last post (Scala example) might at first glance seem odd, perhaps.

What we want to achieve is x = b^n mod m

where b^n is performed first, the result in then operated on by mod m. Mathematically this is what we are doing, this is what we want to achieve.

However, the expmod function computes the value recursively, applying mod at each step of recursion (on each recursion result).

This is in fact a better way to approach the problem, as the intermediate values are kept small (between 0 and m-1) rather than growing exponentially (with potential overflow/performance problems), only to be operated on by modulus to shrink the value back down again!

Here is a simple Scala snippet that compares expMod with fastExp mod m, with some debugging added to show the intermediate values at each stage of recursion.

package test

import java.util.Random;

object ExpTest {

 def main(args : Array[String]) {

   println("fastExpt(4, 7) % 9) = " + fastExpt(4, 7) % 9)
   println("expMod(4, 7, 9) = " + expMod(4, 7, 9))

   println("fastExpt(5, 12) % 6) = " + fastExpt(5, 12) % 6)
   println("expMod(5, 12, 6) = " + expMod(5, 12, 6))
}

 def expMod(base : Int, exp : Int, m : Int) : Int = {

   val res = if (exp == 0)
     1
   else if (even(exp))
     remainder(square(expMod(base, (exp / 2), m)), m)
   else
     remainder(base * expMod(base, exp - 1, m), m)

   println("expMod: b = " + base + ", exp = " + exp + ", m = " + m + ", res = " + res)
   res
 }

 def fastExpt(b : Int,  exp : Int) : Int = {

   val res = if (exp == 0)
     1
   else if (even(exp))
     square(fastExpt(b, exp / 2))
   else
     b * fastExpt(b, exp - 1)

   println("fastExpt: b = " + b + ", exp = " + exp + ", res = " + res)
   res
 }

 def square(n : Int) : Int = {

   n * n
 }

 def even(n : Int) : Boolean = {

   remainder(n, 2) == 0
 }

 def remainder(n : Int, d : Int) : Int = {

     n % d
 }
}

Results are as follows:

fastExpt: b = 4, exp = 0, res = 1
fastExpt: b = 4, exp = 1, res = 4
fastExpt: b = 4, exp = 2, res = 16
fastExpt: b = 4, exp = 3, res = 64
fastExpt: b = 4, exp = 6, res = 4096
fastExpt: b = 4, exp = 7, res = 16384
fastExpt(4, 7) % 9) = 4
expMod: b = 4, exp = 0, m = 9, res = 1
expMod: b = 4, exp = 1, m = 9, res = 4
expMod: b = 4, exp = 2, m = 9, res = 7
expMod: b = 4, exp = 3, m = 9, res = 1
expMod: b = 4, exp = 6, m = 9, res = 1
expMod: b = 4, exp = 7, m = 9, res = 4
expMod(4, 7, 9) = 4
fastExpt: b = 5, exp = 0, res = 1
fastExpt: b = 5, exp = 1, res = 5
fastExpt: b = 5, exp = 2, res = 25
fastExpt: b = 5, exp = 3, res = 125
fastExpt: b = 5, exp = 6, res = 15625
fastExpt: b = 5, exp = 12, res = 244140625
fastExpt(5, 12) % 6) = 1
expMod: b = 5, exp = 0, m = 6, res = 1
expMod: b = 5, exp = 1, m = 6, res = 5
expMod: b = 5, exp = 2, m = 6, res = 1
expMod: b = 5, exp = 3, m = 6, res = 5
expMod: b = 5, exp = 6, m = 6, res = 1
expMod: b = 5, exp = 12, m = 6, res = 1
expMod(5, 12, 6) = 1

Most importantly, the functions yield the same results, but expMod achieves it in a more efficient and scalable way.

Just a small posting, as whilst appearing simple, modular exponentiation underpins much of modern cryptographic methods, and efficient algorithms are important.


.

Scala, Fermat's little theorem

Today, another Scala posting by way of example, using the interesting Fermat's Little Theorem test for primality. This is a probabilistic test that provides no false negatives (if a number is found not prime, that is certain) but can provide false positives (a number indicated as prime is not certain to be so). The test can be run a number of times with a different base value (a) to gain increasing confidence that the number is prime.

Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

There are a small set of special numbers that "fool" this test, these are the Carmichael numbers. Further details can be found here http://en.wikipedia.org/wiki/Carmichael_number

Carmichael numbers are extremely rare. There are only 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601.

Because the Carmichael numbers are a special subset of the Fermat prime numbers that satisfy the same condition, they can be known as absolute Fermat pseudoprimes. The Fermat "primes" can be known as Fermat pseudoprimes. If we remove the absolute Fermat pseudoprimes from the Fermat Pseudoprimes then we end up with the absolute primes.

There are revised versions of this test that remove the false positive Carmichael numbers, such as the famous Miller-Rabin test (Miller 1976, Rabin 1980). This starts from an alternate form of Fermat's Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the (n - 1)st power is congruent to 1 modulo n.

For this Scala example, I'm only using the original Fermat's Little Theorem. Here is the Scala file, the main contains a number of test cases.

import java.util.Random;

object FermatsLittleTheorem {

 def main(args : Array[String]) {

   val attempts = 10;  // the number of attempts, higher numbers give greater confidence in positive results.

   var n = 17;
   println("result1: n = " + n + ", res = " + fastPrime(n, attempts))  // should be true
   n = 13
   println("result2: n = " + n + ", res = " + fastPrime(n, attempts))  // should be true
   n = 11
   println("result3: n = " + n + ", res = " + fastPrime(n, attempts))  // should be true
   n = 9
   println("result4: n = " + n + ", res = " + fastPrime(n, attempts))  // should be false
 }

 def fastPrime(n : Int, times : Int) : Boolean = {

   if (times == 0)
     true
   else
     if (fermatTest(n)) fastPrime(n, times - 1) else false
 }

 def expmod(base : Int, exp : Int, m : Int) : Int = {

   if (exp == 0)
     1
   else if (even(exp))
     remainder(square(expmod(base, (exp / 2), m)), m)
   else
     remainder(base * expmod(base, exp - 1, m), m)
 }

 def square(n : Int) : Int = {

   n * n
 }

 def even(n : Int) : Boolean = {

   remainder(n, 2) == 0
 }

 def remainder(n : Int, d : Int) : Int = {

     n % d
 }

 def fermatTest(n : Int) : Boolean = {

   def tryIt(a : Int) : Boolean = {

     val res = expmod(a, n, n)
     println("res = " + res + ", a = " + a + ", n = " + n + ", a % n = " + a % n)
     res == a % n
   }

   tryIt(random(n - 1) + 1)    // get a random int between 1 and n
 }

 def random(n : Int) : Int = { // return a random value between 0 and n - 1

   val random = new Random();

   random.nextInt(n);
 }
}

This was refactored from the following Scheme code, as an exercise in Scala:

(define (expmod base exp m)
 (cond ((= exp 0) 1)
   ((even? exp)
    (remainder (square (expmod base (/ exp 2) m))
      m))
   (else
     (remainder (* base (expmod base (- exp 1) m))
      m))))

 (define (even? n)
   (= (remainder n 2) 0))

 (define (fermat-test n)
   (define (try-it a)
     (= (expmod a n n) a))
     (try-it (+ 1 (random (- n 1)))))

 (define (fast-prime? n times)
   (cond ((= times 0) true)
     ((fermat-test n) (fast-prime? n (- times 1)))
   (else false)))

A note of the tail recursiveness of the function fastPrime:

Comment (summary) from PaulP from #scala:

"It's not tail recursive but only for one reason. It's neither final nor private. It just needs to be able to determine it won't be overridden. It'd be tailrec if in an object.

There has also been discussion of a @tailrec annotation so you could get a compiler warning if a tagged function wasn't compiled tailrec as you'd thought."


.

Scala, placeholders and partial functions

A couple of Scala examples to demonstrate the use of place-holder syntax and partial functions. These two things are related but partial functions goes beyond syntactical conciseness to provide new and powerful constructions.

Substitution:

package test

object Placeholders {

  def main(args : Array[String]) {

    val myNumbers = 1 to 10 //List(1, 2, 3, 4, 5, 6, 7, 8, 9);

    println("Greater than 3")

    var result = myNumbers.filter((x : Int) => x > 3)

    result.foreach(println) // result.foreach((x) => println(x))

    println("Greater than 4")

    result = myNumbers.filter(x => x > 4)

    result.foreach(println)

    println("Greater than 5")

    result = myNumbers.filter(_ > 5) // _ placeholder _ for

    result.foreach(println)
  }
}

Partially applied functions:

Partial functions are functions defined with only some of the arguments (or none), as the following example demonstrates:

package test

object PartiallyAppliedFunctionsTest {

  def main(args : Array[String]) {

    val partiallyAppliedFunctions = new PartiallyAppliedFunctions();

    println("sum 4 arg 1 + 2 + 3 + 4 = " + partiallyAppliedFunctions.getSum4arg()(1, 2, 3, 4))                  // expect 10

    println("partiallyAppliedFunction 3 arg, 1 + 2 + 3 = " + partiallyAppliedFunctions.getSum3arg()(1, 2, 3))   // expect 6

    println("partiallyAppliedFunction 2 arg, 1 + 2 = " + partiallyAppliedFunctions.getSum2arg()(1, 2))          // expect 3
  }
}

class PartiallyAppliedFunctions() {

  private def sum(i1 : Int, i2 : Int, i3 : Int, i4 : Int) = {

    i1 + i2 + i3 + i4
  }

  def getSum4arg() = {

    sum _
  }

  def getSum3arg() : (Int, Int, Int) => Int = {

    sum(0, _ : Int, _ : Int, _ : Int)
  }

  def getSum2arg() : (Int, Int) => Int = {

    sum(0, 0,  _ : Int, _ : Int)
  }
}

The above example shows the function _ syntax to reference a function as a value.

Also, functions getSum3arg() and getSum4arg() show the use of partial functions to re-use an existing function by partially defining and supplying some of the arguments.


.

Scala, example finding prime numbers

Firstly, Happy New Year! Happy 2009!

Continuing on with Scala, here is a further example, a simple test for prime numbers, also showing re-factoring from Scheme to Scala.

This simple example tests for primality, based on the simple algorithm taken from SICP in the following example given in the programming language Scheme:

package test

object FindPrimes {

  def main(args : Array[String]) {

    for (n <- 1 to 500) {

      val d = smallestDivisor(n)
      println(n + ": lcd = " + d + (if (n == d) " prime!" else " not prime") )
    }
  }

  def isPrime(n : Int) : Boolean = {

    n == smallestDivisor(n)
  }

  def smallestDivisor(n : Int) : Int = {

    findDivisor(n, 2)
  }

  def findDivisor(n : Int, testDivisor : Int) : Int = {

    if (square(testDivisor) > n)
      n
    else if (divides(testDivisor, n))
      testDivisor
    else
      findDivisor(n, testDivisor + 1)
  }

  def square(n : Int) : Int = {

    n * n
  }

  def divides(d : Int, n : Int) : Boolean = {

    (n % d) == 0
  }
}

The above example has a main that can be run. The code tests the first 500 integers for primality using the simple, unoptimised prime test algorithm which looks for the least divisor of n (below root(n)).

It's worth pointing out that the findDivisor function is recursive, but if you look at the way it's constructed, the recursion appears at the end of the construction - and is thus amenable to tail recursion (optimisation).

Note: When testing for Primes in this way, if no divisor d of n is found less than root(n) then the number is prime, thus the search for divisors can end at root(n). This is because for any divisor d of n, there is a corresponding divisor n/d. So the maximum value for either/both occurs at root(n), beyond this, as d increases above root(n), n/d decreases below root(n) symmetrically.

"If d is a divisor of n, then so is n/d. But d and n/d cannot both be greater than n."


In the statement:

println(n + ": lcd = " + d + (if (n == d) " prime!" else " not prime") )

We can see the use of an if expression. In this situation is looks rather like Java's ternary if construct, but Scala's if expressions along with other expressions like for etc are fundamentally different, in that the construct equates to a value, in this example a value of type implicitly determined as String.

However, it's worth noting that the following alteration to the println statement does not output "prime!" text:

println(n + ": lcd = " + d + (if (n == d) " prime!") )

My presumption (will confirm this) is that in the first case, all paths return String, so type inference determines type String. In the second case, the implicit else statement is missing, so not all paths return a String, so type inference probably determines a type of Nothing and the result is lost.

Update: As Jorge Ortiz has kindly pointed out in his comment, this is because the type inference of the Least Upper Bound (LUB). If not all paths return a type, the overall inference is Unit (like void) because this is the only safe inference that covers all cases.


.