FAQ archive (Programming Languages)

From Spivey's Corner
Jump to: navigation, search


Q: With regard to the language M1 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 without the need to rely on such behaviour of primitives like =. --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

Compiling the interpreters

Q: Does anyone have any advice on how to get Fun working on Windows?

A: I added some notes to the page about Installing GHC. The key thing is to use the --make option to GHC, which asks it to find and compile all the modules that make up the program, using the import declarations that appear at the top of each module. So if the main program is in Fun.hs (as it is for the first of our interpreters), then

ghc --make -main-is Fun Fun.hs -o fun

compiles the code from Fun.hs and all the other modules, such as Environment.hs and FunParser.hs and Parsing.hs, that are needed to support it --Mike

Q: New versions of GHC complain when compiling Fun.

stav149:Fun alex$ ghc --make Fun -o prog
Warning: output was redirected with -o, but no output will be generated
because there is no Main module.

Apparently, the new versions require the main module to be called (unsurprisingly) Main. – Alex

A: This has always been the case with GHC; what's changed is that I've given each module an explicit name in this year's revisions, so now you must say (note the uneven pattern of hyphens),

$ ghc --make -main-is Fun Fun.hs -o prog

(I don't think it would kill the GHC people to assume that the one module named on the command line is the main program, instead of just saying "shan't!") I'll try to hunt down places where I've failed to change the instructions. – Mike

Q: What other reasons are there why Fun will not build with GHC 7.2? – Mike

A: I mistakenly included in the Parsing module some references to the old layout of the Haskell standard library, and this old layout has disappeared in GHC 7.2. In particular, the modules System and IO have become System.Environment and System.IO, just to keep us on our toes. (In C, by contrast, you can say #include <stdio.h> and it has always just worked, one of many reasons for liking C.)

I hope I've made the appropriate changes now, so if you download the code again, everything should work. – Mike


Q: "This latter kind of recursion is worrying because the recursive evaluation is applied to an expression that may be larger than the application that leads to it." Isn't recursing on larger expressions necessary for Turing-completeness?

A: Yes it is. But it also leads inevitably to the possibility of nontermination.

Q: In Problem Sheet 1, you assert: "Sometimes it is convenient to allow several definitions at once, and sometimes it is essential, where it is necessary to define recursively several functions that may call each other." Furthermore, in his paper, Landin models mutually recursive functions by allowing λ-bound variables to be tuples or lists. How would this be modelled in the pure, one-variable-per-λ, untyped λ-calculus? – Alex

A: You can get tuples by using Church encoding:

pair x y f = f x y

fst p = p (\ x y -> x)

snd p = p (\ x y -> y)

And you can get a fixpoint combinator Y from your favorite supplier. Then the factorial function is

Y (\ fac -> \ n -> if n = 0 then 1 else n * fac (n-1))

And (even, odd) are

Y (\ p -> let even = fst p in let odd = snd p in 
    pair (\ n -> if n = 0 then true else odd (n-1))
      (\ n -> if n = 0 then false else even (n-1)))

(where of course the let can be read as syntactic sugar). – Mike

Q: You've used CPS to make call by value explicit. Is it possible to do the same with call by name?

A: Yes. Just as in Lab 2, where we implemented call by name by giving procedure values the constructor Proc ([M Value] → M Value), we can use the same type where M α is the monad of continuations, M α = (α → Answer) → Answer. That amounts to evaluating each argument e with eval e env to get a function of type M α that is still waiting to be supplied with a continuation. That continuation comes when the parameter is used inside the procedure. But since each use of the parameter is supplied with a different continuation, we can't hope to get the fully lazy behaviour of Haskell, where each expression is evaluated at most once, with the result of the first evaluation shared among all subsequent uses.

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?

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

A2: 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?

A1: Yes, there is. Watch for clues!

A2: 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