Programming Language Fundamentals: Core Concepts

1. Why Study Programming Language Concepts?

• Expressiveness: Leverage diverse language features

• Selection: Match language to task (e.g., LISP for AI, PHP for web)

• Learning: Foundations ease uptake of new languages

• Efficiency: Choose constructs (recursion vs. iteration) for performance

• Maintenance: Better code reuse and understanding

2. Programming Domains and Typical Languages

3. Language Categories

• Imperative: Variables + assignment + iteration (C, Java, Python, Perl)

• Functional: Computation by function application (LISP, Scheme)

• Logic: Rule-based inference (Prolog)

• Hybrid/Markup: Adds programming to markup (XSLT, JSTL)

4. Programming Language Evaluation Criteria

• Readability

  • Simplicity & orthogonality: Few primitives, legal combinations

  • Minimal overloading and exceptions

  • Clear control constructs and data-structure syntax

• Writability

  • Expressivity: Rich operators, abstraction support

  • Orthogonality: Combine constructs consistently

• Reliability

  • Strong typing, exception handling, minimal aliasing

  • Natural expression of algorithms

• Cost

  • Development tools, execution speed, maintenance

  • Training, compiler availability, portability

5. Design Trade-Offs in Language Design

• Reliability ↔ Execution Cost

  • E.g., Java bounds-checks vs. runtime overhead

• Readability ↔ Writability

  • E.g., APL’s powerful symbols vs. steep learning curve

• Writability ↔ Reliability

  • E.g., C pointers offer flexibility but risk safety

6. Influences on Programming Language Design

• Computer Architecture: Von Neumann model → imperative dominance

• Methodologies: Structured, data-oriented, then object-oriented design

7. Programming Language Implementation Methods

• Compilation

  • Source → machine code; phases: lexing, parsing, semantic analysis, code generation

  • Pros: Fast execution; cons: Slower build time

• Interpretation

  • Source executed by VM; easy error reporting, but slower (10×–100×)

• Hybrid

  • Compile to intermediate (e.g., Java bytecode), then interpret/JIT

8. The von Neumann Model and Language Design

• Fetch-Decode-Execute Cycle

• Bottleneck: Memory–CPU bandwidth limits performance

• Language Mapping: Variables ≈ memory cells; assignment ≈ data piping; loops ≈ efficient repetition

Hybrid and Just-In-Time (JIT) Implementation

• Hybrid Systems

  • Compile source → intermediate code (bytecode) → interpret

  • Faster than pure interpretation, simpler than full compilation

  • Examples:

    • Perl (partial compile for error checking)

    • Early Java (bytecode + JVM)

• Just-In-Time (JIT)

  • Translate source → intermediate; at runtime compile “hot” methods → native code

  • Cache compiled methods for reuse

  • Common in: Java (HotSpot), .NET CLR

Preprocessors in Language Development

• Run before compilation to expand macros & includes

• Macros: #define, file inclusion via #include

• Simplify repetitive code, centralize headers

• Classic: C preprocessor (cpp)

Programming Environments: IDEs and Toolchains

Chapter 3: Syntax and Semantics

1. Definitions: Syntax and Semantics

   • Syntax: Form/structure of programs (tokens, grammar)

   • Semantics: Meaning of those structures (dynamic behavior)

2. Lexical vs. Grammatical Analysis

   • Lexeme: Raw character sequence (e.g., count, *)

   • Token: Category of lexemes (e.g., identifier, mult_op)

3. Generators vs. Recognizers

   • Generator: Describes how to write valid sentences (you as coder)

   • Recognizer: Parser checks input against grammar

4. Regular Expressions for Lexical Patterns

   • Describe lexeme patterns:

     • a|b (choice), ab (concatenation), a* (repetition), ( ) (grouping)

   • Example: C identifier → (letter|_) (letter|digit|_)*

5. Context-Free Grammars (BNF/EBNF)

   • Nonterminals: <expr>, <stmt>

   • Terminals: Actual tokens/lexemes (if, then, ;)

   • Productions:

     <stmt> → <var> = <expr>
     <expr> → <term> + <term> | <term> - <term>

   • Start Symbol: Entry point (<program>)

6. Derivation in Grammars

   • Repeatedly replace nonterminals with RHS until only terminals remain

   • Yields a valid sentence