Тип данных для условий над подписью в SML - PullRequest
Новая
       10

Тип данных для условий над подписью в SML

0 голосов
/ 14 марта 2011

Я хочу реализовать произвольную подпись в SML.Как определить тип данных для терминов над этой подписью? Мне понадобится написать функции, которые проверяют, правильно ли сформированы термины.

1 Ответ

1 голос
/ 17 марта 2011

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

Если мы определим следующий BNF (извлеченный из определения SML и слегка упрощенный) 

<exp> ::= <exp> andalso <exp>
        | <exp> orelse <exp>
        | raise <exp>
        | <appexp>

<appexp> ::= <atexp> | <appexp> <atexp>

<atexp> ::= ( <exp>, ..., <exp> )
          | [ <exp>, ..., <exp> ]
          | ( <exp> ; ... ; <exp> )
          | ( <exp> )
          | ()

Как уже говорилось, это упрощено, и большая часть atexp опущена.

1. Серия возможных взаимно рекурсивных типов данных

Здесь вы, например, создадите тип данных для выражений, объявлений, шаблонов и т. Д. Обычно вы создаете тип данных для каждого нетерминала в вашем BNF.

Скорее всего, мы создадим следующие типы данных 

datatype exp = Andalso of exp * exp
             | Orelse of exp * exp
             | Raise of exp
             | App of exp * atexp
             | Atexp of atexp

and atexp = Tuple of exp list
          | List of exp list
          | Seq of exp list
          | Par of exp
          | Unit

Обратите внимание, что нетерминал использовался в типе данных exp вместо того, чтобы иметь его как свой собственный. Это просто загромождает AST без причины. Вы должны помнить, что BNF часто пишется таким образом, что он также определяет прецеденты и ассоциативность (например, для арифметики). В таких случаях вы часто можете упростить BNF, объединив несколько нетерминалов в один тип данных.

Хорошая вещь в определении нескольких типов данных состоит в том, что вы как бы хорошо разбираетесь в своем AST. Если, например, у нас также был нетерминал для объявлений, мы знаем, что AST будет содержать объявление внутри списка (поскольку там могут быть только выражения). Из-за этого большинство из вас хорошо проверено на правильность.

Это, однако, не всегда хорошо. Часто вам все равно нужно выполнить некоторую проверку AST, например, проверку типа. Во многих случаях BNF довольно велик, и, следовательно, число типов данных, необходимых для моделирования AST, также довольно велико. Помня об этом, вы должны создать одну функцию для каждого из ваших типов данных, для каждого типа изменений, которые вы не хотите делать в своем AST. Во многих случаях вам не нужно изменять только небольшую часть вашего AST, но вам (скорее всего) все равно нужно будет определить функцию для каждого типа данных. Большинство этих функций будут в основном идентичными, и тогда только в нескольких случаях вы будете выполнять желаемую работу.

Если, например, мы не хотим считать, сколько единиц в данном AST, мы можем определить следующие функции 

fun countUnitexp (Andalso (e1, e2)) = countUnitexp e1 + countUnitexp e2
  | countUnitexp (Orelse (e1, e2)) = countUnitexp e1 + countUnitexp e2
  | countUnitexp (Raise e1) = countUnitexp e1
  | countUnitexp (App (e1, atexp)) = countUnitexp e1 + countUnitatexp atexp
  | countUnitexp (Atexp atexp) = countUnitatexp atexp

and countUnitatexp (Tuple exps) = sumUnit exps
  | countUnitatexp (List exps) = sumUnit exps
  | countUnitatexp (Seq exps) = sumUnit exps
  | countUnitatexp (Par exp) = countUnitexp exp
  | countUnitatexp Unit = 1

and sumUnit exps = foldl (fn (exp,b) => b + countUnitexp exp) 0 exps

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

2. Один (большой) тип данных (узлы) - и дерево этих узлов

Позволяет объединить типы данных из предыдущих, но изменить их так, чтобы они не содержали своих детей. Потому что в этом подходе мы строим древовидную структуру, которая имеет узел и несколько дочерних элементов этого узла. Очевидно, что если у вас есть идентификатор, то идентификатор должен содержать фактическое строковое представление (например, имя переменной).

Итак, давайте начнем с определенных узлов для древовидной структуры. 

(* The comment is the kind of children and possibly specific number of children
   that the BNF defines to be valid *)
datatype node = Exp_Andalso   (* [exp, exp] *)
              | Exp_Orelse    (* [exp, exp] *)
              | Exp_Raise     (* [exp] *)
              | Exp_App       (* [exp, atexp] *)
(* Superflous:| Exp_Atexp     (* [atexp] *) *)
              | Atexp_Tuple   (* exp list *)
              | Atexp_List    (* exp list *)
              | Atexp_Seq     (* exp list *)
              | Atexp_Par     (* [exp] *)
              | Atexp_Unit    (* [] *)

Посмотрите, как Atexp из tupe теперь становится излишним, и, таким образом, мы удаляем его. Лично я думаю, что было бы хорошо иметь следующий комментарий, сообщая, каких детей (в древовидной структуре) мы можем ожидать. 

(* Note this is a non empty tree. That is you have to pack it in an option type
   if you wan't to represent an empty tree *)
datatype 'a tree = T of 'a * 'a tree list

(* Define the ast as trees of our node datatype *)
type ast = node tree

Затем мы определяем общее дерево и определяем тип ast как «дерево узлов». Если вы используете какую-то библиотеку, есть большая вероятность, что такая древовидная структура уже существует. Также может оказаться удобным позднее расширить эту древовидную структуру, чтобы она содержала больше, чем просто узел в качестве данных, однако здесь мы просто оставим это простым. 

fun foldTree f b (T (n, [])) = f (n, b)
  | foldTree f b (T (n, ts)) = foldl (fn (t, b') => foldTree f b' t) 
                                      (f (n, b)) ts

Для этого примера мы определяем функцию сгиба для дерева, опять же, если вы используете библиотеку, то все эти функции для свертывания, отображения и т. Д., Скорее всего, уже определены. 

fun countUnit (Atexp_Unit) = 1
  | countUnit _ =  0

Если мы затем возьмем пример из предыдущего, что мы не хотим подсчитывать количество вхождений единицы, мы можем просто сложить вышеуказанную функцию над деревом. 

val someAST = T(Atexp_Tuple, [ T (Atexp_Unit, [])
                             , T (Exp_Raise, [])
                             , T (Atexp_Unit, [])
                             ]
               )

Простой AST может выглядеть так, как указано выше (обратите внимание, что это на самом деле неверно, поскольку у нас есть Exp_Raise без дочерних элементов). И тогда мы могли бы сделать подсчет по 

foldTree (fn (a,b) => (countUnit a) + b) 0 someAST

Недостатком этого подхода является то, что вам нужно написать функцию проверки, которая проверяет, правильно ли сформирован ваш AST, поскольку нет никаких ограничений при создании AST. Это включает в себя то, что дочерние элементы имеют правильный «тип» (например, только Exp_ * как дочерние элементы в Exp_Andalso) и что существует правильное число дочерних элементов (например, точно два дочерних элемента в Exp_Andalso).

Этот подход также требует небольшого труда для начала, поскольку вы не используете библиотеку, для которой определено дерево (включая вспомогательные функции для модификации дерева). Однако в конечном итоге это окупается.

...