Smalltalk › Squeak › Squeak - Dev

TypeInference: File based way of thinking

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

14 messages Options

Damien Cassou-3

TypeInference: File based way of thinking

Hi,

I'm currently interested in type inference. RoelTyper works by:

- searching all messages that are sent to instance variables
- searching all affections to instance variables

I think this is the kind of things that can be done on file based
languages (dynamically typed).

But we are working with a live system with classes and their instances.
It may be interesting to look at the instances of a given class and then
get the type of the instance variable you want. If there are multiple
instances of the class, we have to merge the results.

Is it a good idea ?

Doug Way

Re: TypeInference: File based way of thinking

On Fri, 30 Jun 2006 15:05:04 +0200, "Damien Cassou"
<[hidden email]> said:
> ...
> But we are working with a live system with classes and their instances.
> It may be interesting to look at the instances of a given class and then
> get the type of the instance variable you want. If there are multiple
> instances of the class, we have to merge the results.
>
> Is it a good idea ?

Yes, it's easier to implement, at least. Vassili Bykov wrote exactly
such an instance-based inferencer (or "type collector") for Squeak, and
I included it in my Whisker browser so that it shows the types for
instance variables in the browser when it can. See the Whisker Browser
on SqueakMap, or at
http://www.mindspring.com/~dway/smalltalk/whisker.html . (Better to use
with 3.8 at the moment... I need to put out the 3.9-compatible version
soon.)

See the "Whisker-VB-Type Collector" category for the implementation of
the type collector.

- Doug

Alexandre Bergel-2

Re: TypeInference: File based way of thinking

In reply to this post by Damien Cassou-3

> I'm currently interested in type inference. RoelTyper works by:
>
> - searching all messages that are sent to instance variables
> - searching all affections to instance variables
>
> I think this is the kind of things that can be done on file based
> languages (dynamically typed).

It is not the only way to infer types with dynamically typed languages.
For instance, let's assume you have:

a := A new.
self foo: a.

Then you can infer than foo: takes a type A as argument.

I know that Lex Spoon worked on a type inference system.

> But we are working with a live system with classes and their
> instances.
> It may be interesting to look at the instances of a given class and
> then get the type of the instance variable you want. If there are
> multiple instances of the class, we have to merge the results.
>
> Is it a good idea ?

Maybe be interesting to couple this with testing...

Cheers,
Alexandre

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.cs.tcd.ie/Alexandre.Bergel
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

Damien Cassou-3

Re: TypeInference: File based way of thinking

>> Is it a good idea ?
>
> Maybe be interesting to couple this with testing...

Yes, this is the problem with type inference. There are multiple ways of
doing the thing and neither is perfect. That's why we need a good Type
merging system to merge all the guesses.

Gerardo Richarte

Re: TypeInference: File based way of thinking

In reply to this post by Damien Cassou-3

Hi Damien

> Hi,
> I'm currently interested in type inference. RoelTyper works by:

Francisco Garau worked on his Thesis on Type Inference in Squeak, and
the result was a quite complete Type Inference system working on Squeak. I spent
some time trying to find a URL for it, but I couldn't. Everything seems to point
to the now extinct swiki.net (http://typeinference.swiki.net).

I think that you should be able to find it looking for it some more time,
or at least use it as pointer to find other related work. If you finally give up
finding his work, and unsuccessfully tried to contact him, and are still interested,
let me know.

gera

Damien Cassou-3

Re: TypeInference: File based way of thinking

Gerardo Richarte wrote:
> Francisco Garau worked on his Thesis on Type Inference in Squeak, and
> the result was a quite complete Type Inference system working on Squeak. I spent
> some time trying to find a URL for it, but I couldn't. Everything seems to point
> to the now extinct swiki.net (http://typeinference.swiki.net).
>
> I think that you should be able to find it looking for it some more time,
> or at least use it as pointer to find other related work. If you finally give up
> finding his work, and unsuccessfully tried to contact him, and are still interested,
> let me know.

Thank you for this.

Marcus Denker

Re: TypeInference: File based way of thinking

In reply to this post by Gerardo Richarte

On 02.07.2006, at 16:29, Gerardo Richarte wrote:

> Hi Damien
>
>> Hi,
>> I'm currently interested in type inference. RoelTyper works by:
>
> Francisco Garau worked on his Thesis on Type Inference in Squeak, and
> the result was a quite complete Type Inference system working on
> Squeak. I spent
> some time trying to find a URL for it, but I couldn't. Everything
> seems to point
> to the now extinct swiki.net (http://typeinference.swiki.net).
>
> I think that you should be able to find it looking for it some
> more time,
> or at least use it as pointer to find other related work. If you
> finally give up
> finding his work, and unsuccessfully tried to contact him, and are
> still interested,
> let me know.

I have both the Thesis pdf and the source. If anyone is interested, I
can mail it.

Marcus

Damien Cassou-3

Re: TypeInference: File based way of thinking

> I have both the Thesis pdf and the source. If anyone is interested, I
> can mail it.

Please Markus.

Thank you

Marcus Denker

Re: TypeInference: File based way of thinking

On 02.07.2006, at 18:01, Damien Cassou wrote:

>> I have both the Thesis pdf and the source. If anyone is
>> interested, I can mail it.
>

http://www.iam.unibe.ch/~denker/temp/TiThesis-1.pdf
http://www.iam.unibe.ch/~denker/old-download/TypeInference.sar

Damien Cassou-3

Re: TypeInference: File based way of thinking

Marcus Denker wrote:

>
> On 02.07.2006, at 18:01, Damien Cassou wrote:
>
>>> I have both the Thesis pdf and the source. If anyone is interested, I
>>> can mail it.
>>
>
> http://www.iam.unibe.ch/~denker/temp/TiThesis-1.pdf
> http://www.iam.unibe.ch/~denker/old-download/TypeInference.sar
>
>

Thank you very much

Lex Spoon

Re: TypeInference: File based way of thinking

In reply to this post by Alexandre Bergel-2

Info on my type inference work is here:

http://www.lexspoon.org/ti

This includes documentation and a demo image that you can download and
play with. You can also install my inferencer from SqueakSource, but
I have not tested it with anything newer than Squeak 3.7.

The main selling point of my inferencer is that it has a serious
attempt at being sound. I worked out a formal semantics of Smalltalk,
and my analyzer generates correct results (upper bounds on the types)
so long as you stay within the assumptions of the system.

Garau's inferencer includes an unrealistic assumption that you do not
have aliases, i.e. that you never have two different variables
pointing to the same object. Wutz's SOUL-based inferencer is very
fast but is based entirely on heuristics.

I'd guess you would want to use Wutz's inferencer for browsers in
contexts where you do not *really* need the result to be correct, and
mine in curcumstances where an error in the inferencer is more costly.

To return to the initial query, Damien is discussing the initial state
of the heap. By default my inferencer assumes an initially empty
heap--or equivalently, that the code you ask about does not use things
in the initial heap. Often this is enough. For other cases, you
would have to have the system consider the initial heap in some
fashion. This is possible with my inferencer--look through the
methods of class Inferencer--but I have not worked with it much and so
it is immature.

Finally, there are limits to how far any analyzer can go. For
example, no system can allow the programmer to add and remove
arbitrary methods and classes as the program runs. All (sound) static
analyzers make some assumptions about the program and then find out
what is possible given those assumptions.

-Lex

Roel Wuyts

Re: TypeInference: File based way of thinking

I completely agree.

But note that the name is Wuyts, not Wutz :-)

On 04 Jul 2006, at 16:45, Lex Spoon wrote:

> Info on my type inference work is here:
>
> http://www.lexspoon.org/ti
>
>
> This includes documentation and a demo image that you can download and
> play with. You can also install my inferencer from SqueakSource, but
> I have not tested it with anything newer than Squeak 3.7.
>
> The main selling point of my inferencer is that it has a serious
> attempt at being sound. I worked out a formal semantics of Smalltalk,
> and my analyzer generates correct results (upper bounds on the types)
> so long as you stay within the assumptions of the system.
>
> Garau's inferencer includes an unrealistic assumption that you do not
> have aliases, i.e. that you never have two different variables
> pointing to the same object. Wutz's SOUL-based inferencer is very
> fast but is based entirely on heuristics.
>
> I'd guess you would want to use Wutz's inferencer for browsers in
> contexts where you do not *really* need the result to be correct, and
> mine in curcumstances where an error in the inferencer is more costly.
>
>
> To return to the initial query, Damien is discussing the initial state
> of the heap. By default my inferencer assumes an initially empty
> heap--or equivalently, that the code you ask about does not use things
> in the initial heap. Often this is enough. For other cases, you
> would have to have the system consider the initial heap in some
> fashion. This is possible with my inferencer--look through the
> methods of class Inferencer--but I have not worked with it much and so
> it is immature.
>
>
> Finally, there are limits to how far any analyzer can go. For
> example, no system can allow the programmer to add and remove
> arbitrary methods and classes as the program runs. All (sound) static
> analyzers make some assumptions about the program and then find out
> what is possible given those assumptions.
>
>
> -Lex
>
>
>

Damien Cassou-3

Re: TypeInference: File based way of thinking

In reply to this post by Lex Spoon

Ok, thank you for your explanations and the link. I appreciate your help.

Bye

Alexandre Bergel-2

Re: TypeInference: File based way of thinking

In reply to this post by Lex Spoon

Thanks Lex!

Alexandre

Am Jul 4, 2006 um 3:45 PM schrieb Lex Spoon:

--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.cs.tcd.ie/Alexandre.Bergel
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.