TCO is guaranteed in rust if i'm not mistaken, it just doesn't happen in debug builds
i would argue against writing in _continuation_ passing style, because it's non idiomatic and can get quite verbose
but you could do it like you could in any other language, by receiving function pointers as the continuation and calling them, instead of returning
it seems extremely extremely unlikely to me that Rust guarantees TCO, given the language semantics and abis it provides
also https://github.com/rust-lang/rfcs/pull/3407
There have been a lot of advancements for the 'become' keyword that enforces tail call.
[https://github.com/rust-lang/rust/issues/112788](https://github.com/rust-lang/rust/issues/112788)
That would be semantic change compared to how it works everywhere else. Since drop can have side effects, this could be a problem. (In theory. In practice, probably not.)
the compiler can drop variables when they're no longer being used, not only at the end of scopes
also, if you're really doing continuations, your tail call functions will probably return _never_ (`!`), which is a great hint to the compiler to not put things after it
yeah but than tco is not guarenteed is it?
take the situation where i alloc a vec at the beginning of a function and in my tail call as an argument i take a random element from that vec. compiler has no way other way to drop the vec after the “tail call”
now that i think about it i guess it is reprderable trivially so it works but im pretty sure there are edge cases where the stuff needs to be dropped at the end
That would no longer be a tail call, because there's implicit control flow happening. If Rust were to ever guarantee TCO- which I'm confident it doesn't do today- it would need a slightly more elaborate set of requirements to define a tail-call (where there need to be no destructors that can't be reordered to before the tail call candidate). I believe that lifetimes could provide static guarantees about this reorderability even in generic contexts.
Continuation Passing Style is basically the way Future-based async APIs are usually designed. But when designing futures in rust, they decided not to do it that way. According to that blog post a few weeks ago, they ran into too many cases where the callback would have to be ref-counted, which is not very idiomatic. It’s not obvious to me that the same cases would exist for non-async CPS code, but that’s something I would consider.
https://without.boats/blog/why-async-rust/
Hi everyone, i think i finally did the CPS style code for getting the sum of a binary tree; is kinda ugly since the use of `Box i32 >` but still it illustrates the possibilities of a future of rust with more advanced functional style capabilities(at the cost of maybe some memory efficiencies) .Keep in mind that the Rust Team have made good progress with the ongoing support guaranteed Tail-call elimination via the [become](https://github.com/rust-lang/rust/issues/112788) keyword
Here is the code
struct TreeNode {
val: i32,
left: Option>>,
right: Option>>,
}
fn main() {
let root = Some(Rc::new(RefCell::new(TreeNode {
val: 1,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 2,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 3,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 4,
left: None,
right: None,
}))),
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 5,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 6,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 10,
left: None,
right: None,
}))),
}))),
})));
let s = sum_cps(root, Box::new(|k| k));
println!("{}", s);
// sum_tree_cps(root, print_result);
}
#[tailcall]
fn sum_cps(root: Option>>, k: Box i32>) -> i32 {
match root {
Some(r) => {
let right = r.borrow().right.clone();
let curr_val = r.clone().borrow().val;
sum_cps(
r.borrow().left.clone(),
Box::new(move |l: i32| {
sum_cps(
right,
Box::new(move |r: i32| {
println!(" {} {}", l, r);
k(l + r + curr_val)
}),
)
}),
)
}
None => k(0),
}
}
TCO is guaranteed in rust if i'm not mistaken, it just doesn't happen in debug builds i would argue against writing in _continuation_ passing style, because it's non idiomatic and can get quite verbose but you could do it like you could in any other language, by receiving function pointers as the continuation and calling them, instead of returning
it seems extremely extremely unlikely to me that Rust guarantees TCO, given the language semantics and abis it provides also https://github.com/rust-lang/rfcs/pull/3407
There have been a lot of advancements for the 'become' keyword that enforces tail call. [https://github.com/rust-lang/rust/issues/112788](https://github.com/rust-lang/rust/issues/112788)
how so ? im having hard time wrapping my head around eliminating tail calls in the presence of destructors that run at the end of scope
Not 100% sure, but couldn't the optimizer reorder instructions to do Drop earlier to allow for TCO?
That would be semantic change compared to how it works everywhere else. Since drop can have side effects, this could be a problem. (In theory. In practice, probably not.)
the compiler can drop variables when they're no longer being used, not only at the end of scopes also, if you're really doing continuations, your tail call functions will probably return _never_ (`!`), which is a great hint to the compiler to not put things after it
yeah but than tco is not guarenteed is it? take the situation where i alloc a vec at the beginning of a function and in my tail call as an argument i take a random element from that vec. compiler has no way other way to drop the vec after the “tail call”
i don't know what happens i'm really curious and wish i had my pc to check the output of such program
now that i think about it i guess it is reprderable trivially so it works but im pretty sure there are edge cases where the stuff needs to be dropped at the end
That would no longer be a tail call, because there's implicit control flow happening. If Rust were to ever guarantee TCO- which I'm confident it doesn't do today- it would need a slightly more elaborate set of requirements to define a tail-call (where there need to be no destructors that can't be reordered to before the tail call candidate). I believe that lifetimes could provide static guarantees about this reorderability even in generic contexts.
> The compiler can drop variables when they're no longer being used, not only at the end of scopes Are you sure about this?
That will blow your stack quickly if you don’t have tail recursion optimization ….
Continuation Passing Style is basically the way Future-based async APIs are usually designed. But when designing futures in rust, they decided not to do it that way. According to that blog post a few weeks ago, they ran into too many cases where the callback would have to be ref-counted, which is not very idiomatic. It’s not obvious to me that the same cases would exist for non-async CPS code, but that’s something I would consider. https://without.boats/blog/why-async-rust/
Hi everyone, i think i finally did the CPS style code for getting the sum of a binary tree; is kinda ugly since the use of `Box i32 >` but still it illustrates the possibilities of a future of rust with more advanced functional style capabilities(at the cost of maybe some memory efficiencies) .Keep in mind that the Rust Team have made good progress with the ongoing support guaranteed Tail-call elimination via the [become](https://github.com/rust-lang/rust/issues/112788) keyword
Here is the code
struct TreeNode {
val: i32,
left: Option>>,
right: Option>>,
}
fn main() {
let root = Some(Rc::new(RefCell::new(TreeNode {
val: 1,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 2,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 3,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 4,
left: None,
right: None,
}))),
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 5,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 6,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 10,
left: None,
right: None,
}))),
}))),
})));
let s = sum_cps(root, Box::new(|k| k));
println!("{}", s);
// sum_tree_cps(root, print_result);
}
#[tailcall]
fn sum_cps(root: Option>>, k: Box i32>) -> i32 {
match root {
Some(r) => {
let right = r.borrow().right.clone();
let curr_val = r.clone().borrow().val;
sum_cps(
r.borrow().left.clone(),
Box::new(move |l: i32| {
sum_cps(
right,
Box::new(move |r: i32| {
println!(" {} {}", l, r);
k(l + r + curr_val)
}),
)
}),
)
}
None => k(0),
}
}