Fundamental Concepts in Computer Architecture and Lambda Calculus

Foundations of Lambda Calculus

• Definition and Origin: Lambda Calculus ($λ$ calculus) is described as the world's smallest programming language. It was invented in the 1930s by the mathematician Alonzo Church.
• Core Concepts: It serves as a mathematical framework to formalize logic and computation. It is the foundation of functional programming, influencing languages such as Haskell and Lisp.
• The Single Rule: Virtually everything in Lambda Calculus is built from a single idea: variable substitution.
• Universality: Any computable function can be expressed using Lambda Calculus.
• Building Blocks:     * Variable: A placeholder or name, such as $x$, $y$, or $z$.     * Function (Lambda Abstraction): Denoted by $λx.x$. The structure consists of $λ$ + variable + $.$ + body. For example, the mathematical function $f(x) = x$ is written as $λx.x$.     * Application: Denoted by $(λx.x) y$. This represents applying a function to an argument. The expression $λx.x$ can be visualized as a "function machine" that takes an input $x$ and returns it unchanged.

Fundamental Reductions in Lambda Calculus

• α-Reduction (Alpha Reduction):     * Definition: The process of renaming bound variables within a function. This is analogous to renaming a parameter in source code.     * Effect: The function's semantic meaning remains identical.     * The Identity Rule: $λx.x \equiv α \equiv ζ \equiv λt.t$. All represent the identity function.     * Analogy: Calling a friend "buddy" or "pal"; the name changes, but the person remains the same.     * Examples:         * $λx.(x+1) \rightarrow λz.(z+1)$ (Rename $x$ to $z$).         * $λx.αy.(x+y) \rightarrow λa.λb.(a+b)$ (Rename $x \rightarrow a$, $y \rightarrow b$).         * $λf.λx.(f x) \rightarrow λg.λt.(g t)$ (Rename $f \rightarrow g$, $x \rightarrow t$).         * $λx.(x x) \rightarrow λw.(w w)$ (Rename $x \rightarrow w$).
• β-Reduction (Beta Reduction):     * Definition: The process of evaluating a function by applying it to its argument. This involves substituting the argument into the function's body.     * Rule: $(λx.body) argument \rightarrow β body[argument/x]$.     * Analogy: Plugging $x=3$ into the function $f(x) = x + 2$ results in $f(3) = 3+2 = 5$.     * Examples:         * $(λx.x) y \rightarrow β y$ (Identity function: replacing $x$ with $y$).         * $(λx.x+1) 5 \rightarrow β 5+1 = 6$ (Arithmetic substitution).         * $(λx.αy.x+y) 3 \rightarrow β αy.3+y$ (Partial application).         * $(λx.x \times x) 4 \rightarrow β 4 \times 4 = 16$ (Square function).
• Step-by-Step Beta Reduction Execution:     1. Start: $((λx. x + x)) 7$     2. Identify: Identify that the bound variable $x$ is to be replaced by the argument $7$.     3. Substitute: Replace all occurrences of $x$ with $7$ resulting in $7 + 7$.     4. Result: The final value is $14$.

Currying and Functional Chaining

• Origin: Named after the mathematician Haskell Curry, although it was actually invented by Moses Schönfinkel in 1924.
• Definition: The transformation of a function that takes multiple arguments into a chain of functions that each take exactly one argument.
• Key Idea: Each function takes one input and returns a new function to handle the subsequent input.
• Comparison:     * Without Currying: $add(x, y) = x + y$ results in $add(3, 4) = 7$.     * With Currying (λ style): $(λx. λ y.(x + y)) 3 4$.
• Currying Execution Trace:     * Step 1: Binary function application: $(λx. λ y.(x + y)) 3 \rightarrow β αy.(3 + y)$.     * Step 2: Final application: $(αy.(3 + y)) 4 \rightarrow β 3 + 4 = 7$.
• Numerical Examples of Currying:     * Multiplication: $(λx.αy.(x \times y)) 5 6 \rightarrow (αy.(5 \times y)) 6 \rightarrow 30$.     * Three Arguments: $(λx.αy.λz.(x+y+z)) 1 2 3 \rightarrow (αy.λz.(1+y+z)) 2 \rightarrow (λz.(1+2+z)) 3 \rightarrow 6$.     * Partial Application (add5):         * Define: $add5 = (λx. αy. (x + y)) 5$         * Simplify: $add5 = αy. (5 + y)$.         * Application 1: $add5 \, 3 = (αy.(5 + y)) 3 = 8$.         * Application 2: $add5 \, 7 = (αy.(5 + y)) 7 = 12$.

Practice Problems and Solutions

• Problem 1: Reduce $(λx. x + 3) 5$.     * Result: $8$.
• Problem 2: Reduce step by step: $(λx. x \times 2) 4$.     * Result: $8$.
• Problem 3: Reduce $((λx. (λ y. x + y)) 3) 6$.     * Step 1: $(λ y. 3 + y) 6$.     * Step 2: $3 + 6 = 9$.
• Problem 4: Reduce $(λx. x \times x) (λ y. y + 1)$.     * Result: $(λ y. y + 1) \times (λ y. y + 1)$.
• Problem 5: Reduce $(λx. αy. x - y) 8 2$.     * Step 1: $(αy. 8 - y) 2$.     * Step 2: $6$.
• Problem 6: Write curried version of $f(x, y, z) = x + y + z$.     * Ans: $λx.αy.λz.(x + y + z)$.
• Problem 7: Convert to curried lambda form: $f(x, y, z) = x \times y + z$.     * Ans: $λx.αy.λz.(x \times y + z)$.
• Complex Reduction Step-by-Step:     * Expression: $(λx. αy. x y) (λz. z + 1) 4$     * Step 1: Substitute $x = (λz. z + 1)$ into the first abstraction: $(αy. (λz. z + 1) y) 4$.     * Step 2: Substitute $y = 4$: $(λz. z + 1) 4$.     * Step 3: Substitute $z = 4$ into the final function: $4 + 1 = 5$.

Quick Recap and Discussion

• Q: What does α-reduction do?     * A: It renames bound variables while maintaining the exact same meaning.
• Q: What does β-reduction do?     * A: It applies a function to an argument by substituting values into the body.
• Q: What is currying?     * A: Breaking down multi-argument functions into chains of one-argument functions.
• Q: Are $λx.x$ and $αz.z$ different?     * A: No. They are α-equivalent, meaning they are identical under renaming.
• Conclusion on System Foundations: Together, α-reduction, β-reduction, and currying (referred to here as $γ$) make Lambda Calculus a complete computing system equivalent to any computer.

Turing Machines and Formal Computation

• Alan Turing's Objective: To design a model of computation that is simple, intuitive, generic, and formalizes the process of computation as performed by the human mind.
• Formalization Elements:     * Tape: Simulates unlimited sheets of paper to facilitate computation.     * Tape Head: Reads and writes symbols onto tape cells; moves left and right.     * States: Simulates the shifting states of a human mind during a task.     * Transition Function: The rule set governing changes.
• Machine Operations:     * Write: Optionally writes a new symbol at the current position.     * Move: Moves the tape head left or right (L/R).     * Think: Transitions to a new internal state.
• Input/Output: The initial finite symbols on the tape represent input; the final finite symbols represent output.
• Examples and Language Acceptance:     * The machine can be designed to accept specific languages, such as $L = {0^n1^n | n \geq 1}$.     * Transitions are typically written as (Current State, Symbol) $ightarrow$ (Next State, Write Symbol, Direction).

Programming Before Von Neumann: The ENIAC Era

• Context: Early computing (e.g., ENIAC in 1945) lacked software, keyboards, and screens. Programming was a physical process.
• The Big Idea: "Program = Physical Wires." Operators programmed machines by plugging cables between units and flipping switches.
• Data Representation (Rotary Switches):     * Numbers were set using rotary dials labeled $0$ through $9$.     * Internally, these acted as selectors connecting electricity to one of 10 metal contact points via a rotating "wiper."     * Electrical Pulsing: Setting a switch to $5$ prepares the machine to send $5$ electrical pulses.     * Decimal Places: For the number $005$, the hundreds and tens switches were set to $0$, and the ones switch to $5$.
• Accumulators: Storage units that functioned like modern registers. They counted pulses to store values.
• Execution Trace (Sum of 5 + 3):     * Step 1: Turn rotary dial 1 to $5$; route to Accumulator 1 via cable.     * Step 2: Turn rotary dial 2 to $3$; route to Accumulator 2 via cable.     * Step 3: Physical wiring of the operation. Connect the output of Accumulator 1 and Accumulator 2 into an Adder unit, then wire the output back to Accumulator 1.     * Step 4: Trigger execution with a pulse signal. Result ($8$) is stored in Accumulator 1.
• Changing the Program: To change from addition to multiplication, one had to unplug cables and replug them into a Multiplier unit. This process could take hours or even days.
• Water Tap Analogy: Setting a switch to $5$ is like allowing $5$ drops of water to fall; the accumulator is a bucket that counts the drops.

Von Neumann Architecture and The Stored-Program Concept

• Historical Context: John von Neumann (1903–1957) was a Hungarian-American mathematician who consulted on ENIAC and wrote the "First Draft of a Report on the EDVAC" in 1945.
• Innovation: The report outlined the stored-program concept, which proposed storing both instructions and data in the same memory using the same binary format.
• Five Major Components:     1. Memory (RAM): Divided into addressable cells to store instructions and data.     2. Control Unit (CU): Part of the CPU that fetches, decodes, and manages timing.     3. Arithmetic Logic Unit (ALU): Part of the CPU that performs math ($+, -, \times, /$) and logic ($AND, OR, NOT, XOR$).     4. Input Devices: Keyboard, mouse, sensors.     5. Output Devices: Monitors, printers, speakers.
• Fetch-Decode-Execute Cycle:     * Fetch: CU reads the instruction from the memory address held in the Program Counter (PC).     * Decode: CU interprets what the instruction means (e.g., identifying an "ADD" operation).     * Execute: ALU performs the task and stores the result (e.g., in a register).     * Repeat: This cycle happens billions of times per second in modern processors.
• Von Neumann vs. Harvard Architecture:     * Von Neumann: Unified memory for code and data. It is simpler and more flexible but suffers from the Von Neumann Bottleneck (the CPU must share the same bus to fetch instructions and data, limiting speed).     * Harvard: Separate memory and buses for instructions and data. It is faster (can fetch both simultaneously) and more secure, but more complex to design.     * Modern Compromise: Use of Modified Harvard Architecture, featuring separate L1 instruction and data caches but a unified main RAM.
• Memory Disambiguation: The CPU cannot tell instructions from data based on format alone. The Program Counter dictates which binary strings are treated as instructions.

Intel 8086 Microprocessor Architecture

• Specifications: Released in 1978. It was the first 16-bit microprocessor in the x86 family.     * Data Bus: 16-bit.     * Address Bus: 20-bit, allowing access to $2^{20} = 1,048,576$ bytes ($1\,MB$) of memory.     * Clock Speed: $5\,MHz - 10\,MHz$.
• Functional Units:     * Bus Interface Unit (BIU): Manages bus operations, fetches instructions, and calculates physical addresses. Contains segment registers ($CS, DS, SS, ES$), the Instruction Pointer ($IP$), and a $6$-byte instruction queue.     * Execution Unit (EU): Decodes and executes instructions using the ALU and registers ($AX, BX, CX, DX$, etc.).
• Pipelining: The use of a $6$-byte prefetch buffer (Instruction Queue) allows the BIU to fetch future instructions while the EU is executing the current one, increasing speed by up to $40\%$.
• Memory Segmentation:     * Uses 16-bit registers to address $1\,MB$ by dividing memory into segments.     * Physical Address Formula:     $Physical \, Address = (Segment \, Address \times 16_{10}) + Offset$     * Hex Calculation: $(Segment \times 10H) + Offset$.     * Example: If $CS = 1000H$ and $IP = 0050H$, then:     $10000H + 0050H = 10050H$.
• Operating Modes:     * Minimum Mode ($MN/MX \, pin = 1$): Single-processor system where the 8086 generates all control signals.     * Maximum Mode ($MN/MX \, pin = 0$): Multiprocessor system requiring an 8288 Bus Controller.

8086 Instruction Set and Registers

• General Purpose Registers (can be split into High/Low 8-bit registers):     * AX (AH:AL): Accumulator; used in MUL and DIV.     * BX (BH:BL): Base register; used for memory addressing.     * CX (CH:CL): Count register; used for loops.     * DX (DH:DL): Data register; holds 16-bit MUL/DIV components.
• Pointer and Index Registers: $SP$ (Stack Pointer), $BP$ (Base Pointer), $SI$ (Source Index), $DI$ (Destination Index).
• Arithmetic Instructions:     * ADD/SUB: Affects CF, ZF, SF, OF, PF, AF flags.     * MUL (Unsigned): 8-bit: $AX = AL \times src$. 16-bit: $DX:AX = AX \times src$. Sets CF and OF if the upper result is non-zero.     * DIV (Unsigned): 8-bit: $AL = quotient$, $AH = remainder$. Undefined flags afterward.     * INC/DEC: Does NOT affect the Carry Flag (CF).     * NEG: Calculates 2's complement ($0 - dst$).
• Logical Instructions:     * AND: Used for masking bits.     * OR: Used to set specific bits.     * XOR: Used to toggle bits. XOR AX, AX is the fastest way to zero a register.     * NOT: Performs 1's complement.     * TEST: Non-destructive AND; affects flags but does not change the destination.
• Shifts and Rotates:     * SHL/SHR: Logical shift left/right (multiply/divide by 2 for unsigned counts).     * SAR: Arithmetic right shift; preserves the sign bit.     * ROL/ROR: Circular rotation where bits wrap around.
• Numerical Trace for Subtraction:     * $05h - 07h$:     1. $07h$ in binary: $0000\,0111$.     2. 2's complement of $07h$: Invert ($1111\,1000$) + 1 = $1111\,1001$ ($F9h$).     3. Add $05h$ ($0000\,0101$) + $F9h$ ($1111\,1001$) = $1111\,1110$ ($FEh$).     4. Result: $FEh$ represents $-2$. Flags: $CF=1$, $SF=1$, $ZF=0$.