SI413 Class 20:

Reading

Section 6.1 of the textbook.

Homework

• As the book mentions near the end of Section 6.1, some languages offer "multiway" assignment. One might imagine this working as follows in SPL:

  new div := lambda args { new x := args[0]; new y := args[1]; new q := x/y; new r := x - q*y; res := (q,r); };
  new ans := div((27,3));
  write ans[0];
  9
  write ans[1];
  0
  new q := 0;
  new r := 0;
  (q,r) := div((27,3));
  write q;
  9
  write r;
  0 
  	

  1. Sketch out what additional things need to change (assuming arrays are actually available as detailed in the notes below) to make this happen? You don't have to give specific code, but describe which parts need to change and how. For instance, does the lab8.l file need to change? Does the grammar need to change? Does eval need to change? For each change, state briefly what needs to happen.
  2. One detail about your changes: what would you need to ensure about each component of the left-hand-side array?

Arrays & l-values

At some point in programming we'll always want our good friend: the array. The semantics of arrays in every language we know - C, C++, Java, Scheme - is that an object of type "array" is pointer/reference to some sequential arrangement of objects. Thus, assignment of arrays or passing arrays in and out of functions never makes copies of the objects within the array, only the reference.

int *A = new int[5];
int *B = A;

> (define A '#(1 2 3 4 5))
> (vector-ref A 3)
4
> (define B A)
> (vector-set! B 3 9)
> A
#5(1 2 3 9 5)
	

This means, as you of course know, that changing an element in B changes the elements as seen by A as well. Also, a valid expression that can be used as the 'index' into an array is known as an "i-value."

Now let's imagine how to add arrays to our SPL interpreter. It's not hard, here it is:

1. Add the lines

   "("        { yylval = 0; return LP; }
   ")"        { yylval = 0; return RP; }
   "["        { yylval = 0; return LK; }
   "]"        { yylval = 0; return RK; }
   ","        { yylval = 0; return COMMA; }
   	    

   to your lab8.l file.
2. Add the lines

   const int _explist = 17;
   const int _arrayref = 19;
   	    

   to your ast.h file. NOTE: you may need different numerical values, but you should be able to figure that out.
3. Add LK, RK and COMMA to your list of tokens at the top of lab8.ypp.
4. Add the following to the exp grammar rules in lab8.ypp:

   | exp LK exp RK       { $$ = new Node(_arrayref,0,"",$1,$3); }
   | LP RP                     { $$ = new Node(_explist,0,""); }
   | LP exp COMMA RP { $$ = new Node(_explist,0,"",$2); }
   | LP expl RP             { $$ = $2; }
   	    

   and add the new rule

   	    
   expl: expl COMMA exp { $1->child.push_back($3); $$ = $1; }
   | exp COMMA exp      { $$ = new Node(_explist,0,"",$1,$3); }
   

   as well.
5. In lab8.ypp add the following cases to eval:

     case _arrayref:
       Obj A = eval(root->child[0],env);
       if (A.otype != _oarray) 
       { cerr << "Subscripting non-array" << endl; return nullobj; }
       Obj I = eval(root->child[1],env);
       if (I.otype != _oint) 
       { cerr << "Subscripting array with non-int" << endl; return nullobj; }
       return (*A.aval)[I.ival];
     case _explist: {
       Obj A; A.otype = _oarray;
       A.aval = new vector<Obj>(root->child.size());
       for(int i = 0; i < root->child.size(); ++i)
         (*A.aval)[i] = eval(root->child[i],env);
       return A;
     }
   

6. In lab8.ypp, modify your case for _asn to be the following (or something very like it):

     case _asn: {
       Obj RHS = eval(root->child[1],env);  
       if (root->child[0]->ntype == _id) // THE ID CASE
       {
         Frame *tenv = lookup(root->child[0]->idVal,env);
         if (tenv == NULL) {
   	cerr << "Undefined variable " << root->child[0]->idVal << endl; 
   	return nullobj; }
         (*tenv)[root->child[0]->idVal] = RHS; 
       }
       else if (root->child[0]->ntype == _arrayref) // THE ARRAY SUBSCRIPT CASE
       {
         Obj I = eval(root->child[0]->child[1],env);
         Obj A = eval(root->child[0]->child[0],env);
         (*A.aval)[I.ival] = RHS;
       }
       else
       {
         cerr << "Error! non l-value in assignment!" << endl;
       }
       if (root->child.back() != NULL) eval(root->child.back(),env);
       return nullobj; }
   

7. Finally, add to your Obj def's until you end up with something like:

   // Structure for representing SPL objects by a type/value pair
   class Obj
   {
   public:
     int otype; 
     union { int ival; bool bval; Closure *fval; vector<Obj> *aval; };
   };
   
   // Object "otype" codes: "_oundef" means undefined - it comes in handy
   const int _oundef = 0, _oint = 1, _obool = 2, _ofun = 3, _oarray = 4;
   
   // Handy functions for creating an Obj from a value
   Obj mkobj(int k)      { Obj o; o.otype = _oint;  o.ival = k; return o; }
   Obj mkobj(bool b)     { Obj o; o.otype = _obool; o.bval = b; return o; }
   Obj mkobj(Closure* p) { Obj o; o.otype = _ofun;  o.fval = p; return o; }
   

With all that done, you can do fun things like:

new foo := lambda args { new x := args[0]; new y := args[1]; if (y < x) { res := y; } else { res := x; } };
write foo((3,7));
3
write foo((7,3));
3
new div := lambda args { new x := args[0]; new y := args[1]; new q := x/y; new r := x - q*y; res := (q,r); };
new ans := div((27,3));
write ans[0];
9
write ans[1];
0

	  

... and much more.