Programming Languages Big Review

Six reasons to study programming language concepts

Increased ability to express ideas; improved background for choosing appropriate languages; increased ability to learn new languages; better understanding of the significance of implementation; better use of languages already known; overall advancement of computing.

Scientific domain needs and representative language

Large numbers of floating-point computations, arrays | Fortran

Business domain needs and representative language

Reports, decimal numbers, characters | COBOL

Artificial Intelligence domain needs and representative language

Symbols rather than numbers, linked lists | LISP

Systems domain needs and representative language

Efficiency, because of continuous use | C

Web software domain needs and representative language

Eclectic mix: markup, scripting, general purpose | HTML, PHP, Java

The four principal language evaluation criteria

Readability, writability, reliability, cost

Readability factors

Overall simplicity (manageable feature set, minimal feature multiplicity, minimal operator overloading), orthogonality, data types, syntax considerations

Writability factors

Simplicity and orthogonality, support for abstraction, expressivity

Reliability factors

Type checking, exception handling, aliasing, readability and writability

Cost factors

Training programmers, writing programs, executing programs, reliability, maintaining programs

Von Neumann Architecture

Data and programs stored in memory, memory separate from CPU, instructions and data piped from memory to CPU

Von Neumann Bottleneck

The memory-processor connection speed is the primary limiting factor in computer speed

Fetch-execute cycle

Initialize the program counter, then repeat forever: fetch instruction pointed by counter, increment counter, decode instruction, execute instruction

Four language categories

Imperative, Functional, Logic, Markup/programming hybrid

Reliability vs. Cost of Execution trade-off

Example: Java array bounds checks raise execution cost to improve reliability

Readability vs. Writability trade-off

Example: APL's powerful operators and new symbols are compact but hard to read

Writability/Flexibility vs. Reliability trade-off

Example: C++ pointers are powerful and flexible but unreliable

Compilation phases (in order)

Lexical analysis (characters to lexical units), syntax analysis (lexical units to parse trees), semantic analysis (generate intermediate code), code generation (machine code)

Pure interpretation characteristics

No translation; easier implementation; 10 to 100 times slower than compiled programs; made a comeback with web scripting languages (JavaScript, PHP)

Hybrid implementation systems

Translate to an intermediate language that allows easy interpretation; faster than pure interpretation (e.g., Java byte code + JVM)

JIT (Just-in-Time) compilers

Translate to intermediate language, then compile subprograms into machine code when called; machine code kept for subsequent calls (delayed compilers)

Preprocessors

Process a program immediately before compilation to expand embedded macros (e.g., C preprocessor expands #include, #define)

Fortran I (1957) characteristics

First compiled high-level language; designed for IBM 704; scientific applications; machine efficiency most important; no dynamic storage

LISP characteristics

Designed by McCarthy for AI; data in lists rather than arrays; symbolic computation; atoms and lists; syntax based on lambda calculus

ALGOL 60 contributions

Block structure (local scope), two parameter-passing methods, subprogram recursion, stack-dynamic arrays; first machine-independent language; first language whose syntax was formally defined (BNF)

COBOL contributions

First macro facility in a high-level language, hierarchical data structures (records), nested selection, long names, separate data division

SIMULA 67 contributions

Designed for simulation based on ALGOL 60; introduced coroutines, classes, objects, and inheritance

Pascal (1971)

Designed by Wirth for teaching structured programming; small, simple; most widely used teaching language from mid-1970s to late 1990s

C (1972)

Developed by Dennis Ritchie at Bell Labs for systems programming; evolved from B, BCPL, and ALGOL 68; powerful operators, poor type checking; spread through UNIX

Smalltalk

Developed at Xerox PARC by Alan Kay; first full implementation of an object-oriented language (data abstraction, inheritance, dynamic binding); pioneered the GUI

C++ (1980)

Developed by Stroustrup; evolved from C and SIMULA 67; supports both procedural and object-oriented programming

Java (Early 1990s)

Developed by Sun for embedded devices; simplified C++ (no pointer arithmetic, references instead of pointers); portable via JVM and JIT

Prolog

Logic programming language based on formal logic; non-procedural; an intelligent database system that uses an inferencing process to query facts/rules

Ada

History's largest design effort; contributions include packages (data abstraction), exception handling, generic units, and concurrency tasking model

Syntax vs. Semantics

Syntax is the form or structure of expressions, statements, and program units; semantics is their meaning

Lexeme vs. Token

A lexeme is the lowest level syntactic unit of a language (e.g., sum, begin); a token is a category of lexemes (e.g., IDENT)

Recognizers vs. Generators

Recognizers read input strings and decide if they belong to a language (parsers); generators generate sentences of a language (grammars)

Backus-Naur Form (BNF)

Invented by John Backus to describe syntax of Algol 58; equivalent to context-free grammars; uses nonterminals and terminals with rules (LHS -> RHS)

Derivation & Sentential Form

A derivation is a repeated application of rules starting from the start symbol; every string of symbols in a derivation is a sentential form

Parse Tree

A hierarchical representation of a derivation

Grammar Ambiguity

A grammar is ambiguous if it generates a sentential form that has two or more distinct parse trees (fixed by encoding precedence and associativity)

EBNF Extensions

Brackets [ ] for optional parts, parentheses ( ) with vertical bars for alternatives, braces { } for repetitions (0 or more)

Attribute Grammar

A context-free grammar with added attribute values and evaluation functions/predicates; used for static semantics specification and compiler error checking

Synthesized vs. Inherited Attributes

Synthesized attributes are computed from child nodes (bottom-up); inherited attributes are computed from parent/sibling nodes (top-down)

Operational Semantics

Describes meaning by executing statements on a machine (simulated or actual); the change in the state of the machine defines the meaning

Denotational Semantics

Based on recursive function theory; defines mathematical objects for each language entity and functions mapping entities to those objects

Axiomatic Semantics

Based on formal logic (predicate calculus) and assertions ({P} statement {Q}); used for program verification and weakest preconditions

Weakest Precondition

The least restrictive precondition that guarantees the postcondition after a statement executes

Loop Invariant

A condition that is true before and after each iteration of a loop, used in axiomatic semantics to prove loop correctness

Lexical Analyzer (Lexer)

Low-level component based on a regular grammar / finite automaton; groups characters into lexemes and assigns tokens

Parser (Syntax Analyzer)

High-level component based on a context-free grammar / push-down automaton; builds parse trees and checks syntax

Top-Down Parsing

Builds parse tree from root down (leftmost derivation); examples include recursive-descent and LL parsers

Bottom-Up Parsing

Builds parse tree from leaves up (reverse of rightmost derivation); examples include LR parsers using handle pruning and shift-reduce

LL Grammar Disqualifiers

Left recursion and lack of pairwise disjointness (multiple RHSs sharing a FIRST set)

Handle

In bottom-up parsing, the specific right-hand side of a rule that matches the current sentential form and should be reduced next (leftmost simple phrase)

LR Parser Actions

Shift, Reduce, Accept, Error (driven by ACTION and GOTO tables)

PHP Characteristics

Weakly typed, interpreted server-side scripting language; C++-ish syntax; case-sensitive; uses $ for variables

PHP == vs ===

== checks value equality; === checks identical value and type (or same object in OOP)

PHP Prepared Statements

Used in database queries (e.g., prepare, bind_param, execute) to prevent SQL injection ("Bobby tables")

PHP require vs include

Both import code from another file; require halts execution with a fatal error if the file is missing, while include issues a warning and continues