Abstract syntax of quirk21.  [Revision 2]

Revision history:

Revision 2, 1 October 2004:
    Added the astFree and astUpdateFree operations.

Revision 1, 29 September 2004:
    Added comments to some of the constructors and selectors.
    Added a note concerning makeNewRecordExp and astNewRecordExp.fields.
    Corrected kDoubleType to kFloatType.

The abstract syntax used by our quirk21 compilers involves the
following data types:

    Qoperation          binary and unary operations
    Qkind               tags for different kinds of AST
    Qsymbol             identifiers et cetera
    Ast                 abstract syntax trees
    
    char                Scheme's characters
    string              Scheme's strings
    int                 Scheme's exact integers
    float               Scheme's inexact reals
    List(t)             Scheme's lists, restricted to elements
                          of type t
    
The Qoperation and Qkind data types are represented as Scheme
symbols.  Qsymbol and Ast are abstract data types that are
defined by their operations, which are listed and specified
below.

Some of these data types may later be extended to include more
operations.

                                * * *

Qoperation:

The following Scheme symbols are used to represent the unary and
binary operations of quirk21:

    NOP
    assign
    or
    and
    eq
    lt
    gt
    ne
    le
    ge
    eq_bool
    ne_bool
    eq_char
    ne_char
    eq_int
    lt_int
    gt_int
    ne_int
    le_int
    ge_int
    eq_float
    lt_float
    gt_float
    ne_float
    le_float
    ge_float
    plus
    minus
    times
    divide
    plus_int
    minus_int
    times_int
    divide_int
    plus_float
    minus_float
    times_float
    divide_float
    not
    length
    coerce_int_to_float

                                * * *
Qkind:

The following Scheme symbols are used to represent the different
kinds of abstract syntax trees:

    kVoidType
    kBoolType
    kCharType
    kIntType
    kFloatType
    kTypeId
    kArrayType
    kFunType
    kSumType
    kProductType

    kPgmDec
    kModDec
    kFunDec
    kVarDec
    kTypDec
    kFormalDec
    kBindingDec

    kLambdaExp
    kLetExp
    kLetrecExp
    kNewArrayExp
    kNewRecordExp
    kCaseExp
    kIfExp
    kBeginExp
    kBinOpExp
    kUnOpExp
    kLiteralExp
    kVarExp
    kCallExp
    kFieldExp
    kArrayExp

    kTrueLit
    kFalseLit
    kCharLit
    kStringLit
    kIntLit
    kFloatLit

                                * * *

Qsymbol:

Signature:

    Qsymbol.NOSYMBOL: Qsymbol

    Qsymbol.intern:   String -> Qsymbol
    Qsymbol.equals:   Qsymbol x Qsymbol -> boolean
    Qsymbol.toString: Qsymbol -> String

Specification:

  For every String s, s1, s2, and for some fixed but arbitrary
  String s0,

    NOSYMBOL = (Qsymbol.intern s0)

    (Qsymbol.equals (Qsymbol.intern s1) (Qsymbol.intern s2))
        =  (string=? s1 s2)

    (string=? (Qsymbol.toString (Qsymbol.intern s)))

Note:

It would be incorrect to assume that a Qsymbol is a Scheme symbol.

                                * * *

Ast:

Signature:

  Basic constructors:

    makeVoidType:        int -> Ast
    makeBoolType:        int -> Ast
    makeCharType:        int -> Ast
    makeIntType:         int -> Ast
    makeFloatType:       int -> Ast
    makeTypeId:          int x Qsymbol -> Ast
    makeArrayType:       int x Ast -> Ast
    makeFunType:         int x List(Ast) x Ast -> Ast
    makeSumType:         int x List(Ast) -> Ast         ; list of FormalDec
    makeProductType:     int x List(Ast) -> Ast         ; list of FormalDec

    makePgmDec:          int x Ast x List(Ast) -> Ast
    makeModDec:          int x List(Qsymbol) x List(Ast) x List(Ast) -> Ast
    makeFunDec:          int x List(Qsymbol) x List(Ast) -> Ast
    makeVarDec:          int x List(Qsymbol) x List(Ast) -> Ast
    makeTypDec:          int x List(Qsymbol) x List(Ast) -> Ast
    makeFormalDec:       int x Qsymbol x Ast -> Ast
    makeBindingDec:      int x Qsymbol x Ast -> Ast

    makeLambdaExp:       int x List(Ast) x Ast x Ast -> Ast
    makeLetExp:          int x List(Ast) x Ast -> Ast
    makeLetrecExp:       int x List(Ast) x Ast -> Ast
    makeNewArrayExp:     int x Ast x Ast x Ast -> Ast
    makeNewRecordExp:    int x Qsymbol x List(Ast) -> Ast ; list of FieldExp(*)
    makeCaseExp:         int x Ast x List(Qsymbol) x List(Qsymbol)
                                x List(Ast) x Ast -> Ast
    makeIfExp:           int x Ast x Ast x Ast -> Ast
    makeBeginExp:        int x List(Ast) -> Ast
    makeBinOpExp:        int x Qoperation x Ast x Ast -> Ast
    makeUnOpExp:         int x Qoperation x Ast -> Ast
    makeLiteralExp:      int x Ast -> Ast
    makeVarExp:          int x Qsymbol -> Ast
    makeCallExp:         int x Ast x List(Ast) -> Ast
    makeFieldExp:        int x Ast x Qsymbol -> Ast
    makeArrayExp:        int x Ast x Ast -> Ast

    makeTrueLit:         int -> Ast
    makeFalseLit:        int -> Ast
    makeCharLit:         int x char -> Ast
    makeStringLit:       int x string -> Ast
    makeIntLit:          int x int -> Ast
    makeFloatLit:        int x float -> Ast

  Selectors:

    astPos:                     Ast -> int
    astKind:                    Ast -> Qkind

    astTypeId.name:             Ast -> Qsymbol
    astArraytype.elementType:   Ast -> Ast
    astFuntype.argumentTypes:   Ast -> List(Ast)
    astFuntype.returnType:      Ast -> Ast
    astSumType.fields:          Ast -> List(Ast)          ; list of FormalDec
    astProductType.fields:      Ast -> List(Qsymbol)      ; list of FormalDec

    astPgmDec.exp:              Ast -> Ast
    astPgmDec.mods:             Ast -> List(Ast)
    astModDec.names:            Ast -> List(Qsymbol)
    astModDec.decs:             Ast -> List(Ast)
    astModDec.exps:             Ast -> List(Ast)
    astFunDec.names:            Ast -> List(Qsymbol)      ; names of formals
    astFunDec.exps:             Ast -> List(Ast)          ; types of formals
    astVarDec.names:            Ast -> List(Qsymbol)
    astVarDec.exps:             Ast -> List(Ast)
    astTypDec.names:            Ast -> List(Qsymbol)
    astTypDec.types:            Ast -> List(Ast)
    astFormalDec.name:          Ast -> Qsymbol
    astFormalDec.type:          Ast -> Ast
    astBindingDec.name:         Ast -> Qsymbol
    astBindingDec.exp:          Ast -> Ast                ; expression

    astLambdaExp.formals:       Ast -> List(Ast)          ; list of FormalDec
    astLambdaExp.returnType:    Ast -> Ast
    astLambdaExp.body:          Ast -> Ast                ; expression
    astLetExp.bindings:         Ast -> List(Ast)          ; list of BindingDec
    astLetExp.body:             Ast -> Ast                ; expression
    astLetrecExp.bindings:      Ast -> List(Ast)          ; list of BindingDec
    astLetrecExp.body:          Ast -> Ast                ; expression        
    astNewArrayExp.type:        Ast -> Ast
    astNewArrayExp.size:        Ast -> Ast                ; expression
    astNewArrayExp.init:        Ast -> Ast                ; expression
    astNewRecordExp.name:       Ast -> Qsymbol
    astNewRecordExp.fields:     Ast -> List(Ast)          ; list of FieldExp(*)
    astCaseExp.dispatchExp:     Ast -> Ast
    astCaseExp.fieldNames:      Ast -> List(Qsymbol)
    astCaseExp.varNames:        Ast -> List(Qsymbol)
    astCaseExp.bodyExps:        Ast -> List(Ast)          ; list of expression
    astCaseExp.defaultExp:      Ast -> Ast                ; expression
    astIfExp.testExp:           Ast -> Ast
    astIfExp.thenExp:           Ast -> Ast
    astIfExp.elseExp:           Ast -> Ast
    astBeginExp.bodyExps:       Ast -> List(Ast)          ; list of expression
    astBinOpExp.op:             Ast -> Qoperation
    astBinOpExp.lhs:            Ast -> Ast
    astBinOpExp.rhs:            Ast -> Ast
    astUnOpExp.op:              Ast -> Qoperation
    astUnOpExp.lhs:             Ast -> Ast
    astLiteralExp.literal:      Ast -> Ast
    astVarExp.name:             Ast -> Qsymbol
    astCallExp.proc:            Ast -> Ast
    astCallExp.args:            Ast -> List(Ast)
    astFieldExp.exp:            Ast -> Ast
    astFieldExp.name:           Ast -> Qsymbol
    astArrayExp.lhs:            Ast -> Ast
    astArrayExp.rhs:            Ast -> Ast

    astCharLit.value:           Ast -> char
    astStringLit.value:         Ast -> string
    astIntLit.value:            Ast -> int
    astFloatLit.value:          Ast -> float

  Output:

    astWrite:                   Ast ->

  Mutable state:

    astN1:                      Ast -> int
    astN2:                      Ast -> int
    astN3:                      Ast -> int

    astUpdate1:                 Ast x int ->
    astUpdate2:                 Ast x int ->
    astUpdate3:                 Ast x int ->

    astInits:                   Ast -> List(int)
    astUpdateInits:             Ast x List(int) ->

    astFree:                    Ast -> List(Qsymbol)                          !
    astUpdateFree:              Ast x List(Qsymbol) ->                        !

Specification:

  If c is one of the basic constructors listed above, and k is the
  Qkind that corresponds to c, then

    (astPos (c p ...)) = p
    (astKind (c p ...)) = k

    (astTypeid.name (makeTypeId p q))  =  q
    (astArraytype.elementType (makeArrayType p t))  =  t
    (astFuntype.argumentTypes (makeFunType p argtypes rtntype))  =  argtypes
    (astFuntype.returnType (makeFunType p argtypes rtntype))  =  rtntype
    (astSumType.fieldNames (makeSumType p qs ts))  =  qs
    (astSumType.fieldTypes (makeSumType p qs ts))  =  ts
    (astProductType.fieldNames (makeProductType p qs ts))  =  qs
    (astProductType.fieldTypes (makeProductType p qs ts))  =  ts

    (astModDec.names (makeModDec p qs ds es))  =  qs
    (astModDec.decs (makeModDec p qs ds es))  =  ds
    (astModDec.exps (makeModDec p qs ds es))  =  es
    (astFunDec.names (makeFunDec p qs es))  =  qs
    (astFunDec.exps (makeFunDec p qs es))  =  es
    (astVarDec.names (makeVarDec p qs es))  =  qs
    (astVarDec.exps (makeVarDec p qs es))  =  es
    (astTypDec.names (makeTypDec p qs ts))  =  qs
    (astTypDec.types (makeTypDec p qs ts))  =  ts
    (astFormalDec.name (makeFieldDec p q t))  =  q
    (astFormalDec.type (makeFieldDec p q t))  =  t
    (astBindingDec.name (makeFieldDec p q e))  =  q
    (astBindingDec.type (makeFieldDec p q e))  =  e

    (astLambdaExp.varNames (makeLambdaExp p qs ts t e))  =  qs
    (astLambdaExp.varTypes (makeLambdaExp p qs ts t e))  =  ts
    (astLambdaExp.returnType (makeLambdaExp p qs ts t e))  =  t
    (astLambdaExp.body (makeLambdaExp p qs ts t e))  =  e

et cetera.

In the list of FieldExp that is passed to makeNewRecordExp and is             !
returned by astNewRecordExp.fields, each FieldExp e.i represents              !
i : e in the source syntax.  Please note the reversal.                        !

The astWrite operation writes a description of its argument 
to the current output port.

The Ast ADT is mostly functional, but every object of type
Ast also contains a mutable state that includes three
components n1, n2, and n3 of type int.  The current values
of these components are fetched by the astN1, astN2, and
astN3 operations, and their values can be updated by the
astUpdate1, astUpdate2, and astUpdate3 operations.

The mutable state of an object of type Ast also includes
a component of type List(int), which may be the empty list.
The current value of this state component is fetched by the
astInits operation, and its value is updated by the astUpdateInits
operation.

The mutable state of an object of type Ast also includes
a component of type List(Qsymbol), which represents a set
of Qsymbol.  The current value of this state component is
fetched by the astFree operation, and its value is updated
by the astUpdateFree operation.