Frequently asked questions (OOP2015)

From Spivey's Corner
Jump to: navigation, search

Arising from lectures

The following line introduces the definition of Observable in the AutoSnail program. What does it do?

trait Observable[T <: Observable[T]] { this: T =>

In AutoSnail, the class PathFinder extends Observable, and the class AppFrame extends Observer, having a method

def refresh(pathfinder: PathFinder).

Calling notifyObservers() from a PathFinder object should call that method, passing the PathFinder object itself as a parameter. Note the type that's given to the argument: we know when refresh is called that the subject is a PathFinder, and we can access its methods from within refresh without any failure-prone type conversions. In order to get all this to fit together, we need that funny heading for Observable, and we also need to introduce PathFinder with a line like

class PathFinder extends Observable[PathFinder] {

The features being used here are type bounds (P in S, p. 402) and self types (p. 537). It's nice that Scala can allow this pattern to be expressed in a type-safe way, but not so important to understand every detail of the mechanism by which it does so.

Edit: actually, the heading of Observable can be simplified to

trait Observable[T] { this: T =>

because the upper bound T <: Observable[T] is implied by that.

Handout 4 sometimes use the name elems for an array in the concrete state, and sometimes uses the name members, which surely describes the abstract state. Why is this?'

That's an unfortunate mistake, no doubt caused by my editing the materials together from too many sources using too little care. I've uploaded a corrected version of the handout.

The materials for lab1 contain the following code. What does it do?

/** Insert the contents of a file. */
def loadFile(in: java.io.Reader) {
    var nread = 0
    gap = 0; len = 0
    makeRoom(4096)
    while ({ nread = in.read(buffer, gap, max-len); nread >= 0 }) {
        gap += nread; len += nread
        makeRoom(4096)
    }
}

We're using the Java I/O library here, because Scala doesn't really have one yet. The call to in.read reads some of an input file into the array buffer, and returns the number of characters that were read, or returns a negative number if the file is finished. Because in unix the input file might be a pipe or the keyboard, we can't tell in advance how big the file might be, and we have to read it piece by piece, in a way that means our program could start to process the first part of the input before later parts have been created. For reasonable efficiency, the code here ensures that there's always space to read at least 4096 characters from the file at a time, and probably more.

The expression { nread = in.read(...); nread >= 0} is evaluated by first executing the in.read call and putting the result in nread, then testing whether nread >= 0. I'd agree that this is not very clear at first sight, but it's an idiom that quickly becomes familiar. So on each iteration, the code tries to read from the stream. If the result is negative, the loop terminates; if it is non-negative, then the gap and len are adjusted and (after making more room in the buffer) the loop iterates again.

This is a classic place where an 'n+1/2' loop is needed, because some work is necessary to determine whether the file has any more data, and that work must be done before testing whether the loop should terminate. If Scala had a break statement, I would have written the method like this:

def loadFile(in: java.io.Reader) { // NOT VALID SCALA
    gap = 0; len = 0
    while (true) {
        makeRoom(4096)
        val nread = in.read(buffer, gap, max-len)
        if (nread < 0) break
        gap += nread; len += nread
    }
}

But Scala does not have such a construct, and The Book tries to convince us (Section 7.6) that we won't miss it, though we may suspect that the argument given is disingenuous, and that it's more nearly true that the Scala people didn't want the trouble of implementing break. We could rewrite the method using return instead of break, because as it happens the loop is the last thing in the method body.

An alternative would be to use a do ... while loop like this:

def loadFile(in: java.io.Reader) {
    var nread = 0
    gap = 0; len = 0
    do {
        makeRoom(4096)
        nread = in.read(buffer, gap, max-len)
        if (nread >= 0) { gap += nread; len += nread }
    } while (nread >= 0)
}

and code like this appears in the program Edit0.scala. But I don't like to repeat the condition nread >= 0. Equally, I don't like the repeated code in this version:

def loadFile(in: java.io.Reader) {
    var nread = 0
    gap = 0; len = 0
    makeRoom(4096)
    nread = in.read(buffer, gap, max-len)
    while (nread >= 0) do {
        gap += nread; len += nread
        makeRoom(4096)
        nread = in.read(buffer, gap, max-len)
    }
}

(although, admittedly, I couldn't quite bring myself to embed the makeRoom(4096) in the while condition in my original code, but allowed it to be duplicated).

I'm also not about to introduce a Boolean flag into the program like this:

def loadFile(in: java.io.Reader) {
    var more = true
    gap = 0; len = 0
    while (more) {
        makeRoom(4096)
        val nread = in.read(buffer, gap, max-len)
        if (nread < 0)
            more = false
        else {
            gap += nread; len += nread
        }
    }
}

Initially, this seems to do the job without repetition of code or tests, but for my money it's too difficult to explain in static terms what is the significance of the flag more – that is to say, what the invariant and bound function of the loop would be.

We could also solve the problem with a tail-recursive helper function:

def loadFile(in: java.io.Reader) {
    def loop() {
        val nread = in.read(buffer, gap, max-len)
        if (nread >= 0) {
            gap += nread; len += nread
            loop()
        }
    }
    gap = 0; len = 0; loop()
}

But now this is getting silly!

Knuth's classic paper Structured programming with GOTO statements is well worth studying for this and similar problems, if only to see that they were already with us in 1974.

You briefly mentioned a more 'functional-style' program for the editing problem. Can we see the code?

It's included as the file Edit1.scala in the lab materials. Here it is:

object Edit1 {
    def main(args: Array[String]) {
        val buf = new ArrayBuffer[Char]
        scala.io.Source.stdin.copyToBuffer(buf)

        val buf2 = buf.flatMap(ch =>
            ch match {
                case 'a' => Array('a', 'b')
                case _ => Array(ch)
            })
        print(buf2.mkString)
    }
}

Apart from the use of shorter forms for the reading and writing, this program differs from the others by having a kind of list comprehension at its heart: in Haskell terms, it is equivalent to

buf2 = concat [ f ch | ch <- buf ]

where f 'a' = ['a', 'b'] and f ch = [ch] otherwise. Because of the way collections work in Scala, both buf and buf2 are represented as instances of ArrayBuffer, each a wrapper around an array that allows the array to grow as needed.

The program takes a time that is linear in the size of the input, but the constant factor will be larger than our more intricately designed programs. Specifically, the program allocates two ArrayBuffer objects with as many elements as there are characters in the text; one is created explicitly by new ArrayBuffer[Char], and the other implicitly as the result of the flatMap. The nature of the JVM's machine model means that the elements of these ArrayBuffer objects are boxed characters, consuming a dozen or more bytes per character. At the end, the expression buf2.mkString additionally allocates a string to contain the entire output. As well as the time needed to initialise all this storage, there is the additional overhead of calling the anonymous function and creating and garbage collecting a little array for each character. A program like this is fine for a quick-and-dirty job, but for production use we will want to have better control over the costs incurred.

Why make the charAt(i) operation on texts raise an exception if the index i is out of range? Why not have it return Option[Char] instead?

We could perfectly well specify and implement such an operation. Its precondition would be trivial, because it would be guaranteed always to deliver a result. The implementation could be like this (untested):

def optCharAt(i: Int): Option[Char] = {
    if (0 <= i < len) {
        if (i < gap)
            Some(buf(i))
        else
            Some(buf(MAX-len+i))
    } else {
        None
    }
}

But now think what the caller would look like! Instead of

if (t.charAt(i) == 'a') ...

we would be writing

t.optCharAt(i) match {
    case Some ch => if (ch == 'a') ...
    case None => ???
}

and it's not clear to me what you want to write in place of the ???, particularly since we're in a situation where we ought to be sure that the value of i is within the required bounds. Raising an exception rather than returning an Option value means that the caller doesn't have to deal with such errors, and they can propagate the outermost level, where we can adopt some strategy to mitigate the effect of unplanned errors.

You could equally well ask why it is that array indexing raises an out-of-bounds exception rather than returning Option[T]; the fact is, we need to be able to deal with partially-defined operations in our programs, and it's necessary to have a strategy for that. Even in functional programming, we have operations like head on a list that are undefined if the list is empty.

Scala vs. Java

Why Scala and not Java?

I've given a very similar course before using Java as the programming language, and deploying the argument that nobody's career prospects are harmed by a little knowledge of that language. Two things convinced me that I should try using Scala instead this time: that some things that we want to do involve so much writing in Java that it's offputting, and that current undergraduates have already used Scala and will use it again. It's a not unwelcome bonus that Scala programs are generally terser and therefore more pleasant to write on the board and discuss.

XKCD #1597

Why Java? Why not C++?

I think Ken Thompson and others have answered that one better than I can.

Why Mercurial? Why not Git?

For our purposes, Mercurial and Git are pretty much equivalent. I prefer Mercurial partly because the commands needed in day-to-day work are a bit simpler, partly because the community surrounding Mercurial is less ... dogmatic, but mostly because of the existence of TortoiseHG. I can do version control entirely from the command line if I have to, but it requires mental effort that I'd rather spend on other things. Having a THG window open gives a useful real-time picture of what's going on.

What features of Scala will we be using?

It's easier to give a list of features we won't be using, so that you can skip the irrelevant parts of the book. We will be sticking more-or-less to a Java-like subset of Scala, and avoiding a number of more advanced features, listed on another page. We will, however, be making crucial use of the freedom to methods as objects, which Scala has always had, and Java has added in version 8.

Scala help

Is there any good tutorial material for Scala Swing online?

I found this paper (local copy) very helpful. Also, for general Scala help as well as Swing, there's this site: http://scalatutorial.de, though it's in German. Since Scala Swing is just a thin wrapper around the Java libraries, for the detailed behaviour of components you are pretty much forced to go to the Java documentation – poor though it sometimes is.

What are some traps for young players in Scala?

I answer as a beginner myself. First, the syntax for declaring a method that doesn't return a result is like this:

def hello(String name) {
    println("Hello " + name)
}

with no equals sign between the ) and the {. The syntax for declaring a method that does return a result is like this:

def more(n: Int): Int = {
  val n1: Int = n + 1
  n1 * n1
}

In simple cases like this, you can leave out the result type and have it inferred by the compiler. But don't leave out the equals sign, or the compiler gets confused. Often it will give a helpful hint as part of the resulting error message, but not always.

(To be continued)

What are some useful Stack Overflow answers about Scala?

Here are some I have found helpful:

I tried adding the transpose command to the editor keymap by adding the following line of code, but got a wierd error message. What's happening?

The code:

Display.ctrl('T') -> _.transposeCommand,

The error message:

Editor.scala:368: error: missing parameter type for expanded function
((x$31) => Display.ctrl('T').$minus$greater(x$31.transposeCommand))

The problem here is that the usual (slightly fragile) mechanism by which Scala parses and type-checks expressions like this has broken down. The short answer: you can fix it by enclosing part of the expression in parentheses like this:

Display.ctrl('T') -> (_.transposeCommand),

The long answer: Scala uses the added parentheses to limit the scope of the placeholder _ in the expression _.transposeCommand, so that the line is shorthand for

Display.ctrl('T') -> (x => x.transposeCommand),

Without the parentheses, the line is taken as shorthand for

x => (Display.ctrl('T') -> x.transposeCommand),

which is not what we wanted. Now, when it comes to type-checking, the Scala compiler uses context ("The dove from above") to see that the type it wants for the line is Tuple2[Int, Editor => Change]. By a convoluted process involving implicits and the class ArrowAssoc, the compiler works out that the type it wants in the correct line for the expression (x => x.transposeCommand) is Editor => Change, so that the formal parameter x must have type Editor. Everything is sweet.

In the incorrect line, however, this process fails, and the compiler is left not even knowing what type it wants to give the formal parameter x, let alone that the expression would not subsequently type-check. Hence the error message.

Is Scala too complicated?

Sometimes it seems that way:

Assessment

How will the course be assessed?

  • For undergraduates, there will be an assessed practical exercise over the Christmas vacation, and also a conventional sit-down exam. The practical exercise will build on the lab work you have done during term, and will be issued on Friday of eighth week. The exercise will require you to design and implement a programming task and write a report on the design decisions you made. You will have until the start of Hilary Term to complete the exercise and submit a listing and report. The written paper will be set at the same time as the other Part A papers in June.
  • M.Sc. students will complete the same practical exercise as undergraduates, and will be required to submit the practical report at the beginning of Hilary Term, together with their other assignments. They will also have a sit-down exam at the beginning of Hilary Term.

For both undergraduates and M.Sc. students, the assessed practical will count for 35% of the marks, and the written exam for 65% of the marks.

If the lab work is part of the assessment, will help from demonstrators still be available?

During term, demonstrator help will be available in the lab exactly as usual, and the demonstrators will provide help and advice in competing all parts of the lab work. They will not know which parts of the lab work are more or less relevant to the Christmas practical exercise. Once the exercise is issued, your work on it must be entirely independent, and no further demonstrator help will be provided, neither with the relevant parts of the lab work from term, nor with the new elements introduced as part of the assessment.

Why won't the demonstrator sign off my practicals?

We're not doing signing-off for this course. You're welcome to show the demonstrator your progress, and he or she will record your attendance at the lab sessions, purely so that tutors can know through the usual channels if you haven't appeared for at least some of the sessions. But the practical work will be assessed by means of the report you submit after Christmas, and there's no need for you to produce reports or for us to assign marks during the term. That's also the reason why the lab exercises don't have identified 'optional' parts that you need to do for an S+. Because we're not awarding S or S+ marks, there's no need for that.

Is the material on GUI programming in Swing examinable?

What is examinable is what is on the syllabus for the course. It would be quite wrong of me at this stage to give any more information than that.

Personal tools

Variants
Actions
Navigation
Tools