TigerBook/PROGRAM1

Chapter 1 の PROGRAM

導入部なので概要説明と思ったらいきなりプログラムを書かせるあたり なかなか鬼。SML に慣れておけ、と言う意味もあるのだろう。

教科書では以下の型定義と

type id = string
datatype binop = Plus | Minus | Times | Div
datatype stm =
        CompoundStm of stm * stm
      | AssignStm   of id * exp
      | PrintStm of exp list
    and exp =
        IdExp of id
      | NumExp of int
      | OpExp of exp * binop * exp
      | EseqExp of stm * exp

以下の構文木が与えられている。

val prog =
   CompoundStm( AssignStm( "a", OpExp(NumExp 5, Plus, NumExp 3)),
		 CompoundStm(
		   AssignStm(
		     "b",
		     EseqExp( PrintStm [IdExp "a",
					OpExp( IdExp "a", Minus, NumExp 1)],
			      OpExp( NumExp 10, Times, IdExp "a" ))),
		   PrintStm[IdExp "b"]))

PROGRAM 1

構文木に含まれる print の引数の最大値を求める。

fun maxargs stm =
   let
	fun max a b = if a > b then a else b
	fun max_stm_rec m stm =
	    case stm of
		CompoundStm (u,v) => max (max_stm_rec m u) (max_stm_rec m v)
	      | AssignStm (i,e) => max_exp_rec m e
	      | PrintStm el => max_expl_rec m 0 el
	and max_exp_rec m exp =
	    case exp of
		IdExp i => m
	      |	NumExp n => m
	      | OpExp (e1,b,e2) => max (max_exp_rec m e1) (max_exp_rec m e2)
	      | EseqExp (s,e) => max (max_stm_rec m s) (max_exp_rec m e)
	and max_expl_rec m p elist =
	    case elist of
		[] => max m p
	      |	hd::tl => max_expl_rec (max_exp_rec m hd) (p+1) tl
   in
	max_stm_rec 0 stm
   end

PROGRAM 2

与えられた構文木を翻訳実行する。 書いてから思ったけど print ERROR してるところは exception 〜 raise のほうがいいね。 (文法を調べずに書いたんで。あは。)

fun interp stm =
   let
	fun searchenv env key =
	    case env of
		(i,v)::tl => if i = key then v else searchenv tl key
	      | [] =>(print "ERROR\n";0)
	fun stm_rec env stm =
	    case stm of
		CompoundStm (u,v) => stm_rec (stm_rec env u) v
	      | AssignStm (i,e) => let val (env_new, evald) = exp_rec env e in
				       (i, evald) :: env_new
				   end
	      | PrintStm el => let val env_new = pr_expl_rec env el in
				   print "\n"; env_new
			       end
	and exp_rec env exp =
	    case exp of
		IdExp i => (env, (searchenv env i))
	      |	NumExp n => (env, n)
	      | EseqExp (s,e) => exp_rec (stm_rec env s) e
	      | OpExp (e1,b,e2) =>
		let val (env_new1, e1d) = exp_rec env e1 
		    val (env_new2, e2d) = exp_rec env_new1 e2 in
		    case b of
			Plus  => (env_new2, e1d + e2d)
		      | Minus => (env_new2, e1d - e2d)
		      | Times => (env_new2, e1d * e2d)
		      | Div   => (env_new2, e1d div e2d)
		end
	and pr_expl_rec env elist =
	    case elist of
	    	hd::tl => let val (env_new, evald) = exp_rec env hd in
			      print ((Int.toString evald)^" ");
			      pr_expl_rec env_new tl
			  end
	      | [] => env
   in
	stm_rec [] stm
   end