Hacker News new | ask | show | jobs
by qsort 1872 days ago
We are doing this already.

- Configuration languages (JSON, YAML, XML) are pure combinatorial logic.

- Regular expressions are... mostly not actually regular, but you get the idea.

- Some templating languages are deliberately less powerful than Turing machines, e.g. ST4 is context-free.

- Prepared SQL statements are a similar idea on a different axis.

The real question is whether a non-TC language could be useful for general purpose programming. Such a language might come with very strong guarantees (termination, time complexity, even correctness or a limited form of correctness), but they might be extra-cumbersome for 'normal' workloads.
1 comments
ludamad 1872 days ago
A non-TC language can be achieved just by forcing proofs. Oh, you want that program to run? Just prove that it is bounded memory and can't halt, etc
link
qsort 1872 days ago
Yeah, but that's the 'cumbersome' part. Could we imagine a non-TC language with simple syntax that's suitable for at least some of the task you'd use a TC language for?
link
magmastonealex 1872 days ago
C compiled down to eBPF (as implemented with the Linux kernel) is not turing-complete. eBPF has a wide variety of uses from network filtering to hooking into certain syscalls.

The bytecode is theoretically turing-complete, but the verifier present in the kernel ensures that the code contains no loops and accesses no out-of-bounds memory.

With `clang`, you can compile C down to eBPF bytecode. It's a subset of C, with a lot of restrictions, but it is familiar and capable of some remarkable things past just simple packet parsing & filtering.

link
qsort 1872 days ago
I had no idea, this is fascinating. Thanks for sharing.
link
UncleMeat 1872 days ago
A useful subset of SQL is not turing-complete and is suitable for meaningful computational tasks. Datalog is also not turing-complete and is similarly useful.
link
qsort 1872 days ago
Sure, more examples are CSP solvers and AMPL. They are all somewhat specific though. I was wondering if it would be possible to make one that's "general purpose" in the same sense you call programming languages "general purpose", i.e. one you'd write application software in.
link
UncleMeat 1872 days ago
Datalog would be the closest I can think of. A bunch of static analysis engines are implemented in it.
link