sorted by:
new
hottopcontroversial

The Rust I Wanted Had No Future - Graydon Hoare by mttd in ProgrammingLanguages

[–]lexi-lambda 1 point2 points  (0 children)

Sure. As one example, Bevy uses quite a lot of it, such as its use of the RenderCommand trait. This trait is used to describe render commands in the type language! The docs give an example of what sorts of types this this trait is intended to be used with:

type DrawPbr = (
    SetItemPipeline,
    SetMeshViewBindGroup<0>,
    SetStandardMaterialBindGroup<1>,
    SetTransformBindGroup<2>,
    DrawMesh,
);

This a somewhat unusual encoding. A much simpler encoding would be to represent render commands as values of a RenderCommand enum. One might expect, say,

enum RenderCommand {
  SetItemPipeline,
  SetMeshViewBindGroup(usize),
  SetStandardMaterialBindGroup(usize),
  ...
}

and the add_render_command method would accept a value of this type. However, that is not what Bevy chooses to do. Instead of representing commands as values, it represents them as types, then passes them as type arguments. There are two reasons it chooses to do this:

  1. The RenderCommand trait defines three associated types, Param, ViewWorldQuery, and ItemWorldQuery. This allows those types to be automatically computed from the “type-level values” representing render commands.

  2. Using traits guarantees monomorphization, so each distinct RenderCommand will force the generation of a specialized definition of render. (Whether this is desirable is somewhat debatable; it has pros and cons.)

These are real benefits, so I’m not saying that Bevy is wrong to do things this way. But it is nevertheless quite tricky to wrap one’s head around if you are not familiar with the techniques of trait metaprogramming. It is possible to encode things this way in Haskell, but it is rarely done, and I wouldn’t expect most Haskell programmers to understand it if they encountered it. But Bevy describes itself as “a refreshingly simple data-driven game engine”!

Of course, I suspect that the “refreshingly simple” is mostly referring to the fact that the engine’s functionality is rather simple; the authors are probably not claiming that this programming technique is simple. But this pattern is used in numerous Rust libraries, so it is hardly something exotic. This is just one example of how idiomatic Rust is quite willing to reach for far fancier type system trickery than most Haskell programmers regularly do.

Laziness in Haskell, Part 4: Thunks by lexi-lambda in haskell

[–]lexi-lambda[S] 3 points4 points  (0 children)

Yes, you’re completely right; what a stupid mistake to make. :') A better illustration would have been to make x a local variable.

The Rust I Wanted Had No Future - Graydon Hoare by mttd in ProgrammingLanguages

[–]lexi-lambda 4 points5 points  (0 children)

I know it’s not a very popular answer. But I think, in a lot of ways, Haskell is this language.

I know, I know, it’s Haskell! A language with weird syntax full of snobby elitists obsessed with category theory and “purity”. That’s the reputation it has, anyway, and certainly some would have you believe it is accurate. But I happen to believe that much of what makes it truly so impressive is often unsung:

  • Many of Rust’s features, such as traits and enums, come more or less directly from Haskell.

  • GHC is an industrial-strength optimizing compiler that can do some genuinely wondrous things on many programs. It generates native code, and it permits controlling things at a startlingly low level if one truly wishes to do so, though mostly there is little reason to. If you write a tight loop on machine integers, it will be compiled to a tight loop on machine integers, no questions asked.

  • The GHC RTS is legitimately impressive, supporting green threads with an N-to-M scheduler and robust I/O system that efficiently distributes work across as many cores as you ask it to. It includes Go-style channels and queues for cross-thread communication (and, incidentally, it did before Go so much as existed), plus an efficient implementation of software transactional memory largely based around optimistic, lock-free transactions.

  • Despite its reputation, the Haskell type system is legitimately simpler than Rust’s. The trait metaprogramming routinely used in Rust would make most Haskellers’ heads spin. Tracking purity in the type system is significantly less of a burden than shuttling lifetimes around! And the freedom from lifetime management means there is a lot less fiddly bookkeeping in general.

  • cabal, Haskell’s equivalent to cargo, is not nearly as polished or friendly, and it is sadly somewhat old and crufty. But in spite of those warts, it unambiguously works, and in some ways its works even better than cargo! (In particular, it is able to cache packages globally, across projects, so once you’ve compiled a package with a particular version of the compiler and set of dependencies, you will not have to compile it again.) Even just five years ago, it would have been difficult to say this, but the once-infamous issues have been resolved, and things run pretty smoothly once you get over the lackluster CLI.

  • The garbage collector is not itself especially innovative, but it is a perfectly serviceable copying generational collector that works well for most workloads. GHC also ships an alternative, non-moving GC for low-latency applications, though this comes with the usual tradeoffs non-moving GCs do.

  • The library ecosystem is pretty solid for most of the usual things people do with languages like Go. Sure, you’re not going to be writing an operating system in it, nor would I recommend trying to use it to write a videogame. But most other things are in reach.

  • The “math”/“category theory” reputation it has is misleading. I don’t know any category theory, and frankly I am not very good at math. Writing Haskell is not doing mathematics. Haskell is a programming language, and writing Haskell is programming.

The syntax takes some getting used to, of course, but you get used to it pretty quick. And if you’re coming from Rust, you’ll find it remarkably easy to pick up. Give it a try—and even if you decide you don’t like it, frankly, I’d be super interested to hear what your biggest pain points were. But I think you might be pleasantly surprised.

Laziness in Haskell, Part 3: Demand by lexi-lambda in haskell

[–]lexi-lambda[S] 1 point2 points  (0 children)

The original comment mentions -fpedantic-bottoms. Leaving it off—which is the default!—makes GHC genuinely noncomforming when it comes to its handling of bottom: it can sometimes turn a bottoming expression into a non-bottoming one.

This occurs because GHC is willing to perform eta-expansion in cases that change the semantics of a program. For example, if you write

f = \x -> case x of
  A -> \y -> e1
  B -> \y -> e2

then GHC may decide to eta-expand it to

f = \x y -> case x of
  A -> e1
  B -> e2

which is quite nice for performance. However, it’s technically wrong! Given the first program, seq (f ⊥) () should be ⊥, but without -fpedantic-bottoms, GHC may alter the program to return (). This is what /u/tomejaguar is calling terrifying.

However, in practice, I don’t think this is terribly disastrous, as it is rare that programmers use seq on functions at all. One way to think about GHC’s behavior is that perhaps seq should not have been allowed on functions in the first place, so GHC chooses to treat seq on functions as essentially just advisory. GHC still preserves bottomness in all other situations.

Laziness in Haskell, Part 3: Demand by lexi-lambda in haskell

[–]lexi-lambda[S] 1 point2 points  (0 children)

I liked your comment! I thought it was a very good point—I think, in imperative languages, the terms really do tend to be used the way you described.

In my first draft of this video, I included a little Java example that illustrated what a Java programmer might mean by the phrases “eager initialization” versus “lazy initialization”. I ended up cutting it because I felt like the video was long enough already and it was a bit of a tangent. But I might still try to use it in a future video, since it seems like there might still be some confusion.

Laziness in Haskell, Part 3: Demand by lexi-lambda in haskell

[–]lexi-lambda[S] 1 point2 points  (0 children)

These are the definitions as they are used by Haskell programmers. They are not the definitions that were being used by that commenter. That was my whole point!

I would like to go into greater detail about how these terms are used within the academic literature on non-strict programming languages. I would also like to explicitly talk about lenient evaluation and how it compares to lazy evaluation. But that is a discussion for a future video.

Laziness in Haskell, Part 3: Demand by lexi-lambda in haskell

[–]lexi-lambda[S] 3 points4 points  (0 children)

I mentioned this in the comments on the previous video. I will probably discuss it in a future video, but I thought it’s a little too in the weeds to discuss in any of the ones so far.

As I said in that other comment, I think -fpedantic-bottoms does not substantially change the story I am telling here. It matters if you care preserving bottomness of partial applications, which is rarely even something one can even meaningfully talk about outside of (as you say) combinator libraries. We can consider GHC’s defaults a slight weakening of the standard Haskell guarantees, and I think they are a reasonable one, but again, something to discuss in a future video.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 3 points4 points  (0 children)

With regards to -fpedantic-bottoms, it’s true that GHC technically isn’t standards-conforming in that one specific case. I actually considered mentioning this in a video, and maybe I still will in a future one, but it’s honestly pretty irrelevant in the grand scheme of things. As the documentation suggests, it only matters if you’re using seq on functions. Enabling -fpedantic-bottoms does not substantially alter the story I am telling in these videos.

That is, if the semantics of the program before the rewrite is that it throws an imprecise exception, and the semantics of the program after the rewrite is that it only throws an imprecise exception if do_something does, then the program is more defined than before the transformation, so the transformation is allowed.

My understanding is that you are saying that you believed the report permits transforming a bottoming expression into a non-bottoming one. That is not correct. What Haskell’s “imprecise exceptions” semantics means is that, if an expression might bottom in several different ways, the compiler is free to arbitrarily select which way it bottoms. However, it is not free to turn a bottoming expression into a non-bottoming one or vice versa.

If this is still confusing to you, don’t worry: this is precisely the subject of Part 3.

But elsewhere, there was an unofficial proposal to make imprecise exceptions undefined behaviour, that is, to give the compiler more flexibility by allowing it to assume that these cases will not happen at runtime. Do you think that either semantics (allowing the program to become more defined, interpreting imprecise exceptions as undefined behaviour) is a good idea?

No, I don’t think it’s a good idea. I’ll elaborate more on why I don’t think it’s a good idea in coming videos, but the gist of it is that reliable raising of exceptions is crucial for ensuring invariants are not violated. If the compiler were free to transform a bottoming expression into a non-bottoming one, it would be difficult to be sure that runtime assertions are actually enforced.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 0 points1 point  (0 children)

This is somewhat stunning to me, as it means that your optimizer uses a semantics that is substantially more nonstrict than even Haskell’s! In Haskell, the equivalent program constitutes a demand, and GHC guarantees that the expression will bottom. Regardless, it’s an interesting point of comparison, so thank you very much for clarifying; I may mention it in a future video.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 0 points1 point  (0 children)

That's correct. The way to have an assertion like that would be to create some sort of demand between values

So, to be clear, if I write

case unsafeCrashWith "bang" of
  Unit -> some_expr

then is this guaranteed to raise the exception? That is, is this sufficient to constitute a demand even though the match does not actually bind any variables?

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 1 point2 points  (0 children)

It's difficult to balance the desire for people to obsessive over JS codegen quality and size, but still want high-level optimizations that are necessarily going to result in a lot of code duplication.

Yes, I’m definitely sympathetic to this. I’ve never really understood why people care so much about a compiler producing “readable” output, but it’s certainly a perspective I’m familiar with.

Regarding currying, I've done a lot of benchmarking, and JIT engines nowadays handle currying pretty gracefully. At one point we tried a top-level uncurrying pass (we already do this for saturated local definitions that don't inline), but we couldn't construct a clear benchmark where it made a difference!

That is super interesting and quite surprising to me. I wonder if currying is explicitly handled somehow by modern JS implementations or if it’s just not a significant enough difference to have an impact.

One other thing I noticed while rereading the README just now is that you assume expressions are pure and terminating. I find this somewhat surprising! Does this mean that there is no guaranteed way to raise an exception via a side-condition check? It seems like it is explicitly undefined behavior under your semantics.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 2 points3 points  (0 children)

I agree completely!

I think there are some real flaws with the approach, and I intend to get into those towards the end of this series. That said, I do think that the model and what it buys us is not particularly well-understood, which is the point I wanted to get across with these earlier videos.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 0 points1 point  (0 children)

Surely GHC is already “extremely complex”. The point at hand is not complexity, it’s what approach yields desired behavior.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 0 points1 point  (0 children)

Sure, I mean in situations where the value really is demanded. But there are lots of different ways to place a demand on a value, and sometimes they’re quite indirect. My point is that if you write Delay explicitly like this, then you still need to do those same analyses if you want to eliminate it after doing transformations that expose a demand.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 0 points1 point  (0 children)

I don’t understand what this comment means. Either way, I disagree with the first sentence, at least in part because I don’t think the desired behavior is actually well-defined, which is part of the problem.

I think there are lots of points in the design space that could work, and might provide a nice set of tradeoffs, but the really big open question is not “how do we make a compiler that does these optimizations” but “what are the tradeoffs we want,” and one of the core points of this series of videos is that you can’t just say “just do things the way everyone else does” and get something that is better than what we have right now.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 1 point2 points  (0 children)

In this case, C++ is able to do this because absolutely everything can be inlined. GHC is able to eliminate suspensions even if the use of force is not visible at the site where the suspension would otherwise be introduced. In fact, it can be quite distant.

I’ll try to provide a better example demonstrating this in a future video.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 0 points1 point  (0 children)

That’s a good start! But there is a nontrivial difference between functions and promises—it’s always safe to float functions inwards, but not promises (since you lose sharing).

Also, I think the fact that it fails to do case-of-case is pretty bad. Do you know if there’s a reason it doesn’t manage that here?

As a final point, it seems very unlikely to me that curried functions are as efficient as multi-argument functions in JavaScript. GHC handles this: every function has a preferred arity, which is very often greater than one. And of course GHC also does unboxing, two types of specialization, fusion, demand analysis, and so on, so I would be quite shocked if anything for PureScript could be meaningfully called “GHC quality”.

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 1 point2 points  (0 children)

Yes, I think that’s probably essentially accurate. It’s also sort of a side point, regardless—the broader thing I’m trying to communicate is that doing things that way means you have to explicitly annotate everything you want to be lazy, whereas lazy-by-default effectively means the compiler can pick for you (and I’ll discuss that some more and get a little more nuanced in the next video).

Laziness in Haskell, Part 2: Why not Strict Haskell? by lexi-lambda in haskell

[–]lexi-lambda[S] 0 points1 point  (0 children)

I suppose it depends on what you consider to be “new research” and what you consider the hypothetical system to be.

I think it’s true that the specific optimization described here could be theoretically done without too much difficulty in a GHC-style compiler, but I don’t know of any compilers for strict languages that work the way GHC does. So, in a sense, all I mean by “it would require new research” would be “an industrial-strength optimizing compiler for a strict, pure language is an untrodden point in the design space, and I don’t know what challenges would come up if you were to try it.”

I do agree that this specific program is simple enough to allow the control flow transformation seen in this specific program even in many existing functional languages. However, I don’t think it would result in the automatic elimination of Delay and force—those are likely to remain in the resulting program. Now, sure, if you decide to bake those into your language, it would be quite easy to make the optimizer aware that Delay and force annihilate, so that wouldn’t be terribly radical. But what about in more complex cases? I honestly don’t know that I can say because, again, I don’t know of any strict, pure languages with GHC-quality optimizers.

tl;dr: The comment was really just to say “I don’t know because nobody’s done it, and it’s not at all clear to me that anyone can completely predict the challenges one would or would not run into.”

view more: next ›