Hot answers tagged

18

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/


14

I think you are asking about two different things. The ability of a programming language to represent all its programs as data. Reasoning about programs as data. For analytical purposes it's useful to keep them apart. I will focus on the former. The ability of a programming languages to represent, manipulate (and run) its programs as data goes ...


12

The answer is no, there is no exponential bound on PR. PR contains Knuth's up-arrow functions, Elementary functions, etc. PR is equal to the union of Grzegorczyk hierarchy. Exponential functions appear at the third level of the Grzegorczyk hierarchy. PR can alternatively be defined using the iteration function in place of recursion. A good reference for ...


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

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


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} \ ⋃p ∈ S { p q : q ∈ N, q ≥ p } The following code is stuck, reflecting the above definition more or less verbatim: primes = gaps 2 $ foldr (\p r-> ...


6

No there is no current system that does all four steps in your system. If you want to design a system one of the first requirements is homoiconic language. At minimum you would want your core programming language that you have as small as possible so that when you enter the system and start to make it interpret itself it will work. So therefore you want a ...


6

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


6

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)


6

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


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


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


4

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


4

As @user217281728's answer mentions there are a type of machines related more to inference and AI, called Gödel Machines A Gödel machine is a self-improving computer program invented by Jürgen Schmidhuber that solves problems in an optimal way. It uses a recursive self-improvement protocol in which it rewrites its own code when it can prove the new ...


3

This paper by Jurgen Schmidthuber might be of interest: http://arxiv.org/pdf/cs/0309048.pdf


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

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

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


2

From Recursive Functions article on SEP: The use of recursion goes back to the 19th century. Dedekind [1888] used the notion to obtain functions needed in his formal analysis of the concept of natural number. In logic, recursion appears in Skolem [1923], where it is noted that many basic functions can be defined by simple applications of the method. The ...


2

Maybe slightly tangential to the original question, but the blog entry "How recursion got into programming: a comedy of errors" describes an interesting part of early computing history.


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

It is $n^{\Theta(\log n)}$, although I'm not sure exactly what the constant in the theta is. For the upper bound (the one you already have), note that, even without the $n^2$ term but with a base case of $1$ rather than $0$, this recurrence is dominated term-by-term by the recurrence $$U(n)=nU(\frac{n}{2}).$$ For the lower bound, note that it dominates the ...


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


1

I do not know when it came up, but the recursive solution for Towers of Hanoi is frequently used as introductory example. The problem originated before formal approaches on computation.



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