\section{Illustration}\label{sec:xamples}

This section illustrates our generic model of component lookup through a small set of existing lookup schemes. More examples can be found in a longer version of this paper~\cite{techrep} (e.g. examples based on nominal and structural subtyping or on reuse frequency~\cite{BayPauls05}).

\subsection{Unique Identifiers}

As a first simple example, we consider the selection mechanism based on a unique component identifier.
In that case the matching module can be described by the following triplet:
\[
\begin{array}{lcll}
\matchmodfor{\mathfrak{UId}}&::=&(\mathbb{N}, \mathbb{N}, \match_\mathfrak{UId})&\\
&&where~\matchrelfor{\mathfrak{UId}}: &\mathbb{N} \times \mathbb{N} \mapsto \{~0,~1~\}\\
&&\matchrelfor{\mathfrak{UId}}(x, y)~=~&1~ if x=y\\
&&&0~otherwise\\
\end{array}
\]
As a first example of use, we can imagine a collection of software components that have unique identifiers:
\[
\compset=\{(\{1_{\mathfrak{UId}}\},C_1),...,(\{1337_{\mathfrak{UId}}\},C_{1337}),...,(\{n_{\mathfrak{UId}}\},C_n) \}
\]
Looking up component identified by number 1337 can be made as follows:
%\begin{lstlisting}
%template: LL_UID_TEMPLATE_TERM
%component: LL_COMPONENT
%components: LL_COMPONENT_COLLECTION
%...
%create template.make ("1337")
%component:= (components^template).get_first_component
%... 
%\end{lstlisting}
\[
\lookup{\compset}{1337_{\mathfrak{UId}}} = \{(\{1337_{\mathfrak{UId}}\},C_{1337})\}
\]
Note that a variation of this module can be used to describe the DNS.
 
\subsection{Regular Expressions}

Among the most widespread and popular descriptions of components are component APIs, and component documentation. One can imagine selecting components based on criteria expressed on their textual description, in addition to other specifications. An example is selecting components according to their author(s), as appearing in the documentation.
This constitutes the case of matching regular expressions (note that we use the original regular expressions as defined in Kleene algebra):
\[
\begin{array}{lcll}
char&::=&\multicolumn{2}{l}{a~|~...}\\
string&::=&\multicolumn{2}{l}{char~|~string~string}\\
expr&::=&\multicolumn{2}{l}{\varnothing~|~char~|~(expr~expr)~|~(expr+expr)~|~expr*}\\
\matchmodfor{\mathfrak{regexp}}&::=&\multicolumn{2}{l}{(string,expr,\matchrelfor{\mathfrak{regexp}})}\\
&&where~\matchrelfor{\mathfrak{regexp}}: string\times expr \mapsto  \mathbb{N}\\
&&\matchrelfor{\mathfrak{regexp}}(s,e)=number~of~occurrences~of~s~in~e\\
\end{array}
\]
Now imagine that a user wants to obtain a component for which John Doe is indicated as the main author of that component in the accompanying documentation and preferably take the component with the unique identifier 1337.
A collection including such a component could then be:
%\begin{lstlisting}
%uid_specification_term: LL_UID_SPECIFICATION_TERM
%regexp_specification_term: LL_REGEXP_SPECIFICATION
%... 
%create uid_specification_term.make ("1337")
%create regexp_specification_term.regexp_specification("This component... 
%                     author: John Doe")
%Current.add_specification_term_to_spec(uid_specification_term)
%Current.add_specification_term_to_spec(regexp_specification_term)
%... 
%\end{lstlisting}
\[
\begin{array}{lcl}
\compset=&\{&(\{1_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp}\},C_1),...\\
         &  &(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp}\},C_{1337}),...\\
         &  &(\{n_{\mathfrak{UId}}\},C_n) \}\\
\end{array}
\]
Looking up a component fulfilling at least one of these characteristics would then produce:
\[
\begin{array}{ll}
\multicolumn{2}{}l{\lookup{\compset}{(1337_{\mathfrak{UId}}+``*author: John~Doe*"_\mathfrak{regexp})} = }\\
~\{&(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp}\},C_{1337}),\\
&(\{1_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp}\},C_1)\}
\end{array}
\]
Looking up a component fullfilling both criteria can be made as follows:
\[
\begin{array}{ll}
\multicolumn{2}{l}{\lookup{\compset}{(1337_{\mathfrak{UId}}*``*author: John~Doe*"_\mathfrak{regexp})} = }\\
~\{&(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp}\},C_{1337})\}\\
\end{array}
\]
%A module willing to look the component up could then acquire a reference to that component through by issuing the following calls:
%\begin{lstlisting}
%uid_template: LL_UID_TEMPLATE 
%regexp_template: LL_REGEXP_TEMPLATE 
%component: LL_COMPONENT
%components: LL_COMPONENT_COLLECTION
%...
%create uid_template.make ("1337")
%create regexp_template.regexp_template ("*author: John Doe*")
%component:= (components^(uid_template+regexp_template)).get_first_component
%... 
%\end{lstlisting}

\subsection{Load Balancing}

Another criterion of component linking, is its current load. 
\[
\begin{array}{lcl}
\matchmodfor{\mathfrak{load}}&::=&(\mathbb{N},~\varnothing,~\matchrelfor{\mathfrak{load}})\\
&&where~\matchrelfor{\mathfrak{load}}: \mathbb{N} \times \varnothing \mapsto \mathbb{N}^+\\
&&\matchrelfor{\mathfrak{load}}(n)=number~of~components~currently~using~component~n\\
\end{array}
\]
Imagine that a user wants to obtain the component which is currently experiencing the smallest load written by John Doe.
Suppose also that some components support only up to 10 clients at the time.
A collection containing such components could then be specified as follows:
\[
\begin{array}{lcl}
\multicolumn{3}{l}{\compset=\{(\{1_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp},C_1),...}\\
         &  &(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp},\requal~1337_\mathfrak{load}<10.0\},C_{1337}),...\\
         &  &(\{n_{\mathfrak{UId}},n_\mathfrak{load}\},C_n) \}\\
\end{array}
\]


%\begin{lstlisting}
%uid_specification_term: LL_UID_SPECIFICATION_TERM
%regexp_specification_term: LL_REGEXP_SPECIFICATION
%load_specification_term: LL_LOAD_SPECIFICATION
%... 
%create uid_specification_term.make ("1337")
%create regexp_specification_term.make ("This component... 
%                     author: John Doe")
%create load_specification_term.make (Current.component)
%
%Current.add_specification_term_to_spec(uid_specification_term)
%Current.add_specification_term_to_spec(regexp_specification_term)
%Current.add_specification_term_to_spec(load_specification_term<10.0)
%... 
%\end{lstlisting}

%Just like in the previous two examples we added the specification term to the component. As an additional possibility we can set conditions that the matched component has to fulfill. Here we decaled that the load on the component has to be inferior to ten.

A programmer wishing to get such a component should perform the following lookup (note that the result is dependant of the number of clients currently connected to both components):
\[
\begin{array}{ll}
\multicolumn{2}{l}{\lookup{\compset}{(``*author: John~Doe*"_\mathfrak{regexp}/(1.0+_\mathfrak{load}))} = }\\
~\{&(\{1_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp},C_1),\\
&(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp}\},C_{1337})\}\\
\end{array}
\]
%A module willing to look the component up could then acquire that component's reference by making the following calls:
%\begin{lstlisting}
%uid_template: LL_UID_TEMPLATE 
%regexp_template: LL_REGEXP_TEMPLATE 
%load_template: LL_LOAD_TEMPLATE 
%component: LL_COMPONENT
%components: LL_COMPONENT_COLLECTION
%...
%create uid_template.makr ("1337")
%create regexp_template.make ("*author: John Doe*")
%create load_template.make
%component:= (components^((uid_template+regexp_template)/(1.0+load_template))).get_first_component
%...
%\end{lstlisting}
 
\subsection{Compliance to an Interface}\label{subsec:comply}

It very often happens that programmers want to obtain components that comply to a given interface.
Informally, compliance to an interface is expressed in terms of a structural subtyping relationship. 
Suppose that $I_1$ is compliant to $I_2$ if and only if $I_1$ has at least the same procedures as $I_2$.
\[
\begin{array}{lcl}
p&& procedure~names\\
t&& types~names\\
procedure&::=&(p,\{t_0,...,t_n\})\\
I&::=&\{procedure_1,...,procedure_n\}\\
\matchmodfor{\mathfrak{comply}}&::=&(Interfaces,~Interfaces,~\matchrelfor{\mathfrak{comply}})\\
&&where~\matchrelfor{\mathfrak{comply}}: Interfaces \times Interfaces \mapsto \{0,~1\}\\
&&\matchrelfor{\mathfrak{comply}}(I_1,I_2)= 1~iff~I_2\subseteq I_1,~0~otherwise\\
\end{array}
\]
Supposing that some components offer procedures to set and get their internal attributes, the collection of components could be:
\[
\begin{array}{lcl}
\multicolumn{3}{l}{\compset=\{(\{1_{\mathfrak{UId}},\{set\_a~\{Void,~string\},get\_a~\{string\},decrement~\{\}\}_\mathfrak{comply},C_1),...}\\
         &  &(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp}\},C_{1337}),...\\
         &  &(\{n_{\mathfrak{UId}},n_\mathfrak{load}, \{set\_a~\{Void,~string\},get\_a~\{string\}\}\}_\mathfrak{comply},C_n) \}\\
\end{array}
\]
Then a program seeking for components that comply to an interface containing $set\_a$ and $get\_a$ could make the following lookup:
\[
\begin{array}{ll}
\multicolumn{2}{l}{\lookup{\compset}{\{set\_a~\{Void,~string\},get\_a~\{string\}\}_\mathfrak{comply}} = }\\
~\{&(\{1_{\mathfrak{UId}},\{set\_a~\{Void,~string\},get\_a~\{string\},decrement~\{\}\}_\mathfrak{comply},C_1),\\
&(\{n_{\mathfrak{UId}},n_\mathfrak{load}, \{set_a~\{Void,~string\},get_a~\{string\}\}\}_\mathfrak{comply},C_n)\}\\
\end{array}
\]
Variants of this example are countless as we could return the number of procedures in common, or the number of lacking procedures etc.
However this is the simplest variant  and it corresponds to the approach of service groups~\cite{SAKOMI01}. 

\subsection{Secure Linking}\label{subsec:secure}

By specifying a \ensuremath{\textbf{required}} clause, a component \emph{provider} can enforce the matching of a specification as a necessary precondition for handing out any reference to its component.
Our current example is presenting encrypted matching and can be considered as a subset of tagged sets~\cite{Oriol:05:TSASTCM} or any other matching mechanisms driven or restricted by encryption~\cite{BOV99,EB05}.

We call \ensuremath{E(K,value)} the encryption and \ensuremath{D(K,value)} the decryption, for which we give the semantics \ensuremath{\mathcal{S}\translate{\cdot}} that we detail below.
\[
\begin{array}{lclll}
SKey&&&&Symetric Keys\\
\overline{AKey}&&&&Asymmetric~Keys~(private)\\
AKey&&&&Asymmetric~Keys~(public)\\
value&::=&\multicolumn{3}{l}{basic_value~|~value_{\overline{AKey}}~|~value_{SKey}}\\
e&::=&\multicolumn{3}{l}{value~|~E(SKey,e)~|~E(AKey,e)~|~D(SKey,e)~|~D(AKey,e)}\\
\\
\multicolumn{5}{l}{\mathcal{S}\translate{\cdot}:~e\mapsto value}\\
\multicolumn{5}{l}{\mathcal{S}\translate{value}=value}\\
\multicolumn{5}{l}{\mathcal{S}\translate{value}=value}\\
\multicolumn{5}{l}{\mathcal{S}\translate{E(SKey,e)}=\mathcal{S}\translate{e}_{SKey}}\\
\multicolumn{5}{l}{\mathcal{S}\translate{E(\overline{AKey},e)}=\mathcal{S}\translate{e}_{\overline{AKey}}}\\
\multicolumn{5}{l}{\mathcal{S}\translate{D(SKey,e_{SKey})}=\mathcal{S}\translate{e}}\\
\multicolumn{5}{l}{\mathcal{S}\translate{D(AKey,e_{\overline{AKey}})}=e}\\
\end{array}
\]
The associated matching module is then:
\[
\begin{array}{lclll}
mm_\mathfrak{Crypt}&::=&\multicolumn{3}{l}{(Keys,~Keys,~\match_\mathfrak{Crypt})}\\
&&where~\match_\mathfrak{Crypt}: &\multicolumn{2}{l}{Keys \times Keys \mapsto \{0,1\}}\\
&&&\match_\mathfrak{Crypt}(K_1,K_2)=&1~if~\mathcal{S}\translate{D(K_2,E(K_1,value))}=value\\
&&&&0~otherwise\\
\end{array}
\]
A collection containing components being locked by an asymmetric key $AKey$ could then be : 
\[
\begin{array}{lcl}
\multicolumn{3}{l}{\compset=\{(\{1_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp},C_1),...}\\
         &  &(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp},\requal AKey_{\mathfrak{Crypt}} = 1.0\},C_{1337}),...\\
         &  &(\{n_{\mathfrak{UId}},n_\mathfrak{load},AKey_{\mathfrak{Crypt}}\},C_n) \}\\
\end{array}
\]
A programmer wishing to know all the components locked with $AKey$ should then make the following lookup:
\[
\begin{array}{ll}
\multicolumn{2}{l}{\lookup{\compset}{\overline{AKey}_\mathfrak{Crypt}} = }\\
&\{(\{1337_{\mathfrak{UId}},``... author: John~Doe..."_\mathfrak{regexp},\requal AKey_{\mathfrak{Crypt}} = 1.0\},C_{1337})\\
&(\{n_{\mathfrak{UId}},n_\mathfrak{load},AKey_{\mathfrak{Crypt}}\},C_n) \}\\
\end{array}
\]
Implementation-wise, locking a component with a cryptographic key means that the access to the component should be made on the platform where the component is located.
Similarly to tagged sets~\cite{Oriol:05:TSASTCM}, the keys do not need to transit through the network.

%\begin{lstlisting}
%component: LL_COMPONENT
%crypto_specification_term: LL_ASYM_CRYPTO_SPECIFICATION
%private_key: ASYM_CRYPTOGRAPHIC_KEY
%... 
%create crypto_specification_term.make (private_key)
%...
%Current.add_specification_term_to_spec(crypto_specification_term=1.0)
%... 
%\end{lstlisting}


%\begin{lstlisting}
%crypto_template: LL_ASYM_CRYPTO_TEMPLATE 
%component: LL_COMPONENT
%public_key: ASYM_CRYPTOGRAPHIC_KEY
%...
%create crypto_template.make (publich_key)
%component:= (components^crypto).get_first_component
%\end{lstlisting}


%\subsection{Other matching modules}\label{subsec:other}
%
%We envision many other matching modules to be added to this very small list.
%We already defined some of them formally and present them in a separate technical report~\cite{}.
%Among them, we defined matching modules based on subtyping and structural subtyping.
%We also defined modules based on an extended notion of the reuse frequency defined by Bay\textit{et al.}~\cite{Bay}.


