Reinforcement Learning and Artificial Intelligence (RLAI)

# specifications for the tiny-crystal project

All changes to this spec since Nov 15 (the printed version) are listed at the end of the page.

PLEASE USE THE FOLLOWING DRIVER-LOOP FOR YOUR SUBMISSON:
This is the same driver-loop as given before, we're just emphasizing its use to make grading it possible.
Also, please use the name "the-global-path" as your global path to make this driver-loop work.

```(define (driver-loop)   (display "crystal> ")   (let ((name (read)))     (cond ((or (equal? name '(quit))            (equal? name '(exit))            (equal? name '(bye)))        (display "thank you for using the crystal interpreter")        (newline))       (else        (display (call name the-global-path))        (driver-loop))))) ```

The project is to implement in scheme an interpreter for an imaginary programming language called tiny crystal.

Tiny crystal is a version of crystal as presented in class but reduced and simplified to make it easier to implement. Tiny crystal differs from the crystal you have seen so far in that the set of vertices V is divided into terminals and nonterminals.  Terminal vertices are vertices that can't have outgoing edges. All scheme objects are terminals: numbers, symbols, #f, strings, pairs, procedures, etc. Nonterminal vertices, on the other hand, can have edges and child vertices (but do not have to). Nonterminal vertices are constructed by the elementary graph operation `make-nonterminal-vertex`. An important special kind of nonterminal vertex is the stub, used to implement virtual connections.

A consequence of the terminal/nonterminal divide is that names that return a terminal vertex cannot be extended to access other vertices.  Thus, if `(+ 1 1)` returns the vertex 2, then we can't add an additional vertex to the 2 that allows us to handle `(+ 1 1 1)`. To handle this case one would have to specify a separate virtual connection for the three-argument version of `+`.

Tiny crystal also differs in that connect names must be of fixed length.  Instead of saying `(connect a b c 7)` you must more explicitly say

`(connect '(a b c) 7)`

Another difference is that, in tiny crystal, virtual connections can include the symbol `?` preceding the labels corresponding to the formal parameters.  ```All labels after the ? must be formal parameters. ```For example:

```      (virtually-connect '(sum of squares ? x y)         '(+ (square (x))             (square (y)))) ```Your tiny crystal interpreter must be able to call (evaluate) this name (expression) and the other examples listed below.  To do this, some scheme procedures will have to be accessible as primitives.  Make the following accessible: ```+, -, *, /, =, <, >, equal, list, display, newline, if, ...  ```The basic non-primitive crystal names that your interpreter must handle are

```    connect     reconnect     virtually-connect     push-path     pop-path     new ```
See the crystal vocabulary notes for their semantics (modulo the differences noted above between crystal and tiny crystal).

Finally, and importantly, tiny crystal differs from full crystal in that vertices along the way of the virtual part (after the ?) of a virtual connection cannot be returned or connected to.  See the example near the end of this page.

Your interpreter must provide a scheme procedure "`call`" that can be applied to two scheme lists, one representing a name and the other a path, as in `(call '``(connect '(x) 5)```` path)```. The path must be a list of nonterminal vertices.  You must provide an initial path called the-global-path. Below are some names you must be able to call (these would have to be quoted to be used as input to `call`) and a printed representation of the vertex returned.  You do not have to use this printed representation, but the values returned by `call` must be correct.
``` (push-path (new))```
```     <nonterminal-vertex> () ``````     <nonterminal-vertex>```
```(connect '(x) 5)     5 ``````(connect '(y) 7)     7 ``````(connect '(z) 9)     9 ``````(x)     5 ``````(+ (x) (y))     12 ``````()     <nonterminal-vertex with edges (x . 5) (y . 7) (z . 9)> (connect '(ship) (new)) ``````     <nonterminal-vertex> ``````(push-path (ship))     <nonterminal-vertex> (connect '(x) 100)     100 (connect '(y) (+ (x) 10))     110 (connect '(dx) (connect '(dy) 0))     0 (x)     100 (reconnect '(x) (+ (x) 1))     101 (reconnect '(z) (+ (z) 1))     10 (pop-path)     ``````<nonterminal-vertex with edges (x . 101) (y . 110) (dx . 0) (dy . 0)>```
```(ship) ````    ````<nonterminal-vertex with edges (x . 101) (y . 110) (dx . 0) (dy . 0)> (x)     5 (y)     7 ``````(ship x)     101 (connect '(x) 3)     3 (connect-from (ship) '(x) 200)     200 (x)     3 (ship x) ````    ````200 ``````(list (x) (y) 4 x (ship dx) ship (new))     (3 7 4 x 0 ship <``````nonterminal-vertex>) ``` ```(virtually-connect '(factorial ? n)    '(if (= (n) 0)         1         '(* (n) (factorial (- (n) 1)))))     <stub> (factorial 4)     24 (factorial (connect '(x) 5))     120 ``````(virtually-connect '(square ? x)    '(* (x) (x))) ``````    <stub> (square (+ (x) 2))     49   ``````(virtually-connect '(sum of squares ? x y)    '(+ (square (x))        (square (y)))) ``````    <stub> ``````(sum of squares 6 7)     85 ``````(sum of squares 6 7 (x))     error: no match to ``````(sum of squares 6 7 5)```
```(connect '(sos) (sum of squares))     ``````<stub> (sos 2 3)     13 (push-path (sos)) ``````    <stub> ; the examples below are optional - not required for the project ; that is, you do not need to implement 'begin' nor the ability to ; process the virtual part of a virtual connection on its own (as in ; the immediately following example). (4 5)     41 ()     <stub> (pop-path) ``````    <stub> (sos)     ``````<stub> `````` (connect '(sos4) (sum of squares 4))     error: tiny crystal can't return intermediate virtual vertices (connect '(print foo)    (begin (display foo) (newline))) foo (print foo) (connect '(print foo)    '(begin (display foo) (newline)))     (begin (display foo) (newline))) (print foo)     (begin (display foo) (newline))) (virtually-connect '(print foo)    '(begin (display foo) (newline))) (print foo) foo . . . `````` ```You can construct your interpreter any way you want consistent with the above spec (and the spirit of the project), but you may find it helpful to break it into the four parts described in the following links.  If you follow the procedure names exactly as suggested here it may also enable us to give you more part marks if your interpreter is not completely correct.
The following documents are for the full version of crystal, not the tiny version used in the class project. But their general comments are still very relevant. In particular, see the discussion of the procedures `call` and `lookup` in the vocabulary notes.

Changes since Nov 15:

"new" was added to the list of basic crystal names that your interpreter must handle.

``` (connect ship (new)) ```was corrected to` ```` (connect '(ship) (new)) "if" ```was added to the list of scheme procedures that have to be accessible as primitives.

the text was corrected to indicate that stubs are nonterminal vertices, not terminal vertices.

Nov 19: some small corrections to the examples of crystal behavior on this page.

Extend this Page   How to edit   Style   Subscribe   Notify   Suggest   Help   This open web page hosted at the University of Alberta.   Terms of use  1995/0