But you also might choose to provide some sort of guarantees about execution time, and that’s really hard. The two approaches work. One is to make sure that processing is obviously linear.
As we know from the PRF exercise, this won’t actually prevent people from writing arbitrary recursive programs. It’ll just require some roundabout code to do that. But maybe that’ll be enough of a speedbump to make someone invent a simple solution, instead of brute-forcing the most obvious one?
Do not use recursion to ensure that all executions that should be bounded are bounded. […]
Put a limit on everything because, in reality, this is what we expect—everything has a limit. For example, all loops and all queues must have a fixed upper bound to prevent infinite loops or tail latency spikes. This follows the “fail-fast” principle so that violations are detected sooner rather than later. Where a loop cannot terminate (e.g. an event loop), this must be asserted.
I see only allowing primitive (or more accurately structural) recursion as the language designers way of helping the user do the sensible thing. Writing an infinite loop sometimes happens by mistake, unlike using foreach <really large number> to effectively get a while loop (that’s a conscious choice).
In my opinion general recursion is an effect, it doesn’t belong in a pure language. When used it should be made explict via some effect system (to other humans and to the machine).
I am a CUE developer. CUE is primitive recursive. It also happens to fulfill the desired criteria for a “good” configuration language exposed in the article.
So, an equivalent-in-power definition would be to say that an TM is an FSM endowed with two stacks.
This of course creates an obvious question: is an FSM with just one stack a thing? Yes! It would be called a pushdown automaton, and it would correspond to context-free languages.
How many stacks do context-sensitive languages require?
Context-sensitive in a sense of Chomsky hierarchy? That is, the one where we require that rhs of a rewrite rule is longer than lhs (and so brute force search works)?
Strictly more than one (as this is a wider class than CFGs) but strictly less than two (as it isn’t quiet Turing machine yet. In particular, it is still decidable)
You wrote in the article that pushdown automaton is FSM with one stack, and that pushdown automatons can distinguish context-free languages. This is not true. FSMs with one stack are deterministic pushdown automatons, but context-free languages can be recognized by non-deterministic pushdown automatons. https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars
Thanks! This is confusing terminology, but unqualified PDA is often taken to mean the non-deterministic one. I’ll update to less confusing terminology though!
This is a good point because, in terms of expresssive power, non-determinism is equivalent to determinism below (FSM) and above (TM), but is actually a meaningful difference in the middle!
In case anyone’s curious, Martin Hofmann’s paper Linear types and non-size-increasing polynomial time computation (1999) explains how to do this.
Quoting from
TIGER_STYLE.md:I see only allowing primitive (or more accurately structural) recursion as the language designers way of helping the user do the sensible thing. Writing an infinite loop sometimes happens by mistake, unlike using
foreach <really large number>to effectively get a while loop (that’s a conscious choice).In my opinion general recursion is an effect, it doesn’t belong in a pure language. When used it should be made explict via some effect system (to other humans and to the machine).
Thanks! As embarrassing as it is, I didn’t make this connection!
I am a CUE developer. CUE is primitive recursive. It also happens to fulfill the desired criteria for a “good” configuration language exposed in the article.
For fun, here is CUE simulating an arbitrary but finite number of steps of Rule 110[0]: https://cuelang.org/play/?id=Ityqia88Mvq#w=function&i=cue&f=export&o=cue
[0] https://en.wikipedia.org/wiki/Rule_110
That’s a very nice observation.
That was an interesting read, thanks to the author of the post.
How many stacks do context-sensitive languages require?
I really wanted to read that discussion…
Context-sensitive in a sense of Chomsky hierarchy? That is, the one where we require that rhs of a rewrite rule is longer than lhs (and so brute force search works)?
Strictly more than one (as this is a wider class than CFGs) but strictly less than two (as it isn’t quiet Turing machine yet. In particular, it is still decidable)
You wrote in the article that pushdown automaton is FSM with one stack, and that pushdown automatons can distinguish context-free languages. This is not true. FSMs with one stack are deterministic pushdown automatons, but context-free languages can be recognized by non-deterministic pushdown automatons. https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars
Thanks! This is confusing terminology, but unqualified PDA is often taken to mean the non-deterministic one. I’ll update to less confusing terminology though!
This is a good point because, in terms of expresssive power, non-determinism is equivalent to determinism below (FSM) and above (TM), but is actually a meaningful difference in the middle!