9

I was working through the "Programming in Scala" book, and was struck by a bit of a problem in the implementation of the class Rational in Chapter 6.

This is my initial version of the Rational class (based on the book)

class Rational(numerator: Int, denominator: Int) {
  require(denominator != 0)

  private val g = gcd(numerator.abs, denominator.abs)

  val numer = numerator / g
  val denom = denominator / g

  override def toString  = numer + "/" + denom

  private def gcd(a: Int, b: Int): Int =
    if(b == 0) a else gcd(b, a % b)

  // other methods go here, neither access g
}

The problem here is that the field g remains for the lifetime of the class, even if never again accessed. This problem can be seen by running the following mock program:

object Test extends Application {

  val a = new Rational(1, 2)
  val fields = a.getClass.getDeclaredFields

  for(field <- fields) {
    println("Field name: " + field.getName)
    field.setAccessible(true)
    println(field.get(a) + "\n")
  }  

}

Its output is going to be: 

Field: denom
2

Field: numer
1

Field: g
1

A solution I found at the Scala Wiki involves the following: 

class Rational(numerator: Int, denominator: Int) {
  require(denominator != 0)

  val (numer, denom) = { 
    val g = gcd(numerator.abs, denominator.abs)
    (numerator / g, denominator / g)
  }

  override def toString  = numer + "/" + denom

  private def gcd(a: Int, b: Int): Int =
    if(b == 0) a else gcd(b, a % b)

  // other methods go here
}

Here, the field g is only local to its block, but, running the small test application, I found another field x$1 which keeps a copy of the tuple consisting of (numer, denom)!

Field: denom
2

Field: numer
1

Field: x$1
(1,2)

Is there any way to construct a rational in Scala with the above algorithm, without causing any memory leaks?

Thanks,

Flaviu Cipcigan

Improve this question
4
  • 1
    Same question: stackoverflow.com/questions/1118669/… Commented Aug 2, 2009 at 14:19
  • Thanks, and sorry for asking the question again :). The answers in the linked post clarified my question. Commented Aug 2, 2009 at 16:03
  • Have you confirmed that denom and numer are really values? I would not at all be surprised if they were "only" accessor methods of the form def denom = x$1._2. Commented Aug 31, 2011 at 10:30
  • 2
    It is not a memory leak, it is a memory overhead. Commented Aug 31, 2011 at 16:34

7 Answers 7

Reset to default
13

A companion object can provide the flexibility you need. It can define a "static" factory methods that replace the constructor.

object Rational{

    def apply(numerator: Int, denominator: Int) = {
        def gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a % b)
        val g = gcd(numerator, denominator)
        new Rational(numerator / g, denominator / g)
    }
}

class Rational(numerator: Int, denominator: Int) {
  require(denominator != 0)

  override def toString  = numerator + "/" + denominator
  // other methods go here, neither access g
}

val r = Rational(10,200)

In the scope of the factory method g can be calculate and used to the derive the two constructor values.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thanks for the answer, I was thinking of a factory as well, but that would add a couple of complications. For example, a user could invoke the object's constructor (e.g. new Rational(10,20)) and in the process create an invalid rational. One could add an require(gcd(numerator, denominator) == 1) to the constructor or make the class constructor private and oblige the users to use the factory. I am not sure what would be best... a factory does seem a bit overkill for a Rational :)
Note that since the factory method's name is apply, it can be called like this: Rational(10, 20).
Not an overkill -- this is the correct answer. This is extremely typical for scala and is the recommended pattern - private ctor and use the companion apply. :)
13

You could do this:

object Rational {
    def gcd(a: Int, b: Int): Int =
        if(b == 0) a else gcd(b, a % b)
}

class Rational private (n: Int, d: Int, g: Int) {
    require(d != 0)

    def this(n: Int, d: Int) = this(n, d, Rational.gcd(n.abs, d.abs))

    val numer = n / g

    val denom = d / g

    override def toString = numer + "/" + denom

}
Improve this answer

Comments

6

You could do this:

val numer = numerator / gcd(numerator.abs, denominator.abs)
val denom = denominator / gcd(numerator.abs, denominator.abs)

Of course you'd have to do the calculation twice. But then optimizations are often a trade-off between memory/space and execution time.

Maybe there are other ways too, but then the program might get overly complex, and if there's one place where optimization is rarely premature, it's brain power optimization :). For instance, you could probably do this:

val numer = numerator / gcd(numerator.abs, denominator.abs)
val denom = denominator / (numerator / numer)

But it doesn't necessarily make the code more understandable.

(Note: I didn't actually try this, so use at your own risk.)

Improve this answer

1 Comment

Thanks, your second solution works (though I haven't done any rigorous testing) and does get rid of any superfluous fields with negligible overhead.
6

There's a small problem with Thomas Jung's example; it still allows you to create a Rational object with a common term in the numerator and denominator - if you create the Rational object using 'new' yourself, instead of via the companion object:

val r = new Rational(10, 200) // Oops! Creating a Rational with a common term

You can avoid this by requiring client code to always use the companion object to create a Rational object, by making the implicit constructor private:

class Rational private (numerator: Int, denominator: Int) {
    // ...
}
Improve this answer

Comments

3

... actually, I don't see how this constitutes a "memory leak".

You declare a final field within the scope of the class instance, and are then apparently surprised that it "hangs around". What behaviour did you expect?

Am I missing something here?

Improve this answer

3 Comments

The problem is that there's no clean way to define a temporary variable that's only used during the construction of the object, as you could with a Java constructor.
This is not formally a memory leak, since it is still reachable from global or local variables (which is why the GC doesn't clean it up). It is certainly a "leak" in the informal sense that it's data that live on even though you will never need it.
I think the choice of title is a bit misleading.
0

I came across this article which you might find useful: http://daily-scala.blogspot.com/2010/02/temporary-variables-during-object.html

It seems you could write this: 

class Rational(numerator: Int, denominator: Int) {
  require(denominator != 0)

  val (numer,denom) = {
      val g = gcd(numerator.abs, denominator.abs)
      (numerator/g, denominator/g)
  }

  override def toString  = numer + "/" + denom

  private def gcd(a: Int, b: Int): Int =
    if(b == 0) a else gcd(b, a % b)

  // other methods go here, neither access g
}
Improve this answer

Comments

0

Could be like:

def g = gcd(numerator.abs, denominator.abs)

instead of val

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.