Programming Languages
Modules
CSCI-GA.2110-003 Fall 2020
Modules
Programs are built out of components called modules. Each module:
■ has a public interface that defines entities exported by the module
■ may include other (private) entities that are not exported
■ may depend on the entities defined in the interface of another module
(weak external coupling)
■ should define a set of logically related entities (strong internal coupling)
2 / 39
What is a module?
■ different languages use different terms
■ different languages have different semantics for this construct
(sometimes very different)
■ a module is somewhat like a record, but with an important distinction:
◆ record =⇒ consists of a set of names called fields, which refer to values in the record.
◆ module =⇒ consists of a set of names, which can refer to values, types, routines, other language-specific entities, and possibly other modules
3 / 39
Language constructs for modularity
Issues:
■ public interface
■ private implementation
■ dependencies between modules
■ naming conventions of imported entities
■ relationship between modules and files
■ access control: module controls whether a client can access its contents
■ closed module: names must be explicitly imported from outside the
module
■ open module: outside names are accessible inside module (no explicit
import)
4 / 39
Language choices
■ Ada : package declaration and body, with and use clauses, renamings
■ C : header files, #include directives
■ C++ : header files, #include directives, namespaces, using
declarations/directives, namespace alias definitions
■ Java : packages, import statements
■ ML : signature, structure and functor definitions
5 / 39
Ada: Packages
package Queues is
Size: constant Integer := 1000;
type Queue is private; — information hiding
procedure Enqueue (Q: in out Queue, Elem: Integer); procedure Dequeue (Q: in out Queue; Elem: out Integer); function Empty (Q: Queue) return Boolean;
function Full (Q: Queue) return Boolean;
function Slack (Q: Queue) return Integer;
— overloaded operator “=”:
function “=” (Q1, Q2: Queue) return Boolean;
private
… — concern of implementation, not of package client
end Queues;
6 / 39
Information hiding
package Queues is
… — visible declarations
private
type Storage is
array (Integer range <>) of Integer; type Queue is record
Front: Integer := 0; — next elem to remove
Back: Integer := 0; — next available slot Contents: Storage (0 .. Size-1); — actual contents Num: Integer := 0;
end record; end Queues;
7 / 39
Implementation of Queues
package body Queues is
procedure Enqueue (Q: in out Queue;
begin
if Full(Q) then
Elem: Integer) is
— need to signal error: raise exception
else
Q.Contents(Q.Back) := Elem;
end if;
Q.Num := Q.Num + 1;
Q.Back := (Q.Back + 1) mod Size;
end Enqueue;
8 / 39
Predicates on queues
function Empty (Q: Queue) return Boolean is begin
return Q.Num = 0; — client cannot access — Num directly
end Empty;
function Full (Q: Queue) return Boolean is begin
return Q.Num = Size; end Full;
function Slack (Q: Queue) return Integer is begin
return Size – Q.Num; end Slack;
9 / 39
Operator Overloading
function “=” (Q1, Q2 : Queue) return Boolean is begin
if Q1.Num /= Q2.Num then return False;
else
for J in 1 .. Q1.Num loop
— check corresponding elements
if Q1.Contents((Q1.Front + J – 1) mod Size) /= Q2.Contents((Q2.Front + J – 1) mod Size)
then
return False;
end if;
end loop;
return True; — all elements are equal
end if;
end “=”; — operator “/=” implicitly defined
— as negation of “=”
10 / 39
Client can only use visible interface
with Queues; use Queues; with Text_IO;
procedure Test is
Q1, Q2: Queue; — local objects of a private type Val : Integer;
begin
Enqueue(Q1, 200); — visible operation for J in 1 .. 25 loop
Enqueue(Q1, J);
Enqueue(Q2, J);
end loop;
Dequeue(Q1, Val); — visible operation if Q1 /= Q2 then
Text_IO.Put_Line(“lousy␣implementation”); end if;
end Test;
11 / 39
Implementation
■ package body holds bodies of subprograms that implement interface
■ package may not require a body:
package Days is
type Day is (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
subtype Weekday is Day range Mon .. Fri;
Tomorrow: constant array (Day) of Day
:= (Tue, Wed, Thu, Fri, Sat, Sun, Mon);
Next_Work_Day: constant array (Weekday) of Weekday := (Tue, Wed, Thu, Fri, Mon);
end Days;
12 / 39
Syntactic sugar: use and renames Visible entities can be denoted with an expanded name:
with Text_IO;
… Text_IO.Put_Line(“hello”);
use clause makes name of entity directly usable:
with Text_IO; use Text_IO; …
Put_Line(“hello”);
renames clause makes name of entity more manageable:
with Text_IO;
package T renames Text_IO; …
T.Put_Line(“hello”);
13 / 39
Sugar can be indispensable
with Queues;
procedure Test is
Q1, Q2: Queues.Queue;
begin
if Q1 = Q2 then …
— error: “=” is not directly visible
— must write instead: Queues.”=”(Q1, Q2)
Two solutions:
■ import all entities:
use Queues;
■ import operators only:
use type Queues.Queue;
14 / 39
C++ namespaces
■ late addition to the language
■ an entity requires one or more declarations and a single definition
■ a namespace declaration can contain both, but definitions may also be
given separately
// in .h file
namespace util {
int f (int); /* declaration of f */
}
// in .cpp file
namespace util { int f (int i) {
}
// definition provides body of function
… }
15 / 39
Dependencies between modules
■ files have semantic significance: #include directives means textual substitution of one file in another
■ convention is to use header files for shared interfaces #include
int main () {
std::cout << "C++␣is␣really␣different"
return 0; }
<< std::endl;
16 / 39
Header files are visible interfaces
namespace stack { // in file stack.h void push (char);
char pop ();
}
#include "stack.h" // import into client file
void f () {
stack::push(’c’);
if (stack::pop() != ’c’) error("impossible");
}
17 / 39
Namespace Definitions
#include "stack.h" // import declarations
namespace stack { // the definition const unsigned int MaxSize = 200; char v[MaxSize];
unsigned int numElems = 0;
} }
void push (char c) {
if (numElems >= MaxSize)
}
throw std::out_of_range(“stack␣overflow”); v[numElems++] = c;
char pop () {
if (numElems == 0)
throw std::out_of_range(“stack␣underflow”); return v[–numElems];
18 / 39
Syntactic sugar: using declarations
namespace queue { // works on single queue void enqueue (int);
int dequeue ();
}
#include “queue.h” // in client file
using queue::dequeue; // selective: a single entity
void f () {
queue::enqueue(10); // prefix needed for enqueue queue::enqueue(-999);
if (dequeue() != 10) // but not for dequeue
error(“buggy␣implementation”); }
19 / 39
Wholesale import: using directive
#include “queue.h” // in client file
using namespace queue; // import everything
void f () {
enqueue(10); // prefix not needed enqueue(-999);
if (dequeue() != 10) // for anything
error(“buggy␣implementation”); }
20 / 39
Shortening names
Sometimes, we want to qualify names, but with a shorter name.
In Ada:
package PN renames A.Very_Long.Package_Name;
In C++:
namespace pn = a::very_long::package_name; We can now use PN as the qualifier instead of the long name.
21 / 39
Visibility: Koenig lookup
When an unqualified name is used as the postfix-expression in a function call (expr.call), other namespaces not considered during the usual unqualified look up (basic.lookup.unqual) may be searched; this search depends on the types of the arguments.
For each argument type T in the function call, there is a set of zero or more associated namespaces to be considered. The set of namespaces is determined entirely by the types of the function arguments. typedef names used to specify the types do not contribute to this set.
The set of namespaces are determined in the following way:
22 / 39
Koenig lookup: details
■ If T is a primitive type, its associated set of namespaces is empty.
■ If T is a class type, its associated namespaces are the namespaces in
which the class and its direct and indirect base classes are defined. ■ If T is a union or enumeration type, its associated namespace is the
namespace in which it is defined.
■ If T is a pointer to U, a reference to U, or an array of U, its associated
namespaces are the namespaces associated with U.
■ If T is a pointer to function type, its associated namespaces are the
namespaces associated with the function parameter types and the namespaces associated with the return type. [recursive]
23 / 39
Koenig Example
namespace NS {
class A {};
void f( A *&, int ) {} }
int main() {
}
NS::A *a; f( a, 0 );
//calls NS::f
24 / 39
Linking
■ an external declaration for a variable indicates that the entity is defined elsewhere
extern int x; // will be found later
■ a function declaration indicates that the body is defined elsewhere
■ multiple declarations may denote the same entity extern int x; // in some other file
■ an entity can only be defined once
■ missing/multiple definitions cannot be detected by the compiler: link-time
errors
25 / 39
Packages in Java
■ ■ ■ ■
package structure parallels file system
a package corresponds to a directory
a class is compiled into a separate object file
each class declares the package in which it appears (open structure)
package polynomials; class poly {
… // in file …/alg/polynomials/poly.java }
package polynomials; class iterator {
… // in file …/alg/polynomials/iterator.java }
Default: anonymous package in current directory.
26 / 39
Dependencies between classes
■ dependencies indicated with import statements:
import java.awt.Rectangle; // declared in java.awt
import java.awt.*; // import all classes // in package
■ no syntactic sugar across packages: use expanded names
■ none needed in same package: all classes in package are directly visible to
each other
27 / 39
Modules in Java
■ A module is a group of closely related packages
■ Each module goes into its own module root directory and must be
compiled before use.
■ Each root directory has a module descriptor file, module-info.java.
■ Module descriptor file describes the module:
◆ Name
◆ Dependencies – all modules on which this module depends
◆ Public packages – packages to be exposed
◆ Services offered – service implementations to be published
◆ Services consumed – service implementations to be used
◆ Reflection permissions – controls access to private members
■ Modules must be nested under a root directory using the same name as the module.
◆ E.g., edu.nyu.modules/edu/nyu/modules
◆ With modules, periods are ordinary characters–not directory path
dividers
28 / 39
Modules in Java
■ Define an ordinary class “Stacks” in an ordinary package “edu.nyu.proglang.stacks”:
package edu.nyu.proglang.stacks;
public class Stack {
public static void push(…) { … } public static void pop() { … } public static bool isempty() { … }
}
■ Put it in a module that has the same name as the package, inside module-info.java:
module edu.nyu.proglang.stacks { exports edu.nyu.proglang.stacks;
}
29 / 39
Modules in Java
■ Consume it from another module, main.application. Add this to the module’s module-info.java:
module edu.nyu.proglang.main.application { requires edu.nyu.proglang.stacks;
}
■ Create an application that imports the module: // this package
package edu.nyu.proglang.main.application;
// looks like an ordinary package import!
import edu.nyu.proglang.stacks.Stack;
public class Main {
public static void main(String[] args) {
}
Stack.push(6); }
30 / 39
Modules in ML
There are three entities:
■ signature : an interface
■ structure : an implementation
■ functor : a parameterized structure
A structure implements a signature if it defines everything mentioned in the signature (in the correct way).
31 / 39
ML signature
An ML signature specifies an interface for a module.
signature STACKS = sig
end
type stack
exception Underflow
val empty : stack
val push : char * stack -> stack val pop : stack -> char * stack val isEmpty : stack -> bool
32 / 39
ML structure
A structure provides an implementation.
structure Stacks : STACKS = struct
end
type stack = char list exception Underflow val empty = [ ]
val push = op::
fun pop (c::cs) = (c, cs)
| pop [] = raise Underflow
fun isEmpty [] = true | isEmpty _ = false
33 / 39
Signature ascription
Opaque ascription (denoted :>) hides the identity of types beyond that which is conveyed in the signature. That is, additional type information provided by the structure will be considered abstract.
structure Stacks :> STACKS = …
Transparent ascription (denoted 🙂 exposes the identity of types beyond that conveyed in the signature. That is, additional type information provided by the structure will augment the signature.
structure Stacks : STACKS = …
Both: prohibit the introduction of identifiers not already present in the signature. This is component hiding.
Both: permit types (in structures) which are broader than the signature. Permitted:
Signature: var blah : int -> int; // int -> int
Structure: fun blah x = x; // ’a -> ’a
34 / 39
Opaque ascription
signature SetSignature = sig
end;
type ’a set
val empty : ’’a set
val singleton : ’’a -> ’’a set
structure Set = struct type ’a set = ’a list; val empty = [];
fun singleton a = [a] val aux = [];
end;
structure Set2 :> SetSignature = Set; Set2.aux; (* error – component hiding *) Set2.singleton(2) = [2]; (* error – list
representation hidden *)
35 / 39
Transparent ascription
signature SetSignature = sig
end;
type ’a set
val empty : ’’a set
val singleton : ’’a -> ’’a set
structure Set = struct type ’a set = ’a list; val empty = [];
fun singleton a = [a] val aux = [];
end;
structure Set2 : SetSignature = Set; Set2.aux; (* error – component hiding *) Set2.singleton(2) = [2]; (* okay *)
36 / 39
ML functor
A functor creates a structure from a structure.
signature TOTALORDER = sig
type element;
val lt : element * element -> bool;
end;
functor MakeBST(Lt: TOTALORDER): sig
type ’label btree;
exception EmptyTree;
val create : Lt.element btree;
val lookup : Lt.element * Lt.element btree
-> bool;
val insert : Lt.element * Lt.element btree
-> Lt.element btree;
37 / 39
Functors (cont’d)
end;
val deletemin : Lt.element btree -> Lt.element * Lt.element btree;
val delete : Lt.element * Lt.element btree -> Lt.element btree;
end = struct open Lt;
datatype ’label btree = Empty |
Node of ’label val create = Empty;
* ’label btree * ’label btr
fun lookup(x, Empty)
fun insert(x, Empty) exception EmptyTree;
fun deletemin(Empty)
fun delete(x,Empty) = …;
= …; = …;
= …;
38 / 39
Invoking the Functor
structure String : TOTALORDER = struct
type element = string; fun lt(x,y) =
end; end;
let
fun lower(nil) = nil |
lower(c::cs) =
(Char.toLower c)::lower(cs);
in
implode(lower(explode(x))) < implode(lower(explode(y)))
structure StringBST = MakeBST(String);
39 / 39