Return a list of free(unbound) variables in SML

Question

I've created my own datatypes:

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

Using these, i need to write a function isFV that returns a list of any free variables passed into the function. So far, my code is:

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 is meant to initially take an empty list and recursively call itself until it gets a VarExpr term. It'll then add that to aggr_list.

How do i apply the FuncExpr? I know to use the VarExpr as a string type, but what do i use as a typ type? Currently i have:

|   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)

But we know that passing a typ into anaExp will cause a type error (c and d).

Answer 1

[...] a function isFV that returns a list of any free variables passed into the function.

Here is some feedback:

• That sounds like a bad name for a function that returns a list. It sounds like a good name for a predicate function that determines whether something is a free variable. Also, the function seems a bit unclear. I assume it is any expression fed to isFV.

• I assume that FunExpr is a lambda. For example, the expression (λx.x+y) 5 is encoded as ApplyExpr (FunExpr ("x", ?, Int, Int, PlusExpr (VarExpr "x", VarExpr "y")), IntExpr 5).

  I'm not sure what the second string parameter in FunExpr is used for. Maybe it's either a named or an anonymous function? That should probably make one of the parameters a string option...

  If FunExpr is a lambda, should x be considered a free or a bound variable in the expression (λx.x+y) x? Clearly, x is both at different times, but what should the function return?

• You have a fine basic strategy: a recursive function that traverses expressions and keeps an "aggregated list" of variables that have been seen in sub-expressions. If an expression is seen again, it is not included the second time.

  But if a variable occurs in separate sub-expressions, they are all included, e.g. PlusExpr (VarExpr "a", VarExpr "a") would produce ["a"] @ ["a"], because the aggregated list is not updated between calls to sub-expressions.

• You don't seem to differentiate between free and bound variables. Assuming that a FunExpr actually creates a bound variable, the aggregated state of your recursive function must be a little more complex to catch the distinction:

  A variable is not just free because it's a variable, but because it hasn't occurred as a bound variable in the current scope (maintained by some set of currently bound variables).

• It might be easier with a set type rather than the list type. Depending on your SML compiler, there might be a built-in set type. In SML/NJ, for example, you have a list-based set functor:

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

Here is a template for one solution:

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

In this, think of

• when to update the bound and free sets, and
• if/when to use the returned bound and free sets.

How do i apply the FuncExpr?

I don't understand that question. If you mean how you write the FunExpr clause in your function, you have to specify what it's trying to achieve to get any sensible feedback. So far, there has been a bit of guesswork on my side as to what these constructors are supposed to do.

what do i use as a typ type?

As Ionuț said, the type does not matter for the output of this function.

Answer 2

The FunExpr case is supposed to augment aggr_list with the name of the parameter that the function takes. I presume the first string of FunExpr is the function name and the second string is the parameter name. You should then add this parameter name to the list of bound variables, i.e., aggr_list, and then recurse on the function's body. You can safely ignore the function's types for this problem.