Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I think 2) seems incorrect. What you can’t have is unbounded loops and recursion. Bounded loops are perfectly fine and I don’t tend to need unbounded ones when programming (with exceptions being infinite loops for handling asynchronous events, which a configuration language doesn’t need to do).

Recursion is trickier. I think banning it or simply limiting stack depth seems fairly reasonable? In fact I’m pretty sure most Turing-complete languages have a stack depth limit, so unbounded recursion is not allowed for those either. I don’t see a limit being a problem, because again this is a config language.

I don’t see why HTML escaping needs Turing-completeness. It shouldn’t need any unbounded iteration (it should be limited to the size of the input string) or unbounded loops. In general, I can’t think of any typical data processing code where turning completeness is required, but could be wrong. Do you have any practical examples of transformations that need unbounded iteration?



> I don’t see why HTML escaping needs Turing-completeness.

First of all, let's avoid "Turing-completeness" because then we might start arguing about whether a language with unrestricted recursion is or isn't Turing-complete since there are stack depth limits / memory limits / universe will end one day / etc.

I would phrase this question as "why would HTML escaping need unrestricted recursion or loops" -- since in practice config languages either have unrestricted recursion or loops (Nickel), or they don't (CUE, Dhall, Starlark).

For HTML escaping specifically, just having `.map(f)` and `.concat` available (in functional languages), or `for char in string` (in imperative languages), would be enough.

For something like HTML un-escaping, it's already trickier. If you are using recursion, your language needs to understand the concept of the string becoming "smaller" at each step. If you are using loops, `for ... in ...` is not enough anymore.

An even trickier example would be mergesort:

  merge(xs, ys) = ...

  mergeSort(xs) =
    let len   = xs.length
        left  = mergeSort(xs.slice(0, len/2))
        right = mergeSort(xs.slice(len/2, len))
    in merge(left, right)
It might seem obvious that this should terminate, because of course `.slice` will return a smaller array, but the actual termination proof in Agda is already something I wouldn't want in my config language: <https://stackoverflow.com/a/22271690/615030>

(Not to mention that this implementation is faulty and will loop at len=1.)

Limiting stack depth at [arbitrary number] -- this is similar to (1). I don't know why configuration languages don't do it, to be honest.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: