Frequently asked questions (Programming Languages)

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

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.

New questions

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