Of course, obviously the point of the exercise is to encourage thinking about how a computer actually performs computations, which is in a linear, imperative fashion. In that case, why use Scheme in the first place? Its syntax and semantics encourage exactly the opposite style of programming, and in my opinion, obstruct the learning process in this kind of problem.
To make an analogy, teaching this problem using Scheme is like teaching someone how to bake a cake using an unplugged Kitchenaid. The Kitchenaid would work great if it was plugged in, but it's not, so you have to push the beater around by hand. Why not just use a hand beater in the first place? [Scheme would work great for this problem if it had memoization, but it doesn't, so you have to solve the problem as if you were using Python. Why not just use Python in the first place?]
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))Scheme was also designed to encourage implementing non-recursive control structures, as well as programming with side effects. Scheme isn't supposed to be totally pure. If you encounter a problem that requires mutation, you're supposed to try to abstract away from the mutation, if possible, and it gives you the tools to do that. (first class functions, macros, continuations, etc. are all very effective tools for abstraction, once you learn them.)
I recommend that you use SICP to learn Scheme, as it will make more sense when you actually know how to use it. It's an incredibly elegant and beautiful language, and it's certainly still relevant.
P.S. If you're thinking of those problems in terms of iteration and mutation, you're probably doing it wrong :). Think more functionally.
I used it my entire graduate career, under an advisor who is part of the inner circle of PLT/Racket. I'm quite familiar with it.
> P.S. If you're thinking of those problems in terms of iteration and mutation, you're probably doing it wrong :). Think more functionally.
I primarily program in Mercury and Coq (languages which are both purely functional). I can promise you I have no problem "thinking functionally". The solution presented in SICP is not structurally recursive (while the "naïve" solution is) but rather relies on an accumulator, tail calls, and a measure to terminate recursion... this is much closer in spirit to an iterative algorithm than a recursive one.
http://pnyf.inf.elte.hu/fp/FunctionGraphs_en.xml
http://pnyf.inf.elte.hu/fp/Diagrams_en.xml
Others here: http://pnyf.inf.elte.hu/fp/Overview_en.xml
http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussma...
I recommend a project with lots of IO and State. You'll quickly come to understand why the monadic approach to such things is excellent (even if Haskell's implementation is a bit verbose).
http://www.starling-software.com/blogimg/tsac/1011/fremlin-t...
In my opinion the idea that there is a division between functional and non-functional programming at all comes because of a disagreement or misunderstanding with the principles of SICP: C is a perfectly functional programming language if you say that each statement is a function from machine state to machine state. . .
I'm a little worried that I'm so good at imperative programming, though, since it might indicate that I'm "crippled" when it comes to functional programming. I bet one of you could code circles around me when it comes to e.g. implementing a DSL.
Anyone have advice about how I'd go about "diving into functional programming"? What's a fun project to do in Haskell, for example?
I rarely approach a programming problem by trying to define functional routines. Instead, I almost always use state. Seems like a bad habit that I need to focus on breaking.