| Term | Definition |
| Reasons for Studying Concepts of Programming Languages | -Increased ability to express ideas
-Improved background for choosing appropriate languages
-Increased ability to learn new languages
-Better understanding of significance of implementation |
| Programming Domains | -Scientific applications
-Business applications
-Artificial Intelligence
- Systems programming
-Web Software
-Mobile Devices
-Real Time
-Concurrent |
| Language Evaluation Criteria | -Readability: the ease with which programs can be read and understood
-Writability: the ease with which a language can be used to create programs
-Reliability: conformance to specifications
-Cost: the ultimate total cost |
| Evaluation Criteria: Readability | -Overall simplicity
-Orthogonality
-Data types
-Syntax considerations |
| Evaluation Criteria: Writability | -Simplicity and orthogonality
-Support for abstraction
-Expressivity |
| Evaluation Criteria: Reliability | -Type checking
-Exception handling
-Aliasing
-Readability and writability |
| Evaluation Criteria: Cost | -Training programmers to use the language
-Writing programs
-Compiling programs
-Executing programs
-Language implementation system: availability of free compilers
-Reliability: poor reliability leads to high costs
-Maintaining programs |
| Evaluation Criteria: Others | -Portability
-Generality
-Well-definedness |
| Von Neumann Architecture Influence | Imperative languages are most dominant
- variables model memory cells
- assignments model piping
- iteration is efficient |
| Von Neumann Computers | - data and programs stored in memory
- memory is separate from CPU
- instructions are piped in from memory to CPU |
| 1950s and early 1960s Programming Methodologies | simple applications and worry about machine efficiency |
| Late 1960s Programming Methodologies | people efficiency became important; readability, better control structures
-structured programming
-top-down design and step-wise refinement |
| Reasons for Studying Concepts of Programming Languages pt 2 | -Better use of languages that are already known
-Overall advancement of computing
-Increased Job prospects |
| Late 1970s Programming Methodologies | Process-oriented to data-oriented
-data abstraction |
| Middle 1980s Programming Methodologies | Object-oriented programming
-Data abstraction + inheritance + polymorphism |
| Imperative Language Category | -features: variables, assignment statements, and iteration
-include languages that support object-oriented programming
-C, java, perl, javascript, Visual BASIC, .NET, C++ |
| Functional Language Category | -main means of making comparisons is by applying functions to given parameters
-LISP, Scheme, ML, F# |
| Logic Language Category | -rule-based
- prolog |
| Markup/programming hybrid | -markup languages extended to support some programming
-JSTL, SXLT |
| Language Design Trade-Offs | -Reliability vs. cost of execution
-Readability vs. writability
-Writability vs. reliability |
| Compilation Implementation Method | -Programs are translated into machine language; includes JIT systems
-Faster and code can be optimized
-Only translates once
-Use: Large commercial applications |
| Pure Interpretation Implementation Method | -Programs are interpreted by another program known as an interpreter
-Nicer to develop (REPL)
-Use: Small programs or when efficiency is not an issue |
| Hybrid Implementation Method | -A compromise between compilers and pure interpreters
-Use: Small and medium systems when efficiency is not the first concern
-Java |
| Von Neumann Bottleneck | -Connection speed between a computer’s memory and its processor determines the speed of a computer
-Program instructions often can be executed much faster than the speed of the connection
-The primary limiting factor in the speed of computers |
| What is a PL? | syntax: grammatical rules
semantics: meaning
natural languages are enormous and imprecise and ambiguous |
| PL Generations | 1st: machine instructions (binary)
2nd: assembly languages (not portable & low level)
3rd: high level languages
4th: code generators
5th: prolog? |
| Abstractions on PLs | -data
-control
-process |
| Programs | data structures + algorithms = programs |
| Zuse's Plankalkul | -Designed in 1945 but not published until 1972
-Never implemented
-Advanced data structures (floating point, arrays, records)
- invariants
-Designed by Konrad Zuse |
| Issues with using machine code | -Poor readability
-Poor modifiability
-Expression coding was tedious
-Machine deficiencies--no indexing or floating point |
| Short Code | -developed by John Mauchly in 1949
-developed for the BINAC computer
- expression were coded L->R
-was implemented with a pure interpreter |
| Speedcoding | -developed by John Backus in 1954
- developer for the IBM 701
-pseudo ops for arithmetic and math functions
-conditional and unconditional branching
-Auto-increment register for array access
-Slow! |
| UNIVAC Compiling System | -developed between 1951 and 1953 by a team led by Grace Hopper
- expanded a pseudo code into machine code subprograms |
| Fortran | -Designed for the IBM 704, which had index registers and floating point hardware
- Fortran I was developed in 1957
- Developed by John Backus
-Fortran II was distributed in 1958
-Changed forever the way computers are used
-Was developed for scientifi |
| LISP | -Designed by John McCarthy in 1958
-AI research needed a language to process data in lists and symbolic computation
-syntax is based on lambda calculus
-pioneered functional programming
-still the dominant language for AI |
| Scheme | -Developed at MIT in the mid 1970s
-small
-extensive use of static scoping
-functions as first class entities
-well suited to educational applications
-functional programming language |
| Common Lisp | -an effort to combine features of several dialects of Lisp into a single language
-large and complex language |
| ALGOL 60 | -result of efforts to design a universal language
-ACM and GAMM met for four days in 1958
-was the standard way to publish algorithms for over 20 years
-all subsequent imperative languages are based on it
-first machine-independent language
-lacked I |
| ALGOL 60 pt 2 | -first language whose syntax was formally defined (BNF)
-never widely used
-lacked I/O
-lack of support from IBM |
| COBOL | -computerizing business records
-based on FLOW-MATIC
-first design meeting (Pentagon) May 1959
-nested selection statements
-still the most widely used business application language
-first language required by the DoD |
| Basic | -designed by Kemeny & Kurtz at Dartmouth in 1971
-Easy to learn and user for non-science students
-current popular dialect: Visual Basic
-first widely used language with time sharing |
| PL/I | -designed by IBM and Share in 1964
-originally was named a new programming language
-built to do both scientific and business applications
-too large and too complex
-first pointer data type
- |
| APL | -a programming language
-designed by Ken Iverson at IBM in 1960
-highly expressive
-programs are difficult to read |
| SNOBOL | -designed as a string manipulation language
-Designed at Bell Labs by Farber, Griswold, and Polensky in 1964
- powerful operators for string pattern matching
-still used for certain text processing tasks |
| SIMULA 67 | -Designed for system simulation in Norway by Nygaard and Dahl
-based on ALGOL 60 and SIMULA 1
-Coroutines
-classes, objects, and inheritance |
| ALGOL 68 | -user-defined data structures
-reference types
-dynamic arrays
-less usage than AGLOL 60 |
| Pascal | -developed in 1971 by Niklaus Wirth
-designed for teaching structured programming
-small and simple
-largest impact was on teaching programming |
| C | -designed for systems programming at Bell Labs by Dennis Richie in 1972
-powerful set of operators, but poor type checking
-designed as a systems language
-used in many application areas
-initially spread through UNIX |
| Prolog | -developed by Comerauer and Rousesel
-early 1970s
-based on formal logic
-non-procedural
-comparitively inefficient
-few application areas |
| Ada | -huge design effort and took about 8 years
-Sequence of requirements (1975-1978)
-Named Ada after Augusta Ada Byron, the first programmer
-exception handling
-concurrency
-generic program units
--packages |
| Ada 95 | -began in 1988
-support for OOP
-new concurrency features |
| Ada 2005 | -interfaces and synchronizing interfaces
-popularity suffered because the DoD no longer requires its uses but also because of the popularity of C++ |
| Smalltalk | -developed at Xerox PARC by Alan Kay and Adele Goldberg
-first full object-oriented language
-pioneered the graphical user interface design
-promoted oop |
| C++ | -developed at Bell Lab by Bjarne Stroustrup at Bell Labs in 1980
-evolved from C and SIMULA 67
-supports both procedural and OOP
-rapidly grew in popularity
-ANSI standard approved in November 1997 |
| Objective-C | -designed by Brad Cox early 1980s
-used by apple for systems programs
-uses smalltalk's method for calling syntax |
| Java | -imperative- based OOP language
-developed at Sun in the early 1990s
-based on c++
-supports only OOP
-has references, but not pointers
-supports concurrency
-portable (JVM)
-widely used for web programming
-use increased faster than any prev lang |
| Perl | -designed by Larry Wall in 1987
-scripting language
-variables are statically typed but implicitly declared
-powerful and somewhat dangerous
-replacement for UNIX system administration language |
| JavaScript | -Began at Netscape
-client-side HTML embedded scripting language
purely interpreted
-related to Java only through syntax |
| PHP | -hypertext preprocessor
-designed by Rasmus Lerdorf
-purely interpreted |
| Python | - oo interpreted scripting language
- dynamically typed
-type checked
-supports lists, tuples, and hashed |
| Ruby | -designed in Japan by Yukihiro Matsumoto (Matz)
-began as a replacement for Perl and Python
-a pure object-oriented scripting language
-purely interpreted |
| Lua | -an oo interpreted scripting language
-type checked but dynamically typed
-easily extendable
-supports lists, tuples, and hashes all with its single data structure, the table |
| C# | -Part of the .NET development platform (2000)
-based on C++, Java and Delphi
-include pointers, delegates, properties, enumeration times, a limited kind of dynamic typing, and anonymous types
-is evolving rapidly |
| XSLT | -eXtensible markup language (XML)
-eXtensible Stylesheet Language Transformation
-programming constructs
-hybrid language |
| JSP | -java server pages: collection of technologies to support dynamic Web Documents
-JSTL, a JSP library, include programming constructs in the form of HTML elements |
| syntax | the form or structure of the expression, statements, and program units (grammar) |
| semantics | the meaning of the expressions, statements, and program units |
| Language definition | provided by the syntax and semantics of a language |
| sentence | a string of characters over some alphabet |
| language | a set of sentences |
| lexeme | the lowest level syntactic unit of a language (*, sum, begin) |
| token | is a category of lexemes (identifier) |
| recognizer | a recognition device that reads input strings over the alphabet of the language and decides whether the input strings belong to the language |
| generators | -a device that generates sentences of a language
-one can determine if the syntax of a particular sentence is syntactically correct by comparing it to the structure of the generator |
| context-free grammars | -developed by Noam Chomsky in the mid-1950s
-language generators, meant to describe the syntax of natural languages
-define a class of languages called context-free languages |
| Backus-Naur Form | -invented by John Backus to describe the syntax of Algol 58
-BNF is equivalent to context-free grammars
-developed in 1959 |
| BNF Fundamentals | -abstractions are used to represent classes of syntactic structures
-terminals are lexemes or tokens
-LHS (nonterminal) and RHS (string of terminals and/or nonterminals)
-nonterminals are enclosed in angle brackets < > |
| Grammar | a finite non-empty set of rules |
| Start symbol | a special element of the nonterminals of a grammar |
| BNF Rules | -an abstraction (nonterminal) can have more than one RHS |
| Describing Lists BNF | -syntactic lists are described using recursion
<ident_list> -> ident | ident, <ident_list> |
| derivation | a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols) |
| Example BNF Grammar | <program> -> <stmts>
<stmts> -> <stmt> | <stmt> ; <stmts>
<stmt> -> <var> = <expr>
<var> -> a | b | c | d
<expr> -> <term> + <term> | <term> - <term>
<term> -> <var> | const |
| Example BNF Derivation | <program> => <stmts> => <stmt>
=> <var> = <expr>
=> a = <expr>
=> a = <term> + <term>
=> a = <var> + <term>
=> a = b + <term>
=> a = b + const |
| derivations | -every string of symbols in a derivation is a sentential form
-a sentence is a sentential form that only has terminal symbols
-can be leftmost or rightmost |
| left-most derivation | a derivation in which the left-most nonterminal in each sentential form is the one that is expanded |
| ambiguous grammar | if an only if it generates a sential form that has two or more distinct parse trees |
| precedence levels | must be unambiguous expression grammar |
| Extended BNF (EBNF) | -optional parts are places in brackets [ ]
-alternative parts of RHSs are placed inside parentheses and separated via vertical bars
-Repetitions (0 or more) are placed inside braces {} |
| Context-sensitive syntax | -static semantics (scope rules: must declare id prior to referencing)
-attribute grammars: associate attribute values with symbols |
| Operational Semantics | define semantics in terms of effect on state of simple virtual machine |
| Axiomatic semantics | goal of proving program correctness, impose constraints called preconditions and postconditions |
| denotation semantics | formal approach based on recursive function theory |
| Theory of computation | -computability
-complexity |
| P | polynomial time |
| NP | nodeterministic solution in polynomial time |
| Formal Language Theory (Syntax) | Chomsky Hierarchy
-type 3: regular languages (finite automata)
-type 2: context free languages (pushdown automata)
-type 1: context sensitive languages (linear bounded automata)
-type 0: recursively enumerable languages (Turing machines) |
| non determinism | the ability to "guess" correct alternative |
| close relation between generators and recognizers | generators: production rules
recognizers: automata |
| In E(BNF) you can produce a recognizer from a generator | |
| lexical analysis (tokenizing) | -break stream of characters into toxens (lexemes)
-pattern matching |
| syntax analysis (parsing) | check syntax and build a parse tree |
| parse tree | can parse top-down or bottom-up |
| concurrency can occur at four levels | -machine instruction level
-high-level language statement level
-unit level
-program level |
| Late 1950s multiprocessor architectures | one general purpose processor and one or more special purpose processors for input and output operations |
| Early 1960s multiprocessor architectures | multiple complete processors, used for program-level concurrency |
| Mid 1960s multiprocessor architectures | multiple partial processors, used for instruction level concurrency |
| Flynn's Taxonomy | SISD: single instruction, single data
SIMD: single instruction, multiple data
MISD: multiple instructions, single data
MIMD: multiple instructions, multiple data |
| Categories of Concurrency | -physical concurrency
- logical concurrency |
| Physical Concurrency | Multiple independent processors (multiple threads of control) |
| Logical Concurrency | The appearance of physical concurrency is presented by time-sharing one processor (software can be designed as if there were multiple threads of control) |
| Coroutines (quasi-concurrency) | have a single thread of control |
| thread of control | the sequence of program points reached as control flows through the program |
| Concurrency vs. Parallelism | -concurrency >= 1 CPU
-parallelism > 1 CPU |
| multithreading | > 1 thread |
| concurrent units | coroutines, tasks |
| task/process/thread | a program unit that can be in concurrent execution with other program units |
| heavyweight tasks | execute in their own address space |
| lightweight tasks | run in the same address space
more efficient |
| disjoint task | does not communicate with or affect the execution of any other task in the program in any way |
| Task Synchronization | a mechanism that controls the order in which tasks execute |
| Task communication is necessary for synchornization | -shared nonlocal variables
-parameters
-message passing |
| cooperation synchronization | task A must wait for task B to complete some specific activity before task A can continue its execution (producer-consumer problem) |
| competition | two or more tasks must use the same resource that cannot be simultaneously used (a shared counter)
-usually provided by mutually exclusive access |
| Major issues | -communication between tasks (message passing, lock on nonlocal variables)
-synchronization (cooperative, competitive) |
