-
Notifications
You must be signed in to change notification settings - Fork 400
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Automatic deforestation. #167
Comments
That's a great question. Sadly, no, HVM won't do that, by design. That's because we follow the Linux philosophy of doing just one thing, and doing it well: it is a runtime, not an optimizing compiler. GHC does both at once, but HVM separates these responsibilities. As such, it will just run the program you feed as fast as it can, but it won't alter it in any way. It is the compiler's job (i.e., the language that is targeting the HVM) to apply optimizing transformations. This is good because it gives the source language full control over what will actually run. That said, it is worth noting that, due to optimal reduction, we already have "runtime deforestation"! Yes, that's right. That's because optimal reduction can be seen as as if HVM was doing aggressive inlining at runtime, which in all other languages used to be a compile-time thing. Let me give you a concrete example. Consider the following program:
It just applies
As you can see, each call to Map adds exactly 400 to the total cost. Now, as you may be aware, a popular deforestation technique employed by Haskell is
Here is the number of rewrites in function of the number of calls to Map:
As you can see, each call to |
Thank you very much for the detailed answer. The separation makes total sense to me. It should be noted that that's how most popular languages do it and it works well for them, there's probably no need to innovate there with this project, I agree. Your answer manages to convey so many good things. Very exciting! |
Hello, I just have a quick question.
Do the maintainers plan to implement some sort of automatic deforestation to get rid of intermediary trees when doing separate calculations over the same tree? (Or is this even something that a virtual machine based on lambda calculus could provide us for free?)
(If the maintainers are familiar with recursion schemes:) By deforestion I'm talking about the kind of deforestation that one gets from e.g. using a hylomorphism instead of an anamorphism followed by a catamorphism. Or e.g. by manually inlining multiple tree traversals into one traversal.
Recursion schemes aren't really practical in most languages, even if one can simulate higher kinded types, because they require an explicit fusion model for having them be performant and worth the effort. If HVM could address this issue as well, that would be absolutely phenomenal. (I'm not claiming that you should focus on that, I was just wondering whether this is something that one could expect.)
The text was updated successfully, but these errors were encountered: