Building Abstraction with Procedures

The acts of the mind: Combining, relating, abstracting ideas John Locke, An Essay Concerning Human Understanding

• Computational process
• Programming languages

Lisp

• LISt Processing
• Late 1950s
• reasoning about the use of certain logical expressions - recursion equations
• Interpreter - carries out processes
• Introduced atoms and lists
• Blur “passive” data and “active” processes

Elements of Programming

• Primitive expressions
• means of combination

• means of abstraction

• Combinations: operator & operands
  • arguments : values of operands

• prefix notation

• (define var obj)

• environment: associating values with symbols

• Evaluating combinations:
  1. eval subexpression
  2. apply operands to procedure
• Note : recursive eval
  • tree accumulation
  • special forms: define(not operator & operands)
• procedure definitions: give compound operation a name
• (define (name formal-parameters) body)
• Substitution model:
  • each formal parameter replaced by the corresponding argument
  • evaluate the body of the procedure
• Evaluation order:
  • normal-order: expand and then reduce
  • applicative-order: evaluate the arguments and then apply
  • applicative : avoid multiple eval, less complicated for procedures that can’t be modeled by substitution

Conditional Expressions and Predicates

• case analysis, Lisp-cond
  • (cond (p1 e1) (p2 e2) …(else default))
  • predicates are evaluated one by one
• if
  • (if predicate consequent alternative)
  • and, or, not

Procedure abstraction: name is an abstraction of procedure

Local names

• formal parameter: bound variable
• binds: defining formal parameters in procedure
• free variable

• scope

• block structure: nesting of definitions
  • right solution to the simplest name-packaging problem

• Internal definition gets value from enclosing procedure: lexical scoping

Procedures and the processes they generate

• procedure : local evolution of a computational process
• Linear recursion and iteration
  • deferred operations
  • recursive process
    • if grows linearly, linear recursive process
    • program variables & deferred operations
  • iterative process(does not grow or shrink, state variables)
    • grows linearly with input, linear iterative process
    • program variables provide a complete description
    • tail recursion(prevent unnecessary environment growth)
  • recursive procedure(if func calls itself)
• Tree recursion: fib

• Orders of growth

• fermat test, fast-exp

• Probabilistic algorithms

Formulating abstraction with higher-order procedures

Procedures that manipulates procedures

• Procedures as arguments
• Construct procedures using lambda(anonymous function)
  • (lambda (formal-parameters) body)
  • (let ((var1 exp1) (var2 exp2)…) body)
• Procedures as general methods(fixed point method: newton’s …)
• Procedures as returned value

Building abstraction with data

Recall: key aspects of programming languages

• Combining process - compound process
• Combining data - compound data
  • data abstraction - separate the representation & implementation of data from usage of data
  • abstraction barrier
  • closure - the glue for combining data objects(procedural representation of data)
  • conventional interface¹
  • symbolic expressions - arbitrary symbols for its parts
  • generic operations and data-directed programming

Introduction to Data Abstraction

• Pairs
  • cons
  • car
  • cdr(Pron: could-er)
  • z = cons x y, x = z 0, y = z 1
• Data: only the minimal basis that needed for a representation
• high-level, implementation-irrelevant
• message passing : procedural representation of data

Hierarchical Data and the Closure Property

Closure property of cons: can create pairs of pairs - results of combinations can themselves be combined - hierarchical structures

• List (nil appended at the end)
  • map, zip …
• Hierarchical structures
  • tree … map
• Conventional interface
  • enumerator, filter, map …
  • similarity between tree & map²
• higher-order operations : abstracting patters of combining painters
• stratified design : complex system should be structured as a sequence of level

Symbolic Data

• quote - ’ - take the symbol

Multiple representations for Abstract data

• incorporate modules into larger systems additively
• dispatching on type - check type and call appropriate procedure
• data-directed programming : query type-procedure table
  • decompose into rows: let type dispatch itself
  • message passing: (define (apply-generic op arg) (arg op))

Systems with generic operations

• added table for different types
• coersion
• hierarchy of types : subtype
• Inadequacies of hierarchies - may have more than one supertype
  • which to resolve to
• example: symbolic algebra

Modularity, objects, and state

Assignment and local state

• For modularity: computational objects have local state variables
• Assignment operator to change the value associated with a name
• (begin exp1 exp2 …)
• (set! variable value)
• referentially transparent: equals can be substituted for equals(violated by set!)
• Imperative programming, the order of sequence in important

Environment model of evaluation

• variable designate a place where values are stored
• Environment
  • sequence of frames - each is a table of bindings
  • frames points to its enclosing environment, unless global
  • value is the value in the first frame that conatins the binding or unbound
  • bindings in newer frame shadow that in the older ones
• rules for eval:
  • procedure: code + environment
  • procedure object is applied to a set of arguments by constructing a frame
  • new frame has as its enclosing environ the environ part of the procedure object
  • eval lambda-expression relative to a given environment
  • define creates a binding in the current frame, set! find and change the binding
• Internal definitions
  • no interference with external procedure
  • can access arguments of the enclosing procedure

Modeling with mutable data

• mutators: modify data objects
  • mutable data objects: data for which mutators are defined
• List: set-car! set-cdr!
• parallel-execute make-mutex (’acquire ’release)
  • atomical actions
  • deadlock - processes stalled waiting for each other

Streams

mitigate some of the complexity of modeling state: List + delayed evaluation

• cons-streams, stream-car, stream-cdr
  • use (delay exp): create a delayed object
  • (delay exp) : (lambda () exp)
  • force: evaluate a delayed object
  • (define (force delayed-object) (delayed-object)) or with memoization
• streams of balances
• functional languages designed to resolve the issue on objects with mutable states
  • behavior does not change referentially transparent

Metalinguistic Abstraction

establishing new languages

An evaluator or interpreter for a programming langage is a procedure that, when applied to an expression of the language, performs the actions required to evaluate that expression.

The evaluator, which determiness the meaning of expressions in a programming language, is just another program

Metacircular evaluator: applicative-order:call-by-name

• Lisp evaluator in Lisp
• eval a combination
  • eval the subexpression
  • apply the value
• apply compound procedure
  • eval the body in a new environment

• eval - apply model

• core - Eval
  • an expression and an environment
  • primitive expressions
  • Special forms
    • quoted expression
    • assignment & definition
    • if
    • lambda
    • begin
    • cond
  • combinations
    • recursive eval
      • procedure arguments :processes a procedure application
    • apply
• Representing expressions
  • derived expressions: syntactic sugar
• Evaluator data structures
  • representation of T/F
  • representation of procedures
  • representation on environments
• running the evaluator as a program
• data as programs
  • evaluator: universal machine - mimics other machines(lisp programs³)
  • Halting problem - proved by contradiction
• Internal definitions
  • simultaneous definition - create simultaneous(undefined) but not evaluated yet
  • Separating syntatic analysis from execution

Lazy Evaluation:call-by-need

• non-strict
  • procedure entered before arguments
• strict
  • arguments are evaluated before the procedure is entered
• delayed arguments - thunks
  • evaluating thunks - forcing
  • avoid re-eval - memoize
• representing thunks - (expression & environment)

Variations on a Scheme - Nondeterministic Computing

Generate and test applications

• Amb and search
  • returns on possible choice
  • depth-first search/chronological backtracking
  • dependency-directed backtracking -> truth maintenance
• Implementation:
  • may resulting in a deadend and backtrack
  • environment and continuation procedures
    • sucess continuation and failure continuation
  • failure continuation:
    • amb expressions
    • top-level driver
    • assignments: backtracking will have to undo this
  • failure executes:
    • when program executes
    • try-again
    • when processing failure - back to choice, back one level

Logic programming

• expression oriented languages
  • expression -> value of a function
  • also means of computing
  • unidirectional computations
• Logic programming
  • relational vision of programming
  • unification - symbolic pattern matching
  • using what is to solve how to
  • query language -> formulating queries
  • rules as the abstraction
• deductive information rerival
  • assertions - data
  • queries using pattern variable
  • compound queries - combined pattern matching
• Two central operations
  • pattern matching
    • pattern matcher is a program that tests whether some datum fits a specified pattern
    • pattern, datum, frame(bindings for various pattern variables)
    • streams of frames
    • compound queries
  • Unification
    • generalization to rule conclusions
• simple queries:
  • stream of extended frames - matching the pattern against all assertions in the database
  • stream of extended frames - applying all possible rules(unifier)
• not P - P not deducible(close world assumption)

Computing with register machines

Register Machine : sequentially executes instructions that manipulate the contests of a fixed set of storage elements called registers

Designing register machines

• Data paths - registers and operations
• controller - how to sequence these operations
• language to describe
  • controller - a sequence of instructions together with labels that identify entry points
  • name of a data-path button to push to assign a value to a register
  • test instruction
  • conditional branch
  • unconditional branch
• subroutine : assign resgister state and able to continue from it
• Stack : recursion
  • save
  • restore

A register-machine simulator

• instruction execution procedure -> execute the current instruction
• execute kicks off the instruction sequence
• assembler:
  • take text and machine model
  • returns the instruction sequence
• monitoring machine performance

Storage allocation and garbage collection

• list-structured memory
• automatic storage allocation(illusion of infinite memory)
  • when no longer needed, recycled, garbage collection
• Name : address, location
  • address arithmetic
  • base address + index
• symbol -> pointer: interning
  • maintain an obarray
• Garbage : no longer needed pairs policy
  • stop-and-copy : copy those in the working memory and compact into a list
    • car: tag it is moved - broken heart
    • cdr: forwarding address
    • free points to start of free space
  • mark and sweep

The explicit-control evaluator

describing the precedure-calling and argument-passing in terms of operation on regs and stack

Compilation

• native language, machine language
• compilation: source language -> object program
• Structure: for each type of structure dispatch to a specialized code generator
• Target: the reg that stores the return value
• linkage descriptor: where to proceed
  • continue at the next isntruction in sequence
  • return from the procedure
  • jump to a named entry point
• instruction sequence?
  • set of registers must be initialized
  • set of registers that are modified
  • actual instruction
• lexical addressing(frame number and displacement)