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

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 ...


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 ...


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 ...


5

Not the first, but important so far as the practical application is concerned: "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" by John McCarthy (in which he introduced Lisp)


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

Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime? Yes. Note that if a tally language has “recursive algorithm” with polynomial “recursive runtime,” then it is in P. There is a tally language in E∖P by a standard diagonalization argument. Is there a problem which can be solved in time $f(n)$, ...


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 ...


3

All you really need is the definition of the untyped $\lambda$-calculus, which you can find in numerous places. Everything else follows from that.


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, ...


2

There's a good chance this question is independent of ZFC for most programming languages. In particular, I'd expect it to be true of any language where the shortest Quine is longer than the Kolmogorov complexity decidability bound, the integer $n$ such that no string can be proven to have Kolmogorov complexity $> n$. I don't know to prove this, since ...


1

A super quine exists in any language where some n-quines exist: just take the smallest program among all n-quines. I guess you wanted to ask another question. a k-quine is also always a (kn)-quine for any $n$, so the smallest super quine is a super n-quine for infinitely many n in any "acceptable programming language" we can prove that for all n, there ...


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