<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
Exercise 5: structured-code interpreter using structs

The goal of this exercise is to implement and specialize a recursive
structured-code interpreter written using structs.  But to cover a few
basics needed for next time, you're first going to specialize the
power program using function pointers.

(0) Power with function pointers

Implement a power function which takes a binary operator represented
as a function pointer as an argument, as well as the exponent,
neutral, and base value.  Make it specialize into something that
directly applies the operator.

Hints: provide alias information for the function pointer, so that
Tempo can eliminate it, and use post inlining.

Pitfalls:

 - Tempo apparently does not handle function pointers as argument to
   the entry point very well.  Solution: wrap the pointer (and perhaps
   also the neutral value?) in a struct, and pass this struct as an
   argument (which is kind of nice anyway).  Monovariant structures,
   which are explained below in (1) are fine here.

 - There are in some cases some issues with function pointers which
   cannot be found when Tempo tries to link the program for
   speicalization.  A solution is to put the magic

     AT2SPEC_struct.all_functions_present_externally:=true;

   in config.sml, and then provide definitions of the functions in
   your sctx.c file, for example:

     int add(int a, int b) { return *((int*)0); }
     int mul(int a, int b) { return *((int*)0); }
 
   (Tempo should never call them, it just uses their address, which is
   why I defined them to generate an error if called.)

 - The generated code might not look so nice, even after inlining in
   FLAT mode.  Here are my favorite flags for making the code nicer:

    post_porky := true;
    post_porky_flags := "-copy-prop -const-prop -dead-code -unused-syms -iterate";

  (if postprocessing breaks, turn them off again :-)

 - The functions must be in the main C file for Tempo to be able to be
   able to inline them (otherwise they will not be processed by
   Tempo).  Putting them in the actx.c file is not correct, since what
   goes there is not always real C code (it might just simulate the
   effects of the real code).  To be able to refer to them in the
   actx.c file, declare them as 'extern'.

(1) Interpreter with monovariant structures

Implement datastructures for representing an arithmetic expression
with operators, constants, and variables, for example:

struct Exp;

#define TAG_ADD 1
struct Add {
  struct Exp *left;
  struct Exp *right;
};

#define TAG_VAR 2
struct Variable {
  int identifier;
  /* resolved identifier, index into array which
     represents the environment */
};

union UExp {
  struct Add *add;
  struct Variable *variable;
};

struct Exp {
  char tag; /* holds TAG_x */
  union UExp exp; /* holds expression */
};

Add more expressions types, and write a recursive interpreter that
given an expression and an environment (as an array of ints) computes
the value of the expression.  Test that it works.

Then specialize the interpreter using Tempo.  Ideally, you should end
with something quite close to the equivalent C expression 
(post_inlining will be useful here).

Pitfalls:

 - Tempo does not understand union, it transforms it into a struct
   (using an evil #define in some cases, so be careful!)

 - By default, Tempo uses monovariant structures, which means that all
   structures of a given type are given the same binding time (flow
   sensitively - they can start out being static and then become
   dynamic).  To make the contents of a struct be static, list the
   structure in static_locations, e.g. 

     static_locations := ["Add.left", "Add.right", ...]

   it is not necessary to even initialize the parameters in the actx.c
   file.

 - "ABSYN.field_type_spec: no declaration found for field" means that
   you mistyped a field name in static_locations

 - The field Exp.exp is a struct, so it is not given a binding time
   (its binding time is that of the struct), so listing it in
   static_locations gives an error

 - Don't use casts between structs, the binding-time analysis does not
   understand them (and effectively ignores the effects)

(2) Interpreter with polyvariant structures

Create a new datastructure which makes use of the fact that structures
have compatible memory-layout, so that you no longer need the union,
e.g.:

struct Exp {
  int tag;
}

struct Add {
  int tag;
  struct Exp *left;
  struct Exp *right;
}

IMPORTANT: due to a bug in Tempo, the datastructure must be defined a
bit differently, see below; the example above illustrates the
principle.

IMPORTANT: Tempo does not know anything about memory layout, it uses
the names of the fields to trace what's going on.  So the fields of
the structs that you are going to cast between must have the same
names if the memory layout is compatible and different names if it is
not.

You can then for example use

  struct Exp *e = ...;
  if(e->tag==TAG_ADD) {
    struct Add *add = (struct Add*)e;
    ...
  }

However, this does not work correctly when using monovariant
structures - you could probably make the program specialize, but Tempo
has no idea what's going on.  If, for example, you were to modify the
tag field to become dynamic through a pointer qualified by 'Exp', it
would have no effect on the binding-time of the field 'tag' if it was
an 'Add' struct you were pointing to.

To turn on structure polyvariance, use:

  struct_version := MONOPOLY;
  poly_structs := POLY_STRUCTS["Exp","Add",...];

Note that the polyvariant binding time analysis is experimental, and
has even more quirks than Tempo normally does.

Pitfalls:

 - If no aliases are defined for a location, the binding-time analysis
   has a tendency to sometimes believe that dereferencing the location
   gives a static value - to specialize correctly, you must define a
   context.

 - A bug in Tempo prevents you from using the 'tag' field as above.
   The tag field must be a struct, as follows:

    struct Tag {
      int t;
    };
    
    struct Exp {
      struct Tag tag;
    };
    
    #define TAG_ADD 1
    struct Add {
      struct Tag tag;
      struct Exp *left;
      struct Exp *right;
    };

  (which should also be listed in POLY_STRUCTS).

 - A correct alias context is one which reflects that there are
   multiple 'Add' locations and that each field can point to multiple
   things.  I build the context as follows:

    struct Add add_loc[1];
    
    extern int staticvalue();
    
    void set_analysis_context(struct Exp **e, int **env) {
      if(staticvalue())
        add_loc[0].left = (struct Exp*)add_loc;
      else
        add_loc[0].left = (struct Exp*)var_loc;
      ...similarly for right and everything else...
      if(staticvalue())
        *e = (struct Exp*)add_loc;
      else
        ...
    }

 - An error like the following:

    structure Add must be monovariant
    structure Add must be monovariant
    ...
    structure Tag must be monovariant
    ERROR (TOP_FUNC 1): incorrect static_locations

   The first couple of lines are not errors - only the last line is an
   error, and it indicates that your polyvariant structs have been
   listed by type in static_locations, which does not make sense.  Get
   rid of the static_locations declaration, you don't need it for the
   poly structs.