{"size": 13723, "ext": "scrbl", "max_stars_repo_path": "www/notes/neerdowell.scrbl", "max_stars_repo_name": "plum-umd/cmsc430", "max_stars_repo_stars_event_min_datetime": "2021-04-08T15:54:52.000Z", "max_stars_repo_stars_event_max_datetime": "2022-01-10T06:43:32.000Z", "max_issues_repo_path": "www/notes/neerdowell.scrbl", "max_issues_repo_name": "plum-umd/cmsc430", "max_issues_repo_issues_event_min_datetime": "2021-01-16T14:38:10.000Z", "max_issues_repo_issues_event_max_datetime": "2021-12-28T00:12:56.000Z", "max_forks_repo_path": "www/notes/neerdowell.scrbl", "max_forks_repo_name": "plum-umd/cmsc430", "max_forks_repo_forks_event_min_datetime": "2020-05-02T21:44:12.000Z", "max_forks_repo_forks_event_max_datetime": "2022-03-12T00:18:12.000Z"}
{"max_stars_count": 13, "max_issues_count": 15, "max_forks_count": 14, "avg_line_length": 33.0674698795, "max_line_length": 164, "alphanum_fraction": 0.6757268819}
#lang scribble/manual

@(require (for-label (except-in racket compile ... struct?) a86))
@(require redex/pict
	  racket/runtime-path
	  scribble/examples
	  "utils.rkt"
	  "ev.rkt"
	  "../fancyverb.rkt"
	  "../utils.rkt")

@(define codeblock-include (make-codeblock-include #'h))

@(ev '(require rackunit a86))
@(ev `(current-directory ,(path->string (build-path notes "neerdowell"))))
@(void (ev '(with-output-to-string (thunk (system "make runtime.o")))))
@(void (ev '(current-objs '("runtime.o"))))
@(for-each (λ (f) (ev `(require (file ,f))))
	   '("interp.rkt" "compile.rkt" "compile-expr.rkt" "compile-literals.rkt" "compile-datum.rkt" "utils.rkt" "ast.rkt" "parse.rkt" "types.rkt" "unload-bits-asm.rkt"))

@title[#:tag "Neerdowell"]{Neerdowell: structures}

@emph{Structures don't march in the streets.}

@table-of-contents[]

@section[#:tag-prefix "neerdowell"]{Defining structs}

So far we've built up a number of important datatypes in our language:
integers, booleans, characters, pairs, lists, boxes, vectors, strings,
symbols, and functions, to be precise.  But despite all of this,
programmers may still want more.  In fact, we probably can't
anticipate all of the possible datatypes they might want, so let's
instead provide a mechanism for defining new kinds of datatypes.
We'll add the same @racket[struct] mechanism for user-defined
structure types that we've been using all semester.

We'll call it @bold{Neerdowell}.


@section[#:tag-prefix "neerdowell"]{Syntax}

We will add the following concrete syntax to Neerdowell programs:

@#reader scribble/comment-reader
(racketblock
(struct _struct-type (_field0 ...))
)

Structure type definitions will only be allowed at the top-level along
with other definitions, so a Neerdowell program might look like:

@#reader scribble/comment-reader
(racketblock
(struct posn (x y))
(posn 1 2)
)

Each structure definition creates four kinds of things:

@itemlist[

@item{A constructor, e.g. @racket[posn].}

@item{A predicate, e.g. @racket[posn?].}

@item{A set of accessor functions, e.g. @racket[posn-x] and @racket[posn-y].}

@item{A pattern constructor, e.g. @racket[posn].}
]

The constructor is a function that takes as many arguments as fields
in the structure type definition and creates an instance of that
structure type with the given arguments populating the fields.

The predicate is a unary function that takes any value and returns
@racket[#t] is an instance of that structure type.

The accessor functions are each unary functions that take an instance
of the structure type and retrieve the value of the corresponding
field.

We're going to take a slightly different approach to parsing and
interpreting/compiling structure definitions.  Rather than
implementing the structure operations directly, we will instead
consider a set of generic structure operations that can be used to
implement the constructor, predicate, and accessor operations.

A structure definition will be translated into a set of source-level
function definitions that use these generic operations to implement
the structure-specific operations.  That translation will be
carried-out by the parser.

Here are the generic operations:

@#reader scribble/comment-reader
(racketblock
;; make-struct : Symbol Value ... -> StructVal
;; struct? : Symbol Value -> Boolean
;; struct-ref : Symbol Int StructVal -> Value
)

Here the @tt{Symbol} argument represents the name of the structure
type.  So for example, to create an instance of the @racket[posn]
structure type, you'd call @racket[(make-struct 'posn 1 2)].  To check
if @racket[_x] is an instance of a @racket[posn] structure, you'd call
@racket[(struct? 'posn _x)].  To access the first field of an instance
of a @racket[posn] structure type @racket[_x], you'd call @racket[(struct-ref
'posn 0 _x)].

With these operations in mind, you can see @racket[struct] as a kind
of shorthand:

@#reader scribble/comment-reader
(racketblock

(struct posn (x y))

;; means:

(define (posn x y)
  (make-struct 'posn x y))

(define (posn? x)
  (struct? 'posn x))

(define (posn-x x)
  (struct-ref 'posn 0 x))

(define (posn-y x)
  (struct-ref 'posn 1 x))
)

To accomplish this, we add the following function to the parser:

@#reader scribble/comment-reader
(racketblock
;; parse-struct : S-Expr -> [Listof Defn]
)

Here's an example:

@ex[
(parse-struct '(struct posn (x y)))
]

And here's an example of an expression that makes use of some of the
operations:

@ex[
(parse-e '(posn-x (posn 3 4)))
]

The generic struct primitives are @emph{only} used by the code
generated by the struct definitions, a property which is achieved by
the parser by not treating @racket['make-struct], @racket['struct?],
and @racket['struct-ref] as keywords.  If you write a program that
uses these names, they will be treated as variables, not primitives:

@ex[
(parse-e '(struct? 'posn x))
]

The @racket[parse-struct] function is defined as follows:

@filebox-include-fake[codeblock "neerdowell/parse.rkt"]{
;; S-Expr -> [Listof Defn]
(define (parse-struct s)
  (match s
    [(list 'struct (? symbol? n) flds)
     (if (andmap symbol? flds)
         (list* (make-struct-defn-construct n flds)
                (make-struct-defn-predicate n)
                (make-struct-defn-accessors n (reverse flds)))  
         (error "parse struct definition error"))]
    [_ (error "parse struct definition error")]))

;; Id [Listof Id] -> [Listof Defn]
(define (make-struct-defn-construct n flds)
  (Defn n flds
    (Prim 'make-struct (cons (Quote n) (map Var flds)))))

;; Id -> [Listof Defn]
(define (make-struct-defn-predicate n)
  (Defn (symbol-append n '?) (list 'x)
    (Prim 'struct? (list (Quote n) (Var 'x)))))
     
;; Id [Listof Id] -> [Listof Defn]
(define (make-struct-defn-accessors n flds)
  (match flds
    ['() '()]
    [(cons f flds)
     (cons (Defn (symbol-append n '- f) (list 'x)
             (Prim 'struct-ref
                   (list (Quote n)
                         (Quote (length flds))
                         (Var 'x))))
           (make-struct-defn-accessors n flds))]))

;; Symbol ... -> Symbol
(define (symbol-append . ss)
  (string->symbol
   (apply string-append (map symbol->string ss))))
}


@section[#:tag-prefix "neerdowell"]{Structure and Interpretation}

In the interpreter, we choose to represent a structure instance as an
instance of a @racket[StructVal] structure, which will contain the
structure type name (represented as a symbol) and a vector, which
holds the values of the fields:

@#reader scribble/comment-reader
(racketblock
;; type Value = ...
;;            | (StructVal Symbol (Vectorof Val))
)

So for example the value produced by @racket[(posn 3 4)] would be
@racket[(StructVal 'posn #(3 4))].  With this representation,
implementing the generic operations is pretty simple.  Here's the
complete @racket[interp-prims] function.

@filebox-include-fake[codeblock "neerdowell/interp-prims.rkt"]{
;; type Struct = (StructVal Symbol (Vectorof Value))
(struct StructVal (name vals))

;; Op [Listof Value] -> Answer
(define (interp-prim p vs)
  (match (cons p vs)
    ;; ...
    [(list 'struct? s v)
     (match v
       [(StructVal n _) (eq? s n)]
       [_ #f])]
    [(list 'struct-ref s i (StructVal n vs))
     (if (and (eq? s n) (<= 0 i (sub1 (vector-length vs))))
         (vector-ref vs i)
         'err)]
    ;; OpN
    [(cons 'make-struct (cons (? symbol? n) vs))
     (StructVal n (list->vector vs))]))
}

And we can try it out:

@ex[
(define (run . p)
  (interp (parse p)))
  
(run '(struct posn (x y))
     '(posn? (posn 3 4)))

(run '(struct posn (x y))
     '(posn-x (posn 3 4)))

(run '(struct posn (x y))
     '(posn-y (posn 3 4)))
]

@section[#:tag-prefix "neerdowell"]{Compiling Structures}

Providing support for structures in the compiler largely follows the
same outline of previous additions.  In particular, we add yet another
tagged pointer type to represent structure instances.  The runtime is
extended to add support for printing structures.

Structure instance are represented as an array of values.  The first
element is a symbol, which names the structure type and the remaining
elements hold the values of the fields for the structure.  The length
of the structure is not stored in memory since the width of structure
instances is statically determined, just like closures.

Compiling the @racket[struct?] and @racket[struct-ref] operations are
fairly straightforward, requiring just a slight bit more than say
@racket[vector?] and @racket[vector-ref].  The slight be more being
the checking that the structure type symbols match between the
(automatically inserted) argument and the structure instance value.
The @racket[struct-ref] operation actually requires slightly less in
that there's no need for bounds checking since it is the compiler
itself that inserted indices and we can trust the code we wrote is
correct.  For a similar reason, there's no need to do type tag
checking on the structure type and index arguments, but there still
needs to be checking of the structure instance argument since that
comes from the user.

One consequence of the source transformation approach to implementing
structures is that, although the type structure symbol and the integer
index have known, fixed types (a symbol and an integer, respectively),
they will still be represented as arbitrary values, i.e. as tagged
pointers or bit-shifted numbers.  That means the operations must
compute accordingly and there's a small performance hit because of it.
(It wouldn't be difficult to specialize the compilation of these
primitives so these arguments are treated distinctly, thus avoiding
the performance hit, but making the compiler itself more complicated.)

Here is the implementation of @racket[compile-op] for @racket[struct?]
and @racket[struct-ref]:

@filebox-include-fake[codeblock "neerdowell/compile-ops.rkt"]{
;; Op -> Asm
(define (compile-op p)
  (match p
    ;; ...
    ['struct?
     (let ((f (gensym))
           (t (gensym)))
       (seq (Pop r8)
            ; don't need to do this we generated the code
            ; (assert-symbol r8) 
            (Mov r9 rax)             ; check the tag bits
            (And r9 ptr-mask)
            (Cmp r9 type-struct)     ; compare tag to the structure tag
            (Jne f)                  ; not a structure
            (Xor rax type-struct)    ; untag the structure pointer
            (Mov rax (Offset rax 0)) ; get the structure type symbol
            (Cmp r8 rax)             ; compare it to the type argument
            (Mov rax (imm->bits #t))
            (Jne f)                  ; a structure, but not this kind
            (Jmp t)                  ; a structure of the same kind
            (Label f)
            (Mov rax (imm->bits #f))
            (Label t)))]

   ['struct-ref
     (seq (Pop r8)
          (Pop r11)
	  ; don't need to check
	  ; (assert-symbol r11)
	  ; (assert-integer r8)
          (assert-struct rax)
          (Xor rax type-struct)
          (Mov r10 (Offset rax 0))  ; get the structure type symbol
          (Cmp r11 r10)             ; compare it to the type argument
          (Jne 'raise_error_align)  ; a structure, but not this kind
          (Sar r8 int-shift) ; convert to raw int
          (Add r8 1)         ; +1 to skip symbol element
          (Sal r8 3)         ; *4 for byte offset
          (Add rax r8)
          (Mov rax (Offset rax 0)))]))
}

Handling @racket[make-struct] is slightly more complicated.  The
complication comes from the fact that @racket[make-struct] needs to be
a primitive that accepts an arbitrary number of arguments.  All other
primitives have a fixed arity so they know if and how many arguments
to pop from the stack, whereas for @racket[make-struct] it depends on
the kind of structure being created.

We assume the @racket[make-struct] primitive is given the appropriate
number of arguments.  (This is consistent with many other assumptions
we make about that well-formedness of programs that are not explicitly
checked by the compiler.)  Under this assumption, the number of
arguments indicates how many values to pop, so we have a special case
for @racket[make-struct] in @racket[compile-prim] to compute the
length and call a separate function for handling the
@racket[make-struct] operation:

@filebox-include-fake[codeblock "neerdowell/compile-expr.rkt"]{
;; Op (Listof Expr) CEnv -> Asm
(define (compile-prim p es c)
  (seq (compile-es* es c)  
       (match p
         ['make-struct (compile-make-struct (length es))]
         [_ (compile-op p)])))
}

The @racket[compile-make-struct] function is defined as follows:

@filebox-include-fake[codeblock "neerdowell/compile-ops.rkt"]{
;; Nat -> Asm
;; Emit instructions for creating a structure of length n
;; using values on top of stack
(define (compile-make-struct n)
  (seq (compile-make-struct/a n 1)
       (Mov rax rbx)
       (Or rax type-struct)
       (Add rbx (* 8 n))))

;; Nat Nat -> Asm
;; Pop elements off stack, writing them to heap
(define (compile-make-struct/a n i)
  (if (= n i)
      (seq (Mov (Offset rbx (* 8 (- n i))) rax))
      (seq (Mov (Offset rbx (* 8 (- n i))) rax)
           (Pop rax)
           (compile-make-struct/a n (add1 i)))))
}

We can now see structures in action:

@ex[
(define (run . p)
  (unload/free (asm-interp (compile (parse p)))))

(run '(struct posn (x y))
     '(posn? (posn 3 4)))

(run '(struct posn (x y))
     '(let ((p (posn 3 4)))
       (cons (posn-x p)
             (posn-y p))))

(run '(struct leaf ())
     '(struct node (v l r))
     '(define (count bt)
       (if (leaf? bt)
           0
	   (+ 1 (+ (count (node-l bt))
	           (count (node-r bt))))))
      '(count (node 8
                    (node 3 (leaf) (leaf))
		    (leaf))))
]