Abstract syntax of quirk20.  [Revision 0]

The abstract syntax of a quirk20 compiler 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 in general,
                          including lists of ASTs

The Qoperation and Qkind data types are represented as small
integers.  Qsymbol and Ast are abstract data types that are
defined by their operations, which are listed and specified
below.  Unless otherwise specified, each operation of an ADT
is a static method of the class that corresponds to the ADT.

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

                                * * *
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 = intern (s0)

    equals (intern (s1), intern (s2))
        = (s1.equals (s2))

    s.equals (toString (intern (s)))

                                * * *
Qoperation:

Signature:

    Qoperation.iNOP:            int
    Qoperation.iAssign:         int
    Qoperation.iOr:             int
    Qoperation.iAnd:            int
    Qoperation.iEq:             int
    Qoperation.iLt:             int
    Qoperation.iGt:             int
    Qoperation.iNe:             int
    Qoperation.iLe:             int
    Qoperation.iGe:             int
    Qoperation.iEq_bool:        int
    Qoperation.iNe_bool:        int
    Qoperation.iEq_int:         int
    Qoperation.iLt_int:         int
    Qoperation.iGt_int:         int
    Qoperation.iNe_int:         int
    Qoperation.iLe_int:         int
    Qoperation.iGe_int:         int
    Qoperation.iEq_double:      int
    Qoperation.iLt_double:      int
    Qoperation.iGt_double:      int
    Qoperation.iNe_double:      int
    Qoperation.iLe_double:      int
    Qoperation.iGe_double:      int
    Qoperation.iEq_string:      int
    Qoperation.iLt_string:      int
    Qoperation.iGt_string:      int
    Qoperation.iNe_string:      int
    Qoperation.iLe_string:      int
    Qoperation.iGe_string:      int
    Qoperation.iPlus:           int
    Qoperation.iMinus:          int
    Qoperation.iTimes:          int
    Qoperation.iDivide:         int
    Qoperation.iPlus_int:       int
    Qoperation.iMinus_int:      int
    Qoperation.iTimes_int:      int
    Qoperation.iDivide_int:     int
    Qoperation.iPlus_double:    int
    Qoperation.iMinus_double:   int
    Qoperation.iTimes_double:   int
    Qoperation.iDivide_double:  int
    Qoperation.iPlus_string:    int
    Qoperation.iNot:            int
    Qoperation.iCoerce_int2dbl: int
    Qoperation.iCoerce_dbl2int: int

    Qoperation.toString: int -> String

Specification:

These constants are distinct non-negative integers.

                                * * *
Qkind:

Signature:

    Qkind.iEmptyList:    int
    Qkind.iNonemptyList: int

    Qkind.iVoidType:     int
    Qkind.iBoolType:     int
    Qkind.iCharType:     int
    Qkind.iStringType:   int
    Qkind.iIntType:      int
    Qkind.iDoubleType:   int
    Qkind.iArrayType:    int
    Qkind.iFunType:      int
    Qkind.iTypeId:       int

    Qkind.iDefAccess:    int
    Qkind.iPubAccess:    int

    Qkind.iClassDec:     int
    Qkind.iConstDec:     int
    Qkind.iGlobalDec:    int
    Qkind.iFieldDec:     int
    Qkind.iFunDec:       int
    Qkind.iVarDec:       int
    Qkind.iFormalDec:    int

    Qkind.iSkipStm:      int
    Qkind.iExpStm:       int
    Qkind.iIfStm:        int
    Qkind.iWhileStm:     int
    Qkind.iReturnStm:    int
    Qkind.iBlockStm:     int

    Qkind.iAssignExp:    int
    Qkind.iOrExp:        int
    Qkind.iAndExp:       int
    Qkind.iBinOpExp:     int
    Qkind.iUnOpExp:      int
    Qkind.iLiteralExp:   int
    Qkind.iNewRecordExp: int
    Qkind.iNewArrayExp:  int
    Qkind.iStaticExp:    int
    Qkind.iCallExp:      int
    Qkind.iVarExp:       int
    Qkind.iFieldExp:     int
    Qkind.iArrayExp:     int

    Qkind.iNullLit:      int
    Qkind.iTrueLit:      int
    Qkind.iFalseLit:     int
    Qkind.iCharLit:      int
    Qkind.iStringLit:    int
    Qkind.iIntLit:       int
    Qkind.iFloatLit:     int

    Qkind.toString: int -> String

Specification:

These constants are distinct non-negative integers.

                                * * *
Ast:

Signature:

  Basic constructors:

    Ast.emptyList:    -> Ast
    Ast.cons:         Ast x Ast -> Ast

    Ast.voidType:     int -> Ast
    Ast.boolType:     int -> Ast
    Ast.charType:     int -> Ast
    Ast.stringType:   int -> Ast
    Ast.intType:      int -> Ast
    Ast.doubleType:   int -> Ast
    Ast.arrayType:    int x Ast -> Ast
    Ast.funType:      int x Ast x Ast -> Ast
    Ast.typeId:       int x Qsymbol -> Ast

    Ast.defAccess:    int -> Ast
    Ast.pubAccess:    int -> Ast

    Ast.classDec:     int x Qsymbol x Ast -> Ast
    Ast.constDec:     int x Ast x Qsymbol x Ast -> Ast
    Ast.globalDec:    int x Ast x Qsymbol x Ast -> Ast
    Ast.fieldDec:     int x Ast x Qsymbol -> Ast
    Ast.funDec:       int x Ast x Qsymbol x Ast x Ast -> Ast
    Ast.varDec:       int x Ast x Qsymbol x Ast -> Ast
    Ast.formalDec:    int x Ast x Qsymbol -> Ast

    Ast.skipStm:      int -> Ast
    Ast.expStm:       int x Ast -> Ast
    Ast.ifStm:        int x Ast x Ast x Ast -> Ast
    Ast.whileStm:     int x Ast x Ast -> Ast
    Ast.returnStm:    int x Ast -> Ast
    Ast.blockStm:     int x Ast x Ast -> Ast

    Ast.assignExp:    int x Ast x Ast -> Ast
    Ast.orExp:        int x Ast x Ast -> Ast
    Ast.andExp:       int x Ast x Ast -> Ast
    Ast.binOpExp:     int x int x Ast x Ast -> Ast
    Ast.unOpExp:      int x int x Ast -> Ast
    Ast.literalExp:   int x Ast -> Ast
    Ast.newRecordExp: int x Qsymbol -> Ast
    Ast.newArrayExp:  int x Ast x Ast -> Ast
    Ast.staticExp:    int x Qsymbol x Qsymbol -> Ast
    Ast.callExp:      int x Ast x Ast -> Ast
    Ast.varExp:       int x Qsymbol -> Ast
    Ast.fieldExp:     int x Ast x Qsymbol -> Ast
    Ast.arrayExp:     int x Ast x Ast -> Ast

    Ast.nullLit:      int -> Ast
    Ast.trueLit:      int -> Ast
    Ast.falseLit:     int -> Ast
    Ast.charLit:      int x char -> Ast
    Ast.stringLit:    int x String -> Ast
    Ast.intLit:       int x int -> Ast
    Ast.floatLit:     int x double -> Ast

  Selectors:

    Ast.pos:                   Ast -> int
    Ast.kind:                  Ast -> int

    Ast.isEmpty:               Ast -> boolean
    Ast.head:                  Ast -> Ast
    Ast.tail:                  Ast -> Ast

    Ast.arrayType_elementType: Ast -> Ast
    Ast.funType_returnType:    Ast -> Ast
    Ast.funType_argumentTypes: Ast -> Ast
    Ast.typeId_name:           Ast -> Qsymbol

    Ast.classDec_name:         Ast -> Qsymbol
    Ast.classDec_decs:         Ast -> Ast
    Ast.constDec_type:         Ast -> Ast
    Ast.constDec_name:         Ast -> Qsymbol
    Ast.constDec_exp:          Ast -> Ast
    Ast.globalDec_type:        Ast -> Ast
    Ast.globalDec_name:        Ast -> Qsymbol
    Ast.globalDec_exp:         Ast -> Ast
    Ast.fieldDec_type:         Ast -> Ast
    Ast.fieldDec_name:         Ast -> Qsymbol
    Ast.funDec_returnType:     Ast -> Ast
    Ast.funDec_name:           Ast -> Qsymbol
    Ast.funDec_formals:        Ast -> Ast
    Ast.funDec_body:           Ast -> Ast
    Ast.varDec_type:           Ast -> Ast
    Ast.varDec_name:           Ast -> Qsymbol
    Ast.varDec_exp:            Ast -> Ast
    Ast.formalDec_type:        Ast -> Ast
    Ast.formalDec_name:        Ast -> Qsymbol

    Ast.expStm_exp:            Ast -> Ast
    Ast.ifStm_test:            Ast -> Ast
    Ast.ifStm_then:            Ast -> Ast
    Ast.ifStm_else:            Ast -> Ast
    Ast.whileStm_test:         Ast -> Ast
    Ast.whileStm_body:         Ast -> Ast
    Ast.returnStm_exp:         Ast -> Ast
    Ast.blockStm_decs:         Ast -> Ast
    Ast.blockStm_stms:         Ast -> Ast

    Ast.assignExp_lhs:         Ast -> Ast
    Ast.assignExp_rhs:         Ast -> Ast
    Ast.orExp_lhs:             Ast -> Ast
    Ast.orExp_rhs:             Ast -> Ast
    Ast.andExp_lhs:            Ast -> Ast
    Ast.andExp_rhs:            Ast -> Ast
    Ast.binOpExp_op:           Ast -> int
    Ast.binOpExp_lhs:          Ast -> Ast
    Ast.binOpExp_rhs:          Ast -> Ast
    Ast.unOpExp_op:            Ast -> int
    Ast.unOpExp_lhs:           Ast -> Ast
    Ast.literalExp_literal:    Ast -> Ast
    Ast.newRecordExp_name:     Ast -> Qsymbol
    Ast.newArrayExp_type:      Ast -> Ast
    Ast.newArrayExp_size:      Ast -> Ast
    Ast.staticExp_class:       Ast -> Qsymbol
    Ast.staticExp_name:        Ast -> Qsymbol
    Ast.callExp_proc:          Ast -> Ast
    Ast.callExp_args:          Ast -> Ast
    Ast.varExp_name:           Ast -> Qsymbol
    Ast.fieldExp_lhs:          Ast -> Ast
    Ast.fieldExp_name:         Ast -> Qsymbol
    Ast.arrayExp_lhs:          Ast -> Ast
    Ast.arrayExp_rhs:          Ast -> Ast

    Ast.charLit_value:         Ast -> char
    Ast.stringLit_value:       Ast -> String
    Ast.intLit_value:          Ast -> int
    Ast.floatLit_value:        Ast -> double

  Output:

    Ast.write:        Ast ->

  Mutable state:

    Ast.n1:           Ast -> int
    Ast.n2:           Ast -> int
    Ast.n3:           Ast -> int

    Ast.update1:      Ast x int ->
    Ast.update2:      Ast x int ->
    Ast.update3:      Ast x int ->

    Ast.inits:        Ast         -> int[]
    Ast.updateInits:  Ast x int[] ->

    Ast.updateOp:     Ast x int ->

Specification:

    pos (voidType (i)) = i
    pos (boolType (i)) = i
    pos (charType (i)) = i
    pos (stringType (i)) = i
    pos (intType (i)) = i
    pos (doubleType (i)) = i
    pos (arrayType (i, t)) = i
    pos (funType (i, t1, t2)) = i
    pos (typeId (i, s)) = i
    pos (defAccess (i)) = i
    pos (pubAccess (i)) = i
    pos (classDec (i, s, x)) = i

et cetera.

    kind (emptyList()) = iEmptyList
    kind (cons (x, y)) = iNonemptyList
    kind (voidType (i)) = iVoidType
    kind (boolType (i)) = iBoolType
    kind (charType (i)) = iCharType
    kind (stringType (i)) = iStringType
    kind (intType (i)) = iIntType
    kind (doubleType (i)) = iDoubleType
    kind (arrayType (i, t)) = iArrayType
    kind (funType (i, t1, t2)) = iFunType
    kind (typeId (i, s)) = iTypeId
    kind (defAccess (i)) = iDefAccess
    kind (pubAccess (i)) = iPubAccess
    kind (classDec (i, s, x)) = iClassDec

et cetera.

    isEmpty (emptyList()) = true
    isEmpty (cons (x, y)) = false
    head (cons (x, y)) = x
    tail (cons (x, y)) = y

    Ast.arrayType_elementType (arrayType (i, t)) = t

    Ast.funType_returnType (funType (i, t1, t2)) = t1
    Ast.funType_argumentTypes (funType (i, t1, t2)) = t2

    Ast.typeId_name (typeId (i, s)) = s

    Ast.classDec_name (classDec (i, s, x)) = s
    Ast.classDec_decs (classDec (i, s, x)) = x

    Ast.constDec_type (constDec (i, t, s, e)) = t
    Ast.constDec_name (constDec (i, t, s, e)) = s
    Ast.constDec_exp (constDec (i, t, s, e)) = e

    Ast.globalDec_type (globalDec (i, t, s, e)) = t
    Ast.globalDec_name (globalDec (i, t, s, e)) = s
    Ast.globalDec_exp (globalDec (i, t, s, e)) = e

    Ast.fieldDec_type (fieldDec (i, t, s)) = t
    Ast.fieldDec_name (fieldDec (i, t, s)) = s

    Ast.funDec_returnType (funDec (i, t, s, x, c)) = t
    Ast.funDec_name (funDec (i, t, s, x, c)) = s
    Ast.funDec_formals (funDec (i, t, s, x, c)) = x
    Ast.funDec_body (funDec (i, t, s, x, c)) = c

et cetera.

The Ast.write operation writes a description of its argument 
to standard output.

The Ast ADT is mostly functional, but every object of type
Ast also contains a mutable state that includes three
variables n1, n2, and n3 of type int.  The current values
of these variables are fetched by the Ast.n1, Ast.n2, and
Ast.n3 operations, and their values can be updated by the
Ast.update1, Ast.update2, and Ast.update3 operations.

The mutable state of an object of type Ast also includes
a variable of type int[], which may be null.  The current
value of this state variable is fetched by the Ast.inits
operation, and its value is updated by the Ast.updateInits
operation.

If a Ast t was created by Ast.binOpExp or Ast.unOpExp,
then its binary or unary operator is the value of a mutable
state variable that can be updated by the Ast.updateOp
operation.  In some cases, the Ast.updateOp operation may
change its first argument into a completely different kind
of node.  For example,

    Ast.updateOp (t, Qoperation.iPlus_string)

might change t into the abstract syntax tree for a call to
a library procedure that concatenates two strings.