Tuesday, February 20, 2007

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

No comments: