5 ms·

Turing Tarpit

65 points by jaytaylor 11y ago

pdpi 11y ago
It's worth noting that, even if a language is a Turing Tarpit, it doesn't mean there's no value in it. For example, I think of Brainfuck as a brilliant language to introduce people to writing interpreters.
bvaldivielso 11y ago
Designing and implemeting one of this languages is fun and useful to learn how a Turing machine works. I'm not really into PL design, but I guess this could be a good task to get started.
- arethuza 11y ago
  At university I had great fun creating a functional programming language that macro expanded to lambda calculus that was then "compiled" to various sets of combinators - I still find the fact that you can express recursive progams using Y purely in terms of two trivial function (S and K) to be one of the most surprising things in CS.
jjoonathan 11y ago
I like it. Is there a term for the opposite situation? Where you're operating in a declarative environment, what you want to do should be possible, everything similar to the thing you want to do is possible, but your particular use case is excluded due to lack of foresight/manpower/understanding by the authors? (Obviously not entirely specific to non-Turing-complete environments but they tend to be the worst offenders and the hardest to work around for obvious reasons.)
- binarymax 11y ago
  Not an opposite situation, but avoidance of this issue (mostly related to management of state) is outlined in the fantastic paper 'Out of the Tarpit' - which in my opinion every developer should read at least once. http://shaffner.us/cs/papers/tarpit.pdf http://shaffner.us/cs/papers/tarpit.pdf
  - plonh 11y ago
    Ironically, that 66 page document is a massively overcomplicated discussion of the simple idea that inessential mutable state causes problems.
  - PaulHoule 11y ago
    Funny enough I have been doing a deep dive on production rules and logic programming lately, facing up to why the technology has not caught on more than it has. One thing I find is that novices are creating rule bases that form infinite loops and that the CS community has been paralyzed by the fear of infinite loops and poor scaling for particular reasoning chains. Working with mainstream languages, however, I don't find infinite loops (or Turing's Halting Problem) to be all that relevant and the big reason is that the mainstream languages that people like to complain about already have structures built in that make infinite loops less likely to happen.
- deleted 11y ago
  [deleted]
jaytaylor 11y ago
I posted this link after seeing it in this [0] article condemning functional programming languages. While I don't necessarily agree that FPL's should be avoided, I was hoping some interesting discussion might emerge from it. [0] https://news.ycombinator.com/item?id=10566899 https://news.ycombinator.com/item?id=10566899
- sethrin 11y ago
  That article was a fairly factless rant. To my mind, while there may be good reasons to avoid FPLs, that article doesn't present any. It reads like it was written by an angry non-technical co-founder, and its use of images was more appropriate to Buzzfeed than HN. There are certainly more businesses where an army of mediocre Java or PHP programmers are sufficient to keep a piece of software in a useful state than there are environments where you need FPLs, but blanket condemnation is not really worth the time it takes to read. Also, equating a $60k PHP dev and a $150k Haskell dev is likely to be a serious error. And of course, describing FPLs as Turing Tarpits is indefensible. In other words, there's not much in that article to discuss.
  - jaytaylor 11y ago
    Fair enough, thanks for your thoughtful analysis!
- acjohnson55 11y ago
  I shared that same link a couple days ago, mostly hoping to see if it sparked some interesting convo. No one bit. It's a silly article though given that it's pretty clear that functional programming is actually taking over, bit by bit. Not so much the functional languages themselves, but the techniques -- Python's comprehensions, Ruby's blocks, Javascript's Underscore library, and so on. I guess it's debatable whether real startups should go "full functional" but as traditionally imperative and traditionally functional languages continue to converge, it probably matters less and less.
- asgard1024 11y ago
  I don't think FPLs by themselves are (Turing) tar pits. On the other hand, there are lambda-calculus tar pits - for example SKI combinators. This shows that even a language that has referential transparency and lazy evaluation can be a tar pit; so these qualities by themselves are not a way to avoid complexity. I hope one day we will be able to mathematically formulate what is "unnecessary complexity".. but so far, no idea.
kyberias 11y ago
I suspect any Lisp is a Turing tarpit.
- shade23 11y ago
  > A Turing tarpit (or Turing tar-pit) is any programming language or computer interface that allows for flexibility in function but is difficult to learn and use because it offers little or no support for common tasks. Which common task could you not perform with Lisp?And if you are stressing on the `Little or no support`,then thats true any of the lesser popular languages isn't it?
- DonHopkins 11y ago
  Are you sure you don't mean any Lisp is a Turing Carpet, with all those curling parenthesis nestled warmly together like deep twisting loops of shaggy pile?
bqe 11y ago
My favorite Turing tarpit is FRACTRAN, devised by John Conway. It's flabbergasting that it is actually Turing complete, but it is. A FRACTRAN program is a list of fractions, rational numbers. You input an integer and then you find the first fraction that gives you an integer when multiplied by your input. That process is repeated with the new, multiplied number until there is no fraction that produces an integer when multiplied. Conway wrote a program that generates primes, there's others that mathematical sequences, but my favorite is just the addition program: 3/2 Given an input 2^x * 3^y, it will stop at 3^(x+y), which adds x and y together.
- stingraycharles 11y ago
  For the lazy: https://en.m.wikipedia.org/wiki/FRACTRAN https://en.m.wikipedia.org/wiki/FRACTRAN
- pavlov 11y ago
  For some reason this makes me imagine an alternate history sci-fi universe where Pythagoras (famous for his love of fractions) invents FRACTRAN. Then Archimedes builds a mechanical computer to execute those programs, and one of the successors of Alexander The Great puts the computer to use in warfare and conquers the world. Science is accelerated so that nuclear physics are invented by the time Jesus is born... Surely there's some kind of plot waiting there :)
  - saulrh 11y ago
    "My words are backed with NUCLEAR WEAPONS!"
1ris 11y ago
I think this article is missing a description of the phenomenon "accidentially turing-complete". Configurations langues or DSLs that over the time evolved and somehow got turing complete. I suspect these are the most common turing tarpits. And it's a horrible smell.
- RyanZAG 11y ago
  That's kind of an interesting one: consider two configuration languages. The first is not turing complete and can be considered a good language. The second is an identical copy of the first, but includes the ability to have recursive definitions which ends up making it turing complete. Is the second language really worse than the first? They can both be used the same way, but the second one can allow for some shortcuts in configuration by abusing turing completeness. I'd guess the arguments would be: the 2nd language is better, it can create an identical configuration in less lines. Alternatively: the 1st language is better as should allow for easier parsing and is simpler to verify for correctness.
  - Retra 11y ago
    > the 2nd language is better, it can create an identical configuration in less lines. A simple macro or syntax sugar could save you the same lines. A good language will give you a good, terse syntax for representing common configurations, and enough flexibility for clearly denoting the uncommon ones. If your configuration is particularly obscure, it should need more lines to express. It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it.
    - TeMPOraL 11y ago
      Be careful, 'lest your macro language itself turn Turing-complete. > It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it. It's also important to remember it's not always worth sacrificing power to gain verifiable correctness. Not every class of problems needs it. "Freedom for security", something something. ;).
  - 11y ago
tomphoolery 11y ago
This reminds me of something my voice teacher used to say to me in criticism of my flamboyant style of jazz improvisation, and it's my basic philosophy on interface design (of all kinds): "Just because you can, doesn't mean you should." I also apply it to improvisation. :)
13thLetter 11y ago
They can be entertaining, though, if you don't get enough of annoying coding hassles at work! To that end there's a miniature genre of programming puzzle games on the PC. I'd recommend Human Resource Machine, SpaceChem, and TIS-100 for starters.

65 points by jaytaylor 11y ago

pdpi 11y ago

It's worth noting that, even if a language is a Turing Tarpit, it doesn't mean there's no value in it. For example, I think of Brainfuck as a brilliant language to introduce people to writing interpreters.

bvaldivielso 11y ago

Designing and implemeting one of this languages is fun and useful to learn how a Turing machine works. I'm not really into PL design, but I guess this could be a good task to get started.

arethuza 11y ago
At university I had great fun creating a functional programming language that macro expanded to lambda calculus that was then "compiled" to various sets of combinators - I still find the fact that you can express recursive progams using Y purely in terms of two trivial function (S and K) to be one of the most surprising things in CS.

jjoonathan 11y ago

I like it. Is there a term for the opposite situation? Where you're operating in a declarative environment, what you want to do should be possible, everything similar to the thing you want to do is possible, but your particular use case is excluded due to lack of foresight/manpower/understanding by the authors? (Obviously not entirely specific to non-Turing-complete environments but they tend to be the worst offenders and the hardest to work around for obvious reasons.)

binarymax 11y ago
Not an opposite situation, but avoidance of this issue (mostly related to management of state) is outlined in the fantastic paper 'Out of the Tarpit' - which in my opinion every developer should read at least once. http://shaffner.us/cs/papers/tarpit.pdf http://shaffner.us/cs/papers/tarpit.pdf
- plonh 11y ago
  Ironically, that 66 page document is a massively overcomplicated discussion of the simple idea that inessential mutable state causes problems.
- PaulHoule 11y ago
  Funny enough I have been doing a deep dive on production rules and logic programming lately, facing up to why the technology has not caught on more than it has. One thing I find is that novices are creating rule bases that form infinite loops and that the CS community has been paralyzed by the fear of infinite loops and poor scaling for particular reasoning chains. Working with mainstream languages, however, I don't find infinite loops (or Turing's Halting Problem) to be all that relevant and the big reason is that the mainstream languages that people like to complain about already have structures built in that make infinite loops less likely to happen.
deleted 11y ago
[deleted]

jaytaylor 11y ago

I posted this link after seeing it in this [0] article condemning functional programming languages. While I don't necessarily agree that FPL's should be avoided, I was hoping some interesting discussion might emerge from it. [0] https://news.ycombinator.com/item?id=10566899 https://news.ycombinator.com/item?id=10566899

sethrin 11y ago
That article was a fairly factless rant. To my mind, while there may be good reasons to avoid FPLs, that article doesn't present any. It reads like it was written by an angry non-technical co-founder, and its use of images was more appropriate to Buzzfeed than HN. There are certainly more businesses where an army of mediocre Java or PHP programmers are sufficient to keep a piece of software in a useful state than there are environments where you need FPLs, but blanket condemnation is not really worth the time it takes to read. Also, equating a $60k PHP dev and a $150k Haskell dev is likely to be a serious error. And of course, describing FPLs as Turing Tarpits is indefensible. In other words, there's not much in that article to discuss.
- jaytaylor 11y ago
  Fair enough, thanks for your thoughtful analysis!
acjohnson55 11y ago
I shared that same link a couple days ago, mostly hoping to see if it sparked some interesting convo. No one bit. It's a silly article though given that it's pretty clear that functional programming is actually taking over, bit by bit. Not so much the functional languages themselves, but the techniques -- Python's comprehensions, Ruby's blocks, Javascript's Underscore library, and so on. I guess it's debatable whether real startups should go "full functional" but as traditionally imperative and traditionally functional languages continue to converge, it probably matters less and less.
asgard1024 11y ago
I don't think FPLs by themselves are (Turing) tar pits. On the other hand, there are lambda-calculus tar pits - for example SKI combinators. This shows that even a language that has referential transparency and lazy evaluation can be a tar pit; so these qualities by themselves are not a way to avoid complexity. I hope one day we will be able to mathematically formulate what is "unnecessary complexity".. but so far, no idea.

kyberias 11y ago

I suspect any Lisp is a Turing tarpit.

shade23 11y ago
> A Turing tarpit (or Turing tar-pit) is any programming language or computer interface that allows for flexibility in function but is difficult to learn and use because it offers little or no support for common tasks. Which common task could you not perform with Lisp?And if you are stressing on the `Little or no support`,then thats true any of the lesser popular languages isn't it?
DonHopkins 11y ago
Are you sure you don't mean any Lisp is a Turing Carpet, with all those curling parenthesis nestled warmly together like deep twisting loops of shaggy pile?

bqe 11y ago

My favorite Turing tarpit is FRACTRAN, devised by John Conway. It's flabbergasting that it is actually Turing complete, but it is. A FRACTRAN program is a list of fractions, rational numbers. You input an integer and then you find the first fraction that gives you an integer when multiplied by your input. That process is repeated with the new, multiplied number until there is no fraction that produces an integer when multiplied. Conway wrote a program that generates primes, there's others that mathematical sequences, but my favorite is just the addition program: 3/2 Given an input 2^x * 3^y, it will stop at 3^(x+y), which adds x and y together.

stingraycharles 11y ago
For the lazy: https://en.m.wikipedia.org/wiki/FRACTRAN https://en.m.wikipedia.org/wiki/FRACTRAN
pavlov 11y ago
For some reason this makes me imagine an alternate history sci-fi universe where Pythagoras (famous for his love of fractions) invents FRACTRAN. Then Archimedes builds a mechanical computer to execute those programs, and one of the successors of Alexander The Great puts the computer to use in warfare and conquers the world. Science is accelerated so that nuclear physics are invented by the time Jesus is born... Surely there's some kind of plot waiting there :)
- saulrh 11y ago
  "My words are backed with NUCLEAR WEAPONS!"

1ris 11y ago

I think this article is missing a description of the phenomenon "accidentially turing-complete". Configurations langues or DSLs that over the time evolved and somehow got turing complete. I suspect these are the most common turing tarpits. And it's a horrible smell.

RyanZAG 11y ago
That's kind of an interesting one: consider two configuration languages. The first is not turing complete and can be considered a good language. The second is an identical copy of the first, but includes the ability to have recursive definitions which ends up making it turing complete. Is the second language really worse than the first? They can both be used the same way, but the second one can allow for some shortcuts in configuration by abusing turing completeness. I'd guess the arguments would be: the 2nd language is better, it can create an identical configuration in less lines. Alternatively: the 1st language is better as should allow for easier parsing and is simpler to verify for correctness.
- Retra 11y ago
  > the 2nd language is better, it can create an identical configuration in less lines. A simple macro or syntax sugar could save you the same lines. A good language will give you a good, terse syntax for representing common configurations, and enough flexibility for clearly denoting the uncommon ones. If your configuration is particularly obscure, it should need more lines to express. It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it.
  - TeMPOraL 11y ago
    Be careful, 'lest your macro language itself turn Turing-complete. > It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it. It's also important to remember it's not always worth sacrificing power to gain verifiable correctness. Not every class of problems needs it. "Freedom for security", something something. ;).
- 11y ago

tomphoolery 11y ago

This reminds me of something my voice teacher used to say to me in criticism of my flamboyant style of jazz improvisation, and it's my basic philosophy on interface design (of all kinds): "Just because you can, doesn't mean you should." I also apply it to improvisation. :)

13thLetter 11y ago

They can be entertaining, though, if you don't get enough of annoying coding hassles at work! To that end there's a miniature genre of programming puzzle games on the PC. I'd recommend Human Resource Machine, SpaceChem, and TIS-100 for starters.