Stack Overflow
Stack Overflow

Questions tagged [trampolines]

A technique to emulate (or augment) jumps / function calls by a custom dispatch. A single trampoline is sufficient to express all control transfers of a program.

A technique to emulate (or augment) jumps / function calls by a custom dispatch to converted functions which return control back to the dispatch (a.k.a. the trampoline) instead of making the function calls themselves, using data to control the control flow.

A single trampoline is sufficient to express all control transfers of a program; a program so expressed is trampolined or in "trampolined style"; converting a program to trampolined style is trampolining. Trampolined functions can be used to implement tail recursive function calls in stack-oriented languages.

See Wikipedia.

71 questions
119
votes
8 answers

What is a trampoline function?

During recent discussions at work, someone referred to a trampoline function. I have read the description at Wikipedia. It is enough to give a general idea of the functionality, but I would like something a bit more concrete. Do you have a simple…
Benoit
  • 37,894
  • 24
  • 81
  • 116
53
votes
3 answers

How to understand trampoline in JavaScript?

Here is the code: function repeat(operation, num) { return function() { if (num <= 0) return operation() return repeat(operation, --num) } } function trampoline(fn) { while(fn && typeof fn === 'function') { fn = fn() …
Zhen Zhang
  • 1,052
  • 1
  • 11
  • 18
21
votes
3 answers

What are some good ways of implementing tail call elimination?

I've written a small Scheme interpreter in an unholy mix of C/C++, but I have yet to implement proper tail calls. I am aware of the classic Cheney on the MTA algorithm, but are there other nice ways of implementing this? I know I could put the…
csl
  • 10,937
  • 5
  • 57
  • 89
20
votes
2 answers

Why doesn't Haskell need Trampolining?

As Scala developer learning the IO Monad, and therefore technicalities of Trampolining in general that are necessary for recursion where tail call optimization is not possible, I wonder how Haskell seems to natively avoid it. I get that Haskell is a…
MaatDeamon
  • 9,532
  • 9
  • 60
  • 127
20
votes
2 answers

How to use TailCalls?

If I understand correctly, scala.util.control.TailCalls can be used to avoid stack overflows for non-tail-recursive functions by using a trampoline. The example given in the API is straightforward: import scala.util.control.TailCalls._ def…
Landei
  • 54,104
  • 13
  • 100
  • 195
15
votes
2 answers

How to create a trampoline function for hook

I'm interested in hooking and I decided to see if I could hook some functions. I wasn't interested in using a library like detours because I want to have the experience of doing it on my own. With some sources I found on the internet, I was able to…
Stratus
  • 373
  • 1
  • 4
  • 9
11
votes
3 answers

Applicative vs. monadic combinators and the free monad in Scalaz

A couple of weeks ago Dragisa Krsmanovic asked a question here about how to use the free monad in Scalaz 7 to avoid stack overflows in this situation (I've adapted his code a bit): import scalaz._, Scalaz._ def setS(i: Int): State[List[Int], Unit]…
Travis Brown
  • 138,631
  • 12
  • 375
  • 680
10
votes
2 answers

FoldRight over Infinite Structures in Scala using Trampolines

Let's start with a straightforward definition of foldRight: def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = { as match { case Nil => base case head +: next => f(head, foldRight(base)(f)(next)) } } One of the advantages…
Hugo Sereno Ferreira
  • 8,600
  • 7
  • 46
  • 92
9
votes
3 answers

How to adapt trampolines to Continuation Passing Style?

Here is a naive implementation of a right fold: const foldr = f => acc => ([x, ...xs]) => x === undefined ? acc : f(x) (foldkr(f) (acc) (xs)); This is non-tail recursion and hence we cannot apply a trampoline. One approach would be to…
user5536315
9
votes
2 answers

MonoDevelop settings to fix "ran out of trampolines type 2" error

we are developing an iOS app. When we tested the app on PC, everything works well but when we ran it on a iPad/iPhone4 we frequently receive the "Ran out of Trampolines type 2" error message and the app crash. We have been spending the last few…
Richard
  • 111
  • 3
8
votes
0 answers

Track notifications click without trampolines (forbidden in Android 12)

Android 12 has forbidden the so called notification trampolines: https://developer.android.com/about/versions/12/behavior-changes-12#notification-trampolines Currently I'm tracking notification click events trough analytics tools but making use of a…
Carlo Codega
  • 93
  • 4
8
votes
0 answers

Does this (Trampoline-like) construct have a name?

I've wanted to avoid blowing the stack while creating a system similar to function advice or method combination. This involves tree traversal (in my implementation), conditional recursion, etc. One of the very few methods available for converting…
snawster
  • 152
  • 3
  • 9
8
votes
3 answers

What is the standard way to optimise mutual recursion in F#/Scala?

These languages do not support mutually recursive functions optimization 'natively', so I guess it must be trampoline or.. heh.. rewriting as a loop) Do I miss something? UPDATE: It seems that I did lie about FSharp, but I just didn't see an example…
Bubba88
  • 1,910
  • 20
  • 44
7
votes
1 answer

What do "Runtime Trampolines" mean in MonoTouch 6.0.8 Release Notes?

MonoTouch 6.0.8 release notes say: Runtime Trampolines: It is no longer necessary to manually manage trampolines in the Mono runtime, trampolines are now handled dynamically. What does this mean? How do you manually manage trampolines anyway? Do…
Dan Abramov
  • 264,556
  • 84
  • 409
  • 511
6
votes
3 answers

Using Lambda/Template/SFINAE to automate try/catch-safeguarding of trampoline functions

I have 100 or so trampoline functions. I would like to know whether it is possible to automate wrapping each one inside a try/catch block. Please be warned in advance, this is not an easy question. I will start by describing the problem with…
P i
  • 29,020
  • 36
  • 159
  • 267
1
2 3 4 5