Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Representing Type Lattices Compactly

bernsteinbear.com

Post reply on HN
Print view View original

21–29 of 29 posts

Re: Representing Type Lattices Compactly

#24

Post by cobertos »

pjs_ wrote: post #10

Come on man just do duck typing. You are killing me with this stuff. It all reads so technical and long and mathematically academic but it’s just a bit mask. I absolutely hate writing python now because I have to reason about a “list of list of errors” type defined by a teenager and they get mad at me if I don’t then define a new “list of list of errors, or none” type when I manipulate it. You guys are now employed b…

Duck typing requires the primitives of the properties to also be typed. This is a building block you must built to build up to duck typing.

I'm also unsure how you would represent a "list of list of errors" succintly without calling it just that. A list of a list of errors. An `Error[][]`. How would "duck typing" as you describe make this type somehow less complex?

Re: Representing Type Lattices Compactly

#25

Post by cobertos »

You mention integer ranges as a specific type you hope gets handled. But how does something like that work? It feels somewhere between the general type and the specialization type? Would this just be a higher level in the integer section of the specialization lattice? Or would you want it out of the lattice structure completely? Because it would kinda conflict with integer unions, when thinking about it lattice-y

(Admittedly I'm in the same boat, I don't know the math but stumbled upon implementing my own type system recently)

Re: Representing Type Lattices Compactly

#26

Post by sparkie »

cobertos wrote: post #25

You mention integer ranges as a specific type you hope gets handled. But how does something like that work? It feels somewhere between the general type and the specialization type? Would this just be a higher level in the integer section of the specialization lattice? Or would you want it out of the lattice structure completely? Because it would kinda conflict with integer unions, when thinking about it lattice-y (Ad…

Every _BitInt(N) is a subtype of _BitInt(N+1). For practical purposes though, you'd usually make each intN a subtype of intN*2, up to some top integer type which supports arbitrary precision.

    int8
For this mini subtype hierarchy, you can literally just number the types in increasing order, and use `For inclusion of unsigned integers, the same rule applies, but each `unsigned _BitInt(N)` is also a subtype of `signed _BitInt(N+1)`. It might make sense to number the unsigned integers one higher than their signed variants of the same width to simplify testing for compatibility. A specific bit, such as 1000b could indicate a signed integer.

    UNSIGNED    = 0000b;
    SIGNED      = 1000b;

    enum IntType {
        UINT8   = UNSIGNED | 1,
        UINT16  = UNSIGNED | 2,
        UINT32  = UNSIGNED | 3,
        UINT64  = UNSIGNED | 4,
        UBIGINT = UNSIGNED | 7,

        INT8    = SIGNED | 0,
        INT16   = SIGNED | 1,
        INT32   = SIGNED | 2,
        INT64   = SIGNED | 3,
        BIGINT  = SIGNED | 7,
    };

    is_uint8_subtype(ty)    = (ty | UNSIGNED)
This is approximately how I handle it the numerical tower in my interpreter (extended with some ad-hoc rules to also support rationals, real, complex and quaternions).

Re: Representing Type Lattices Compactly

#27

Post by tekknolagi »

cobertos wrote: post #25

You mention integer ranges as a specific type you hope gets handled. But how does something like that work? It feels somewhere between the general type and the specialization type? Would this just be a higher level in the integer section of the specialization lattice? Or would you want it out of the lattice structure completely? Because it would kinda conflict with integer unions, when thinking about it lattice-y (Ad…

Probably a different thing entirely than the specialization. A new lattice. A pair of uint64 for int ranges that has its own join function, maybe. CF Bolz-Tereick has a good blog post about this for pypy and it also talks about known bits

Re: Representing Type Lattices Compactly

#28

Post by cobertos »

sparkie wrote: post #26
cobertos wrote: post #25

You mention integer ranges as a specific type you hope gets handled. But how does something like that work? It feels somewhere between the general type and the specialization type? Would this just be a higher level in the integer section of the specialization lattice? Or would you want it out of the lattice structure completely? Because it would kinda conflict with integer unions, when thinking about it lattice-y (Ad…

Every _BitInt(N) is a subtype of _BitInt(N+1). For practical purposes though, you'd usually make each intN a subtype of intN*2, up to some top integer type which supports arbitrary precision. int8 For this mini subtype hierarchy, you can literally just number the types in increasing order, and use ` For inclusion of unsigned integers, the same rule applies, but each `unsigned _BitInt(N)` is also a subtype of `signed…

Interesting, I wasn't thinking of sized integers when thinking of int ranges (moreso of Python ranges like `3..7` for integers `3 | 4 | 5 | 6 | 7`) but this is fascinating as well. The interplay between different types of ranges feels like it might be complex to model.

I wonder if a type system exists that can modify the type lattice at run-time or just before run-time, so user-defined types can be added to a system even if the program is already built. As the types usually require explicit language support but I can always foresee more explicit un-typable things that might be useful just not useful enough to put in a general type system

Re: Representing Type Lattices Compactly

#29

Post by cobertos »

tekknolagi wrote: post #27
cobertos wrote: post #25

You mention integer ranges as a specific type you hope gets handled. But how does something like that work? It feels somewhere between the general type and the specialization type? Would this just be a higher level in the integer section of the specialization lattice? Or would you want it out of the lattice structure completely? Because it would kinda conflict with integer unions, when thinking about it lattice-y (Ad…

Probably a different thing entirely than the specialization. A new lattice. A pair of uint64 for int ranges that has its own join function, maybe. CF Bolz-Tereick has a good blog post about this for pypy and it also talks about known bits

Ah! So like lower and upper bound that join separately to include the total min and total max between the two ranges types. I see
Post reply on HN