-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Concepts in Programming Languages by John C. Mitchell -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- PART 1: Functions and Foundations -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 1: Introduction - goals 1 to understand design space of PL past and future concepts major conflicts and trade-offs between features, including implementation costs 2 better understanding through comparison 3 understand techniques associated with different language features - themes 1 computability 2 static analysis 3 expressiveness vs efficiency - features for comparison expressions functions heap storage exceptions modules objects threads -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 2: Computability - partial functions and computability programs define functions computations without values error termination (divide by zero) nontermination partial functions defined on some arguments, undefined on others computability partial recursive functions computable in principal not computable in practice, could take to much time or space Alonzo Church's Thesis definition the same class of functions on integers can be computed on any general computing device three definitions 1 mathematical 2 using Turing Machine 3 using lambda calculus Turing completeness all standard general purpose PLs give us the same class of computable functions non-computable (undecidable) halting problem is undecidable -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 3: Lisp: Functions, Recursion, and Lists 3.1 history Lisp: John McCarthy Scheme: Guy Steele and Gerald Sussman 3.2 Good Language Design motivating application Lisp symbolic computations, logic, experimental programming C Unix operating system Simula Simulation PL/1 tried to solve all problems, not successful or influential abstract machine (clear program execution model) Lisp expression to be evaluated continuation representing the remaining program association list (a-list) for variables heap of cons cells Fortran flat register machine no stacks, no recursion memory as linear array Algol family Stack of activation records heap storage Small talk Objects, communicating by messages theoretical foundations Lisp partial recursive functions for symbolic expressions based on lambda calculus 3.3 Brief Language Overview atoms, s-exps, lists (cons cells) functions vs special forms special forms do not eval their arguments evaluation of expressions eval arguments, including function position, then apply function to arguments static vs dynamic scope dynamic traditionally as bug. scheme and common list static 3.4 Innovations in the design of Lisp expression vs statement vs declaration 3.4.1 expression can be side effect free or not terminate statement is always side effect declaration conditional expressions 3.4.2 structured control structure vs goto the Lisp Abstract Machine 3.4.3 1 A LISP EXPRESSION to be evaluated 2 a CONTINUATION, which is a function representing the remain program to evaluate when done with the current expression 3 an ASSOCIATION LIST, commonly called the A-list in much of literature on Lisp and called the run-time stack in literature on Algol-based languages. The purpose of the A-list is to store the values of variables that may occur either in the current expression to be evaluate or in the remaining expressions in the program 4 a HEAP, which is a set of cons cells (pairs stored in memory) that might be pointed to by pointers in the A-list. programs as data 3.4.4 macros function expressions 3.4.4 (lambda ...) recursion 3.4.6 allow forward reference for recursive function calls higher order function 3.4.7 a function that takes a function as an argument or returns a function or both garbage collection 3.4.8 mark and sweep pure lisp vs lisp with side effects 3.4.9 rplaca rplacd set-car! set-cdr! setq set! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 4: Fundamentals 4.1 Compilers and Syntax source program input lexical analyzer break into tokens syntax analyzer grammatical parsing semantic analyzer type checking, operator annotation intermediate code generation RTL code optimizer see below code generator machine code target program Hello, world! code optimizer common subexpression elimination copy propagation dead-code elimination loop optimization move code to before unrolling ... in-lining function calls strength reduction ... grammars (overlap with DCFL's of automata theory) 4.1.2 BNF=Backus naur form derivations parse trees and ambiguity if-then-else example parsing and precedence 4.2 Lambda Calculus Functions and Function Expressions 4.2.1 Lambda Expressions 4.2.2 Syntax of Expressions grammar is simple - M ::== x | MM| lambda x.M Variable Binding alpha-equivalent if only diff in expressions is variables lambda x . x is alpha-equivalent to lambda y . y scope lambda x . M M is the scope of x Equivalence and Substituion lambda x . M = lambda y . [y/x] M (more formally than alpha-equivalence) (lambda x . M) N = [N/x] M (beta-equivalence (function application)) beta-equivalence is the Alpha 50 copy rule for evaluating function calls also related to macroexpansion and in-line substituion of functions always remember to rename bound variables in M that might be the same as free variables in N Programming in Lambda Calculus 4.2.3 Functions of Several Arguments f(g,x) = g(x) two arguments f-curry = lamba g. lambda x. gx one argument, returns function of one argument f-curry g x = gx = f(g,x) curring in this case works becuase (see left) Declarations let x = M in N (let ((x M) n) Lisp/Scheme ( lambda x . N ) M lambda calculus syntacic sugar - derivative sweeter syntax - declarations are good example Recursion and Fixed Points fixed point of a function F is a value f such that f=G(f) one lambda calculus fixed point operator Y=lambda f . (lambda x . f (x x)) (lambda x . f (x x)) Y f = (lambda x . f (x x)) (lambda x . f (x x)) Y f = f(lambda x . f (x x)) (lambda x . f (x x)) Y f = f (Y f) example of using Y with factorial f function f(n) { if n=0 then 1 else n*f(n-1)}; f(n) = if n=0 then 1 else n*f(n-1) f = lambda n . if n=0 then 1 else n*f(n-1) G = lambda f. lambda n . if n=0 then 1 else n*f(n-1) f = G(f) fact = YG fact 2 = (YG) 2 = G (YG) 2 = (lambda f. lambda n . if n=0 then 1 else n*f(n-1)) (YG) 2 = (lambda n . if n=0 then 1 else n*(YG)(n-1)) 2 = if 2=0 then 1 else 2*(YG)(2-1)) = if 2=0 then 1 else 2*(YG)(1)) = 2*((YG)1) = 2* G (YG) 1 = 2* (lambda f. lambda n . if n=0 then 1 else n*f(n-1)) (YG) 1 = 2*(lambda n . if n=0 then 1 else n*(YG)(n-1)) 1 = 2* if 1=0 then 1 else 1*(YG)(1-1)) = 2* if 1=0 then 1 else 1*(YG)(0)) = 2*1*((YG)0) = 2*1* G (YG) 0 = 2*1 (lambda f. lambda n . if n=0 then 1 else n*f(n-1)) (YG) 0 = 2*1(lambda n . if n=0 then 1 else n*(YG)(n-1)) 0 = 2*1 if 1=0 then 1 else 1*(YG)(0-1)) = 2*1*1 = 2 Reduction, Confluence, and Normal Forms 4.2.4 if we change equivalence to reduction (lambda x . M) N -> [N/x] M (beta-reduction) then we have a direction to evaluate normal forms use reductions until you cannot proceed, then you are in normal form confluence eval order does not affect final value this implies there is only one normal form Important Properties of Lambda Calculus 4.2.5 every computable function can be in pure lambda calculus no need for side effects numbers can be expressed with church numerals recursion with Y operator evaluation is order independant because of confluence 4.3 Denotational Semantics the meaning of program is a function of states to states Compositionality meaning of program from meaning of parts not syntactical operations like subsitution operation semantics step by step state transitions lambda calculs reduction 4.4 Functional and Imperative Languages functional: lisp and ML pure functional: no side effects can always replace common subexpressions referential transparency if we say that a variable refers to its location in memory then imperative languages are referentially transparent but not if a variable refers to the value stored in that location concurrency pure functional: evaluate in parallel imperative: must evaluate in order practical functional programming Backus's FP Haskell Lazy ML -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- PART 2: Procedures, Types, Memory Management, and Control -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 5: The Algol Family and ML 5.1 The Algol Family of Programming Languages Algol 60, Pascal, C Algol 58, Algol 68, Algol W, Euclid, EL1, Mesa, Modula-2, Oberon, Modula-3 Algol 60 5.1.1 included backus of fortran mccarthy of lisp alan perlis important features simple statement-oriented syntax with semicolon blocks with begin and end (C {}) recurisve functions and stack storage allocation few ad hoc restrictions general expression in array indices procedures that could be called with procedures parameters a primitive static type system the bad type of procedure parameters doesn't include arg types array parameters without bounds pass-by-value and pass-by-name pass-by-name interacts badly with side-effects pass-by-value expensive for arrays control flow problems with memory management jumping out of nested blocks Algol 68 5.1.2 second system effect some features made compilation inefficient improved on primitive type system primitive modes: int, real, char. bool, string, complex, bits, bytes, semaphore, format, file compound modes: array, structure, procedure, set, pointer unrestricted combinations such as array of pointers to procedures memory stack for local variables heap for non-locals, but garbage collected calling convention pass-by-value pass-by-reference with pointers basically C's model Pascal 5.1.3 simple one pass compiler type system: algol 60 < pascal < algol 68 records, varaint records, subranges Modula 5.1.4 pascal + module system 5.2 The Development of C arrays = pointers no nested function declarations C++ has stronger type checking rules 5.3 The LCF System and ML ML: a function-oriented imperative language LCF: Logic for Computable Functions reasons to study ML most important concepts of Lisp/Algol families ML type system is ofetn considered the cleanest and most expressive higher-order functions, ... two basic concepts arising from ML 1 type correctness 2 exceptions (which are also type safe) 5.4 The ML Programming Language constructs (more details below) patterns declarations functions polymorphism (later chapter) overloading type declarations reference cells exceptions (later chapter) Interactive Sessions and the Run-Time System 5.4.1 repl style expressions vs declarations div vs / no auto casting of integers to/from reals Identifiers vs Variables declarations introduce constants, not variables for variables, declare a mutable cell (see reference cells below) Basic Types and Type Constructors 5.4.2 types unit bool int strings real tuples #1(2, 4)=>2 records #First_name({First_name="Donald", Last_name="Knuth"}), lists 1::2::3::nil = [1,2,3] Patterns, Declarations, and Function Expressions 5.4.3 value declarations can destructure structured types val (x,y,z) = (1,2,3); this is how functions declaration sugar works fun f(x,y) = x+y; but more generally fun length(nil) = 0 | length (x::xs) = 1+length(xs); pattern match happens in order of declaration ML Data-Type Declaration 5.4.4 enumeration style datatype color = Red|Blue|Green union style datatype student = BS of name | MS of name*school | PhD of name*faculty; pattern match on BS/MS/PhD tags recursive types datatype tree = LEAF of int | NODE of (tree*tree); polymorphic datatype 'a tree = LEAF of 'a | NODE of ('a tree*'a tree); Reference Cells and Assignment 5.4.5 rev v creates ref to v !r returns value in cell r r:=v places v in ref cell r ie val x = ref 0; x := (3*!x)+5; !x =>5 expression sugar e1;e2 = (fn x => e2) e1 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 6: Type Systems and Type Inference 6.1 Types in Programming Three main uses of types 1 naming and organizing concept 2 making sure the bit sequences stored in computer memory are interpreted consistently 3 providing information to the computer about data manipulated by the program Program Organization and Documentation 6.1.1 Type Errors 6.1.2 Hardware Errors x() if x is not a function Unintended Semantics int_add(3, 4.5) Types and Optimization 6.1.3 typing can lead to efficient machine code for example, for record/struct access 6.2 Type Safety and Type Checkin type safety 6.2.1 examples not safe c/c++ type casts, pointer arithmetic almost safe pascal explicit dealoc, danlging pointers safe lisp, ml, smalltalk, java complete type checking compile-time vs run-time checking 6.2.2 compile time reduces need for run-time checks, benefit performance (lisp vs ml) compile time checking tends to be sound and conservative sound if no programs with errors are considered correct conservative if some programs without errors are still considered to have errors tied to halting problem if we assume all things halt, we find compile errors that might not happen at run-time 6.3 Type Inference First Examples of Type Inference (EXAMPLES page 137) 6.3.1 Type Inference Algorithm 6.3.2 1.) assing a type to the express and each subexpresion. for any compound expression or variable, use a type variable. for known operations or constants such as + or 3, use the type that is known to match the symbol 2.) generates a set of constraints on types, using the parse tree of the expression. these constraints reflect the fact that if a function is applied to an argument, for example, then the type of the argument must equal the type of the domain of the function. function application: if the type of f is a, the type of e is b, and the toype of fe is c, then we must have a = b->c lambda abstraction (function expression): if the type of x is a and the type of e is b, then the type of "lambda x .e" must be a->b 3.) solve these constrains by means of unification, which is a substituion-based algorithm for solving systems of equations 6.4 Polymorphism and Overloading forms parameteric polymorphism - type variables (C++ templates) ad hoc polymorphism - overloading subtype polymorphism - inheritence parameteric polymorphism 6.4.1 implementation 6.4.2 c++ polymorphism implemented at link time faster/code bloat ml has uniform data representation so no bloat, but potentially inefficent polymorphism vs overloading 6.4.3 parameteric polymorphism, same algorithm on different types ad hoc polymorphism, different algorithm for different types (at compile-time) 6.5 Type Declarations and Type Equality transparent - alternative name only, can be mixed 6.5.1 aka structural type equality type Celsius = real; opqaue - new type not equal to any previous aka name type equality datatype (above) and abstract types -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 7: Scope, Functions, and Storage Management 7.1 Block-Structured Languages block structure often denote scope variable classes local variables (stack allocated in activation record) parameters (also stack allocated in activation record) global variables (or simply "free variables", since they could be just from outside the local scope) 7.2 In-line Blocks activation records (aka stack frame) 7.2.1 stuff for blocks even without function calls referenced by environment pointer (aka stack pointer) space for local varibles space for intermediate results control link (aka dynamic link) to top of previous activation record 7.2.2 (7.3 Functions and Procedures) additional stuff in activation records for function calls 7.3.1 space for actual parameters (like local varibles) return address return result address addition for static scoping access link (aka static link) parameter passing 7.3.2 main distinctions the time that the actual parameter is evaluated the location used to store the parameter value mechanisms pass-by-reference: pass the l-value (address) of the actual parameter pass-by-value: pass the r-lvalue (contents of address) of the actual parameter pass-by-name: algol 60, beta-reduction, C macros pass-by-value-result (aka call-by-value-result or copy-in/copy-out) issues: side effects aliasing efficiency scope vs lifetime (7.2.1) scope: a region of text in which a declaration is visible (compile-time) lifetime: the duration, during a run of a program, during which a location is allocated as teh result of a specific declaration (run-time) scope can be different than lifetime when nested declarations hide scope of outer declarations static scope vs dynamic scope 7.3.3 static: a global id refers to the id with that name declared in the closest enclosing scope of the text examples: newer lisps, scheme, algol, pascal, c, ml, most current languages dyanmic: a global id refers to the id associated with the most recent activation record examples: older lisps, tex/latex, exceptions, marcos tail recursion 7.3.4 can be used to express iteration optimization to reuse activation records necessary for iteration to use constant space 7.4 Higher-order Functions first class (functions in this case, but for any type) 7.4.1 delcared within any scope pass as arguments to functions 7.4.2 returned as results of functions 7.4.3 downward funarg problem closures used for maintaining static scope when functions are passed to functions or returned as results. contains link to defining activation frame pointer to code when closure invoked allocate new activation frame as usual set access link to closure's defining activation frame upward funarg problem (aka upward fun-result problem) closures to the rescue again when functions are returned from nested scopes (with free variables), activation records do not obey a stack discipline can use garbage collection to recover frames -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 8: Control in Sequential Languages 8.1 Structured Control goto vs if/then/else/end while/do/end for{} case... 8.1.1/8.1.2 8.2 Exceptions Purpose of an Exception Method 8.2.1 jump out of a block or funciton invocation pass data as part of the jump return to a program point that was setup to continue the computation ML Exceptions 8.2.2 terms and syntax (ml syntax: exception name of type) raising (aka throwing) (ml: raise name arguments) handling (aka catching) (ml: handle => ) uses for error conditions for efficency handlers are typical searched via dynamic scope (dynamic link, control link) C++ exceptions 8.2.3 throw/try/catch (no finally...) problems with deallocation can lead to leaks if not careful More About Exceptions 8.2.4 Exceptions for Error Conditions obvious Exceptions for Efficency bail out of deep recursion Static and Dynamic Scope ML uses dynamic scope for evaluating variables in handler Typing and Exceptions ML type inference has to assign types to expressions handling exceptions just as for other expressions Exceptions and Resource Allocation GC languages are easy C++ has to invoke destructors as unroll stack make sure you don't lose memory... 8.3 Continuations A Function Representing "The Rest of the Program" 8.3.1 Continuation Passing Form (or cps continuation passing style) 8.3.2 fun fact(n) = if n=0 then 1 else n*fact(n-1) fun factk(n) = let fun f(n, k) = if n=0 then k(1) else f(n-1, fn x => k(n*x)) in f(n, fn x => x) make sure you are tail-recursive :) Compiling with Continuations (Steele and Sussman MIT AI MEMO 474) 8.3.3 1. lexical analysis 2. translate to lambda calculs form 3. conversion to CPS 4. optimization of CPS 5. closure conversion - eliminate free variables 6. elimination of nested scopes 7. register spilling - no expression with more than n free vars 8. generation of target-assembly language program 9. assembly to production target-machine program compiles calls directly to jumps (lambda the ultimate goto) 8.4 Functions and Evaluation Order delay and force (macro/special forms) Delay(e) == fn() => e Force(e) == e() -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- PART 3: Modularity, Abstraction, and Object-Oriented Programming -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 9: Data Abstraction and Modularity 9.1 Structured Programming top-down step-wise refinement? beware: smaller tasks might be harder than one algorithm Data Refinement 9.1.1 modifying data structures to support finer grained operations Modularity 9.1.2 interface - a description of the parts of a component that are visible to other program components specification - a description of the behavior ot the component, as observable through its interface client vs implementation client is user of component interface implementation is code that defines program component concretely 9.2 Language Support for Abstraction Abstraction 9.2.1 Procedural Abstraction well-defined interface information hiding of locals variables (reduce namespace clutter) reusability Data Abstraction indentify interface to data structure information hiding of implementation details reuse of data structures Abstract Data Types (from Clu clusters) 9.2.2 (not extensible like OOP but separates interface from implementation) type with set of operations abstype cmplx = C of real*real with fun cmplx(x,y:real) = C(x,y) fun x_coord(C(x,y)) = x fun y_coord(C(x,y)) = y fun add(C(x1,y1), C(x2,y2)) = C(x1+x2, y1+y2) end ML abstype could include type variables, useful to define say "set" 9.2.3 Representational Independence 9.2.4 example - we can declare variables "x : int" - there is a specific set of built-in operations on the type (int +/-/*/etc) - only these build-in operations can be applied to values of type int it is not type correct to apply string or other types of ops to int therefore "representational independence" can be implemented with 1's complement, 2's complement program should not care C does not do this of course bit-wise operators can tell 1's complement from 2's complement In a type sfe programming language with abstract data types - we can declare variables on any abstract type - we define operations on any abstract type - the type-checking rules guarantee that only these specified operations can be applied to the values of the abstract type Data-Type Induction 9.2.5 Partion Operations constuctors: build elements of type operators: map elements of the type defined with constuctors to others that are definable only with constuctors observers: operations that return a result of another type example with set: constuctors: empty and insert operations: union observer: isMember Induction over Constuctors because all elements of a given abstract type are given by a sequence of constuctor operations, we may prove properties fo all elements of an abs type by induction on the number of constuctors necessary to produce a given element. 9.3 Modules (from Modula) a module simply allows a number of declarations to be grouped together may also allow programmer to control visibility of items in a module also, may support parameterized modules Modula terms 9.3.1 interface is called definition module implementation is called implementation module Ada packages 9.3.1 ML modules 9.3.2 structures, signatures, functors signatures = interfaces structures = modules not first class, only bound to id's or passed to functors functors = functions from structures to structures used to define generic modules not higher-order, no need for signatures 9.4 Generic Abstractions C++ Function Templates 9.4.1 Simple Polymorphic Function Operations on Type Parameters Comparison with ML Polymorphism Standard ML Functors 9.4.2 a parameterized structure is called a functor written in functionlike form parameter list containing structure names and signatures C++ Standard Template Library 9.4.3 1 Containers 2 Iterators 3 Algorithms 4 Adapters 5 Function objects - a form of closure 6 Allocators - encapsulate the memory pool : GC, reference counting, persistent memory, etc (from slides) uses template mechanism but not overloading Does NOT rely on objects - No virtual functions efficient in time but not always space Boost Lambda Library C++ library giving lambda expressions implementation uses overloading -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 10: Concepts in Object-Oriented Languages objects interactions by messages or member-function calls (from slides) varieties of object oriented languages class based - behavior by class - only care about this for cs242 object based - objects defined directly multi-methods - operations depends on operands 10.1 Object Oriented Design - identify the objects at a given level of abstraction - identify the semantics (intended behavior) of these objects - identify relationships among the objects - implement the objects 10.2 Four Basic Concepts in Object-Oriented Languages dynamic lookup: object chooses how to respond to message (runtime, vs overloading at compile-time) 10.2.1 abstraction: implementation details are hiden 10.2.2 subtyping: if object a has the functionality of b, then we may use a in any context expecting b 10.2.3 inheritence: reuse the definition of one kind of object to define another kind of object 10.2.4 inheritence breaks some abstraction inheritence is not subtyping 10.2.6 subtyping is about interfaces, inheritence is about implementation closures can be seen as simple objects 10.2.5 dynamic lookup via function pointers abstraction through static scoping but no subtyping (what about is-a?) but no inheritence (what about delegation to contained closure?) 10.3 Program Structure function oriented each operation contains a dispatch based on type object-oriented each type contains each operation 10.4 Design Patterns it sovles a problem it is a proven concept the solution is not obvious it describes a relationship the pattern has a significant human component (mimimize human intervention) examples singleton facade -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 11: History of Objects: Simula and Smalltalk 11.1 Origin of Objects in Simula Object and Simulation 11.1.1 Main Concepts in Simula 11.1.2 added to algol 60 class concepts and reference variables (pointers to objects) pass-by-reference char, text, i/o features coroutines, mechanism for concurrent programs removed from algo 60 changed pass-by-name to combo pass-by-value and pass-by-reference some initialization requirements on variables own variables (C static variables) algol 60 string type (in favor of new text type) 11.2 Objects in Simula class: a procedure returna pointer to its activation record object: an activation record produce by call to a class, called an instance of the class Basic Object-Oriented Features in Simula 11.2.1 dynamic lookup: operations selected from activation record abstraction: in later versions subtyping: arising from the way types associated with classes inheritence: in the form of class prefixing, including redefining parts of subclass extras inner: method of aub should be called in combination with exec of inner superclass code inspect and qua: inspect is a class (type) test and qua is a form of type cast checked at runtime 11.2.2 An Example: Points, Lines, and Circles 11.2.3 Sample Code and Representation of Objects (from slides) object is represented by activation record access link to find global variables according to static scoping class procedure that returns pointer to activation record initialization code always run as procedure body objects closure created by class encapsulation private and protected added after original 1967 language subtyping by class heirarchy inheritence class prefixing 11.3 Subclass and Subtypes in Simula Subclasses and Inheritence 11.3.1 Object Types and Subtypes 11.3.2 11.4 Development of Smalltalk diff from simula in smalltalk, everything is object, even a class all operations are therefore messages to objects objects/classes were shown to be useful organizing concepts for building an entire programming environment and system abstract was added, distinguishing between private (protected actually) instance variables (data) and public methods (code) dynamic lookup: method lookup by receiver of messages, search local method dictionary first, then upward ingalls test: can you define a new type of integer and have it work everywhere? passing ingalls test can mean substantial run-time cost, java avoided this abstraction: as noted above subtyping: no compile time types, as long as two objects respond to the same messages they are subtypes ...at observing semantic substitution inheritence: by default from superclass 11.5 Smalltalk Language Features Terminology 11.5.1 Object Class Subclass Selector: The name of a message (analogous to a function name) Message: A selector together with actual parameter values (analogous to a function call) Method Instance Variable Classes and Objects 11.5.2 Inheritence 11.5.3 Abstraction in Smalltalk 11.5.4 (from slides) object contains pointer to class instance members class contains pointer to superclass pointer to template for instance members pointer to method dictionary method dictionary map from method name to code 11.6 Smalltalk Flexibility Dynamic Lookup and Polymorphism 11.6.1 Booleans and Blocks 11.6.2 Booleans are objects with selector named ifTrue:ifFalse if iB in a base class, then f may be fivcen type A->C in a derived class, provided C<:B Visibility must be the same. (return type may be replaced with subtype) Abstract Base Classes 12.4.4 at least one pure virtual member function 12.5 Multiple Inheritence Implementation of Multiple Inheritence 12.5.1 casts with multiple inheritence cause runtime pointer arithmetic Name Clashes, Diamond Inheritence, and Virtual Base Classes 12.5.2 Name Clashes implicit resolution: python and clos explicit resolution: C++ (eiffel?) disallow name clashes Diamond Inheritence two copies of a super class? or share one copy? Virtual Base Classes share one copy -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 13: Portability And Safety: Java the language the compilers and runtime (vm) the library and toolkits 13.1 Java Language Overview Java Language Goals Goals 13.1.1 portability reliability safety dynamic linking multithreaded execution simplicity and familiarity efficiency reduced emphasis on efficiency gave Java designers more flexibility ------------------------------------------------------------------------ Portability Safety Simplicity Efficiency Interpreted + + - Type safe + + +/- +/- Most values are objects +/- +/- + - Object by means of pointers + + - Garbage collection + + + - Concurrency support + + ------------------------------------------------------------------------ Design Decisions 13.1.2 Interpreted Type safe compile time verifier run time Objects and references Garbage collection Concurrency support Simplicity dropped from c/c++ structs and unions functions multiple inheritence goto operator overloading (to be added) automatic coercions pointers 13.2 Java Classes and Inheritence Classes and Objects 13.2.1 Initialization Static Fields and Methods Overloading Garbage Collection and Finalize Packages and Visibility 13.2.2 Inheritence: 13.2.3 method overriding and field hiding constructors final methods and classes class Object getClass, toString, equals, hashCode, clone, wait/notify/notifyAll, finalize Abstract Classes and Interfaces 13.2.4 13.3 Java Types and Subtyping Classification of Types 13.3.1 Subtyping for Classes and Interfaces 13.3.2 Arrays, Convariance, and Contravariance 13.3.3 array covariance problem class A {...} class B extends A {..} B[] bArray = new B[10] A[] aArray = bArray; // considered OK since B[] <: A[] aArray[0] = new A(); // allowed but run-time ArrayStoreException many runtime checks necessary Java Exception Class Hierarchy 13.3.4 unchecked: runtime and error checked: throwable, exception, and user defined exceptions Java Subtype Polymorphism 13.3.5 13.4 Java System Architecture Java Virtual Machine 13.4.1 Class Loader 13.4.2 Java Linker, Verifier, and Type Discipline 13.4.3 Bytecode Interpreter and Method Lookup 13.4.4 invokevirtual invokevirtual.quick remembers mtable offset invokeinterface invokeinterface.quick caches pointer to last class and method invokestatic invokespecial 13.5 Security Features Buffer Overflow Attack 13.5.1 The Java Sandbox 13.5.2 Class Loader The Bytecode Verifier and Virtual Machine Run-Time Tests The Security Manager Security and Type Safety 13.5.3 ------------------------------------------------------------------------ dynamic lookup: abstraction: subtyping: inheritence: -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- PART 4: Concurrency and Logic Programming -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 14: Concurrency and Distributed Programming multiprogramming: multple programs, one processor multiprocessing: multple programs, multple processors 14.1 Basic Concepts in Concurrency Execution Order and Nondeterminism 14.1.1 Communication, Coordination, and Atomicity 14.1.2 mechanisms for: communications buffered vs unbuffered sync vs async message order coordiation locking semaphores atomicity Mutal Exclusion and Locking 14.1.3 critical sections mutual exclusion: only one process at a time in critical section progress: if no process is in section, one may proceed bounded waiting: no waiting process should have to wait indefinitely implementation locks and busy waiting deadlocks Semaphores 14.1.4 wait and signal (P and V (pass and release)) binary vs counting little busy waiting (just for critical section on counter and wait queue) Monitors 14.1.5 more common in programming languages than raw semaphores, but conceptually equally powerful 14.2 The Actor Model Carl Hewitt's Planner actors no shared state use buffered asynchronous message passing for all communication actors may 1 send communication to itself or other actors 2 it may create actors 3 it may specify a replacement behavior, which is essentially another actor that takes the place of the actor that creates it for the purpose or responding to later communication no side effects of local variables except to specify a relpacement behavior "mail system" used for communication to "mail addresses" tasks - name for a message between actors 1 a unique tag 2 a target mail address 3 a communication, data contained in the message replacement behavior state changes only after completely processing input async buffering easily implemented in WAN 14.3 Concurrent ML Threads and Channels 14.3.1 threads spawn other threads, returing thread_id "forever" creates tail-recursive infinite loop channels send and recv blocking unicast or multicast Selective Communication and Guarded Commands 14.3.2 problem with blocking queue thread between producers and consumers can block either reading from producer or writing to consumer solution: Dijkstra's guarded command language do Producer is ready to send => Receive input and store in queue Consumer is ready to receive and queue is not empty => Send to waiting consumer od First-Class Synchronous Operations: Events 14.3.3 events recv built by sync-hronizing on a recvEvt fn recv(ch) = sync(recvEvt(ch)) send similar with sendEvt select built on choose from list of events fn select(evs) = sync(choose(evs) select is used to implement guarded commands mvars (M-structures from ID) memory cell with two states: empty and full 14.4 Java Concurrency Threads, Communication, and Synchronization 14.4.1 threads communication via memory etc Synchronized Methods 14.4.2 synchonization object locks for mutual exclusion objects wait sets for semaphores thread termination Virtual Machine and Memory Model 14.4.3 Distributed Programming and Remote Method Invocation 14.4.4 RMI locating remote objects communcation with remote objects transmitting objects across the network -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- CHAPTER 15: The Logic Programming Paradigm and Prolog 15.1 History of Logic Programming 15.2 Brief Overview of the Logic Programming Paradigm 15.2.1 Declarative Programming 15.2.2 Interactive PRogramming 15.3 Equations solved by unification as Atomic ACtions 15.3.1 Terms 15.3.2 Substitutions 15.3.3 Most General Unifiers 15.3.4 A Unification Algorithm Martelli-Montanari Algorithm 15.4 Clauses as Parts of Procedure Declarations 15.4.1 Simple cluases 15.4.2 Computation Process 15.4.3 Clauses Example % append(Xs, Ys, Zs) :- Zs is the result of concatenating the lists Xs and Ys append(Xs, Ys, Zs) :- Xs = [], Zs = Ys. append(Xs, Ys, Zs) :- Xs = [ H | Ts ], Zs = [ H | Us ], append(Ts, Ys, Us). Query to compute concatenation ?- append([jan, feb, mar], [april, may], Zs) Zs = [jan, feb, mar, april, may] Query to confirm yields empty subsitution ?- append([jan, feb, mar], [april, may], [jan, feb, mar, april, may]) Query for this false asserts fails ?- append([jan, feb, mar], [april, may], [jan, feb, mar, april]) append([feb, mar], [april, may], [feb, mar, april]) append([mar], [april, may], [mar, april]) append([], [april, may], [april]) 15.5 Prolog's Approach to Programming 15.5.1 Multiple Uses of a Single Program as with append, "member" can be used for testing and for computing a.) testing for membership, b.) listing members ?- member(wed, [mon, wed, fri]); yes ?- member(X, [mon, wed, fri]); Xs = mon; Xs = wed; Xs = fri; no (";" means next answer) append example, give all possible combinations ?- append(Xs, Ys, [mon, wed, fri]); Xs = [] Ys = [mon, wed, fri]; Xs = [mon] Ys = [wed, fri]; Xs = [mon, wed] Ys = [fri]; Xs = [mon, wed, fri] Ys = []; no 15.5.2 Logical Variables 15.6 Arithmetic in Prolog 15.6.1 Arithmetic Operators 15.6.2 Arithmetic Comparison Relations ?- quicksort([7,9,8,1,5], Ys) Ys = [1,5,7,8,9] ?- quicksort([7,9,8,1,5], [1,5,7,9,8]) no 15.6.3 Evaluation of Arithmetic Expressions 15.7 Control, Ambivalent Syntax, and Meta-Variables 15.7.1 Cut 15.7.2 Ambivalent Syntax and Meta-Variables 15.7.3 Control Facilities 15.7.4 Negation as failure 15.7.5 Higher-order Programming and Meta-Programming in Prolog 15.8 Assessment of Prolog 15.9 Bibliographic remarks 15.10 Summary introduced unification as a computation mechanism realized concept of "computation as deduction" showed a fragment of first-order logic can be used as a PL declarative programming is an interesting alternative to structured programming in the imperative programming style Logic Programming Imperative Programming equation solved by unification assignment relation symbol procedure identifier term expression atom procedure call query program definition of a relation procedure declarative local variable of a rule local variable of a procedure logic program set of procedure declarations "," between atoms sequencing (";") substitution state composition of substitution state update -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Other Important Things To Know Based On old Comps - C function type syntax arithmetic promotion - Smalltalk message passing method dictionary - C++ vtables (virtual function tables) name mangling and other linker tricks - Algol 60 pass by name - defintion of state of computation (similar to architecture section) program counter stack pointer - memory management stack allcoation - activation records - frame pointer heap allocation malloc fragmentations handles allows compaction to prevent fragmentation must double dereference garbage collection - conservative - mark and sweep - stop and copy compaction helps VM performance avoids fragmentation generational collectors shared memory - error handling exceptions - concurrency threads (kernel vs user) synchonization monitors semaphores (binary and counting) test-and-set (spin) vs locks (block) reentrance - lambda calculus alpha renaming beta reduction Y fixed point operator - operational vs denotation semantics - argument passing pass by value pass by reference pass by name - iteration recursion tail recursion - polymorphism generic types - object oriented encapsulation inheritence overloading - scope static scope dynamic scope object lifetime -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Luca Cardelli Type Systems 20 Page tutorial Basic Polymorphic Type Checking