a major revision of the bytecode generator and JIT compiler. the effect is that now we can compute with lambda functions and with true tail recursion

1 files changed, 62 insertions, 42 deletions

diff --git a/src/compiler/GF/Compile/GenerateBC.hs b/src/compiler/GF/Compile/GenerateBC.hs
index 0e26994fe..2c407b880 100644
--- a/src/compiler/GF/Compile/GenerateBC.hs
+++ b/src/compiler/GF/Compile/GenerateBC.hs
@@ -4,7 +4,7 @@ import GF.Grammar
 import GF.Grammar.Lookup(lookupAbsDef)
 import GF.Data.Operations
 import PGF(CId,utf8CId)
-import PGF.Internal(Instr(..))
+import PGF.Internal(Instr(..),IVal(..),TailInfo(..),Literal(..))
 import qualified Data.Map as Map
 import Data.List(nub)
 
@@ -46,108 +46,128 @@ compileEquations gr st (i:is) eqs       bs = whilePP eqs Map.empty
       let case_instr = 
             case t of
               (Q (_,id)) -> CASE (i2i id)
-              (EInt n)   -> CASE_INT n
-              (K s)      -> CASE_STR s
-              (EFloat d) -> CASE_FLT d
+              (EInt n)   -> CASE_LIT (LInt n)
+              (K s)      -> CASE_LIT (LStr s)
+              (EFloat d) -> CASE_LIT (LFlt d)
           (bs1,instrs) = compileEquations gr (st+n) (push_is st n is) eqs bs
-      in (bs1, EVAL_ARG_VAR (st-i-1) : case_instr (length bs1) : instrs)
+      in (bs1, EVAL (ARG_VAR (st-i-1)) RecCall : case_instr (length bs1) : instrs)
 
     compileBranch ((t,n),eqs) bs =
       let case_instr =
             case t of
               (Q (_,id)) -> CASE (i2i id)
-              (EInt n)   -> CASE_INT n
-              (K s)      -> CASE_STR s
-              (EFloat d) -> CASE_FLT d
+              (EInt n)   -> CASE_LIT (LInt n)
+              (K s)      -> CASE_LIT (LStr s)
+              (EFloat d) -> CASE_LIT (LFlt d)
           (bs1,instrs) = compileEquations gr (st+n) (push_is st n is) eqs ((case_instr (length bs1) : instrs) : bs)
       in bs1
 
 compileBody gr st avs fvs e bs es =
   let (heap,bs1,instrs) = compileFun gr st avs fvs e 0 bs es
-  in (bs1,((if heap > 0 then (ALLOC heap :) else id) .
-           (instrs ++) .
-           (if st == 0 then (UPDATE :) else id))
-          [RET st])
+  in (bs1,if heap > 0 then (ALLOC heap : instrs) else instrs)
 
+compileFun gr st avs fvs (Abs _ x e) h0 bs es =
+  let (h1,bs1,_,_,is) = compileLambda gr st st avs fvs [x] e h0 bs
+      (st1,h2,bs2,is1,is2,is3) = compileArgs gr st st avs fvs h1 bs1 (reverse es)
+  in (h2,bs2,is++is3++is2++(if st == 0 then [EVAL (HEAP h0) RecCall,UPDATE,RET st] else [EVAL (HEAP h0) (TailCall st st1)]))
 compileFun gr st avs fvs (App e1 e2) h0 bs es =
   compileFun gr st avs fvs e1 h0 bs (e2:es)
 compileFun gr st avs fvs (Q (m,id))  h0 bs es =
   case lookupAbsDef gr m id of
     Ok (_,Just _)
-       -> let (h1,bs1,is1,is2,is3) = compileArgs gr st st avs fvs h0 bs (reverse es)
-          in (h1,bs1,is3 ++ is2 ++ [TAIL_CALL (i2i id)])
+       -> let (st1,h1,bs1,is1,is2,is3) = compileArgs gr st st avs fvs h0 bs (reverse es)
+          in (h1,bs1,is3 ++ is2 ++ []++(if st == 0 then [CALL (i2i id) RecCall,UPDATE,RET st] else [CALL (i2i id) (TailCall st st1)]))
     _  -> let h1 = h0 + 2 + length es
-              (h2,bs2,is1,is2,is3) = compileArgs gr st st avs fvs h1 bs es
-          in (h2,bs2,PUT_CONSTR (i2i id) : is1 ++ is3)
+              (_,h2,bs2,is1,is2,is3) = compileArgs gr st st avs fvs h1 bs es
+          in (h2,bs2,PUT_CONSTR (i2i id) : is1 ++ is3 ++ (if st == 0 then [UPDATE] else []) ++ [RET st])
 compileFun gr st avs fvs (QC qid)    h0 bs es =
   compileFun gr st avs fvs (Q qid) h0 bs es
 compileFun gr st avs fvs (Vr x)      h0 bs es =
-  let (h1,bs1,is1,is2,is3)  = compileArgs gr st st avs fvs h0 bs (reverse es)
-      i = case lookup x avs of
-            Just i  -> EVAL_ARG_VAR (st-i-1)
-            Nothing -> case lookup x fvs of
-                         Just i  -> EVAL_FREE_VAR i
-                         Nothing -> error "compileFun: unknown variable"
-  in (h1,bs1,is3 ++ is2 ++ [i])
+  let (st1,h1,bs1,is1,is2,is3)  = compileArgs gr st st avs fvs h0 bs (reverse es)
+      mki = case lookup x avs of
+              Just i  -> EVAL (ARG_VAR (st1-i-1))
+              Nothing -> case lookup x fvs of
+                           Just i  -> EVAL (FREE_VAR i)
+                           Nothing -> error "compileFun: unknown variable"
+  in (h1,bs1,is3 ++ is2 ++ (if st == 0 then [mki RecCall,UPDATE,RET st] else [mki (TailCall st st1)]))
 compileFun gr st avs fvs (EInt n)    h0 bs _  =
   let h1 = h0 + 2
-  in (h1,bs,[PUT_INT n])
+  in (h1,bs,[PUT_LIT (LInt n)]++(if st == 0 then [UPDATE] else [])++[RET st])
 compileFun gr st avs fvs (K s)       h0 bs _  =
   let h1 = h0 + 1 + (length s + 4) `div` 4
-  in (h1,bs,[PUT_STR s])
+  in (h1,bs,[PUT_LIT (LStr s)]++(if st == 0 then [UPDATE] else [])++[RET st])
 compileFun gr st avs fvs (EFloat d)  h0 bs _  =
   let h1 = h0 + 3
-  in (h1,bs,[PUT_FLT d])
+  in (h1,bs,[PUT_LIT (LFlt d)]++(if st == 0 then [UPDATE] else [])++[RET st])
+compileFun gr st avs fvs e _ _ _ = error (show e)
 
 compileArgs gr st st0 avs fvs h0 bs []     =
-  (h0,bs,[],[],[])
+  (st0,h0,bs,[],[],[])
 compileArgs gr st st0 avs fvs h0 bs (e:es) =
-  (h2,bs2,i1:is1,i2:is2,is++is3)
+  (st1,h2,bs2,i1:is1,i2:is2,is++is3)
   where 
     (h1,bs1,i1,i2,is)    = compileArg gr st st0 avs fvs e h0 bs []
-    (h2,bs2,is1,is2,is3) = compileArgs gr st (st0+1) avs fvs h1 bs1 es
+    (st1,h2,bs2,is1,is2,is3) = compileArgs gr st (st0+1) avs fvs h1 bs1 es
 
+compileArg gr st st0 avs fvs (Abs _ x e) h0 bs es =
+  compileLambda gr st st0 avs fvs [x] e h0 bs
 compileArg gr st st0 avs fvs (App e1 e2) h0 bs es = compileArg gr st st0 avs fvs e1 h0 bs (e2:es)
 compileArg gr st st0 avs fvs e@(Q(m,id)) h0 bs es =
   case lookupAbsDef gr m id of
     Ok (_,Just _)
        -> if null es
             then let h1 = h0 + 2
-                 in (h1,bs,SET_VALUE h0,PUSH_VALUE h0,[PUT_FUN (i2i id),SET_PAD])
-            else let es_fvs = nub (foldr freeVars [] es)
+                 in (h1,bs,SET (HEAP h0),PUSH (HEAP h0),[PUT_FUN (i2i id),SET_PAD])
+            else let es_fvs = nub (foldr (\e fvs -> freeVars [] fvs e) [] es)
                      h1 = h0 + 1 + length is
                      (bs1,b) = compileBody gr 0 [] (zip es_fvs [0..]) e bs es
                      is = if null es_fvs
                             then [SET_PAD]
                             else map (fst . compileVar st st0 avs fvs) es_fvs
-                 in (h1,(ENTER:b):bs1,SET_VALUE h0,PUSH_VALUE h0,PUT_CLOSURE (length bs) : is)
+                 in (h1,(ENTER:b):bs1,SET (HEAP h0),PUSH (HEAP h0),PUT_CLOSURE (length bs) : is)
     _  -> let h1 = h0 + 2 + length es
-              (h2,bs2,is1,is2,is3) = compileArgs gr st st avs fvs h1 bs es
-          in (h2,bs2,SET_VALUE h0,PUSH_VALUE h0,PUT_CONSTR (i2i id) : is1 ++ is3)
+              (_,h2,bs2,is1,is2,is3) = compileArgs gr st st avs fvs h1 bs es
+          in (h2,bs2,SET (HEAP h0),PUSH (HEAP h0),PUT_CONSTR (i2i id) : is1 ++ is3)
 compileArg gr st st0 avs fvs (QC qid)    h0 bs es = compileArg gr st st0 avs fvs (Q qid) h0 bs es
 compileArg gr st st0 avs fvs (Vr x)      h0 bs es =
   let (i1,i2) = compileVar st st0 avs fvs x
   in (h0,bs,i1,i2,[])
 compileArg gr st st0 avs fvs (EInt n)    h0 bs _  = 
   let h1 = h0 + 2
-  in (h1,bs,SET_VALUE h0,PUSH_VALUE h0,[PUT_INT n])
+  in (h1,bs,SET (HEAP h0),PUSH (HEAP h0),[PUT_LIT (LInt n)])
 compileArg gr st st0 avs fvs (K s)       h0 bs _  =
   let h1 = h0 + 1 + (length s + 4) `div` 4
-  in (h1,bs,SET_VALUE h0,PUSH_VALUE h0,[PUT_STR s])
+  in (h1,bs,SET (HEAP h0),PUSH (HEAP h0),[PUT_LIT (LStr s)])
 compileArg gr st st0 avs fvs (EFloat d)  h0 bs _  =
   let h1 = h0 + 3
-  in (h1,bs,SET_VALUE h0,PUSH_VALUE h0,[PUT_FLT d])
+  in (h1,bs,SET (HEAP h0),PUSH (HEAP h0),[PUT_LIT (LFlt d)])
 
 compileVar st st0 avs fvs x =
   case lookup x avs of
-    Just i  -> (SET_ARG_VAR (st-i-1),PUSH_ARG_VAR (st0-i-1))
+    Just i  -> (SET (ARG_VAR (st-i-1)),PUSH (ARG_VAR (st0-i-1)))
     Nothing -> case lookup x fvs of
-                 Just i  -> (SET_FREE_VAR i,PUSH_FREE_VAR i)
+                 Just i  -> (SET (FREE_VAR i),PUSH (FREE_VAR i))
                  Nothing -> error "compileVar: unknown variable"
 
-freeVars (App e1 e2) vs = (freeVars e1 . freeVars e2) vs
-freeVars (Vr x)      vs = x:vs
-freeVars _           vs = vs
+compileLambda gr st st0 avs fvs e_avs (Abs _ x e) h0 bs =
+  compileLambda gr st st0 avs fvs (x:e_avs) e h0 bs
+compileLambda gr st st0 avs fvs e_avs e           h0 bs =
+  let e_fvs   = freeVars e_avs [] e
+      (bs1,b) = compileBody gr (length e_avs)
+                               (zip e_avs [0..])
+                               (zip e_fvs [0..])
+                               e bs []
+      is = if null e_fvs
+             then [SET_PAD]
+             else map (fst . compileVar st st0 avs fvs) e_fvs
+      h1 = h0 + 1 + length is
+  in (h1,(ENTER:b):bs1,SET (HEAP h0),PUSH (HEAP h0),PUT_CLOSURE (length bs) : is)
+
+freeVars avs fvs (Abs _ x e) = freeVars (x:avs) fvs e
+freeVars avs fvs (App e1 e2) = freeVars avs (freeVars avs fvs e2) e1
+freeVars avs fvs (Vr x)     
+  | not (elem x avs)         = x:fvs
+freeVars avs fvs _           = fvs
 
 i2i :: Ident -> CId
 i2i = utf8CId . ident2utf8