Constrained genericity
Constrained genericity means that a parametrized type or function (see Parametric Polymorphism) can only be instantiated on types fulfilling some conditions, even if those conditions are not used in that function.
You are encouraged to solve this task according to the task description, using any language you may know.
Say a type is called "eatable" if you can call the function eat on it. Write a generic type FoodBox which contains a collection of objects of a type given as parameter, but can only be instantiated on eatable types. The FoodBox shall not use the function eat in any way (i.e. without the explicit restriction, it could be instantiated on any type). The specification of a type being eatable should be as generic as possible in your language (i.e. the restrictions on the implementation of eatable types should be as minimal as possible). Also explain the restrictions, if any, on the implementation of eatable types, and show at least one example of an eatable type.
This language feature only applies to statically-typed languages.
Ada
Ada allows various constraints to be specified in parameters of a generics. A formal type constrained to be derived from certain base is one of them: <lang ada>with Ada.Containers.Indefinite_Vectors;
package Nutrition is
type Food is interface; procedure Eat (Object : in out Food) is abstract;
package Food_Boxes is
new Ada.Containers.Indefinite_Vectors
( Index_Type => Positive,
Element_Type => Food'Class
);
subtype Food_Box is Food_Boxes.Vector;
end Nutrition;</lang> The package Nutrition defines an interface of an eatable object, that is, the procedure Eat. Then a container package is instantiated with the elements to be of the class Food. I.e. the elements can be only the members of the class Food. Example of use: <lang ada>type Banana is new Food with null record; overriding procedure Eat (Object : in out Banana) is null;
type Tomato is new Food with null record; overriding procedure Eat (Object : in out Tomato) is null;</lang> We have declared Banana and Tomato as a Food. <lang ada> Lunch_Box : Food_Box; begin
Lunch_Box.Append (Banana'(null record)); Lunch_Box.Append (Banana'(null record)); Lunch_Box.Append (Tomato'(null record));</lang>
The lunch box contains two banana and one tomato.
C#
In C#, type constraints are made on the type hierarchy, so here we make IEatable an interface, with an Eat method. Types which are eatable would have to implement the IEatable interface and provide an Eat method.
<lang csharp>interface IEatable {
void Eat();
}</lang>
Type constraints in type parameters can be made via the where keyword, which allows us to qualify T. In this case, we indicate that the type argument must be a type that is a subtype of IEatable.
<lang csharp>using System.Collections.Generic;
class FoodBox<T> where T : IEatable {
List<T> food;
}</lang>
For example, an eatable Apple:
<lang csharp>class Apple : IEatable {
public void Eat()
{
System.Console.WriteLine("Apple has been eaten");
}
}</lang>
C# also has the interesting functionality of being able to require that a generic type have a default constructor. This means that the generic type can actually instantiate the objects without ever knowing the concrete type. To do so, we constrain the where clause with an additional term "new()". This must come after any other constraints. In this example, any type with a default constructor that implements IEatable is allowed.
<lang csharp>using System.Collections.Generic
class FoodMakingBox<T> where T : IEatable, new() {
List<T> food;
void Make(int numberOfFood)
{
this.food = new List<T>();
for (int i = 0; i < numberOfFood; i++)
{
this.food.Add(new T());
}
}
}</lang>
C++
The current C++ standard doesn't support constrained genericity (however you can emulate it by having the container refer to the corresponding eat function without actually calling it). The next version will, however, allow it through concepts: <lang cpp>#include <concepts>
- include <vector>
auto concept Eatable<typename T> // auto makes it apply automatically {
void eat(T);
};
template<std::Moveable T>
requires Eatable<T>
class FoodBox { public:
std::vector<T> food;
};</lang> The only requirement to implement an Eatable type is, indeed, that a suitable function eat is defined for it (to put it in the FoodBox, in addition it has to be Moveable, since std::vector requires that; but that's ortogonal to the type being Eatable). A possible implementation of an eatable type could be: <lang cpp>class Banana {}; void eat(Banana const &) {}</lang> Even a built-in type can be made eatable by defining a suitable eat function. The following makes double an eatable type: <lang cpp>void eat(double) {}</lang>
Another way to make an existing type eatable is to use a concept map. Let's assume we have an abstract base class Food which looks like this; <lang cpp>class Food { public:
virtual void munch() = 0;
virtual ~Food() {}
};</lang> Then we can make all classes derived from Food eatable using Food::munch() for eat with the following concept map template: <lang cpp>template<std::DerivedFrom<Food> T>
concept_map Eatable<T>
{
void eat(T const& t) { t->munch(); }
}</lang> The difference to a global function void eat(Food const&) is that the function in the concept map is only visible to functions using that concept, thus reducing namespace polution. Functions directly operating on Food objects can use the interface provided by Food itself, e.g. apple.munch(), or explicitly invoke Eatable<Food>::eat(apple). Of course, concept maps also work with built-in types: <lang cpp>concept_map Eatable<int> {
void eat(int) {}
}</lang>
Common Lisp
The task says that this task is only for statically typed languages, and Common Lisp is dynamically typed. However, there are many places where type declarations can be provided to the compiler, and there is user access to the type system (e.g., a user can ask whether an object is of a particular type). Via the latter mechanism, one could write a class containing a collection such that the insert method checked that the object to be inserted is of an appropriate type.
In this example, we define a class food, and two subclasses, inedible-food and edible-food. We define a generic function eat, and specialize it only for edible-food. We then define a predicate eatable-p which returns true only on objects for which eat methods have been defined. Then, using deftype with a satisfies type specifier, we define a type eatable to which only objects satisfying eatable-p belong. Finally, we define a function make-food-box which takes, in addition to typical array creation arguments, a type specifier. The array is declared to have elements of the type that is the intersection of food and the provided type. make-eatable-food-box simply calls make-food-box with the type eatable.
The only shortcoming here is that the compiler isn't required to enforce the type specifications for the arrays. A custom insert function, however, could remember the specified type for the collection, and assert that inserted elements are of that type.
<lang lisp>(defclass food () ())
(defclass inedible-food (food) ())
(defclass edible-food (food) ())
(defgeneric eat (foodstuff)
(:documentation "Eat the foodstuff."))
(defmethod eat ((foodstuff edible-food))
"A specialized method for eating edible-food." (format nil "Eating ~w." foodstuff))
(defun eatable-p (thing)
"Returns true if there are eat methods defined for thing." (not (endp (compute-applicable-methods #'eat (list thing)))))
(deftype eatable ()
"Eatable objects are those satisfying eatable-p." '(satisfies eatable-p))
(defun make-food-box (extra-type &rest array-args)
"Returns an array whose element-type is (and extra-type food).
array-args should be suitable for MAKE-ARRAY, and any provided element-type keyword argument is ignored."
(destructuring-bind (dimensions &rest array-args) array-args
(apply 'make-array dimensions
:element-type `(and ,extra-type food)
array-args)))
(defun make-eatable-food-box (&rest array-args)
"Return an array whose elements are declared to be of type (and
eatable food)."
(apply 'make-food-box 'eatable array-args))</lang>
D
In D this can be done in two different ways.
<lang D>interface Edible { void eat(); } interface NonPoisonous {}
class FoodBox(T : Edible) {
static assert (is (T : NonPoisonous), "don't eat that!"); T[] food;
}</lang>
First one is similar to Java example. Trying to instantiate or create alias of FoodBox parametrized with type that can't be implicitly converted to Edible result in compiler error.
The second one is using static assert and is-expression. (Static asserts are checked during compilation).
Usage: <lang D>class Banana : Edible, NonPoisonous {
void eat() { Stdout("eating banana").newline; }
}
class AmanitaMuscaria : Edible {
void eat() { Stdout("eating that red thinggy").newline; }
}
class Car { }
void main() {
// is ok alias FoodBox!(Banana) BananaBox; // will fail due to static assert alias FoodBox!(AmanitaMuscaria) ShroomBox; // will fail due to class template specialization alias FoodBox!(Car) CarBox;
}</lang>
E
It is surely arguable whether this constitutes an implementation of the above task:
<lang e>/** Guard accepting only objects with an 'eat' method */ def Eatable {
to coerce(specimen, ejector) {
if (Ref.isNear(specimen) && specimen.__respondsTo("eat", 0)) {
return specimen
} else {
throw.eject(ejector, `inedible: $specimen`)
}
}
}
def makeFoodBox() {
return [].diverge(Eatable) # A guard-constrained list
}</lang>
Haskell
A type class defines a set of operations that must be implemented by a type: <lang haskell>class Eatable a where
eat :: a -> String</lang>
We just require that instances of this type class implement a function eat which takes in the type and returns a string (I arbitrarily decided).
The FoodBox type could be implemented as follows: <lang haskell>data (Eatable a) => FoodBox a = F [a]</lang> The stuff before the => specify what type classes the type variable a must belong to.
We can create an instance of Eatable at any time by providing an implementation for the function eat. Here we define a new type Banana, and make it an instance of Eatable. <lang haskell>data Banana = Foo -- the implementation doesn't really matter in this case instance Eatable Banana where
eat _ = "I'm eating a banana"</lang>
We can declare existing types to be instances in the exact same way. The following makes Double an eatable type: <lang haskell>instance Eatable Double where
eat d = "I'm eating " ++ show d</lang>
Another way to make an existing type eatable is to declare all instances of another type class instances of this one. Let's assume we have another type class Food which looks like this; <lang haskell>class Food a where
munch :: a -> String</lang>
Then we can make all instances of Food eatable using munch for eat with the following instance declaration: <lang haskell>instance (Food a) => Eatable a where
eat x = munch x</lang>
Java
In Java type constraints are made on the type hierarchy, so here we make Eatable an interface, with an eat method. Types which are Eatable would have to implement the Eatable interface and provide an eat method.
<lang java>interface Eatable {
void eat();
}</lang>
Type constraints in type parameters can be made via the extends keyword, indicating in this case that the type argument must be a type that is a subtype of Eatable.
<lang java>import java.util.List;
class FoodBox<T extends Eatable> {
public List<T> food;
}</lang>
Similarly a generic method can constrain its type parameters <lang java>public <T extends Eatable> void foo(T x) { }</lang>
OCaml
OCaml handles type constraints through modules and module types.
A module type defines a set of operations that must be implemented by a module: <lang ocaml>module type Eatable = sig
type t val eat : t -> unit
end</lang> We just require that module instances of this module type describe a type t and implement a function eat which takes in the type and returns nothing.
The FoodBox generic type could be implemented as a functor (something which takes a module as an argument and returns another module): <lang ocaml>module MakeFoodBox(A : Eatable) = struct
type elt = A.t type t = F of elt list let make_box_from_list xs = F xs
end</lang>
We can create a module that is an instance of Eatable by specifying a type providing an implementation for the function eat. Here we define a module Banana, and make it an instance of Eatable. <lang ocaml>type banana = Foo (* a dummy type *)
module Banana : Eatable with type t = banana = struct
type t = banana let eat _ = print_endline "I'm eating a banana"
end</lang>
We can also create modules that use an existing type as its t. The following module uses float as its type:
<lang ocaml>module EatFloat : Eatable with type t = float = struct
type t = float let eat f = Printf.printf "I'm eating %f\n%!" f
end</lang>
Then, to make a FoodBox out of one of these modules, we need to call the functor on the module that specifies the type parameter: <lang ocaml>module BananaBox = MakeFoodBox (Banana) module FloatBox = MakeFoodBox (EatFloat)
let my_box = BananaBox.make_box_from_list [Foo] let your_box = FloatBox.make_box_from_list [2.3; 4.5]</lang> Unfortunately, it is kind of cumbersome in that, for every type parameter we want to use for this generic type, we will have to explicitly create a module for the resulting type (i.e. BananaBox, FloatBox). And the operations on that resulting type (i.e. make_box_from_list) are tied to each specific module.