Hacker News Reader

Comment by pcwalton | Hacker News Reader

In addition to what the other commenter said, pattern matching is really nice for this kind of thing. Of all of the functional programming languages, OCaml has probably the most sophisticated pattern matching engine around (and we basically copied it into Rust, incidentally), supporting or-patterns, multiple bindings, guards, and so forth. Pattern matching lets you essentially match on the shape of subtrees of arbitrary data structures with complex predicates.

If you're familiar with old-school compiler construction, this is like having a souped-up BURG built into the language. For example, pattern matching lets you say things like "if I have Load(Var, Add(Var, Constant)) where constant is a small power of two, fold it into the x86 indexed addressing mode" in one line. Unsurprisingly this is useful not only for compiler construction but for any kind of term rewriting/symbolic manipulation.

View on HN

Ok, tangent question: if I wanted an interesting project to learn Rust with, would a symbolic evaluation checker for (say) C code be a really good fit? In the same sense as emulators turned out to be a fantastic fit for Golang?

If that's true, what are the features of Rust that make this so, and roughly how would they apply to that problem domain? (I could answer that question for Golang and emulators pretty quickly).

(Hopefully this question comes across the way I intend it to, which is: I have no plans on using OCaml any time soon, believe the comments that say you want a language with pattern matching to do this in, and would love to tinker more with both Rust and symbolic evaluation.)

Sure, I think it'd be a fun project to try! We use Rust for compiler construction, obviously, and it works great for us. Bear in mind, though, that Rust is manually memory managed, and there is significant cognitive overhead of having a compiler that checks that you're doing the manual memory management properly as opposed to just using a GC.

I think if you want a really fast symbolic evaluation checker—say, the kind that you're going to run on $BIG_COMPANY's codebase on every checkin—Rust would be a really good fit, because you get pattern matching and excellent performance. Other than OCaml and (maybe?) F#, I don't know of a language that has as sophisticated a pattern matcher as Rust does, which helps a lot with this stuff. But, if you're building a one-off tool, a more dynamic language with a GC might be more convenient.

Would it be likely that I could get around that problem just by using arena allocation? Do you think the allocation patterns of a symbolic checker fit that sort of "just allocate everything and forget about it, then free it all at once" pattern? Does Rust make it easy to punt that way?

Yup, you can use arenas for that, and in fact that is likely what I'd do. There's an arena crate on crates.io. https://crates.io/crates/typed-arena/1.0.1

F# has Active Patterns, which really rock. They let you define custom patterns or destructuring functions, then use them like normal patterns.

https://msdn.microsoft.com/en-us/library/dd233248.aspx

Okay, an off-topic question: Can you pls briefly explain Golang-emulators-fit? Links to projects/blogs would help too. Thx.

In what ways is OCaml's pattern matching superior to Haskell's?

Or patterns.

See http://stackoverflow.com/questions/24700762/or-patterns-in-h...

On the flipside, Haskell just got pattern synonyms[1] which are incredibly useful for being able to refactor and work with abstract types.

It also has view patterns which are quite useful. I don't know how to replicate that in OCaml.

Combining the two lets types expose fairly sophisticated interfaces as normal patterns, which is incredibly useful for things like graphs.

[1]: https://downloads.haskell.org/~ghc/latest/docs/html/users_gu...

I'm mildly surprised, why isn't this a thing in Haskell? Can't it be easily added, considering an or pattern is trivially expanded to two (or more) patterns?

I've been surprised/annoyed by this as well. My conclusion was that there are no practical problems that would make this hard, and it is most likely held back simply by the theoretical trivialness of it (what academic wants to work on something that doesn't make a good paper?).

I've heard that or-patterns can result in superlinear blowup in the number of cases, which is why Haskell compilers have not implemented it so far.

As far as I know, that's never really been a reason as to why we haven't implemented it in GHC. It's much more likely just that nobody has ever gotten around to implementing it. Shouldn't be especially hard, I imagine.

How so? There's one case per branch. It's no more blowup than writing out the branches by hand would be.

> Can't it be easily added, considering an or pattern is trivially expanded to two (or more) patterns?

At least limited support has been done as a library providing a quasiquoter [0], and there is an open ticket for it as a ghc feature. [1]

[0] https://hackage.haskell.org/package/OrPatterns-0.1/docs/OrPa...

[1] https://ghc.haskell.org/trac/ghc/ticket/3919

Reply on news.ycombinator.com