Modules.lhs

> module Modules where

> import List (partition, nub)
> import Maybe (fromJust)

> -- implementation only
> import QualNames



Module system parameters
========================

The module system is parametrized on four type parameters:

    * The type of identifiers used in the source code of a program (#qn#).
      Those may be qualified or unqualified names.
    
    * The type of module names and name qualifiers (#m#).
      These are used to name modules, in import declarations, export lists,
      and qualified names.

    * The type of simple names (#n#).  Those are used
      to name entities in definitions or when exported.

    * The type of entities (#ent#).  These are the objects referred to by 
      identifiers in the program and are introduced by declarations 
      (functions, type constructors, value constructors, field selectors,
      classes, class methods).


The parameters are not completely arbitrary, in fact there is a close relation
between the first three.  To capture this, we use the class #QualNames#:

| class QualNames qn m n | qn -> m n, m n -> qn where
|   -- observers
|   isQual          :: qn -> Bool
|   getQualifier    :: qn -> m
|   getQualified    :: qn -> n
| 
|   -- constructors
|   mkUnqual        :: n -> qn 
|   mkQual          :: m -> n -> qn 

In order for the types to be suited for the purposes of the module system,
we require that they be related by the #QualNames# class.
This essentially forces #i# to be a type similar to the following:

| data Name m n = Unqualified n | Qualified m n


We also require that there be a special element in #m#, which we shall
call "Main", and a special element in #qn# which shall be denoted as "main".


For the type of entities, we require that there is a way to identify value
constructors,  and that we know the the ownership relation between
entities (e.g. a type constructor may "own" a number of value constructors).
Formally this is captured by the requirement that the type #ent#
be an instance of the following class:

| class Entity ent where
|   isCon   :: ent -> Bool
|   owns    :: ent -> [ent]


Finally, all four types should be in the #Eq# class, i.e. values of the
appropriate types should be comparable for equality. 



The abstract syntax
===================


A Haskell module consists of a name, an export specification, a number
of import declarations and a number of local declarations.  This 
suggests the following data structure:

> data Mod qn m n ent = Mod
>     { modName       :: m
>     , modExport     :: Maybe [ExpListEntry qn m]
>     , modImports    :: [Import m n]
>     , modDefines    :: Rel n ent
>     }                                                 

In the concrete syntax of Haskell, it is valid to just have the module body
(imports and declarations).  This is considered to be an abbreviation for 
a module with name "Main" (i.e. the special element of the #m# type),
and export specification exporting a single entity named "main"
(the special element of the #qn# type).  (sect 5.1. of report)

It is also valid to omit just the export specification (sect 5.2 of report),
but this is not considered to be an abbreviation.  Instead it is a special
kind of specification, one saying that only (and all) locally defined
entities are to be exported.  

> data ExpListEntry qn m    = Ent (EntSpec qn) | ModuleExp m

In an export list a programmer may write two kinds of things - either
the name of an entity with (perhaps) some subordinate names (here modeled
by an #EntSpec#), or the so called "module" export, which in concrete
Haskell syntax is written as #module M# (where #M# is a module alias).

An #EntSpec# consists of the name of an entity, with possibly the
names of some subordinate names.  An explicit list of subordinate names
is modeled with the #Some# component of the #SubSpec# data type,
while a request for all available subordinate names (the #(..)# notation
of Haskell) is modeled using #All#.

> data EntSpec j          = EntSpec j (Maybe (SubSpec j)) deriving Eq
> data SubSpec j          = All | Some [j]                deriving Eq

The #EntSpec# type is in fact shared between export lists and import
declarations, as they are structurally the same.  The only difference 
between the two is the types used to name entities (i.e. the #j# parameter
above).  In the case of an export list we use #qn# (the type of program
identifiers - qualified or not), while in the case of import declarations
we use #n# (the type of simple names).

We note that our abstract syntax is slightly more permissive than Haskell's
as one may add subordinate names to any name, while in Haskell
it is syntactically invalid to add subordinate names to lower case
identifiers.  

This brings us to the data structure used to model import declarations:

> data Import m n     = Import
>     { impQualified  :: Bool
>     , impFrom       :: m 
>     , impAs         :: m
>     , impSpec       :: (ImpMethod, [EntSpec n])
>     }                  
>
> data ImpMethod = Importing | Hiding

An import may be qualified (or not), contains the name of the module from which 
entities are to be imported, an alias to be used in qualified names for entities
which came through this import, and finally a specification of which entities 
are to be imported.  In concrete Haskell terms, the only required field is
the name of the source module, but the omissions of any of the other fields
are considered to be abbreviations as follows:

    * The value of #impQualified# is #False# unless the #qualified#
    keyword was present in the source code, in which case it is #True#.

    * If the #as# clause of a module is omitted, this field gets the same
    value as the #impFrom# field, i.e. the name of the source module
    is used to qualify names.

    * If the import specification is omitted, it is assumed to be
    #(Hiding, [])# (or #hide ()# in Haskell syntax), essentially saying that
    all entities are to be imported.
    


Semantics
=========

The abstract syntax above was nicely structured in the sense that bigger 
pieces were made out of smaller ones.  It would be nice to be able to
give meanings of the bigger pieces in terms of the meanings of the smaller
ones and this is the approach we take.  Each piece of the abstract syntax
is modeled as a relation transformer, i.e. given a relation it
produces a new relation. To put the whole idea in perspective
we first need a brief digression to relations.


Relations
---------

We use relations to model the association between names and entities.
This seems like a natural choice as in a single framework we may
represent undefined names (i.e. names which refer to no entities),
ambiguous names (names referring to more than one entity) and proper
names (referring to exactly one entity).  It is not enough to restrict
ourselves to just using proper names, as there are valid Haskell
programs containing ambiguous names in scope (report section 5.5.2),
of course there is the requirement that such names are not used.
Furthermore, one may use the information provided by the relation to
generate useful error messages.  We model relations as lists of pairs:

> type Rel a b = [(a,b)]

The exports of a module are modeled by a relation between simple names
and entities (i.e. #Rel n ent#), while the names in scope of a module
are modeled as a relation between identifiers and entities (i.e. #Rel qn ent#).
Ultimately our goal is for each module to come up with two relations:

    * the "export" relation of type #Rel n ent#
    * the "in scope" relation of type #Rel qn ent#


Functions used to compute both "exports" and "in scope" relations
-----------------------------------------------------------------

From the structure of a module we know what entities it defines.  Now
we need to consider how may a programmer refer to those entities
(i.e. what is the relation between names and entities defined in a module).
This is specified by the #locals# function, which computes a part
of the "in scope" relation of a module.  When an entity is defined in
a module one may refer to it by either using its simple name 
or by qualifying it with the name of the module 
(report section 5.5.1).  Formally this is:

| locals :: ...
|   => Mod qn m n ent 
|   -> Rel qn ent

> locals mod = [ (mkUnqual n, e) | (n,e) <- defEnts ]
>           ++ [ (mkQual m n, e) | (n,e) <- defEnts ]
>   where
>   m       = modName mod
>   defEnts = modDefines mod

This function is also used to give semantics to modules without an
export specifications.


As we saw above, there is a certain commonality between the structure of
export lists and import declarations, in the sense that they both made
use of the #EntSpec# data type.  It is nice that we (nearly) have this
commonality at the semantic level as well.  When occurring in an export
list and a non-hiding import declaration, #EntSpec#s have essentially the same
meaning.  A difference occurs in the #hiding# case of an import declaration,
in which case it was decided that ambiguities are not important and 
the semantics is slightly more permissive.

The design choice made in Haskell was that the exports of a module should
be unambiguous in the sense that all exported entities have distinct
(simple) names.  The one exception to this rule is that a type and
a data constructor may have the same name.  The reason for this is
practical - although two different entities have the same name, one
may determine from the context which entity is meant, so the ambiguity
is not crucial (as types and data constructors are never interchangeable).
The only situation in which one may not distinguish between such
entities from the context is in an export lists and import declarations.
So in Haskell a different disambiguating mechanism is used in such cases -
the only way to export (or import) a value constructor is as a subordinate 
name.  Unfortunately this is not the case in #hiding# imports, where
if a name refers to more than one entity, all of them are hidden (i.e.
not imported).

To model this asymmetry in Haskell, we add
an additional parameter to the meaning function of #EntSpec#s, namely a
predicate over entities.  As we shall see later this predicate would
either be #not . isCon# (i.e. ignore constructors), or #const True#
for the #hiding# imports case, where everything is treated in the same way.

| mEntSpec :: ...
|   => (ent -> Bool) -> EntSpec j
|   -> Rel j ent -> Rel j ent
 
> mEntSpec p (EntSpec x spec) r = xents ++ xsubs
>   where
>   xents       = [ (y,e) | (y,e) <- r, y == x, p e ]
>
>   xsubs = case spec of 
>       Nothing         -> []
>       Just All        -> allxsubs
>       Just (Some xs)  -> [ (y,e) | (y,e) <- allxsubs, y `elem` xs ]
>
>   allxsubs    = [ (y,e) | (_,xe) <- xents, s <- owns xe, (y,e) <- r, e == s ]

It is not important if the relation passed as a parameter to #mEntSpec# is
an "export" or an "in scope" one.  The idea is that we take all entities
which may be named #x# (#xents#), and then we add
all subordinate entities belonging to entities in #xent# and
satisfy #spec# (#xsubs#).
If there was no specification, then we add no entities,
if the #(..)# specification was used, then we add all the subordinate entities
in scope (#allxsubs#) and finally if an explicit list of entities was provided
we only consider elements of #allxsubs# which conform to the specification.



Export relations
----------------

To compute the exported entities of a module, we need to know what is the 
relation between names and entities in scope of the module (#inscp#).

| exports :: ...
|   => Mod qn m n ent
|   -> Rel qn ent -> Rel n ent

> exports m inscp = [ (getQualified qn, e) | (qn,e) <- exps ]
>   where
>   exps = case modExport m of
>     Nothing   -> locals m
>     Just es   -> concat [ mExpListEntry e inscp | e <- es ]

If the programmer omitted the export specification, we just export the 
locally defined entities using the #locals# function.
Alternatively if an explicit export list was present,  we take
the union of the meanings of all entries in the list.
Finally to obtain an "export" relation, we remove all qualifiers.
Note that after removing the qualifiers (or even before that)
we might end up with a relation containing ambiguous names.
This is not valid in Haskell (except for the special case mentioned in
the previous section), but we choose to handle this and all other error
related issues at a later stage.

There are two different kinds of entries which may occur in an export list are:

    * export entity by qualifier (the so called "module" export).  The
    meaning of such an export specification is described in the report 
    as follows (report 5.2 - item 5 in list):

The form "module M" abbreviates the set of all entities whose unqualified name, e, is in scope, and for which the qualified name M.e is also in scope and refers to the same entity as e.

    * export entity by name, i.e. when the programmer uses the name of an
    entity in the export list with perhaps some subordinate names.  We already
    have a function to handle such situations - #mEntSpec#.  Since a data
    constructors may not be exported on its own (report 5.2 - item 2 in list)
    we pass #not . isCon# as the additional parameter to #mEntSpec#.

| mExpListEntry :: ...
|   => ExpListEntry qn m   
|   -> Rel qn ent -> Rel qn ent

> mExpListEntry (ModuleExp m) inscp =
>               [ (x,ent) | (x,ent) <- unqs, (qual m x,ent) `elem` qs ]
>   where
>   (qs,unqs) = partition (isQual . fst) inscp
>
> mExpListEntry (Ent ispec) inscp = mEntSpec (not . isCon) ispec inscp

 
In scope relations
------------------

To compute what names are in scope within a module, we need to know the
exports of all imported modules.  The parameter #expsOf# is a function
mapping module names to their exports.  
Simply put, the entities in scope of a module are all locally
defined entities and the union of all entities imported through an import
declaration:

| inscope :: ...
|   => Module qn m n ent
|   -> (m -> Rel n ent) -> Rel qn ent 
  
> inscope m expsOf = imports ++ locals m 
>   where
>   imports = concat [ mImp imp (expsOf (impFrom imp)) | imp <- modImports m ]


The meaning of an import declaration is a relation transformer, which 
changes "export" relations to "in scope" ones:

| mImp :: ...
|   => Import m n
|   -> Rel n ent -> Rel qn ent
 
> mImp imp exps 
>   | impQualified imp  = qs
>   | otherwise         = unqs ++ qs
>   where
>   m           = impAs imp
>   qs          = [ (mkQual m n, e) | (n,e) <- incoming ]
>   unqs        = [ (mkUnqual n, e) | (n,e) <- incoming ]
>   incoming    = mImpSpec (impSpec imp) exps

We use the semantic function for import specifications to compute what entities
come in scope (#incoming#), and then we adjust their names appropriately.
In the case of a #qualified# import, we only consider qualified names (#qs#),
otherwise we also add unqualified names (#unqs#).


The meaning of import specifications is computed by #mImpSpec#, which is
essentially a "front end" to the #mEntSpec# function.
We have two cases to consider - "importing" and #hiding# specifications.
In the first case we take the union of the relations corresponding to 
the entity specifications.  We ignore data constructors, as those may
only be imported as subordinate names (#not . isCon#).
For #hiding# specifications we essentially take the complement of
the non-hiding case, except now we do not ignore data constructors.

| mImpSpec :: ...
|   => ImpSpec m n 
|   -> Rel n ent -> Rel n ent
 
> mImpSpec (method, specs) exps = case method of
>   Importing   -> ents (not . isCon)
>   Hiding      -> [ exp | exp <- exps, exp `notElem` ents (const True) ]
>   where
>   ents p = [ x | spec <- specs, x <- mEntSpec p spec exps ]



Iteration
---------

The reader might have noticed that to compute the exports of a module we
need to know what is in scope, and to compute what is in scope we need
to know certain exports.  If we allow for mutually recursive modules, our
equations become mutually recursive and care needs to be taken when
solving them.  The idea is that the "export" and "in scope" relations for a
group of mutually recursive modules are computed at the same time (as they all
depend on each other).  In fact one could process _all_ modules in a 
program together, which is less efficient from an implementation point
of view, but simplifies this presentation as we need not supply the code
for computing groups of mutually recursive modules and dependencies between
those (a standard graph algorithm, followed by a topological sort).

To represent the "in scope" and "exports" relations of a group of modules
we use lists.  Since relations may in general be ordered by inclusion,
we may also order lists (of equal length) of relations as follows:

> (<<=) :: (Eq a, Eq b) => [Rel a b] -> [Rel a b] -> Bool
> xss <<= yss = and (zipWith subEq xss yss)
>   where
>   xs `subEq` ys   = all (`elem` ys) xs 

Note that this order is different from the one usually used in Haskell and
is only well defined on finite lists.  Since Haskell programs only have
finitely many modules this is not a problem.  In fact the lists we deal
with all have the same length, namely the number of modules in the program,
so one could think of them as tuples of relations.

We not only have an ordering structure on the lists of relations, we also
have a lattice structure which is directly inherited from the lattice structure
on the relations (operations defined element-wise as in the ordering above).
The lattice we deal with is finite, as each module may only define finitely
many entities and each entity may only have finitely many names.
Names get associated with entities in two ways:

    * by local declaration, in which case an entity receives two names
    (qualified and unqualified)

    * by import declaration, in which case an entity receives either one or
    two names.

Since there are only finitely many local and import declarations,
an entity may only have finitely many names. 


| computeInsOuts :: ...         
|   => [Mod qn m n ent]       
|   -> [(Rel qn ent, Rel n ent)]

> computeInsOuts otherExps mods = inscps `zip` exps
>   where
>   inscps          = nub `map` computeIs exps 
>   exps            = lfpAfter nextExps (repeat [])
>
>   nextExps        = computeEs . computeIs 
>
>   computeEs is    = zipWith (\m -> nub . exports m) mods is
>   computeIs es    = (\m -> inscope m (toFun es)) `map` mods
> 
>   toFun es m = maybe (otherExps m) (es !!) $ lookup m mod_ixs
>   -- toFun es m = let Just pos = lookup m mod_ixs in es !! pos
>   mod_ixs     = (modName `map` mods) `zip` [0 .. ] 

> lfpAfter :: Eq a => (a -> a) -> (a -> a) 
> lfpAfter f x = let fx = f x in if fx == x then x else lfpAfter f fx

The semantic functions #exports# and #inscope# deal with only one module
at a time, but it is easy to generalize them to work on multiple modules.
Given a list of modules and a list of "in scope" relations we may 
apply #exports# in "parallel" to compute a list of "export" relations
(#computeEs#).

If we are given a list of "export" relations, we may convert it to
a function associating each module with its exports (#toFun#). This
is achieved with the aid of the association list #mod_ixs#, which 
relates modules to their positions in the list (tuple) of modules.
Now that we have a function relating modules to their exports,
we may apply #inscope# to compute the "in scope" relations of the modules
(#computeIs#).

We observe that both #exports# and #inscope# are monotonic with respect to the
relation ordering.  This follows essentially from the monotonicity of
 #mEntSpec# and the definition of "module exports" (the first case
of #mExpListEntry#).  But then #computeEs# and #computeIs# are also monotonic
when lists are ordered as described above, and hence their composition
is monotonic.  Since we work in a finite lattice this is enough to conclude
that the function #nextExps# has a least fixed point.

We may than define the exports of the argument list of modules as the least
fixed point of #nextExps#.  Intuitively, given a list of "export" relations
 #nextExps# will compute what should be in scope in each module, and then based
on that compute a better approximation of what should be exported.
Similarly, the "inscope" relations of the modules may be defined as the
least fixed point of #computeIs . computeEs#, but using the well known
fact $fix (f . g) = f (fix (g . f))$ we obtain the alternative definition
used above.