Writing a simple interpreter which can add numbers in tree form

General
1

Following code works perfect:

#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.

#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))
2

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

3

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.

1 Like
4

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.:

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

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

2 Likes
7

I cleaned the code:

#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))))