Getting Started Building a Cat Translator
This is a blog post that is intended to help people new to interpreters with the steps of building a translator from Cat to some other language.
The first step is to figure out how you want to embed Cat in the other language. Two of the simplest ways to do this are: map every Cat instruction on to a function or object in the target language or write a mini-interpreter in the other language.Â
A mini-interpreter might be in the form of an evaluate statement that takes a list of objects representing Cat instructions. An example of a mini-interpreter of Cat in Scheme is:
(define (cat-eval stk exp)
(if (not (list? exp))
(error "can only evaluate lists"))
(if (null? exp)
stk
(cat-eval
(trace
(case (car exp)
((true) (cons #t stk))
((false) (cons #f stk))
((apply) (cat-eval (cdr stk) (car stk)))
((papply) (cons (cons (cadr stk) (car stk)) (cddr stk)))
((pop) (cdr stk))
((dup) (cons (car stk) stk))
((swap) (cons (cadr stk) (cons (car stk) (cddr stk))))
((dip) (cons (cadr stk) (cat-eval (cddr stk) (car stk))))
((add) (cons (+ (cadr stk) (car stk)) (cddr stk)))
((mul) (cons (* (cadr stk) (car stk)) (cddr stk)))
((sub) (cons (- (cadr stk) (car stk)) (cddr stk)))
((div) (cons (/ (cadr stk) (car stk)) (cddr stk)))
((eq) (cons (= (cadr stk) (car stk)) (cddr stk)))
((lt) (cons (< (cadr stk) (car stk)) (cddr stk)))
((lteq) (cons (<= (cadr stk) (car stk)) (cddr stk)))
((gt) (cons (> (cadr stk) (car stk)) (cddr stk)))
((gteq) (cons (>= (cadr stk) (car stk)) (cddr stk)))
((empty) (cons (null? (car stk)) stk))
((cons) (cons (list (cadr stk) (car stk)) (cddr stk)))
((uncons) (cat-eval (cdr stk) (car stk)))
((unconsd)(cons (car stk) (cat-eval (cddr stk) (cadr stk))))
((makeref)(cons (list (car stk)) (cdr stk)))
((setref) (begin
(set-car! (car stk) (cadr stk))
(cons (car stk) (cddr stk))))
((deref) (cons (car (car stk)) (cdr stk)))
((if) (if (caddr stk)
(cat-eval (cdddr stk) (cadr stk))
(cat-eval (cdddr stk) (car stk))))
(else (cons (car exp) stk))))
(cdr exp))))
Notice that there are two arguments: the stack and the expression. This function manipulates the stack according to the instructions.
If Scheme is hard for you to read I suggest taking a look at the JavaScript interpreter source code which shows a similar approach in JavaScript.
The other option for a translator is to map Cat instructions and literals directly on to functions or objects in the target language, and provide a library for the primitives. For example: we can imagine with the proper library support translating the following function definition in Cat
define f { 2 dup quote apply add }
into the following C++ (or Java or C#) code where all functions share access to a common global stack:
class F : Object {
virtual void eval() {
int_literal(2).eval();
dup().eval();
quote().eval();
apply().eval();
add().eval();
}
};
I should point out that this only one of a huge number of possible implementation options. A stack-based language can be implemented in many different ways such as through the use of graph reduction, or rewriting rules. I suggest though that a first attempt you should try and stay as simple as possible. Afterwards you will probably have lots of ideas about how to optimize your implementation in different ways (e.g. making it run concurrently, running as fast as possible on a single thread, making it extremely space efficient, etc.)