Language Design and Theory of Computation

Undecidable Parsing

Deciding whether to print "syntax error" shouldn't require simulating a Turing machine.

• Parsing Bash is Undecidable
  • Bash, Perl, and Make can't be statically parsed because they interleave parsing and execution.
  • C++ can't be statically parsed because it has two Turing complete computation mechanisms -- the templates at compile times and normal code at runtime -- and parsing sits in between them.

Accidentally Turing Complete

• Shell wasn't Turing complete when first designed.

• Make wasn't Turing complete when first designed. See Example Code in Shell, Awk, and Make.

  • makelisp

• sedlisp is proof that sed is Turing complete. Not sure what constructs are used.

• Accidentally Turing Complete -- nice comprehensive list, including some games which we don't care about here

  • SQL
    • However, with the features Common Table Expressions and Windowing, SQL is Turing Complete.
    • https://wiki.postgresql.org/wiki/Cyclic_Tag_System
  • Apache rewrite rules
  • sendmail
  • MediaWiki templates

• What about TeX and PostScript? I suspect those were both intended to be Turing Complete, although the syntax is odd.

• CSS3 proven to be Turing Complete --

  • https://github.com/elitheeli/stupid-machines
  • http://eli.fox-epste.in/rule110/

• printf is Turing complete. %n specifier writes to memory?

  • printbf -- Brainfuck interpreter in printf
  • Section 6.2.1 of http://nebelwelt.net/publications/files/15SEC.pdf

  When we control the arguments to printf(), it is possible to obtain Turing-complete computation. We show this formally in Appendix B by giving calls to printf() which create logic gates.

• x86 MMU Fault Handling

  • trapcc -- Compute with 0 instructions on Intel!

  This is a proof by construction that the Intel MMU's fault handling mechanism is Turing complete. We have constructed an assembler that translates 'Move, Branch if Zero, Decrement' instructions to C source that sets up various processor control tables. After this code has executed, the CPU computes by attempting to fault without ever executing a single instruction.

Context-Free Grammars are not Powerful Enough in Practice

Humans are better than computers at parsing programming languages.

To-do: collect instances of people arguing for grammars . For tools, IDEs?

• Nice series by Trevor Jim
  • Python is not context-free? by Trevor Jim
    • https://news.ycombinator.com/item?id=5184022
  • Is Java context-free? by Trevor Jim.
    • two grammars is a sign that context-free
  • about 4 or 5 other posts
• The Context-Sensitivity of C's Grammar
  • Revisited
• CoffeeScript video: "Rise of Transpilers": "cheating"
• Perl/C++/Make : not really on the table because they're not statically parseable.
• Ruby: experience with writing a full Ruby parser in Ruby https://news.ycombinator.com/item?id=13041646

GLR: Pure Declarative Syntax Lost and Regained.

Langsec: this is a different issue.

TODO:

Sweet spot : Turing complete , linear time , and statically parse able

Lexing and Parsing should be Separate.

PEGs combine them, only for reasons of presentation.

Had this discussion twice: at work about GLR, and maybe about Gazelle. And on HN: https://news.ycombinator.com/item?id=13042835

Related Issues

• Turing completeness vs. side effects/capabilities. Both of these are design issues and shouldn't be conflated.
• Whether there is abstraction power like functions. I think Awk was Turing complete at first, but it didn't have functions. Related lobsters thread.