CS 345 slide 1 Spring 200518 January 2005CS 345: Programming LanguagesCourse ObjectivesAfter completing this course you should be able todemonstrate your understanding of a number ofimportant programming-language concepts by• predicting the results of programs that use them• developing small programs or program fragmentsthat make essential use of them• explaining how they are typically implementedThis course…• is not a “grand tour” of programming languages.• is not intended to provide expertise in any specificlanguage• is a survey of programming-language concepts,using portions of numerous programminglanguages to illustrate them.The Goal:To help you become a sophisticated “consumer” ofprogramming languages, able to understand theirstrengths and limitations and why they have them.E.W. Dijkstra: “A Programming Language is a toolthat has profound influence on our thinkinghabits.”The Organizing Theme: Problems and Solutions• Each programming-language concept and featureis intended as a solution of some computation-specification problem.• We try to identify the purpose behind theconcepts and features that we examine.CS 345 slide 2 Spring 200518 January 2005What is a programming language?• a formal notation for specifying computations•“notation” vs. “language”Two views of what programs are for:• original view: The purpose of software is tocontrol computers• modern view: The purpose of software is tospecify computations (and the purpose ofcomputers is to execute the software). Aprogram’s most important audience is notmachines but people.Why are there so many programming languages?• many different machines (old view)• many different applications• need for better tools (yielding software that’smore trustworthy, faster, and less expensive)How should programming languages be judged?Some criteria:0. extent of support for program correctness1. cost of program development and modification2. cost of program use (time, space)Total cost: always some combination of 1 and 2. there’s a trade-off: cost vs. speedCS 345 slide 3 Spring 200518 January 2005Early programming languages0. machine languages (1940’s) andassembly languages (1950’s)• machine–specific (nonportable)• verbose• modularity: zero1.FORTRAN, COBOL, ALGOL (1960’S)—the first “high-level”languages— brought improved• portability (reusability)• redundancy ( consistency checks)• conciseness, readability• modularity (subroutines, procedures)The transition 01 brought about• small increase in the cost of use as softwarebecame slightly bigger and slower• large reduction in the cost of development(reportedly a factor of 10) as software becamemuch cheaper, more portable, and more reliable.For most purposes, level–1 (“higher-level”) languageshave replaced level–0 languages.The quest for another similar increase in program-mer productivity continues to this day— so far, withno clear success (although industrial use of Erlang isdelivering 4 improvements over C++/Java).CS 345 slide 4 Spring 200518 January 2005Programming paradigmsMost programming languages belong to one of twodistinct paradigms:• Imperative: focus on machine, execution viastate changes (bottom-up, original-view)Central operation: assignmentExamples: FORTRAN, COBOL, ALGOL–60Variations and extensions:  structured control: Pascal, C  concurrency : Ada  encapsulation (ADTs): Modula–2, C++  object-orientation: C++, Smalltalk, Java• Declarative: focus on computation in theabstract (top-down, modern-view)Functional: execution via evaluationCentral operation: function applicationVariations:  “eager” evaluation (impure):ML, Scheme, Erlang  “lazy” evaluation (pure):Miranda, HaskellLogic: execution via deductionCentral operation: unificationExample: PrologCS 345 slide 5 Spring 200518 January 2005A transportation analogy:assembler spelunkingC hikingC++ driving a carJava riding the busHaskell flyingEach has its uses— there are places you can’t get toexcept by spelunking, etc.This course spends a lot of time on Haskell— why?• Haskell is our representative of the functionalparadigm.• Most students are already familiar with theimperative paradigm• To understand a new paradigm, you can’t justlearn a few facts— you must learn enough of alanguage to write real programs in it.• In many ways —especially its type system—Haskell is a state-of-the-art language regardless ofparadigm; some of its features are beginning to becopied in more conventional languages.According to The Pragmatic Programmers’ Languageof the Year Project (2002)http://www.pragmaticprogrammer.com/loty,“This year’s language is Haskell. We’ve chosen Haskellbecause it’s a popular functional programminglanguage, and we’re interested in learning more aboutthe functional programming paradigm.”CS 345 slide 6 Spring 200518 January 2005Programming’s biggest problem:Unmastered ComplexityThe sheer scale of digital computations—• megabits of information• millions of operations per second— requires us to focus our small brainson one part at a time.A programming language helps if … it is as small and simple as possible (but nosimpler)• it suppresses unnecessary detail• it consists of a few parts that fit together insimple ways it supports modularization• programs are readily built up from separatesubprograms (modules)• modules’ interfaces are clear and simple it supports sharing and reuse of program partsCS 345 slide 7 Spring 200518 January 2005Modularity and StructureStructure: the relationship between the whole and theparts.A time-honored technique for solving complexproblems:divide and conquer:0. divide the problem into (easier) subproblems1. solve each subproblem separately2. combine the separate solutions (modules)The source of divide-and-conquer’s power isrecursivity i.e., the same technique can be applied to eachsubproblem.Among the most significant advances in program-ming languages are discoveries of new ways… • to decompose (divide) problems • to combine solutionsCS 345 slide 8 Spring 200518 January 2005Problem decompositions are seldom unique.Example problem:To output the elements of a list that occur more thanonce — i.e., the list’s duplicates.1. functional decompositiona. sort the listb. in the sorted list, find adjacent duplicates sortfindAdjacentDuplicateslistsortedlistduplicatesduplicates =