Parametric types which add or delete fields.

[Anonymous]

So I have a pretty complex problem in designing my type data structure which I haven't been able to solve.  Let's say I have an abstract car type:

abstract AbstractCar

now let's say I have the following possible features for a car:

color

horsepower

model

year

Now I want to be able to create all possible composite concrete types containing any combination of these features, so that would be 2^4=16 different composite types I need to define, and I would need to give them all names, so for example one of these 16 composite types would be

CarHorseModel <: AbstractCar

  horsepower

  model

end

Obviously this is untenable since the number of possible types grows exponentially with the number of features.  Thus a different approach that avoids this is to have one concrete type

Car <: AbstractCar

  color

  horsepower

  model

  year

end

and then to set it up so that any features which I don't want to include are set to nothing.  This avoids the problem above, but is messy and inelegant.  However the bigger problem with it is that I want to have a container type for all my cars, call this container type Garage, and I want this container type to require that all cars in my garage have the same features.  Thus in my original design with 16 separate composite types, I could simply set up my container type to be of the form

type Garage{C <: AbstractCar}

  cars::Vector{C}

end

Unfortunately for the approach where I have a single Car type with all the features included and those I don't want set to nothing, there is no straight forward way to enforce this.  The situation is further complicated because I then have various methods which I would like to dispatch on certain types of garages.  For instance one method may only work for garages which contain cars which have a color feature, maybe another method only works on garages which have both a color feature and a year feature.

What I would like is something that works like a parametric type, but instead of the parametric type changing the type of the fields, it effectively decides what field names are included in my composite type.  So for instance Car{Color, Year} would produce the type

Car{Color, Year} <: AbstractCar

  color::ASCIIString

  year::Int

end

However! A further problem, is that say I have a method which works on all garages which contain Car types which have a color feature, so that includes 2^3=8 different possible Garage types (all those which contain cars with a color feature), so this also grows exponentially with the number of features.

What does everyone think is the right way to handle this problem

[Tamas Papp]

(Note that your code is not valid in Julia as you wrote it, missing
`type` for many declarations, etc.)

You could have

type Car{C,H,M,Y}
color::C
horsepower::H
model::M
year::Y
end

and set parameters to Void when they are not needed. This would enforce
what you require, and also seems to result in a smaller allocated size
when a parameter is Void.

Best,

Tamas

[Toivo Henningsson]

As you say, it's a lot of types. If you would really need to instantiate an exponential number of types then maybe you should reconsider, because the jit compiler has to do quite a lot of work for each type that is used.

But if you're not actually going to instantiate such a humongous number of them, or if you really want to be able to use specialization and dispatch in this way: How about a middle road where you use a parametric type and set the types of all unused fields to Void (the type of nothing)? That should be able to support the cases that you mentioned.

Also, in many cases, storage for a value worth known type of eg Void is free, since it is known that there is only one instance. The exception is if the value could be uninitialized as well.

[Anonymous]

OP here,

So it looks like the consensus is to use a single type with un-used features set to nothing.  I've actually been playing around with this approach since I posted this question.  Here's what I've got:

abstract AbstractCar

abstract Color

abstract Year

typealias ColorOrVoid Union{Color, Void}

typealias YearOrVoid Union{Year, Void}

type Car{C<:ColorOrVoid, Y<:YearOrVoid} <: AbstractCar

  color::typeMap(C)

  year::typeMap(Y)

end

where the function typeMap will send Void to itself, Color to ASCIIString and Year to Int.  However I tried doing this and I got an error, I probably the way to do this is with meta-programming and macros, but I'm not sure how since I'm a complete novice at meta-programming.

I would also like to have outer constructors which allow me to avoid having to enter Void for all the un-used features, so if I'm only interested in Year, I would have an outer constructor of the form:

Car{Year}(y::Int) = Car{Void, Year}(nothing, y)

However this gives me an error saying that static parameter Year does not occur in signature for call at none.

[Mauro]

On Fri, 2016-04-15 at 07:28, Anonymous <esp...@gmail.com> wrote:
> OP here,
>
> So it looks like the consensus is to use a single type with un-used
> features set to nothing. I've actually been playing around with this
> approach since I posted this question. Here's what I've got:
>
> abstract AbstractCar
>
> abstract Color
> abstract Year
>
> typealias ColorOrVoid Union{Color, Void}
> typealias YearOrVoid Union{Year, Void}
>
> type Car{C<:ColorOrVoid, Y<:YearOrVoid} <: AbstractCar
> color::typeMap(C)
> year::typeMap(Y)
> end

This should work:

type Car{C<:ColorOrVoid, Y<:YearOrVoid} <: AbstractCar

color::C
year::Y
end

(Aside:
I think using a function inside the type definition is only possible if
it can be evaluated at compile time (I might be wrong though). Consider
this example:

julia> g(T) = Vector{T}
g (generic function with 1 method)

julia> type B{T}
b::g(T)
end

julia> B([1,2])
B{Int64}([1,2])

julia> h(T) = string(Int.name.name)[1]=="I" ? Int : Float64
h (generic function with 1 method)

julia> h(AbstractString)
Float64

julia> type C{T}
c::h(T)
end
WARNING: static parameter T does not occur in signature for call at none:2.
The method will not be callable.

end-aside)

> where the function typeMap will send Void to itself, Color to ASCIIString
> and Year to Int. However I tried doing this and I got an error, I probably
> the way to do this is with meta-programming and macros, but I'm not sure
> how since I'm a complete novice at meta-programming.
>
> I would also like to have outer constructors which allow me to avoid having
> to enter Void for all the un-used features, so if I'm only interested in
> Year, I would have an outer constructor of the form:
>
> Car{Year}(y::Int) = Car{Void, Year}(nothing, y)
>

> However this gives me an error saying that *static parameter Year does not
> occur in signature for call at none*.

Outer constructors are a bit hard to grok because type parameter feature
twice, in the same location, but have a completely different
meaning:

Car{Year}(y::Int) = Car{Void, Year}(nothing, y)

^^^^ ^^^^^^^^^^
function parameter type parameters

Function parameters need to be inferred from the arguments, whereas type
parameters are part of the type. (this might get cleared up in the future)

Consider that for just an ordinary function, you cannot do this:

f{T<:Int}(i::I) = 5
# now call it like so
f{Int}(4) # error

Anyway, the solution is just (assuming Color and Year can be
distinguished by type):

Car(y::Year) = Car{Void, Year}(nothing, y)
Car(c::Color) = Car{Color,Void}(c, nothing)
Car(c::Color, y::Year) = Car{Color,Year}(c, y)

If you want to explicate specify the type then (like is used in
Julia-Base for e.g. array constructors):

Car(T::Type{Year}, y) = Car{Void, Year}(nothing, y)
...

[Anonymous]

I need the fields color and year to be Int and ASCIIString, respectively, and I can't just make the types Color and Year type aliases of Int and ASCIIString, since I need these abstract types to distinguish different types of Car for the purposes of multiple dispatch.  

Basically let's say I have 6 possible features and I want to include features 3, 5 and 6.  And let's say those features are ASCIIString, Int and Int, respectively, then I want to be able to write:

Car{Feature3, Feature5, Feature6}(a, b, c)

where a is a string, and b and c are both integers, and then I want the constructor to return:

Car{Void, Void, Feature3, Void, Feature5, Feature6}(nothing, nothing, a, nothing, b, c) 

[Anonymous]

edit of previous post: 

I have color and year reversed, color should be ASCIIString and year should be Int, same thing with Color and Year.

[Mauro]

On Fri, 2016-04-15 at 09:56, Anonymous <esp...@gmail.com> wrote:
> I need the fields color and year to be Int and ASCIIString, respectively,
> and I can't just make the types Color and Year type aliases of Int and
> ASCIIString, since I need these abstract types to distinguish different
> types of Car for the purposes of multiple dispatch.

Maybe you need to introduce your Color and Year types. However if they
alias to different types then your good.

typealias MyYear Int
typealias MyColor ASCIIString

Car(y::MyYear) = Car{Void, Year}(nothing, y)
Car(c::MyColor) = Car{Color,Void}(c, nothing)
Car(c::MyColor, y::MyYear) = Car{Color,Year}(c, y)

(Note though that this will construct types which have abstract
field-types. Those are bad for performance (but only worry about this
in critical code), have a look at the performance section of the docs)

> Basically let's say I have 6 possible features and I want to include
> features 3, 5 and 6. And let's say those features are ASCIIString, Int and
> Int, respectively, then I want to be able to write:
>
> Car{Feature3, Feature5, Feature6}(a, b, c)

Well, outer constructors cannot work like this.

> where a is a string, and b and c are both integers, and then I want the
> constructor to return:
>
> Car{Void, Void, Feature3, Void, Feature5, Feature6}(nothing, nothing, a,
> nothing, b, c)
>
> On Friday, April 15, 2016 at 12:18:56 AM UTC-7, Mauro wrote:
>>
>>

>> On Fri, 2016-04-15 at 07:28, Anonymous <esp...@gmail.com <javascript:>>

[Tim Holy]

Hi Anonymous,

Whether all this is worth it depends on how you're going to use these objects.
Particularly if you're likely to need to work with long lists of cars of
different types, the path you're following is probably not worthwhile. The
issue is this: if you have a container where julia knows the type of each
element in advance (all objects in the container have the same *concrete*
type), then julia can emit efficient code for processing the whole list. In such
cases, this path is worthwhile. The other place where it might be worthwhile
is if you have an enormous amount of computation you're going to do on each
object, and that processing is greatly sped up by having "sub-functions" that
know the full type details. (In such cases you'll want a function barrier,
http://docs.julialang.org/en/stable/manual/performance-tips/#separate-kernel-functions.)

If in contrast item[i+1] has a different type than item[i], and the amount of
processing is quite modest, then it may not be worth it. Because julia can't
predict the type at compile-time, it has to look up the type at run-time,
search for the appropriate method in method tables, decide (via type
intersection) which one matches, determine whether it has been JIT-compiled
yet (and do so if not), and then make the call. You're asking the full type-
system and JIT-compilation machinery to basically execute the equivalent of a
switch statement or dictionary lookup in your own code. Julia can do this, but
it's a lot of churn under the hood. If this is the situation you're in, it
seems likely to be better to just write that switch statement or to use a
dictionary.

Julia emphasizes the "real" use for types---being able to make important
decisions at compile time---rather than the "window dressing" (glorified switch
statements) uses that some OOP paradigms seem to encourage.

Best,
--Tim

[Tamas Papp]

On Fri, Apr 15 2016, Tim Holy wrote:

> Julia emphasizes the "real" use for types---being able to make important
> decisions at compile time---rather than the "window dressing" (glorified switch
> statements) uses that some OOP paradigms seem to encourage.

When learning Common Lisp, many people go through a "I am gonna write
macros for EVERYTHING" phase. Perhaps the Julia equivalent is
constructing elaborate schemes using the type system. I guess this is
normal, since it is one of the most elaborate features of the language.

Having concocted my fair share of complicated and frequently pointless
computational acrobatics with the type system, now I try to forget that
types exist in Julia until I have a working prototype that I can
profile.

Best,

Tamas

[Eric Forgy]

On Friday, April 15, 2016 at 6:40:37 PM UTC+8, Tim Holy wrote:

If in contrast item[i+1] has a different type than item[i], and the amount of
processing is quite modest, then it may not be worth it. Because julia can't
predict the type at compile-time, it has to look up the type at run-time,
search for the appropriate method in method tables, decide (via type
intersection) which one matches, determine whether it has been JIT-compiled
yet (and do so if not), and then make the call. You're asking the full type-
system and JIT-compilation machinery to basically execute the equivalent of a
switch statement or dictionary lookup in your own code. Julia can do this, but
it's a lot of churn under the hood. If this is the situation you're in, it
seems likely to be better to just write that switch statement or to use a
dictionary.

Hi Tim, 

Thanks for writing this. I am finally starting to write some serious Julia code and I am in exactly the situation you described above. It is kind of depressing to read what you wrote, but it makes sense I guess. Now I need to rethink my strategy.

It's probably obvious, but could you or someone else help elaborate on "just write that switch statement or use a dictionary"?

What is the best way to deal with this situation?

Basically, I have a long list of concrete objects "PriceableType1", "PriceableType2", etc, all subtypes of "AbstractPriceableType" and I have a different "Price" function for each different concrete time that dispatches as I run through the list to come up with the price of the list.

Should I make methods "priceType1", "priceType2", etc and just switch based on "typeof" rather than use dispatch? :(

Thanks again and have a great weekend!

Eric

[Tim Holy]

Your best bet is always to benchmark. Here's how I make such decisions:

# The type-based system:
julia> immutable Container1{T}
val::T
end

julia> inc(::Int) = 1
inc (generic function with 1 method)

julia> inc(::Float64) = 2
inc (generic function with 2 methods)

julia> inc(::UInt8) = 3
inc (generic function with 3 methods)

julia> vec = [Container1(1), Container1(1.0), Container1(0x01)]
3-element Array{Container1{T},1}:
Container1{Int64}(1)
Container1{Float64}(1.0)
Container1{UInt8}(0x01)

julia> function loop_inc1(vec, n)
s = 0
for k = 1:n
for item in vec
s += inc(item.val)
end
end
s
end
loop_inc1 (generic function with 1 method)

# The dictionary solution
julia> immutable Container2
code::Symbol
end

julia> vec2 = [Container2(:Int), Container2(:Float64), Container2(:UInt8)]
3-element Array{Container2,1}:
Container2(:Int)
Container2(:Float64)
Container2(:UInt8)

julia> dct = Dict(:Int=>1, :Float64=>2, :UInt8=>3)
Dict(:Int=>1,:UInt8=>3,:Float64=>2)

julia> function loop_inc2(vec, dct, n)
s = 0
for k = 1:n
for item in vec
s += dct[item.code]
end
end
s
end
loop_inc2 (generic function with 1 method)

# The switch solution
julia> function loop_inc3(vec, n)
s = 0
for k = 1:n
for item in vec
if item.code == :Int
s += 1
elseif item.code == :Float64
s += 2
elseif item.code == :UInt8
s += 3
else
error("Unrecognized code")
end
end
end
s
end

loop_inc3 (generic function with 1 method)

julia> loop_inc1(vec, 1)
6

julia> loop_inc2(vec2, dct, 1)
6

julia> loop_inc3(vec2, 1)
6

julia> @time loop_inc1(vec, 10^4)
0.002274 seconds (10.17 k allocations: 167.025 KB)
60000

julia> @time loop_inc1(vec, 10^5)
0.025834 seconds (100.01 k allocations: 1.526 MB)
600000

julia> @time loop_inc2(vec2, dct, 10^5)
0.010278 seconds (6 allocations: 192 bytes)
600000

julia> @time loop_inc3(vec2, 10^5)
0.001561 seconds (6 allocations: 192 bytes)
600000


So in terms of run time, the bottom line is:
- The "switch" version is fastest (by quite a lot), but ugly.
- The dictionary is intermediate. You would likely be able to do even better
with a "perfect hash" dictionary, see
http://stackoverflow.com/questions/36385653/return-const-dictionary
- The type-based solution is slowest, but not much worse than the dictionary.

Note that none of this analysis includes compilation time. If you're writing a
large system, the type-based one in particular will require longer JIT times,
whereas the first two get by with only a single type and hence will need much
less compilation.

Of course, if `inc` were a complicated function, it might change the entire
calculus here. That's really the key: what's the tradeoff between the amount of
computation per element and the price you pay for dispatch to a type-
specialized method? There is no universal answer to this question.

Best,
--Tim

[Eric Forgy]

Thank you Tim! That is some excellent wisdom. I appreciate that and shared it with my team.

[Greg Plowman]

Notwithstanding the explosion of possible types and the excellent advice and insight provided by Tim, you can get the following to compile and run.

typealias Color ASCIIString
typealias Horsepower Float64
typealias Model ASCIIString
typealias Year Int

type Car{
        C<:Union{Color,Void},
        H<:Union{Horsepower,Void},
        M<:Union{Model,Void},
        Y<:Union{Year,Void}

    }
    color::C
    horsepower::H
    model::M
    year::Y
end

# outer constructor
function Car(; color=nothing, horsepower=nothing, model=nothing, year=nothing)
    Car(color, horsepower, model, year)
end

# create cars by use keyword arguments in any order
myoldcar = Car(year=1967, horsepower=450.0, color="Red")
mynewcar = Car(year=2016, color="White")

# function operates on any homogeneous garage of cars with color and year defined
function Count_Red_1963{C<:Color,H,M,Y<:Year}(garage::Vector{Car{C,H,M,Y}})
    count = 0
    for car in garage
        if car.color == "Red" && car.year == 1963
            count += 1
        end
    end
    return count
end

garage_color_model_year = [ Car(color="Red", model="GTX", year=1963) for i = 1:10 ]
# TODO: work out how to avoid messy conversion
garage_color_model_year = convert(Vector{typeof(garage_color_model_year[1])}, garage_color_model_year)

garage_color_year = [ Car(color="Red", year=y) for y = 1960:1969 ]
garage_color_year = convert(Vector{typeof(garage_color_year[1])}, garage_color_year)

Count_Red_1963(garage_color_model_year)
Count_Red_1963(garage_color_year)

[fblscode]

Are you sure you desperately need to dispatch methods on the features? The fact that it's possible doesn't mean it's a good idea ;)
These days, when I run into types where a lot of fields are nil some of the time; It's almost always better posed as a relational problem. What if the features were tables/dicts, and membership indicated a specific record/object has the feature and any extra feature info? It's difficult to say from the information available, I'm not sure what problem you're really trying to solve.

Peace