7 Dupe: a duplicity of types

7.4

← prev up next →

7 Dupe: a duplicity of types

There are 10 types of values...

7.1 Integers and Booleans

7.2 Meaning of Dupe programs

7.3 Ex uno plures: Out of One, Many

7.4 An Example of Dupe compilation

7.5 A Compiler for Dupe

7.6 Correctness and testing

7.1 Integers and Booleans

Up until now we have worked to maintain a single type of values: integers. This led to some awkwardness in the design of conditionals. Let us lift this restriction by considering a multiplicity of types. To start, we will consider two: integers and booleans.

We’ll call it Dupe.

We will use the following syntax, which relaxes the syntax of Con to make '(zero? e) its own expression form and conditionals can now have arbitrary expressions in test position: '(if e0 e1 e2) instead of just '(if (zero? e0) e1 e2). We also add syntax for boolean literals.

Together this leads to the following grammar for Dupe. One thing to take note of is the new nonterminal v which ranges over values, which are integers and booleans:

Which can be modeled with the following definitions:

dupe/ast.rkt
  #lang racket
  (provide (all-defined-out))

  ;; type Expr =
  ;; | Integer
  ;; | Boolean
  ;; | `(add1 ,Expr)
  ;; | `(sub1 ,Expr)
  ;; | `(zero? ,Expr)
  ;; | `(if ,Expr ,Expr ,Expr)

  (struct int-e (i))
  (struct bool-e (b))
  (struct add1-e (e))
  (struct sub1-e (e))
  (struct zero?-e (e))
  (struct if-e (p t f))

  (define (ast->sexpr a)
    (match a
      [(int-e i)    `(int-e ,i)]
      [(bool-e b)   `(bool-e ,b)]
      [(add1-e e)   `(add1-e ,(ast->sexpr e))]
      [(sub1-e e)   `(sub1-e ,(ast->sexpr e))]
      [(zero?-e e)  `(zero?-e ,(ast->sexpr e))]
      [(if-e i t f) `(if-e ,(ast->sexpr i)
                           ,(ast->sexpr t)
                           ,(ast->sexpr f))]))

We also have a predicate for well-formed Dupe expressions, as well as our helper function sexpr->ast for automating the creation of an AST from a well-formed s-expression that conforms to our language:

dupe/syntax.rkt
  #lang racket
  (provide (all-defined-out))
  (require "ast.rkt")

  ;; Any -> Boolean
  ;; Is x a well-formed expression?
  (define (expr? x)
    (match x
      [(? integer?) #t]
      [(? boolean?) #t]
      [`(add1 ,x) (expr? x)]
      [`(sub1 ,x) (expr? x)]
      [`(zero? ,x) (expr? x)]
      [`(if ,x ,y ,z)
       (and (expr? x)
            (expr? y)
            (expr? z))]
      [_ #f]))


  ; SExpr -> AST
  ; Parse the s-expr into our AST
  ; This should be a one-to-one mapping for now.
  (define (sexpr->ast s)
    (match s
      [(? integer? s) (int-e s)]
      [(? boolean? b) (bool-e b)]
      [`(add1 ,e)     (add1-e (sexpr->ast e))]
      [`(sub1 ,e)     (sub1-e (sexpr->ast e))]
      [`(zero? ,e)    (zero?-e (sexpr->ast e))]
      [`(if ,p ,t ,f) (if-e (sexpr->ast p) (sexpr->ast t) (sexpr->ast f))]
      [_              (error "operation not supported")]))

7.2 Meaning of Dupe programs

To consider he meaning of Dupe programs, we must revisit the meaning of conditions. Previously we branched on whether a subexpression evaluated to 0. We will now consider whether the subexpression evaluates to #f.

Let’s consider some examples:

(if #f 1 2) means 2 since the test expression means #f.
(if #t 1 2) means 1 since the test expression means #t, which is not #f.

Just as in Racket (and Scheme, generally), we will treat any non-#f value as “true.” So:

(if 0 1 2) means 1 since the test expression means 0, which is not #f.
(if 7 1 2) means 1 since the test expression means 7, which is not #f.

The new (zero? e) expression form evaluates to a boolean: #t when e evaluates to 0 and #f to an integer other than 0.

The #t and #f literals mean themselves, just like integer literals.

Once a multiplicity of types are introduced, we are forced to come to grips with type mismatches. For example, what should (add1 #f) mean? What about (if 7 #t -2)?

Languages adopt several approaches:

Prohibit such programs statically with a type system (e.g. OCaml, Java)
Coerce values to different types (e.g. JavaScript)
Signal a run-time error (e.g. Racket)
Leave the behavior unspecified (e.g. Scheme, C)

We are going to start by taking the last approach. Later we can reconsider the design, but for now this is a simple (and dangerous!) approach.

The semantics is still a binary relation between expressions and their meaning, however the type of the relation is changed to reflect the values of Dupe, which may either be integers or booleans:

This relies on two helper judgments:

Notice that here we are following the semantics of Racket, which says that anything that is not #f counts as true in a conditional.

Returning to the issue of type mismatches, what does the semantics say about (add1 #f)? What about (if 7 #t -2)?

What it says is: nothing. These programs are simply not in the semantic relation for this language. There’s only one rule for giving meaning to an (add1 e0) expression and it’s premise is that e means some integer i0. But (#f, i) ∉ 𝑫 for any i. So there’s no value v such that ((add1 #f), v) ∈ 𝑫. This expression is undefined according to the semantics.

The interpreter follows the rules of the semantics closely and is straightforward:

dupe/interp.rkt
  #lang racket
  (provide (all-defined-out))

  (require "ast.rkt")

  ;; type Value =
  ;; | Integer
  ;; | Boolean

  ;; Expr -> Value
  (define (interp e)
    (match e
      [(int-e i) i]
      [(bool-e b) b]
      [(add1-e e0)
       (+ (interp e0) 1)]
      [(sub1-e e0)
       (- (interp e0) 1)]
      [(zero?-e e0)
       (zero? (interp e0))]
      [(if-e p e1 e2)
       (if (interp p)
           (interp e1)
           (interp e2))]))

We can confirm the interpreter computes the right result for the examples given earlier:

Examples
> (interp (bool-e #t))
#t
> (interp (bool-e #f))
#f
> (interp (sexpr->ast '(if #f 1 2)))
2
> (interp (sexpr->ast '(if #t 1 2)))
1
> (interp (sexpr->ast '(if 0 1 2)))
1
> (interp (sexpr->ast '(if 7 1 2)))
1
> (interp (sexpr->ast '(if (zero? 7) 1 2)))
2

Correctness follows the same pattern as before, although it is worth keeping in mind the “hypothetical” form of the statement: if the expression has some meaning, then the interpreter must produce it. In cases where the semantics of the expression is undefined, the interpreter can do whatever it pleases; there is no specification.

Interpreter Correctness: For all Dupe expressions e and values v, if (e,v) in , then (interp e) equals v.

Consider what happens with interp on undefined programs such as (add1 #f): the interpretation of this expression is just the application of the Racket add1 function to #f, which results in the interp program crashing and Racket signalling an error:

Examples
> (interp (add1-e (bool-e #f)))
+: contract violation
  expected: number?
  given: #f
  argument position: 1st
  other arguments...:
   1

This isn’t a concern for correctness, because the interpreter is free to crash (or do anything else) on undefined programs; it’s not in disagreement with the semantics, because there is no semantics.

From a pragmatic point of view, this is a concern because it complicates testing. If the interpreter is correct and every expression has a meaning (as in all of our previous languages), it follows that the interpreter can’t crash on any Expr input. That makes testing easy: think of an expression, run the interpreter to compute its meaning. But now the interpreter may break if the expression is undefined. We can only safely run the interpreter on expressions that have a meaning.

We’ll return to this point in the design of later langauges.

7.3 Ex uno plures: Out of One, Many

Before getting in to the compiler, let’s first address the issue of representation of values in the setting of x86.

So far we’ve had a single type of value: integers. Luckily, x86 has a convenient datatype for representing integers: it has 64-bit signed integers. (There is of course the problem that this representation is inadequate; there are many (Con) integers we cannot represent as a 64-bit integer. But we put off worrying about this until later.)

The problem now is how to represent integers and booleans, which should be disjoint sets of values. Representing these things in the interpreter as Racket values was easy: we used booleans and integers. Representing this things in x86 will be more complicated. x86 doesn’t have a notion of “boolean” per se and it doesn’t have a notion of “disjoint” datatypes. There is only one data type and that is: bits.

We chose 64-bit integers to represent Con integers, because that’s the kind of value that can be stored in a register or used as an argument to a instruction. It’s the kind of thing that can be returned to the C run-time. It’s (more or less) the only kind of thing we have to work with. So had we started with booleans instead of integers, we still would have represented values as a sequence of bits because that’s all there is. Now that we have booleans and integers, we will have to represent both as bits (64-bit integers). The bits will have to encode both the value and the type of value.

As discussed in the lecture video, there are many possible ways of representing multiple types, this is just how we’ve decided to do it.

Here is the idea of how this could be done: We have two kinds of data: integers and booleans, so we could use one bit to indicate whether a value is a boolean or an integer. The remaining 63 bits can be used to represent the value itself, either true, false, or some integer.

Let’s use the least significant bit to indicate the type and let’s use #b0 for integer and #b1 for boolean. These are arbitrary choices (more or less).

The number 1 would be represented as #b10, which is the bits for the number (i.e. #b1), followed by the integer tag (#b0). Note that the representation of a Dupe number is no longer the number itself: the Dupe value 1 is represented by the number 2 (#b10). The Dupe value #t is represented by the number 3 (#b11); the Dupe value #f is represented by the number 1 (#b01).

One nice thing about our choice of encoding: 0 is represented as 0 (#b00).

If you wanted to determine if a 64-bit integer represented an integer or a boolean, you simply need to inquire about the value of the least significant bit. At a high-level, this just corresponds to asking if the number is even or odd. Odd numbers end in the bit (#b1), so they reprepresent booleans. Even numbers represent integers. Here are some functions to check our understanding of the encoding:

Examples
; Bits -> Value
> (define (bits->value bs)
    (match (even? bs)
      [#t (/ bs 2)]
      [_ (match bs
           [1 #f]
           [3 #t])]))
> (bits->value 0)
0
> (bits->value 1)
#f
> (bits->value 2)
1
> (bits->value 3)
#t
> (bits->value 4)
2
> (bits->value 5)
match: no matching clause for 5
> (bits->value 6)
3
> (bits->value 7)
match: no matching clause for 7

Notice that not all bits represent a value; name any odd number that’s neither 1 (#f) or 3 (#t).

We can also write the inverse:

Examples
; Value -> Bits
> (define (value->bits v)
    (match v
      [#f 1]
      [#t 3]
      [n (* n 2)]))
> (value->bits #t)
3
> (value->bits #f)
1
> (value->bits 0)
0
> (value->bits 1)
2
> (value->bits 2)
4
> (value->bits 3)
6
> (bits->value (value->bits #t))
#t
> (bits->value (value->bits #f))
#f
> (bits->value (value->bits 0))
0
> (bits->value (value->bits 1))
1
> (bits->value (value->bits 2))
2
> (bits->value (value->bits 3))
3

The interpreter operates at the level of Values. The compiler will have to work at the level of Bits. Of course, we could, as an intermediate step, define an interpreter that works on bits, which may help us think about how to implement the compiler.

We want a function

; interp-bits : Expr -> Bits

such that

; ∀ e : Expr . (interp-bits e) = (value->bits (interp e))

Let’s design interp-bits by derivation. This is a common functional programming technique whereby we start from a specification program and through a series of algebraic transformations, arrive an correct implementation.

First, let’s state the specification of interp-bits as a function that “cheats,” it uses interp to carry out evaluation and then finally converts to bits.

Examples
; Expr -> Bits
> (define (interp-bits e)
(value->bits (interp e)))

It’s clearly correct with respect to the spec for interp-bits that we started with because the code is just the specification itself.

We can even do some property-based random testing (which obviously succeeds):

Examples
(define (interp-bits-correct e)
  (with-handlers ([exn:fail? (λ (x) 'ok)])
    (interp e)
    (check-equal? (interp-bits e)
                  (value->bits (interp e)))))
(define es
  (for/list ([i 100])
    (sexpr->ast (random-expr))))
(for-each interp-bits-correct es)

The one wrinkle is we really only need the spec to hold when e is defined according to the semantics. Since we know interp crashes (by raising an exception) whenever e is undefined, we use an exception handler to avoid testing when e is undefined.

Now let us inline the defintion of interp:

Examples
; Expr -> Bits
(define (interp-bits e)
  (value->bits
   (match e
     [(int-e i) i]
     [(bool-e b) b]
     [(add1-e e0)
      (add1 (interp e0))]
     [(sub1-e e0)
      (sub1 (interp e0))]
     [(zero?-e e0)
      (zero? (interp e0))]
     [(if-e e0 e1 e2)
      (if (interp e0)
          (interp e1)
          (interp e2))])))

It’s still correct:

Examples
> (for-each interp-bits-correct es)

Now let’s “push” the value->bits inward by using the following equation:

(f (match m [p e] ...)) = (match m [p (f e)] ...)

So we get:

Examples
; Expr -> Bits
(define (interp-bits e)
  (match e
    [(int-e i) (value->bits i)]
    [(bool-e b) (value->bits b)]
    [(add1-e e0)
     (value->bits (add1 (interp- e0)))]
    [(sub1-e e0)
     (value->bits (sub1 (interp e0)))]
    [(zero?-e e0)
     (value->bits (zero? (interp e0)))]
    [(if-e e0 e1 e2) (value->bits
      (if (interp e0)
          (interp e1)
          (interp e2)))]))

Still correct:

Examples
> (for-each interp-bits-correct es)

In the first two cases, we know that i and b are integers and booleans, respectively. So we know (values->bits i) = (* 2 i) and (values->bits b) = (if b 1 3). We can rewrite the code as:

Examples
; Expr -> Bits
(define (interp-bits e)
  (match e
    [(int-e i) (* 2 i)]
    [(bool-e b) (if b 3 1)]
    [(add1-e e0)
     (value->bits (add1 (interp e0)))]
    [(sub1-e e0)
     (value->bits (sub1 (interp e0)))]
    [(zero?-e e0)
     (value->bits (zero? (interp e0)))]
    [(if-e e0 e1 e2)
     (value->bits
      (if (interp e0)
          (interp e1)
          (interp e2)))]))

Still correct:

Examples
> (for-each interp-bits-correct es)

We can rewrite the last case by the following equation:

(f (if e0 e1 e2)) = (if e0 (f e1) (f e2))

Examples
; Expr -> Bits
(define (interp-bits e)
  (match e
    [(int-e i) (* 2 i)]
    [(bool-e b) (if b 3 1)]
    [(add1-e e0)
     (value->bits (add1 (interp e0)))]
    [(sub1-e e0)
     (value->bits (sub1 (interp e0)))]
    [(zero?-e e0)
     (value->bits (zero? (interp e0)))]
    [(if-e e0 e1 e2)
     (if (interp e0)
         (value->bits (interp e1))
         (value->bits (interp e2)))]))

Still correct:

Examples
> (for-each interp-bits-correct es)

Let’s now re-write by the following equations:

(add1 e) = (+ e 1)
(sub1 e) = (- e 1)
(f (+ e0 e1)) = (+ (f e0) (f e1))
(f (- e0 e1)) = (- (f e0) (f e1))

to get:

Examples
; Expr -> Bits
(define (interp-bits e)
  (match e
    [(int-e i) (* 2 i)]
    [(bool-e b) (if b 3 1)]
    [(add1-e e0)
     (+ (value->bits (interp e0)) (value->bits 1))]
    [(sub1-e e0)
     (- (value->bits (interp e0)) (value->bits 1))]
    [(zero?-e e0)
     (value->bits (zero? (interp e0)))]
    [(if-e e0 e1 e2)
     (if (interp e0)
         (value->bits (interp e1))
         (value->bits (interp e2)))]))

Still correct:

Examples
> (for-each interp-bits-correct es)

By computation, (value->bits 1) = 2.

We can now rewrite by the equation of our specification:

(value->bits (interp e)) = (interp-bits e)

Examples
; Expr -> Bits
(define (interp-bits e)
  (match e
    [(int-e i) (* 2 i)]
    [(bool-e b) (if b 3 1)]
    [(add1-e e0)
     (+ (interp-bits e0) 2)]
    [(sub1-e e0)
     (- (interp-bits e0) 2)]
    [(zero?-e e0)
     (value->bits (zero? (interp e0)))]
    [(if-e e0 e1 e2)
     (if (interp e0)
         (interp-bits e1)
         (interp-bits e2))]))

Still correct:

Examples
> (for-each interp-bits-correct es)

We can rewrite by the equation

(zero? (interp e0)) = (zero? (interp-bits e0))

and inline value->bits specialized to a boolean argument:

Examples
; Expr -> Bits
(define (interp-bits e)
  (match e
    [(int-e i) (* 2 i)]
    [(bool-e b) (if b 3 1)]
    [(add1-e e0)
     (+ (interp-bits e0) 2)]
    [(sub1-e e0)
     (- (interp-bits e0) 2)]
    [(zero?-e e0)
     (match (zero? (interp-bits e0))
       [#t 3]
       [#f 1])]
    [(if-e e0 e1 e2)
     (if (interp e0)
         (interp-bits e1)
         (interp-bits e2))]))

Still correct:

Examples
> (for-each interp-bits-correct es)

Finally, in the last case, all that matters in (if (interp e0) ...) is whether (interp e0) returns #f or something else. So we can rewrite in terms of whether (interp-bits e0) produces the representation of #f (#b01):

Examples
; Expr -> Bits
(define (interp-bits e)
  (match e
    [(int-e i) (* 2 i)]
    [(bool-e b) (if b 3 1)]
    [(add1-e e0)
     (+ (interp-bits e0) 2)]
    [(sub1-e e0)
     (- (interp-bits e0) 2)]
    [(zero?-e e0)
     (match (zero? (interp-bits e0))
       [#t 3]
       [#f 1])]
    [(if-e e0 e1 e2)
     (match (interp-bits e0)
       [1 (interp-bits e2)]
       [_ (interp-bits e1)])]))

Still correct:

Examples
> (for-each interp-bits-correct es)

Note that whenever bs are bits representing an integer, then (value->bits (add1 (bits->value bs))) is equal to (+ bs 2), i.e. adding #b10. When bs represents a boolean, then (value->bits (add1 (bits->value bs))) would crash, while (+ bs 2) doesn’t, but this is an undefined program, so changing the behavior is fine.

Looking back: starting from the spec, we’ve arrived at a definition of interp-bits that is completely self-contained: it doesn’t use interp at all. It also only uses the Bits representation and does no conversions to or from Values.

We can recover the original interpreter by wrapping the bit interpreter in a final conversion:

Examples
; Expr -> Value
> (define (interp.v2 e)
(bits->value (interp-bits e)))
> (interp.v2 (bool-e #t))
#t
> (interp.v2 (bool-e #f))
#f
> (interp.v2 (sexpr->ast '(if #f 1 2)))
2
> (interp.v2 (sexpr->ast '(if #t 1 2)))
1
> (interp.v2 (sexpr->ast '(if 0 1 2)))
1
> (interp.v2 (sexpr->ast '(if 7 1 2)))
1
> (interp.v2 (sexpr->ast '(if (zero? 7) 1 2)))
2
> (interp.v2 (sexpr->ast '(add1 #f)))
#t
> (interp.v2 (sexpr->ast '(add1 #t)))
match: no matching clause for 5

Notice the last two examples. What’s going on?

The interp.v2 function is also a correct interpreter for Dupe, and importantly, it sheds like how to implement the compiler since it uses the same representation of values.

7.4 An Example of Dupe compilation

The most significant change from Con to Dupe for the compiler is the change in representation, but having sorted those issues out at the level of interp-bits, it should be pretty easy to write the compiler.

Let’s consider some simple examples:

42: this should compile just like integer literals before, but needs to use the new representation, i.e. the compiler should produce '(mov rax 84), which is (* 42 2).
#f: this should produce '(mov rax 1).
#t: this should produce '(mov rax 3).
(add1 e): this should produce the instructions for e followed by an instruction to add 2, which is just how interp-bits interprets an add1.
(sub1 e): should work like (add1 e) but subtracting 2.
(zero? e): this should produce the instructions for e follows by instructions that compare 'rax to 0 and set 'rax to #t (i.e. 3) if true and #f (i.e. 1) otherwise.
(if e0 e1 e2): this should work much like before, compiling each subexpression, generating some labels and the appropriate comparison and conditional jump. The only difference is we now want to compare the result of executing e0 with #f (i.e. 1) and jumping to the code for e2 when they are equal.

Examples
> (compile-e (int-e 42))
'((mov rax 84))
> (compile-e (bool-e #t))
'((mov rax 3))
> (compile-e (bool-e #f))
'((mov rax 1))
> (compile-e (sexpr->ast '(zero? 0)))
'((mov rax 0) (cmp rax 0) (mov rax 1) (jne nzero3223) (mov rax 3) nzero3223)
> (compile-e (sexpr->ast '(if #t 1 2)))
'((mov rax 3) (cmp rax 1) (jne if3224) (mov rax 4) (jmp if3225) if3224 (mov rax 2) if3225)
> (compile-e (sexpr->ast '(if #f 1 2)))
'((mov rax 1) (cmp rax 1) (jne if3226) (mov rax 4) (jmp if3227) if3226 (mov rax 2) if3227)

7.5 A Compiler for Dupe

Based on the examples, we can write the compiler:

dupe/compile.rkt
  #lang racket
  (provide (all-defined-out))
  (require "ast.rkt")

  ;; Expr -> Asm
  (define (compile e)
    `(entry
      ,@(compile-e e)
      ret))

  ;; Expr -> Asm
  (define (compile-e e)
    (match e
      [(int-e i)
       `((mov rax ,(* i 2)))]
      [(bool-e b)
       `((mov rax ,(if b #b11 #b01)))]
      [(add1-e e1) (let ((c1 (compile-e e1)))
                  `(,@c1
                    (add rax 2)))]
      [(sub1-e e1) (let ((c1 (compile-e e1)))
                  `(,@c1
                    (sub rax 2)))]
      [(zero?-e e1) (let ((c1 (compile-e e1))
                          (l1 (gensym "nzero")))
                   `(,@c1
                    (cmp rax 0)
                    (mov rax #b01)
                    (jne ,l1)
                    (mov rax #b11)
                    ,l1))]
      [(if-e p t f) (let ((c1 (compile-e p))
                          (c2 (compile-e t))
                          (c3 (compile-e f))
                          (l1 (gensym "if"))
                          (l2 (gensym "if")))
                      `(,@c1
                        (cmp rax #b01) ; compare to false
                        (jne ,l1)
                        ,@c3
                        (jmp ,l2)
                        ,l1
                        ,@c2
                        ,l2))]))

The one last peice of the puzzle is updating the run-time system to incorporate the new representation. The run-time system is essentially playing the role of bits->value: it determines what is being represented and prints it appropriately. However instead of using high-level mathematical operations like even?, /, etc., it uses low-level bit operations.

It uses an idiom of “masking” in order to examine on particular bits of a value. So for example if we want to know if the returned value is an integer, we do a bitwise-and of the result and 1. This produces a single bit: 0 for integer and 1 for boolean. In the case of an integer, to recover the number being represented, we need to divide by 2, which can be done efficiently with a right-shift of 1 bit. Likewise with a boolean, if we shift right by 1 bit there are two possible results: 0 for false and 1 for true:

dupe/main.c

#include <stdio.h>
#include <inttypes.h>

#define typeof_mask 1 
#define val_shift   1 
#define type_fixnum 0 
#define type_bool   1 


int64_t entry();

int main(int argc, char** argv) {
  int64_t result = entry();
  switch (typeof_mask & result) {
  case type_fixnum:
    printf("%" PRId64 "\n", result >> val_shift);
    break;
  case type_bool:
    printf("#%c\n", (result >> val_shift) ? 't' : 'f');
    break;
  }
  return 0;
}

Examples
> (asm-interp (compile (bool-e #t)))
#t
> (asm-interp (compile (bool-e #f)))
#f
> (asm-interp (compile (sexpr->ast '(zero? 0))))
#t
> (asm-interp (compile (sexpr->ast '(zero? -7))))
#f
> (asm-interp (compile (sexpr->ast '(if #t 1 2))))
1
> (asm-interp (compile (sexpr->ast '(if #f 1 2))))
2
> (asm-interp (compile (sexpr->ast '(if (zero? 0) (if (zero? 0) 8 9) 2))))
8
> (asm-interp (compile (sexpr->ast '(if (zero? (if (zero? 2) 1 0)) 4 5))))
4

7.6 Correctness and testing

We can randomly generate Dupe programs. The problem is many randomly generated programs will have type errors in them:

Examples
> (require "random.rkt")
> (random-expr)
#t
> (random-expr)
'(sub1 -5)
> (random-expr)
'(if #f #t (sub1 (zero? #t)))
> (random-expr)
'(if -1025 (add1 (if 1 (zero? #t) #t)) (sub1 #f))
> (random-expr)
'(zero? (add1 #t))
> (random-expr)
-4

When interpreting programs with type errors, we get Racket errors, i.e. the Racket functions used in the implementation of the interpreter will signal an error:

Examples
> (interp (sexpr->ast '(add1 #f)))
+: contract violation
  expected: number?
  given: #f
  argument position: 1st
  other arguments...:
   1
> (interp (sexpr->ast '(if (zero? #t) 7 8)))
zero?: contract violation
  expected: number?
  given: #t

On the hand, the compiler will simply do something by misinterpreting the meaning of the bits:

Examples
> (asm-interp (compile (sexpr->ast '(add1 #f))))
#t
> (asm-interp (compile (sexpr->ast '(if (zero? #t) 7 8))))
8

This complicates testing the correctness of the compiler. Consider our usual appraoch:

Examples
> (define (check-correctness s)
    (let ((e (sexpr->ast s)))
      (check-equal? (asm-interp (compile e))
                    (interp e)
                  e)))
> (check-correctness '(add1 7))
> (check-correctness '(add1 #f))
+: contract violation
  expected: number?
  given: #f
  argument position: 1st
  other arguments...:
   1

This isn’t a counter-example to correctness because '(add1 #f) is not meaningful according to the semantics. Consequently the interpreter and compiler are free to do anything on this input.

Since we know Racket will signal an error when the interpreter tries to interpret a meaningless expression, we can write an alternate check-correctness function that catches any exceptions and produces void, effectively ignoring the test:

Examples
> (define (check-correctness s)
    (let ((e (sexpr->ast s)))
      (with-handlers ([exn:fail? void])
        (check-equal? (asm-interp (compile e))
                      (interp e)
                      e))))
> (check-correctness '(add1 7))
> (check-correctness '(add1 #f))

Using this approach, we check the equivalence of the results only when the interpreter runs without causing an error.

← prev up next →

	Syllabus
	Texts
	Schedule
	Notes
	Assignments
	Midterms
	Project
	Racket

1	What is a Compiler?
2	From OCaml to Racket
3	Abscond: a language of numbers
4	Agreement: a language of numbers between friends
5	Blackmail: incrementing and decrementing
6	Con: branching with conditionals
7	Dupe: a duplicity of types
8	Extort: when errors exist
9	Fraud: local binding and variables
10	Refactoring the Compiler
11	Grift: binary operations
12	Hustle: heaps and lists
13	Iniquity: function definitions and calls
14	Jig: jumping to tail calls
15	Knock: first-class function (pointers)
16	Using Graphviz/ dot to visualize our AST
17	Loot: lambda the ultimate
18	Shakedown: Calling functions C functions

7.1	Integers and Booleans
7.2	Meaning of Dupe programs
7.3	Ex uno plures: Out of One, Many
7.4	An Example of Dupe compilation
7.5	A Compiler for Dupe
7.6	Correctness and testing