Re: Reconstructing the Types of Stack-Machine Codes

Oukseh Lee <cookcu@ruby.kaist.ac.kr> writes:
> Whoever knows about TYPE ANALYSIS of STACK-MACHINE CODES?


The paper I have to hand (by a strange coincidence) is


        Type-checking in an untyped language
        Allan Ramsay
        Int. J. Man-Machine Studies (1984) 20, 157-167


He describes a technique for taking the virtual machine code for Pop11
(which you may regard for these purposes as a Lisp with an
Algol-family syntax and a Postscript/Forth-style open stack) and doing
type inference to spot places where the code is either type-incorrect
or additional run-time type-checks should be inserted.


Ramsay's motivation is checking the validity of code, rather than
run-time efficiency, but there are obvious cross-overs.


My very rough summary is that the virtual machine operations are
tracked, doing stack simulation while you can and using the results of
previous analyses when simulating function calls [there is hackery to
cope with recursions and calling not-yet-analysed
functions]. Conditionals and loops are handled by generating sets of
linear execution paths and recombining the results from those paths
(doing a type merge).


It makes interesting reading. I remember thinking at the time that it
was a compelling demonstration that this kind of analysis is better
done on ASTs than on linearised code -- but then you have to go with
what you've got, yes?


Notettes: Pop11 is dynamically typed, not "untyped" (a term better
used for languages like BCPL). I'm a long-time Pop11 fan, which, given
my description of Pop above, you may use to calibrate my sanity. And I
know the reference to the paper is right, because I have a paper copy
here in my hot sticky hands.
--


Regards, | ``"I can't suit myself," said Weinbaum, a little petulantly.
Kers. | "I work for the Government".'' - Blish, "The Quincunx of Time".

Return to the comp.compilers page.
Search the comp.compilers archives again.