3 ms·

None of those listed are programming languages. They are data formats. They perform no computation. Calling them Turing-complete or Turing-incomplete is meaning

None of those listed are programming languages. They are data formats. They perform no computation. Calling them Turing-complete or Turing-incomplete is meaningless.

baq 6y ago
yes, hence the jinja2 comment.
btilly 6y ago
They are all data formats that are used for configuration. Configuration systems tend to sprout macro systems of various kinds. So you're writing in JSON, but it is fed into a macro system and voila! You have a programming language. The progression from data format to custom programming language is surprisingly short. And sometimes the transition is unexpected. For example https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html https://beza1e1.tuxen.de/articles/accidentally_turing_comple... includes as an example of a Turing complete language, HTML+CSS!
- phoe-krk 6y ago
  I'm aware of the distinction. Data syntax from data formats is sometimes used directly for programming languages, too; the path from S-expressions to Lisp is very short, too, and I write that as a lisper. A very relevant recent article is https://news.ycombinator.com/item?id=24892297 https://news.ycombinator.com/item?id=24892297 The point is that when we are talking about "JSON, but with macros" we already have a programming language in play, not merely just a data format. This is because macros are functions from text into text, or from data into data, and these functions require to be written in some sort of actual programming language. At this point the data format becomes an extension of this programming language, either some sort of input for functions in this programming language or another means of expressiong this language's syntax.
a1369209993 6y ago
Actually they do perform (drastically cutailed) computation; for example INI performs computations of the form: [foo] # section = "foo" bar=baz # table[section]["bar"] = "baz" Similarly, wc is a programming language with ~4 operations: 'a' # inc byte counter, add word flag to word counter, clear word flag # any other non-space/newline is the same as 'a' ' ' # inc byte counter, mark word flag \n # inc byte counter, mark word flag, inc line counter EOF # (implied) print counters That set of operations is of extremely limited usefulness, but that's more or less true of any non-turing-complete language (and many that are turing-complete, even).
- deleted 6y ago
  [deleted]
- goto11 6y ago
  INI does not perform any computations, it is a file format without any execution model defined. What you describe is a possible execution model by an INI parser, but an INI parser is not required to do that.
  - baq 6y ago
    this point is dangerous - the same logic can be applied to C code or any other programming language. source files only encode the AST, after all. it's the compiler/interpreter doing the actual work. it just so happens that the INI interpreter doesn't usually do much else than load the list of key value maps - and that's the problem - people extend INI source files in a different language which can do more.
    - goto11 6y ago
      No, a programming language like C have both a syntax and an execution model. In Turing-machine terminology, it has a set of symbols and rules for processing the symbols. This is why you can reason about things like the halting-problem. If you only have a set of symbols but no rules for processing the symbols, you don't have a machine, and you cant meaningfully talk about "termination". INI does not have a defined execution model, so it is not a machine the way C is. A particular implementation could read the data into key-value maps but it is not required to. E.g. it could just search through the file for a specific key. Or it could do nothing.
samatman 6y ago
This is a dangerous misconception, which those of us in langsec have worked hard to dispel. Data is not inert. Trivially, yes, insofar as a .json file just sits there until you do something with it – but this is true of .js as well. Data in use is active, it is an input to your program which drives computation. This is the same as inputs which are Turing complete, just restricted in various ways. Being complacent about this fact is a great way to receive a malicious payload, which puts your program into an unexpected and exploitable state.
- phoe-krk 6y ago
  I agree with your statement even though it seems to completely miss the original point that I have made. Yes, you are correct, if you are running a suid binary and you specify / as a temporary directory instead of the default that looks like /tmp/foo-12345abcd/ in its configuration file, then the script may invalidly perform cleanup by deleting everything on the filesystem. But this does not suddenly mean that Unix pathnames are Turing-complete or Turing-incomplete or that Turing-completeness somehow applies to strings as data formats. It's not the path string that does the deletion. It's not the path string that was written in a programming language that performs the unlink() syscall. It's not the data itself that causes people to curse loudly. Sure, secure your data, validate your inputs, ensure that your code cannot be misused, just don't say that data, even when it is in use, performs some computation on its own.
  - samatman 6y ago
    I'm getting the sense that you're not quite picking up what I'm laying down here. Code also performs no computation on its own. A function with no parameters is just a complex constant. Computation is always the union of code and data. People can and do embed full programs in 'inert' formats like JSON, and write an interpreter for that program. This is a bad idea, and the notion that JSON is "just data" is exactly what fools people into writing such inner languages (implementing, of course, half of Common Lisp). Reducing the motivating examples (JSON, TOML, etc.) to path strings is a weak argument, because path strings are not strong enough to provide for such an inner platform, while the data formats under discussion are, it happens all the time. The very fact that I can point out that a path string is capable of driving less complex calculations than YAML is, points out that there is in fact a continuum from pure code to 'mere data' (a float, let's say), which undermines the argument that there is some strong distinction to be made here.

None of those listed are programming languages. They are data formats. They perform no computation. Calling them Turing-complete or Turing-incomplete is meaningless.

baq 6y ago

yes, hence the jinja2 comment.

btilly 6y ago

They are all data formats that are used for configuration. Configuration systems tend to sprout macro systems of various kinds. So you're writing in JSON, but it is fed into a macro system and voila! You have a programming language. The progression from data format to custom programming language is surprisingly short. And sometimes the transition is unexpected. For example https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html https://beza1e1.tuxen.de/articles/accidentally_turing_comple... includes as an example of a Turing complete language, HTML+CSS!

phoe-krk 6y ago
I'm aware of the distinction. Data syntax from data formats is sometimes used directly for programming languages, too; the path from S-expressions to Lisp is very short, too, and I write that as a lisper. A very relevant recent article is https://news.ycombinator.com/item?id=24892297 https://news.ycombinator.com/item?id=24892297 The point is that when we are talking about "JSON, but with macros" we already have a programming language in play, not merely just a data format. This is because macros are functions from text into text, or from data into data, and these functions require to be written in some sort of actual programming language. At this point the data format becomes an extension of this programming language, either some sort of input for functions in this programming language or another means of expressiong this language's syntax.

a1369209993 6y ago

Actually they do perform (drastically cutailed) computation; for example INI performs computations of the form: [foo] # section = "foo" bar=baz # table[section]["bar"] = "baz" Similarly, wc is a programming language with ~4 operations: 'a' # inc byte counter, add word flag to word counter, clear word flag # any other non-space/newline is the same as 'a' ' ' # inc byte counter, mark word flag \n # inc byte counter, mark word flag, inc line counter EOF # (implied) print counters That set of operations is of extremely limited usefulness, but that's more or less true of any non-turing-complete language (and many that are turing-complete, even).

deleted 6y ago
[deleted]
goto11 6y ago
INI does not perform any computations, it is a file format without any execution model defined. What you describe is a possible execution model by an INI parser, but an INI parser is not required to do that.
- baq 6y ago
  this point is dangerous - the same logic can be applied to C code or any other programming language. source files only encode the AST, after all. it's the compiler/interpreter doing the actual work. it just so happens that the INI interpreter doesn't usually do much else than load the list of key value maps - and that's the problem - people extend INI source files in a different language which can do more.
  - goto11 6y ago
    No, a programming language like C have both a syntax and an execution model. In Turing-machine terminology, it has a set of symbols and rules for processing the symbols. This is why you can reason about things like the halting-problem. If you only have a set of symbols but no rules for processing the symbols, you don't have a machine, and you cant meaningfully talk about "termination". INI does not have a defined execution model, so it is not a machine the way C is. A particular implementation could read the data into key-value maps but it is not required to. E.g. it could just search through the file for a specific key. Or it could do nothing.

samatman 6y ago

This is a dangerous misconception, which those of us in langsec have worked hard to dispel. Data is not inert. Trivially, yes, insofar as a .json file just sits there until you do something with it – but this is true of .js as well. Data in use is active, it is an input to your program which drives computation. This is the same as inputs which are Turing complete, just restricted in various ways. Being complacent about this fact is a great way to receive a malicious payload, which puts your program into an unexpected and exploitable state.

phoe-krk 6y ago
I agree with your statement even though it seems to completely miss the original point that I have made. Yes, you are correct, if you are running a suid binary and you specify / as a temporary directory instead of the default that looks like /tmp/foo-12345abcd/ in its configuration file, then the script may invalidly perform cleanup by deleting everything on the filesystem. But this does not suddenly mean that Unix pathnames are Turing-complete or Turing-incomplete or that Turing-completeness somehow applies to strings as data formats. It's not the path string that does the deletion. It's not the path string that was written in a programming language that performs the unlink() syscall. It's not the data itself that causes people to curse loudly. Sure, secure your data, validate your inputs, ensure that your code cannot be misused, just don't say that data, even when it is in use, performs some computation on its own.
- samatman 6y ago
  I'm getting the sense that you're not quite picking up what I'm laying down here. Code also performs no computation on its own. A function with no parameters is just a complex constant. Computation is always the union of code and data. People can and do embed full programs in 'inert' formats like JSON, and write an interpreter for that program. This is a bad idea, and the notion that JSON is "just data" is exactly what fools people into writing such inner languages (implementing, of course, half of Common Lisp). Reducing the motivating examples (JSON, TOML, etc.) to path strings is a weak argument, because path strings are not strong enough to provide for such an inner platform, while the data formats under discussion are, it happens all the time. The very fact that I can point out that a path string is capable of driving less complex calculations than YAML is, points out that there is in fact a continuum from pure code to 'mere data' (a float, let's say), which undermines the argument that there is some strong distinction to be made here.