# Writing compilers and interpreters in Factor

## Chris Double — 2006-10-28 14:16:10

    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

## Peter Lawrence — 2006-10-30 20:07:37

    On 29 Oct 2006 14:12:20 -0000, concatenative@yahoogroups.com wrote:

     > There is 1 message in this issue.

    > Topics in this digest:

    > 1. Writing compilers and interpreters in Factor

    > From: Chris Double

    > 1. Writing compilers and interpreters in Factor

    > Posted by: "Chris Double" chris.double@... doublecnz

    > Date: Sat Oct 28, 2006 7:20 am (PDT)

    > 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'm interested in any approaches that other concatenative languages

    > use for writing interpreters/compilers. Any thoughts on best

    > approaches?

     The approach I'm using in developing Furphy (see

    http://member.netlink.com.au/~peterl/furphy.htm) is to build bottom up

    from a Forth-ish base, aiming to arrive at something that supports

    concatenative programming. The language itself is, in a sense, emergent

    from whatever I arrive at, and I don't expect it will be the final form.

    For now, I'm doing pieces that I haven't pulled together, and I expect

    to provide garbage collection by snarfing (piggybacking) development

    versions on something that already has it, e.g. an eforth implementation

    in Perl. Once that stabilises it should be straightforward to migrate

    the base to C and attach a garbage collector from some library, maybe a

    commercial implementation. For now, I'm just letting memory leak.

    I'm trying to follow a Forth philosophy here, not a top down one with a

    known destination that needs to be implemented. PML.

    GST+NPT=JOBS

    I.e., a Goods and Services Tax (or almost any other broad based production tax),

    with a Negative Payroll Tax, promotes employment.

    See http://member.netlink.com.au/~peterl/publicns.htm#AFRLET2 and the other

    items on that page for some reasons why.

    -- Arachne V1.77+/B~5