Возврат списка свободных (несвязанных) переменных в SML

Я создал свои собственные типы данных:

datatype typ = Bool | Int | Arrow of typ*typ;
(* i.e., Arrow(argType, returnType) *)
(* diMLazy expressions *)
datatype expr = TrueExpr
              | FalseExpr
              | IntExpr of int
              | VarExpr of string
              | PlusExpr of expr*expr
              | LessExpr of expr*expr
              | IfExpr of expr*expr*expr
              | ApplyExpr of expr*expr
              | FunExpr of string*string*typ*typ*expr

Используя их, мне нужно написать функцию isFV, которая возвращает список любых свободных переменных, переданных в функцию. Пока что мой код:

fun isFV (exp:expr) =
    let
      val bound_list = [];
    (*Contains returns true if x:string is within a string list.*)
      fun contains (i:string, str_list:string list) =
          foldr(fn (x,y) => i = x orelse y) false str_list;

      fun anaExp (ex:expr, aggr_list:string list) =
          case ex of 
              TrueExpr => []
            | FalseExpr => []
            | IntExpr (a) => []
            | PlusExpr (a, b) => anaExp(a,aggr_list) @ anaExp(b,aggr_list)
            | LessExpr (a, b) => anaExp(a,aggr_list) @ anaExp(b,aggr_list)
            | IfExpr (a, b, c) => anaExp(a,aggr_list) @ anaExp(b,aggr_list) @ anaExp(c,aggr_List)
            | ApplyExpr (a,b) => anaExp(a,aggr_list) @ anaExp(b,aggr_list)
            | FunExpr (a, b, c, d, e) => ??????
            | VarExpr (a) = if(contains (a,aggr_List)) then [] else [a]
    in
      anaExp(exp, bound_list)
    end

anaExp предназначен для первоначального взятия пустого списка и рекурсивного вызова самого себя, пока не получит термин VarExpr. Затем он добавит это в список aggr_list.

Как мне применить FuncExpr? Я знаю, чтобы использовать VarExpr в качестве строкового типа, но что я могу использовать в качестве типового типа? В настоящее время у меня есть:

|   FunExpr (a, b, c, d, e) => anaExp(VarExpr(a),aggr_list) @ anaExp(VarExpr(b),aggr_list) 
                                    @ anaExp(c,aggr_list) @ anaExp(d,aggr_list) @ anaExp(e,aggr_list)

Но мы знаем, что передача типа в anaExp вызовет ошибку типа (c и d).

Источник

2 ответа

[...] функция isFV, которая возвращает список любых свободных переменных, переданных в функцию.

Вот некоторые отзывы:

  • Это звучит как плохое имя для функции, которая возвращает список. Это звучит как хорошее имя для функции предиката, которая определяет, является ли что-то свободной переменной. Кроме того, функция кажется немного неясной. Я предполагаю, что это какое-то выражение isFV,

  • Я предполагаю что FunExpr это лямбда Например, выражение (λx.x+y) 5 кодируется как ApplyExpr (FunExpr ("x", ?, Int, Int, PlusExpr (VarExpr "x", VarExpr "y")), IntExpr 5),

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

    Если FunExpr такое лямбда, следует ли считать x свободной или связанной переменной в выражении (λx.x + y) x? Ясно, что x находится в разное время, но что должна возвращать функция?

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

    Но если переменная встречается в отдельных подвыражениях, все они включаются, например PlusExpr (VarExpr "a", VarExpr "a") будет производить ["a"] @ ["a"]потому что сводный список не обновляется между обращениями к подвыражениям.

  • Вы, кажется, не различаете свободные и связанные переменные. Предполагая, что FunExpr на самом деле создает связанную переменную, агрегированное состояние вашей рекурсивной функции должно быть немного сложнее, чтобы уловить различие:

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

  • Это может быть проще с заданным типом, чем с типом списка. В зависимости от вашего SML-компилятора может существовать встроенный тип набора. Например, в SML/NJ у вас есть функтор набора на основе списка:

    structure Set = ListSetFn(struct
                            type ord_key = string
                            val compare = String.compare
                          end)

Вот шаблон для одного решения:

fun getVars expr0 =
  let
    fun gv bound free expr =
        case expr of
            TrueExpr => (bound, free)
          | FalseExpr => (bound, free)
          | IntExpr => (bound, free)
          | VarExpr var => if Set.member (var, bound)
                           then ...
                           else ...
          | PlusExpr (a, b) =>
            let val (bound', free') = gv bound free a
                val (bound'', free'') = gv ... ... b
            in (..., ...) end
          | LessExpr (a, b) => ...
          | IfExpr (a, b, c) => ...
          | ApplyExpr (a, b) => ...
          | FunExpr (var, whatIsThis, _, _, a) =>
            let val bound' = Set.add (bound, var)
                val (bound'', free'') = gv ... ... a
            in (..., ...) end

    val (bound, free) = gv Set.empty Set.empty expr0
  in
    ...
  end

В этом думать о

  • когда обновлять связанные и бесплатные наборы, и
  • если / когда использовать возвращенные связанные и свободные множества.

Как мне применить FuncExpr?

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

что я использую в качестве типа шрифта?

Как сказал Ionuț, тип не имеет значения для вывода этой функции.

Источник

FunExpr дело должно увеличиваться aggr_list с именем параметра, который принимает функция. Я полагаю первый string из FunExpr это имя функции и второй string это имя параметра. Затем вы должны добавить это имя параметра в список связанных переменных, т.е. aggr_list, а затем повторить на теле функции. Вы можете спокойно игнорировать типы функций для этой проблемы.

Источник
Другие вопросы по тегам