3 ms·
The title's a little misleading, as it suggests that there's something strange or even wrong about the type that OCaml or Haskell infer for the program. Of cour
by seliopou 12y ago
The title's a little misleading, as it suggests that there's something strange or even wrong about the type that OCaml or Haskell infer for the program. Of course the type that these systems infer for the program is correct, and the author does demonstrate an understanding of that. But that a small input to a system can produce a large output should be little surprise to any person that works with complex systems, especially computer systems.
The underlying mechanism that leads to the computational complexity in HM(x) systems--the process of generalizing types to schemas and instantiating schemas to types in order to support let-polymorphism--would make for an interesting discussion, but the author hasn't hit on that yet. Unfortunately, the only people that really understand that part of the algorithm are the people that have implemented the algorithm, and there aren't many of those people around. Strange but true. The algorithm that's taught and implemented in most undergraduate PL courses (PL:AI-based courses included) does not support let-polymorphism. If the author's reading, upgrade to ATTAPL[0] and start implementing.
Also, to answer the question "How to compile Turing machines to ML types", have a look at typo[1] for one way to do it in Haskell (by reducing it to lambda calculus (shameless plug)).
[0]: http://www.cis.upenn.edu/~bcpierce/attapl/ http://www.cis.upenn.edu/~bcpierce/attapl/
[1]: https://github.com/seliopou/typo https://github.com/seliopou/typo
- JadeNB 12y agoI think that this is my new favourite esolang. Type-level naturals (http://www.haskell.org/haskellwiki/Type_arithmetic http://www.haskell.org/haskellwiki/Type_arithmetic), eat your heart out! What was your inspiration for making this? By the way, sorry for a "useless use of cat" (http://en.wikipedia.org/wiki/Cat_%28Unix%29#Useless_use_of_cat http://en.wikipedia.org/wiki/Cat_%28Unix%29#Useless_use_of_c...) nit-pick, but note that $ cat examples/fac.typo | typo should probably be $ typo < examples/fac.typo
- seliopou 12y agoThanks! Typo made it HN last summer, so here's a response to your question on motivation[0]. Also, the 'cat' thing has come up before. Here's my response to that[1] as well. But now that I'm rereading my response it doesn't seem clear what I mean. The README for the language demonstrates how you can use shell grouping as a poor man's module system. When you do that, you have to use 'cat' on single files in certain situations. So I stuck with 'cat' for the simple example so it's consistent with the more complex examples. If you take a look at the typo script[2] that wraps the compiler, you'll see that I know when to use redirects and when to use 'cat'. But regardless of all that, I think most modern machines can spare an extra process. [0]: https://news.ycombinator.com/item?id=6176340 https://news.ycombinator.com/item?id=6176340 [1]: https://github.com/seliopou/typo/pull/4 https://github.com/seliopou/typo/pull/4 [2]: https://github.com/seliopou/typo/blob/cc64ec38603a50c6543b3834d47b4ff0431c2b3e/typo#L14 https://github.com/seliopou/typo/blob/cc64ec38603a50c6543b38...
- JadeNB 12y agoThanks for the helpful reply. By the way, I didn't mean to suggest that you didn't know when to use `cat` vs. re-directs; I just thought it might have been an oversight. I'm sorry if it came across as rude.