Separate CompilationSeparate CompilationSeparate Compilationldots Separate Compilationldots Module ConceptsModule Conceptsldots Separate Compilation --- ProblemsSeparate Compilationldots Separate Compilationldots Separate Compilationldots Separate Compilationldots Separate Compilationldots Encoding the Symbol TableExampleExample --- M.symExample --- M.symldots Information HidingInformation HidingModular Languages --- MesaModular Languages --- Mesaldots Modular Languages --- Mesaldots Modular Languages --- AdaModular Languages --- Adaldots Modular Languages --- Modula-2Modular Languages --- Modula-2ldots Modular Languages --- Modula-2ldots Language ComparisonsLanguage Comparisonsldots Information Hiding -- How?Information Hiding -- How?ldots Information Hiding -- How?ldots Binding TimeExchanging Information at Binding TimeReadings and ReferencesSummary520—Spring 2005—49CSc 520Principles of ProgrammingLanguages49: ModularityChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—49Separate Compilation[2]520—Spring 2005—49Separate CompilationFrom the very beginning of language design history, itwas realized that monolithic languages (the entireprogram is stored in one file and compiled all at once)were no good.Monlithic languages made compilation slow and made itdifficult for several programmers to work on the sameproblem.As early as 1958, FORTRAN II had separately compiledprocedures!Eventually it was realized that a more formal approachhad to be taken to the definition of separately compiledmodules. A number of languages (Mesa, Modula-2,Ada, ...) constructed module systems built on theideas of David Parnas:[3]520—Spring 2005—49Separate Compilation...The specification must provide1. to the intended user all the information that he will needto use the program, and nothing more.2. to the implementerall the information about theintended use that he needs to complete the program,andno additional information.[4]520—Spring 2005—49Separate Compilation...Each module has two parts, the specification and theimplementation. Much like .h and .c files in C, onlyeach part is separately compiled.IMPORT PartDiffEqn;SPEC TelescopicLens;SPEC SolarPanel;MODULE Hubble;IMPORT TelescopicLens;IMPORT SolarPanel;[5]520—Spring 2005—49Module ConceptsIn one-to-one languages, there is one specification unitfor every implementation unit. Inmany-to-manylanguages, each module can consist of severalimplementation and several specification units.#specs #impls languageone -to- zero Eiffelone -to- one Modula-2, Adamany -to- many Modula-3, Mesa[6]520—Spring 2005—49Module Concepts...The specification unit of a module contains thedeclarations of the types, constants, exceptions,procedures, etc, that the module exports.The implementation unit contains the implementation(procedure bodies, e.g.) of these objects.[7]520—Spring 2005—49Separate Compilation — ProblemsHow do we perform inter-module type checking? E.g.,we must make sure that imported procedures are calledwith the right types of arguments.How are compiled modules joined together to form anexecutable program?How can we make sure that specification andimplementation units are compiled in the correct order?How can we implement Parnas’ information hiding; i.e.how can we make sure that only the neccessaryinformation is given in the specification unit, and therest deferred to the implementation unit?[8]520—Spring 2005—49Separate Compilation...Let’s assume that a module M’s specification part is keptin a file called M.def, and that the implementation partis in M.mod.Usually, M.def is compiled into a file M.sym, whichcontains a compiled version of M.def’s symbol table.M.mod is compiled into a .o object file.Assume that M imports module N. When M.mod iscompiled, the compiler needs access to N’s symboltable, in order to be able to type-check M. The compilertherefore reads N.sym.If M imports N and N imports R, then M may (indirectly)be able to refer to R’s objects. Hence, when M iscompiled, we need access to R’s object.[9]520—Spring 2005—49Separate Compilation...COMPILERImplUnitsSpecUnitsEDITORLINKCompiledSpecsCompiledCodeExecutableProgramLOADERDYNLINK[10]520—Spring 2005—49Separate Compilation...IMPORT N,RIMPORT NM.defM.modM.symM.oIMPORT RIMPORT RN.modN.defN.symN.oR.defR.modR.symR.o[11]520—Spring 2005—49Separate Compilation...IMPORT N,RM.modcompilerM.oN.symR.symR.symcompilerN.symR.symR.symN.symM.symM.defIMPORT N[12]520—Spring 2005—49Separate Compilation...Time-stampsIf, in the slide before last, R.def was edited, R.def will(naturally) have to be recompiled. Furthermore, N.defwill have to be recompiled since it makes use ofsymbols from R.def, and now that R.def has changedwe need to type-check N.def again. For the samereason, M.def must also be recompiled.How does the compiler detect these dependencies?Each compiled specification unit M.sym, contains (inaddition to the compiled symbol table) a time-stamp,the time when the module was compiled. It also holdstime-stamps for all imported modules. This is enough todetect compilation order violations.[13]520—Spring 2005—49Encoding the Symbol TableEach specification unit is compiled into a symbol file, anencoding of the symbol table of exported symbols.We can encode the symbol table as a sequence oftuples. Each tuple defines an identifier. It stores themodule which defines the name; the kind(const,proc,type,etc), name, and type of the identifier;and extra information.nr kind mod name type extra(1) module M · · ·(2) const (1) C (3) val=45(3) const (0) int basic(4) · · · · · · · · · · · · · · ·[14]520—Spring 2005—49ExampleDEFINITION MODULE M;IMPORT N;TYPE T = RECORD a : INTEGER; b : N.T; END;END M.DEFINITION MODULE N;IMPORT R;TYPE T = ARRAY [1..R.C] OF R.T;END N.DEFINITION MODULE R;TYPE T = CHAR;CONST C = 45;END R.[15]520—Spring 2005—49Example — M.symnr kind mod name type extra(1) module M TS="10-06 23:11"(2) import N TS="10-05 09:24"(3) import R TS="10-06 14:46"(4) type std CHAR(5) type std INT(6) type equiv (3) T (4)[16]520—Spring 2005—49Example — M.sym...nr kind mod name type extra(7) const (3) C (5) val=45(8) type range (2) T$1 (5) range=[1, (7)](9) type array (2) T (6) range=(8)(10) type rec (1) T(11) field (1) a (5) record=(10)(12) field (1) b (9) record=(10)[17]520—Spring 2005—49Information Hiding[18]520—Spring
View Full Document