0

I'm designing the AST for a compiler and found that I don't actually know how to represent the Call node.

Currently, the relevant part of the AST looks like this (where the arrows denote inheritance):

ASTNode -> Expression  -> Call
        -> Declaration -> Statement -> Call
                       -> TypeDeclaration, etc...

For example,

// this is a declaration 
def f(x: Integer from 0 to 16) - > {
    // This is a call that is also a statement
    print(x)
}

How do I reconcile these two definitions of Call? In this particular grammar, the only expression that is also a statement is Call. The language I'm using only supports single inheritance.

Is there a way to sidestep this problem entirely without compromising on the type safety of a heterogeneous AST?

As a side note, any additional reading you can recommend would be great.

  • Could you add some pseudo-code examples? E.g. in most languages, a function call is not a declaration. So it's not clear to me how an expression-call differs from a statement-call? – amon May 4 '18 at 10:58
  • I'm basing it off the idea that everything is a declaration (you declare that an action is to take place). Even if statements were considered the 'base' type, the problem would still exist. – Straivers May 4 '18 at 13:08
  • Why do you have both expressions and statements in your language? It is simpler to have only expressions (like in Scheme, Ocaml, ...) -perhaps side effecting ones- and avoid statements entirely – Basile Starynkevitch May 4 '18 at 15:06
  • 1
    Recommended readings: Scott's Programming Language Pragmatics, the Dragon Book, SICP, Lisp In Small Pieces – Basile Starynkevitch May 4 '18 at 15:21
  • @Basile I want to avoid delimiters as much as possible. Doing it this way allows me to use a model similar to Lua, where only specific productions can begin or end an expression or statement. – Straivers May 5 '18 at 2:40
4

The AST is a bridge between the concrete syntax and the semantic model of your language. It does not have to conform exactly to the syntax. In particular, it is generally OK if the AST could theoretically represent structures that cannot be rendered in the syntax. (Notably, the reStructured Text markup language is defined in terms of a document object model that is substantially more expressive than the actual syntax.)

Therefore, you could introduce an expression-statement AST node, even though the syntax constrains this expression to be a call. This is sensible if statement-calls and expression-calls do not have to be treated differently in your language.

An example where statements and expressions do have to be treated differently is a function definition in JavaScript. Roughly, the statement function foo() {} declares a foo variable that holds a function object. The same definition in an expression will not introduce a variable in the enclosing scope, and evaluates to that function object.

It could then be sensible to represent this using different types, e.g. FunctionExpression versus FunctionStatement. This does not have to lead to excessive duplication! E.g. the statement variant could contain a FunctionExpression object. Alternatively, the function statement could be immediately desugared in the AST to something like Assign(Var("foo"), Function(...)) where the Function AST node only has to model the expression variant.

So in your case, introducing a CallStatement AST node that merely contains the Call expression AST node could be a viable approach.

Note that type safety is relative, anyway. By using inheritance to model your AST nodes, your type system is allowing arbitrary new AST node types as long as they conform to some interface. E.g. it would be possible to create an expression subtype that serves as an adapter to any declaration, even though that seems to make little sense in your model. If you need stricter guarantees, you will have to avoid open inheritance and use a language with more constrained sum types.

  • "By using inheritance to model your AST nodes, your type system is allowing arbitrary new AST node types as long as they conform to some interface." – This depends on the language, I would say. There are languages in which you can constrain inheritance. – Jörg W Mittag May 4 '18 at 17:13
  • 1
    @JörgWMittag yes, Scala comes to mind as you can restrict inheritance to the current file. Other languages like Java have tricks with private constructors + nested classes. But e.g. Scala does give you the benefits of real sum types, like warnings for non-exhaustive pattern matching. – amon May 4 '18 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.