| Latest revision |
Your text |
| Line 1: |
Line 1: |
| [[Category:Research]]
| | Warning: This article is a work in progress! No refunds if it moves! |
| [[Recursion]] is a fantastic and often ignored feature of programming languages. Most introductions show an example you'd never use in practice, so this article is my attempt at showing some better ones using Lua.
| |
|
| |
|
| ==Loops==
| | TODO: This article is about tail calls |
| Recursion can create loops without language constructs.
| | |
| | - introduction/overview |
|
| |
|
| Here's an infinite loop:
| | - 'magic of recursion'? |
| function infinite_loop()
| |
| print("Hello there!")
| |
| return infinite_loop()
| |
| end
| |
| infinite_loop()
| |
|
| |
|
| This is a bit longer than a non-recursive example.
| | - lua |
|
| |
|
| Here's a counting loop:
| | ==Recursion== |
| function count_down(number)
| | As a quick refresher, recursion is when code calls itself. |
| if number == 0 then return end
| |
| print(number)
| |
| return count_down(number - 1)
| |
| end
| |
| count_down(100)
| |
|
| |
|
| A non-recursive version of this would likely use some kind of for or while loop.
| | Here's a textbook example: |
|
| |
|
| Here's a loop that asks a user to pick a valid choice:
| | function fac(n) |
| function get_choice(choices) | | if n < 1 then |
| local line = io.read()
| | return 1 |
| choice = choices[line]
| |
| if choice then | |
| return choice | |
| else | | else |
| print("Invalid choice! Try again")
| | return n * fac(n - 1) |
| return get_choice(choices) | |
| end | | end |
| end | | end |
| print("Select a letter to get a number: A, B, C") | | |
| choice = get_choice({A=1, B=2, C=3})
| | print(fac(20)) |
| print("You picked number " .. choice)
| | -- prints 2432902008176640000 |
| Without recursion this code would look a lot more confusing, at least to me.
| | |
| | This code has a function 'fac' that takes a number and: |
| | |
| | * Returns 1 if the number is less than 1 |
| | * Calls fac with the number minus 1 |
| | * Multiplies the result of fac by the number |
| | * Returns the multiplied result |
| | |
| | Unfortunately there's a problem with this. When we call fac we need to save our current number to the 'stack' so we can multiply it with the result of fac. If we recurse too many times we run out of memory on the stack to save our numbers. |
| | |
| | Because of this tendency to overflow the stack recursion isn't seen much in mainstream programming. |
|
| |
|
| ==State machines== | | ==Tail calls== |
| Not all recursion has to be direct. Indirect recursion lets you represent state machines easily.
| | What if we didn't need to save anything? We could recurse forever without any stack overflows. |
|
| |
|
| Here's a tiny adventure game with the player choosing state transitions:
| | Let's say we rewrite our factorial code to this: |
| function dark_room() | | function fac(n, acc) |
| print("You are in a dark room.")
| | if n < 1 then |
| print("Pick a door: fuzzy or metal")
| | return acc |
| choice = get_choice({fuzzy=1, metal=2})
| | else |
| if choice == 1 then return fuzzy_room() | | return fac(n - 1, acc * n) |
| elseif choice == 2 then return metal_room() | |
| end | | end |
| end | | end |
| function fuzzy_room() | | |
| print("This room feels pretty fuzzy...")
| | print(fac(20, 1)) |
| print("Pick a door: dark, metal")
| | -- prints 2432902008176640000 |
| choice = get_choice({dark=1, metal=2})
| | |
| if choice == 1 then return dark_room()
| | This new code has a function 'fac' that takes a number and accumulator: |
| elseif choice == 2 then return metal_room()
| | |
| end
| | * Returns the accumulator if the number is less than 1 |
| end
| | * Multiplies the accumulator by the number |
| function metal_room()
| | * Calls fac with the number minus 1 and new accumulator value |
| print("This room feels really metallic.")
| | * Returns result of fac |
| print("Pick a door: dark, fuzzy or win")
| | |
| choice = get_choice({dark=1, fuzzy=2, win=3})
| | Instead of storing numbers on the stack and multiplying them afterwards, we now accumulate them as we go. |
| if choice == 1 then return dark_room()
| | |
| elseif choice == 2 then return fuzzy_room()
| | TODO: explain tail calls |
| elseif choice == 3 then return metal_room()
| | |
| end
| | ==Tail call elimination== |
| end
| | We still have a problem. I didn't mention it earlier, but when we call functions in programming languages we also put a return address on the stack. We don't store any numbers on the stack but we still store a return address every time we call fac. If we recurse too many times we still run out of memory. |
| function win_room()
| | |
| print("You found the treasure!")
| | What if we |
| return
| | |
| end
| | - we've been writing code as there's no stack |
| dark_room()
| | |
| Without recursion you'd likely need to put everything in a single function with a loop and state variable.
| | - tail call elimination |
| | |
| | - NOT an optimization, how many optimizations decide which way you can program? |
| | |
| | - hints deeper at function calls vs jumps |
| | |
| | - structured programming, goto wars |
| | |
| | ==Loops== |
| | - recursion can implement loops! |
| | |
| | - implementing a for loop |
| | |
| | - implementing a while loop |
| | |
| | - implementing a do while loop |
|
| |
|
| Some things just make more sense when implemented recursively, to me at least.
| | - each loop iteration only shares global and function args |
|
| |
|
| == Tail call optimization == | | ==State machines== |
| There is a caveat with recursive programs: Each function call takes up stack space. The deeper you recurse, the more likely you are to run out of stack space and crash your program. This makes recursion useless in most programming languages.
| | - implementing a stateful algorithm |
|
| |
|
| However there is a compromise: If a return in a function is just a call to another function then that return call is a 'tail call'. Languages that implement tail call optimization will re-use the current function call's stack for the function you're calling, solving the issue of stack space.
| | - some kind of menu system |
|
| |
|
| All the examples on this page use tail calls and run in Lua which implements tail call optimization. This means every program on this page is immune to stack overflows.
| | - the code makes sense to read |
|
| |
|
| The 1977 [https://en.wikisource.org/wiki/Index:AIM-443.djvu AI Lab Memo 443] talks more broadly about how tail calls are like goto statements that you can pass arguments to. Huge shout-out to the folks at Wikisource that transcribed this to an accessible text form.
| | - this is mutual recursion |
|
| |
|
| The significant downside of tail call optimization from a user perspective is that it can make debugging more difficult as you lack a proper stack trace.
| | - very hard to do in a traditional structured language |
|
| |
|
| From an implementer perspective the problem is that stack cleanup is tricky: A function that tail calls another cannot clean up any temporary variables it passes along. The solution to this is to make sure function stack use is identical and have the caller clean up, or to implement garbage collection.
| | ==Lambdas== |
| | - lambdas to actually replace looping constructs/switch statements |
|
| |
|
| ==Language support==
| | - most mainstream languages support lambas |
| Despite languages slowly adding features from functional languages developed 40 years ago, tail call optimization is still unpopular. I'm guessing that the reason is because not many people see the use of recursion.
| |
|
| |
|
| Here's an incomplete list of languages that support it automatically:
| | - recursion-based control flow |
|
| |
|
| * Haskell
| | ==Mainstream support== |
| * Erlang (and Elixir)
| | - functional programming languages |
| *Any Scheme implementation (Chez Scheme, Chibi Scheme, Chicken Scheme, TinyScheme)
| |
| *Lua (see [https://www.lua.org/pil/6.3.html Programming in Lua 6.3 - Proper Tail Calls])
| |
| *Steel Bank Common Lisp (See [http://www.sbcl.org/manual/#Debug-Tail-Recursion SBCL Debug Tail Recursion])
| |
| *Squirrel (See [http://squirrel-lang.org/squirreldoc/reference/language/threads.html Squirrel's Threads page])
| |
| *Racket (See [https://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html#%28part._tail-recursion%29 The Racket Guide 2.3.3 - Tail Recursion])
| |
| Here's an incomplete list of languages that require explicit support:
| |
| * Clang C and C++ (see the [https://clang.llvm.org/docs/AttributeReference.html#musttail Clang musttail attribute])
| |
| * Tcl (see [https://www.tcl.tk/man/tcl/TclCmd/tailcall.html Tcl's tailcall manual page])
| |
| *OCaml (See [https://ocaml.org/manual/attributes.html OCaml's tailcall attribute])
| |
| * Perl (See [https://perldoc.perl.org/functions/goto Perl's goto function], specifically the goto &NAME variant)
| |
| *Unix (See [https://jeapostrophe.github.io/2012-05-28-exec-vs--post.html exec and Tail-call Optimization])
| |
| *Assembly (Instead of returning set up registers and jump)
| |
| *Ruby (See [https://nithinbekal.com/posts/ruby-tco/ Ruby's tailcall_optimization compile option])
| |
| *Zig (See [https://ziglang.org/documentation/master/#call Zig's always_tail call option])
| |
|
| |
|
| Here's an incomplete list of popular languages that don't support it:
| | - lua |
|
| |
|
| * C and C++
| | - clang mustcall |
| * Go
| |
| * Rust
| |
| * Swift
| |
| * PHP
| |
| *Python
| |
| *Raku
| |
| * Anything running on the JVM (Java, Clojure, Scala, Kotlin)
| |
| * Anything running on .NET (C#, F#)
| |
| * Anything running on WebAssembly
| |
| * Anything JavaScript or transpiling to JavaScript (TypeScript, CoffeeScript)
| |
| Things look decent for desktops, but not so much for phones or web browsers.
| |
|
| |
|
| Personally I lean towards the idea of languages adding new keywords or explicit support for this, such as a 'goto' or 'jump' keyword. It helps in a debugger when you have stack frames by default, and it helps make it clear that it's important that this tail call is optimized.
| | - webassembly |