Frequently asked questions
Some questions from previous years have been moved to the FAQ archive.
General
Q: Can I ask any kind of question here?
A: Yes you can. Questions might be about the way the course is organised, or about the material we cover. I'll probably remove organisational questions as the answers become clear, or as they are dealt with elsewhere --Mike
Q: Is Functional Programming really necessary as a prerequisite for this course?
A: Yes, I'm afraid so. We will be using a number of things from the start of the course that are only covered towards the end of a beginning course on Functional Programming. There's no way to avoid this.
Q: Why are monads in Haskell so hard to understand?
A: Perhaps because three things come together: (i) Monads as a way of organizing and structuring a program is a way that makes algebraic sense; (ii) Monads as an interface to parts of Haskell that are implemented in a non-pure way; (iii) The do notation, which allows monadic code to look (superficially) as if it is written imperatively. --Mike
Q: Is this really a "FP made difficult" course, or could we say it's "Haskell made difficult" instead?
A: We will use next to none of the more obscure features of Haskell, because one of our goals is to explain the meaning of different features that we can add to the object language Fun, and the more features we assume in the meta-language Haskell, the less we can claim to have given a good explanation.
So the main things that are needed are:
- Algebraic data types,
- Recursive definitions,
- Higher order functions.
And those things are present in almost every functional programming language. We'll be using higher-order functions in a particular pattern called monads, but we won't be using the monad-related features of Haskell, and monads will in any case be fully explained, with plenty of examples. --Mike
Compiling the interpreters
Q: How can I modify the Fun interpreter to print the abstract syntax of each expression?
A: Find the equation that reads
obey (Calculate exp) env =
(print_value (eval exp env), env)
and change it to
obey (Calculate exp) env =
(show exp ++ "\n" ++ print_value (eval exp env), env)
– Mike
Clarifications
Q: Is the triangle function actually secretly the bind function?
A: Yes, what I write as ▹ is the thing that's written >>= in Haskell. Except that I spell it $> in source code for reasons that will become obvious. --Mike
Q: Your definitional interpreter for FunMem uses two explicit mappings: an environment that maps identifiers to values, with one kind of value being a location; and a memory that maps locations to storable values. Isn't it possible to combine these into a single mapping?
A: In some restricted circumstances, yes it is. But doing so in a language that combines nested scopes with assignable variables requires some kind of dirty trick, as I explain elsewhere. – Mike
New questions
Q: In library the type (→) a which is a → is an instance of Functor typeclass, I suppose that → b is also a Functor. If so, how can we implement it in Haskell?
[I noticed this question long after it had been asked. I'm sorry about that, but will answer it anyway].
a → ? is a functor because if x is any type, then a → x is a type, and what's more if f :: x → y then we can define lift f : (a → x) → (a → y) by lift f h = f . h. This definition satisfies the laws lift id = id and lift (g . f) = lift g . lift f as it should.
On the other hand, ? → b is a contravariant functor. For any type x, we can form the type x → b, but if f :: x → y, what we can define is colift f :: (y → b) → (x → b), by writing colift f h = h . f. This satisfies the properties colift id = id and colift (g . f) = colift f . colift g.
Q: Are the lecture notes a draft of a new functional programming book? Will you publish it? Thanks.
Yes, all being well. Finding time to tidy up all the details is very difficult.
Q: How does the parser work? Will it match as long as possible? When I put Loop expression after While it won't work. However I put it before While and If it will work fine. I saw there is a More in Result of Parsing.hs, is that for looking ahead indefinitely, which means it is a LL(n) Parser?
Some of the details of the Parsing module are explained in Appendix B of the lecture notes: appendices. I'm not sure I understand what you're asking when you want to know if the parser will 'match as long as possible'. The parser matches inputs that conform to the grammar it's been given, and in the parser for Fun, things are arranged so that the body of an if or while must be enclosed in parentheses if it consists of more than one statement. What's not clear to me is whether you're asking about where you should insert the loop construct into your parser, or where loop constructs can appear in the input language. If you're trying to complete Lab 3, then perhaps the lab demonstrator will be able to help you.
The More k result from parsers is there so that the parser can request more input, so as to deal with the case where a complete phrase did not appear on one line of input, and the parser would like the top level to request another line and feed it to the parser. The value k is a continuation that is called when more input is available. This has nothing to do with the class of grammars that can be handled by the parser combinators, namely the set that can be recognised top down in a deterministic way. This includes the LL(1) grammars.
Q: I've installed the GHC compiler and I'm trying to compile FunLab2 from the 2nd practical, but it keeps saying "Parsing.hs:17:8: Could not find module System.Posix". How do you get around that?
A: I'm guessing that you're using a Windows machine, and you've downloaded the file labs.tar.gz or checked out the labs from the Subversion repository. Both these places contain the Unix version of Parsing.hs; what you need is the version of that file that's contained in the archive labs.zip on the laboratory exercises page.
All the other files are the same in all versions, so it's enough to add a copy of the Windows version of Parsing.hs and recompile.
Q: Why did you say that the pipeline for computing primes is not the sieve of Eratosthenes?
A: See this fascinating article: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
Q: Your language FunPipe was implemented using continuations. But a process in that language is just a kind of stream function that maps an input stream to an output stream. Couldn't you forget the continuations and implement the language using lazy lists instead?
For the purely functional variant of the language, yes – at least, provided you're prepared to ignore the unimportant detail of what value a process or pipeline yields if it terminates, and you compromise on the ability to accept input from the terminal. You can replace the monad type used in my interpreter with
type M a = [Value] -> ([Value], [Value], a)
with the idea that if (inp1, out1, x) = xm inp then inp represents the stream of values that process xm can read, inp1 is returned as the unconsumed part of the input, out is the output produced by xm, and x is the value it yields. All the operations we used in the lecture can be defined on this type, with the operation pipe xm ym connecting the output produced by xm to the input accepted by ym. The prime sieve program works nicely.
What you can do with continuations but not with streams is describe a language that combines these concurrent processes with, say, assignable variables. You can use assignment to detect the time at which various actions occur, and when implementing pipe xm ym in a monad like the one above, it is very hard to arrange that the actions of xm are interleaved with those of ym, or to incorporate memory in a way that does not destroy the laziness. With continuations, all this happens naturally: we just add a memory state as an argument of each continuation, and thread a single memory through the entire computation.
Q: How are call by reference and call by name different and what are legal parameters that could be passed to functions that are implemented in one of those ways? For example, if we have a function G(x) and x is passed by name, are we allowed to call G(y+z) for some variables y and z? This doesn't make sense when we make a call by reference?
A: Parameters passed by reference make sense in a language where references are denotable but not (necessarily) expressible, like Fungol. There we can require that actual parameters are variables (or more generally, expressions with an l-value), and call the procedure by making the formal parameters denote the same references as the actual parameters. This form of parameter passing is commonly provided in languages in the Pascal family. Your example G(x+y) would not be allowed if the parameter is passed by reference.
Parameters passed by name may be any expression, but the expression is not evaluated at the time of the call, but each time the parameter value is needed. It's common today in lazy pure functional languages, where the purity allows the optimisation to parameters passed by need, where the value is calculated the first time it is needed, then saved and reused if the parameter value is needed again. Lab 2 concerns a language that is not purely functional, but has explicit dereferencing, where references are expressible. In that language, we could write the call G(!y+!z) to ask that the contents of y and z are evaluated afresh each time the formal parameter x occurs in the body of G.
In the lab, the expression
sum(i, 0, 10, !i * !i)
is used; with a suitable definition of sum, this varies i from 0 to 9, summing the values taken by the expression !i * !i as it goes. This trick was known as Jensen's device in Algol 60. Because in our language references are values, the first occurrence of i is passing a reference to i, while the two occurrences of !i denote the contents of that reference at the time the parameter is used in the function body. These parameters are, of course, evaluated in the environment of the function call, not the environment where the formal parameter occurs in the function body.
[FORTRAN provided (only) a variant of parameters passed by reference where the actual parameter could be an arbitrary expression; if it had no l-value, then a location would be allocated to hold the value, and the formal parameter would denote that location in the body of the procedure. Algol 60 had both parameters passed by value and a variant of parameters passed by name such that if the actual parameter had an l-value, then the formal parameter would denote the same location (recalculated on each use); that gave the benefits of parameters passed by reference.
It's not clear to me that the designers of Algol 60 had a complete appreciation of what their parameter mechanism implied when they defined it.]
Q: Why did we require that Rec definitions define only functions in the original Fun and FunMem?
Recursive definitions of anything but functions commit us to some kind of laziness. For Fun, that's not necessarily a problem, but for FunMem it is: we don't want to deal with expressions like
let val g = new() in let rec x = g := x; 3 in !g
that ought to have the value 3, but won't do so in any sensible implementation. The same holds when we make a monadic interpreter, unless we assume that the monad itself supports a suitable fixpoint operator fix :: (α → M α) → M α.
Q: The join operation in Exercise 2.10 can make some effects of the Monad disappear, for example in the list monad, join [[1,2,3],[4,5]] = [1,2,3,4,5], which means we lose the length of the sublists. And in the Maybe monad, join Nothing = join (Just Nothing) = Nothing, which also loses the infomation about how the computation fails.
(1) Are there some situations in which the monad will not lose any information, such as the identity Monad? (2) Is the State monad the same as the Memory monad? What is the join operation for it?
If join :: M (M α) → M α is an injection, then it seems likely that M α and α are in one-one correspondence, so we are in the identity monad or something very much like it. Yes, the monads of Memory and State are very similar, except that Haskell's State monad is parametrised by the type of states, and we take the state space always to be memories Mem. The join operation is
join :: (Mem -> (Mem -> ('a, Mem), Mem)) -> Mem -> ('a, Mem)
join xmm mem = let (xm, mem') = xmm mem in xm mem'
I don't really know how to describe that in helpful words.
Note that 'losing information' here means ignoring the way an outcome was produced, and concentrating on the outcome itself, viewing programs extensionally in a sense that allows us to assert meaningful identities between programs.
Q: In the lecture, you said that 3(square) is a syntactically valid Fun program, though one that has no value. What if we wanted to rule it out as a valid program, and say that it was a syntax error?
A: You could (in principle) easily change the parser so that in a function application f(x), the f had to be an identifier; and you could do this without changing the abstract syntax. But I understand you want to allow any expression except a number to appear as f, and you want this restriction reflected in the abstract syntax.
You can do this by introducing two mutually dependent types Expr and Expr2, something like this:
data Expr = Number Integer | Nonnum Expr2
data Expr2 =
Variable Ident
| Apply Expr2 [Expr]
| IfExpr Expr Expr Expr
| ...
(Note that the first argument of Apply must be an Expr2.) That's OK, but it will lead to a lot of clutter, and really it's best from a practical point of view to accept a more liberal abstract syntax.
Neither of these moves removes the need to deal during evaluation with the problem that a function call may refer to a non-function: consider the program
let val three = 3 in three(square)
In a typed version of Fun, both this and the original expression would contain a type error; in our untyped interpreter, both lead to the error "applying a non-function".
Q: Instead of writing,
xm $> f = (\ mem -> let (x, mem') = xm mem in f x mem'),
wouldn't be better to define xm ▹ f = uncurry f . xm ?
A: Perhaps so, because then the general law uncurry (λ x → p . q x) = p . uncurry q would allow us to calculate
(xm $> f) $> g = uncurry g . uncurry f . xm = uncurry (\ x -> uncurry g . f x) . xm = xm $> (\ x -> f x $> g)
And what's more, result = curry id, so
xm @> result = uncurry (curry id) . xm = id . xm = xm.
and even
result x $> f = uncurry f . curry id x = f x
Neat!