Выбор, использовать ли дискриминированные союзы или типы записей для небольшого AST в F #

Question

Допустим, я реализую очень простой парсер языка игрушек. Я решаю, использовать ли DU или типы записей (возможно, сочетание обоих?). Структура языка будет:

a Namespace consists of a name and a list of classes
a Class consists of a name and a list of methods
Method consists of a name, return type and a list of Arguments
Argument consists of a type and a name

Пример программы на этом простом языке:

namespace ns {
  class cls1 {
    void m1() {}
  }

  class cls2 {
    void m2(int i, string j) {}
  }
}

Как бы вы смоделировали это и почему?

Answer 1

Вы почти наверняка захотите использовать DU для реализации чередований, где любая часть структуры кода может быть одной из множества возможностей. Сочетание, вероятно, было бы идеальным, хотя вы могли бы использовать кортежи вместо записей - что может упростить их использование, но, возможно, сложнее читать и поддерживать, потому что у вас нет именованных элементов в кортежах.

Я бы смоделировал это как-то так

type CompilationUnit = | Namespace list

and Namespace = { Name : String
                  Body : NamespaceBody }

and NamespaceBody = | Classes of Class list

and Class = { Name : String
              Body : ClassBody }

and ClassBody = | Members of Member list

and Member = | Method of Method

and Method = { Name : String
               Parameters : Parameter list option
               ReturnType : TypeName option
               Body : MethodBody }

and Parameter = { Name : String
                  Type : TypeName }

and MethodBody = ...

and TypeName = ...

Потребность в DU может быть не очевидна при использовании вашего примера языка, но станет понятной, как только у вас появится какая-либо точка в коде, которая может быть одним или несколькими элементами. Скажем, например, если вы добавляете поля в свой класс - вам просто нужно добавить новую Field дискриминацию к Member.

Если вы используете грамматику для анализа вашего языка (LL / LALR или аналогичного), вам, вероятно, понадобится соответствующий DU для каждого правила чередования, которое есть в грамматике.

Answer 2

Пространство имен состоит из имени и списка классов Класс состоит из имени и списка методов Метод состоит из имени, типа возвращаемого значения и списка аргументов. Аргумент состоит из типа и имени Пример программы на этом простом языке:

Вам также нужно определение типа для вашей системы типов, и это фактически единственное место, где тип объединения имеет значение:

type Type = Void | Int | String

Таким образом, тип в вашем языке - это либо int, либо string, либо void, но не может быть ничем (например, null) и не может быть более одного из этих параметров.

Тип пространства имен может быть полностью анонимным, например:

string * (string * (Type * string * (Type * string) list) list) list

Вы можете определить свое примерное пространство имен следующим образом:

"ns", ["cls1", [Void, "m1", []]
       "cls2", [Void, "m2", [Int, "i"; String, "j"]]]

На практике вам, вероятно, понадобится возможность помещать пространства имен в другие пространства имен и помещать классы в классы, чтобы вы могли развить код в нечто вроде этого:

type Type =
  | Void
  | Int
  | String
  | Class of Map<string, Type> * Map<string, Type * (Type * string) list>

type Namespace =
  | Namespace of string * Namespace list * Map<string, Type>

Namespace("ns", [],
          Map
            [ "cls1", Class(Map[], Map["m1", (Void, [])])
              "cls2", Class(Map[], Map["m2", (Void, [Int, "i"; String, "j"])])])

Анонимные типы хороши, если они не будут источником путаницы. Как правило, если у вас есть два или три поля, и они имеют разные типы (например, «метод»), тогда кортеж - это хорошо. Если имеется больше полей или несколько полей одного и того же типа, то пришло время переключиться на тип записи.

Так что в этом случае вы можете ввести тип записи для методов:

type Method =
  { ReturnType: Type
    Arguments: (Type * string) list }

and Type =
  | Void
  | Int
  | String
  | Class of Map<string, Type> * Map<string, Method>

type Namespace =
  | Namespace of string * Namespace list * Map<string, Type>

Namespace("ns", [],
          Map
            [ "cls1", Class(Map[], Map["m1", { ReturnType = Void; Arguments = [] }])
              "cls2", Class(Map[], Map["m2", { ReturnType = Void; Arguments = [Int, "i"; String, "j"] }])])

и, возможно, вспомогательная функция для создания этих записей:

let Method retTy name args =
  name, { ReturnType = retTy; Arguments = args }

Namespace("ns", [],
          Map
            [ "cls1", Class(Map[], Map[Method Void "m1" []])
              "cls2", Class(Map[], Map[Method Void "m2" [Int, "i"; String, "j"]])])