- 论坛徽章:
- 0
|
Guido van Rossum - I guess that's what I was calling out. Though what do you mean by "strict" superset? Surely Haskell, C and Python are all Turing complete?
Guido van Rossum - +Pierre Thierry I have been assured that Haskell does not do general tail call optimization, because the language is lazy. Are you one of those Haskell fans who hasn't actually used Haskell?
Russell Nelson - Yeeks! /me hugs tail recursion optimization.
John Millikin - "Strict superset" is probably an imprecise or non-academic way to put it, but oh well.
I mean any C or Python code can be translated into Haskell, retaining its basic form[1].
Lots of people are taught that Haskell is some sort of idiot-savant language, which supposedly works well despite having lots of important things missing. Some of the features I've heard people claim it lacks are pointers, dynamic typing, direct memory management, mutable arrays, and so on.
This misinformation can be cured effectively by taking an existing stateful library (for example, Pthon's docutils RST TableParser) and rewriting it line-by-line into procedural-style Haskell.
Even the gnarliest, most stateful, most procedural code can be translated to Haskell with patience. The result will of course be very non-idiomatic, and likely much longer than in its native language, but it will compile and run.
[1] With caveats; some features, such as C's static allocation or Python's introspection, would require a lot of support code to be written first.
John Millikin - I'm not sure what "general tail call optimization" is; Haskell compilers do TCO if they can prove (though strictnes analysis or use of 'seq') that the function is actually tail recursive.
This is dependent on how the function executes, not its syntactic form (eg, where its return is located), so maybe that's a source of confusion?
Pierre Thierry - I'm really a Lisper, so yes! I'm actually very curious about the details on why Haskell doesn't do TCO… (my procrastination devil thanks you)
Michael Foord - So, Python 4 to be implemented in Haskell then?
Russell Nelson - def a(b):
if b < 10: return 5
return b*a(b-1)
If this doesn't consume any stack space, then your language does TCO. I can't see why any proof would be necessary.
John Millikin - Proofs of TCO-ishness are required because functions can be much more complicated than that.
For example, what if the function builds a closure, and passes it to the recursive call?
What if the return value is a generator expression?
Both of these are examples of laziness in Python; they inhibit TCO because they require the function's environment to persist beyond when it has returned.
Add in exceptions and things get even more complicated. A TCO-enabled compiler must be careful that it will never accidentally change the exception-throwing behavior of some code by applying an optimization.
(all of this applies equally to Python, Haskell, Lisp, or any other high-level language)
楼下续发 |
|