2

What I am trying to build is a generic abstract syntax tree. I assume I have a fixed set of syntactic constructs and I define an F# type for each of them. However the representation of e.g. Identifier names and Expressions should be left open (generic). Thus the code will look something like:

module GAST =
    type Declaration<'Name, 'Expr> = 
    {
        id: 'Name
        initialValue: 'Expr
    }

    type Loop<'Name, 'Expr> =
    {
        condition: 'Expr
        body: Statement<'Name, 'Expr> list
    }

    and Statement<'Name, 'Expr> = 
    | Declaration of Declaration<'Name, 'Expr>
    ...
    | Loop of Loop<'Name, 'Expr>
    ...

You see the problem: I have lots of types, all parameterised by 'Name and 'Expr. When I want to "instantiate" my generic AST to a specific AST I would have to write a new module where I instantiate each individual type:

module SpecificAST =
    type Name = string
    type Expr = | Name of Name | Const of int | Addition of Expr * Expr

    type Declaration = GAST.Declaration<Name, Expr>
    type Loop = GAST.Loop<Name, Expr>
    type Statement = GAST.Statement<Name, Expr>

This seems like a lot of code duplication, and cries for something like a module that you could pass types as arguments, because I really just want something like

module SpecificAST = GAST<Name, Expr>

The above is not possible in F#. When searching I found Is it possible to pass parameters to F# modules? but there the issue is different. There is only one type definition but the behaviour of that type's functions is parameterised which can be solved by turning the record type into a class and pass the behaviour as an argument upon instantiation.

I have also seen Can ML functors be fully encoded in .NET (C#/F#)? but I did not see how the various links there could help me.

So my question is this: Given many generic types with the same type parameters. Can I instantiate all at once but avoid an awful code duplication in the instantiating module?

Friedrich Gretz
  • 535
  • 4
  • 14

1 Answers1

2

I think the solution you have is the best you can do with F# using your current way of structuring the problem - F# does not have ML functors and there is no universal way of simulating them.

That said, I would not be surprised if there was an alternative way of structuring the problem that would let you solve it in a nicer way. Your minimal example is good enough to see that you cannot simulate ML functors with F#, but it does not give enough details for alternative solutions:

  • How many specific ASTs are you planning to construct? Your example has just one, but even if you had three, it might well be easier to just duplicate the code rather than introducing abstractions that will not let you reuse much.

  • What do you want to do with the shared types? Are there some functions that will work for all the concrete ASTs? Perhaps there is another way that would let you reuse this functionality without having ML style functors.

So, I think the answer to your question is that your solution is the best you can do, but if you provided more information about the motivation for it, there might be a nicer F# design.

Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • The current implementation has two trees, untyped and typed. They have the same structure but differ in the representation of names, (source language) types and expressions. They both have (pre and post order) walkers that traverse the tree structure while executing some given actions. The question that came up was whether the common parts - the structure and its walkers - could be unified. Then the untyped and typed trees would merely be instances of the same AST with different implementations for names, (source language) types and expressions. Hence the proposed design. – Friedrich Gretz Sep 28 '17 at 11:36
  • Of course, the design is not the best solution anyway, because eventually I would like to play around with the language server interface of editors. For that, parts of the trees would need to be recomputed in real-time which probably requires a different setup altogether. – Friedrich Gretz Sep 28 '17 at 11:40