Questions tagged [tail-call-optimization]
A tail-call optimization is when a function returns directly the result of a called function, to avoid allocating a new stack frame. It is especially useful in recursive functions.
170
questions
0
votes
0
answers
30
views
Tail call optimization for procs possible?
I see that tail call optimization can be enabled in ruby and that it works with method calls following these instructions, but I need it to work for Procs too for use with blocks/lambdas, since only ...
1
vote
1
answer
103
views
Converting a simple recursive haskell function to be tail recursive
2 weeks new to haskell and functional programming. In the process of covering foldl and foldr in class, I found that I was quite new to tail recursion and never actually tried writing a tail recursive ...
1
vote
0
answers
82
views
Tail-calls corrupted when compiled with __attribute__((musttail))
I was working a Lisp interpreter with a 'threaded' design, where it compiles to a VM where each instruction is a C function that calls the next instruction — if the compiler does tail call elimination,...
0
votes
1
answer
55
views
Why does clang have trouble with optimizing tail calls in destructors?
Here is a simplified singly-linked list, where each node owns the next, along with a function for destroying the list:
struct Node {
Node* next = nullptr;
~Node() {
delete next;
}
};
void ...
10
votes
2
answers
286
views
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(...
0
votes
1
answer
65
views
Tail call stack
I'm having trouble understanding the Stack manipulation needed in order to implement Tail call in assembly language.
When we have a Tail call to function We basically want to override the current ...
1
vote
2
answers
73
views
Question regarding tail call optimization
As far as I know, there is a prerequisite for performing tail call optimization is that the recursion point should be the last sentence in the function, and the result of the recursive call should be ...
0
votes
1
answer
87
views
Tail call optimization with eigen
I'm trying to make the compiler tail-call optimize eigen-expressions that are passed recursively. The following will optimize using GCC -O2:
inline double recursive(const double &A,
...
1
vote
0
answers
38
views
JavaScript: how do I improve this repeat function using tail call optimization
Here is a repeat function that recursively calls itself
const repeat = x => f => {
if (x > 0) {
f()
return repeat (x - 1) (f)
}
}
The problem with it is it can ...
1
vote
1
answer
213
views
Are tail calls on diverging functions optimized in Rust?
If I have the following functions:
fn a() -> ! {
b()
}
fn b() -> ! {
loop {}
}
Does Rust optimize such calls to simple jumps?
I have looked at a Playground to show the assembly, but a ...
-2
votes
1
answer
69
views
Why is this tail-call optimized method not recognized as such by the Scala compiler?
This simple regex implementation (scastie here) does not compile, where I expected it to. The error is at line 14, where an intermediate recursive call is interpreted as to break the @tailrec ...
0
votes
1
answer
62
views
print a newline using tail call optimization
There's this unanswered question in the Igor Zhirkov's book Low-Level Programming :
"Try to rewrite print_newline without calling print_char or copying its code. Hint: read
about tail call ...
3
votes
1
answer
171
views
Why does non-trivial destructor of return type prevent tail-call optimization?
Currently, in C++ compilers one of the rules for tail-call optimization is that the return type must be trivially destructible. (Based on analyzing GCC, Clang trunk behavior. MSVC has troubles with ...
1
vote
3
answers
140
views
How I could use tail call optimisation on this combination function?
My exercise, that you can see here, says that I need to
implement a recursive version of C(n, k).
That's my solution:
module LE1.Recursao.Combinacao where
combina :: Integral a => a -> a -> ...
2
votes
0
answers
148
views
Tail call optimization in ifort vs gfortran
I have some code that when is compiled with gfortran, a tail call optimization is done, but when compiled with ifort, it isn't.
Here are some very simple snips describing the issue:
gfortran
ifort
...
1
vote
1
answer
199
views
Is there a way to optimize tail calls in Scala?
I am aware that Scala has optimizations for tail-recursive functions (i.e. those functions in which the recursive call is the last thing executed by the function). What I am asking here is whether ...
0
votes
2
answers
67
views
Can JavaScript function call subexpressions be tail calls?
Consider the following return statement:
return f() || g();
The call f() obviously is not a tail call, because the function does not actually return if f() is falsy.
What about the g() part though, ...
5
votes
2
answers
209
views
Will this be tail call optimized in SWI-Prolog
step_n(0, I, I).
step_n(N, In, Out) :-
N > 0, plus(N1, 1, N), phase_step(In, T),
step_n(N1, T, Out).
phase_step is a function that transforms data.
Will this step_n run in almost the same ...
2
votes
1
answer
197
views
How to convert a variation of ackermann function to support tail call?
I'm currently solving a problem which is to implement a variation of ackermann function in scala with tail call optimization support so that the stack does not overflow.
The problem is, I cannot find ...
1
vote
3
answers
286
views
Scheme: Iterative process to reconstruct a list in original order?
My question is: how to write a procedure that utilises tailcall, and that constructs a list not in the reverse order.
To show what I mean, here is an example of a very simple procedure that is ...
2
votes
1
answer
276
views
Why does this kind of tail call of fibonacci run faster than pure tree recursion in Haskell?
I'm trying to undestand tail call recursions. I convert pure tree-recursion fibonacci function:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
to a tail call version:
fib' 0 a = a
fib' 1 a = 1 + ...
0
votes
2
answers
170
views
Get results for sub problems using tail call recursion in Scala
I am trying to calculate results for each sub problem using @tailrec
similar to how normal recursive solutions can produce solutions for each sub problem.
Following is the example I worked on.
@...
0
votes
1
answer
571
views
Telling GCC to tail-call a function
Let's say I've got a C function:
unsigned int fact(unsigned int n, unsigned int acc) {
if(n > 0) return fact(n - 1, n * acc);
return acc;
}
Is there a way to tell GCC to tail call the ...
2
votes
0
answers
454
views
Use of thunks, trampolines and continuation passing in python
I came to know about the concept of Tail Call Optimization(TCO) from this blog: Sing Me A Song of Stack Overflow: A Musical Tail Call Optimization.
Going into this concept(or "feature" or "...
2
votes
0
answers
1k
views
Why is my tail call-optimized implementation faster than the normal recursive if it's not supported in c#?
I recently got introduced to the concept of tail-call optimization and as far as I can read it's not inherently supported in the .NET compiler but there is a workaround called "Trampolining" which I'...
2
votes
2
answers
280
views
Erlang, Last Call Optimization, lambda functions, and how to prevent growing a stack
I'm writing some Erlang code, and I've run into a bizarre situation that I don't understand.
The code:
-module(recursive_test).
-export([a/2]).
a(_, []) -> ok;
a(Args, [H|T]) ->
F = fun() ...
3
votes
2
answers
183
views
Do bound functions support proper tail calls in ES6?
In the ECMAScript 2015 Language Specification, the definitions of Function.prototype.apply and Function.prototype.call both include "Perform PrepareForTailCall()" as one of their steps, so we know ...
3
votes
1
answer
121
views
Tail recursion [C]
The question in my book is "Which of the recursive calls (not functions!) are tail recursive?"
unsigned f(unsigned x)
{
if(x==0) return 1;
else if(x==1) return f(x-1);
else return 3*x ...
3
votes
1
answer
148
views
Compiler Friendly Tail Recursion + Tail Recursion Checking in ATS
What is the best way to check that a function has been tail call optimized in ATS? (So far I have been running "top" to see if memory usage is constant)
As a follow up: Say you have a complex tail-...
0
votes
1
answer
437
views
How can I tell if my function has been tail call optimized?
I'm reading section 2.8 (Tail Recursion) in On Lisp. It has an example of a tail recursive function:
(defun our-length-tr (lst)
"tail recursive version with accumulator"
(labels ((rec (lst acc)
...
1
vote
3
answers
90
views
how to insert in the middle of a list, being tail-call friendly but without hurting performance?
So I have this function which seems to be non-tail-call friendly, right?
let rec insertFooInProperPosition (foo: Foo) (bar: list<Foo>): list<Foo> =
match bar with
| [] -> [ foo ...
1
vote
2
answers
916
views
tail rec kotlin list
I'm trying to do some operations that would cause a StackOverflow in Kotlin just now.
Knowing that, I remembered that Kotlin has support for tailrec functions, so I tried to do:
private tailrec fun ...
6
votes
1
answer
268
views
Why does gcc perform tail call optimization for one version but not for the other?
Experimenting with tail call optimization (tco), I stumbled upon the following curious example:
unsigned long long int fac1(unsigned long long int n){
if (n==0)
return 1;
return n*fac1(n-1);
}...
6
votes
1
answer
1k
views
Elixir tail-call recursive function
I have this function that finds the even numbers in a list and returns a new list with only those numbers:
def even([]), do: []
def even([head | tail]) when rem(head, 2) == 0 do
[head | ...
5
votes
1
answer
83
views
Is there a tco pattern with two accumulating variables?
Just for fun (Project Euler #65) I want to implement the formula
n_k = a_k*n_k-1 + n_k-2
in an efficient way. a_k is either 1 or (* 2 (/ k 3)), depending on k.
I started with a recursive solution:
...
63
votes
5
answers
33k
views
How do I replace while loops with a functional programming alternative without tail call optimization?
I am experimenting with a more functional style in my JavaScript; therefore, I have replaced for loops with utility functions such as map and reduce. However, I have not found a functional ...
0
votes
1
answer
98
views
Is continuation style implementation of factorial tail call optimized (TCO)?
Here are two factorial implementation from this site:
Tail Call Optimized (TCO):
function fact(n) {
return tail_fact(n,1) ;
}
function tail_fact(n,a) {
if (n == 0)
return a ;
else
...
4
votes
1
answer
567
views
How 'smart' is GCC's Tail-Call-Optimisation?
I just had a discussion where the following two peices of C code were being discussed:
For-Loop:
#include <stdio.h>
#define n (196607)
int main() {
long loop;
int count=0;
for (loop=0;...
4
votes
3
answers
2k
views
Tail recursion in NodeJS
So I recently came across case I needed to write code where callback calls itself and so on and wondered about NodeJS and tail-call support, so I found this answer https://stackoverflow.com/a/30369729 ...
12
votes
1
answer
423
views
Why is tail call optimization not occurring here?
We are using recursion to find factors and are receiving a StackOverflow exception. We've read that the C# compiler on x64 computers performs tail call optimizations:
JIT definitely does tailcals ...
2
votes
0
answers
113
views
Does Gforth optimize proper tail calls?
I have the following (somewhat inefficient) code:
\ RNG support
VARIABLE seed
: rand ( -- random )
seed @
DUP 13 LSHIFT XOR
DUP 17 RSHIFT XOR
DUP 5 LSHIFT XOR
DUP seed ! ;
\ Checker for number of ...
2
votes
1
answer
211
views
Prolog Tail call optimization for flattening a tree
I want to flatten a tree in prolog using tail recursion.I have done it with append list with recursive calls. I want to optimize my version. This is my function which uses recursive call.I want to ...
3
votes
3
answers
411
views
At which stage should I implement tail call optimization for my compiler
I wrote a small compiler in Racket for a scheme-like language. Now I want to implement TCO for my compiler.
My idea is: I need to detect tail calls before transform them into intermedia ...
1
vote
3
answers
313
views
Using Default Optional argument and recur together in Clojure
I am able to set a default argument and do a regular recursion with it, but for some reason I cannot do with recur for tail optimization... I keep getting an java.lang.UnsupportedOperationException: ...
0
votes
1
answer
291
views
Haskell: TCO and Lazy evaluation
I'm trying to understand why the first main does not terminate when c is not valid, while the second terminates. From the description here
main is just an unevaluated thunk, and executing it is just ...
1
vote
1
answer
570
views
Disable tail calls to a function in Visual Studio
How can I disable tail calls to a specific function in Visual Studio?
The reason I need this is because I have a function that breaks to the debugger that I use when an error occurs and I need to see ...
3
votes
1
answer
62
views
What reasoning lead to `Sequence expression containing recursive definition is compiled incorrectly`
The question Stack overflow despite tail call position but only in 64-bit lead to uncovering a bug in the F# compiler.
After reading the answer I am curious as to the reasoning that lead to finding ...
17
votes
1
answer
316
views
Can/does the (forward) pipe operator prevent tail call optimization?
For a parameter optimization problem at work I wrote a genetic algorithm to find some good settings because a brute-force solution is unfeasible. Unfortunately, when I return in the morning, most of ...
1
vote
0
answers
312
views
Octave/Matlab - tail call optimization for tail recursive lambda function
I am trying to write recursive anonymous function, so far what works for me is to use the Y combinator.
%{ Call lambda function with any number of arguments. %}
call_ = @feval;
%{ Internal ...
6
votes
2
answers
2k
views
What is the difference between loop/recur and recur by itself?
I'm having trouble finding the answer to this in the Clojure docs. I'm new to Clojure and it seems as though you can use recur in two different ways and essentially get the same result.
Example 1:
(...