I'm working on the crafting interpreters book and as a personal project I've decided to implement JLox on Go instead of Java mainly to learn Go. Currently I'm stuck with the parser, I'm unsure how to use the type system to build on the grammar. There are some clues here but I want to use types a la Haskell or Rust (maybe I'm mistaken here) .
So far this is what I've got:
package ast
import (
"golox/lexer"
)
type Stream interface {
Peek() lexer.Token
Next() lexer.Token
}
type TokenStream []lexer.Token
func (s *TokenStream) Peek() lexer.Token {
return (*s)[0]
}
func (s *TokenStream) Next() lexer.Token {
result := (*s)[0]
*s = (*s)[1:]
return result
}
type NUMBER struct {value float32}
type STRING struct {value string}
type NULL struct {value any}
type BOOL struct {value bool}
func (v NUMBER) Value() float32 {
return v.value
}
func (v STRING) Value() string {
return v.value
}
func (v BOOL) Value() bool {
return v.value
}
func (v NULL) Value() {
}
type Literal interface {
NUMBER | STRING | BOOL | NULL
}
type Expr interface {Literal | Unary | Binary | Grouping}
type Grouping[E Expr] struct {
right lexer.Token
left lexer.Token
expr *E
}
type Unary[E Expr] struct {
operator lexer.Token
expr *E
}
type Binary[E Expr] struct {
operator lexer.Token
left *E
right *E
}
func ParseType(s Stream) (err error) {
switch p:=s.Peek(); p {
}
return
}
My intent is to type check on the token stream and then join those tokens as expressions of different kinds. My main question lies on the types I've defined since the compiler complains that my definitions are invalid (I thought that providing a pointer as a field for the recursive type would suffice, but alas it doesn't). Any insight is appreciated! I know there probably is an implementation of this language in go but I would like to understand this problem before checking someone else's answer!
The compilation error is invalid recursive type Expr, and it is because you declare Expr as set of types, the type may be one of (Literal | Unary | Binary | Grouping) union. The compiler tries to resolve E at compile time based on the type constraint Expr, and because Expr contains Grouping, which creates a recursive type reference, leading to the error.
I thought that providing a pointer as a field for the recursive type would suffice, but alas it doesn't
You may wondering why it works
type A struct {
a *A
}
this is because The compiler knows exactly what *A is (pointer to A) if no generics involved whereas recursive type constraints are invalid even if you use pointer
In other language like Rust, we can define an enum type to describe all the possible expressions:
#[derive(PartialEq, Clone, Debug)]
pub enum Literal {
Bool(bool),
Number(String),
String(String),
Null,
}
#[derive(Debug, PartialEq)]
pub enum Expression {
Litera(Literal),
Grouping(Box<Expression>),
Unary(Token, Box<Expression>),
Binary(Box<Expression>, Token, Box<Expression>),
}
But since golang do not have enum type, the idiomatic way to implement it is using interface
var (
_ Expr = new(Literal)
_ Expr = new(Grouping)
_ Expr = new(Unary)
_ Expr = new(Binary)
)
type Expr interface {
Evaluate() string
}
type Literal struct {
Value string
}
func (l *Literal) Evaluate() string {
return l.Value
}
type Grouping struct {
Expr Expr
}
func (g *Grouping) Evaluate() string {
if g.Expr == nil {
return ""
} else {
return fmt.Sprintf("(group %s)", g.Expr.Evaluate())
}
}
type Unary struct {
Token *Token
Right Expr
}
func (u *Unary) Evaluate() string {
if u.Right == nil {
return ""
} else {
token := ""
if u.Token != nil {
token = u.Token.Data
}
return fmt.Sprintf("(%s %s)", token, u.Right.Evaluate())
}
}
type Binary struct {
Left Expr
Token *Token
Right Expr
}
type A struct {
a *A
}
func (b *Binary) Evaluate() string {
if b.Left == nil || b.Right == nil || b.Token == nil {
return ""
} else {
return fmt.Sprintf("(%s %s %s)", b.Token.Data, b.Left.Evaluate(), b.Right.Evaluate())
}
}