`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:

Post a Comment