Programação Multiparadigma (2014/2015)

Teórica 03 (23/Set/2014)

All the elements of an infinite data structure must be accessible!
Controlling of the order of evaluation using non-strict evaluation.
Closures.
Implementing non-strict lists in Java.
The primitive non-strict mechanisms of Scala.
Reimplementing non-strict lists in Scala using call-by-need.
A sophisticated class for call-by-need lists in Scala.

All the elements of an infinite data structure must be accessible!

For example, consider the infinite list of the odd numbers

val zodd: ZList[Int] = ZNode(1, u=>zadd(zodd,2))

and the infinite list of the even numbers:

val zevan: ZList[Int] = ZNode(2, u=>zadd(zeven,2))

If you concatenate both lists, like this,

zappend(zodd, zevan)

you will get a new list where all the even numbers appear after the odd numbers. This means that if you want to reach the even numbers, you must first transverse all the odd numbers. But this amount to saying that the even numbers are not even there because they are beyond infinite!

In a computational setting, all the elements of an infinite data structure must be reachable. You will need to remember this whenever you build a data structure.

Usually, keeping the elements sorted will do the trick. For example, a suitable way of joining the lists zodd and zeven is by means of the function zmerge, like this:

zmerge(zodd, zevan)

Controlling of the order of evaluation using non-strict evaluation

This is the last application of non-strict evaluation we will study: defining new operations where we can control if and when should the parameter be evaluated.

In the following example, we pass the second argument in the form of a parameterless function to obtain non-strictness. This is the classic example of the cand operation (conditional-and):

def cand(a: Boolean, b: Unit=>Boolean) = if(a) b(()) else false

Notice that the second parameters is evaluated only if necessary. See the following example of use:

cand(5<3, u=>7<5)

This technique works in any functional language, even a eager functional language like OCaml, for example.

Closures

The concept of closure is a sophisticated concept that lurks behind the seemingly simplicity of all functional languages.

Let us examine closely, again, the method zadd from the previous lesson:

def zadd(l: ZList[Int], n: Int): ZList[Int] =
{
    l match {
        case ZNil => ZNil
        case ZNode(x,xs) => ZNode(x+n, u=>zadd(xs(()), n))
    }
}

Note the anonymous function that appears in the second branch of the match. This function depends on the non-local variables xs and n, so doubts may arise about what might happen when the function zadd returns because those variables seemingly will cease to exist. When the anonymous function is evaluated later, how will it obtain the correct values for xs and n?

What happens is that each function is internally represented by its code along with a representation of its surrounding environment. This surrounding environment will be kept alive as long as the anonymous function remains active. This pair of two elements <code, environment> is called a closure. Closures constitute a powerful mechanism that is available in functional languages.

The concept of closure was first implemented in the functional language Scheme, in the 1960s.

Implementing non-strict lists in Java

It is possible to implement non-strict lists in Java. The biggest problem is the representation of the delayed lists, because Java does not support functions. But a function can be represented using an object with a method inside and some features of full closures can be emulated in Java using anonymous classes and final variables and attributes. These two mechanisms were introduced in version 1.1 of Java in 1997 (Java 1.1).

Below, we define non-strict lists.

This is the type we will use instead of Unit=>ZList:

interface ZListDelayed { // The "delayed lists" will be instances of inner
    ZList fun() ;        // anonymous classes implementing this interface
}

The type ZList is a sum type with two variants, ZNode and ZNil:

interface ZList {
    int Head() ;
    ZList Tail() ;
    boolean IsEmpty() ;
    void Print() ;
    ZList Add(int n) ;
}

class ZNode implements ZList {
    private int head ;
    private ZListDelayed tail ;

    ZNode(int h, ZListDelayed t) { head = h ; tail = t ; }

    public int Head() { return head ; }
    public ZList Tail() { return tail.fun() ; }
    public boolean IsEmpty() { return false ; }
    public void Print() {
        System.out.print("[" + head) ;
        for( ZList l = Tail() ; !l.IsEmpty() ; l = l.Tail() )
            System.out.print("; " + l.Head()) ;
        System.out.println("]") ;
    }
    public ZList Add(final int n) {
      // Create an instance of a inner anonymous class implementing the interface ZListDelayed.
      // Only works because the parameter n was declared as final.
        ZListDelayed base = new ZListDelayed()
            { public ZList fun() { return Tail().Add(n) ; } } ;
      // Returns the new list
        return new ZNode(head + n, base) ;
    }
}

class ZNil implements ZList {
    ZNil() {}

    public int Head() { throw new Error("Head: Empty list!") ; }
    public ZList Tail() { throw new Error("Tail: Empty list!") ; }
    public boolean IsEmpty() { return true ; }
    public void Print() { System.out.println("[]") ; }
    public ZList Add(int n) { return this ; }
}

class TestZLists {
    static ZList zints ; // Must be this way, not initialized. Otherwise, it does not compile.
    public static void main(String[] args) {
        zints = new ZNode(1, new ZListDelayed() { public ZList fun() { return zints.Add(1) ; } }) ;  // Too verbose :(
        zints.Print() ; // Prints an infinite list of integers. CTRL-C to stop.
    }
}

Using Java 8, the two expressions of the form "new ZListDelayed() ..." can be replaced by lambda expressions. For example, the definition of "zints" becomes much more compact:

    zints = new ZNode(1, ()->zints.Add(1)) ;

The primitive non-strict mechanisms of Scala

There are three primitive mechanism for direct support of non-strict evaluation in Scala:

def declarations
lazy val declarations [F:160]
call-by-name parameters (=>T)

def declarations [E:12]

A definition such as

def x = exp

does not evaluate exp immediately. The expression exp will be re-evaluated, whenever x is used, or not evaluated at all if x is never used. So this definition behaves very much like a call-by-name parameter. Example:

scala> def f() = {
            def x = { println("hello") ; 1 }
            x + x + x
       }

scala> f()
hello
hello
hello
res5: Int = 3

lazy val declarations [E:109]

A definition such as lazy val x = exp does not evaluate exp immediately. The expression exp will be evaluated only once, the first time x is used, and then the result is stored in a cache for later use. So this definition behaves very much like a call-by-need parameter. Example:

scala> def f() = {
            lazy val x = { println("hello") ; 1 }
            println("good day")
            x + x + x
       }
f: ()Int

scala> f()
good day
hello
res6: Int = 3

call-by-name parameters [E:14]

Scala support regular call-by-name parameters, using parameter declarations of the form =>T. A call-by-name parameters is re-evaluated whenever the parameter is used, or not evaluated at all if he parameter is never used. Example:

scala> def cand(a: Boolean, b: =>Boolean) = if(a) b else false
cand: (Boolean,=> Boolean)Boolean

scala> cand(true, { println("hello") ; true })
hello
res4: Boolean = true

scala> cand(false, { println("hello") ; true })
res5: Boolean = false

Another example:

def While(p: =>Boolean, s: =>Unit) {
    if(p) { s ; While(p, s) }
}

Exercise: In this example, why do you need to pass the second parameter by-name?

Exercise: How do you simulate a call-by-need parameter, using the available non-strict mechanisms.

Reimplementing non-strict lists in Scala using call-by-need

Reimplementing non-strict lists using call-by-need will dramatically improve their efficiency in some cases.

The type of the ZLists do not change, but we will use the following auxiliary function that builds delayed lists that are evaluated using call-by-need instead of call-by-name:

def lz[T](l: =>ZList[T]) = { lazy val v = l ; (u:Unit)=>v }

The following method will as comes in handy for making ZNodes:

def mZNode[T](h: T, t: =>ZList[T]) = ZNode(h, lz(t))

Examples

Using the slightly changed representation, here is how we reimplement our operations and constants:

val z123 = mZNode(1, mZNode(2, mZNode(3, ZNil)))

def zadd(l: ZList[Int], n: Int): ZList[Int] =
{
    l match {
        case ZNil => ZNil
        case ZNode(x,xs) => mZNode(x+n, zadd(xs(), n))
    }
}

val zints: ZList[Int] = mZNode(1, zadd(zints,1))

Improved efficiency

The call-by-need implementation dramatically increases the efficiency in the following circumstances:

when the same delayed list appears multiple times in the same expression (there is no point in keeping re-evaluating it again and again);
in circular definitions.

For example, in the case of the circular definition of zints, the old technique gives rise of a solution with complexity O(n2) while the new technique gives rive to a solution with complexity O(n). To prove this, let us print all the add operations during the generation of values using the following auxiliary method:

def padd(a: Int, b: Int) = { print (a+b) ; print(" ") ; a + b }

The output generated by the old call-by-need technique is the following:

2 2 3 2 3 4 2 3 4 5 2 3 4 5 6 2 3 4 5 6 7 2 3 4 5 6 7 8
2 3 4 5 6 7 8 92 3 4 5 67 8 9 10 2 3 4 5 6 7 8 9 10 11
res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

The output generated by the new call-by-need technique is the following:

2 3 4 5 6 7 8 9 10 11 res3: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

For reference, here is the code corresponding to the first experiment:

def padd(a: Int, b: Int) = { print (a+b) ; print(" ") ; a + b }

def zadd(l: ZList[Int], n: Int): ZList[Int] =
{
    l match {
        case ZNil => ZNil
        case ZNode(x,xs) => ZNode(padd(x,n), u=>zadd(xs(), n))
    }
}

def zshowX[T](l: ZList[T], n: Int): List[T] =
{
    if (n == 0) Nil
    else l match {
        case ZNil => Nil
        case ZNode(x,xs) => x::zshowX(xs(), n-1)
    }
}
def zshow[T](l: ZList[T]) = zshowX(l, 10)

val zints: ZList[Int] = ZNode(1, u=>zadd(zints,1))

zshow(zints)

Now, the code corresponding to the second experiment:

def padd(a: Int, b: Int) = { print (a+b) ; print(" ") ; a + b }

def zadd(l: ZList[Int], n: Int): ZList[Int] =
{
    l match {
        case ZNil => ZNil
        case ZNode(x,xs) => mZNode(padd(x,n), zadd(xs(), n))
    }
}

def zshowX[T](l: ZList[T], n: Int): List[T] =
{
    if (n == 0) Nil
    else l match {
        case ZNil => Nil
        case ZNode(x,xs) => x::zshowX(xs(), n-1)
    }
}
def zshow[T](l: ZList[T]) = zshowX(l, 10)

val zints: ZList[Int] = mZNode(1, zadd(zints,1))

zshow(zints)

A sophisticated class for call-by-need lists in Scala

The following example shows how call-by-need lists can be nicely implemented in a modular way, using classes and singletons. This will be our final implementation of non-strict list in Scala.

Notice all the sophistication of the Scala language allows.
Notice the apply methods, that allow objects to be applied as if they are functions.
Notice that the ZLists are functional lists, that is, they are made of immutable objects. Indeed, there are no var declarations in the implementation.

// 1 - All the ZLists should be built using the object ZList applied as if
//     it was a function. This ensures the call-by-need discipline in the lists.
//     Please, never use the constructor ZNode(.,.).
//     Examples of creation of ZLists:
//         val ints6: ZList[Int] = ZList(1, 2, 3, 4, 5, 6)
//         val ints: ZList[Int] = ZList(1, ints.map(x=>x+1))
//
// 2 - Accessing the lists using the attributes head and tail is more
//     convenient than using pattern-matching because the attribute tail
//     comes already applied to (). Se no "case classes" are defined here
//     and pattern matching is not even supported in this implementation.
//
// 3 - This code does not work inside the scala interpreter because it
//     contains forward references to classes. It must be compiled using
//     the command scalac ZList.scala and run with scala Test.

object ZList {
    private def build[T](l: List[T]): ZList[T] = {
        if( l.isEmpty ) ZNil
        else ZList(l.head, build(l.tail))
    }
    def apply[T](xs: T*) = {    // variable-length list of parameters 
        build(xs.toList)
    } 
    def apply[T](hd: T, tl: =>ZList[T]) = {
        lazy val v = tl             // this is a call-by-need "cache"
        new ZNode(hd, (u:Unit)=>v)  // ZNode is used only here
    }
}

abstract class ZList[+T] {
    def isEmpty: Boolean
    def head: T
    def tail: ZList[T]
    def length: Int = {
        if (isEmpty) 0
        else 1 + tail.length
    }
    def map[U](f: T=>U): ZList[U] = {
        if (isEmpty) ZNil
        else ZList(f(head), tail.map(f))
    }
    def show(n: Int): List[T] = {
        if (n == 0 || isEmpty) Nil
        else head::(tail.show(n-1))
    }
    def show10: List[T] = show(10)
}

object ZNil extends ZList[Nothing] {
    def isEmpty: Boolean = true
    def head: Nothing = sys.error("head: head of empty list")
    def tail: ZList[Nothing] = sys.error("tail: tail of empty list")
}

class ZNode[T](hd: T, tl: Unit=>ZList[T]) extends ZList[T] {
    def head: T = hd
    def tail: ZList[T] = tl()
    def isEmpty: Boolean = false
}

object Test extends App {
    val ints: ZList[Int] = ZList(1, ints.map(x=>x+1))
    println(ints.show10)
}

This implementation is inspired by the implementation of lists in Scala: List.scala.

#15