Re: [xacml] Bags of structured type

[Polar Humenn <polar@syr.edu>]

On Fri, 5 Mar 2004, Seth Proctor wrote:

> [snip]
>
> > Unfortunately our Bag function(s) are defined for only primitive types.
> > So, when you introduce a new data type, you must introduce all functions
> > that deal with it, such as any "*-set"  operations, or any other
> > "primitive" functions dealing with the types.
>
> I don't see how we could do better here. We can only define the type-*
> function identifiers for the known, standard types. Then you have to
> hope that the system you use provides the right functionality. In my
> code, for example, the type-* functions are specifically designed so
> it's trivial to get them to support any new datatypes you define.

However we do have "type-*" functions that really can handle the
polymorphism.

In order to describe this let me use Haskell notation. To review the type
notation. A type description of "a -> b" means a function that takes an
argument of type "a" and returns a value of type "b" (which can be a
function). For example, "integer-abs" has the following type:

integer_abs: Integer -> Integer

likewise for multi argument functions:

integer_add: Integer -> (Integer -> Integer)

We use a "*" notation for functions that take a variable amount of
arguments of the same type. (This is not Haskell notation, but well
understood). For instance,

n_of: Integer -> Boolean* -> Boolean

which is the function that first takes an integer, any number, zero or
more, of boolean values, and returns a boolean value.

So, where we can do better is with two functions, right off the bat,
bag-size, and bag. Where we currently have:

integer_bag_size: Bag Integer -> Integer
double_bag_size:  Bag Double -> Integer
string_bag_size:  Bag String -> Integer

can easily be made into a polymorphic function of:

bag_size: Bag a -> Integer

likewise whereas

integer_bag:  Integer* -> Bag Integer
double_bag:   Double* -> Bag Double
string_bag:   String* -> Bag String

we could just have:

bag: a* -> Bag a

In fact, that is exactly how we implement the "*-bag" functions, just by
calling the polymorphic "bag" function implementation.

> The alternative would be to redefine the type-* functions without the
> type qualifier, so there is only a single is-in (for example) function
> that operates over all types. This has benefits and drawbacks that we
> discussed at length before 1.0 came out (this focused around the map
> function, I think).

The thing with "type-*" functions is that you must specify the equality
predicate that is used. The definition of:

string_is_in:  String -> Set String -> Boolean

actually specifies that it must be implemented in accordance with
"string-equal".

A polymorphic "is-in" function would have to specify the equality function
to be complete:

polymorphic_is_in:  (a -> a -> Boolean) -> Set a -> Boolean

which is to say that "polymorphic_is_in" takes as its first argument, a
function that takes two arguments of the same type and returns a boolean.
The second argument to "polymorphic_is_in" is the set of that specific
type. Therefore an implementation of "string-is-in" would look like

string_is_in  x y = is_in string_equal  x y
integer_is_in x y = is_in integer_equal x y
etc.

And, again, all the "*-set* functions are implemented this way in our
implementation.

Furthermore, this can easily be done in XACML today (in our
implementation), actually, with non-standard functions, such as
polymorphic_is_in:

<Apply FunctionId="polymorphic_is_n">
    <Function FunctionId="string-equal"/>
    <AttributeValue DataType="string">Hello</AttributeValue>
    <ResourceAttributeDesignator AttributeId="some-string-attribute/>
</Apply>

Works.

Cheers,
-Polar

> seth
>