Sunday, December 31, 2006

EOPL - 1.2.2 - Some Important Examples

The first 2 chapters of the book are quite basic, but in this section we get some interesting tidbits regarding static versus dynamic typing.

Beginning with two easy functions, remove and remove-first. The type definition for a list of symbols is

<list-of-symbols> ::= [] | <symbol> :: <list_of_symbols>

And the implementation of the functions are:

let rec remove_first s los =
match los with
[] -> []
| (smb :: los') when smb = s -> los'
| (smb :: los') -> smb :: (remove_first s los')

let rec remove s los =
match los with
[] -> []
| (smb :: los') when smb = s -> remove s los'
| (smb :: los') -> smb :: (remove s los')

Of course, the structural equality operator (=) here implies that these functions work not only with lists of symbols, but lists of any type. The type checker correctly infers the type 'a -> 'a list -> 'a list for both lists. In Scheme too it's possible to get generic functions using the structural equality function equal? -- and as it is the function is guaranteed to work with symbols, numbers and characters because it uses eqv? -- but the authors probably didn't want to talk about parametric polymorphism at this point in the discussion.

Now to two more functions, subst and notate-depth, that work on symbol expressions. A symbol expression is either a symbol or a list of symbol expressions, called an slist:

<s-list> ::= [] | <symbol-expression> :: <s-list>
<symbol-expression> ::= <symbol> | <s-list>

So now we can't directly define in F# functions that work either on a symbol or a list of similar data. We must define a new type that is a disjoint union of symbols and lists of symbol expressions:

type SymbolExp = Symbol of string | SList of SymbolExp list

And now define the function subst as in the book:

let rec subst n old slist =
match slist with
[] -> []
| (s :: sls) -> (subst_in_symbol_expression n old s) ::
(subst n old sls)
and subst_in_symbol_expression n old sexp =
match sexp with
Symbol s when s = old -> Symbol n
| Symbol s -> Symbol s
| SList sl -> SList (subst n old sl)

Note that subst receives plain strings as the new and old parameters, not a Symbol str where str is a string. Also, the list that subst receives is a SymbolExp list and not a SymbolExp that is a SList. The former fact is a difference in relation to the Scheme version (but could easily be changed) and the latter is consistent with the Scheme version; both may seem a bit confusing.

For notate-depth there's still another problem: the values returned by it are not really slists. While in Scheme this causes no problem, in F# we have to define a new type that includes the depth information with every symbol. So we get

type NotatedSymbolExp = NSymbol of string * int
| NSList of NotatedSymbolExp list

And finally, the function:

let rec notate_depth_in_slist slist n =
match slist with
[] -> []
| (s :: sls) -> (notate_depth_in_symbol_expression s n) ::
(notate_depth_in_slist sls n)
and notate_depth_in_symbol_expression sexp n =
match sexp with
Symbol s -> NSymbol (s, n)
| SList sl -> NSList (notate_depth_in_slist sl (n + 1))

let notate_depth slist = notate_depth_in_slist slist 0


The rest of the code are solutions to the exercises that require coding.

Exercise 1.11

let rec subst n o slist =
match slist with
[] -> []
| ((Symbol s)::sls) when s=old -> ((Symbol n)::subst n o sls)
| ((SList sl)::sls) -> ((SList (subst n o sl))::subst n o sls)
| (s::sls) -> s :: subst n o sls


Exercise 1.12

let rec subst_in_symbol_expression n old sexp =
match sexp with
Symbol s when s = old -> Symbol n
| Symbol s -> Symbol s
| SList sl -> SList (subst3 n old sl)
and subst n old slist =
List.map (subst_in_symbol_expression n old) slist


Exercise 1.13

let rec notate_depth_in_slist slist n =
List.map (notate_depth_in_symbol_expression n) slist
and notate_depth_in_symbol_expression n sexp =
match sexp with
Symbol s -> NSymbol (s, n)
| SList sl -> NSList (notate_depth_in_slist sl (n + 1))

No comments: