Does Rust have trampolines? Or is there a better alternative somehow?
Trampolines usually refer to some kind of runtime code generation, which doesn't really fit with Rust's philosophy, but it's also a term which means many different things in different contexts, so perhaps you could explain the exact behavior you're looking for?
A trampoline usually is a guard function that calls functions so as to avoid using stack.
No?
Anyway we have a parser in Lua where we give it some [input token] = next state or [input token] = function that returns next state and that's basically a trampoline. How do you do that in Rust tho?
I think you are referring to something similar to Clojure's trampoline. indeed, because JVM doesn't support proper tail recursion, programmers must manually use trampoline if they want to avoid unbounded recursion to overflow the stack. however, for a language with tail recursion implemented, you don't typically need such construct.
could you please describe the problem in detail? maybe trampoline is not the solution you were looking for.
as geeklint points out, trampoline is a term which can mean different things in contexts, for example, some people use the term trampoline to refer to little code segments generated at runtime (e.g. by a JIT compiler, also sometimes called thunk).
anyway, I glanced over your code, but didn't find anything specific to recursion or stack control. are you referring to the defs table which has both strings and function as values? if so, a roughly smilar state machine can be implemented using an enum, something like this:
enum State {
StateA,
StateB,
StateC,
}
enum NextState {
Eager(State),
Lazy(Box<dyn Fn() -> State>),
}
type TransitionRule = HashMap<State, NextState>;
let mut rules = HashMap::new();
rules.insert(State::StateA, NextState::Eager(State::StateB));
rules.insert(State::StateB, NextState::Lazy(Box::new(|| State::StateC)));
// you can use helper functions to make it less verbose
rules.insert(State::StateC, next(|| State::StateA))
but I don't really understand your code, I might be misunderstanding your problem. could you please elaborate a little more?
we want rules to be a type instead of a value tho.
we want a compile-time, but mutable (at compile-time), "defs table".
ah, I see. I think this should be possible via type level computation, but it might not be very practical except in some contrived simple scenarios. sorry I can only give some contrived examples, I don't know how to apply to your real problem.
trait State {
// I assume eventually you'll need a runtime value?
//type Value;
//fn get(&self) -> Self::Value;
// transition to next state
type Next: State;
// run time
//fn next(&self) -> &Self::Next;
}
type LazyState<S: State> = Box<dyn Fn() -> S>;
impl<S: State> State for LazyState<S> {
type Next = S::Next;
}
struct StateA;
struct StateB;
struct StateC;
impl State for StateA {
type Next = StateB;
}
impl State for StateB {
type Next = StateC;
}
impl State for StateC {
type Next = LazyState<StateA>;
}
// if you need runtime representation,you can use a trait object
type AnyState = Box<dyn State>;
so the way we have it, we have the "[input] = next state" table, but also, when the input maps to a function, the function gets additional state passed to it.
so maybe something like this?
trait StateMachine {
???
}
enum Foo {
A, B, C
}
impl StateMachine for Foo {
???
}
enum Bar {
Foo(Foo), X, Y
}
impl StateMachine for Bar {
???
}
we don't know...
to be honest, I don't know what you are trying to achieve, like, I don't really know what do you mean by
also, I don't have the knowledge to understand the Lua code you provided, but in rust, parsing is often done via parser combinator libraries, such as nom and chumsky; since you mentioned Lua, I suppose you might be familiar with LPeg, there's also a PEG based parsing library called pom , although not as popular as nom, but still widely used.
the benefit of it being a bunch of tables is that any API consumer can just... [input] = new next state.
it's an extensible parser, basically.
well in that particular case it's an extensible lexer but anyway.
it's basically a monkeypatchable parser/lexer.
I implemented a basic trampolined recursion pattern:
use std::ops::Add;
enum Trampoline<O> {
Pending(Box<dyn FnOnce() -> Trampoline<O>>),
Finished(O),
}
impl<T, U> Add<Trampoline<U>> for Trampoline<T>
where
T: Add<U>,
T: 'static,
U: 'static,
{
type Output = Trampoline<<T as Add<U>>::Output>;
fn add(self, rhs: Trampoline<U>) -> Self::Output {
use Trampoline::*;
match (self, rhs) {
(Finished(t), Finished(u)) => Finished(t + u),
(Finished(t), Pending(func)) => Pending(Box::new(|| Finished(t) + func())),
(Pending(func), Finished(u)) => Pending(Box::new(|| func() + Finished(u))),
(Pending(func_t), Pending(func_u)) => Pending(Box::new(|| func_t() + func_u())),
}
}
}
fn fib(n: usize) -> Trampoline<usize> {
if n < 2 {
Trampoline::Finished(1)
} else {
Trampoline::Pending(Box::new(move || fib(n - 1) + fib(n - 2)))
}
}
fn main() {
let n = 10;
let mut trampoline = fib(n);
while let Trampoline::Pending(func) = trampoline {
trampoline = func();
}
match trampoline {
Trampoline::Pending(_) => unreachable!(),
Trampoline::Finished(value) => println!("fib({}) = {}", n, value),
}
}
Does this suit your needs? The Add implementation seems like a lot of boilerplate that could likely be reduced further using combinators.
hmm we don't think we could use this for a parser...
This is the classic trampolined recursion pattern, e.g. as described as in this blog. Because nothing can get monomorphized and every trampoline step requires at least one allocation, it is a lot slower than standard recursion, but saves stack space (preventing a stack overflow in all cases). Because you could also just spawn a new thread and assign the stack space you need, this pattern is somewhat useless in most scenarios in Rust. I have used this pattern in Closure and JavaScript before, where this isn't an option in most cases, but have never heard of this being applicable for a parser infrastructure - parsing an AST usually doesn't go into depths where this pattern would be needed or wanted, and if it would, you could just Box or Arc your nodes.
With that said, here is a better version making use of combinators like map and zip to implement fib, if you need it for whatever reason.
we're probably asking the wrong things...
This might be the case - this Wikipedia disambiguation page might help you find the exact term you need to be able to rephrase your question. I referred to the first bullet point in the section "High-level programming".
This is exactly what I implemented and what fits this description. Instead of using the stack, there is a data structure called a trampoline (the name might me misleading, I've not actively researched the proper terms) which is either a directly usable value or a closure/function on the heap. The fib function is one example of how such a structure might be used - this recursion explicitly avoids using the stack.
With that said, you specified that you weren't satisfied with the solution I posted - you might want to give more detail into why this is the case, and provide a more concrete example. Your question, as it stands right now, seems ambiguous and could be interpreted in one of the many ways enumerated in this reply's first link.
well, our goal is to do something akin to the lua thing, but in rust. but we also have no idea how to go about it. >.<
but we also don't want "a parser". the lua thing has a few specific properties we would like to carry over.
I don't have any experience with these, but there are at least two crates that purport to offer the kind of trampoline I believe you are talking about:
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.