(* A demonstartion of how to express mathematical semantics in SML as directly as possible. (1) Forget about parsing, if at all possible, or delay it Think of this as providing "Syntactic Sugar" for the user. (2) Define Abstract syntax as an ML datatype (3) Define compositional semantics using ML functions Example. The Binary Numbers Exercise. How about Decimal Numbers *) datatype Bit = One | Zero; (* Ullman Page 118*) datatype Num = S of Bit | P of Num * Bit; (* Ullman page 120 *) fun N(S(Zero)) = 0 | N(S(One) ) = 1 | N(P(n:Num,Zero)) = 2 * N(n) | N(P(n:Num,One )) = 2 * N(n) + 1; "N(0)"; N(S(Zero)); "N(\"010\")\n\t"; N(P(P(S(Zero),One),Zero)); (* Also see Page 142..143, Boolean Expressions...*) (* For those who need sugar....*) (* does not have a string constructor so we can not use string patern matching. One approach is to convert strings to lists and then pattern match as follows *) fun parse_list(["0"]) = S(Zero) | parse_list(["1"])=S(One) | parse_list("0"::rest)=P(parse_list(rest),Zero) | parse_list("1"::rest)=P(parse_list(rest),One); fun parse(s:string)=parse_list(rev(explode(s))); parse("010"); N(parse("010")); (* Or you can go for a more trad approach like the following *) fun parse2(s:string):Num = if s="0" then S(Zero) else if s="1" then S(One) else let val n = size(s); val front=substring(s,0,n-1); val last=substring(s,n-1,1) in if last="0" then P(parse2(front), Zero) else P(parse2(front), One) end; parse2("010"); N(parse2("010"));