[ANN] Chuck type inferencer
stéphane ducasse
ducasse at iam.unibe.ch
Thu May 27 08:06:29 UTC 2004
Hi lex
Excellent!
Thanks for your work.
You got an ecoop paper this is great, Are you coming?
Stef
On 26 mai 04, at 19:55, Lex Spoon wrote:
> The Chuck type inferencer is now available on SqueakMap. This is a
> tool
> I've been working on for a few years that can answer questions about
> the
> types of variables and expressions by searching through your program
> code. For example, you can ask for the type of a variable x, and it
> will go find every expression that writes into x (e.g., x := y), and
> find the types of the right-hand-sides, and so on recursively. It's
> similar to what people do by hand anyway to find types, but Chuck
> automates it.
>
> Additionally, this kind of tool should be useful as a building block
> for
> other tools. First, Chuck should be a useful as part of the backend
> for
> for programming tools such as compilers and dead code removers.
> Second, the "AutoChuck" part of it maintains a handy model of all the
> system's source code along with various lookup tables like "who writes
> into this variable"; this part alone should be useful to people who
> want
> to do any sort of investigations about the source code of the system.
>
> If you want to play with the inferencer, you need to grab Squeak 3.7 (I
> am at update 5707), install the Refactoring Browser, and then install
> the Chuck package from SqueakMap. From there, you can run and read
> some
> test cases. For serious day to day use, you then need to turn on
> AutoChuck, which is a preference in the "browsing" area of the
> preferences browser. This will spend 10-60 minutes filling up your
> image with 75 megabytes or so of lookup tables; after that, it should
> be
> invisible to your normal activities, and the refactoring browser will
> have two new menu items available:
>
> 1. "infer type", in code panes. Select any expression and you can run
> this, and it will dig up a type for you.
>
> 2. "specific senders of", in message-list panes. It acts like
> senders-of but uses type inference on the message-senders in order to
> reject some of the message senders as impossible.
>
> More serious users may want to tweak the "preferences" class methods of
> ChuckInferencer; you can tweak how many goals the inferencer will use
> and how much wall-clock time it will spend before bailing out. (I
> intend to extend the ChuckConfigurator dialog to let users set these
> things in a GUI, but that hasn't happened yet.)
>
> The project home page is:
>
> http://www.cc.gatech.edu/~lex/chuck/
>
> This page includes a good description of the algorithm, although more
> description -- about 100-150 pages more -- is on the way by next May.
>
>
> A quick word on what this type inferencer is giving you. The types it
> infers are guaranteed bounds on what the variables or expressions will
> evaluate to at runtime. They do not represent what the programmer
> intended to be possible for the variable, and they are not necessarily
> a
> good summary of what the variable is.
>
> An example should help. If you infer a type of PlayingCardDeck's
> stackingPolicy variable, Chuck will tell you that it will hold one of
> these things: nil, #stagger, #straight, #altStraight, or #single. The
> comment of the variable tells a slightly different story! First, the
> comment gives #none as an option while the type inference does not; the
> reason is that nothing in the image uses #none, even though the code
> can
> handle it. Second, the comment does *not* mention #stagger as an
> option. #stagger does indeed get assigned to the variable, so the code
> and the comment are out of sync here. The first item is more
> interesting I think: for this tool to be effective, you want to have
> uses of the code loaded in addition to the code you are studying.
>
>
> Finally, some people may be curious about the general approach of this
> thing. There is some documentation on the web site, and some more
> serious documentation being developed, but let me give a quick summary
> because Chuck is a little unusual. Essentially, Chuck posts goals to
> itself and then tries to solve them. In the course of solving a goal,
> it is allowed to post more goals. Each goal is initially given a very
> optimistic tentative solution (e.g., this variable is never assiged any
> value), and then the algorithm repeatedly updates the tentative
> solutions, making them less precise, until it has found an entire set
> of
> solutions that are consistent with each other. At that point the
> tentative solutions can be treated as full solutions.
>
> This is different from other algorithms I know of, which do one of two
> things: they simulate the program in the abstract, using types instead
> of values, or, they generate a huge pile of constraints ("type of x is
> greater than type of y"...), and solve them all. What Chuck's approach
> allows it to do, however, is to *prune* its subproblems. That is,
> Chuck
> can at any time answer a goal with a trivial but poor answer; the
> subgoals of such a goal then become unnecessary and can be abandoned.
> If Chuck is trying to find the type of "node isNil", and it is unable
> to
> infer the type of "node", it has the option of substituting "Anything"
> for the type of node and then proceding onwards (in this case, still
> finding the optimal solution of {True False}). In short, Chuck's
> architecture lets its performance degrade gracefully as programs get
> large. The existing algorithms seem to get into trouble with around
> 30-50 kloc programs, whereas Squeak has about 300 klocs.
>
> All right, have at it. Comments welcome!
>
> -Lex
>
More information about the Squeak-dev
mailing list
|