4 ms·

> Most anything in software can easily end up Turing-complete though. not really, if you actually pay attention when youre designing the type system: https://

by 38 3y ago

> Most anything in software can easily end up Turing-complete though. not really, if you actually pay attention when youre designing the type system: https://arxiv.org/pdf/2005.11710.pdf https://arxiv.org/pdf/2005.11710.pdf

insanitybit 3y ago
"if you actually pay attention" or, in other words, if you produce novel research into the area that's worthy of publishing, and noting that this is only just the start and has its own limitations: > The cost is that of requiring a whole program analysis and disallowing programs that would result in infinite instantiations (Section 5.3). Clearly, this is the beginning of the story, not the end.
- deleted 3y ago
  [deleted]
bhouston 3y ago
My experience with Turing-completeness in any custom DSL or similar is that you will generally get Turing-complete systems unless you work really really hard to avoid them. And it only takes one wrong move by anything anywhere in the system, and you'll end up with Turing-completeness. Instead of trying to avoid Turing-completeness, just expect it, embrace it and instead deal with its consequences to contain the fallout.
- 38 3y ago
  > Instead of trying to avoid Turing-completeness, just expect it, embrace it and instead deal with its consequences to contain the fallout. this seems like such a cop out. its like saying "oh failure is a given, so don't even try to succeed". at least currently, Go generics are NOT Turing complete. the generics were designed in part specifically to avoid that. so just because Rust (and others) failed, doesn't mean its impossible.
  - bhouston 3y ago
    > this seems like such a cop out. its like saying "oh failure is a given, so don't even try to succeed". It is a pragmatic cop-out yes. I found it is easier to make progress by assuming that you'll get to Turing Complete rather than investing in the time to avoid it. I found that the downsides of Turing Completeness are usually overhyped or primarily theoretical. > so just because Rust (and others) failed, doesn't mean its impossible. It definitely is not impossible. But I don't know if it is worth it. In the end I want fast compile times, type safety, easy to maintain code and good error messages. I do not care if the type system is Turing Complete.
    - 38 3y ago
      > In the end I want fast compile times, type safety, easy to maintain code and good error messages. I do not care if the type system is Turing Complete. I think the problem is some languages with Rust go too far with generics, which probably triggers the turing complete. for example, this is valid Rust code: let mut handles = Vec::new(); for i in 0..10 { let handle = do_work(i); handles.push(handle); } but you have to follow the code all the way to "do_work" before you ever find the type of anything. Go does not allow this. you need to either declare a concrete type: var handles []int or a explicit generic type: type slice[T any] []T var handles slice[int] I think Rust is lose lose, because the underlying type implementation is Turing complete, and I would argue the code is actually less readable because of the overuse of type inference.
      - bhouston 3y ago
        > I think Rust is lose lose, because the underlying type implementation is Turing complete I am not a Rust coder so I can't really comment. Currently, I do TypeScript, which also has a Turing complete type system, and I love it. Of course all things in moderation. Even though I could make a completely obtuse type design for projects, I try to not write code that others can not understand.
  - insanitybit 3y ago
    I don't think most people care at all that their type system is turing complete. It basically never comes up.

by 38 3y ago

insanitybit 3y ago

"if you actually pay attention" or, in other words, if you produce novel research into the area that's worthy of publishing, and noting that this is only just the start and has its own limitations: > The cost is that of requiring a whole program analysis and disallowing programs that would result in infinite instantiations (Section 5.3). Clearly, this is the beginning of the story, not the end.

deleted 3y ago
[deleted]

bhouston 3y ago

My experience with Turing-completeness in any custom DSL or similar is that you will generally get Turing-complete systems unless you work really really hard to avoid them. And it only takes one wrong move by anything anywhere in the system, and you'll end up with Turing-completeness. Instead of trying to avoid Turing-completeness, just expect it, embrace it and instead deal with its consequences to contain the fallout.

38 3y ago
> Instead of trying to avoid Turing-completeness, just expect it, embrace it and instead deal with its consequences to contain the fallout. this seems like such a cop out. its like saying "oh failure is a given, so don't even try to succeed". at least currently, Go generics are NOT Turing complete. the generics were designed in part specifically to avoid that. so just because Rust (and others) failed, doesn't mean its impossible.
- bhouston 3y ago
  > this seems like such a cop out. its like saying "oh failure is a given, so don't even try to succeed". It is a pragmatic cop-out yes. I found it is easier to make progress by assuming that you'll get to Turing Complete rather than investing in the time to avoid it. I found that the downsides of Turing Completeness are usually overhyped or primarily theoretical. > so just because Rust (and others) failed, doesn't mean its impossible. It definitely is not impossible. But I don't know if it is worth it. In the end I want fast compile times, type safety, easy to maintain code and good error messages. I do not care if the type system is Turing Complete.
  - 38 3y ago
    > In the end I want fast compile times, type safety, easy to maintain code and good error messages. I do not care if the type system is Turing Complete. I think the problem is some languages with Rust go too far with generics, which probably triggers the turing complete. for example, this is valid Rust code: let mut handles = Vec::new(); for i in 0..10 { let handle = do_work(i); handles.push(handle); } but you have to follow the code all the way to "do_work" before you ever find the type of anything. Go does not allow this. you need to either declare a concrete type: var handles []int or a explicit generic type: type slice[T any] []T var handles slice[int] I think Rust is lose lose, because the underlying type implementation is Turing complete, and I would argue the code is actually less readable because of the overuse of type inference.
    - bhouston 3y ago
      > I think Rust is lose lose, because the underlying type implementation is Turing complete I am not a Rust coder so I can't really comment. Currently, I do TypeScript, which also has a Turing complete type system, and I love it. Of course all things in moderation. Even though I could make a completely obtuse type design for projects, I try to not write code that others can not understand.
- insanitybit 3y ago
  I don't think most people care at all that their type system is turing complete. It basically never comes up.