Ask HN: What data structure do I use for Lox AST in Rust?

2 points by backslash_16 4 years ago | 3 comments

I'm working through the excellent Crafting Interpreters book and learning Rust at the same time by writing the interpreter in the first part of the book in Rust. For anyone who hasn't read the book, you totally should!, you implement an interpreter for a made up dynamically typed language called Lox.

The scanner was relatively straightforward and now I'm having a hard time figuring out how I can implement a data structure to contain the AST for Lox. I'm pretty sure the core question is "How do I represent a tree of heterogeneous objects in Rust?"

In the book he uses polymorphism. There is a base class of Expression, with subclasses for each expression type.

At this point I think I'm holding Rust wrong and approaching the problem the wrong way. Potentially because I've used OOP for must of my life, with any functional-ish programming being pure functions, C#'s LINQ, and emulating concepts like free functions that act on data in C# or Java.

This is the specific part of the book where I'm having trouble. http://craftinginterpreters.com/representing-code.html#implementing-syntax-trees

I have the sense that I need to use a struct with an enum of expression type as the data field but I can't figure out to tie the data into it in a nice way. Is it as simple as having each variant of the enum contain the "complex" data structure that represents that expression kind?

Can someone poke or prod me in the right direction? I'm doing this for the sole purpose of learning so I don't necessarily want to be given the answer.

conradludgate 4 years ago |

Other than enums, there is another way to achieve a sort of polymorphism in Rust similar to how it's used in that compiler book.

You can use Traits to encapsulate an idea and implement them on Structs. You can then use `dyn Trait` to represent a type erased dynamic instance of that trait (similar to how abstract class instances are represented).

This has some benefits in libraries, allowing external parties ability to implement their own instances of traits, but in a compiler where you will implement all possibilities, its not as useful. You also lose the ability to match on variants (instead having to resort to downcasting)

conradludgate 4 years ago |

Enums are almost certainly the way to go here. Something like

    enum Expr {
        Literal(Literal),
        Binary(Op, Box<Expr>, Box<Expr>),
        //... 
    }

A value with type of Expr could be a literal or a binary expression. Binary expressions contain an operator and two other expressions (boxed to prevent infinite sized types).

This is the building block for your tree

backslash_16 4 years ago | |

Thanks, this makes a lot of sense. I'd like to think I was slowly closing in on this. Mine isn't as clean as what you put but I made the data within each of the enum possibilities a discrete struct.

  pub enum Expr {
      Binary(BinaryExpr),
      Grouping(GroupingExpr),
      LiteralBool(bool),
      LiteralNil,
      LiteralNumber(f32),
      LiteralString(String),
      Unary(UnaryExpr)
  }