4 ms·

"There's not much you can do in Awk that you can't do elsewhere: Turing-completeness and all that." The fact that Awk is Turing-complete has nothing to do with

by kenko 13y ago

"There's not much you can do in Awk that you can't do elsewhere: Turing-completeness and all that." The fact that Awk is Turing-complete has nothing to do with the fact (if it is a fact) that there's not much you can do in it that you can't do elsewhere. The SKI combinator calculus is Turing-complete, but you can't read a CSV file with it.

throwaway1980 13y ago
> The SKI combinator calculus is Turing-complete, but you can't read a CSV file with it. Of course you can, it's just a matter of input handling. For that matter you can read a CSV file with any Turing machine. It's just easier elsewhere.
- kenko 13y ago
  Well, I must be very confused, then, because I don't see where the input comes in given just the s, k and i combinators. (The Jot programming language, which can be translated into SKI, for instance, doesn't do input or output. You want the Zot variant for that.) How would one write a program, using just s, k, i, and application, that takes the name of a file on the command line, opens it and reads it in, then prints the lines in reverse order to stdout?
  - Millennium 13y ago
    If you really wanted to do pure SKI, you'd have to do more than just a program: you'd have to implement the whole machine and the OS running on it. You could do that, but as you might imagine, it's quite a lot of work. That said, keep in mind that most likely, you'd want to start implementing levels of abstraction pretty early on. The fact that SKI is Turing-equivalent means that you can implement a Turing machine (or anything else that is Turing-equivalent) in it. Build your favorite abstraction, and then implement your machine and OS the way you would using that abstraction. It's still SKI underneath, so you're golden.
    - innguest 13y ago
      I don't understand how your reply addresses anything kenko said. I agree with kenko and I wish people would stop bringing turing completeness/equivalence into discussions about what languages can do what. Turing completeness is inconsequential in such discussions; we're talking about what's practical and reasonable to do in each language. I wish people would stop trying to impress us with academic tangents.
      - Millennium 13y ago
        The site's called Hacker News for a reason, and it caters to entrepreneurs for the same reason. We're already people with something of a penchant for not caring about the "practical" or "reasonable," or even considering that to be a challenge. But if we're going to talk about what is practical and reasonable, then let's look back at awk's niche: prying data out of line-oriented text files. For that particular task, C and the basic lisps rank among my languages of last resort: assembler (pick an architecture) would be worse, but that's just about it. There are libraries for these languages which would help significantly, but my awk script would be finished and halfway through the dataset by the time I even got the build environment set up for these languages, and the code would still be more clear. Like I said, the right tool for the job. For many tasks -most, actually- awk would not be very high on my list of languages to try. But find a task that hits awk's sweet spot, and nothing beats it.
    - kenko 13y ago
      Maybe so, but that completely gives the lie to the idea that two languages are equipotent if they're both Turing complete. The sorts of abstractions you'd need to implement go far beyond what's required for Turing completeness Unlambda, for instance, is Turing complete, and moreover, it can do I/O. An Unlambda program is nevertheless incapable of opening files or doing different things depending on its command-line arguments. You can write cat (the version of cat that just echoes stdin to stdout) in Unlambda, but not ls. You might be able to write an Unlambda-based operating system in which all the various sorts of input events that an OS needs to respond to are represented as elements in its input stream (or, even better, an OS in Lazy-K). But when you've got that OS up and running, Unlambda programs running on it still won't be able to open files. (Frankly I'd be surprised if the "abstractions" necessary to get something like that up and running weren't essentially an interpreter written in another language dealing with the encoding and decoding of input and output to your Unlambda/Lazy-K program, rather than abstractions written in Unlambda/Lazy-K. (Consider that the numbers that Lazy-K outputs are church encoded and must be converted by the Lazy-K interpreter into C-like integers before characters can be output to stdout.) This isn't really important, though.) Consider also this final note from the Lazy-K page: "Remove output entirely. You still have a Turing-complete language this way, and it is if anything more elegant. But, as with the equally elegant SMETANA, you can't do anything with it except stare at it in admiration, and the novelty of that wears off after a few minutes." That's not really true, of course: there are other things you can do, like increase the temperature of your processor. Not many other things, though.

by kenko 13y ago

throwaway1980 13y ago

> The SKI combinator calculus is Turing-complete, but you can't read a CSV file with it. Of course you can, it's just a matter of input handling. For that matter you can read a CSV file with any Turing machine. It's just easier elsewhere.

kenko 13y ago
Well, I must be very confused, then, because I don't see where the input comes in given just the s, k and i combinators. (The Jot programming language, which can be translated into SKI, for instance, doesn't do input or output. You want the Zot variant for that.) How would one write a program, using just s, k, i, and application, that takes the name of a file on the command line, opens it and reads it in, then prints the lines in reverse order to stdout?
- Millennium 13y ago
  If you really wanted to do pure SKI, you'd have to do more than just a program: you'd have to implement the whole machine and the OS running on it. You could do that, but as you might imagine, it's quite a lot of work. That said, keep in mind that most likely, you'd want to start implementing levels of abstraction pretty early on. The fact that SKI is Turing-equivalent means that you can implement a Turing machine (or anything else that is Turing-equivalent) in it. Build your favorite abstraction, and then implement your machine and OS the way you would using that abstraction. It's still SKI underneath, so you're golden.
  - innguest 13y ago
    I don't understand how your reply addresses anything kenko said. I agree with kenko and I wish people would stop bringing turing completeness/equivalence into discussions about what languages can do what. Turing completeness is inconsequential in such discussions; we're talking about what's practical and reasonable to do in each language. I wish people would stop trying to impress us with academic tangents.
    - Millennium 13y ago
      The site's called Hacker News for a reason, and it caters to entrepreneurs for the same reason. We're already people with something of a penchant for not caring about the "practical" or "reasonable," or even considering that to be a challenge. But if we're going to talk about what is practical and reasonable, then let's look back at awk's niche: prying data out of line-oriented text files. For that particular task, C and the basic lisps rank among my languages of last resort: assembler (pick an architecture) would be worse, but that's just about it. There are libraries for these languages which would help significantly, but my awk script would be finished and halfway through the dataset by the time I even got the build environment set up for these languages, and the code would still be more clear. Like I said, the right tool for the job. For many tasks -most, actually- awk would not be very high on my list of languages to try. But find a task that hits awk's sweet spot, and nothing beats it.
  - kenko 13y ago
    Maybe so, but that completely gives the lie to the idea that two languages are equipotent if they're both Turing complete. The sorts of abstractions you'd need to implement go far beyond what's required for Turing completeness Unlambda, for instance, is Turing complete, and moreover, it can do I/O. An Unlambda program is nevertheless incapable of opening files or doing different things depending on its command-line arguments. You can write cat (the version of cat that just echoes stdin to stdout) in Unlambda, but not ls. You might be able to write an Unlambda-based operating system in which all the various sorts of input events that an OS needs to respond to are represented as elements in its input stream (or, even better, an OS in Lazy-K). But when you've got that OS up and running, Unlambda programs running on it still won't be able to open files. (Frankly I'd be surprised if the "abstractions" necessary to get something like that up and running weren't essentially an interpreter written in another language dealing with the encoding and decoding of input and output to your Unlambda/Lazy-K program, rather than abstractions written in Unlambda/Lazy-K. (Consider that the numbers that Lazy-K outputs are church encoded and must be converted by the Lazy-K interpreter into C-like integers before characters can be output to stdout.) This isn't really important, though.) Consider also this final note from the Lazy-K page: "Remove output entirely. You still have a Turing-complete language this way, and it is if anything more elegant. But, as with the equally elegant SMETANA, you can't do anything with it except stare at it in admiration, and the novelty of that wears off after a few minutes." That's not really true, of course: there are other things you can do, like increase the temperature of your processor. Not many other things, though.