This is the overriding concern of the FP advocate. They want to reason about their code. This is a strange proposition to the vast majority of industry. They don't want to reason about it, they want it to be easy to implement and run fast!Well, you do find trolls on the internet, but I was surprised to see a professor say:
... I've always come at these problems from the industrial standpoint, not the academic theoretical I-want-to-reason-about-it standpoint.
I would cheerfully give up [the ability to off-line analyze a file] for the sake of [a top-level REPL and a model where loading a file is just like “typing it in”].Analysis of code doesn't just mean ‘automated theorem proving’. It also means being able to casually look over the code and get a clue as to what it is doing. Just looking at what identifiers are defined in a program and which are free can give a lot of the context. But as you can see, you cannot just slavishly evaluate each form in turn in order to understand the entire program.
As to Student B's question, “How you can tell what you need to evaluate and what you don't?” I think I was too vague in presenting the question or too caught up in anthropomorphization. We need to step back from what the interpreter does with the code (evaluation) and abstract from it (abstract evaluation). Student B, of course, wouldn't be expected to understand this, but the professor should, and he ought to be able to frame the issue in a way that Student B can at least follow.
For the specific example of this quiz, you can simply say ‘ignore any top-level form that isn't a definition’. This is usually a pretty good rule of thumb, and I'll start there, but we need to be a lot more precise. (Since the questions, if poorly stated, at least have agreed upon answers, we ought to be able to precisely specify why our answers are correct.)
2 comments:
In this precise case, assuming a basic understanding of the concept of a function (in the functional programming sense), and given that fib is a function (assuming there is no hidden trap, such as redefinition of basic operators, fib does not violate functional programming in any obvious way, such as using set!), basic algebra can help with this evaluation :
(= (- (fib 100) (fib 99)) (fib 98))
-> (= (- (+ (fib 99) (fib 98)) (fib 99)) (fib 98))
and it should be pretty clear that
(- (+ (fib 99) (fib 98)) (fib 99)) yields (fib 98), without any need for evaluating anything beyond that.
I admit this is quite specific to this given problem, but if Student B was not able to see this in a few minutes, he has some fundamental misunderstanding about either very basic algebra or the concept of a function (he apparently does not believe that a function will return the same answer when called with the same arguments). If I ever were a teacher facing that student, I think I would tell him that there is a brick wall in his head that needs to be destroyed, namely the one between functional programming and mathematics. Which might boil down to the same thing as telling him to reason about code instead of evaluating it, but sometimes presenting things from a different viewpoint and making parallels with previous knowledge can help a lot.
Of course, this only holds for functional programming (and perhaps logic programming ?). For more imperative styles, the parallel with mathematics is way less obvious.
By the way, is there any compiler that would actually detect that kind of simplification ? I do not know much about lazy evaluators such as Haskell compilers, but I doubt lazy evaluation alone would be enough. (And, of course, the compiler would need to know it is dealing with pure functions, which might not be possible in a non-pure language such as scheme.)
Gary, you might be fascinated by how smart GCC is for some problems like this:
http://blog.32leaves.net/?p=674
I actually recall reading a test where someone was trying to use fibonacci to do a benchmark and discovered that when computing fib(n) for moderately small N using a double-recursive-call implementation and compiling with GCC -O3, that GCC would actually be smart enough to precalculate the result at compile time and store it as a constant! Obviously, to do that, it would have to do some static analysis showing that the function was pure. Unfortunately, I'm not in an environment where I can test it right now, and I can't find where I read about it.
Post a Comment