EOPL - 2.2.2 - Exercise 2.10

Chapter 2 includes examples and exercises for parsing and unparsing textual representations (e.g. parse-expression on page 51). The parsing functions assume a Scheme reader, and just convert from a list representation to an abstract syntax-tree representation based on define-datatype. The unparsing functions do the converse, from the syntax-tree representation to a list representation. As we don't have a list reader in F#, I skipped the examples and exercises related to parsing and unparsing. I also skipped other exercises that I felt wouldn't add much.

So here is Exercise 2.10 about generating fresh identifiers for renaming of variables that might be captured. I first defined a type for lambda-calculus expressions.

type Exp = Identifier of string | Lambda of string * Exp
        | App of Exp * Exp

Then there's all-ids and a converted version of fresh-id:

let rec all_ids exp =
   match exp with
     Identifier i -> [i]
   | Lambda (x, e) -> x :: (all_ids e)
   | App (e1, e2) -> (all_ids e1) @ (all_ids e2)
  
let fresh_id exp s =
   let syms = all_ids exp in
   let rec loop n =
       let sym = s + (string_of_int n) in
       if List.mem sym syms then loop (n + 1)
       else Identifier sym in
   loop 0