4 ms·

It's when it's part of the core language, as any Turing complete language can implement any feature of any other Turing complete language. It's not a useful sta

It's when it's part of the core language, as any Turing complete language can implement any feature of any other Turing complete language. It's not a useful statement to say all languages support all features.

pjmlp 5y ago
So I guess Common Lisp, Raket, Scheme, C++, C#, F#,... just lost a couple of features.
- weavejester 5y ago
  If those features are supplied by libraries outside the core language, I don't think I'd count them. I use Clojure a fair bit, and that has a miniKanren implementation in the form of core.logic. Would I say that makes Clojure a relational programming language? No, I don't think so, because it's not part of the core language. Similarly, there exists an optional static typing library for Clojure called core.typed - does that make Clojure a statically typed language? Again, I don't believe so. You can build a library to implement any feature, particularly in Lisps or other languages with support for AST transformations. Those features may even be counter to the core design of the language - you could write a library in Haskell to support dynamically typed, imperative programming, for example.
kazinator 5y ago
Rather, any Universal Turing Machine can be programmed to calculate whatever any other Universal Turing Machine can be programmed to calculate. It's not necessarily done with the same features, or use of resources. In some cases, the only way the features of some UTM A's architecture will be obtained through UTM B, is if UTM B is used to create a simulation of UTM A, and so then that provides a way to execute the UTM A instructions themselves. In that situation, UTM B itself has not acquired the features of UTM A.
- weavejester 5y ago
  There are two problems with making that distinction. First, by that definition, few languages have regular expressions as a feature. Second, in languages with support for syntax rewriting, that would mean the internal implementation, not the user-facing syntax, is what decides what counts as a "real" feature.
  - kazinator 5y ago
    A TM is a machine which accepts a tape, together with a specific tape: it performs a very specific calculation. A UTM can take an instructional input which turns it into a different machine, which can then process tapes designed for a different TM mechanism. A fixed programming language (and its standard library) is a UTM. If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. Everything else is instructions: additional libraries, macros, whatever. We can extend languages by pretending that the additional code we have written (libraries, syntax rewriting) comprise a new, extended language. So that's a new UTM. There are limits in what syntactic rewriting can provide in a seamless, efficient way. Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. The use of the features it provides is walled off within the embedded syntax. (Not to deny that this is nevertheless valid and practically useful.) The UTM theory tells us that we can always adapt a UTM to accept the tapes intended for any TM mechanism. However, it doesn't tell us how costly that is. For some TM mechanisms, the approach may be to translate a given tape up-front into the UTM's own instructions and then run it directly. For some TM mechanisms, the approach may be to simulate the mechanism: the UTM's instructions execute the simulator, which executes the tape. The UTM theory mostly talks about simulation. What we know is given a Turing Complete language A (i.e. a UTM) we can always write an interpreter for language B. That's the baseline. We then have a new UTM equivalent to B, consisting of language A, plus the interpreter. That setup then accepts programs of language B, and their inputs.
    - weavejester 5y ago
      > If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. By "the library" do you mean the core library of the language? If a language didn't have regular expressions as part of its core library, does that mean regular expressions would not be a feature of that language? > Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. Why inefficient? Why interpreted? What if the syntax was efficiently compiled?

pjmlp 5y ago

So I guess Common Lisp, Raket, Scheme, C++, C#, F#,... just lost a couple of features.

weavejester 5y ago
If those features are supplied by libraries outside the core language, I don't think I'd count them. I use Clojure a fair bit, and that has a miniKanren implementation in the form of core.logic. Would I say that makes Clojure a relational programming language? No, I don't think so, because it's not part of the core language. Similarly, there exists an optional static typing library for Clojure called core.typed - does that make Clojure a statically typed language? Again, I don't believe so. You can build a library to implement any feature, particularly in Lisps or other languages with support for AST transformations. Those features may even be counter to the core design of the language - you could write a library in Haskell to support dynamically typed, imperative programming, for example.

kazinator 5y ago

Rather, any Universal Turing Machine can be programmed to calculate whatever any other Universal Turing Machine can be programmed to calculate. It's not necessarily done with the same features, or use of resources. In some cases, the only way the features of some UTM A's architecture will be obtained through UTM B, is if UTM B is used to create a simulation of UTM A, and so then that provides a way to execute the UTM A instructions themselves. In that situation, UTM B itself has not acquired the features of UTM A.

weavejester 5y ago
There are two problems with making that distinction. First, by that definition, few languages have regular expressions as a feature. Second, in languages with support for syntax rewriting, that would mean the internal implementation, not the user-facing syntax, is what decides what counts as a "real" feature.
- kazinator 5y ago
  A TM is a machine which accepts a tape, together with a specific tape: it performs a very specific calculation. A UTM can take an instructional input which turns it into a different machine, which can then process tapes designed for a different TM mechanism. A fixed programming language (and its standard library) is a UTM. If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. Everything else is instructions: additional libraries, macros, whatever. We can extend languages by pretending that the additional code we have written (libraries, syntax rewriting) comprise a new, extended language. So that's a new UTM. There are limits in what syntactic rewriting can provide in a seamless, efficient way. Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. The use of the features it provides is walled off within the embedded syntax. (Not to deny that this is nevertheless valid and practically useful.) The UTM theory tells us that we can always adapt a UTM to accept the tapes intended for any TM mechanism. However, it doesn't tell us how costly that is. For some TM mechanisms, the approach may be to translate a given tape up-front into the UTM's own instructions and then run it directly. For some TM mechanisms, the approach may be to simulate the mechanism: the UTM's instructions execute the simulator, which executes the tape. The UTM theory mostly talks about simulation. What we know is given a Turing Complete language A (i.e. a UTM) we can always write an interpreter for language B. That's the baseline. We then have a new UTM equivalent to B, consisting of language A, plus the interpreter. That setup then accepts programs of language B, and their inputs.
  - weavejester 5y ago
    > If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. By "the library" do you mean the core library of the language? If a language didn't have regular expressions as part of its core library, does that mean regular expressions would not be a feature of that language? > Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. Why inefficient? Why interpreted? What if the syntax was efficiently compiled?