Applying Crary and Weirich to
Adaptive Programming in Functional Style a la Shriram and Mitch
===============================================================

Example: Finding free variables in a Scheme-like program.

What is the complexity of the following method:

In class Program:
List freeVariables(ClassGraph cg, String strategy) {
 return (List) cg.traverse(this, strategy, new FreeVariablesVisitor());
 }

Questions:

Do your "Resource Bound Certification" techniques apply here?
The program is very generic: we don't know the class graph
(to be constructed by reflection) and we don't know the strategy.

How does the running time of the program depend on the 
structure of the class graph and the strategy?

import edu.neu.ccs.demeter.dj.*;
import java.util.*;
import edu.neu.ccs.demeter.*;

class FreeVariablesVisitor extends FunctionVisitor {

         Object combine(Object[] values) {

              if(values.length==0)
                 return null;

              if(values[0] != null && values[0] instanceof Hashtable) {
                     Hashtable h=(Hashtable) values[0];
                     
                     for(int i=1;i<values.length; i++)
                       if(values[i]!=null)
                          h.putAll((Hashtable)values[i]);
                  
                     return h;
              }

              List result = new ArrayList();
              
              for(int i=0;i<values.length; i++) {
                  if(values[i]!=null)
                     result.addAll((List)values[i]);
              }

              return result;

          }

          Object around(LetNode l,Subtraversal st) {
              Hashtable h = (Hashtable)st.apply("bindings");
              System.out.println("Contents of hashtable "+h);
              System.out.println("End of hashtable");
              List aList = (List)st.apply("nodelist");
              java.util.Collection c = h.values();

              List result = new ArrayList();

              Iterator it = c.iterator();
              while(it.hasNext()) {
                  List ll=(List)it.next();
                  result.addAll(ll);
              }

              it = aList.iterator();
              while(it.hasNext()) {
                  String s = (String) it.next();

                  if(!h.containsKey(s))
                      result.add(s);
              }
              
              
              return result;
          }

          Object around(Ident id,Subtraversal st) {
              List aList = new ArrayList();
              
              aList.add(id.toString());

              return aList;
          }

          Object around(Binding b,Subtraversal st) {
              Hashtable table = new Hashtable();
              List aList1 = (List) st.apply("ident");
              List aList2 = (List) st.apply("node");
              

              table.put(aList1.get(0),aList2);

              return table;
          }

          Object around(ProcNode p,Subtraversal st) {
              Hashtable h = (Hashtable)st.apply("formalparameters");
              List aList = (List)st.apply("nodelist");

              List result = new ArrayList();

              Iterator it = aList.iterator();
              while(it.hasNext()) {
                  String s = (String) it.next();

                  if(!h.containsKey(s))
                      result.add(s);
              }


              return result;

          }

          Object around(FormalParameter f, Subtraversal st) {
              Hashtable table = new Hashtable();
              List aList1 = (List) st.apply("ident");
              String s = new String("useless");
              

              table.put(aList1.get(0),s);

              return table;
          } 

}
import edu.neu.ccs.demeter.dj.*;
import java.util.*;
import edu.neu.ccs.demeter.*;
class Main {
  static public void main(String args[]) throws Exception {
    ClassGraph cg=new  ClassGraph(true,false);

    Program p = Program.parse(System.in);

    System.out.println("DJ start ");
    System.out.println();
    TraversalGraph allWeights = new TraversalGraph(
      "from Program bypassing -> *,tail,* to edu.neu.ccs.demeter.Ident",cg);
    System.out.println(" check free variables ");

    FunctionalOGS fogs=new FunctionalOGS(p,allWeights);

    List l=(List)fogs.traverse(new FreeVariablesVisitor());

    for(int i=0; i<l.size(); i++) {
       if(l.get(i) != null)
         System.out.println(l.get(i));
    }
					  }           
}

Class graph:
===========================

Program =  NodeList .
Node : lookahead (@ 2 @) AppNode | LetNode | lookahead (@ 2 @) AssignNode | lookahead (@ 2 @) AddNode| Term | ProcNode .
LetNode = "let" Bindings "in" NodeList .
AddNode = <a> Term "+" <b> Term .
Term : VarNode | LitNode .
VarNode = Ident .
LitNode = <v> int .
ProcNode = "proc" "(" [ FormalParameters ] ")" NodeList . 
AppNode = Ident "(" [ ActualParameters ] ")" .
AssignNode = Ident "=" Node .
Bindings = List(Binding) .
Binding = Ident "=" Node .
FormalParameters = NList(FormalParameter) .
FormalParameter = Ident .
ActualParameters = NList(ActualParameter) .
ActualParameter = Node . 
NodeList = "begin" List(Statement) "end" .
Statement = Node ";" .

NList(S) ~ S {"," S} .  
List(S) ~ {S} .


Input:
===========================
begin
let x=0
    y= proc(x,y) begin x+y; end
    in begin
            x+y;
           end;
end