Menu

SI413 Class 20:


Reading
Section 6.1 of the textbook.

Homework

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.


Christopher W Brown
Last modified: Tue Dec 1 08:25:14 EST 2009