FAQ archive (Imperative Programming)

General

Does the functional program for QuickSort really take O(N²) time in the best case?

Here's the program:

qsort [] = []
qsort (x:xs) = 
  qsort (filter (< x) xs)
  ++ [x] ++
  qsort (filter (>= x) xs)

The worry is that the ++ operations will take so much time as to spoil the order of growth. Happily, this isn't so; even though they take a time linear in N, this is no more than proportional to the time taken to evaluate the two calls to filter, so does not change the order of growth. In the best case (with a perfectly even split every time) or on average (where bad splits are rare), the program takes O(N log N) time.

Oberon

Why does this code not compile? The compiler complains that xs and ys do not have the same type.

MODULE Bad;
TYPE Node = RECORD data: INTEGER; next: POINTER TO Node END;

VAR xs: POINTER TO Node;

PROCEDURE Pop(VAR ys: POINTER TO Node); BEGIN ... END Pop;

BEGIN
  Pop(xs)
END Bad.

The problem here is that (according to the type rules set out in Appendix A of the O2 report) the types of xs and ys are not declared to be exactly the same. What you need is this:

MODULE Good;

TYPE NodePtr = POINTER TO Node;
  Node = RECORD data: INTEGER; next: NodePtr END;

VAR xs: NodePtr;

PROCEDURE Pop(VAR ys: NodePtr); BEGIN ... END Pop;

BEGIN
  Pop(xs)
END Good.

Technically, Oberon has what language theorists call 'name equivalence' and not 'structural equivalence' of types. This may seem inconvenient, but greatly simplifies the language rules in other places. The consequence is that we need to introduce one, named type for all the pointers in your program, or they will not be treated as having the same type.

Can a procedure ever refer to a global variable?

Yes it can: the copy rule I gave in the lecture provides for renaming parameters and local variables if their names clash with other variables in the program, but that cannot affect a global variable whose name appears in the body of a procedure where it is not a parameter or local. So in Oberon (just as in most other languages), it is OK to refer to global variables from procedures.

In fact, with our first example procedure that did not have parameters, that was the only way of communicating inputs and outputs of the procedure. Generally speaking, it's better to communicate by using parameters and results, unless the procedure is one of a family of procedures (perhaps encapsulated in a module) that provide the interface to a data structure.

The Oxford compiler

(i) Why is the -rsb switch not documented in the obc man page? (ii) Is it acceptable to write code in the practical sessions that only compiles with -rsb? (iii) Is the -rsb switch really named after Richard Bird?

(i) It was a just little hack that I put in to stop one of my friends and esteemed colleagues from complaining about trivial matters of surface syntax. (ii) Yes, if you want the hassle of editing all the supplied code to match. And as an undocumented hack, it may not actually work: for that, you must pay extra. (iii) See (i).

I've written an implementation of the edit distance algorithm from the Algorithms course, but I get this error message:

Runtime error: stack overflow in module EditDistance
In procedure EditDistance.EditDist
  called from EditDistance.%main
  called from MAIN

What could be happening?

Your program contained these lines:

CONST MaxLen = 1024;

PROCEDURE EditDist(A, B: String; a, b: INTEGER): INTEGER;
  VAR ed: ARRAY MaxLen OF ARRAY MaxLen OF INTEGER;

Because your matrix ed is declared as a local variable of a procedure, it lives on the stack. It consists of 1024 * 1024 integers, each 4 bytes, so that comes to 4MB, and by default an Oberon program runs with 1MB of stack space, and the stack doesn't grow if it becomes full. (Actually, there's a good reason for not letting the stack grow: it prevents a program in an endless recursion from bringing the computer to its knees.)

Solutions: (i) reduce the value of MaxLen for your initial trials. (ii) make ed a global variable in your program, so it lives in global space and not on the stack. (iii) – the best – declare ed with

VAR ed: POINTER TO ARRAY OF ARRAY OF INTEGER.

This makes ed a pointer to a variable-size matrix, and you can then allocate space dynamically with NEW(ed, a, b) where a and b are the actual lengths of your two strings. That way, the program will not use more space than it needs in a particular run.

Trivia

Is it possible to implement doubly-linked lists in Haskell?

Of course. But since every element of a doubly linked list gives access to every other one, it's not possible to build a doubly-linked list element by element, only to construct a whole one at once.

A Lyst has an optional data item (absent in the header node) and two pointers.

data Lyst a = Kons (Lyst a) (Maybe a) (Lyst a) deriving Show

The function lystify converts a conventional list into a Lyst. Everything is circular here: definitions as well as data structures

lystify :: [a] -> Lyst a
lystify xs = header
  where 
    header = Kons back Nothing front
    (front, back) = convert header header xs

Now convert left right xs makes the list xs into a Lyst, using left and right as the pointers at the two ends. It returns a pair of pointers (front, back) to the first and last nodes in the result.

convert :: Lyst a -> Lyst a -> [a] -> (Lyst a, Lyst a)
convert left right [] = (right, left)
convert left right (x:xs) = (this, last)
  where 
    this = Kons left (Just x) next
    (next, last) = convert this right xs

Here's a function that runs round the ring in a forwards direction and reconstitutes the original list.

forwards :: Lyst a -> [a]
forwards (Kons back Nothing front) = walk front
  where
    walk (Kons _ Nothing _) = []
    walk (Kons _ (Just x) xs) = x : walk xs

And here for symmetry is one that runs around backwards, yielding the reverse of the original list.

backwards :: Lyst a -> [a]
backwards (Kons back Nothing front) = walk back
  where
    walk (Kons _ Nothing _) = []
    walk (Kons xs (Just x) _) = x : walk xs

Try forwards (lystify [1..10]) to get back [1..10], or backwards (lystify [1..10]) to get the same list in reverse. But don't type just lystify [1..10] unless you want to see an infinite ... there, I did warn you.