DrRacket type mismatch error in eval function using the substitution model

Question

I have implemented the language “ROL”, now I'm trying to extend the language to also support fun and call I'm trying to implement it in the substitution model.

here is my code for the eval function (Note that this code worked just fine without the fun and call. so the problem must be with these two implementations

(: eval : RegE -> RES)
;; evaluates RegE expressions by reducing them to bit-lists
(define (eval expr)
  (cases expr
    [(Reg right) (RegV right)]
    [(Bool b) (RES_Bool b)]
    [(Id name) (error 'eval "free identifier: ~s" name)]
    [(And left right) (reg-arith-op bit-and  (eval left ) (eval right) )]
    [(Or left right) (reg-arith-op bit-or (eval left )  (eval right) )]
    [(Shl E1) (RegV (shift-left (RegV->bit-list (eval E1))))]
    [(Maj E1) (RES_Bool (majority? (RegV->bit-list (eval E1))))]
    [(Geq E1 E2) (RES_Bool (geq-bitlists? (RegV->bit-list (eval E1)) (RegV->bit-list (eval E2))))]
    [(With bound-id named-expr bound-body)
       (eval (subst bound-body
                    bound-id
                    (Reg (RegV->bit-list(eval named-expr)))))]
    [(Fun bound-id bound-body) expr]
    [(Call fun-expr arg-expr)
       (let ([fval (eval fun-expr)])
         (cases fval
           [(Fun bound-id bound-body)
            (eval (subst bound-body
                   bound-id
                   (eval arg-expr)))]
           [else (error 'eval "`call' expects a function, got: ~s"
                              fval)]))]
    [(If E1 E2 E3) (if (RegV->boolean (eval E1)) (eval E2) (eval E3))]



))

and here is my sunst function:

(define (subst expr from to)
  (cases expr
    [(Reg g) expr]
    [(Bool g) expr]
    [(And left right)(And (subst left from to)(subst right from to))]
    [(Or left right)(Or (subst left from to)(subst right from to))]
    [(If bool ifBody elseBody) (If (subst bool from to) (subst ifBody from to) (subst elseBody from to))]
    [(Maj left)(Maj (subst left from to))]
    [(Geq left right)(Geq (subst left from to)(subst right from to))]
    [(Shl left)(Shl (subst left from to))]
    [(Id name) (if (eq? name from) to expr)]
    [(With bound-id named-expr bound-body)
           (if (eq? bound-id from)
               expr
               (With bound-id
                     named-expr
               (subst bound-body from to)))]
    [(Call left right) (Call (subst left from to) (subst right from to))]
    [(Fun bound-id bound-body)
         (if (eq? bound-id from)
           expr
           (Fun bound-id (subst bound-body from to)))]))

I'm getting the errors:

Type Checker: type mismatch
  expected: RegE
  given: RES in: fval
. Type Checker: type mismatch
  expected: RegE
  given: RES in: (eval arg-expr)
. Type Checker: type mismatch
  expected: RES
  given: Fun in: (cases expr ((Reg right) (RegV right)) ((Bool b) (RES_Bool b)) ((Id name) (error (quote eval) "free identifier: ~s" name)) ((And left right) (reg-arith-op bit-and (eval left) (eval right))) ((Or left right) (reg-arith-op bit-or (eval left) (eval right))) ((Shl E1) (RegV (shift-left (RegV->bit-list (eval E1))))) ((Maj E1) (RES_Bool (majority? (RegV->bit-list (eval E1))))) ((Geq E1 E2) (RES_Bool (geq-bitlists? (RegV->bit-list (eval E1)) (RegV->bit-list (eval E2))))) ((With bound-id named-expr bound-body) (eval (subst bound-body bound-id (Reg (RegV->bit-list (eval named-expr)))))) ((Fun bound-id bound-body) expr) ((Call fun-expr arg-expr) (let ((fval (eval fun-expr))) (cases fval ((Fun bound-id bound-body) (eval (subst bound-body bound-id (eval arg-expr)))) (else (error (quote eval) "`call' expects a function, got: ~s" fval))))) ((If E1 E2 E3) (if (RegV->boolean (eval E1)) (eval E2) (eval E3))))
. Type Checker: Summary: 3 errors encountered in:
  fval
  (eval arg-expr)
  (cases expr ((Reg right) (RegV right)) ((Bool b) (RES_Bool b)) ((Id name) (error (quote eval) "free identifier: ~s" name)) ((And left right) (reg-arith-op bit-and (eval left) (eval right))) ((Or left right) (reg-arith-op bit-or (eval left) (eval right))) ((Shl E1) (RegV (shift-left (RegV->bit-list (eval E1))))) ((Maj E1) (RES_Bool (majority? (RegV->bit-list (eval E1))))) ((Geq E1 E2) (RES_Bool (geq-bitlists? (RegV->bit-list (eval E1)) (RegV->bit-list (eval E2))))) ((With bound-id named-expr bound-body) (eval (subst bound-body bound-id (Reg (RegV->bit-list (eval named-expr)))))) ((Fun bound-id bound-body) expr) ((Call fun-expr arg-expr) (let ((fval (eval fun-expr))) (cases fval ((Fun bound-id bound-body) (eval (subst bound-body bound-id (eval arg-expr)))) (else (error (quote eval) "`call' expects a function, got: ~s" fval))))) ((If E1 E2 E3) (if (RegV->boolean (eval E1)) (eval E2) (eval E3))))
>

My datatypes are:

(define-type RegE
[Reg Bit-List]
[Xor RegE RegE]
[And RegE RegE]
[Or RegE RegE]
[Shl RegE]
[Id Symbol]
[With Symbol RegE RegE]
[Bool Boolean]
[Geq RegE RegE]
[Maj RegE]
[If RegE RegE RegE]
[Fun Symbol RegE]
[Call RegE RegE])

and:

(define-type RES
[RES_Bool Boolean]
[RegV Bit-List])

I can see that for (let ([fval (eval fun-expr) doing the (eval fun-expr) will return RES, and I;m guessing this is probably the problem, is there any other way to wite it down? any help would be appreciated..

Answer 1

The key question is how you want to represent functions at runtime. The definition of eval is:

(: eval : RegE -> RES)
;; evaluates RegE expressions by reducing them to bit-lists
(define (eval expr)
  (cases expr
  ...
  [(Fun bound-id bound-body) expr]
  ...

The result of evaluating (Fun bound-id bound-body) needs to be a RES. Maybe extend RES as:

(define-type RES
    [RES_Bool Boolean]
    [RegV Bit-List]
    [FunV Symbol RegE])

Then let eval return a (FunV bound-id bound-body).

In the evaluation of Call, you will then need to switch to

     (cases fval
       [(FunV bound-id bound-body)

since fval is a RES.