Tag Info

Hot answers tagged

15

Computability and Recursion, by Soare. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf This paper is the first of the history of computation papers available here: http://www.people.cs.uchicago.edu/~soare/History/


10

Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?* Yes, it's possible to do things like this, but if you control the compiler, it's usually faster and easier to do something else. The main exception is when ...


8

If you want to include a fixpoint combinator in the language, you don't need to change anything to the syntax of types or the rules to type existing expressions. All it takes is adding one constant, a rule to type it and a rule to reduce expressions containing it: $$ \dfrac{}{\mathsf{fix} : (\tau \rightarrow \tau) \rightarrow \tau} \qquad \mathsf{fix} \, ...


8

You might want to look at the SECD machine. A functional language (though it could be any language) is translated into a series of instructions that manage things such as putting arguments of stacks, "invoking" new functions and so forth, all managed by a simple loop. Recursive calls are never actually invoked. Instead, the instructions of the body of the ...


8

Is memory usage for a tail call not constant and can you get a memory overflow? The stack usage for tail-recursive functions is bounded by a constant (i.e., is $O(1)$). However, you may still need to manipulate the stack at each recursive call in order to ensure that arguments are where the procedure expects them to be. Here's an example of such a ...


8

Yes, there are convincing reasons to believe that recursion can be turned into iteration. This is what every compiler does when it translates source code to machine language. For theory you should follow Dave Clarke's suggestions. If you would like to see actual code that converts recursion to non-recursive code, have a look at machine.ml in the MiniML ...


7

Productive here just means that it isn't stuck. An unorthodox (seemingly impredicative ) formulation of the sieve of Eratosthenes is       S = {n : n ∈ N, n > 1} \ Up ∈ S { pq : q ∈ N, q ≥ p } The following code is stuck, reflecting the above definition more or less verbatim: primes = gaps 2 $ foldr (\p r-> union ...


6

If I understand correctly, you are clear about converting functions that contain no other function calls but to themselves. So assume we have a "call chain" $F \to F_1 \to \dots \to F_n \to F$. If we furthermore assume that $F_1, \dots, F_n$ are not recursive themselves (because we have converted them already), we can inline all those calls into the ...


6

Q: "Is there really a more formal (convincing?) proof that recursion can be converted to iteration?" A: The Turing completeness of a Turing Machine :-) Jokes apart, the Turing equivalent Random Access stored program (RASP) machine model is close to how real microprocessors work and its instruction set contains only a conditional jump (no recursion). The ...


5

Is that the technical term referring to productive sets and creative sets, or is it just a manner of speaking? Neither, actually -- it's a different technical term. The type of streams of natural numbers can be interpreted as the final coalgebra for the functor $F(X) \triangleq \mathbb{N} \times X$. That is, define the category of $F$-algebras as ...


5

For linear recurrences, you may find interesting this recent work: Adrian Nistor, Wei-Ngan Chin, Tiow-Seng Tan, and Nicolae Tapus. 2009. Optimizing the parallel computation of linear recurrences using compact matrix representations. J. Parallel Distrib. Comput. 69, 4 (April 2009), 373-381. DOI=10.1016/j.jpdc.2009.01.004 ...


4

What Sam said. Also, it's really well under a page. If you're familiar with evaluation contexts, you can specify the call-by-value lambda calculus like this: Terms $$M ::= x \mid (M \, M) \mid (\lambda x . M)$$ Values $$V = (\lambda x . M)$$ Evaluation contexts $$E ::= [\:] \mid ([\:] M) | (V [\:])$$ The (only) reduction rule: $$E[((\lambda x . M) ...


3

A context-free grammar is cyclic if there exists a non-terminal $A$ and a derivation in one or more steps $A\Rightarrow^+ A$. It is left-recursive if there exists a non-terminal $A$, a mixed sequence of terminals and non-terminals $\gamma$, and a derivation in one or more steps $A\Rightarrow^+ A\gamma$. Hence cyclic implies left-recursive, but the converse ...


3

I think my comment was a little cryptic, so let me unpack. The key intuition behind hylomorphisms is that they let you reify the call graph as a data structure. You unfold a datastructure to build a representation of the call graph, and then you fold over the intermediate structure to consume and finish the computation. Lists are a little misleading, ...


3

I do not think that the part of Wikipedia you quoted is talking about space complexity. It simply states that unlike non-tail calls, tail calls do not have to store the return addresses in the stack. However, it is not correct to state that tail calls do not touch the stack at all, because you still have to clean up local variables allocated on the stack ...


1

If you're familiar with languages that support lambdas then one avenue is to look into the CPS transformation. Removing use of the call stack (and recursion in particular) is exactly what the CPS transformation does. It transforms a program containing procedure calls into a program with only tail calls (you can think of these as gotos, which is an iterative ...



Only top voted, non community-wiki answers of a minimum length are eligible