3 ms·

In general I'm maybe somewhat disappointed that pattern matching in Rust can't be expressed more as a type system trait-type thing (hand waving here) that any s

In general I'm maybe somewhat disappointed that pattern matching in Rust can't be expressed more as a type system trait-type thing (hand waving here) that any struct could conform to, rather than an explicit first class hardcoded object type with its own storage structuring, etc? I may not be expressing this cogently, but. I've implemented both an AST (as in this article) and an opcode/bytecode interpreter recently, and I feel that in large part Rust's enums are not ideal for either: I never had the memory usage concerns about the AST that this author did, but I wanted to do things like: add a line number / column attribute to every statement node. I had a `Stmt` enum, and I had a choice: put line # and column on every enum possibility (boilerplate and ugly), or put the enum in a new Stmt struct that contains both the original enum and the line/col attributes -- which involved a bunch of refactoring and also didn't feel elegant. I feel there must be a more elegant type system way that my "Stmt" struct could have been reworked, that Rust isn't offering me. And re: the opcode stuff,I am fairly sure that a pattern-matched Rust enum is not an ideal encoding for a VM opcode interpreter performance wise. But the language really does want to point you in this direction, and the facilities for de-structuring patterns are very seductive. I haven't gotten to yak shaving this yet, but again I feel like there's likely some potential for improvements in the type system that could open things up so one could get pattern matching facilities while using one's own preferred lower level impl. I dunno. Thoughts.

aw1621107 3y ago
> pattern matching in Rust can't be expressed more as a type system trait-type thing (hand waving here) that any struct could conform to, rather than an explicit first class hardcoded object type with its own storage structuring, etc? Do you think you can provide a more concrete example? First thing that comes to mind for me is some kind of structural typing [0], but I'm not confident I'm interpreting your comment correctly. [0]: https://en.wikipedia.org/wiki/Structural_type_system https://en.wikipedia.org/wiki/Structural_type_system
- cmrdporcupine 3y ago
  Other people who are better with these things could probably conceptualize it better than me. What I'd like to be able to do is declare a trait that says "this thing can yield the following patterns, can destructure in this pattern, and these are the functions you'd call to extract references to those values" And then be able to use match on it as usual. Putting it another way, I wish an algebraic data type "enum" was something any struct could "be", with the type system providing the means to express that that's the case, and the programmer being able to provide the "how" and with existing Rust enums merely being the default way of doing this.
  - aw1621107 3y ago
    Interesting idea. I feel a bit conflicted about it, but it's probably something I'd have to think about. I suppose it's possible to somewhat approximate this in existing Rust by creating a trait with a function that returns a destructure-able type, performing the transformations that you would have implemented in your hypothetical trait, then pattern match over that. Not sure if that would be "good enough".
  - dan-robertson 3y ago
    Haskell and F# have this feature. In F# it is called active patterns. In Haskell the feature is pattern synonyms (maybe combined with view patterns) and is used to e.g. pattern match on the prefix or suffix of a sequence-like structure, or to match a tree as a an element and left/right node without the caller seeing a bunch of other tree metadata.
patrec 3y ago
Several languages have what I think you are asking for. Have a look at Scala's extractors or F#'s active views.
- foderking 3y ago
  you mean f# active patterns?
  - patrec 3y ago
    Sorry, yes.
- cmrdporcupine 3y ago
  Ah yes, many moons ago (like... almost 15 years) I worked in Scala and I recall extractors, or at least the discussion of them.
dan-robertson 3y ago
An old trick for bytecode interpreters is to use indirect jumps for going to the next opcode’s implementation (gcc had a ‘computed goto’ extension that was used for this. For Rust I guess you would want function pointers plus something to force TCE?) and putting those indirect jumps at the prelude of every opcode implementation. This meant that the indirect-jump-predictor (which cpus have because of oop) would have separate models for the ends of different opcodes and so would be more likely to predict correctly (maybe you have a hard time predicting a the next instruction but it is much more likely that a test is followed by a branch). I think other tricks (e.g. storing top of stack in registers for a stack machine) matter more though, and I don’t know if the trick described above is still relevant.
- AndyKelley 3y ago
  For Zig this is planned via labeled continue syntax inside switch expressions: https://github.com/ziglang/zig/issues/8220 https://github.com/ziglang/zig/issues/8220 As mentioned in the proposal, this would even allow implementation of Duff's Device in Zig :-o
- cmrdporcupine 3y ago
  Yeah I've spent time on this topic before when working in C++, but haven't invested much energy in thinking about how one would do it efficiently in Rust yet. Luckily performance is not my #1 concern, at least not yet. And maybe if I got down that road more I'd just invest in going JIT with cranelift or similar.
- dist1ll 3y ago
  Just to add some jargon for folks who want to do more research into this: The technique of having the interpreter dispatch duplicated in the postlude of each handler function is called "threading". If your dispatch uses an indirect jump, it's called "indirect threading". The indirect-jump-predictor is known as branch target predictor (BTB).

aw1621107 3y ago

> pattern matching in Rust can't be expressed more as a type system trait-type thing (hand waving here) that any struct could conform to, rather than an explicit first class hardcoded object type with its own storage structuring, etc? Do you think you can provide a more concrete example? First thing that comes to mind for me is some kind of structural typing [0], but I'm not confident I'm interpreting your comment correctly. [0]: https://en.wikipedia.org/wiki/Structural_type_system https://en.wikipedia.org/wiki/Structural_type_system

cmrdporcupine 3y ago
Other people who are better with these things could probably conceptualize it better than me. What I'd like to be able to do is declare a trait that says "this thing can yield the following patterns, can destructure in this pattern, and these are the functions you'd call to extract references to those values" And then be able to use match on it as usual. Putting it another way, I wish an algebraic data type "enum" was something any struct could "be", with the type system providing the means to express that that's the case, and the programmer being able to provide the "how" and with existing Rust enums merely being the default way of doing this.
- aw1621107 3y ago
  Interesting idea. I feel a bit conflicted about it, but it's probably something I'd have to think about. I suppose it's possible to somewhat approximate this in existing Rust by creating a trait with a function that returns a destructure-able type, performing the transformations that you would have implemented in your hypothetical trait, then pattern match over that. Not sure if that would be "good enough".
- dan-robertson 3y ago
  Haskell and F# have this feature. In F# it is called active patterns. In Haskell the feature is pattern synonyms (maybe combined with view patterns) and is used to e.g. pattern match on the prefix or suffix of a sequence-like structure, or to match a tree as a an element and left/right node without the caller seeing a bunch of other tree metadata.

patrec 3y ago

Several languages have what I think you are asking for. Have a look at Scala's extractors or F#'s active views.

foderking 3y ago
you mean f# active patterns?
- patrec 3y ago
  Sorry, yes.
cmrdporcupine 3y ago
Ah yes, many moons ago (like... almost 15 years) I worked in Scala and I recall extractors, or at least the discussion of them.

dan-robertson 3y ago

An old trick for bytecode interpreters is to use indirect jumps for going to the next opcode’s implementation (gcc had a ‘computed goto’ extension that was used for this. For Rust I guess you would want function pointers plus something to force TCE?) and putting those indirect jumps at the prelude of every opcode implementation. This meant that the indirect-jump-predictor (which cpus have because of oop) would have separate models for the ends of different opcodes and so would be more likely to predict correctly (maybe you have a hard time predicting a the next instruction but it is much more likely that a test is followed by a branch). I think other tricks (e.g. storing top of stack in registers for a stack machine) matter more though, and I don’t know if the trick described above is still relevant.

AndyKelley 3y ago
For Zig this is planned via labeled continue syntax inside switch expressions: https://github.com/ziglang/zig/issues/8220 https://github.com/ziglang/zig/issues/8220 As mentioned in the proposal, this would even allow implementation of Duff's Device in Zig :-o
cmrdporcupine 3y ago
Yeah I've spent time on this topic before when working in C++, but haven't invested much energy in thinking about how one would do it efficiently in Rust yet. Luckily performance is not my #1 concern, at least not yet. And maybe if I got down that road more I'd just invest in going JIT with cranelift or similar.
dist1ll 3y ago
Just to add some jargon for folks who want to do more research into this: The technique of having the interpreter dispatch duplicated in the postlude of each handler function is called "threading". If your dispatch uses an indirect jump, it's called "indirect threading". The indirect-jump-predictor is known as branch target predictor (BTB).