I've been writing an interpreter and compiler using Factor and wrote a
blog posting about different ways of approaching it - using the AST of
a simple language for the example:
http://www.bluishcoder.co.nz/2006/10/compilers-and-interpreters-in-factor.html
I took two approaches - one using pattern matching and the other using
Factor's OO system. One interpreter looks like:
TUPLE: lit i ;
TUPLE: inc t ;
TUPLE: isz t ;
TUPLE: iff b t e ;
TUPLE: pair a b ;
TUPLE: fst t ;
TUPLE: snd t ;
: eval1 ( a -- a )
{
{ T{ lit f ?i } [ ?i ] }
{ T{ inc f ?t }[ ?t eval1 1+ ] }
{ T{ isz f ?t } [ ?t eval1 zero? ] }
{ T{ iff f ?b ?t ?e } [ ?b eval1 [ ?t ] [ ?e ] if eval1 ] }
{ T{ pair f ?a ?b } [ ?a eval1 ?b eval1 2array ] }
{ T{ fst f ?t } [ ?t eval1 first ] }
{ T{ snd f ?t } [ ?t eval1 second ] }
} match-cond ;
The version using Factor's generic system is:
GENERIC: eval2 ( a -- a )
M: lit eval2 ( a -- a ) lit-i ;
M: inc eval2 ( a -- a ) inc-t eval2 1+ ;
M: isz eval2 ( a -- a ) isz-t eval2 zero? ;
M: iff eval2 ( a -- a ) dup iff-b eval2 [ iff-t ] [ iff-e ] if eval2 ;
M: pair eval2 ( a -- a ) dup pair-a eval2 swap pair-b eval2 2array ;
M: fst eval2 ( a -- a ) fst-t eval2 first ;
M: snd eval2 ( a -- a ) snd-t eval2 second ;
These are a translation of the Haskell:
data Term a where
Lit :: Int -> Term Int
Inc :: Term Int -> Term Int
IsZ :: Term Int -> Term Bool
If :: Term Bool -> Term a -> Term a -> Term a
Pair :: Term a -> Term b -> Term (a,b)
Fst :: Term (a,b) -> Term a
Snd :: Term (a,b) -> Term b
eval :: Term a -> a
eval (Lit i) = i
eval (Inc t) = eval t + 1
eval (IsZ t) = eval t == 0
eval (If b t e) = if eval b then eval t else eval e
eval (Pair a b) = (eval a, eval b)
eval (Fst t) = fst (eval t)
eval (Snd t) = snd (eval t)
For the compiler I generate Factor code and Javascript code. The
compiler to Factor is:
: (compile1) ( a -- )
{
{ T{ lit f ?i } [ ?i , ] }
{ T{ inc f ?t } [ ?t (compile1) \ 1+ , ] }
{ T{ isz f ?t } [ ?t (compile1) \ zero? , ] }
{ T{ iff f ?b ?t ?e } [ ?b (compile1) [ ?t (compile1) ] [ ] make
, [ ?e (compile1) ] [ ] make , \ if , ] }
{ T{ pair f ?a ?b } [ ?a (compile1) ?b (compile1) \ 2array , ] }
{ T{ fst f ?t } [ ?t (compile1) \ first , ] }
{ T{ snd f ?t } [ ?t (compile1) \ second , ] }
} match-cond ;
: compile1 ( a -- quot )
[ (compile1) ] [ ] make ;
The compiler to javascript:
: (compile2) ( a -- )
{
{ T{ lit f ?i } [ ?i number>string % ] }
{ T{ inc f ?t } [ ?t (compile2) "+1" % ] }
{ T{ isz f ?t } [ ?t (compile2) "== 0" % ] }
{ T{ iff f ?b ?t ?e } [
"function() {if(" %
?b (compile2)
") {return " %
?t (compile2)
"} else { return " %
?e (compile2)
"}}()" %
]
}
{ T{ pair f ?a ?b } [ "{ first:" % ?a (compile2) ",second:" % ?b
(compile2) " }" % ] }
{ T{ fst f ?t } [ ?t (compile2) ".first" % ] }
{ T{ snd f ?t } [ ?t (compile2) ".second" % ] }
} match-cond ;
: compile2 ( a -- quot )
[ "(" % (compile2) ")" % ] "" make ;
Examples of usage:
5 <lit> <inc> eval1 => 6
5 <lit> <inc> compile1 => [ 5 1+ ]
5 <lit> <inc> compile2 => "(5+1)"
I'm interested in any approaches that other concatenative languages
use for writing interpreters/compilers. Any thoughts on best
approaches?
Chris.
--
http://www.bluishcoder.co.nz