JD

Chapter 1 Key Vocabulary (Concepts of Programming Languages)

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

  • Better use of languages that are already known

  • Overall advancement of computing

Programming Domains

  • Scientific applications: large numbers of floating point computations; use of arrays; language example: Fortran

  • Business applications: produce reports, use decimal numbers and characters; language example: COBOL

  • Artificial intelligence: symbols rather than numbers manipulated; use of linked lists; language example: LISP

  • Systems programming: need efficiency because of continuous use; language example: C

  • Web software: eclectic collection of languages: markup (e.g., HTML), scripting (e.g., PHP), general-purpose (e.g., Java)

Language Evaluation Criteria

  • Readability: ease with which programs can be read and understood

  • Writability: ease with which a language can be used to create programs

  • Reliability: conformance to specifications (i.e., performs to its specifications)

  • Cost: the ultimate total cost

Evaluation Criteria: Readability

  • Overall simplicity: manageable set of features and constructs; minimal feature multiplicity; minimal operator overloading

  • Orthogonality: relatively small set of primitive constructs can be combined in a small number of ways; every possible combination is legal

  • Data types: adequate predefined data types

  • Syntax considerations: identifier forms, flexible composition; methods of forming compound statements; form and meaning: self-descriptive constructs, meaningful keywords

Evaluation Criteria: Writability

  • Simplicity and orthogonality: few constructs, small number of primitives, small set of rules for combining them

  • Support for abstraction: ability to define and use complex structures or operations while hiding details

  • Expressivity: set of relatively convenient ways of specifying operations; strength and number of operators and predefined functions

Evaluation Criteria: Reliability

  • Type checking: testing for type errors

  • Exception handling: intercept run-time errors and take corrective measures

  • Aliasing: presence of two or more distinct referencing methods for the same memory location

  • Readability and writability: a language that does not support natural ways of expressing an algorithm may require unnatural approaches, reducing reliability

Evaluation Criteria: Cost

  • Training programmers to use the language

  • Writing programs (closeness to particular applications)

  • Executing programs

  • Reliability: poor reliability leads to high costs

  • Maintaining programs

Evaluation Criteria: Others

  • Portability: ease of moving programs from one implementation to another

  • Generality: applicability to a wide range of applications

  • Well-definedness: completeness and precision of the language’s official definition

Influences on Language Design

  • Computer Architecture: languages developed around the prevalent computer architecture (von Neumann architecture)

  • Program Design Methodologies: new software development methodologies (e.g., object-oriented software development) lead to new programming paradigms and languages

Computer Architecture Influence

  • Well-known architecture: Von Neumann

  • Imperative languages dominate due to von Neumann computers:

    • Data and programs stored in memory

    • Memory is separate from CPU

    • Instructions and data are piped from memory to CPU

    • Basis for imperative languages

  • Variables model memory cells

  • Assignment statements model piping

  • Iteration is efficient

The Von Neumann Architecture

  • Components often highlighted: Memory (stores both instructions and data), Instructions and data, Arithmetic and logic unit (ALU), Control unit, Input and output devices, Central processing unit (CPU)

  • Fetch-execute-cycle (on a von Neumann architecture computer): initialize the program counter; repeat forever: fetch the instruction pointed by the counter; increment the counter; decode the instruction; execute the instruction; end repeat

ext{Fetch-execute-cycle}:
\; \text{PC} \leftarrow \text{PC} + 1,\; \text{instruction} \leftarrow \text{Memory}[\text{PC}],\; \text{decode}(\text{instruction}),\; \text{execute}(\text{instruction})\; \text{repeat}.

The von Neumann Architecture (Diagram Description)

  • Memory stores both instructions and data

  • Instructions and data reside in memory

  • Arithmetic and logic unit (ALU) performs computations

  • Control unit coordinates operations

  • I/O devices handle input/output

  • Central processing unit (CPU) orchestrates all components

The von Neumann Bottleneck

  • The connection speed between memory and processor determines computer speed

  • Program instructions can be executed faster than memory access bandwidth

  • The memory–CPU connection bottleneck limits overall system throughput

Programming Methodologies Influences

  • 1950s and early 1960s: simple applications; focus on machine efficiency

  • Late 1960s: emphasis on human efficiency; readability and better control structures; structured programming; top-down design and step-wise refinement

  • Late 1970s: shift from process-oriented to data-oriented; data abstraction

  • Mid 1980s: object-oriented programming; data abstraction + inheritance + polymorphism

Language Categories

  • Imperative: central features are variables, assignment statements, and iteration; includes languages that support object-oriented programming; scripting languages; visual languages; examples: C, Java, Perl, JavaScript, Visual BASIC .NET, C++

  • Functional: computations are made by applying functions to given parameters; examples: LISP, Scheme, ML, F#

  • Logic: rule-based (rules specified in no particular order); example: Prolog

  • Markup/programming hybrid: markup languages extended to support some programming

Language Design Trade-Offs

  • Reliability vs. cost of execution: e.g., Java checks array bounds, increasing execution cost

  • Readability vs. writability: e.g., APL has many symbols enabling compact expressions but reducing readability

  • Writability vs. reliability: e.g., C++ pointers are powerful and flexible but can be unreliable

Implementation Methods

  • Compilation: translate high-level program into machine language; may include Just-In-Time (JIT) systems; used for large commercial applications

  • Pure Interpretation: program runs under an interpreter; easier implementation but slower execution; can require more space; now rare for traditional high-level languages; resurged in some web scripting languages (e.g., JavaScript, PHP)

  • Hybrid Implementation Systems: compromise between compilers and pure interpreters; high-level language translates to an intermediate language for easier interpretation; faster than pure interpretation

Layered View of Computer

  • The operating system and language implementation sit atop the machine interface of a computer; multiple layers separate user-level programming from hardware details

Compilation

  • Purpose: translate a high-level program (source language) into machine code (machine language)

  • Characteristics: slower translation, fast execution

  • Phases:

    • Lexical analysis: converts characters into lexical units (tokens)

    • Syntax analysis: builds parse trees representing syntactic structure

    • Semantics analysis: generates intermediate code (and performs semantic checks)

    • Code generation: produces machine code

ext{Compilation process:} \
\text{Source program} \rightarrow \text{Lexical analyzer} \rightarrow \text{Lexical units} \ \rightarrow \text{Syntax analyzer} \rightarrow \text{Parse trees} \ \rightarrow \text{Intermediate code generator (and semantic analyzer)} \rightarrow \text{Intermediate code} \ \rightarrow \text{Code generator} \rightarrow \text{Machine language}.$$

The Compilation Process (Diagram Elements)

  • Symbol table

  • Source program

  • Lexical analyzer

  • Lexical units

  • Syntax analyzer

  • Parse trees

  • Intermediate code generator (and semantic analyzer)

  • Intermediate code

  • Code generator

  • Optimization (optional)

  • Machine language

Additional Compilation Terminologies

  • Load module (executable image): the user and system code together

  • Linking and loading: process of collecting system program units and linking them to a user program

Von Neumann Bottleneck (Revisited)

  • The memory–processor connection speed is the primary bottleneck in overall system performance

  • This bottleneck motivates design choices that maximize effective memory access patterns and reduce memory traffic

Pure Interpretation

  • No translation to machine code; programs are executed by an interpreter

  • Pros: easier implementation; runtime errors are immediately visible

  • Cons: slower execution (roughly 10–100x slower than compiled code); often requires more space

  • Current status: rare for traditional high-level languages, but common in web scripting languages (e.g., JavaScript, PHP)

Pure Interpretation Process

  • Source program

  • Interpreter

  • Input data

  • Results

Hybrid Implementation Systems

  • Combine compilation and interpretation

  • A high-level language program is translated to an intermediate language that can be interpreted

  • Benefits: faster than pure interpretation; allows easier portability and optimization

  • Examples: early Perl implementations (partial compilation); early Java implementations used a hybrid approach with byte code for portability

Hybrid Implementation Process

  • Source program

  • Lexical analyzer

  • Lexical units

  • Syntax analyzer

  • Parse trees

  • Intermediate code generator (and semantic analyzer)

  • Intermediate code

  • Interpreter

  • Input data

  • Results

Just-in-Time Implementation Systems

  • Initially translate programs to an intermediate language

  • Then compile the intermediate language of subprograms into machine code when they are called

  • The machine code version is cached for subsequent calls

  • Widely used for Java programs

  • .NET languages are implemented with a JIT

  • Overall: JITs are delayed compilers

Preprocessors

  • Preprocessor macros are used to include code from other files

  • A preprocessor processes a program just before compilation to expand embedded macros

  • Example: C preprocessor – expands #include, #define, and similar macros

Programming Environments

  • UNIX: an older OS and tool collection; now often used through a GUI (e.g., CDE, KDE, GNOME) on top of UNIX

  • Microsoft Visual Studio.NET: large, complex visual environment used to build Web and non-Web applications in any .NET language

  • NetBeans: related to Visual Studio .NET, but primarily for Java applications

Summary

  • The study of programming languages is valuable for:

    • Increasing capacity to use different constructs

    • Enabling smarter language selection

    • Making it easier to learn new languages

  • Key evaluation criteria: Readability, writability, reliability, cost

  • Major influences on language design: machine architecture and software development methodologies

  • Major implementation methods: compilation, pure interpretation, and hybrid implementation systems (including JIT approaches and related techniques)