How the right syntax can help teach recursion(akkartik.name)
akkartik.name
How the right syntax can help teach recursion
http://akkartik.name/post/swamp
63 comments
Maybe it's just that I'm not writing code as complicated as you, but 5 years of school and 5 years of industry, I've never had to hold more than a single level of a function in my head at once. My trick is to explicitly say what contract the function fulfills, i.e. if the input has X property, then the output has Y property. Then when you make the recursive call, you can just assume your called function behaves as advertised. I thought this was the whole point of recursion.
What you're describing is how normal functions are generally written.
If there is no difference in complexity between writing a function that calls itself and a function that just computes some data and returns it then surely this discussion wouldn't be happening. I think it's happening for a reason so I tried to articulate this.
I'm speculating that recursive solutions are more difficult for people to write, because (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'), (3) the function calls each relate to each other and likewise so do their values, but this mapping is generally not expressed well within the code or within outputs you might debug (after each function application, a value is received for which the context of how it was produced is often lost.)
I'm probably speaking in too abstract a way to be clear. I think the tools could be improved here; I was thinking about the problem earlier on and I realised that generally I solve it by breaking the problems up into tiny functions [0]. Unfortunately, there's a time cost to this approach, so I would prefer it if debugging tools would instead allow you to annotate blocks of code. They could then represent this information visually. This would help me.
I also think that good teaching is important. I remember that I used to be utterly terrible at writing these functions: my main issue was often that I didn't start by thinking about the 'base case' and the simplest inputs. That's easy to get right.
I do think that my mind has never been very well suited to recursive computation, however I believe I'm decent at understanding and problem-solving around this. It's because I have to think carefully and tool myself when dealing with recursive problems, that I'm able to describe the pitfalls. I have never been the kind of person to compel myself into understanding something merely by stating "this is easy".
[0] https://twitter.com/nouswaves/status/776384680652398592
If there is no difference in complexity between writing a function that calls itself and a function that just computes some data and returns it then surely this discussion wouldn't be happening. I think it's happening for a reason so I tried to articulate this.
I'm speculating that recursive solutions are more difficult for people to write, because (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'), (3) the function calls each relate to each other and likewise so do their values, but this mapping is generally not expressed well within the code or within outputs you might debug (after each function application, a value is received for which the context of how it was produced is often lost.)
I'm probably speaking in too abstract a way to be clear. I think the tools could be improved here; I was thinking about the problem earlier on and I realised that generally I solve it by breaking the problems up into tiny functions [0]. Unfortunately, there's a time cost to this approach, so I would prefer it if debugging tools would instead allow you to annotate blocks of code. They could then represent this information visually. This would help me.
I also think that good teaching is important. I remember that I used to be utterly terrible at writing these functions: my main issue was often that I didn't start by thinking about the 'base case' and the simplest inputs. That's easy to get right.
I do think that my mind has never been very well suited to recursive computation, however I believe I'm decent at understanding and problem-solving around this. It's because I have to think carefully and tool myself when dealing with recursive problems, that I'm able to describe the pitfalls. I have never been the kind of person to compel myself into understanding something merely by stating "this is easy".
[0] https://twitter.com/nouswaves/status/776384680652398592
In a way I find recursive functions _reduce_ the complexity required to reason about a loop. What made me grok recursion was realizing that it's just a more explicitly defined loop:
- You have to define an end condition. (Really this is no different than the 2nd clause of a C-style for() loop, or the expression evaluated by a `while()` loop.)
- You have to explicitly specify the inputs for each iteration of the loop (e.g: explicitly declare what you need in the function signature, instead of just using whatever variables happen to be in the parent scope as working memory.)
- It makes optimization concerns very quickly apparent, as you'll pretty quickly blow the stack or start waiting for the heat-death of the universe. The best heuristics I have for a quick optimization pass are: is it tail-recursive, and does it needlessly recompute values?
Once I realized recursion is just another way to tell the compiler "repeat this thing until [x] is true", it became a lot less mystical and much easier to reason about.
I'd agree with OP to an extent that syntax did make a huge difference in how I viewed recursion. I understood recursion on a theoretical level for a while, but avoided it whenever possible because I too thought it was difficult to reason about.
It wasn't until I learned Elixir that it "clicked" for me. Between pattern matching and multiple function heads: Elixir just made recursion really easy to think about. (Not having any traditional loop construct probably helped a bit, too.)
- You have to define an end condition. (Really this is no different than the 2nd clause of a C-style for() loop, or the expression evaluated by a `while()` loop.)
- You have to explicitly specify the inputs for each iteration of the loop (e.g: explicitly declare what you need in the function signature, instead of just using whatever variables happen to be in the parent scope as working memory.)
- It makes optimization concerns very quickly apparent, as you'll pretty quickly blow the stack or start waiting for the heat-death of the universe. The best heuristics I have for a quick optimization pass are: is it tail-recursive, and does it needlessly recompute values?
Once I realized recursion is just another way to tell the compiler "repeat this thing until [x] is true", it became a lot less mystical and much easier to reason about.
I'd agree with OP to an extent that syntax did make a huge difference in how I viewed recursion. I understood recursion on a theoretical level for a while, but avoided it whenever possible because I too thought it was difficult to reason about.
It wasn't until I learned Elixir that it "clicked" for me. Between pattern matching and multiple function heads: Elixir just made recursion really easy to think about. (Not having any traditional loop construct probably helped a bit, too.)
I agree with you that it is more explicit than looping: I actually think that with complicated logic, loops suffer from even worse problems, and for simple things most people just `filter`, `reduce` or `map`. That said, I do think the debuggability could be improved.
This is a really nice way to think about recursion! Thanks for sharing it.
> (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'),
These aren't issues as long as you can prove your recurrence relation is correct. If you treat the recursive call as a black box, there is no reason to think about how it actually behaves and computes its result.
These aren't issues as long as you can prove your recurrence relation is correct. If you treat the recursive call as a black box, there is no reason to think about how it actually behaves and computes its result.
I find the pen and paper method of visualizing invaluable. Make a small sample input that hits full coverage and trace it through step by step, writing out each call point with its values. Then you see the shape of your recursion (https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.htm...) and if there's a bug it can quickly become apparent.
Buy yourself a copy of The Little Schemer. It is the best book on recursion I have ever seen. Also mbrock's statement is key.
Agreed, a tool to visualize what's going on with a sample input will be a great help in understanding and writing recursive programs.
It's like how proof by induction seems mind-bending until you learn to think in terms of induction hypotheses.
> learn to think in terms of induction hypotheses.
Can you expand on this or link to a good definition?
Can you expand on this or link to a good definition?
The induction hypothesis is a process in mathematics which assumes a formula for P(n) which is true, then uses this assumption and the problem definition to prove the case P(n+1).
As a concrete example, take the formula for the sum of integers: S(n)= n * (n+1)/2. Proving this inductively means asking what value should be assigned to S(n+1). We can calculate this either with a direct "change of variable" expansion of the hypothesized formula or, nothing that S() is the sum of a series, there is an alternate expansion of S(n)+(n+1). Refactoring both sides yields the same algebraic result, (n+1) * (n+2)/2.
[The final step for a full proof would be to establish a "baseline" case, traditionally either 0 or 1, where we show our formula yields the correct result. The inductive step, applied repeatedly, then proves the formula must be correct for the next higher input, and the one just after that, ad inifinitum.]
As a concrete example, take the formula for the sum of integers: S(n)= n * (n+1)/2. Proving this inductively means asking what value should be assigned to S(n+1). We can calculate this either with a direct "change of variable" expansion of the hypothesized formula or, nothing that S() is the sum of a series, there is an alternate expansion of S(n)+(n+1). Refactoring both sides yields the same algebraic result, (n+1) * (n+2)/2.
[The final step for a full proof would be to establish a "baseline" case, traditionally either 0 or 1, where we show our formula yields the correct result. The inductive step, applied repeatedly, then proves the formula must be correct for the next higher input, and the one just after that, ad inifinitum.]
I think the best way to explain it is that a recursive function is a function which should return either:
- A 'base case' value
- The result of a call to itself (could be multiple calls to itself also)
Basically when you call a recursive function, unless it hits the base case (usually decided by an if condition), it will keep calling itself (often with slightly different arguments each time) until it returns the base case.
Once the function returns the base case, the recursion will start to 'unwind' - In the unwind phase, you can use the return values of the previous recursive calls to do more interesting stuff.
The best way to visualize recursion is to imagine that you have a stack of function calls; each time a function calls itself, it creates a copy of itself with new arguments and puts that copy on top of the stack - Then the program pointer moves to the copy (but it keeps a reference of were it was in the previous call) - And it keeps building up the stack with new copies of the function until it reaches the base case (when the function finally returns a concrete value).
The 'unwinding' phase is just when the functions start returning (after the base case has been reached) and all the function 'copies' just get popped off from the top of the stack one by one - Each time the program will continue running from wherever it was in each call stack.
- A 'base case' value
- The result of a call to itself (could be multiple calls to itself also)
Basically when you call a recursive function, unless it hits the base case (usually decided by an if condition), it will keep calling itself (often with slightly different arguments each time) until it returns the base case.
Once the function returns the base case, the recursion will start to 'unwind' - In the unwind phase, you can use the return values of the previous recursive calls to do more interesting stuff.
The best way to visualize recursion is to imagine that you have a stack of function calls; each time a function calls itself, it creates a copy of itself with new arguments and puts that copy on top of the stack - Then the program pointer moves to the copy (but it keeps a reference of were it was in the previous call) - And it keeps building up the stack with new copies of the function until it reaches the base case (when the function finally returns a concrete value).
The 'unwinding' phase is just when the functions start returning (after the base case has been reached) and all the function 'copies' just get popped off from the top of the stack one by one - Each time the program will continue running from wherever it was in each call stack.
Wow, the guy really is teaching his students how to program using his side-project language?!
Man, if I was the student, I would be pretty upset. There are plenty of popular programming languages to learn. Each one has its own caveats. It's hard enough to learn CaML, or C, or Lisp, but these are at least used in the world!
Why would the student need to learn a programming language that no-one uses? It's either that the teacher is using them as guinea pigs, which is bad enough, or using them advertisement, which is even worse. All in all, he's certainly not making them a favor!
Man, if I was the student, I would be pretty upset. There are plenty of popular programming languages to learn. Each one has its own caveats. It's hard enough to learn CaML, or C, or Lisp, but these are at least used in the world!
Why would the student need to learn a programming language that no-one uses? It's either that the teacher is using them as guinea pigs, which is bad enough, or using them advertisement, which is even worse. All in all, he's certainly not making them a favor!
> Why would the student need to learn a programming language that no-one uses?
The same reasons many examples in textbooks and documentation are in pseudo-code. Sometimes you want to learn general concepts and don't want implementation oddities of specific language(s).
Theory first then practice. That way you are more likely to end up with a skillset you can easily transfer between languages/frameworks/platforms/other.
Essentially his language is the same as any other "made up" pseudo-code syntax.
The same reasons many examples in textbooks and documentation are in pseudo-code. Sometimes you want to learn general concepts and don't want implementation oddities of specific language(s).
Theory first then practice. That way you are more likely to end up with a skillset you can easily transfer between languages/frameworks/platforms/other.
Essentially his language is the same as any other "made up" pseudo-code syntax.
...or teaching them facility in learning a language, which is more valuable than knowing any particular language.
If what you glean from a programming course is a language's syntax you haven't learned how to programme. As long as the map between the language you are taught programming with and the cpu architecture it's running on is clear, the syntax is irrelevant.
True, but if you are going to learn the syntax for a language it may as well be one that is useful elsewhere.
Was Knuth wrong to make up a language to use in his Art of Computer Programming books?
What I normally say about university is: "We teach you everything you need to know, and nothing you can use." That would seem to fit the bill here.
Or maybe the teacher is evaluating the quality of his side-project language for teaching and is offering free programming education to students in order to evaluate it.
Honestly, I don't think there are many jobs out there hiring for Mu programmers, but I ALSO don't think that fact makes learning in Mu a bad idea, and I CERTAINLY don't have any objection to what the teacher is doing!
Honestly, I don't think there are many jobs out there hiring for Mu programmers, but I ALSO don't think that fact makes learning in Mu a bad idea, and I CERTAINLY don't have any objection to what the teacher is doing!
I disagree somewhat, but I don't have time to write a detailed answer. Instead here's a quick sketch that is likely only intelligible if you have a fair bit of PLT background.
The basic point is this: you don't need to teach "raw" recursion, just like you don't teach control-flow using goto. Just like structured programming introduced for/while/do loops to structure control flow, you can structure recursive programs into a few major groups. The most important one is good old structural recursion over algebraic data types. It's follows a very set formula, so there isn't much opportunity to go wrong. It helps to have pattern matching in your language to do this.
This is the approach taken by How to Design Programs (http://htdp.org/)
Example blog post you might read if you want to know more about the theoretical background: http://blog.sumtypeofway.com/an-introduction-to-recursion-sc...
The basic point is this: you don't need to teach "raw" recursion, just like you don't teach control-flow using goto. Just like structured programming introduced for/while/do loops to structure control flow, you can structure recursive programs into a few major groups. The most important one is good old structural recursion over algebraic data types. It's follows a very set formula, so there isn't much opportunity to go wrong. It helps to have pattern matching in your language to do this.
This is the approach taken by How to Design Programs (http://htdp.org/)
Example blog post you might read if you want to know more about the theoretical background: http://blog.sumtypeofway.com/an-introduction-to-recursion-sc...
I think this depends on whether you're teaching down or up. I suspect both work for different people.
(Down == "here's some abstract concept, here's some code that implements it in the language's abstract model", Up == "Okay so everytime you call a function, a new stackframe is created." That's the approach I personally prefer.)
I think the reason why recursion is so hard to understand is that programming languages are incredibly misleading. You see "int a = 5;" and you assume that there's a unique 'a' to which 5 has just been assigned, which is of course a complete lie; 'a' is a template for a memory location which is defined only when the function is called. If you don't know this, recursion makes zero sense. "What, now there's two a's??"
I should go do a blogpost on this.
(Down == "here's some abstract concept, here's some code that implements it in the language's abstract model", Up == "Okay so everytime you call a function, a new stackframe is created." That's the approach I personally prefer.)
I think the reason why recursion is so hard to understand is that programming languages are incredibly misleading. You see "int a = 5;" and you assume that there's a unique 'a' to which 5 has just been assigned, which is of course a complete lie; 'a' is a template for a memory location which is defined only when the function is called. If you don't know this, recursion makes zero sense. "What, now there's two a's??"
I should go do a blogpost on this.
I think trying to reason about recursion in terms of stack frames is madness. I find it quickly overwhelms my working memory. This is why we have the patterns---so you don't have to reason on the machine level. It's similar[1] to proof by induction, on the off chance that helps.
[1] By similar I mean exactly the same as.
[1] By similar I mean exactly the same as.
Well, no. Reasoning about stackframes, or even about recursive calls at a higher level, is how I understand a lot about recursion. It's also the only way to reason about whether a function will build up stack frames.
I think reasoning about recursion in terms of stackframes is silly. But stackframes are useful for getting a handle on how recursion functions at all.
Ah, I see. Agreed with that.
Quoting the author:
With Lisp it's always been non-trivial to know when a
function is tail-recursive. You can't just blindly count
parens, you have to try to "run" the function in your mind.
It can still be non-obvious with an optimizing compiler, or with non-Lisp.
I don't see the point in having beginning students think about tail call optimized recursion vs normal recursion unless they're going through SICP. In the end it can totally be a compiler thing. For instance, GCC can optimize this:
I don't see the point in having beginning students think about tail call optimized recursion vs normal recursion unless they're going through SICP. In the end it can totally be a compiler thing. For instance, GCC can optimize this:
int factorial(int x) {
if (x > 1) return x * factorial(x-1);
else return 1;
}
int factorial(int x) {
int result = 1;
while (x > 1) result *= x--;
return result;
}
When you're using TCO-guaranteed language like Scheme, what's important is you recognize tail position, where TCO is guaranteed. Guaranteed TCO lets you express, for example, state machine using mutually recursive functions. You do see the tail calls as gotos and you heavily rely on that while you're coding.
In that regards, I feel that tail call "optimization" is misleading, since it gives an impression that it's some kind of optional bonus the compiler gives to you. The transformation such as your gcc example is, certainly, an "optimization". If you get one, you're lucky; if you don't, fine, you can live with it. Guaranteed tail call elimination is totally different---if you don't have one, you change the way you write code.
(So, the blanket statement of "Lisp" might be inappropriate, for it's only a subset of Lisps that has guaranteed TCO.)
In that regards, I feel that tail call "optimization" is misleading, since it gives an impression that it's some kind of optional bonus the compiler gives to you. The transformation such as your gcc example is, certainly, an "optimization". If you get one, you're lucky; if you don't, fine, you can live with it. Guaranteed tail call elimination is totally different---if you don't have one, you change the way you write code.
(So, the blanket statement of "Lisp" might be inappropriate, for it's only a subset of Lisps that has guaranteed TCO.)
It's actually not hard to see if a Scheme function is tail-recursive, for another reason: All Scheme functions are tail recursive. The difference is whether you're building up stack frames by calling a recursive function inside that last form in the function, thus requiring the language to build an extra stack frame for it.
The only difficulty in seeing if a function is tail recursive, either way, is just checking for branch instructions. This becomes easier if you wait until the thing's been macroexpanded, and have the lexical environment available so you can tell what names refer to what. Again, Schemes need not bother with this: when you comes across the expression will be the return value, tail-call the outermost function, after collecting the values of all inner functions.
The only difficulty in seeing if a function is tail recursive, either way, is just checking for branch instructions. This becomes easier if you wait until the thing's been macroexpanded, and have the lexical environment available so you can tell what names refer to what. Again, Schemes need not bother with this: when you comes across the expression will be the return value, tail-call the outermost function, after collecting the values of all inner functions.
I feel that you are working with a different version of "tail recursive" than any I have heard before.
Specifically, it is certainly possible to make a non-tail recursive implementation of fib in Scheme. Curious why you seem to be implying otherwise.
Specifically, it is certainly possible to make a non-tail recursive implementation of fib in Scheme. Curious why you seem to be implying otherwise.
I was talking about the mechanics of the compiler/interpreter, at least the original Sussman/Steele implementation.
Let's look at Factorial in Scheme. You mentioned Fib, but Factorial is a simpler example, and will suffice.
If that didn't make sense, just read, "LAMBDA: The Ultimate Declarative." it explains it better than I could.
So yes, all functions in Scheme are TCOed (at least, in the original implementation), it's just that some of the build of stack frames. I don't know if that's how other languages work, but it might be.
Let's look at Factorial in Scheme. You mentioned Fib, but Factorial is a simpler example, and will suffice.
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
(* n (fact (- n 1)))
push *n
push $1
call subtract ;;returns t1 on the stack, taken as arg by fact
call fact ;;both n, and t1, the args to mult, are on the stack, followed by the return address.
jmp mult ;;mult re-uses the stack frame, so it's a tail call.
If that didn't make sense, just read, "LAMBDA: The Ultimate Declarative." it explains it better than I could.
So yes, all functions in Scheme are TCOed (at least, in the original implementation), it's just that some of the build of stack frames. I don't know if that's how other languages work, but it might be.
I find this... still an odd definition. To quote Sussman/Abelson[1], "An evaluator that can execute a procedure such as sqrt-iter without requiring increasing storage as the procedure continues to call itself is called a tail-recursive evaluator."
Specifically, the caller of this function will have to clear out the stack of all operations that were pushed. Something you wouldn't have to do on a tail or non-recursive function.
[1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.htm...
Specifically, the caller of this function will have to clear out the stack of all operations that were pushed. Something you wouldn't have to do on a tail or non-recursive function.
[1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.htm...
It is an odd definition, I won't deny that. I was trying to talk about possible implementation, as opposed to the typical definition, so it's possible that I should have used another term.
By the way, this is the paper I was talking about. It won't explain my bizarre choice of words, but it might explain what I meant when I said that Scheme tail-call optimizes unconditionally:
http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-...
By the way, this is the paper I was talking about. It won't explain my bizarre choice of words, but it might explain what I meant when I said that Scheme tail-call optimizes unconditionally:
http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-...
I think I see the difference. There are tail call optimizations, and then there is tail call recursion. They are two different things, potentially.
Thanks for linking the paper!
Thanks for linking the paper!
Yeah, there you go.
That paper is part of a collection of papers, known as The Lambda Papers. If you enjoyed this one, you'll probably want to read the rest:
http://library.readscheme.org/page1.html
That paper is part of a collection of papers, known as The Lambda Papers. If you enjoyed this one, you'll probably want to read the rest:
http://library.readscheme.org/page1.html
This just looks extra confusing to me
I feel like it would be easier to walk through how the machine deals with it at an assembly level. I if you restrict to a really basic level of just pushing, jumping, and linear execution. Recursion then just becomes executing instructions, even if it means calling the same method you're already executing in.
I think the best way to understand recursion is in terms of induction. If someone gave you the solution to your problem for different inputs, could you compose them together to solve the problem for your current input?
Then you just have to show termination.
Thinking procedurally (i.e. in terms of 'unfolding' the call stack) is unlikely to provide much insight.
Then you just have to show termination.
Thinking procedurally (i.e. in terms of 'unfolding' the call stack) is unlikely to provide much insight.
It is a little interesting that it takes so few changes to the source to rewrite the recursive call as a loop. But really the only advantage it has over C (syntactically, anyway) is that it doesn't require a return at the end. By which I mean, it's kind of a stretch to call this the "right" syntax.
Funnily enough, that Lisp, guaranteed not to run anywhere in this universe, is almost valid Scheme, under SRFI-49 or Wisp. The only thing you'd have change is change def to define, and replace rest.x with (cdr x).
This is pretty interesting, and I am tempted to introduce this syntax in my next C programs. Would anyone advise against it?
Just throw The Little Schemer at them.
Anything better than Haskell's?
myst(6)
I can actually describe explicitly why I've occasionally found writing a recursive function hard. In fact I expect a UI could be created that would make it much much easier.
Basically, for ordinary functions I'm able to remember the values stored in each of the variables. (I do not mean a real computation, but the pretend computation I do at all times when programming.)
However, with recursive functions, I sometimes find myself having to remember 5 or more levels of these same variables. Therefore if I have 5 variables, I might end up having to hold 25 values in my head; obviously it is less than this since often there is some pattern to the values that aids in remembering them.
Additionally, I need to flow the return values back through the functions potentially performing extra computations on them; this can be extra confusing if there were multiple entry-points at a particular recursion level of a function. For example, what line and column number was the function called at, and which block of a function was it within? And, do these values belong to the 7th or 9th call of the function? Due to this I'm no longer able to rely on my memory, and I don't get the cognitive benefits of associating computations to place.
Another issue is that if you write some code which never matches its 'base case' it never finishes computing. This is often difficult to debug, and it can cause your machine to lock up.
Perhaps the solution might be:
- A table to represent the values within a recursive function. With colour coded cells that show which level of function a value comes from (and whether it was an argument or return from a deeper level). Effectively, the idea is to reassociate computation with 'place'. Method of Loci.
- Some tools in order to troubleshoot the times in which they've misprogrammed the 'base case'. For example, set a particular recursion depth when developing and exit if this gets reached. Visualise separately how values are advancing towards matching this 'base case'.
I could probably come up with more, but I need to think concretely again to do so usefully; and I'd need to experiment with different recursive solutions to find out whether I'm solving their individual problems.