4 ms·

Just tackling the first part, about restricted languages being better for some applications: Isn’t the advantage that an upper bound on the number of steps req

Just tackling the first part, about restricted languages being better for some applications: Isn’t the advantage that an upper bound on the number of steps required can be computed statically? This means we can refuse to compute things that violate some limit and give back a meaningful error, for all possible inputs. Whereas with the Turing complete plus Runtime Limit approach, we might pick a limit that is too low for some inputs we care about. We won’t know until we run the computation and hit the limit! We see this sometimes with C++ template recursion. I might be totally confused here so I hope some more knowledgable can weigh in :)

mrkeen 2y ago
Accurately predicting fuel usage for a blockchain computation? It's probably interesting to others but not to me. I'd be more interested in using it just as another hammer in the tool-belt to squash bugs that got past earlier hammers (static type-checking, no nulls, no mutations, etc.) Terminating in finite time can't prove correctness, but if I declare that my code will terminate in finite time and my compiler disagrees, I'd certainly believe my code is incorrect.
hinkley 2y ago
I use 10x the reasonable computation amount, ever since a coworker used a number closer to 3x and real workloads hit that limit a few years later. I figure giving a bad workflow several times longer to fail is still measured in milliseconds and doesn’t hurt that much. But I usually run into this problem when someone has treated the problem domain as a DAG but can’t enforce the Acyclic part. But modeling your problem as a DAG is reminiscent of Dark Galadriel, when she contemplates taking the arming from Frodo - All Shall Love Me and Despair. The people who make them are always way prouder of themselves than they deserve to be. Eventually your customers who were attracted by the expensive and complex solution to their problems run out of money, and their problems seem a lot smaller to them. Then you are left - literally - with an app that cannot be made cheap enough per operation to keep their business.
- gopher_space 2y ago
  > treated the problem domain as a DAG but can’t enforce the Acyclic part. Would you mind talking about this for a bit? I'm missing a lot of context.
- lanstin 2y ago
  3 is roughly half of ten logarithmically. And in any business that uses software (to co duct the business) you always want engineering to keep in mind the doubling time, or if the business is shrinking. A lot of efficiency decisions are driven by doubling time. I worked where we had doubling time of 90 days when I started and there keeping everything scaled up so that your idle capacity was. On more than half made sense. When it had increased to a couple years, then your could tighten down to n/n+1 utilization. If it is shrinking, first of all that's a problem, but also you can make the infra much cheaper pretty easily, if the code is still modifiable.
kccqzy 2y ago
And what if that upper bound is an extremely loose upper bound? Say a deterministic quick sort has an upper bound that's quadratic in input size even though typically it's linearithmic? Do you refuse the computation of quick sort then? Or more dramatically consider the Hindley–Milner algorithm which has an upper bound of exponential time even though in practice it runs in linear time?
IshKebab 2y ago
I don't know about "computed statically" but yeah I think the only advantage to drastically limiting the capabilities of a language (as in many new configuration languages, CEL, etc.) is that you can have a sort of computation limit that isn't data dependent. But I struggle to think of a single situation in which that's a real hard requirement. How many systems are there that can't give a "query took too long" error?
- lanstin 2y ago
  Well if the query is from an adversary it has undesirable results.
  - IshKebab 2y ago
    Like what? Can you give an example?
    - lanstin 2y ago
      DDOS against your DB or even just your hash table.
layer8 2y ago
The statically determined upper bound can vastly overestimate the actual runtime complexity in common cases, because it generally can’t predict how conditionals that lead to early exits in recursions will turn out. Note: This assumes lazy evaluation, or short-circuiting conditionals, in order for early exits to affect the runtime, but that’s what you’d generally have in a practical language.

mrkeen 2y ago

Accurately predicting fuel usage for a blockchain computation? It's probably interesting to others but not to me. I'd be more interested in using it just as another hammer in the tool-belt to squash bugs that got past earlier hammers (static type-checking, no nulls, no mutations, etc.) Terminating in finite time can't prove correctness, but if I declare that my code will terminate in finite time and my compiler disagrees, I'd certainly believe my code is incorrect.

hinkley 2y ago

I use 10x the reasonable computation amount, ever since a coworker used a number closer to 3x and real workloads hit that limit a few years later. I figure giving a bad workflow several times longer to fail is still measured in milliseconds and doesn’t hurt that much. But I usually run into this problem when someone has treated the problem domain as a DAG but can’t enforce the Acyclic part. But modeling your problem as a DAG is reminiscent of Dark Galadriel, when she contemplates taking the arming from Frodo - All Shall Love Me and Despair. The people who make them are always way prouder of themselves than they deserve to be. Eventually your customers who were attracted by the expensive and complex solution to their problems run out of money, and their problems seem a lot smaller to them. Then you are left - literally - with an app that cannot be made cheap enough per operation to keep their business.

gopher_space 2y ago
> treated the problem domain as a DAG but can’t enforce the Acyclic part. Would you mind talking about this for a bit? I'm missing a lot of context.
lanstin 2y ago
3 is roughly half of ten logarithmically. And in any business that uses software (to co duct the business) you always want engineering to keep in mind the doubling time, or if the business is shrinking. A lot of efficiency decisions are driven by doubling time. I worked where we had doubling time of 90 days when I started and there keeping everything scaled up so that your idle capacity was. On more than half made sense. When it had increased to a couple years, then your could tighten down to n/n+1 utilization. If it is shrinking, first of all that's a problem, but also you can make the infra much cheaper pretty easily, if the code is still modifiable.

kccqzy 2y ago

And what if that upper bound is an extremely loose upper bound? Say a deterministic quick sort has an upper bound that's quadratic in input size even though typically it's linearithmic? Do you refuse the computation of quick sort then? Or more dramatically consider the Hindley–Milner algorithm which has an upper bound of exponential time even though in practice it runs in linear time?

IshKebab 2y ago

I don't know about "computed statically" but yeah I think the only advantage to drastically limiting the capabilities of a language (as in many new configuration languages, CEL, etc.) is that you can have a sort of computation limit that isn't data dependent. But I struggle to think of a single situation in which that's a real hard requirement. How many systems are there that can't give a "query took too long" error?

lanstin 2y ago
Well if the query is from an adversary it has undesirable results.
- IshKebab 2y ago
  Like what? Can you give an example?
  - lanstin 2y ago
    DDOS against your DB or even just your hash table.

layer8 2y ago

The statically determined upper bound can vastly overestimate the actual runtime complexity in common cases, because it generally can’t predict how conditionals that lead to early exits in recursions will turn out. Note: This assumes lazy evaluation, or short-circuiting conditionals, in order for early exits to affect the runtime, but that’s what you’d generally have in a practical language.