FAQ archive (Programming Languages)

General

Q: With regard to the language M₁ from problem sheet 3 where memory changes are undone after an exception is thrown; is there a name for this feature and do any "real" languages or runtimes provide it?

A: As a programming language feature: there was an idea for 'recovery blocks' for operating systems programming in the 70's, but it never really took off; but then, the idea of writing operating systems in any high-level language other than C never really took off either. In the database and transaction processing world, it's common to implement changes to databases as transactions that either complete successfully, or abort and leave the database unchanged. And the PostScript language that's used to describe pages by many printers has the notion that all changes to the memory state made by a print job will be erased when the job is over, whether the job is successful or not: that way, they cannot affect the printing of the next job.

Finally, there's the way Prolog is usually implemented: the substitution that gives the information that has been deduced so far along the current branch in the tree is represented by assigning to a memory cells associated with each unknown, and keeping track of which assignments must be undone when it becomes necessary to backtrack. That's explained in some detail in my book about Logic Programming and Prolog.

Q: Is there a good reason why you defined the equality test x = y between references x and y so that it always gives the result false?

A: No, not really. You could indeed extend the instance declaration for Eq Value so that references are compared by comparing the underlying addresses; perhaps you would need to make an instance Eq Location to make that work. Doing so would make it trivial to solve the exercise that asks you to show that different invocations of new() yield different locations, and I wanted it to expose the point that imperative operations like assignment allow us to make more discriminating tests of program behaviour. --Mike

Q: In problem 2.5, it says, "In the basic language Fun, we cannot tell whether the actual parameters of a function are evaluated from left to right or from right to left, nor whether the function itself is evaluated (to obtain the function object that is applied to the arguments) before or after the actual parameters." But the following program fails when evaluating 1+nil and not 1*nil. Doesn't that show that arguments are evaluated from left to right?

>>> val f(x,y) = x+y;;

--- f = <function>

>>> f(1+nil, 1*nil);;

Error: bad arguments to primitive +: 1, []

A: What we're really seeing here is a result of the way the list of arguments to the + primitive (which is used in the body of f) is matched by the pattern in the interpreter equation

prim "+" [IntVal a, IntVal b] = IntVal (a+b)

The sub-pattern IntVal a gets matched first, and that causes the argument 1+nil to be evaluated, giving the error. You can see this if you replace the definition of f with

>>> val f(x,y) = y+x;;

-- the result is a message about * instead. It's a contingent property of our Haskell implementation that patterns are matched in this way, and a different Haskell implementation might give results that were the other way round. In a way we are getting information about the order of evaluation for arguments to the + primitive, but nothing about the arguments of f. In fact, if you write

>>> val f(x,y) = 99;;

instead, you get no error message, and this shows again that the lazy behaviour of Haskell is leaking through. --Mike

Q: In lecture 11, you defined Parser α with

type Parser α = [Token] → [(α, [Token])]

but in the module called Parsing, I found

newtype Parser τ α = Parser ([(τ, LineNumber)] → ParseResult τ α)

data ParseResult τ α = MkResult (Maybe (α, [(τ, LineNumber)], Int)) Int

Why the difference?

A: There are a number of differences, all with a practical reason behind them:

• I use the newtype construction because I want to make parsers into a Haskell-style monad in order to use the do notation. Haskell-style monads are based on type classes, and defining a type class requires us to use the data or newtype constuctions. We've avoided that in the course by also avoiding the do notation.
• The type of parsers is generic in the type τ of tokens, but in the lecture I used a single, fixed type Token.
• Tokens are labelled with line numbers to help in generating intelligible error messages.
• Instead of returning a list of results, parsers return a Maybe result. This prevents backtracking, but provided you take care always to return the longest parse first, backtracking is rarely needed.
• The parser keeps track of the greatest number of tokens that it ever manages to read from the input. That is the purpose of the two occurrences of Int in the type ParseResult. If the parse fails, then the error must occur before the first token that can't be read by the parser, and that helps in generating error messages. (The first Int is the number of tokens consumed by a successful parse; the second Int is the maximum number read by any partial parse, successful or otherwise.)

Actually, Parser is still a monad, and supports the same operations (like failure and alternation) that we talked about in the lecture. So there is little difference as far as writing a parser using the tools is concerned, although the tools are doing more internally.

Q: A direct-style interpreter for a purely functional language written in Haskell ought to behave lazily. But in the last lecture, your program primes1.fun failed to produce any output. Why is that?

A: Actually, it would have produced output if you had waited long enough, but the output was buffered, and appeared only when the buffer was full. I've modified the dialog function so that the output from a program is no longer buffered, and the list of primes now appears gradually as one might expect. – Mike

Annoying puzzles

Q: Is it really possible to define a recursive function (like factorial) in pure Fun without using the rec keyword? If so, how?

A₁: Yes, it is. A clue: try applying a function to itself, as in f(f) --Mike

A₂: let val fac(n, f) = if n = 0 then 1 else n * f(n-1, f) in fac(6, fac)

Q: Is there really a one-line Haskell expression with a type that goes on for several pages?

A₁: Yes, there is. Watch for clues!

A₂: let f x = (x, x) in let g = f . f . f . f in g . g . g . g

Q: Can the pipeline-based primes program be written as an unix shell script?

A: Don't let this run for too long: your computer will run out of steam long before the output reaches 1000000.

sieve() {
    read x; echo $x
    while true; do
	read y
	if [ `expr $y % $x` != 0 ]; then echo $y; fi
    done | sieve
}

seq 2 1000000 | sieve