12 ms·
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
by pcwalton 11y ago
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.
- tptacek 11y agoOk, 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.)
- pcwalton 11y agoSure, 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.
- tptacek 11y agoWould 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?
- pcwalton 11y agoYup, 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 https://crates.io/crates/typed-arena/1.0.1
- MichaelGG 11y agoF# 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 https://msdn.microsoft.com/en-us/library/dd233248.aspx
- ignoramous 11y agoOkay, an off-topic question: Can you pls briefly explain Golang-emulators-fit? Links to projects/blogs would help too. Thx.
- jackpirate 11y agoIn what ways is OCaml's pattern matching superior to Haskell's?
- pcwalton 11y agoOr patterns. See http://stackoverflow.com/questions/24700762/or-patterns-in-haskell http://stackoverflow.com/questions/24700762/or-patterns-in-h...
- tikhonj 11y agoOn 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_guide/syntax-extns.html#pattern-synonyms https://downloads.haskell.org/~ghc/latest/docs/html/users_gu...
- barosl 11y agoI'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?
- dragonwriter 11y ago> 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/OrPatterns.html https://hackage.haskell.org/package/OrPatterns-0.1/docs/OrPa... [1] https://ghc.haskell.org/trac/ghc/ticket/3919 https://ghc.haskell.org/trac/ghc/ticket/3919
- marijn 11y agoI'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?).