Latest revision |
Your text |
Line 1: |
Line 1: |
| [[Category:Research]]
| | 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. |
| [[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== | | ==Loops== |
Line 47: |
Line 46: |
| print("You are in a dark room.") | | print("You are in a dark room.") |
| print("Pick a door: fuzzy or metal") | | print("Pick a door: fuzzy or metal") |
| choice = get_choice({fuzzy=1, metal=2}) | | choice = get_choice({fuzzy=1,metal=2}) |
| if choice == 1 then return fuzzy_room() | | if choice == 1 then return fuzzy_room() |
| elseif choice == 2 then return metal_room() | | elseif choice == 2 then return metal_room() |
Line 55: |
Line 54: |
| print("This room feels pretty fuzzy...") | | print("This room feels pretty fuzzy...") |
| print("Pick a door: dark, metal") | | print("Pick a door: dark, metal") |
| choice = get_choice({dark=1, metal=2}) | | choice = get_choice({dark=1,metal=2}) |
| if choice == 1 then return dark_room() | | if choice == 1 then return dark_room() |
| elseif choice == 2 then return metal_room() | | elseif choice == 2 then return metal_room() |
Line 76: |
Line 75: |
| Without recursion you'd likely need to put everything in a single function with a loop and state variable. | | Without recursion you'd likely need to put everything in a single function with a loop and state variable. |
|
| |
|
| Some things just make more sense when implemented recursively, to me at least.
| | ==Mainstream support== |
| | - functional programming languages |
|
| |
|
| == Tail call optimization ==
| | - lua |
| 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.
| |
|
| |
|
| 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.
| | - clang mustcall |
|
| |
|
| 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.
| | - webassembly |
| | |
| 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.
| |
| | |
| 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.
| |
| | |
| 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.
| |
| | |
| ==Language support==
| |
| 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:
| |
| | |
| * Haskell
| |
| * Erlang (and Elixir)
| |
| *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:
| |
| | |
| * C and C++
| |
| * 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.
| |