Guido 在 G+上 发表的 关于Haskell的msg & 留言 (大家有什么看法?)

zcheung

Guido van Rossum  -  上午6:20  -  公開
Haskell fans are funny. They pride themselves that Haskell has no while-loops -- but they have infinite lists. They tell you to define everything using recursive functions, but then warn you that it will take O(N) stack space unless you rewrite it using foldl or seq. I guess nobody's perfect.

[And, by the way, this is just a friendly rib. No need to educate me. I am educating myself about Haskell as we speak, maybe next week I can explain all this. ]


Gina-Marie Ardizzone Behrens  -  http://www.linuxjournal.com/article/8850

Pierre Thierry  -  Actually, that's not specific to Haskell at all. Any compiler worth its salt would optimize terminal recursion as a JMP (or whatever equivalent the CPU your running on provides). So that's what you should aim for in any recursive definition.

John Millikin  -  It sounds like the Haskell fans you're speaking to have never used Haskell

For one, it certainly has while loops (though defined as functions, not build-in keywords).

And it doesn't have a stack, so it's impossible to run out of "stack space"; you could just plain run out of memory by building up a huge value, but this is true of any language.

The actual reason to use folds instead of recursion is that it's easier to read, and less redundant. Sort of like [[ for item in items ]] is used instead of [[ i = 0; while True: item = items; i += 1; ... ]] in Python.

Russell Nelson  -  TRAC doesn't have any loops. The only way to do the same thing again on a different piece of data is to use tail-recursion.

Guido van Rossum  -  +John Millikin Did the author of "learnyouahaskell.com" never use Haskell? I have it right from this page: http://learnyouahaskell.com/recursion#hello-recursion "Recursion is important to Haskell because unlike imperative languages, you do computations in Haskell by declaring what something is instead of declaring how you get it. That's why there are no while loops or for loops in Haskell and instead we many times have to use recursion to declare what something is."

I cannot quote the remark about running out of stack space but it came from a friend who is trying to teach me Haskell. He certainly sounds like he's written (and taught) plenty of Haskell.

John Millikin  -  Haskell tutorials/books always claim there are no loops. I think they're trying to shock learners out of their comfort zone, but it'd be nice if they wouldn't lie about it.

Student: Professor, I want to loop over this list, but I can't figure out how to do a while loop!
Professor: Uh...Haskell can't do loops, you'll have to use folds.
Student: That's hard and annoying, but I guess it can't be helped.

(six months later)

Advanced Student: What the hell do you mean by "no loops"? Every library I look in has them!
Professor: * whistles *

-------------------

Here's a while loop; it'll do (action) until (test) returns false.

while :: Monad m => m Bool -> m () -> m ()
while test action = loop where
.. loop = do
.... run <- test
.... if run then (action >> loop) else return ()

You can use it for things like "wait until a variable contains some value" or "read data from a socket into a buffer until EOF".

Note that while it's implemented with recursion (and thus technically obeying LYAH's statement), the interface it exposes is a procedural loop.

The number one thing to remember when learning Haskell is that it's a strict superset of procedural languages like C or Python. Anything you can do in Python, you can do in Haskell. When a tutorial says "Haskell doesn't support <some common feature>", it's wrong 100% of the time.

Whether you want to use a loop or a catamorphic supercalifragilisticexpialidociousmorphism is up to you.

楼下续发

zcheung

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)

楼下续发

zcheung

Pierre Thierry  -  Actually, proofs about TCO are required only if the environment is stack allocated. If heap allocated, you don't need to bother anymore and it also saves you from the funarg problem.

Guido van Rossum  -  +Russell Nelson That doesn't look like a tail call to me -- the last operation is '*', not a self-call. (Though in some versions of TCO, it doesn't have to be the same function that's called -- the stack frame could potentially be reused by any call, depending on how your compiler/interpreter uses the stack.)

Guido van Rossum  -  +Michael Foord Not likely by me (I'd sooner write a Haskell compiler in Python , but if it was good enough for Perl 6, who knows...

Pierre Thierry  -  +Russell Nelson You need a tail call to get tail call optimization:
def a(b, acc=1):
if b < 10: return acc*5
return a(b-1, b*acc)

Simon Marlow  -  +John Millikin I think you're confusing the issue. The simple fact is, if there's a function call in the corner of an expression, it is always a tail-call. You can identify tail-calls syntactically. +Guido van Rossum I think you may have been misinformed. I can assure you that, having implemented said optimisation, GHC definitely does TCO Perhaps there's a specific example you have in mind? Laziness does make things more interesting, for example in 'map', although the recursive call is not a tail-call, it is lazy, so it runs in O(1) stack.

Duncan Booth  -  +Simon Marlow You can identify some tail-calls syntactically, but others could be more complex. If you take the example from +Russell Nelson it isn't a tail call, but provided your language allows the compiler to assume that the * operator in this situation is associative it might be possible for the compiler to do an automatic translation to +Pierre Thierry's code.

Jiří Šebele  -  I never really got into Haskell... It seems little awkward when making real applications to me.

整个信息完

zcheung

好像没什么人到FP 版 哈

OwnWaterloo

Guido van Rossum其实没什么才华。
或者换种说法， Guido有没有才华不知道， 但总之从Python这门语言看不出他有。

记得以前他有一篇关于tail call optimization的文章，认为不应该支持……
连这都不应该被支持，那什么应该被支持？
只能是表达式的lambda？
只能yield一层的coroutine？
还是添加了global后发现没对，其实要的是nonlocal？

Python才是一门表面优美而内部到处充满"funny"的语言
为什么Lua总是可以一步搞到位，而Python总是一步一个错…… 没才华啊

嗯，发送之前确认一下这里不是python而是functional版块……

zcheung

反正每次我看見有人說Python支持Functional，并且以Python中的lambda map來做論據 的時候，我都會不由自主的開心笑了。。

zcheung

Perl6其语言的具体改变和思想我没有看。
单独就Perl6的程序要运行Parrot其上，这一点纯属意淫行为。

tangboyun

Perl6的原型实现去年10月就放出了，不过估计5->6的升级肯定难产，毕竟改动比python2->3大多了。弄不好死在这上面都可能。
咳，当时还是因为Perl6才开始对Haskell感兴趣的，现在perl的惯用法都忘的差不多了。