The Artima Developer Community
Sponsored Link

Weblogs Forum
Scala: An Effective Blend of Object Oriented and Functional Programming

2 replies on 1 page. Most recent reply: Nov 29, 2005 2:03 PM by Jörg Gottschling

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 2 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Scala: An Effective Blend of Object Oriented and Functional Programming (View in Weblogs)
Posted: Jun 20, 2005 8:38 PM
Reply to this message Reply
Summary
Until relatively recently programming languages have fit neatly into either "imperative" or "functional" categories. Scala represents a new breed of language which obliterates these arbitrary restrictions.
Advertisement

I have been studying the Scala programming language by Martin Odersky and his lab in great depth recently and I really like what I see. Scala is a very effective blend of functional, imperative and object oriented techniques and has a practical minded design despite supporting very advanced techniques.

I was perusing the Scala standard library and came upon the library's implementation of List. The implementation was quite idiomatic of the functional style with the member functions expressed mostly in terms of various combinations of Car (head), Cdr (tail), and Cons (::). The implementation was mediochre because many of the functions were not tail-recursive. This meant that the code was very compact and readable ( which I like ), but caused stack overflows on lists of over 1000 elements (which was unacceptable) as well as being inefficient ( which I can live with ).

I decided to try my hand at rewriting the class to see if I could do any better, and I came upon the observation that a list implementation can be entirely expressed in terms of an interface containing simply one function: foreach. I decided to build a set of classes all deriving from a single Sequence trait ( a kind of abstract class) as follows:

  trait Sequence[+a]  {
    def foreach(f: a => unit): unit;
  }

The List trait introduces dozens of functions derived from this as follows (they are not all tested yet, sorry):

  trait List[+a] extends Sequence[a]
  {
    def defaultElement : a =
      null.asInstanceOf[a];

    def apply(n : Int) =
      { var i = 0; foldLeft[a](defaultElement)((xs, x) => { i = i + 1; if (i - 1 == n) x else xs; }); }

    def head : a =
      apply(0);

    def last: a =
      { var i = 0; foldLeft[a](head)((xs, x) => x); }

    def tail : List[a] =
      { var atHead = true; foldLeft[List[a]](Nil)((xs, x) => if (atHead) { atHead = false; Nil } else x :: xs);  }

    def isEmpty: Boolean =
      length == 0;

    def ::[b >: a](x: b): List[b] =
      new diggins.::(x, this);

    def map[b](f: a => b): List[b] =
      foldLeft[List[b]](Nil)((xs, x) => f(x) :: xs);

    def filter(p: a => Boolean): List[a] =
      foldLeft[List[a]](Nil)((xs, x) => if (p(x)) x :: xs else xs);

    def reverse: List[a] =
      foldLeft[List[a]](Nil)((xs, x) => x :: xs);

    def reverseForeach(f : a => unit) =
      reverse.foreach(f);

    def reverseMap[b](f : a => b) : List[b] =
      reverse.map(f);

    def length: Int =
      { var i = 0; var x = this; while (x != Nil) { i = i + 1; x = x.tail; }; i; }

    def count(p : a => Boolean) : Int =
      { var i = 0; foreach(x : a => if (p(x)) { i = i + 1; }); i; }

    def indices: List[Int] =
      { var i = -1; map[Int](x : a => { i = i + 1; i; }); }

    def init: List[a] =
      take(length - 1);

    def take(n: Int): List[a] =
      { var i = -1; filter(x : a => { i = i + 1; i < n; } ); }

    def drop(n: Int): List[a] =
      { var i = -1; filter(x : a => { i = i + 1; i >= n; } ); }

    def takeRight(n : Int): List[a] =
      drop(length - n);

    def dropRight(n : Int): List[a] =
      take(length - n);

    def splitAt(n: Int): Pair[List[a], List[a]] =
      Pair(take(n), drop(n));

    def takeWhile(p: a => Boolean): List[a] =
      { var ret = true; filter(x => if (p(x)) ret else { ret = false; false; }) }

    def dropWhile(p: a => Boolean): List[a] =
      { var ret = false; filter(x => if (p(x)) ret else { ret = true; true; }) }

    def span(p: a => Boolean): Pair[List[a], List[a]] =
      Pair(takeWhile(p), dropWhile(p));

    def negate_predicate[b](p: b => Boolean)(x : b) : Boolean =
      !p(x);

    def break(p: a => Boolean): Pair[List[a], List[a]] =
      span(negate_predicate[a](p));

    def remove(p : a => Boolean) : List[a] =
      filter(negate_predicate[a](p));

    def partition(p : a => Boolean) : Pair[List[a], List[a]] =
      Pair(filter(p), remove(p));

    def forAll(p : a => Boolean) : Boolean =
      { var ret = true; foreach(x => if (!p(x)) ret = false); ret; }

    def exists(p : a => Boolean) : Boolean =
      { var ret = false; foreach(x => { if (p(x)) ret = true }); ret; }

    def contains(elem: Any): boolean =
      exists(x => x == elem);

    def foldLeft[b](z: b)(f: (b, a) => b): b =
      { var ret = z; foreach(x : a => { ret = f(ret, x); }); ret; }

    def foldRight[b](z: b)(f: (a, b) => b): b =
      { var ret = z; reverseForeach(x : a => { ret = f(x, ret); }); ret; }
  }

This also is another trait, and it can not be instantiated. Two concrete classes which implement the List interface are:

  object Nil extends List[All] {
    override def isEmpty = true;
    override def foreach(f: All => unit): unit = error("head of empty list");
  }

  class ::[+a](hd: a, tl: List[a]) extends List[a] {
    override def isEmpty = false;
    override def foreach(f: a => unit): unit =
      { var x:List[a] = this; while (!x.isEmpty) { f(x.head); x = x.tail; } }
    override def head: a = hd;
    override def tail: List[a] = tl;
  }

A rather nifty feature of Scala is that identifiers can be symbols. In this case :: is a name of a class which implements the List interface. We can also use it with infix notation as follows:

  val x : List = 1 :: 2 :: 3 :: nil;

This is however only the tip of the iceberg. Scala also makes it easy to implement lazy lists ala Haskell. I was able to create a lazy list in only a few lines of code as follows:

  class LazyRange(begin_a : int, end_a : int) extends List[int]
  {
    def begin = begin_a;
    def end = end_a;

    override def foreach(f: int => unit): unit =
      { var i = begin; while (i <= end) { f(i); i = i + 1; }; };

    override def apply(n : int) = n + begin;
    override def reverse : LazyRange = new ReverseLazyRange(begin_a, end_a);
    override def length = end - begin;
    override def head = begin;
    override def last = end;
    override def tail = new LazyRange(begin_a, end_a - 1);
  }

I also created an efficient implementation of a list by using an array adapter:

class ArrayRange[a](arr_a : Array[a], begin_a : int, end_a : int) extends List[a]
{
  val arr = arr_a;
  val begin = begin_a;
  val end = end_a;

  override def isEmpty = begin == end;
  override def tail = { if (length == 1) Nil else new ArrayRange[a](arr, begin + 1, end); }
  override def length : Int = { end - begin; }
  override def apply(n : int) : a = { arr(n); }
  override def head = apply(0);
  override def last = apply(length-1);

  override def foreach(f : a => Unit) : Unit = {
    var i = 0;
    while (i < length) {
      f(apply(i));
      i = i + 1;
    }
  }

  override def map[b](f: a => b): ArrayRange[b] = {
    var ret = new Array[b](length);
    var i = 0;
    while (i < length) {
      ret(i) = f(apply(i));
      i = i + 1;
    }
    fromArray[b](ret);
  }

  override def filter(p: a => Boolean): ArrayRange[a] = {
    var i = 0;
    var j = 0;
    var ret = new Array[a](length);
    while (i < length) {
      if (p(apply(i))) {
        ret(j) = apply(i);
        j = j + 1;
      }
      i = i + 1;
    }
    fromArray[a](ret);
  }

  override def reverse : ArrayRange[a] =
    new ReverseArrayRange[a](arr, begin, end);

  def fromArray[b](x : Array[b]) : ArrayRange[b] =
    new ArrayRange[b](x, 0, x.length);
}

I think Scala is one of the strongest new languages to come out in a long time, I encourage everyone to check it out. For more of my Scala code you can see my posts to the mailing list online at http://news.gmane.org/gmane.comp.lang.scala.


Doug Landauer

Posts: 2
Nickname: scruzia
Registered: Dec, 2004

Re: Scala: An Effective Blend of Object Oriented and Functional Programming Posted: Jun 21, 2005 3:47 AM
Reply to this message Reply
I've been following Scala's development for a while, and have written a few small examples. See http://tmp.i.am/2005/06/20.html .

Jörg Gottschling

Posts: 4
Nickname: jogix
Registered: Sep, 2005

Re: Scala: An Effective Blend of Object Oriented and Functional Programming Posted: Nov 29, 2005 2:03 PM
Reply to this message Reply
Hello,

we are also very interestet in Scala and have read your article. We did not go through the whole source code, but there is one point about your trait Nil.

Why does foreach throw an Error? I would expect it does nothing, because it is a sequence/list with no elements.

-- Jogi (www.myndian.de)

Flat View: This topic has 2 replies on 1 page
Topic: Personal Knowledge Management Platform I'm Considering for Development Previous Topic   Next Topic Topic: XSLT: The Other Programming Language in your Browser


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us