Crystal project

	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)

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

Crystal notes #1 (Nov 9)
Crystal vocabulary notes (Nov 15)

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

specifications for the tiny-crystal project