Lecture 20 - November 1, 2007

We went over two pages on the exam: 

            the one on type, declaration and structural  equivalenced

            the one on bindings:  name, value, type, address.

 

Returned remaining Snobol programs

 

Returned first project submission.

 

In class quiz is shown below along with two additional code examples showing that Snobol does NOT print an error message when you

access an out of bounds array element.

 

 

* filename:  quiz.sno  -- in class quiz - November 1, 2007

 

 

     &TRIM  = 1

      A      = ARRAY(INPUT)

      I      = 1

READ  A<I>   = INPUT     :F(PRINT)

      I      = I + 1     :(READ)

PRINT I       = I - 1    

     OUTPUT   = A<I>      :S(PRINT)

END

     

                 

 

* filename:  quizzie.sno

* illustrates that Snobol provides no information about an out of bounds

* array index (see red code)

 

         &TRIM  = 1

         A      = ARRAY(INPUT)

      I      = 1

READ  A<I> = INPUT           :F(PRINT)

      I         = I + 1     :(READ)

PRINT I         = I - 1    

     OUTPUT     = A<I>      :S(PRINT)

     output     = A<300>   

END

 

– this file illustrates how to force Snobol to tell you if you go out of bounds

*                         - code in red shows how to do it

 

* filename:  quizzie2.sno

* illustrates how to force Snobol to tell you if you go out of bounds

* (see red code)

 

         &TRIM  = 1

         A      = ARRAY(INPUT)

         I      = 1

READ  A<I>  = INPUT           :F(PRINT)

      I         = I + 1     :(READ)

PRINT I         = I - 1    

     OUTPUT     = A<I>      :S(PRINT)

 

     output     =  a<300>    :f(err) s(end)

err  output = ' could not print a<300>'

END

 

 

 

We then talked about some additional Snobol features:  

the TABLE storage structure and

the DATA.primitive function

 

Snobol has an additional data structure known as a TABLE which is similar to an ARRAY except that ARRAY indexes are required to

be integers while TABLE indexes are not.

 

 

The primitive function DATA can be used to define the data type NODE with the two field functions, VALUE and LINK.   This is useful if you want to make a simple linear linked list made up of nodes, each containing a value field and a link field.

       DATA('NODE(VALUE,LINK'))

 

       P = NODE('S')      creates a node with value field S and the null string in the link field

 

The fields can be reference by VALUE(P) and LINK(P)

 

       P = NODE('T',P)   puts node T at the head of the list

       P = LINK(P)         deletes a node from the head of the list

 

We played around with  the DATA function. 

  1. we first created a single element list which didn't point anywhere.
  2. we then added an element to the head of the list
  3. we then added another element at the head of the list
  4. as we added each element we printed its value
  5. we then wrote code to print out all of the elements in the list
    1. we had to be reminded:  NEVER, EVER move the pointer to the head of the list away from the head of the list.
    2. can make a duplicate pointer point to the head of the list and move that
    3. alternatively as we create the list we can keep a pointer to the last element in the list.

NOTE:  in our example we wrote very repetitive code  to print out the contents of the list.  It  should be replaced by a loop once we

              have written enough repetitive code to know what the exit condition is.

 

In the box below is some of this code:

 

* filename node.sno

  DATA('NODE(VALUE,LINK)')

 

  P = NODE('S')

  OUTPUT  = VALUE(P)

  P = NODE('T',P)

  OUTPUT = VALUE(P)

  P = NODE('K',P)

  OUTPUT = VALUE(P)

  M = NODE('L')

  LINK(M) = P

  P = M

  OUTPUT = " value in P is " VALUE(P)

  OUTPUT = " value in M is " VALUE(M)

  OUTPUT = " Here are all of the value in the list from head to the end " HEAD = P

  OUTPUT = VALUE(P)

   P     = LINK(P)

   OUTPUT = VALUE(P)

    P    = LINK(P)

    OUTPUT = VALUE(P)

    P    = LINK(P)

    OUTPUT = VALUE (P)

 

END

 

 

 

 

 

Below is the problem that is to be submitted by 11:59 Monday night to Blackboard.

Let a binary tree be a data structure composed of nodes that contain three fields:  value, left son, right son.  A tree has a distinguished node, the root, that is not the left son or right son of any node.

 

  1. Define a data type BNODE with fields appropriate for a binary tree.

 

  1. Generate a binary tree with three nodes such that the value of the root is +, the value of the left son is X, and the value of the right son is Y.

 

  1. Define a function LLIST that prints out the value of the nodes of a binary tree in the following order:
    1. the value of the root
    2. the value of the nodes in the left subtree
    3. the value of the nodes in the right subtree