CSc 520Principles of Programming Languages1: IntroductionChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 2005What’s a Programming Language?1 What’s a Language???• A formal language is a notation for precisely communicating ideas.• By formal we mean that we know exactly which “sentences” belong to the language and that everysentence has a well-defined meaning.• A language is defined by specifying its syntax and semantics.• The syntax describes how words can be formed into sentences. The semantics describes what thosesentences mean.2 Example Languages• English is a natural, not a formal language. The sentenceMany missiles have many warheads.has multiple possible meanings.• Programming languages: FORTRAN, LISP, Java, C++,. . .• Text processing languages: LATEX, troff,. . .1\begin{slide}{Example Languages}\begin{itemize}\item English is a \highlightbox{natural}, not a formallanguage. The sentence\end{itemize}\end{slide}• Specification languages: VDM, Z, OBJ,. . .Programming Language Design3 Programming Language Design• Programming language design has a long history.• The first modern language (The “Plankalk¨ul”) was designed by Konrad Zuse in the 30s and 40s.• The Language List (http://wuarchive.wustl.edu/doc/misc/lang-list.txt and http://cui.unige.ch/langlist) now contains some 2000entries.4 Programming Language Design. . .• Languages are used for a number of applications:– Programming (of course),– Robot control,– Specification (of compilers, safety-critical software systems, etc.),– Video game scripting,– Database access,– Typesetting, etc.5 Programming Language Design. . .• Programming language design is a lot of fun. Lots of people have felt the urge to design their ownlanguage.• Programming language design is hard. Most language designs are horrible because:– Most people don’t know enough languages to know what is a good one and a bad one.– Most people don’t know about the principles of language design.– Most people don’t know enough about compiler design.– Most people have no taste.26 Goals of Programming Language DesignThese are some of the principles language designers have employed:1. Simple2. Expressive3. Well-defined syntactic/semantic description4. Reliable/safe5. Easy to translate6. Efficient object code7. Orthogonal8. All language objects should be first class7 Goals of Programming Language Design. . .9. Transparent data types10. Machine independence and portability11. Verifiability12. Consistency with familiar notations13. Uniformity14. Extensibility15. Supports programming-in-the-large16. Supports information hiding8 Goals of Programming Language Design. . .• Not all principles can/should be applied everywhere in every language.• Not all principles will apply to every type of language.• Some principles may have made sense at some point in time, but don’t anymore.Compilers and Languages39 Compilers and Languages• The history of compiler design and language design go hand in hand:– The design of new language features have prompted new compiler technology,– New compiler technology has allowed new languages features.• There is a constant struggle between the programming language user (“Please add this feature!”), thelanguage designer (“How can I incorporate the new feature with the existing ones?”), and the compilerwriter (“No more features!”).10 Compilers and Languages. . .• Many successful languages have been designed concurrently with a compiler for the language.• In contrast, many unsuccessful languages have been designed by a committee, without much inputfrom compiler writers.• It is important for the language designer to be aware of state-of-the-art compiler technology.• It is important for the compiler designer (particularly, the compiler tool designer) to be aware of therequirements of modern languages.11 History of Procedural LanguagesModula−2(Wirth, 78)(Xerox PARC, 77)MesaModula(Wirth, 77)(US DoD 83)Ada83Modula−3(DEC−SRC,88)Oberon(Wirth, 88,91)(US DoD 90)Ada90C++(Stroustrup,86)Pascal(Wirth, 70)(Wirth&Apple, 85)Object Pascal(IBM, 54−57)FORTRANPL/I(IBM, 64)C(Ritchie, 72)Algol68Algol60Simula67412• Algol60 introduced structured program-ming.• Simula67 introduced object-orientedprogramming.• Mesa introduced modules.• FORTRAN still rules!Goals of Language Design13 Simplicity• It should be possible to learn the entire language.• The language should have a small set of basic constructs.• It should be easy for a user to figure out what it means to combine different language elements.• A language-rich language is not necessarily a good one:1. Every feature has to be implemented by the compiler writer ⇒ higher risk of compiler bugs.2. Every feature has to be specified in the language design document ⇒ higher risk of design flawsand omissions.3. Features often interact ⇒ it may be impossible to learn only a small part of the language.14 Expressiveness• The language shouldn’t be so simple that it becomes difficult or impossible to write real programs init.• Pascal has very simple procedures for IO: There is a read-statement and a write-statement:var x:integer;read x;write x+1;• But, there is no way to catch erroneous input! If the user entered hello! when the program expectedto read an integer, the program will just fail.515 Well-defined description• Lexical structure (what identifiers/numbers look like) is easy to define.• Syntactic structure is easy to define.• Semantics is hard to define for reasonable size languages. Often done informally or in “semi-formal”English.• Type equivalence was left out of Pascal definition: some implementations used name equivalence somestructural equivalence some declaration equivalence.16 Well-defined description. . .TYPE T1 = RECORD a:CHAR; b:REAL END;TYPE T2 = RECORD a:CHAR; b:REAL END;VAR x1 : T1;VAR x2 : T2;VAR x3,x4: RECORD a:CHAR; b:REAL END;BEGINx1 := x2; (* OK, or not? *)x3 := x4; (* OK, or not? *)END• name-equivalence: both assignments are illegal.• declaration-equivalence: only 2nd assignment is legal.• structural type equivalence: both assignments are legal.17 Well-defined description. . .TYPE Shape = OBJECTMETHOD draw (); · · ·METHOD move (X,Y:REAL); · · ·END;TYPE Cowboy = OBJECTMETHOD draw (); · · ·METHOD move (X,Y:REAL); · · ·END;VAR s:S; c:C;BEGIN s := c; (* OK? *)