compiler design question

In my compiler, I have an emitter function that outputs assembly, affecting the stack, and a variable resolution function that manages local variables and their offset from ebp.

I'm trying to track types through intermediate computations, though, and i don't know whether to put this functionality in the emitter, in the scope resolution system, or to merge the two.

A touhou for your thoughts?

IF I WASN'T BANNED

THE USUAL WAY FOR DEALING WITH TYPES IS TO KEEP IT AT THE SYNTAX TREE LEVEL. FOR INSTANCE, THE TYPE OF THE LITERAL ``3'', IS INTEGER. THE TYPE OF THE LITERAL ``7'', IS ALSO INTEGER. THE PLUS NODE, ``+'' HAS TYPE INTEGER WHEN ITS ARGUMENTS ARE INTEGERS. OR IT HAS TYPE FLOAT WHEN ITS ARGUMENTS ARE FLOATS. IT DEPENDS ON THE LANGUAGE HOW EXACTLY YOU WANT TO HANDLE ALL OF THIS, BUT IF YOU WORK ON THE TREE LEVEL, THE INFORMATION THAT YOU WANT SHOULD BE AVAILABLE TO YOU.

THE LEAVES OF THE SYNTAX TREE ARE WHERE YOU START. GET THOSE TYPES FIRST. CONSTANTS HAVE INTRINSIC TYPES, SO THOSE ARE EASY. FOR VARIABLES, YOU SHOULD LOCATE TEH VARIABLE DECLARATION FOR THE CURRENT SCOPE. IF YOU HAVE NESTED SCOPES, YOU MAY HAVE TO REPRESENT THE SCOPE STRUCTURE WITH A STACK OF HASH TABLES OF VARIABLE DEFINITIONS, OR SOMETHING TO THAT EFFECT. JUST DO A LINEAR SEARCH FROM THE INNER MOST SCOPE TO THE OUTER MOST FOR A DEFINITION. ONCE THE VARIABLE HAS BEEN BOUND TO A DEFINITION, YOU ARE SET FOR THE NEXT PHASE.

IF YOUR LANGUAGE REQUIRES ALL VARIABLE DECLARATIONS TO HAVE A TYPE, THEN YOU CAN EXTRACT THE TYPE FOR THE VARIABLE BY GETTING IT FROM THE VARIABLE'S DEFINITION. IF YOU'RE LANGUAGE USES TYPE INFERENCE, THEN IT'S HARDER. YOU WILL HAVE TO LOOK AT ALL INSTANCES IN THE SYNTAX TREE WHERE THE VARIABLE IS REFERENCED, AND SEE HOW IT IS USED. EACH TIME IT IS USED, THERE WILL BE CONSTRAINTS PLACED ON WHAT ITS TYPE MUST BE. THE TYPE OF THE VARIABLE CAN BE CONSTRUCTED BY UNIFYING THESE CONSTRAINTS.

IF YOU ARE CREATING A DYNAMIC LANGUAGE, YOU DON'T REALLY NEED TO CARE TOO MUCH ABOUT ANY OF THIS. ONCE THE RUN TIME SYSTEM IS COMPLETE, YOU DON'T REALLY CARE WHAT TYPES THINGS ARE AT COMPILE TIME.

THE ONLY WAY I COULD SEE A TYPED STACK BEING USEFUL IS IF YOU WERE CREATING A STATICALLY TYPED STACK BASED LANGUAGE. THIS WOULD BE HARD TO DO, BECAUSE IN MOST STACK BASED LANGUAGES, FUNCTIONS CAN CONSUME A PRODUCES DIFFERENT AMOUNTS OF VALUES BASED UPON THEIR INVOCATION. AND THIS IS IMPOSSIBLE TO KEEP TRACK OF SINCE EVEN TRYING TO CONSTRUCT A PARSE TREE WILL REDUCE TO THE HALTING PROBLEM. IT'S STILL AN INTERESTING THOUGHT THOUGH. IF EVER OPERATOR CONSUMES AND PRODUCES A KNOWN CONSTANT AMOUNT OF VALUES, THEN THE STACK BASED REPRESENTATION IS ACTUALLY EQUIVALENT TO A SYNTAX TREE. BUT THE SYNTAX TREE WILL PROBABLY GIVE YOU BETTER ACCESS TO THE VALUES YOU NEED. GOOD LUCK AND SORRY FOR NOT RESPONDING EARLIER, BUT I WAS BANNED FOR A WEEK. SINCERELY, >>15-SAN. I HAD A LOT TO SAY BECAUSE I HAD A WEEK TO THINK ABOUT IT.

AND ONCE THE TYPE INFORMATION IS ENTERED INTO THE SYNTAX TREE, YOU CAN THEN CREATE TEMPORARY NAMES FOR ALL SUBEXPRESSIONS. THEN EMIT THE CODE FOR THE EVALUATION OF THE TEMPORARY VALUES IN A POST ORDER TREE WALK. THIS WAY, YOU CAN LEVEL OUT THE TREE TO GET A REPRESENTATION MORE SUITABLE FOR AN ASSEMBLY LANGUAGE.

A = (X + (Y * 34)) + 45

WILL BECOME

A = ([T1]: X + ([T2]: Y * 34)) + 45

T2 = Y * 34
T1 = X + T2
A = T1 + 45

AND THIS COMBINED WITH TYPE INFORMATION ABOUT THE INTERMEDIATE VALUES IS ENOUGH INFORMATION TO PRODUCE THE NEEDED ASSEMBLY OUTPUT. AT THIS POINT, ALL THAT REMAINS IS HOW TO ALLOCATE THESE VARIABLES.

>>49

ALSO YOU COULD ELIMINATE COMMON SUB EXPRESSIONS BY KEEPING THE TEMPORARY VALUES INDEXED IN A TABLE BY THEIR EXPRESSION VALUE. IN ORDER TO EMPLOY THIS SUCCESSFULLY, YOU WILL NEED TO BE ABLE TO KEEP TRACK OF EXPRESSIONS THAT HAVE AND DON'T HAVE SIDE EFFECTS. EXPRESSIONS THAT HAVE NO SIDE EFFECTS CAN SAFELY HAVE THEIR RESULTS COMBINED TO A SINGLE VARIABLE AND ONLY BE EVALUATED ONCE, BUT DOING THIS FOR AN EXPRESSION THAT HAS SIDE EFFECTS WILL CHANGE THE MEANING OF THE PROGRAM, AND MUST BE AVOIDED. AN EXPRESSION WILL HAVE SIDE EFFECTS IF AT LEAST ONE OF THE FOLLOWING ARE SATISFIED

THE EXPRESSION IS A PRIMITIVE OPERATOR THAT YIELDS A SIDE EFFECT, LIKE ++.
THE EXPRESSION IS A CALL TO A FUNCTION THAT IS NOT PURE.
THE EXPRESSION CONTAINS A SUBEXPRESSION THAT HAS SIDE EFFECTS.

A FUNCTION IS NOT PURE IF IT SATISFIES AT LEAST ONE OF THE FOLLOWING

IT PERFORMS AN IO OPERATION OR EQUIVALENT
IT MODIFIES A NON LOCAL VARIABLE

NOTE THAT IT IS POSSIBLE FOR A PURE FUNCTION TO CALL A NON PURE FUNCTION IF THE ONLY VARIABLES MODIFIED ARE LOCAL TO THE PURE FUNCTION.

THE PURITY/NONPURITY OF THE FUNCTIONS CAN BE CONSTRUCTED FROM THE BOTTOM UP. LOOPS CREATED WITH RECURSION IS WEIRD THOUGH.