Concepts of Programming Languages – Chapter 1 Review

Find the Missing Number (Unsorted List)

• Problem statement
  • Given a list of n-1 distinct integers drawn from 1\dots n
  • Exactly one integer from that range is absent
  • Goal: identify the missing value efficiently
• Canonical numeric example
  • Input: [1, 2, 4, 6, 3, 7, 8]
  • Output: 5
• Classic arithmetic–series solution
  • Compute theoretical sum of a complete series: S_{full}=\frac{n(n+1)}{2}
  • Compute actual sum of list: S{list}=\sum{k=1}^{n-1} a_k
  • Missing number m=S{full}-S{list}
• Complexity analysis
  • Time: O(n) — single pass to accumulate S_{list}
  • Space: O(1)
• Practical notes / caveats
  • Beware of integer overflow for very large n; use 64-bit or modular arithmetic as needed
  • Alternative XOR method exists, giving same O(n) time / O(1) space while avoiding overflow

Find the Missing Number (Sorted Array Variant)

• Same mathematical premises as above, but the list appears in ascending order
• Illustrative examples
  • [1, 2, 3, 4, 6, 7, 8] \Rightarrow 5
  • [1, 2, 3, 4, 5, 6, 8, 9] \Rightarrow 7
• Exploitable monotonic property
  • Ideal relation: value - index = 1 when indexes are 0\dots n-2
  • First position where this relation fails pinpoints the gap
• Typical algorithmic strategies
  1. Linear scan (trivial)
  • Iterate until arr[i] != i+1; that i+1 is missing
  • O(n) time / O(1) space
  1. Binary search (preferred for large, sorted data)
  • Maintain low, high bounds; inspect mid-index difference
  • Narrows search to \log_2 n comparisons
  • Time: O(\log n), space O(1)
• Edge cases
  • Missing value may be at either end; handle off-by-one logic carefully
  • If no discrepancy, error in problem premises (no number missing)

Chapter 1 – Preliminaries (Sebesta, "Concepts of Programming Languages", 11ᵗʰ Ed.)

Overview of Covered Topics

• Reasons for studying language concepts
• Programming domains
• Language evaluation criteria
• Influences on language design
• Language categories
• Design trade-offs
• Implementation methods
• Programming environments

Reasons for Studying Concepts of Programming Languages

• Increased expressive power
• Better basis for language selection
• Easier acquisition of new languages
• Deeper insight into implementation effects
• More effective use of known languages
• Contributes to overall advancement of computing as a discipline

Programming Domains & Typical Characteristics

• Scientific
  • Heavy floating-point, extensive array use
• Business
  • Reports, decimal arithmetic, string manipulation
• Artificial Intelligence
  • Symbolic computation, linked lists, pattern matching
• Systems Programming
  • Efficiency paramount; low-level access
• Web Software
  • Heterogeneous mix: markup (HTML), scripting (PHP, JavaScript), general-purpose (Java)
• Other emergent areas
  • Mobile apps, gaming, embedded systems

Language Evaluation Criteria

Core dimensions

• Readability — how easily humans comprehend code
• Writability — how easily code can be produced
• Reliability — assurance that program behaves per spec
• Cost — total life-cycle expense (training, development, execution, maintenance)

Ancillary dimensions

• Portability — ease of migrating code between platforms
• Generality — applicability across problem domains
• Well-definedness — clarity & precision of the formal specification

Determinants of Readability

• Overall simplicity
  • Manageable feature set, minimal multiplicity & operator overloading
• Orthogonality
  • Small number of primitives combine freely & legally
• Rich, appropriate data types
• Syntax considerations
  • Intuitive identifier forms
  • Reserved keywords, clear compound-statement delimiters
  • Visible mapping between form and meaning

Determinants of Writability

• Simplicity & orthogonality (mirrors readability benefits)
• Support for abstraction
  • Encapsulation of complex structures/operations
• Expressivity
  • Abundant, powerful operators & library functions for concise notation

Determinants of Reliability

• Strong type checking
• Robust exception handling
• Controlled aliasing (limiting multiple references to same memory)
• Indirectly influenced by readability & writability: “unnatural” expression tends to hurt reliability

Determinants of Cost

• Training time and resources
• Development effort (language–application fit)
• Compilation & execution overhead
• Toolchain availability (free or commercial)
• Reliability: defects increase maintenance cost
• Long-term maintenance burden

Influences on Language Design

• Computer architecture
  • Prevalent von Neumann model shapes imperative languages
• Program-design methodologies
  • Structured programming, data abstraction, OOP each stimulated new languages/paradigms

Von Neumann Architecture Recap

Memory  <—>  CPU (ALU + Control Unit)  <—>  I/O

• Shared memory for code & data
• Sequential fetch–decode–execute cycle
• Leads naturally to variables (memory cells), assignment (data movement), and efficient iteration
• Bottleneck: memory–CPU bandwidth limits throughput ("von Neumann bottleneck")

Fetch–Execute Cycle (pseudo-code)

initialize PC
repeat forever
  IR ← memory[PC]; PC ← PC + 1   // fetch
  decode IR                       // decode
  execute IR                      // execute
end repeat

Evolution of Design Methodologies

• 1950s–60s: machine efficiency focus
• Late 1960s: human efficiency; structured programming, top-down design
• Late 1970s: shift toward data abstraction
• Mid 1980s: full object-oriented programming (abstraction + inheritance + polymorphism)

Language Categories

• Imperative (incl. OO, scripting, visual)
  • Examples: C, C++, Java, JavaScript, Perl, VB.NET
• Functional
  • Computation via mathematical function application
  • Examples: LISP, Scheme, ML, F#
• Logic (rule-based)
  • Example: Prolog
• Markup / programming hybrids
  • Markup languages augmented with programmable constructs
  • Examples: XSLT, JSTL

Typical Design Trade-Offs

• Reliability vs. performance
  • Example: Java’s array-bounds checking improves safety, costs time
• Readability vs. writability
  • Example: APL’s dense symbolic syntax is concise but hard to read
• Flexibility (writability) vs. reliability
  • Example: C++ pointers allow powerful manipulation, risk unsafe behavior

Implementation Methods

Compilation

• Translate source → machine code before execution
• Slow translation, fast runtime
• Phases
  1. Lexical analysis → tokens
  2. Syntax analysis → parse trees
  3. Semantic analysis → intermediate code
  4. Code generation (+ optional optimization) → machine code
• Resulting executable image (load module) produced via linking & loading

Pure Interpretation

• No pre-translation; interpreter executes source directly
• Easier debugging; runtime errors surface immediately
• 10–100× slower; larger memory footprint
• Classic usage dwindled, resurged in Web scripting (JavaScript, PHP)

Hybrid Implementation

• Source compiled to intermediate language; that IL is interpreted
• Faster than pure interpretation; retains portability
• Examples: early Java (bytecode on JVM), Perl’s internal IL

Just-in-Time (JIT) Compilation

• Variation of hybrid approach
• IL compiled to machine code on first call; cached for reuse
• Provides near-compiled speed with platform independence
• Widely used in Java & .NET languages

Preprocessors

• Source‐code rewriter executed prior to compilation
• Expands macros, includes, conditional compilation
• Example: C preprocessor handling #include, #define, etc.

Layered View of a Computer System

| High-level language programs |
|  Language implementation     |
|  Operating system            |
|—— machine interface ———|
| Hardware (CPU, memory, I/O)  |

Programming Environments (Tool Suites)

• UNIX + GUI shells (CDE, KDE, GNOME)
• Microsoft Visual Studio .NET (multi-language, web & desktop)
• NetBeans (Java-centric counterpart to VS)

Chapter Summary

• Studying languages sharpens programming competence and aids informed language choice.
• Core evaluation attributes: readability, writability, reliability, cost (plus portability, generality, well-definedness).
• Design shaped chiefly by underlying hardware (von Neumann) and evolving software methodologies.
• Implementation spectrum spans compilation → interpretation → hybrids/JIT.
• Comprehensive tool ecosystems (programming environments) integrate compilers, debuggers, editors, and other utilities for productivity.