4 ms·

There's no clear value proposition given. What are we sacrificing Turing-completeness in order to gain? For example, one thing a programming language might ga

There's no clear value proposition given. What are we sacrificing Turing-completeness in order to gain? For example, one thing a programming language might gain by sacrificing Turing-completeness is that every program provably halts; no infinite loops! This is called "total function programming." There are probably other interesting properties you can gain by sacrificing Turing-completeness as well. Crema can restrict the computational complexity of the program to the minimum needed to improve security "Computational complexity" is a technical term that is related to performance, but not security.

sirseal 11y ago
From the Crema wiki that I just glanced at, it is indeed not possible to write infinite loops: "The only type of loop supported by Crema is the foreach loop. This loop is used to sequentially iterate over each element of a list. Crema specifically does not support other common loops (such as while or for loops) so that Crema programs are forced to operate in sub-Turing Complete space. In other words, foreach loops always have a defined upper bound on the number of iterations possible during the loop's execution. This makes it impossible to write a loop that could execute for an arbitrary length of time."
samuell 11y ago
Well, from my understanding, I would say "security" is a very broad term, being influenced by a broad range of factors including "computational complexity", don't you think?
GFK_of_xmaspast 11y ago
If all you're doing is sacrificing the possibility for infinite loops, just hack a c++ runtime that kills a process after 24 hours, and blammo non-Turing complete.
DenisM 11y ago
This is called "total function programming." Thanks for bringing it up, I was not aware of this: https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming Recently I had a need to design a small language for a constrained environment, and I spent a bit of time worrying about termination problem. Now I know where to look for more research.
otabdeveloper 11y ago
> There are probably other interesting properties you can gain by sacrificing Turing-completeness as well. Not the author, but I wrote another sub-Turing language. In my opinion, there's two useful properties: a) type inference -- you can infer the type of the whole program b) you can infer memory use and thus avoid the need for garbage collection or manual memory management. Both properties are very useful for performance, of course. :)
- Ono-Sendai 11y ago
  Hi, I'm writing a total functional language as well. I think that garbage collection is still useful however, as it can collect garbage as the program runs, not just at the end.
  - otabdeveloper 11y ago
    I've managed to make it so my memory use is completely deterministic -- no garbage at all.
    - Ono-Sendai 11y ago
      That sounds interesting. Any references or notes on that I can read? (or source code :) ) I would say that just because your memory use is deterministic, doesn't mean you don't get garbage. Garbage is just memory that isn't needed any more. for example, in let a = f(x) b = g(y) in a + b If there is working memory used in the body of f(), it will be garbage when f() has finished executing, because it won't be referred to any more. So it could be freed after f is executed and before g is executed, which may reduce the maximum amount of memory required by the program.

sirseal 11y ago

From the Crema wiki that I just glanced at, it is indeed not possible to write infinite loops: "The only type of loop supported by Crema is the foreach loop. This loop is used to sequentially iterate over each element of a list. Crema specifically does not support other common loops (such as while or for loops) so that Crema programs are forced to operate in sub-Turing Complete space. In other words, foreach loops always have a defined upper bound on the number of iterations possible during the loop's execution. This makes it impossible to write a loop that could execute for an arbitrary length of time."

samuell 11y ago

Well, from my understanding, I would say "security" is a very broad term, being influenced by a broad range of factors including "computational complexity", don't you think?

GFK_of_xmaspast 11y ago

If all you're doing is sacrificing the possibility for infinite loops, just hack a c++ runtime that kills a process after 24 hours, and blammo non-Turing complete.

DenisM 11y ago

This is called "total function programming." Thanks for bringing it up, I was not aware of this: https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming Recently I had a need to design a small language for a constrained environment, and I spent a bit of time worrying about termination problem. Now I know where to look for more research.

otabdeveloper 11y ago

> There are probably other interesting properties you can gain by sacrificing Turing-completeness as well. Not the author, but I wrote another sub-Turing language. In my opinion, there's two useful properties: a) type inference -- you can infer the type of the whole program b) you can infer memory use and thus avoid the need for garbage collection or manual memory management. Both properties are very useful for performance, of course. :)

Ono-Sendai 11y ago
Hi, I'm writing a total functional language as well. I think that garbage collection is still useful however, as it can collect garbage as the program runs, not just at the end.
- otabdeveloper 11y ago
  I've managed to make it so my memory use is completely deterministic -- no garbage at all.
  - Ono-Sendai 11y ago
    That sounds interesting. Any references or notes on that I can read? (or source code :) ) I would say that just because your memory use is deterministic, doesn't mean you don't get garbage. Garbage is just memory that isn't needed any more. for example, in let a = f(x) b = g(y) in a + b If there is working memory used in the body of f(), it will be garbage when f() has finished executing, because it won't be referred to any more. So it could be freed after f is executed and before g is executed, which may reduce the maximum amount of memory required by the program.