Transcription
Programming Languages— An Overview —COMP 524: Programming Language ConceptsBjörn B. BrandenburgThe University of North Carolina at Chapel HillBased in part on slides and notes by S. Olivier, A. Block, N. Fisher, F. Hernandez-Campos, and D. Stotts.Tuesday, January 12, 2010
COMP 524: Programming Language Concepts02: Programming LanguagesA Brief History of Modern ComputingEarly computers required rewiring. For example, ENIAC (Electronic NumericalIntegrator and Computer, 1946)programed with patch cords. Reprogramming took weeks. Used to compute artillery tables.Von Neumann: stored program computers. Innovation: program is data. Program stored in core memory. Allowed for “rapid” reprogramming.Early programming. Programmers wrote bare machine code. Essentially, strings of zeros and ones. Created with punchcards.UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 2010Magnetic core memory. Each core is one bit.Source: Wikimedia CommonsCredit: H.J. Sommer III, Professor of MechanicalEngineering, Penn State University2
COMP 524: Programming Language Concepts02: Programming LanguagesMachine CodeA punch card.Source: Wikimedia CommonsLimitations. Hard for humans to read and write. Very error-prone. Slow development.UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 20103
COMP 524: Programming Language Concepts02: Programming LanguagesAssembly CodeIdea: use the computer to simplifyprogramming! Possible since programs are data. Computer transforms humanreadable input into machine code.First step: direct mapping. Use mnemonic abbreviations forinstructions.‣ One abbreviations for eachinstruction.‣Also encode operands. Computerassembles realprogram by mapping each lineto its machine code equivalent,thus creating a new program. Assemblers are still in use today.UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 20104
COMP 524: Programming Language Concepts02: Programming LanguagesAssembly CodeMachine CodeInstructionsOperandsIdea: use the computer toExample:simplifyIntel x86-32 machine code andprogramming!language of javac program. Possible sinceassemblyprogramsare data. Computer transforms humanreadable input into machine code.First step: direct mapping. Use mnemonic abbreviations forinstructions.‣ One abbreviations for eachinstruction.‣Also encode operands. Computerassembles realprogram by mapping each lineto its machine code equivalent,thus creating a new program. Assemblers are still in use today.UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 20105
COMP 524: Programming Language Concepts02: Programming LanguagesTowards Higher-Level LanguagesLimitations of assembly code. Still hard to read. No error checking. Machine specific, not portable.‣ Hardware architecture changedfrequently in the early days. Example:A macro with two parameters on Linux.Implements the write system call.macro write str, str sizemovl 4, %eaxmovl 1, %ebxmovl \str, %ecxmovl \str size, %edxint 0x80.endmTedious to write.‣ Macros somewhat alleviate this.Desired: higher-level representation. Machine independent. More like mathematical formulas.‣ Usable by scientists. Macro expansion:Programmer defines parametrizedabbreviation; assembler replaces eachoccurrence of abbreviation with definition.Catch common errors.UNC Chapel HillTuesday, January 12, 2010Subsequently, strings can be output withwrite address of string , length instead of the whole system call sequence.Brandenburg — Spring 2010Source: sm.html6
COMP 524: Programming Language Concepts02: Programming LanguagesHigh-Level LanguageKey properties. Provides facilities for data and control flow abstraction. Machine-independent specification. One high-level statement typically corresponds to many machineinstructions. Human-friendly syntax. Programming model / semantics not defined in terms of machinecapabilities.Translation to machine code. Checked and translated by compiler.‣ Alternatively, interpreted (next lecture). Initially, slower than handwritten assembly code.Today, compiler-generated code outperforms most human-writtenassembly code.UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 20107
COMP 524: Programming Language Concepts02: Programming LanguagesEarly High-Level LanguagesFORTRAN John Backus (IBM), 1954. Formula Translating System For numerical computing. Focus: efficiency.LISP John McCarthy (MIT), 1958. List Processor. For symbolic computing. Focus: abstraction.UNC Chapel HillTuesday, January 12, 2010ALGOL John Backus (IBM), Friedrich Bauer (TUMunich), etal., 1958. Algorithmic Language For specification of algorithms. Focus: clear and elegant design.COBOL Grace Hopper (US Navy), 1959. Common Business-Oriented Language. For data processing in businesses. Focus: english-like syntax.Brandenburg — Spring 20108
COMP 524: Programming Language Concepts02: Programming LanguagesEarly High-Level LanguagesALGOL was highly influential and (revised versions)were the de-facto standard for the description ofalgorithms for most of the 20th century.FORTRAN John Backus (IBM), 1954. Formula Translating System For numerical computing. Focus: efficiency.LISP John McCarthy (MIT), 1958. List Processor. For symbolic computing. Focus: abstraction.ALGOL John Backus (IBM), Friedrich Bauer (TUMunich), etal., 1958. Algorithmic Language For specification of algorithms. Focus: clear and elegant design.COBOL Grace Hopper (US Navy), 1959. Common Business-Oriented Language. For data processing in businesses. Focus: english-like syntax.FORTRAN, LISP, and COBOL are still in wide-spread use today!(in revised forms)UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 20109
COMP 524: Programming Language Concepts02: Programming LanguagesDefinitionWhat is a Programming Language? Java?Yes. HTML?No. Javascript?Yes. LaTeX?Yes.A programming language is a formal language thatis both universal (any computable function can be defined) implementable (on existing hardware platforms).Turing-complete: can simulate any Turing machine.(of course, real hardware has space constraints)UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 2010Illustration source: Wikimedia Commons10
COMP 524: Programming Language Concepts02: Programming LanguagesPractical LanguagesTo be of practical interest, a language should also:“Naturally” express algorithms. With respect to its intendedproblem domain. This is often achieved bymimicking existing notation oradopting core concepts (e.g.,function definitions, predicates). In essence, a language mustappeal to its intended users tobe successful.“do whatI mean”UNC Chapel HillTuesday, January 12, 2010Be efficiently implementable. Acceptable definitions of “efficient”vary by problem domain. For example, in high-performancecomputing, there is typically no“efficient enough.” In contrast, in work on artificialintelligence, efficiency was often onlya secondary concern in the past.Design TradeoffBrandenburg — Spring 2010“do exactlywhat I say”11
COMP 524: Programming Language Concepts02: Programming LanguagesProgramming Language SpectrumDeclarative LanguagesImperative Languagesfocus on what the computer should dofocus on how the computer should doFunctional(Ex: LISP/Scheme, ML, Haskell)Procedural / Von Neumann(Ex: Fortran, Pascal, C)Logic and constraint-based(Ex: Prolog)Object-Oriented(Ex: Smalltalk, Eiffel, C , Java)Dataflow(Ex: Id, Val)Scripting(Ex: Shell, TCL, Perl, Python)“do whatI mean”UNC Chapel HillTuesday, January 12, 2010“do exactlywhat I say”Brandenburg — Spring 201012
COMP 524: Programming Language Concepts02: Programming LanguagesProcedural Languagess:Programming Language SpectrumDirect evolution from assembly(and thus how computers work internally):a program is a sequential computation that directly manipulatessimple typed data (memory locations); abstraction is achieved bycalling subroutines as service providers.Declarative LanguagesImperative Languagesfocus on what the computer should dofocus on how the computer should do itFunctional(Ex: LISP/Scheme, ML, Haskell)Procedural / Von Neumann(Ex: Fortran, Pascal, C)Logic and constraint-based(Ex: Prolog)Object-Oriented(Ex: Smalltalk, Eiffel, C , Java)Dataflow(Ex: Id, Val)Scripting(Ex: Shell, TCL, Perl, Python)“do whatI mean”UNC Chapel HillTuesday, January 12, 2010“do exactlywhat I say”Brandenburg — Spring 201013
COMP 524: Programming Language Concepts02: Programming LanguagesProgramming Language SpectrumObject-Oriented Languages:Human-inspired model:problems are solved Imperative LanguagesDeclarativeLanguagesby awhatteam ofobjectsthat collaboratefocus onthecomputershould doby focus on how the computer should do itsending messages to each other.Objects represent“subcontractors” that doFunctionaljob (possibly withhelp of other(Ex: oneLISP/Scheme,ML, theHaskell)“experts”) and encapsulate all related state.The benefit of object-orientation is twofold:Logicthat andlarge,constraint-basedcomplex problems can be(Ex: Prolog)decomposedin a “natural” way; andmessage passing can be compiled intoefficient procedural code.Dataflow(Ex: Id, Val)Procedural / Von Neumann(Ex: Fortran, Pascal, C)Object-Oriented(Ex: Smalltalk, Eiffel, C , Java)Scripting(Ex: Shell, TCL, Perl, Python)“do whatI mean”UNC Chapel HillTuesday, January 12, 2010“do exactlywhat I say”Brandenburg — Spring 201014
COMP 524: Programming Language Concepts02: Programming LanguagesProgramming Language SpectrumFunctional Languages:Mathematics-inspired model: program defined interms of mathematical functions (equivalences).Declarative Languagesfocus on what the computer should doFunctional(Ex: LISP/Scheme, ML, Haskell)Logic and constraint-based(Ex: Prolog)ImperativeLanguagesThere is no conceptof memory:functionssimplythemapcomputervalues onto shouldother values.focuson howdo itThere is no concept of time:ProceduralVon Neumannmathematical/ functionsjust are;(Ex:isFortran,Pascal,C)thereno “before”and “after.”There is no concept of state:functions are only defined in terms of theirObject-Orientedarguments and other functions.(Ex: Smalltalk, Eiffel, C , Java)The computer’s job is to compute the result ofapplying the program (a function) to the input.Dataflow(Ex: Id, Val)ScriptingHow thisis donenot specifiedin the program.(Ex:Shell,isTCL,Perl, Python)Control flow is implicit and based on recursion.“do whatI mean”UNC Chapel HillTuesday, January 12, 2010“do exactlywhat I say”Brandenburg — Spring 201015
COMP 524: Programming Language Concepts02: Programming LanguagesProgramming Language SpectrumDeclarative LanguagesImperative Languagesfocus on what the computer should dofocus on how the computer should do itFunctional(Ex: LISP/Scheme, ML, Haskell)Procedural / Von Neumann(Ex: Fortran, Pascal, C)Logic Languages:Logic and constraint-based(Ex: Prolog)Inspired by propositional logic. Program isObject-Orienteddefined in terms of(Ex: Smalltalk, Eiffel, C , Java)facts (the “knowledge base”),Dataflow(Ex: Id, Val)“do whatI mean”UNC Chapel HillTuesday, January 12, 2010rules (implications,“if X then also Y”), and aScripting(Ex: Shell, TCL, Perl, Python)goal (query, “is Y true?”, “what makes Y true?”).The computer’s job is to construct a proofbased on the given axioms (facts rules).“do exactlywhat I say”Brandenburg — Spring 201016
COMP 524: Programming Language Concepts02: Programming LanguagesProgramming Language SpectrumDataflow Languages:Similar to gate earecomputerTokenson(unitsof data)streamedshouldthrough adoImperative Languagesfocus on how the computer should do itnetwork of primitive functional units.“Unix pipes loops multiple inputs / outputs.”Functional(Ex: LISP/Scheme, ML, Haskell)Procedural / Von Neumann(Ex: Fortran, Pascal, C)Logic and constraint-based(Ex: Prolog)Object-Oriented(Ex: Smalltalk, Eiffel, C , Java)Dataflow(Ex: Id, Val)Scripting(Ex: Shell, TCL, Perl, Python)“do whatI mean”UNC Chapel HillTuesday, January 12, 2010“do exactlywhat I say”Brandenburg — Spring 201017
COMP 524: Programming Language Concepts02: Programming LanguagesProgrammingLanguage SpectrumScripting Languages:Fuzzy category of high-level languagesthat focus heavily on developer productivity(“rapid development”).Declarative Languagesfocus on what the computer should doImperative Languagesfocus on how the computer should do itOften used for integration of components(“glue languages”), more recently for webFunctionalProcedural / Von Neumanndevelopment.(Ex: LISP/Scheme, ML, Haskell)(Ex: Fortran, Pascal, C)Traditionally imperative model, but thereis a trend to include object-oriented andfunctional design elements.Logic and constraint-based(Ex: Prolog)Object-Oriented(Ex: Smalltalk, Eiffel, C , Java)Dataflow(Ex: Id, Val)Scripting(Ex: Shell, TCL, Perl, Python)“do whatI mean”UNC Chapel HillTuesday, January 12, 2010“do exactlywhat I say”Brandenburg — Spring 201018
COMP 524: Programming Language Concepts02: Programming LanguagesProgramming Language SpectrumDeclarative LanguagesImperative Languagesfocus on what the computer should dofocus on how the computer should do itFunctional(Ex: LISP/Scheme, ML, Haskell)Procedural / Von Neumann(Ex: Fortran, Pascal, C)Logic and constraint-based(Ex: Prolog)Object-Oriented(Ex: Smalltalk, Eiffel, C , Java)Dataflow(Ex: Id, Val)Scripting(Ex: Shell, TCL, Perl, Python)Note: this is a very coarse-grained view. most real-world languages are not pure (i.e., they mix categories). there exist many sub-categories (e.g., synchronous reactive FP).UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 201019
COMP 524: Programming Language Concepts02: Programming LanguagesDesign ConsiderationsWhat are the primary use cases?Communicate ideas. Programs are read moreoften than written. Maintenance costs.ReadabilityExactly specify algorithms. Succinct and precise. No ambiguity.ExpressivityCreate useful programs. Development must beeconomically viable.UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 2010WritabilityReliability20
COMP 524: Programming Language Concepts02: Programming LanguagesReadability FactorsWhat does this code fragment do?Simplicity. Limited number of concepts / variants.Orthogonality. Are concepts independent of each other? Lack of special cases.Syntax design. Identifier restrictions (e.g., hyphen vs minus). Terseness; frequency of operator symbols.‣ For example, x vs. x.length().‣ But: x.add(y.times(z)) vs. x y z.Explicit constraints. Assumptions made explicit and checked. Enforced “design by contract.”UNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 2010Java: many ways to increment. x; x ; x x 1; x 1;Java:ArrayList int vs. ArrayList Integer Example: variable name for “globalinput database file”FORTRAN 77: GIDBFL (max 6 chars.)vs.LISP: *input-database-file*Eiffel keywords:invariant, require, ensure21
COMP 524: Programming Language Concepts02: Programming LanguagesEiffel: Checked Constraints Exampleindexing . classCOUNTERfeaturedecrement is-- Decrease counter by one.requireitem 0doitem : item - 1ensureitem old item - em 0endSource: http://archive.eiffel.com/eiffel/nutshell.htmlUNC Chapel HillTuesday, January 12, 2010Brandenburg — Spring 201022
COMP 524: Programming Language Concepts02: Programming LanguagesExample: ExpressivityQuicksort in Haskellqsort [] qsort (x:xs) wherelt xge x[]qsort lt x [x] qsort ge x [y y - xs, y x] [y y - xs, y x]Quicksort in Cqsort( a, lo, hi ) int a[], hi, lo;{int h, w, p, t;if (lo hi) {w lo;h hi;p a[hi];do {while ((w h) && (a[w] p))w w 1;while ((h w) && (a[h] p))h h-1;if (w h) {t a[w];a[w] a[h];a[h] t;}} while (w h);t a[w];a[w] a[hi];a[hi] t;(we will discuss Haskell indetail later in the semester)UNC Chapel HillTuesday, January 12, 2010}Brandenburg — Spring 2010}qsort( a, lo, w-1 );qsort( a, w 1, hi );23
COMP 524: Programming Language Concepts02: Programming LanguagesExample: ExpressivityQuicksort in Haskellqsort [] qsort (x:xs) wherelt xge x[]qsort lt x [x] qsort ge x [y y - xs, y x] [y y - xs, y x]For any ordereddatatype.Quicksort in Cqsort( a, lo, hi ) int a[], hi, lo;{int h, w, p, t;if (lo hi) {w lo;h hi;p a[hi];do {while ((w h) && (a[w] p))w w 1;while ((h w) && (a[h] p))h h-1;if (w h) {t a[w];a[w] a[h];a[h] t;}} while (w h);Only for int.(we will discuss Haskell indetail later in the semester)UNC Chapel HillTuesday, January 12, 2010t a[w];a[w] a[hi];a[hi] t;}Brandenburg — Spring 2010}qsort( a, lo, w-1 );qsort( a, w 1, hi );24
COMP 524: Programming Language Concepts02: Programming LanguagesWritability FactorsFacilities for abstraction Define each concept only once.Haskell: allows numeric integration tobe defined once for any functionRepetition avoidance. DRY principle: “donʼt repeat yourself” Code generation. Generic programming. Sparse type declarations, type inference.Ruby: The “Ruby on Rails” webframework drastically reduced the needfor configuration files.D: designed as a C successor, it hasbeen hindered by the existence ofincompatible compilers and libraries.Quality of development tools. Efficiency of compiler-generated code. Availability of libraries. Leniency of compiler / language system. Turnaround time of edit-compile-test cycle. Number of available compiler / tool chains.Documentation. Availability and quality.UNC Chapel HillTuesday, January 12, 2010gcc: some warnings not used in Linuxdue to excessive false positives.Java: javadoc support ensuresstandardized, indexable documentation.Brandenburg — Spring 201025
COMP 524: Programming Language Concepts02: Programming LanguagesReliability FactorsStatic error detection. Type checking. Constraint checking. Model-driven development. Model extraction.Example: detect use of uninitialized variables.Model-checking is a technique to automaticallyprove safety and liveness properties.Dynamic error detection. Array bounds checking. Integer overflow detection.C: lack of run-time checking has caused billionsin damages due to security incidences.Ease of error handling. Structured exception handling. Error propagation.In Erlang, processes can be linked: if one fails,then all linked processes are also terminated.This prevents “half-dead” systems.Versioning of components. Avoid mismatch in assumptions.Example: detect when interface has changed.Ease of testing. Unit testing support. Test case generation.UNC Chapel HillTuesday, January 12, 2010Haskell: the QuickCheck library aids debuggingby automatically generating counter examples toinvariants based on type signatures.Brandenburg — Spring 201026
COMP 524: Programming Language Concepts02: Programming LanguagesLanguage Design TradeoffprogramsafetydeveloperproductivityUNC Chapel HillTuesday, January 12, 2010programefficiencyBrandenburg — Spring 201027
COMP 524: Programming Language Concepts02: Programming LanguagesSummaryHistory. Programming language development started with a desire forhigher levels of abstraction. Compiling very high levels of abstraction into efficientmachine code is challenging.Programming Language Spectrum. Language design involves many tradeoffs. The result: many competing languages, all slightly different. Often variations on a theme.Categories. Declarative: what to do.‣ Functional, logic-based, dataflow. UNC Chapel HillTuesday, January 12, 2010Imperative: how to do it.‣ Procedural, object-oriented, scripting.Brandenburg — Spring 201028
02: Programming Languages COMP 524: Programming Language Concepts Assembly Code 4 Idea: use the computer to simplify programming! Possible since programs are data. Computer transforms human-readable input into machine code. First step: direct mapping. Use mnemonic abbreviations for instructions. ‣ One abbreviations for each instruction.
