# Writing a simple interpreter which can add numbers in tree form

**URL:** <https://racket.discourse.group/t/writing-a-simple-interpreter-which-can-add-numbers-in-tree-form/1668>\
**Category:** General\
**Created:** [January 27, 2023, 5:45pm UTC](https://racket.discourse.group/t/writing-a-simple-interpreter-which-can-add-numbers-in-tree-form/1668 "2023-01-27T17:45:01Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![devosalain](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/devosalain/32/546_2.png) [@devosalain](https://racket.discourse.group/u/devosalain)\
**Post date:** [January 27, 2023, 5:45pm UTC](https://racket.discourse.group/t/writing-a-simple-interpreter-which-can-add-numbers-in-tree-form/1668/1 "2023-01-27T17:45:01Z")

</div>

Following code works perfect:

```scheme
#lang typed/racket
(require racket/match )
(define-struct myoperand ([O : [U 'plus 'minus] ]))
(define-struct myleaf ([L : Number]))
(define-struct mynode ([N :(cons myoperand (cons ExpT ExpT))]))
(define-type ExpT (U myleaf mynode))

(: myeval : ExpT -> Number)
(define myeval
  (lambda (x)
    [match x
      ([myleaf L]
        L
       );case
      ([mynode N]
       (if (equal? (myoperand-O (car N)) 'plus)
         (+
           (myeval (car (cdr N)))
           (myeval (cdr (cdr N)))
           );+
         -1;else
         );if
       );case
      ];match
    );lambda
  );define

(define testleaf1 (make-myleaf 1))
(define testleaf2 (make-myleaf 2))
(define twoleafs (cons testleaf1 testleaf2))
(define testoperand (make-myoperand 'plus))
(define testnode (make-mynode (cons testoperand twoleafs)))
(define testnode2 (make-mynode (cons testoperand (cons testnode testnode))))
(write (myeval testleaf1))
(write (myeval testnode))
(write (myeval testnode2))
(write (myeval testnode3))

```

Then i modified to code to use more "symbols" as it is a uniform representation of data.

```scheme
#lang typed/racket
(require racket/match )
(define-type myoperand Symbol)
(define-struct myleaf ([L : Symbol]) #:transparent)
(define-struct mynode ([N : (cons myoperand (cons ExpT ExpT))]) #:transparent)
(define-type ExpT (U myleaf mynode))

(: myeval : ExpT -> Number)
(define myeval
  (lambda (x)
    [match x
      [(mynode N)
         (if (equal? (car N) 'plus)
             (let* ([x (cdr N)]
                    [y (car x)]
                    [z (cdr x)])
                    (+ (myeval y) (myeval z))
               );let
             -1;snd
             );if
         ];1st-match
      [(myleaf L)
       (begin
         (let* ([astr (symbol->string L)]
                [n (string->number astr)])
              (if n n -1)
           );let
         );begin
        ] ;2nd-match
      ];match
    );lambda
  );define

(define testleaf1 (make-myleaf '|1|))
(define testleaf2 (make-myleaf '|2|))
(define twoleafs (cons testleaf1 testleaf2))
(define testoperand 'plus)
(define testnode (make-mynode (cons testoperand twoleafs)))
(write (myeval testleaf1))
(write (myeval testnode))

```

---

<div class="post-metadata">

**Author:** ![devosalain](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/devosalain/32/546_2.png) [@devosalain](https://racket.discourse.group/u/devosalain)\
**Post date:** [January 27, 2023, 6:35pm UTC](https://racket.discourse.group/t/writing-a-simple-interpreter-which-can-add-numbers-in-tree-form/1668/2 "2023-01-27T18:35:44Z")

</div>

One of the errors:  
Type Checker: Polymorphic function `car' could not be applied to arguments:  
Types: (Pairof a b) -\> (a : ((! (car (0 0)) False) | (: (car (0 0)) False)) : (car (0 0)))  
(Listof a) -\> a

---

<div class="post-metadata">

**Author:** ![gus-massa](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/gus-massa/32/507_2.png) [@gus-massa](https://racket.discourse.group/u/gus-massa)\
**Post date:** [January 27, 2023, 7:27pm UTC](https://racket.discourse.group/t/writing-a-simple-interpreter-which-can-add-numbers-in-tree-form/1668/3 "2023-01-27T19:27:25Z")

</div>

A few hints, but I still couldn't make the program typecheck:

- `'1` is the number `1`. To get the symbol whose string representation is `"1"` you must write '|1|.

- The result of `string->number` may be `#f#`, so TR complains that it may not be a number. You can use for example `(or (string->number astr) +nan.f)` so the result is always a number.

- My guess is that `[N : (Listof Symbol)]` should be `[N : (List Symbol Symbol)]` so TR is sure that it can apply `(car (cdr ...))`, but I'm not sure.

---

<div class="post-metadata">

**Author:** ![jbclements](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/jbclements/32/11_2.png) [@jbclements](https://racket.discourse.group/u/jbclements)\
**Post date:** [January 27, 2023, 7:40pm UTC](https://racket.discourse.group/t/writing-a-simple-interpreter-which-can-add-numbers-in-tree-form/1668/4 "2023-01-27T19:40:39Z")

</div>

There are a lot of possible ways of fixing this, but let me ask one or two questions first.

1. You gave the `N` field of myNode the type `(Listof Symbol)`. That's not a useful choice, because it means that you can't put nodes inside of nodes. I'm ... assuming that you wanted to be able to nest nodes inside nodes?

2. I'm not sure why you want to use more symbols as a more uniform representation of data, or what exactly you mean by that. I can see two directions you can go in: First, you could make all of your inputs s-expressions, leveraging racket lists. Second, you could go for pure structs, and use symbols and lists only where they're natural choices (e.g. using a list for an arbitrary-length collection of arguments). Which of these are you heading toward? If you don't have a strong opinion, I would steer you toward the second one; it's certainly closer to OCaml, and gives you better type checking, and simplifies the type-checking in and around operators like 'car' and 'cdr'.

3. In case you're not already familiar with this, adding the `#:transparent` tag to structure definitions makes them print more usefully, and allows them to be compared by the testing framework. I strongly suggest using this tag on every structure definition. E.G.:

```scheme
(define-struct myleaf ([L : Number]) #:transparent)

```

(Also, you can just use `struct` rather than `define-struct`.)

---

<div class="post-metadata">

**Author:** ![devosalain](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/devosalain/32/546_2.png) [@devosalain](https://racket.discourse.group/u/devosalain)\
**Post date:** [January 29, 2023, 8:42pm UTC](https://racket.discourse.group/t/writing-a-simple-interpreter-which-can-add-numbers-in-tree-form/1668/7 "2023-01-29T20:42:00Z")

</div>

I cleaned the code:

```scheme
#lang typed/racket
(require racket/match )
(define-struct myoperand ([O : [U 'plus 'minus] ]) #:transparent )
(define-struct myleaf ([L : Number]) #:transparent )
(define-struct mynode ([OP : myoperand] [E1 : myexpr] [E2 : myexpr] ) #:transparent )
(define-struct myexpr ([E : (U myleaf mynode)]) #:transparent )

(: myeval : myexpr -> Number)
(define myeval
  (lambda (x)
    [match (myexpr-E x)
      ([myleaf L] L );case
      ([mynode OP E1 E2]
       (if (eq? (myoperand-O OP) 'plus )
         (+ (myeval E1) (myeval E2) );+
         -1000;else
         ))]))

(: to_expra : Number -> myexpr )
(define to_expra
  (lambda (x)
    [let* ([l (make-myleaf x)]
           [e (make-myexpr l)]
         );let
      e
      ];let
    );lambda
  );define

(: to_exprb : ( U 'minus 'plus ) Number Number -> myexpr )
(define to_exprb
  (lambda (x1 x2 x3)
    [let* ([op (make-myoperand x1)]
           [l1 (make-myleaf x2)]
           [l2 (make-myleaf x3)]
           [n (make-mynode op (make-myexpr l1) (make-myexpr l2))]
           [e (make-myexpr n)]
         );let
      e
      ];let
    );lambda
  );define

(: to_exprc : ( U 'minus 'plus ) myexpr myexpr -> myexpr )
(define to_exprc
  (lambda (x1 e1 e2)
    [let* ([op (make-myoperand x1)]
           [n (make-mynode op e1 e2)]
           [e (make-myexpr n)]
         );let
      e
      ];let
    );lambda
  );define

(write (myeval (to_expra 1)))
(write (myeval (to_exprb 'plus 2 3)))
(write (myeval (to_exprc 'plus (to_exprb 'plus 4 5) (to_exprb 'plus 6 7))))

```