Index: doc/eval.html
==================================================================
--- doc/eval.html
+++ doc/eval.html
@@ -130,11 +130,11 @@
 
 </td></tr>
 		<tr><td id="docfooter">
 			Page was generated with
 			<img src="candydoc/img/candydoc.gif" style="vertical-align:middle; position:relative; top:-1px">
-			on Sat Nov 27 23:29:17 2010
+			on Sun Nov 28 07:28:21 2010
 
 		</td></tr>
 	</table>
 </div>
 <script>

Index: doc/index.html
==================================================================
--- doc/index.html
+++ doc/index.html
@@ -32,10 +32,15 @@
 レイヤ機能を入れたら自動的にすごく自然にマクロが入るなーと思って、
 おまけで実装してみた程度のものです。
 あんまり重要ではないので、適当にスルーして下さいませ。
 単に、適当に入れたら適当で微妙な部分が多く残ってしまったので注意書きが増えているだけで…。
 </p>
+<p>
+言い訳ついでにもう一つ言い訳ですが、この言語は、少なくとも今のところ、
+実用に使うことを考えた設計にはなっていません。どちらかというと、
+Brainfuck や Unlambda や Whitespace の仲間と思ってお使い下さい。
+</p>
 
 
 <script>explorer.outline.incSymbolLevel();</script>
 <dl>
 <script>explorer.outline.writeEnabled = true;</script>
@@ -674,11 +679,11 @@
     @@type = fun(x) {
        if( _isint(x) ) then "int"
        else if( _isstr(x) ) then "str"
        else if( _isbot(x) ) then "runtime error"
        else "type error"
-    }
+    };
 </pre>
 <pre>
     &gt;&gt; @type( 1 )
     int
     &gt;&gt; @type( 2 )
@@ -723,11 +728,11 @@
    @type "if" (c, t, e) {@value(
       if( @type(c)=="int" || @type(c)=="runtime error" ) then
          @type( int_int_int(t(), e()) )
       else
          "type error"
-   )}
+   )};
 </pre>
 <p>
 関数が自動リフトされるので、フィボナッチ関数の型を調べることができます。
 </p>
 <pre>
@@ -1154,11 +1159,11 @@
 
 </td></tr>
 		<tr><td id="docfooter">
 			Page was generated with
 			<img src="candydoc/img/candydoc.gif" style="vertical-align:middle; position:relative; top:-1px">
-			on Sun Nov 28 00:45:59 2010
+			on Sun Nov 28 07:29:42 2010
 
 		</td></tr>
 	</table>
 </div>
 <script>

Index: index.dd
==================================================================
--- index.dd
+++ index.dd
@@ -15,10 +15,15 @@
 レイヤ機能を入れたら自動的にすごく自然にマクロが入るなーと思って、
 おまけで実装してみた程度のものです。
 あんまり重要ではないので、適当にスルーして下さいませ。
 単に、適当に入れたら適当で微妙な部分が多く残ってしまったので注意書きが増えているだけで…。
 </p>
+<p>
+言い訳ついでにもう一つ言い訳ですが、この言語は、少なくとも今のところ、
+実用に使うことを考えた設計にはなっていません。どちらかというと、
+Brainfuck や Unlambda や Whitespace の仲間と思ってお使い下さい。
+</p>
 
 $(DDOC_MEMBERS
 
 $(SECTION Syntax, $(SECBODY
 <p>
@@ -521,11 +526,11 @@
     @@type = fun(x) {
        if( _isint(x) ) then "int"
        else if( _isstr(x) ) then "str"
        else if( _isbot(x) ) then "runtime error"
        else "type error"
-    }
+    };
 </pre>
 <pre>
     &gt;&gt; @type( 1 )
     int
     &gt;&gt; @type( 2 )
@@ -570,11 +575,11 @@
    @type "if" (c, t, e) {@value(
       if( @type(c)=="int" || @type(c)=="runtime error" ) then
          @type( int_int_int(t(), e()) )
       else
          "type error"
-   )}
+   )};
 </pre>
 <p>
 関数が自動リフトされるので、フィボナッチ関数の型を調べることができます。
 </p>
 <pre>

Index: polemy/eval.d
==================================================================
--- polemy/eval.d
+++ polemy/eval.d
@@ -227,11 +227,11 @@
 		{
 			return theID;
 		}
 		override Value eval_( Die e, Table ctx, bool ctxMod )
 		{
-			return new BottomValue;
+			return this.lift(new BottomValue, ctx, e.pos);
 		}
 		override Value eval_( Str e, Table ctx, bool ctxMod )
 		{
 			return this.lift(super.eval_(e,ctx,ctxMod), ctx, e.pos);
 		}
@@ -413,23 +413,22 @@
 
 				// automatic memoized co-recursive execution
 				MemokeyType memokey = new MemokeyType(cast(void*)ast, lay, ctx);
 				if(auto p = memokey in memo)
 				{
-					(*p)[1] ++;
-					return (*p)[0];
+					if( ++(*p)[1] >= 2 ) // [TODO] is 2 really enough??
+						return (*p)[0];
 				}
-				else {
+				else
+				{
 					Value v;
 					try { v = evlay.lift(new BottomValue, ctx, pos); } catch { v = new BottomValue; }
 					memo[memokey] = tuple(v, 0);
 				}
 
 				Value r = nonMemoizedRun();
-
-				int touched = memo[memokey][1];
-				memo[memokey] = tuple(r, 12345678);
+				memo[memokey] = tuple(r, 9999);
 				return r;
 			}
 		}
 		return new UserDefinedFunValue(e,ctx);
 	}

Index: polemy/parse.d
==================================================================
--- polemy/parse.d
+++ polemy/parse.d
@@ -315,16 +315,16 @@
 		auto thenPos = currentPosition();
 		if(!tryEat(":")) {
 			eat("then", "after if condition");
 			tryEat(":");
 		}
-		AST th = E(0);
+		AST th = Body();
 		auto el = doNothingExpression();
 		auto elsePos = currentPosition();
 		if( tryEat("else") ) {
 			tryEat(":");
-			el = E(0);
+			el = Body();
 		}
 		return new App(pos, new Var(pos,"if"), cond, new Fun(thenPos,[],th), new Fun(elsePos,[],el));
 	}
 
 	AST parsePatternMatch(LexPosition pos)
@@ -351,11 +351,11 @@
 			auto pos = currentPosition();
 			string failBranchVar = freshVarName();
 
 			auto pr = parsePattern();
 			eat(":", "after when pattern");
-			AST cBody = E(0);
+			AST cBody = Body();
 			AST judgement = new App(pos, new Var(pos, "if"),
 				ppTest(pmVar, pr), new Fun(pos,[],ppBind(pmVar, pr, cBody)),
 				new Var(pos, failBranchVar));
 			return parsePatternMatchCases(casePos, pmVar, failBranchVar, 
 				new Let(pos, tryThisBranchVar, [],

Index: sample/type.pmy
==================================================================
--- sample/type.pmy
+++ sample/type.pmy
@@ -1,32 +1,172 @@
-@@type = fun(x){
-  if _isint(x): "int"
-  else if _isstr(x): "str" 
-  else: "any"
-};
-
-def binop(a,b,c) {
-  fun(x,y){@value(
-    if( _isbot( @type(x) ) || _isbot( @type(y) ) ) then @type(...) else
-      if( @type(x)==a && @type(y)==b ) then c else "error"
-  )}
+# Lift to types
+@@type (x)
+{
+	if _isint(x): "int"
+	else if _isstr(x): "str"
+	else if _isbot(x): "RE"
+	else if _istbl(x):
+		if x.?car && x.?cdr:
+			let xa = x.car in let xd = x.cdr in
+				mergeType( {list: @type(xa)}, @type(xd) )
+		else
+			{list: "RE"} # tenuki
+	else ...
 };
 
-@type "+" = binop("int", "int", "int");
-@type "-" = binop("int", "int", "int");
-@type "<" = binop("int", "int", "int");
-@type ">" = binop("int", "int", "int");
-
-def mergeType(a,b) {
-  if( _isbot(a) ): ( if( _isbot(b) ):"error" else b  ) else ( a )
+# unify two types
+def mergeType(a, b)
+{
+	if a == "RE": b
+	else if b == "RE": a
+	else if _istbl(a) && _istbl(b):
+		if  a.?list && b.?list:
+			let rt = mergeType(a.list, b.list) in
+				if rt=="TE" || rt=="RE" then rt else {list: rt}
+		else:
+			"TE" # type error
+	else if a == b: a
+	else "TE"  # type error
 };
 
-@type "if" = fun(c,t,e) {@value(
- if(@type(c)=="int" ): mergeType(@type(t()), @type(e())) else : "error"
-)};
-
-def fib(x)
+# helper function
+def Tuni(t1, t0)
+{
+	fun(x) {@value(
+		if @type(x)=="RE": "RE"
+		else if @type(x)=="TE": "TE"
+		else if @type(x)==t1: t0
+		else "TE"
+	)}
+};
+def Tuniany(t0)
+{
+	fun(x) {@value(
+		if @type(x)=="RE": "RE"
+		else if @type(x)=="TE": "TE"
+		else t0
+	)}
+};
+def Tbin(t1, t2, t0)
+{
+	fun(x,y) {@value(
+		if @type(x)=="RE" || @type(y)=="RE": "RE"
+		else if @type(x)=="TE" || @type(y)=="TE": "TE"
+		else if @type(x)==t1 && @type(y)==t2: t0
+		else "TE"
+	)}
+};
+def Tbinany(t0)
 {
-	if x<2 then 1 else fib(x-1) + fib(x-2)
+	fun(x,y){@value(
+		if @type(x)=="RE" || @type(y)=="RE": "RE"
+		else if @type(x)=="TE" || @type(y)=="TE": "TE"
+		else t0
+	)}
+};
+
+# type annotation for built-in ops
+@type "+" = Tbin("int", "int", "int");
+@type "-" = Tbin("int", "int", "int");
+@type "*" = Tbin("int", "int", "int");
+@type "/" = Tbin("int", "int", "int");
+@type "%" = Tbin("int", "int", "int");
+@type "&&" = Tbin("int", "int", "int");
+@type "||" = Tbin("int", "int", "int");
+@type print = fun(x){x};
+@type gensym = fun(){"str"};
+@type argv = {list: "str"};
+@type rand = Tuni("int","int");
+@type "~" = Tbinany("str");
+@type "<" = Tbinany("int");
+@type "<=" = Tbinany("int");
+@type ">" = Tbinany("int");
+@type ">=" = Tbinany("int");
+@type "==" = Tbinany("int");
+@type "!=" = Tbinany("int");
+@type "if" (c,t,e) {@value(
+	if @type(c)=="RE": "RE"
+	else if @type(c)!="int": "TE"
+	else mergeType( @type(t()), @type(e()) );
+)};
+@type _isint = Tuniany("int");
+@type _isstr = Tuniany("int");
+@type _isfun = Tuniany("int");
+@type _istbl = Tuniany("int");
+@type _isbot = Tuniany("int");
+
+###################################
+
+# for lists
+@type "{}"() {@value( {list: "RE"} )};
+@type ".?"(t, s) {@value(
+	if @type(t)=="RE": "RE"
+	else if @type(t)=="TE": "TE"
+	else if _istbl( @type(t) ): "int"
+	else "TE"
+)};
+@type ".="(t, s@value, v) {@value(
+	var tt = @type(t);
+	if tt == "TE": "TE"
+	else if tt == "RE": "RE"
+	else if _istbl(tt) && tt.?list:
+		if s == "car":
+			mergeType(tt, {list: @type(v)})
+		else if s == "cdr":
+			mergeType(tt, @type(v))
+		else:
+			tt
+	else:
+		"TE"
+)};
+@type "."(t, s@value) {@value(
+	var tt = @type(t);
+	if tt == "TE": "TE"
+	else if tt == "RE": "RE"
+	else if _istbl(tt) && tt.?list:
+		if s == "car":
+			tt.list
+		else if s == "cdr":
+			tt
+		else:
+			"TE"
+	else:
+		"TE"
+)};
+
+###################################
+
+def fib(x) { if x < 2 then 1 else fib(x-1) + fib(x-2) };
+def fibE1(x) { if "true!" then 1 else fib(x-1) + fib(x-2) };
+def fibE2(x) { if x<2 then "ichi" else fib(x-1) + fib(x-2) };
+def fibE3(x) { if x<2 then 1 else fib(x-1) ~ fib(x-2) };
+def fibS(x) { if x<2 then "1" else fib(x-1) ~ fib(x-2) };
+def fibBadButTypeIsOK(x) { if x < "2" then 1 else fib(x-1) + fib(x-2) };
+
+print( @type(fib(999)) );
+print( @type(fibE1(999)) );
+print( @type(fibE2(999)) );
+print( @type(fibE3(999)) );
+print( @type(fibS(999)) );
+print( @type(fibBadButTypeIsOK(999)) );
+
+###################################
+
+def nil = {};
+def cons(a, d) { {car: a, cdr: d} };
+
+print( @type(nil) );
+print( @type(cons(1,nil)) );
+print( @type(cons("foo",nil)) );
+print( @type(cons(123, cons("foo",nil))) ); # TE
+
+def rev(xs) {
+	def revi(xs, ys) {
+		case xs
+			when {car: x, cdr: xs}: revi(xs, cons(x,ys))
+			when {}: ys
+	};
+	revi(xs, {})
 };
 
-print( @type(fib(10)) );
+var xs = cons(1, cons(2, cons(3, nil)));
+print( @type( rev(xs) ) );