5 ms·

Lisp programmers realized in the 70s that having an artificial division between code and data was frequently problematic, hopefully other languages continue to

by thurn 6y ago

Lisp programmers realized in the 70s that having an artificial division between code and data was frequently problematic, hopefully other languages continue to catch on as well :)

kiwidrew 6y ago
On the other hand, it's often useful to have data and configuration files that aren't Turing complete, because then you can safely make assumptions about how much time and space is required to load/parse them. Unfortunately every configuration file format these days seems to add so many features that it inevitably becomes Turing-complete... the trick is finding the balance between expressiveness and halting decidability.
- tines 6y ago
  Lisp data aren't Turing complete, only a particular interpretation of them (i.e. EVAL), as you know. You're perfectly welcome to call READ on a file and you will get unevaluated lisp data back (particularly when you set READ-EVAL to NIL in common lisp).
  - fiddlerwoaroof 6y ago
    READ is Turing complete, because the reader can execute arbitrary code: the #. read macro alone is enough to ensure this.
    - dig1 6y ago
      If you set read-eval to false, it will not execute reader macro. [1] [1] http://www.lispworks.com/documentation/HyperSpec/Body/v_rd_eva.htm#STread-evalST http://www.lispworks.com/documentation/HyperSpec/Body/v_rd_e...
      - fiddlerwoaroof 6y ago
        Yeah, but I can use SET-MACRO-CHARACTER to define a version that ignores that variable: basically, you should never use CL:READ on untrusted input, unless you control the readtable.
- lmm 6y ago
  You might like to look into Dhall - a config language that has been careful to remain non-Turing-complete.
  - deleted 6y ago
    [deleted]
  - kiwidrew 6y ago
    Wow, cool, that is a really nifty language! I don't care for the syntax (at all) but I am seriously impressed by the careful design. I've always wondered where you'd need to draw the line between plaintext config files and executable code, and Dhall is much further into "programming language" territory than I would've expected. *Dhall homepage for anyone else that's interested - https://dhall-lang.org https://dhall-lang.org
- fit2rule 6y ago
  Why is configuration performance so important to the application? Sounds a bit like a missing specification for the distinction of load-time and run-time configuration. Configuration, to me, is something that happens once and not often, and is therefore "something = foo". Update is a run-time thing, and therefore "if something then bar". Lua covers both of those cases superlatively. Case A, byte code. Case B, same. Just be sure you have "generate byte code" in the right place, C, too ..
  - kiwidrew 6y ago
    Let's say you want the user of your service to be able to write and upload a configuration file, but you specifically don't want them to be able to execute arbitrary code on your server(s). It would be nice to be able to statically verify that their submitted configuration "behaves nicely", but the moment you introduce any kind of Turing-complete configuration language all guarantees go out the window because the problem becomes literally undecidable. [And then you try to mitigate it by imposing limits like "kill the parse process if it takes longer than X seconds or uses more than Y megabytes of memory".] The advantage of, say, a simple .INI file for configuration purposes is that the time required to parse it (and storage space required to remember what's in it) is O(n) where n=size of config file... EDIT: so take the example Lua file from the original post but change the loop limits from "32" to "16777216": for i = 0, 16777216 do for j = 0, 1677216 do add_body({x = 20 * i, y = 20 * j, mass = -0.1, rad = 2}) end end Congrats! Your 128 byte long configuration file now requires 2^48 iterations of the inner loop to parse and generates 2^48 instances of the "body" object. That's an expansion factor of at least 2^41 generated bytes for every byte of input, which is a shockingly bad Denial-of-Service attack against whatever is responsible for parsing the evil config file.
    - fit2rule 6y ago
      This is hardly a failing of Lua-morphing-from-config-to-turing language, as it is missing sanitation in the customer interaction workflow. Like, I get that there are services that require this level of trust to the end user, but why wouldn't I solve this problem by timing the config load and immediately stopping any config process that takes longer than it should? Its the 21st century, we can still use interrupts. ;)
- megameter 6y ago
  The basic conundrum, as I was just explaining to a friend, is that as you drop syntax and validation, you gain more possible expressible meanings. A machine code instruction stream, concatenative syntax, and S-expressions all sit in very similar territory in that they are very close to a computed result, and in many cases will accept fairly arbitrary combinations of symbols. Concatenative is in one sweet spot since it deals well with compositions of partial expressions that have no particular "address", while s-exps are in another, where the meanings are bundled into fully addressable trees. Both Forth and Lisp make use of quoting to turn data into code and vice-versa, and introduce ways to assign persistent names and therefore reduce local context and allow reusage; their main difference is in whether they primarily serialize a figurative representation of data structure, or the step-by-step sequence of computing the structure. And whichever you choose, that's great(I've gone on a huge concatenative binge myself), but then to define the application's final protocol, you have to filter it. You have to filter to turn many of these meanings into errors, which leads towards syntax, type-checking, and all the rest. And to the extent that this is a problem, it mostly reflects the human and philosophical factors. What we believe in determines what meanings we wish to see represented in the protocol; our beliefs are many, varied and often contradictory, with entire organizations and systems of governance designed around reconciliation of these beliefs; therefore extensively structured protocols are necessary to define the "sometimes-errors" that result from our incoherence, our limited notion of reality. And that is producing the gradual ramp up towards complex languages, formats and protocols that address the impossible with the incomprehensible. But data and protocols that are very truthful usually do not require such a complex structure, or that structure emerges from natural laws. They may be hard to compute, or hard to store - DNA sequences are very large, and modern cryptography is premised on computational difficulty - but the code that deals with these things is not large in expression, and only needs validation along some very particular axes. Regardless the task of discovering and implementing these things is hard, because evaluating the theory is hard, much harder than validating whether a stream of bytes represents a number, a string, or a list.
- Athas 6y ago
  A non-Turing-complete language can still express programs that require exponential time and space, so is that really enough to provide useful guarantees? And would dynamic limits on resource usage not be sufficient, since the "cannot load configuration"-error would occur at runtime anyway?
jandrese 6y ago
Security researchers on the other hand run away screaming when you tell them that all of your data and configuration files are a complete language and you execute the language to parse the files.
- awirth 6y ago
  Depends on the type of security researcher -- some profit from it!
  - saagarjha 6y ago
    Depends on the kind of work it is. A janitor doesn't go around telling you to make a mess so they can remain employed…
    - mcbits 6y ago
      Unless they're the type of janitor who "really cleans up" when called in to "do a job" at the office overnight.
- saagarjha 6y ago
  The problem is usually not Turing completeness but complexity, which invites bugs in the parser implementation. (The former is trivial to solve: add a timeout.)
  - adwn 6y ago
    > The problem is usually not Turing completeness [...] You're technically correct (the best kind of correct), but jandrese wrote "a complete language", not "a Turing-complete language". You don't need Turing-completeness to create security problems – filesystem access alone does that. > The former is trivial to solve: add a timeout. That only solves the termination problem, which is a minor concern anyway. You don't need much time to compromise a system if you have filesystem access. No "bugs in the parser implementation" needed.
deleted 6y ago
[deleted]

by thurn 6y ago

Lisp programmers realized in the 70s that having an artificial division between code and data was frequently problematic, hopefully other languages continue to catch on as well :)

kiwidrew 6y ago

On the other hand, it's often useful to have data and configuration files that aren't Turing complete, because then you can safely make assumptions about how much time and space is required to load/parse them. Unfortunately every configuration file format these days seems to add so many features that it inevitably becomes Turing-complete... the trick is finding the balance between expressiveness and halting decidability.

tines 6y ago
Lisp data aren't Turing complete, only a particular interpretation of them (i.e. EVAL), as you know. You're perfectly welcome to call READ on a file and you will get unevaluated lisp data back (particularly when you set READ-EVAL to NIL in common lisp).
- fiddlerwoaroof 6y ago
  READ is Turing complete, because the reader can execute arbitrary code: the #. read macro alone is enough to ensure this.
  - dig1 6y ago
    If you set read-eval to false, it will not execute reader macro. [1] [1] http://www.lispworks.com/documentation/HyperSpec/Body/v_rd_eva.htm#STread-evalST http://www.lispworks.com/documentation/HyperSpec/Body/v_rd_e...
    - fiddlerwoaroof 6y ago
      Yeah, but I can use SET-MACRO-CHARACTER to define a version that ignores that variable: basically, you should never use CL:READ on untrusted input, unless you control the readtable.
lmm 6y ago
You might like to look into Dhall - a config language that has been careful to remain non-Turing-complete.
- deleted 6y ago
  [deleted]
- kiwidrew 6y ago
  Wow, cool, that is a really nifty language! I don't care for the syntax (at all) but I am seriously impressed by the careful design. I've always wondered where you'd need to draw the line between plaintext config files and executable code, and Dhall is much further into "programming language" territory than I would've expected. *Dhall homepage for anyone else that's interested - https://dhall-lang.org https://dhall-lang.org
fit2rule 6y ago
Why is configuration performance so important to the application? Sounds a bit like a missing specification for the distinction of load-time and run-time configuration. Configuration, to me, is something that happens once and not often, and is therefore "something = foo". Update is a run-time thing, and therefore "if something then bar". Lua covers both of those cases superlatively. Case A, byte code. Case B, same. Just be sure you have "generate byte code" in the right place, C, too ..
- kiwidrew 6y ago
  Let's say you want the user of your service to be able to write and upload a configuration file, but you specifically don't want them to be able to execute arbitrary code on your server(s). It would be nice to be able to statically verify that their submitted configuration "behaves nicely", but the moment you introduce any kind of Turing-complete configuration language all guarantees go out the window because the problem becomes literally undecidable. [And then you try to mitigate it by imposing limits like "kill the parse process if it takes longer than X seconds or uses more than Y megabytes of memory".] The advantage of, say, a simple .INI file for configuration purposes is that the time required to parse it (and storage space required to remember what's in it) is O(n) where n=size of config file... EDIT: so take the example Lua file from the original post but change the loop limits from "32" to "16777216": for i = 0, 16777216 do for j = 0, 1677216 do add_body({x = 20 * i, y = 20 * j, mass = -0.1, rad = 2}) end end Congrats! Your 128 byte long configuration file now requires 2^48 iterations of the inner loop to parse and generates 2^48 instances of the "body" object. That's an expansion factor of at least 2^41 generated bytes for every byte of input, which is a shockingly bad Denial-of-Service attack against whatever is responsible for parsing the evil config file.
  - fit2rule 6y ago
    This is hardly a failing of Lua-morphing-from-config-to-turing language, as it is missing sanitation in the customer interaction workflow. Like, I get that there are services that require this level of trust to the end user, but why wouldn't I solve this problem by timing the config load and immediately stopping any config process that takes longer than it should? Its the 21st century, we can still use interrupts. ;)
megameter 6y ago
The basic conundrum, as I was just explaining to a friend, is that as you drop syntax and validation, you gain more possible expressible meanings. A machine code instruction stream, concatenative syntax, and S-expressions all sit in very similar territory in that they are very close to a computed result, and in many cases will accept fairly arbitrary combinations of symbols. Concatenative is in one sweet spot since it deals well with compositions of partial expressions that have no particular "address", while s-exps are in another, where the meanings are bundled into fully addressable trees. Both Forth and Lisp make use of quoting to turn data into code and vice-versa, and introduce ways to assign persistent names and therefore reduce local context and allow reusage; their main difference is in whether they primarily serialize a figurative representation of data structure, or the step-by-step sequence of computing the structure. And whichever you choose, that's great(I've gone on a huge concatenative binge myself), but then to define the application's final protocol, you have to filter it. You have to filter to turn many of these meanings into errors, which leads towards syntax, type-checking, and all the rest. And to the extent that this is a problem, it mostly reflects the human and philosophical factors. What we believe in determines what meanings we wish to see represented in the protocol; our beliefs are many, varied and often contradictory, with entire organizations and systems of governance designed around reconciliation of these beliefs; therefore extensively structured protocols are necessary to define the "sometimes-errors" that result from our incoherence, our limited notion of reality. And that is producing the gradual ramp up towards complex languages, formats and protocols that address the impossible with the incomprehensible. But data and protocols that are very truthful usually do not require such a complex structure, or that structure emerges from natural laws. They may be hard to compute, or hard to store - DNA sequences are very large, and modern cryptography is premised on computational difficulty - but the code that deals with these things is not large in expression, and only needs validation along some very particular axes. Regardless the task of discovering and implementing these things is hard, because evaluating the theory is hard, much harder than validating whether a stream of bytes represents a number, a string, or a list.
Athas 6y ago
A non-Turing-complete language can still express programs that require exponential time and space, so is that really enough to provide useful guarantees? And would dynamic limits on resource usage not be sufficient, since the "cannot load configuration"-error would occur at runtime anyway?

jandrese 6y ago

Security researchers on the other hand run away screaming when you tell them that all of your data and configuration files are a complete language and you execute the language to parse the files.

awirth 6y ago
Depends on the type of security researcher -- some profit from it!
- saagarjha 6y ago
  Depends on the kind of work it is. A janitor doesn't go around telling you to make a mess so they can remain employed…
  - mcbits 6y ago
    Unless they're the type of janitor who "really cleans up" when called in to "do a job" at the office overnight.
saagarjha 6y ago
The problem is usually not Turing completeness but complexity, which invites bugs in the parser implementation. (The former is trivial to solve: add a timeout.)
- adwn 6y ago
  > The problem is usually not Turing completeness [...] You're technically correct (the best kind of correct), but jandrese wrote "a complete language", not "a Turing-complete language". You don't need Turing-completeness to create security problems – filesystem access alone does that. > The former is trivial to solve: add a timeout. That only solves the termination problem, which is a minor concern anyway. You don't need much time to compromise a system if you have filesystem access. No "bugs in the parser implementation" needed.

deleted 6y ago

[deleted]