7 ms·

Primitive Recursive Functions for a Working Programmer

189 points by ingve 2y ago

fire_lake 2y ago
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.
Exuma 2y ago
[flagged]
- ramses0 2y ago
  Good. Food. Flood. Lews. Lows. Luse. Loose. Lose.
- lgas 2y ago
  > "lose" and "loose" > They dont even sound or look anything alike... You really don't think those two words look anything alike?
- ffhhj 2y ago
  Its. It's.
  - chrisweekly 2y ago
    They're / their.
    - tmtvl 2y ago
      Less / fewer.
      - SoftTalker 2y ago
        Further/farther
- soup_bud 2y ago
  I'm pretty sure that the author's first language is not English :) doesn't seem like an unreasonable mistake to make to me
  - ffhhj 2y ago
    And haven't discovered that LLMs can proofread text.
  - 2y ago
ch0ic3 2y ago
I'm struggling with the mini rant / motivation of the article: > Typically, not being Turing-complete is extolled as a virtue or even a requirement in specific domains. I claim that most such discussions are misinformed — that not being Turing complete doesn’t actually mean what folks want it to mean Why are those discussion misinformed? Most formal analysis tools (Coq, Isabelle, Agda(?)) usually require a proof that a function terminates. This is I think is equivalent to proving that it is total implying it is primitive recursive?
- bmillwood 2y ago
  > This is I think is equivalent to proving that it is total implying it is primitive recursive? No, as the article shows there are functions which terminate that aren't primitive recursive, and indeed Agda and (probably?) the others can prove termination for some (but necessarily not all) terminating non-primitive-recursive functions. I think the misinformation that the article is complaining about is something like (my paraphrase): > "Turing completeness" means "can do computation" while "non-Turing complete" means both "can't do computation" and "has nice configuration-language properties" The article points out: - you can be non-Turing complete and still do lots of computationally-expensive / tricky work - your configuration language probably wants much stricter limits than merely being non-Turing complete
  - chowells 2y ago
    > I think the misinformation that the article is complaining about is something like (my paraphrase): > > "Turing completeness" means "can do computation" while "non-Turing complete" means both "can't do computation" and "has nice configuration-language properties" "Turing complete" means it can do any computation a Turing machine can. That is absolutely more power than is desired about 99.99% of the time. You almost always want your algorithms to contain no infinite loops. (Algorithms. Not IO loops. Those are different, and the process of taking outside input while the program is running is outside the scope of what a Turing machine talks about anyway.) Turing completeness is an ergonomics hack, and one with a decently successful history. But it's no panacea, and if we could find an ergonomic way to get rid of it, that would be a win. Yes, even if we didn't also enforce primitive recursion. Sure, it's nice to know you're also not accidentally running Ackerman's function, but to be honest... I've had many more accidental infinite loops than accidental Ackerman's functions in my code. By approximately 10,000 to 0. No system can ever prevent all errors. So let's focus on preventing the most common current ones.
ykonstant 2y ago
The conclusion to the article has some pretty good points regarding configuration languages; I wonder if any present language satisfies all or most of those points.
- nine_k 2y ago
  Let's pick Dhall and see if it fails any of the points. It seems closest.
  - talideon 2y ago
    Skylark also. It's essentially Python with anything more than primitive recursive functions cut out.
    - extrabajs 2y ago
      One point that the article is trying to make is that even something in PRF can give rise to a very long-running computation.
- nyrikki 2y ago
  While imperative, and not 'pure' even C was created to set upper bound of the number of iterations of every loop being known before entering, thus PR Dennis Ritchie's research at MIT was focused on what he called loop programming. The complexity of loop programs - ALBERT R. MEYER and DENNIS M. RITCHIE https://people.csail.mit.edu/meyer/meyer-ritchie.pdf https://people.csail.mit.edu/meyer/meyer-ritchie.pdf Structured programming, the paradigm that almost every modern programmer follows by default is really pushing you to primitive recursive functions. That almost universal acceptance of structured programming compared to the other two types, pop and functional, is why people are confused about Dykstra's goto is harmful paper. While primitive recursive functions don't contain the entire set of computable functions, they do contain almost all intuitive ones that are guaranteed to HALT (total). Unfortunately there are some real needs for languages to support loops that have an indeterminate number of iterations when you enter the loop, but it is a foot gun that is avoidable by only using them when required. Even COBOL was modernized with unrestricted goto being moved to the ALTER command. I can't think of a modern, useful language that doesn't allow for PR functions. But even in C, if you avoid 'while', explicitly avoid fall through, etc... you will produce code that almost always is a total functions that will always HALT. There are cases like even type inference in ML, which is pathological in that it is way cheaper than the complexity class, thus worth the risk, despite not being total functions that make it hard for a language to restrict those use cases. So I would say that with a pragmatic approach, all languages support defaults that support most of the points, but imposed constraints that enforce them would seriously constrain the utility of the language. If you review even the hated SOLID and Clean frameworks, they're pushing you towards this model too IMHO. I think the universal acceptance of structured programming, makes this easy to forget or even fail to teach. But as an old neck beard, we were taught the risks of WHILE etc...
4ad 2y ago
I am a CUE developer. CUE is primitive recursive. It also happens to fulfill your desired criteria for a "good" configuration language.
- 4ad 2y ago
  For fun, here is CUE simulating an arbitrary but finite number of steps of Rule 110[0]: https://cuelang.org/play/?id=Ityqia88Mvq#w=function&i=cue&f=export&o=cue https://cuelang.org/play/?id=Ityqia88Mvq#w=function&i=cue&f=... [0] https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110
nayuki 2y ago
Self-promotion: https://www.nayuki.io/page/primitive-recursive-functions https://www.nayuki.io/page/primitive-recursive-functions
- keithalewis 2y ago
  Far superior to the original article. But people seem to prefer ELI5 baby talk these days.
  - djaouen 2y ago
    Don't know why you are being downvoted. Quoted article is (obviously) superior.
    - deleted 2y ago
      [deleted]
    - jolmg 2y ago
      My guess is that if they dropped "baby" and just said: > people seem to prefer ELI5 talk they might've not gotten downvoted. (Didn't downvote myself, but this makes sense to me.)
      - keithalewis 2y ago
        You say that as if I give a shit about sanctimonious HN downvotes. :-)
    - olejorgenb 2y ago
      Uh, the quoted article is nice, terse, and seems to contains a lot to play with, but doesn't really address the same things as the topic article.
deleted 2y ago
[deleted]
layer8 2y ago
@author: s/defile/define/ ;) Also: s/necessary/necessarily/
- OJFord 2y ago
  Also: > If math makes you slightly nauseas That's the plural of nausea, you wanted nauseous. But the real reason I mention it is to joke, since you said you were generally descriptivist, that you fell for a common error and actually 'nauseous' describes the thing that makes someone nauseated. ;)
conradludgate 2y ago
I've wanted to write a backend web programming language that is based on non-terminating/bounded principles. My theory is that all functions can prove to the compiler that they have bounded execution based on the state and arguments given, and that X is the lower bound and Y is the upper bound. This propagates all the way to the entry point. I agree with the author with regards to the stronger semantics, and that's why I thought of this language. You often want to have some guarantees over the execution time of your program. It would probably be PRF based at the core, but Turing complete in practice. Like how rust rejects invalid borrows but still offers unsafe for raw pointers, this lang would either calculate the upper bound based on the simple loop primitives, or you'd have to use the unsafe operators and provide an alternative formula for the bounds.
olejorgenb 2y ago
> Suppose it runs faster than O(2^(2^N)). That is, two to the power of two to the power of N, a very large number. ~~While probably meant to simply, this statement sort-of undermines the author's credibility. I mean the "a very large number" part. Correct me if I'm wrong, but surly he means "a very fast growing function".~~ Or - it seems he mean the the program completes in less than O(2^(2^N)) steps.

189 points by ingve 2y ago

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.

Exuma 2y ago

[flagged]

ramses0 2y ago
Good. Food. Flood. Lews. Lows. Luse. Loose. Lose.
lgas 2y ago
> "lose" and "loose" > They dont even sound or look anything alike... You really don't think those two words look anything alike?
ffhhj 2y ago
Its. It's.
- chrisweekly 2y ago
  They're / their.
  - tmtvl 2y ago
    Less / fewer.
    - SoftTalker 2y ago
      Further/farther
soup_bud 2y ago
I'm pretty sure that the author's first language is not English :) doesn't seem like an unreasonable mistake to make to me
- ffhhj 2y ago
  And haven't discovered that LLMs can proofread text.
- 2y ago

ch0ic3 2y ago

I'm struggling with the mini rant / motivation of the article: > Typically, not being Turing-complete is extolled as a virtue or even a requirement in specific domains. I claim that most such discussions are misinformed — that not being Turing complete doesn’t actually mean what folks want it to mean Why are those discussion misinformed? Most formal analysis tools (Coq, Isabelle, Agda(?)) usually require a proof that a function terminates. This is I think is equivalent to proving that it is total implying it is primitive recursive?

bmillwood 2y ago
> This is I think is equivalent to proving that it is total implying it is primitive recursive? No, as the article shows there are functions which terminate that aren't primitive recursive, and indeed Agda and (probably?) the others can prove termination for some (but necessarily not all) terminating non-primitive-recursive functions. I think the misinformation that the article is complaining about is something like (my paraphrase): > "Turing completeness" means "can do computation" while "non-Turing complete" means both "can't do computation" and "has nice configuration-language properties" The article points out: - you can be non-Turing complete and still do lots of computationally-expensive / tricky work - your configuration language probably wants much stricter limits than merely being non-Turing complete
- chowells 2y ago
  > I think the misinformation that the article is complaining about is something like (my paraphrase): > > "Turing completeness" means "can do computation" while "non-Turing complete" means both "can't do computation" and "has nice configuration-language properties" "Turing complete" means it can do any computation a Turing machine can. That is absolutely more power than is desired about 99.99% of the time. You almost always want your algorithms to contain no infinite loops. (Algorithms. Not IO loops. Those are different, and the process of taking outside input while the program is running is outside the scope of what a Turing machine talks about anyway.) Turing completeness is an ergonomics hack, and one with a decently successful history. But it's no panacea, and if we could find an ergonomic way to get rid of it, that would be a win. Yes, even if we didn't also enforce primitive recursion. Sure, it's nice to know you're also not accidentally running Ackerman's function, but to be honest... I've had many more accidental infinite loops than accidental Ackerman's functions in my code. By approximately 10,000 to 0. No system can ever prevent all errors. So let's focus on preventing the most common current ones.

ykonstant 2y ago

The conclusion to the article has some pretty good points regarding configuration languages; I wonder if any present language satisfies all or most of those points.

nine_k 2y ago
Let's pick Dhall and see if it fails any of the points. It seems closest.
- talideon 2y ago
  Skylark also. It's essentially Python with anything more than primitive recursive functions cut out.
  - extrabajs 2y ago
    One point that the article is trying to make is that even something in PRF can give rise to a very long-running computation.
nyrikki 2y ago
While imperative, and not 'pure' even C was created to set upper bound of the number of iterations of every loop being known before entering, thus PR Dennis Ritchie's research at MIT was focused on what he called loop programming. The complexity of loop programs - ALBERT R. MEYER and DENNIS M. RITCHIE https://people.csail.mit.edu/meyer/meyer-ritchie.pdf https://people.csail.mit.edu/meyer/meyer-ritchie.pdf Structured programming, the paradigm that almost every modern programmer follows by default is really pushing you to primitive recursive functions. That almost universal acceptance of structured programming compared to the other two types, pop and functional, is why people are confused about Dykstra's goto is harmful paper. While primitive recursive functions don't contain the entire set of computable functions, they do contain almost all intuitive ones that are guaranteed to HALT (total). Unfortunately there are some real needs for languages to support loops that have an indeterminate number of iterations when you enter the loop, but it is a foot gun that is avoidable by only using them when required. Even COBOL was modernized with unrestricted goto being moved to the ALTER command. I can't think of a modern, useful language that doesn't allow for PR functions. But even in C, if you avoid 'while', explicitly avoid fall through, etc... you will produce code that almost always is a total functions that will always HALT. There are cases like even type inference in ML, which is pathological in that it is way cheaper than the complexity class, thus worth the risk, despite not being total functions that make it hard for a language to restrict those use cases. So I would say that with a pragmatic approach, all languages support defaults that support most of the points, but imposed constraints that enforce them would seriously constrain the utility of the language. If you review even the hated SOLID and Clean frameworks, they're pushing you towards this model too IMHO. I think the universal acceptance of structured programming, makes this easy to forget or even fail to teach. But as an old neck beard, we were taught the risks of WHILE etc...

4ad 2y ago

I am a CUE developer. CUE is primitive recursive. It also happens to fulfill your desired criteria for a "good" configuration language.

4ad 2y ago
For fun, here is CUE simulating an arbitrary but finite number of steps of Rule 110[0]: https://cuelang.org/play/?id=Ityqia88Mvq#w=function&i=cue&f=export&o=cue https://cuelang.org/play/?id=Ityqia88Mvq#w=function&i=cue&f=... [0] https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110

nayuki 2y ago

Self-promotion: https://www.nayuki.io/page/primitive-recursive-functions https://www.nayuki.io/page/primitive-recursive-functions

keithalewis 2y ago
Far superior to the original article. But people seem to prefer ELI5 baby talk these days.
- djaouen 2y ago
  Don't know why you are being downvoted. Quoted article is (obviously) superior.
  - deleted 2y ago
    [deleted]
  - jolmg 2y ago
    My guess is that if they dropped "baby" and just said: > people seem to prefer ELI5 talk they might've not gotten downvoted. (Didn't downvote myself, but this makes sense to me.)
    - keithalewis 2y ago
      You say that as if I give a shit about sanctimonious HN downvotes. :-)
  - olejorgenb 2y ago
    Uh, the quoted article is nice, terse, and seems to contains a lot to play with, but doesn't really address the same things as the topic article.

deleted 2y ago

[deleted]

layer8 2y ago

@author: s/defile/define/ ;) Also: s/necessary/necessarily/

OJFord 2y ago
Also: > If math makes you slightly nauseas That's the plural of nausea, you wanted nauseous. But the real reason I mention it is to joke, since you said you were generally descriptivist, that you fell for a common error and actually 'nauseous' describes the thing that makes someone nauseated. ;)

conradludgate 2y ago

I've wanted to write a backend web programming language that is based on non-terminating/bounded principles. My theory is that all functions can prove to the compiler that they have bounded execution based on the state and arguments given, and that X is the lower bound and Y is the upper bound. This propagates all the way to the entry point. I agree with the author with regards to the stronger semantics, and that's why I thought of this language. You often want to have some guarantees over the execution time of your program. It would probably be PRF based at the core, but Turing complete in practice. Like how rust rejects invalid borrows but still offers unsafe for raw pointers, this lang would either calculate the upper bound based on the simple loop primitives, or you'd have to use the unsafe operators and provide an alternative formula for the bounds.

olejorgenb 2y ago

> Suppose it runs faster than O(2^(2^N)). That is, two to the power of two to the power of N, a very large number. ~~While probably meant to simply, this statement sort-of undermines the author's credibility. I mean the "a very large number" part. Correct me if I'm wrong, but surly he means "a very fast growing function".~~ Or - it seems he mean the the program completes in less than O(2^(2^N)) steps.