속눈썹맨의 블로그

C++에서 OOP를 소개할 때, polymorphism도 덧붙여서 이야기하곤 한다.
하지만 polymorphism과 OOP는 좀 다른 개념이다.

. OOP의 특징
  . dynamic look-up
   . 각 object에 알맞는 member function 찾기
   . virtual member function 사용시
  . encapsulation(= abstraction)
  . subtype
  . inheritance

. Polymorphism
  . 다른 type에 대해서 같은 algorithm을 사용하는 것.

. C++
  . template
  . explicit polymorphism
  . type마다 각자 copy를 가진다.

. ML
  . implicit polymorphism
  . 1개의 copy만 가진다.

. Java
  . generic (Java 1.5의 compile-time)
  . Object class를 이용하여 흉내낼 수도 있다.
   (Java 1.5도 run-time에는 그렇게 동작한다.

#include <iostream>
using namespace std;

class Vehicle {
  public:
       int x;

       virtual void f()
       {
           cout << "Vehicle::f()" << endl;
       }

       void g()
       {
           cout << "Vehicle::g()" << endl;
       }
};

class Airplane : public Vehicle {
  public:
       int y;

       virtual void f()
       {
           cout << "Airplane::f()" << endl;
       }

       virtual void h()
       {
           cout << "Airplane::h()" << endl;
       }
};

void inHeap()
{
  Vehicle *b1 = new Vehicle();
  Airplane *d1 = new Airplane();
  b1->x = 1;
  d1->x = 2;
  d1->y = 3;
 
  b1->f();
  b1->g();
  d1->f();
  d1->g();
  d1->h();

  b1 = d1;

  b1->f();
  b1->g();
  b1->h();
}

void onStack()
{
  Vehicle b2;
  Airplane d2;
  b1.x = 4;
  d1.x = 5;
  d1.y = 6;

  b1.f();
  b1.g();
  d1.f();
  d1.g();
  d1.h();

  b1 = d1;

  b1.f();
  b1.g();
  b1.h();
}

void main()
{
  inHeap();
  onStack();

  return 0;
}

$ g++ a.cpp -g -W -Wall
-------------------------------------------------------
Vehicle::Vehicle()
Vehicle::Vehicle()
Airplane::Airplane()

Vehicle::f()
Vehicle::g()

Airplane::f()
Vehicle::g()
Airplane::h()

Airplane::f() // 자신을 계속 Airplane이라고 생각하고 있다.
Vehicle::g()

Vehicle::Vehicle()
Vehicle::Vehicle()
Airplane::Airplane()

Vehicle::f()
Vehicle::g()

Airplane::f()
Vehicle::g()
Airplane::h()

Vehicle::f()
Vehicle::g()
-------------------------------------------------------
heap에 넣으면 subtype시 자신임을 그대로 유지하고
stack에 넣으면 subtype시 parent가 된다.
그리고 subtype시 두 경우 모두 자신에게만 나타나는 member function은 부를 수 없다.

사실 subtype과 inheritance는 다른 개념이지만 C++에서는 혼용해서 쓰고 있다.
C++은 public base class inheritance를 subtype으로 간주한다.
(반례 - deque를 상속해서 stack, queue를 만드는 경우 inheritance와 subtype의 방향이 반대이다.)

. Simula 67
  . First object-oriented language
  . Designed for simulation
   . Later recognized as general-purpose prog language
  . Extension of Algol 60
  . Standardized as Simula(no "67") in 1977
  . Inspiration to many later designers
   . Smalltalk
   . C++

. Brief histroy
  . Norwegian Computing Center
   . Designers : Dahl, Myhrhaug, Nygaard
   . Simula-1 in 1966 (strictly a simulation language)
   . General language ideas
     . Influenced by Hoare's ideas on data types
     . Added classes and prefixing (subtyping) to Algol 60
   . Nygaard
     . Operations Research specialist and political activist
     . Wanted language to describe social and industrial systems
     . Allow "ordinary people" to understand political(?) changes
   . Dahl and Myhrhaug
     . Maintained concern for general programming

. Comparison to Algol 60
  . Added features
   . class concept
   . reference variables(pointers to objects)
   . pass-by-reference
   . char, text, I/O
   . coroutines
  . Removed
   . Changed default par passing from pass-by-name
   . some var initialization requirements
   . own(= C static) variables
   . string type (in favor of text type)

. Objects in simula
  . class
   . A procedure that returns a pointer to its activation record
  . object
   . Activation record produced by call to a class
  . object access
   . access any local variable or procedures using dot notation : object.
  . Memory management
   . Objects are garbage collected
     . user destructors considered undesirable

. Ex) Circles and lines
  . Problem
   . Find the center and radius of the circle passing through three distinct points, p, q, and r
  . Solution
   . Draw intersecting circles Cp, Cq around p, q and circles Cq', Cr around q, r
     (Picture assumes Cq = Cq')
   . Draw lines through circle intersections
   . The intersection of the lines is the center of the desired circle.
   . Error if the points are colinear

. Approach in Simula
  . Methodology
   . Represent points, lines, and circles as objects
   . Equip objects with necessary operations
  . Operations
   . Point
     . equality(anotherPoint) : boolean
     . distance(anotherPoint) : real (needed to construct circles)
   . Line
     . parallelto(anotherLine) : boolean (to see if lines intersect)
     . meets(anotherLine) : REF(Point)
   . Circle
     . intersects(anotherCircle) : REF(Line)

. Simula Point Class
  . uninitialized ptr has value none
  . =/= : 다름
  . :- : pointer assignment
  . := : value assignment

. Representation of objects
  . Object is represented by activation record with access link to find global variables according to static scoping

. simular line class
. Derived classes in Simula
  . A class decl may be prefixed by a class name
   class A
   A class B
   A class C
   B class D
  . An object of a "prefixed class" is the concatenation of objects of each class in prefix

. Subtyping
  . The type of an object is its class
  . The type associated with a subclass is treated as a subtype of the type assoc with superclass

. Main object-oriented features
  . Classes
  . Objects
  . Inheritance ("class prefixing")
  . Subtyping
  . virtual methods
   . A function can be redefined in subclass
  . Inner : combines code of superclass with code of subclass
  . Inspect/Qua : run-time class/type tests

. Error in simula type system
  . B<:A does not mean ref(B) <: ref(A)

. Coroutine in Simula 67
  . detach
  . resume

. features absent from simula 67
  . Encapsulation
   . All data and functions accessible; no private, protected
  . Self/super mechanism of Samlltalk
   . No self, super, ..
  . Class variables
   . But can have global variables
  . Exceptions
   . Not an OO feature anyway

. simula summary
  . Class
   . "procedure" that returns ptr to activation record
   . initialization code always run as procedure body
  . Objects : closure created by a class
  . Encapsulation
   . protected and private not recognized in 1967
   . added later and used as basis for C++
  . Subtyping : determined by class hierarchy
  . Inheritance : provided by class prefixing

. Smalltalk
  . major language that popularized objects
  . Developed at Xerox PARC
   . Smalltalk-76, Smalltalk-80 were important versions
  . Object metaphor exttended and refined
   . Used some ideas from Simula, but very different lang
   . Everything is an object, even a class
   . All operations are "messages to objects"
   . Very flexible and powerful language
     . Similar to "everything is a list" in Lisp, but more so

. Smalltalk language terminology
  . Object : Instance of some class
  . Class : Defines behavior of its objects
  . Selector : Name of a message
  . Message : Selector together with parameter values
  . Method : Code used by a class to respond to message
  . Instance variable : Data stored in object
  . Subclass : Class defined by giving incremental modifications to some superclass

. Ex) Point class
  . Class definition written in tabular form
  . ^ : return value
  . || : local decl
  . <- : syntax for assginment

. Instance messages and methods

. Encapsulation in Smalltalk
  . Methods are public
  . Instance variables are hidden
   . Not visible to other objects
     . pt x is not allowed unless x is a method
   . But may be manipulated by subclass methods
     . This limits ability to establish invariants
     . Ex)
       . Superclass maintains sorted list of messages with some selector, say insert
       . Sublcass may access this list directly, rearrange order

. Object types
  . Each object has interface
   . Set of instance methods declared in class
   . This is a form of type
     . Names of methods, does not include type/protocol of arguments
  . Object expression and type
   . Send message to object
   . Expression OK if message is in interface

. Subtyping
  . Relation between interfaces
   . Suppose expression makes sense
   . Replace p by q if interface of q contains interface of p

  . Subtyping
   . If interface is superset, then a subtype
   . Ex) ColorPoint subtype of Point
   . Sometimes called "conformance"(일치, 적합, 순응)
  . Can extend to mroe detailed interfaces that include types of parameters

. Subtyping and Inheritance
  . Subtyping is implicit
   . Not a part of the programming language
   . Important aspect of how systems are built
  . Inheritance is explicit
   . Used to implement systems
   . No forced relationship to subtyping

. Smalltalk Flexiblity
  . Measure of PL expressiveness
   . Can constructs of the language be defined in the language itself?
   . Ex)
     . Lisp cond : Lisp allows user-defined special forms
     . ML datatype : sufficient to define polymorphic lists, equivalent to built-in list type
     . ML overloading : limitation, since not available to programmer
     . C, C++ : ???
  . Smalltalk is expressive in this sense
   . many constructs that would be "primitives" other are definable in Smalltalk
   . ex) Booleans and Blocks

. Smalltalk booleans and blocks
  . Boolean value is object with ifTrue:ifFalse:
   . Class boolean with subclasses True and False
   . True ifTrue:B1 ifFalse:B2 executes B1
   . False ifTrue:B1 ifFalse:B2 executes B2
  . Example expression
   . i < j ifTrue: [i add 1] ifFalse: [j subtract 1]
   . i < j is boolean expression, produces boolean object
   . arg's are blocks, objects with execute methods
  . Since booleans and blocks are very common
   . Optimization of boolean
   . Special syntax for blocks

. Self and Super
  . This method can be implemented in Integer, and works even if SmallInt and LargeInt are represented differently,.
  . C++ and Java type systems can't really cope with this.

. Ingalls' test
  . Dan Ingalls : principal designer Samlltalk system
   . Grace Murray Hopper award for Smalltalk and Bitmap graphics work at Xerox PARC
   . 1987 ACM Software Systems Award with Kay, Goldberg
  . Proposed test for "object oriented"
   . Can you define a new kind of integer, put your new integers into rectangles
     (which are already part of the window system), ask the system to blacken a rectangle,
     and have everything work?
   . Smalltalk passed, C++ fails this test

. Smalltalk integer operations
  . Integer expression
   . x plus : 1 times: 3 plus: (y plus: 1) print
  . Properties
   . All operations are executed by sending messages
   . If x is from some "new" kind of integer, expression makes sense as long as x has plus, times, print methods.
  . Actually, compiler does some optimization.
  . But will revert to this if x is not built-in integer
   (revert : 되돌아가다, 복귀v, 회상v)

. Costs and benefits of "true ))"
  . Why is property of Ingalls test useful?
   . Everything is an object
   . All objects are accessed only through interface
   . Makes programs extensible
  . What is implementation cost?
   . Every integer operation involves method call
     . Unless optimizing compiler can recognize many cases
   . Is this worth it?
     . One application where it seems useful?
     . One application where it seems too costly?
     . Are there other issues? Security?

. Smalltalk Summary
  . Class
   . creates objects that share methods
   . pointers to template, dictionary, parent class
  . Objects : created by a class, contains instance variables
  . Encapsulation
   . Mathods public, instance variables hidden
  . Subtyping : implicit, no static type system
  . Inheritance : subclasses, self, super
   . Single inheritance in Samlltalk-76, Smalltalk-80

. Ruby - http://www.ruby-lang.org/
  . Ruby is a "complete, full, pure object oriented language"
   . All data in Ruby are objects, in the sense of Smalltalk
   . ex) the number 1 is an instance of class Fixnum
  . Very flexible
   . Can add methods to a clsss, or even to instance during runtime
   . closures
   . Automatic small integer (Fixnum) large integer (Bignum) conversion
  . Single inheritance only
   . Ruby features single inheritance only, *on purpose*
   . Modules are colections of methods
     . A class can import a module and gets all its methods
  . http://www.rubycentral.com/book/

. Object-oriented programming
  . Primary object-oriented language concepts
  . Dynamic lookup
  . encapsulation
  . inheritance
  . subtyping
  . Program organization
  . Work queue, geometry program, design patterns
  . Comparison
  . Objects as closures?

. Objects
  . An object consists of
  . hidden data
     . instance variables, also called member data
     . hidden functions also possible
  . public operations
     . methods or member functions can also have public variables in some languages

  . Object-oriented program
  . send messages to objects

. What's interesing about this?
  . Universal encapsulation construct
  . Data structure
  . File system
  . Database
  . window
  . Integer

  . Metaphor usefully ambiguous
  . sequential or concurrent computation
  . distributed, sync. or async. communication

. Object-Orientation
  . Programming methodology
  . orginize concepts into objects and classes
  . build extensible systems

  . Language concepts
  . Dynamic lookup
  . Encapsulation
  . Subtyping allows extensions of concepts
  . Inheritance allows reuse of implementation

. Dynamic Lookup
  . In object-oriented programming, object message(arguments)
  code depends on object and message

  . In conventional programming, operation (operands)
  meaning of operation is always the same

  . Fundamental difference between abstract data types and objects

. Example
  . Add two numbers
  . different add if x is integer, complex

  . Conventional programming add(x,y)
  . function add has fixed meaning

  . Very important distinction:
  . Overloading is resolved at compile time, Dynamic lookup at run time.

. Encapsulation
  . Builder of a concept has detailed view
  . User of a concept has abstract view
  . Encapsulation separates these two views
  . Impelmentation code : operate on representation
  . Client code : operate by applying fixed set of operations provided by implementer of abstraction

. Languge concepts
  . "Dynamic lookup"
  . Different code for different object
  . Integer "+" different from real "+"
  . Encapsulation
  . subtyping
  . Inheritance

. Subtyping and Inheritance
  . Interface : The external view of an object
  . Subtyping : Relation between interfaces
  . Implementation : The internal representation of an object
  . Inheritance : Relation between implementations

. Object Interfaces
  . Interface : The messages understood by an object
  . The interface of an object is its type

. Subtyping
  . If interface A contains all of interface B, then
  A objects can also be used B objects.
  . Colored_point interface contains Point
  . Colored_point is a subtype of Point

. Inheritance
  . Implementation mechanism
  . New objects may be defined by reusing implementations of other objects

. Subtyping
  . Colored points can be used in place of points
  . Property used by client program

. Inheritance
  . Colored points can be implementated by reusing point implementation
  . Technique used by implementer of classes

. OO Program Structure
  . Group data and functions
  . Class : Defines behavior of all objects that are instances of the class
  . Subtyping : Place similar data in related classes
  . Inheritance : Avoid reimplementing functions that are already defined
  . Subtyping differs from inheritance

. Design Patterns
  . Classes and objects are useful organizing concepts
  . Culture of design patterns has developed around object-oriented programming
  . Shows value of OOP for program organization and problem solving

. What is a design pattern?
  . General solution that has developed from repeatedly addressing similar problems
  . ex) singleton
  . restrict programs so that only one instance of a class can be created
  . signleton desing pattern provides standard solution
  . Not a class template
  . Using most patterns will require some thought
  . Pattern is meant to capture experience in useful form

. Varieties of OO languages
  . class-based languages (C++, Java, ...)
  . behavior of object determined by its class
  . object-based (Self)
  . objects defined directly
  . multi-methods (CLOS)
  . operation depends on all operands

. History
  . Simula : Object concept used in simulation (1960's)
  . Smalltalk : Object-oriented design, systems (1970's)
  . C++ : Adapted Simula ideas to C (1980's)
  . Java : Distributed programming, internet

. Summary
  . Object-oriented design
  . Primary object-oriented language concepts
  . dynamic lookup
  . encapsulation
  . inheritance
  . subtyping
  . Program organization
  . Work queue, geometry program, design patterns
  . Comparison
  . Objects as closures

Topics
. Modular program development
  . Step-wise refinement
  . Interface, specification, and implementation
. language support for modularity
  . Procedural abstraction
  . Abstract data types
  . Packages and modules
  . Generic abstractions
   . Functions and modules with type parameters

. Stepwise Refinement
  . Wirth, 1971
   . "program gradually developed in a sequence of refinement steps"
   . In each step, instructions .. are decomposed into more detailed instructinos.
  . Historical reading on web
   . N.wirth, program development by stepwise refinement, Communications of the ACM, 1971
   . D. Parnas, On the criteria to be used in decomposing systems into modules, Comm ACM, 1972
   . Both ACM Classics of the Month

. Dijkstra's Example
  . 간단하게 주석처럼 쓰고 점점 코드에 가깝게 만들어 감.

. Program Structure
  . Main program - 밑에 여러개의 sub-program의 tree로 hierarchical하게 구성됨.

. Data Refinement
  . Wirth, 1971 again:
   As tasks are refined, so the data may have to be refined, decomposed, or structured, and it is natural to refine program and data specifications in parallel.

  . Example
   . Bank Transactions - Deposit, Withdraw, Print Statement, Print transaction history
   . For level 2, represent account balance by integer variable
   . For level 3, need to maintain list of past transactions

. Modularity : Basic concepts
  . Component : Meaningful program unit - function, data structure, module
  . Interface : Types and operations defined within a component that are visible outside the component
  . Specification : Intended behavior of component, expressed as property observable through interface
  . Implementation : Data structures and functions inside component

ex) Function Component
  . Component : Function to compute square root
  . Interface : float sqroot(float x)
  . Specification : If x>1, then sqrt(x)*sqrt(x) = x
  . Impelmentation
   . Bisection method를 구현한 코드를 C로 적음.(길어서 생략)

Ex) Data Type
. component : Priority queue : data structure that returns elements in order of decreasing priority
. Interface
  . Type : pq
  . Operations :
   empty : pq
   insert : elt * pq -> pq
   deletemax : pq -> elt * pq
. Specification
  . Insert add to set of stored elements
  . Deletemax returns max elt and pq of remaining elts

. Problem with writing large programs
  . Wulf and Shaw : Global Variables Considered Harmful
   1. side effects - accesses hidden in functions
   2. Indiscriminant access - can't control access
   3. Screening - may lose access via new declaration of variable
   4. Aliasing

  . Characteristics of solution:
   1. No implicit inheritance of variables
   2. Right to access by mutual consent(담합)
   3. Access to structure does not imply access to substructure
   4. Provide different types of access
   5. Decouple declaration, name access, and allocation of space

. ADT : Abstract Data Types
  . Prominent(유명한, 중요한, 탁월한, 현저한) language development of 1970's
  . Main ideas:
   . Separate interface from implementation
     . Sets have empty, insert, union, is_member?
     . Sets implemented as .. linked list ..
   . Use type checking to enforce separation
     . client program only has access to operations in interface
     . Implementation encapsulated inside ADT construct

. Abstract Data Types
  . Package data structure and its operations in same module
  . Data type consists of set of objects plus set of operations on the objects of the type
   (constructor, operatos, observers)
  . Want mechanism to build new data types(extensible types)
  . Should be treated same way as built-in types
  . Representation should be hidden from users(abstraction)
  . Users only have access via operations provided by the ADT(encapsulation)
  . Distinguish between specification and implementation

. ADT Specification
  . ADT specification declares data type and operations without implementation details, but possibly with semantics of operations
  . Provides information needed to use ADT in programs
  . Typically includes
   1. Data strcutures : constants, types, and variables accessible to user
      (although details may be hidden)
   2. Declarations of functions and procedures accessible to user(bodies not provided)

. ADT specification
  . May also specify behavioral obligation of an implementation
  . As an example, an algebraic specification of behavior of a stack might look like

  . Formal specification of ADTs uses universal algebras
   . Data + Operations + Equations = Algebra

. ADT impelmentation (Representation)
  . Definition of the implementation details of an ADT collected in one location
  . Usually not accessible to user - some form of access control
  . Provides details on all data structures (including some hidden to users) and
   bodies of all operations

. Representation in language
  . Three predominant concerns in language design
   . Simplicity of design
   . Application of formal techniques to specification and verification
   . Keep down lifetime costs
  . Reusable modules to represent ADTs quite important
   . Separate (but not independent) compilation
   . Want to maintain type checking
   . Control over export and import of names (scope)

. ML Abstype
  . ADT supported in very straightforward way in ML
  . Provides for encapsulation and information hiding

. Generic stack ADT in ML
  . Cannot get at representation of stack
  . Reference to mkstack(1) will generate an error message
  . Only access through constants and operations
  . Module more sophisticated support with separate compilation

. Clu(1974)
  . Cluster is basis of support for abstrat data types
  . Provides both packaging and hiding of representation
   (cvt used to go back and forth between external abstract type and internal representation)
  . May have parameterized clusters where specify needed properties of type parameter

. Modules
  . General construct for information hiding
  . Two parts
   . Interface : A set of names and their types
   . Impelmentation :
     Declaration for every entry in the interface
     Additional declarations that are hidden

. Ex) Modula modules, Ada packages, ML structures

. Modules and Data abstraction
  . Can define ADT
   . Private type
   . Public operations
  . More general
   . Several related types and operations
  . some languages
   . Separate inferface and implementation
   . One interface can have multiple implementations

. Ada (approx 1979)
  . Designed via a U.S. DoD competition
  . Packages used to define abstract data types
  . Package together type, operations (and state) and hide representation
  . Provides support for parameterized packages(polymorphism)

. Modula-2
  . Modula (modular language) designed by Wirth in 1975 for programming small real-time control systems(no files, sets, or pointers)
  . Modula-2 is 1980 revision (influenced by Mesa at Xerox PARC)
   intended to synthesize systems programming with general purpose language supporting modern software engineering
  . Operating system for Lilith microomputer written in Modula 2
  . Minor changes to Pascal to simplify programming (reliability) and improve program readability and efficiency
  . Upward extension of Pascal to support large system design projects
   (Separately compiled and type checked modules)
  . Downward extension to allow machine-level programming and supports coroutines

. Modula-2
  . Opaque types (thos declared but undefined in Definition module) must be pointers or take no more space than pointers.
  . Compare and contrast Modula-2 and Ada on supporting abstract data types
   . Both can import from other units(modules or packages) and export items to other units
   . For external representations not mush difference
   . Private types in Ada force recompilation if implementation changes, but opaque types in Modula-2 do not.
     (구현이 바뀌었을 때 recompile여부가 다름.)
   . Internal representations almost identical
   . Generics make Ada more flexible - can use to create new instances of packages

. Generic Abstractions
  . Parameterize modules by types, other modules
  . Create general implementations
  . Can be instantiated in many ways
  . Language examples
   . Ada generic packages, C++ templates, ML functors
   . ML geometry modules in book
   . C++ Standard Template Library(STL) provides extensive examples

. ADA generic stack example
  . Stack represented internally in package
  . Data structure of stack is entirely hidden from user - there is no object of type stack available to user.

. C++ Templates
  . Type parameterization mechanism
   . template<class T> indicates type parameter T
   . C++ has class templates and function templates

  . Instantiation at link time
   . Separate copy of template generated for each type
   . Why code duplication?
     . Size of local variables in activation record
     . Link to operations on parameter type

. ex)
  . Monomorphic swap function
  . Polymorphic function template

. STL(Standard Template Library) for C++
  . Many generic abstractions
   . Polymorphic abstract types and operations
  . Useful for many purposes
   . Excellent example of generic programming
  . Efficient running time (but not always space)
  . Written in C++
   . Uses template mechanism and overloading
   . Does not rely on objects - No virtual functions

. Main entities in STL
  . Container : Collection of typed objects
   . Examples : array, list, associative, dictionary
   . Iterator : Generalization of pointer or address
   . Algorithm
   . Adapter : Convert from one form to another
     . ex) produce iterator from updatable container
   . function object : Form of closure("by hand")
   . Allocator : encapsulation of a memory pool
     . ex) GC memory, ref count memory

. Example of STL approach
  . function to merge two sorted lists
   . merge : range(s) x range(t) x comparison(u) -> range(u)
   . This is conceptually right, but not STL syntax.
  . Basic concepts used
   . range(s) - ordered "list" of elements of type s, given by pointers to first and last elements
   . comparison(u) - boolean-valued function on type u
   . subtyping - s and t mush be subtypes of u

. How merge appears in STL
  . Ranges represented by iterators
   . iterator is generalization of pointer
   . supports ++ (move to next element)
  . Comparison operator is object of class Compare
  . Polymorphism expressed using template
   template<class InputIterator1, class InputIterator2,
            class OutputIterator, class Compare>
   OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator1 last2,
                        OutputIterator result, Compare comp)

. Comparing STL with other libraries
  . C : qsort((void*)v, N, sizeof(v[0]), compare_int);
  . C++, using raw C arrays
   int v[N]
   sort(v, V+N);
  . C++, using a vector class;
   vector v(N);
   sort(v.begin(), v.end());

. Efficiency of STL
  . C나 C++ raw arrys qhek dhglfu Qkfmek.

. Main point
  . Generic abstractions can be convenient and efficient
  . But watch out for code size if using C++ templates

. Spaghetti Code
  . Fortran
  . Assembly와 거의 1:1로 mapping된다.
  . CONTINUE statement
     . 아무일도 하지 않고 goto의 label로만 사용함.
  . GOTO를 매우 남발하고 있어서 코드 읽기가 어렵다.
  . block내로 뛰어드는 일도 가능(과거 변수값 재활용 등)

. Structured Control
  . GOTO는 이해하기 어렵기 때문에 다른 것을 PL이 제공해보자
  . Dijkstra - "Goto considered hamful"
  . Control flow(structure jumps)
  . if then else end
  . while do end
  . for { }
  . case
  . Can't jump into the middle of a block
  . Activation Record 처리에 명확한 답이 없고 이상해지므로 compiler가 배제함

. Exceptions
  . Purpose
  . Jump out of a block or function invocation
     . Block내에서 문제를 해결할 수 없을 때 밖으로 나간다.  
     . 여러 단계의 block을 한번에 나간다.(non-local goto와 비슷)
  . Pass data as part of the jump
     . 벗어날 때 parameter를 jump
  . Return to a program point that was set up to continue the computation
     . 정해진 곳으로 return

  . Memory Management
  . Unnecessary activation record may be deallocated

  . raise = throw = abort part = jump
  . handler = catch

  . Static scope와 dynamic scope
  . variable은 static scope가 이해하기 쉽지만
     handler는 dynamic scope가 더 의미가 있다.
  . Static scope로 하게되면 library작성자나 callee가 결정해야 하는 데
     dynamic scope로 하면 library user나 caller가 뭘 할지 정할 수 있다.

  . ML : handle이 pattern match, type이 아닌 다른 특별한 것으로 취급됨
  . C++ : 어떤 type이든 throw하고 type에 따라 handle

  ex) overflow일 때
  . Numerator는 0, Denominator는 1을 return

  ex) Computing the inverse of a matrix
  . determinant가 0이 아닐 때만 inverse가 존재한다.
  . determinant를 먼저 구해 볼수도 있지만 inverse만큼 cost가 크다.
  . 따라서 inverse를 구하는 중간에 determinant가 0이면 raise exception
 
  . Exception은 언제 쓰나?
  . Error conditions에 쓴다.
  . Efficiency를 위해 쓴다.
     ex) short-circuit
     ex) 많은 값을 곱할 때
         . 중간 값이 0이면 더 이상 계산하지 않아도 된다.
         . 심지어 마지막 원소가 0이라도 stack pop시간을 아껴준다.

  . Typing
  . Exception은 무슨 type으로 할까?
     ML에서는 그냥 아무 type(type variable)이 되게 한다.

  . Resource allocation
  . Stack은 그냥 pop한다.
  . Heap은 ML에서는 garbage collector가 챙긴다.
     C에서는 user의 책임이다.
  . Lock, Thread등에서는 문제가 매우 골치아프다.
     (잘 챙기든지, 포기하든지 알아서해라.)

. Continuation
  . http://en.wikipedia.org/wiki/Continuation
  . 현재 value를 바탕으로 remaining work를 기록해둠.
  . Program optimization등에 이용됨.
  . upcall
  . callback
  http://en.wikipedia.org/wiki/Callback_%28computer_science%29
  . the rest of the computation to be performed after it.
  . Continuation으로 error(exception) handling도 가능하다.

. CPS(continuation-passing-style)
  . http://en.wikipedia.org/wiki/Continuation-passing_style
  . control이 continuation이라는 형식으로 통해 explicit하게 pass됨
  . k(Kappa) : continuation argument

. continuation-passing-form
  . function이나 operation이 continuation으로 pass되는 것
  . return 할 필요가 없다.
  . tail call과도 관련 지을 수 있다.
  . ex) fact(9)에서
  fact(8)의 continuation : lx.9*x
  fact(7)의 continuation : ly.(lx.9*x) (8*y)
  fact(6)의 continuation : lz.(ly.(lx.9*x) (8*y)) (7*z)
  . initial continuation : the identity function

. TCO(Tail call optimization)
  . http://en.wikipedia.org/wiki/Tail_call_optimization
  . Recursive call을 iterative로 바꿀 general한 방법은 없다.

. Fortran
  . recursive call이 불가능하다.

. caller : 함수를 부르는 측
. callee : 불린 측

. In-line block
  . function, procedure와 달리 block내에 block이 있어서 자연스럽게 그 block이 수행됨.
  . most simple block(가장 단순한 형태의 block)

. Nested function declaration
  . function내에서 function을 선언하는 것
  . C, C++에서는 지원하지 않는 다.
  (C++에서 Nested class는 지원함)

. Block
  . begin, end marker로 표시되는 프로그램 조각(a region of program text)
  . block의 시작마다 variable declaration이 있다.
  Memory allocation도 한다.
  . block의 끝마다 local variable을 없애고 memory를 deallocation시켜 memory를 아낀다.
  . nesting되야하고 partially overlap은 안된다.
  (if, for 등 모든 것들이 그렇다.)
  . 각 block은 Activation Record를 가진다.

. block의 종류
  . In-line block
  . function
  . procedure

. scope : 변수가 visible한 영역
. lifetime : 변수의 수명(allocation에서 deallocation사이)
. scope와 lifetime은 약간 다르다.
. a hole in the scope
  . lifetime이 expire되지 않았지만 scope상에서 가려져서 visbiel하지 않음.

. variable
  . local variable : 현재 block내에 선언됨
  . global variable : 현재 block 바깥에 선언됨
  . global variable은 항상 어떤 block의 local variable이다.

. scoping
  . global variable의 위치를 결정하는 문제
  . static scoping
  . 가장 가까운 block의 variable을 이용
  . Access Link를 따라가서 변수를 찾음.
  . Access link를 몇 단계 따라갈지는 compiler가 정해줌.
  . 최근 언어들이 채택하고 있음.

  . dynamic scoping
  . 가장 가까운 AR의 variable을 이용.
  . runtime에 일일히 stack frame을 뒤져 variable이 있는 지 확인함.
  . LISP이 채택한 방식

. AR(Activation Record, Stack frame)의 구성요소
  . Control link(CL)
  . Access link(AL)
  . Return address(RA)
  . Return value address(RVA)
  . Parameter
  . local variable
  . Intermediate result(Temporary storage)

. 그 외의 구성요소
  . Program Counter(PC)
  . Environment Pointer(EP)
  . Stack Pointer(SP)

. Control Link = Dynamic link
  . stack frame의 previous frame을 가리킨다.

. Access Link = static link
  . parent block을 가리킨다.
  . parent가 recursive call이었을 때는 가장 최근의 parent를 가리킨다.
  . (lexical scope에 따라 가리킨다.)
  . C는 nested function declaration이 안되므로 AL이 필요없다.
  (AL이 모두 global scope을 가리킬 것이므로)
  . 예상 시험문제 : 다음 프로그램을 보고 CL, AL 등을 연결하세요.

. Return address
  . call이 끝나면 돌아갈 주소(caller의 주소)

. Return value address
  . return시 value을 넣어 줄 곳

. Parameter
  . caller로 부터 넘어온 value

. Intermediate result
  . compiler가 복잡한 expression의 중간 결과를 임의로 저장한 것.
  . temporary value를 저장한다.

. Program Counter(PC)
  . 현재 code상에서 어느 줄을 수행하고 있는 지 나타낸다.

. environment pointer(frame pointer, EP, FP)
  . current stack(run-time stack), 새 activation record(AR)을 가리킨다.
  . 항상 index register에 넣어두기로 약속했다.

. stack pointer(SP)
  . stack의 top을 가리킴

. 사실 stack은 linked list처럼 생겼다.
  . previous node에 해당하는 것을 control link가 가지고 있다.
  . 그럼 왜 linked list가 아닌 stack이라는 이름으로 부를까?
  . linked list는 중간 원소를 없애거나 추가하기도 하지만
  . stack은 항상 top에서만 추가, 삭제를 한다.(LIFO)
  . 따라서 우리의 경우에는 top만 바꾸므로 stack으로 구현한다.

. 새 stack을 allocation(push)하는 instruction
  . M(SP) <- EP
  . EP <- SP
  . SP <- SP + sizeof(AR)

. stack을 deallocation(pop)하는 instruction
  . SP <- EP
  . EP <- M(EP)

. Parameter passing
  . formal parameter
  . declaration시 자리를 차지하는 것(place holder)
  . actual parameter
  . function call시 쓰이는 expression
 
  . call-by-value
  . actual parameter를 evaluation 한 후 r-value(value, contents fo address)를 복사한다.
  . Object가 클 때 비효율(inefficient)적이다.

  . call-by-reference
  . variable의 l-value(memory address)를 넘긴다.
  . object가 아주 작을 때(fit directly on stack) 비효율적이다.
  . 문제점 - parameter가 constant이거나 expression이면 이상해 진다.
  . aliasing이 생겨서 분석이 어렵다.
  . 해결책
     1. call-by-reference를 안쓴다.
     2. 그냥 내버려둔다. (User의 책임이다.)
     3. PL을 잘 design하여 compiler시 error를 낸다.

. Aliasing
  . 2개 이상의 name이 같은 object나 location을 가리킬 때

. Compiler의 중요한 임무
  . variable의 위치를 알아야 함.
  . 위치 : 어느 block(which block)인가 + 몇 번째인가(dispx, displacement x)

. caller가 할 일(AR 만들기)
  1. EP를 새 AR로 set
  2. RA set(자신의 현재 PC)
  . callee의 RA 위치 : EP + sizeof(caller's AR) + 2
  3. Actual parameter set
  . Actual parameter와 formal parameter의 순서는 동일하다.
  4. callee로 jump

. EP + sizeof(AR) = SP

. AR의 위치가 고정적인 이유
  . 그렇게 해야 caller가 callee를 부르고 여러 값들을 정확하게 넘길 수 있다.
  . CL, AL, RA, RVA, parameter의 크기는 고정적이고 compiler가 알아낼 수 있다.
  (caller가 아는 것들, 알아야 되는 것들)
  . 그 다음에 local variable, temporary 등 caller가 몰라도 되는 것을 적는 다.

. function and procedure(공통점과 차이점)
  . function : value를 return한다.(expression이다.)
  . procedure : value를 return하지 않는 다.(statement이다.)
  . 공통점 : side effect가 있다.
  . 거의 비슷하므로 대충 쓰기로 한다.

. Tail call
  . Return시 부른 function의 값을 바꾸지 않고 return하는 것
  (without any further computation)

. Tail recursive call
  . 자기 자신을 tail call하는 것
  . Optimization
  . set return value address to that of caller
  . control link도 더 위로 돌리자.
  . 결국 caller는 자신의 AR을 pop하고 overwrite하면 된다.
  . conclusion : iteravion loop와 같아 진다.

. Recursive call은 iterative로 바꿀 수 있지만 쉽지 않다.
  하지만 tail recursive call의 경우는 automatic하게 할 수 있다.

. AL 결정하기
  . caller가 형제 block을 call할 때는 자신의 Al를 callee의 AL에도 적는 다.
  . in-line block일 때는 AL과 CL이 같다.
  . 삼촌을 부를 때는 아버지의 AL을 set한다.
  . 아버지, 할아버지, 삼촌 이런 정보는 static structure이므로 compiler가 모두 안다.

. first-class function
  . http://en.wikipedia.org/wiki/Closure_%28computer_science%29
  . declared within any scope
  . passed as arguments to other functions
  . stored in data structures
  . returned as the values of other functions

  . functional programming을 구현하기 위해 필요하다.
  . higher-order function을 구현하기 위해 필요하다.

. closure
  . http://en.wikipedia.org/wiki/Closure_%28computer_science%29
  . a function created by a program at run time
  . (env, code) : activation record와 function code를 가리킨다.
  . function을 넘길 때 closure로 넘긴다.
  . C언어에서는 nested function declaration이 안되므로 closure가 필요없다.

. downward funarg problem
  . function argument로 function을 넘길 때
  . closure로 해결된다.
  . 다행히도 가리키는 Access Link는 항상 stack의 윗쪽을 향하므로 별 문제가 안된다.

. upward funarg problem
  . = upward fun-result problem
  . function의 return value로 function을 넘길 때
  . closure를 써야하고 stack도 바꿔야 한다.
  . stack discipline fails

. Garbage collection
  . Stack discipline이 깨지면 explicit deallocation이 힘들다.
  . 쓰이는 지, 안 쓰이는 지 garbage collection으로 판단한다.
  . Lisp, Scheme은 nested function declaration, higher-order function 때문에 garbage colection이 거의 필수이지는 C는 그렇지 않다.

. Language feature와 implementation construct의 관계
  . Block - Activation record with local memory
  . Nested blocks - Control link
  . functions and procedures - return address, return-result address
  . function with static scope - access link
  . function as arguments and results - closures
  . functions returned from nested scope - failure of stack deallocation order for activation records

. 2005년 중간고사 족보

3. 다음 용어를 설명하라.
1. Imperative programming language
  statement(instruction)들이 줄지어 있어서 어떤 일을 할 지 sequential하게 적는 다.
  assignment statement가 있다. (side-effect가 있다.)
  Von neumann architecture에서 기본적으로 나온다.

2. Binding and binding time
  binding : value와 identifier를 연결한다.

  binding time에는 static(early, compile time)과
  dynamic(late, virtual, run-time)이 있다.
  binding을 언제 결정할지 정하는 것.

3. Parse tree
  formal grammar에 따라 string을 sytatic structure를 가진 tree로 나타낸 것.
  parser에 의해 generate된다.

4. Derivation
  parse tree로 나타낼 수 있는 방법의 한 종류,
  left-derivation과 right-derivation이 있다.
  left-derivation에서는 항상 left child쪽으로 derivation을 하고
  right-derivation에서는 항상 right child쪽으로 derivation을 한다.

5. LR(k)
  LR parser : CFG의 bottom-up parser의 일종
  left에서 right로 읽어 right-derivation을 한다.
  k는 unconsumed look ahead input symbol의 갯수

6. ambiguity of grammars(ambiguous grammar)
  parse tree를 한 가지 이상의 방법으로 generate할 수 있을 때
  어떤 방식을 선택할 지 ambiguity가 발생한다.
  해결을 위해서는 grammar를 ambiguity없이 다시 쓰거나
  precedency나 associativity를 정해 준다.

7. dynamic scope
  runtime에 bing이 결정됨.
  함수 call 순서의 영향을 받음.
  perl, common lisp등에서 사용.

8. virtual machine
  http://en.wikipedia.org/wiki/Java_virtual_machine
  언어와 실제 machine의 중간 쯤 되는 가상적인 것.
  중간코드와 실제 machine사이에서 돈다.
  Portability 등을 위해 사용되기도 한다.
  Java virtual machine 같은 예가 있다.

9. Overloading
  함수나 operator의 argument(input, operand) type에 따라
  각자에 맞는 알고리즘(다른 알고리즘)을 적용하여 계산한다.
  같은 name을 가졌지만 type에 따라 다른 일을 한다.

10. aliasing
  memory 장소(값)을 하나 이상의 변수로 가리키는 것

11. value model of variabls
  http://en.wikipedia.org/wiki/Variable

12. referentially transparent (referential transparency)
  subexpression을 의미의 변화없이 value로 substitute할 수 있음.

13. polymorphism
  여러 type에 대해 동일한 algorithm을 적용해서 각 input type과 관련된 output을 줄 수 있음.

14. Short-circuiting
  필요하지 않은 것은 evaluation하지 않음.
  boolean or : e1이 true이면 e2는 eval하지 않고 true를 return함 e2가 undefined라도 상관없음.

15. side effect
  어떤 function이 return value외에 다른 값을 바꿀 때.
  assigment statement가 있으면 side effect가 발생한다.
  일반적으로 imperative programming language는 side effect가 있고
  functional language는 side effect를 최소화하려고 한다.
  Pure lisp의 경우 side effect가 없다.

16. tail recursion
  recursion을 iteration으로 쉽게 바꿀 수 있는 special case
  stack에 값을 누적하지 않으므로 spack space를 줄일 수 있다.

17. type system
  type check를 하는 system
  type간의 관계를 정의하고 각 변수, input, output type을 검사한다.
  type inference, casting, coercion을 할 수도 있다.

  http://en.wikipedia.org/wiki/Type_checking
  value와 variable을 type으로 classify한다.
  각 type들을 어떻게 manipulate하고 그들이 어떻게 interact하는 지 정의한다.

18. strong typing
  conservative하게 type을 check함(sound)
  이것을 통과한 것에 대해서는 항상 type-safe하다고 할 수 있다.
  영원이 돌거나 의도한 결과를 준다.

19. coercion vs casting
  http://en.wikipedia.org/wiki/Type_casting
  coercion : implicit type conversion
  compiler가 automatic하게 바꾼다.

  casting : expilcit type conversion
  checked : type을 바꾸기전에 가능한 것인지 확인한다.
  unchecked : check를 안한다.
  bit pattern : bit representation이 그냥 복사된다.

20. control flow statement 중 selection statement의 종류를 나열하라.
  . control flow statement
  http://en.wikipedia.org/wiki/Control_flow
  sequential order에 변화를 줄 수 있는 statement
  labels, goto, subroutines, if then else, loop, conditions, exception, nonlocal goto
  . selection statement
  if then, if then else, else if, switch-case, computed goto, arithmetic if,

21. subroutine closure
  http://en.wikipedia.org/wiki/Closure_%28computer_science%29
  . a subroutine bundled together with a referencing environment
  . a closure is a function that refers to free variables in its lexicla context.

22. applicative-order evaluation
  http://en.wikipedia.org/wiki/Applicative-order_evaluation
  evaluation strategy의 하나.
  function의 argument가 left to right 순의 post-order traversal로 reduce됨.
  function bod에서 가능한한 많은 evaluation을 reduce함.

23. Name equivalence of type checking
  name이 같을 때 같은 type으로 본다.
  C의 record, ada, modula-2

  structural equivalence : structure가 같으면 같은 type으로 본다.

24. derived type vs subtype in ADA

25. Module type

. 2004년 중간고사 족보
1. 다음 용어를 설명하라.
  1. type inference
    strongly statically typed programing lagnuages의 특성
    값에 type이 annotation되어 있지 않아도 자동으로 값의 type을 추론해냄.
    각 값의 관계에 따라 type에 관한 equation을 만드록
    그 equation을 풀면 된다.    

  2. coercion
  3. virtual machine  
    http://en.wikipedia.org/wiki/Virtual_machine
    User와 platform 환경 사이를 virtualize함.

  4. type compatibility by name
  5. overloaded operator (operator ad-hoc polymorphism)
    http://en.wikipedia.org/wiki/Operator_overloading
    operator의 argument의 type에 따라 다른 implementation을 사용하는 것

  6. dangling pointer
    http://en.wikipedia.org/wiki/Dangling_pointer
    적절한 type의 object를 가리키고 있지 못하는 pointer,
    잘못된 공간을 가리키고 있는 pointer
    unpredictable한 결과를 초래할 수 있다.

  7. axiomatic semantics
    수학 logic을 이용하여 computer program의 correctness을 prove하는 것

  8. interpreter
    http://en.wikipedia.org/wiki/Interpreter_%28computing%29
    a computer program that executes other programs.
    source code를 바로 실행시킴.
    반면에 compiler는 translate만 하고 execution은 안함.
    prototyping이나 test시에 간편하게 쓰임.

  9. aliasing
    하나의 값을 2개 이상의 변수가 가리키는 것.

  10. stack-dynamic array
     http://www2.hawaii.edu/~cheungca/ICS313/hw6/2031.txt
     Stack-dynamic array have dynamically bound subscript ranges and dynamic storage allocation at run time and have greater flexibility not requiring array size until used.
     Fixed heap-dynamic array have dynamically bound subscript ranges and dynamic storage allocation, but are static after storage allocation on a heap, rather than stack, and are bound when at user-program request.  Heap-dynamic array have dynamic binding of subscript ranges and storage allocation, can change, if flexible, and can adapt to the size required.

  11. orthogonality in programming language
     어떤 조합이든 valid하게 정의되어 사용될 수 있는 것,
     record의 array, int array, float array, array의 record 등이 모두 가능.
     primitive type과 combination, operator와 operand 등.

  12. enumeration type (enumerated type)
     http://en.wikipedia.org/wiki/Enumerated_type
     programmer가 a finite list로 data type의 value를 정의한 것.
     C언어에서는 enum으로 정의가능.

  13. reference count for memory management
     각 memory cell이 자신을 가리키고 있는 reference(pointer)의 갯수를
     가지고 있음. reference count가 0이 되면 garbage collect됨.

  14. grammar가 ambiguous하다.
     http://en.wikipedia.org/wiki/Ambiguous_grammar
     어떤 string이 여러가지 방법으로 parse tree가 생성될 수 있다.

2. subtype and derived type
  http://en.wikipedia.org/wiki/Subtype
  supertype에 관련되어 만들어진 type.
 
  derived type
  original type과 구조적으로 같지만 다른 type으로 정의된 것.
  의도적으로 두 개를 별개의 type으로 보기 위해 이름을 다르게 붙인 것.

  subtype과 derived type의 공통점 : 원래 type으로 부터 나온다.
  원래 type의 구조를 포함하고 있다.

  차이점 : derived type은 원래 type과 구조가 같지만
  subtype은 원래 type에 일부 구조를 더 할 수 있다.

3. 각 binding time에 일어나는 binding을 여러분이 아는 language에서 예를 하나씩 들어라.
  1. language design time

  2. language impelmentation time

  3. compile time by translator(compiler)

  4. runtime on entry of subprogram

  5. runtime at arbitrary point of execution

4. static array int A[LB1:UB1, LB2:UB2]가 있을 때
  어떤 array element A[i,j]를 access하는 공식을 i, j의 함수로 나타내라.
  필요한 상수는 정의하여 사용하고 그 값을 구하는 방법을 명기하라.
  (row-major로 나열하라.)

  row-major order
  http://en.wikipedia.org/wiki/Row_major

  NUMROWS = LB1 - UB1 + 1
  NUMCOLS = LB2 - UB2 + 1

  A[i, j]

  row-major일 때
  offset = (i - LB1) * NUMCOLS + (j - LB2)

  column-major일 때
  offset = (j - LB2) * NUMROWS + (i - LB1)

5. BNF로 정의된 grammar에 대하여 답하라.
  <S> -> a <S> a | b <S> b | c
  (1) parse tree 그리기

  (2) grammar로 정의된 L를 우리말로 쓰기

  (3)
  . denotational semantics
  M('c') = 0
  M(a <S> a) = 2 * M(<S>)
  M(b <S> b) = 2 * M(<S>) + 1

  'babcbad'의 의미는 무엇인가?
  2 * (2 * (2 * (0) + 1)) + 1 = 5
  0을 2배해서 1 더하고 그것을 2배하고 다시 2배해서 1을 더한다.
  => 5

  (4) <S> -> (a|b)<s>(a|b) | c
  이 grammar는 원래 grammar와 같은 가?
  다르다.
  'bca'라는 string의 경우 원래 grammar에서는 안되지만
  이 grammar에서는 된다.
  증명) 원래 grammar에서는 a,b가 항상 짝수개만 올 수 있다.

6.
  (1) union이란 무엇인가?
     http://en.wikipedia.org/wiki/Union_%28computer_science%29
     여러 종류의 type을 하나의 장소에 넣을 수 있다.
 

  (2) 다음과 같은 program segment가 있을 때, 이 언어는 왜 compile time에
     type compatibility를 check 할 수 있는 지/없는 지 이유를 말하라.

     union (real, int) chameleon;
     int intvar;
     real reavar;
     chameleon = intvar;
     ............
     realvar = chameleon;

     프로그램을 직접 수행하지 않고는 언제 chameleon이 int나 real로 되는 지
     예측할 수 없다.

  (3) 이러한 union type의 변수가 포함된 statement에서 type이 일치하는 지를
     runtime에는 check할 수 있게 하는 방안을 설명하라.
     union type의 변수에 tag를 달아서 현재 어떤 type의 값을 저장했는 지 기록한다.
     assign시마다 assign하는 값의 type을 적어둔다.

. Algol 60
  . Basic language of 1960
  . Simple imperative language + functions
  . Successful syntax, BNF - used by many successors
     . statement oriented (statement by statement)
     . begin .. end blocks (like C { } )
     . if .. then .. else
  . recursive functions and stack storage allocation
  . fewer ad hoc restrictions than fortran
     . general array references : A[x+B[3]*y]
     . orthogonality : 간단한 몇 개의 primitive가 어디든 적용된다.
       . 어떤 type이든 array가 됨
       . 어떤 type이든 pointer가 됨
  . Type discipline was imporved by later languages. (type을 강요함)
  . Very influential but not widely used in US (유럽에서는 좀 씀.)
. Fortran은 IF(B) stmt, (else가 없다.)
  . IF (exp) 30, 40, 50 (arithmetic if, -,0,+에 따라 goto함)
. Fortran은 변수 선언 안해도 됨.
  => 변수명을 쓰다가 오타가 나면 새 변수가 생겨버림.(실수 확률이 높다.)

. Algol 60 Sample
  . no array bounds
  . end; 바로 앞 stmt에 semicolon이 없다.
  . return command가 없다. procedure명과 같은 변수명에 assign

. Algol Joke
  . Question
  . Is x:= x equivalent to doing nothing? (C와 다르다.)
  . equivalent가 아니고 recursive call일 수도 있다.
  integer procedure p;
  begin

  p := p
  앞의 p : return value p에 assign(l-value)
  뒤의 p : procedure p를 recursive call(r-value)
  end;

. Algol의 모든 variable의 reference는 자동으로 dereference된다.
  int ref ref x ; (= int **p)
  int y;
  y = x + 1;이라고 적으면 C의 y = **x + 1과 같다.
  automatic dereference를 한다.

. Some trouble spots in algol 60
  . Type discipline improved by later languages
  . parameter types can be array
     . no array bounds
  . parameter type can be procedure
     . no argument or return types for procedure parameter

     int procedure f(x, y, g)
         int x, y;
         procedure g;

     f : int * int * fun -> int
     g : don't care

  . Parameter passing methods
  . Pass-by-name had various anomalies
     . "Copy rule" based on substitution, interacts with side effects
  . Pass-by-value expensive for arrays(전부 copy한다.)
  . Some awkward control issues
  . goto out of block(non-local goto) requires memory management
  . non-local goto : exception handlgin에서 주로 사용한다.

. Algol 60 Pass-by-name
  . Substitute text of actual parameter
  . Unpredictable with side effects
  . Ex)
  procedure inc2(i, j);
     integer i, j;
     begin
       i := i+1;
       j := j+1
     end;
  inc2(k, A[k]);

  i=>k, j => A[k]로 치환

     begin
       k := k+1;
       A[k] := A[k]+1
     end;

  Is this what you expected?
  (따라서 원하지 않은 결과가 나타난다.)
  . 특징 - 별 짓을 다할 수 있다. (젠센's device)

. Algol 68
  . Considered difficult to understand
  . idiosyncratic(기이한, 색다른) terminology
     . types were called "modes"
     . arrays were called "multiple values"
  . vW grammars instead of BNF
     . context-sensitive grammar invented by A. van Wijngaarden
       http://en.wikipedia.org/wiki/Context-sensitive_grammar
       ex)
       S → abc | aSBc
       cB → Bc
       bB → bb

       a^n b^n c^n, a^n b^n c^n d^n 같은 것도 표현할 수 있다.
       (context-free grammar로 안되는 것)
       Noam-chomsky가 제안했다. CFG보다 표현력이 좋고 TM보다는 덜하다.
  . elaborate type system
  . complicated type conversions
  . Fixed some problems of algol 60
  . eliminated pass-by-name
  . Not widely adopted 

. Algol 68 Modes
  . Primitive modes
  . int, real, char, bool, string, compl(complex), bits, bytes, sema(semaphore), format(I/O),
     file
  . compound modes
  . arrays, structures, procedures, sets, pointers
  . Rich and structured type system is a major contibution of algol 68
  . Orthogonaloty : primitive mode와 compound mode의 모든 combination이 가능함.

. Other features of algol 68
  . Storage management
  . local storage on stack
  . Heap storage, explicit alloc and garbage collection(free는 알아서 함)
  . Parameter passing
  . pass-by-value
  . Use pointer types to obtain pass-by-reference
  . Assignable procedure variables
  . Follow "orthogonality" principle rigorously

. Pascal - Algol이 너무 복잡해서 type을 단순하게 만들고 교육하기 쉽게함.
  . http://en.wikipedia.org/wiki/Pascal_programming_language
  . Revised type system of algol
  . Good data-structuring concepts
     . records, variants, subranges
  . More restrictive than algol 60/68
     . procedure parameters cannot have procedure parameters
  . Popular teaching language(교육용)
  . Simple one-pass compiler
  . gcc는 매우 여러번 program을 본다.

. Limitations of pascal
  . Array bounds part of type
  procedure p(a:array[1..10] of integer)
  procedure p(n:integer, a:array[1..n] of integer) -> illegal, 제약이 너무 심하다.
  . int a[10], b[11] -> a와 b를 다른 type으로 간주함.
  . Attempt at orthogonal design backfires
  . parameter must be given a type
  . type cannot contain variables
  . How could this have happened? emphasis on teaching
  . Not successful for "industrial-strength" projects
  . Kernighan - Why Pascal is not my favorite language
  . Left nich for C; niche has expanded.
  . 하나의 파일에 program을 다 써야 한다.

. C programming language
  . Designed for writing unix by dennis ritchie
  . evloved from B, which was based on BCPL
  . B was an untyped language; C adds some checking
  . Relation between arrays and pointers
  . An array is treated as a pointer to first element
  . E1[E2] is equivalent to ptr dereference *((E1)+(E2))
  . pointer arithmetic is not common in other languages.
     (이해가 어렵다. ex - p = p+ 1 , p는 pointer, p의 size에 따라 +의 의미가 다르다.)
  . Ritchie quote "C is quirky, flawed, and a tremendous success."
  (나쁘고 변덕스러운 언어)
  . DEC의 PDP machine의 OS를 다시 만듬 : Unix
  . Unix를 위해 만든 언어 : C
  . C는 assembly도 끼워 넣을 수 있다.

. ML
  . Typed programming laguage
  . Intended for interactive use
  . Combination of Lisp and Algol-like features
  . Expression-oriented
  . Higher-order functions
  . Garbage collection
  . Abstrac data types
  . Module system
  . Exceptions(exception handler)
  . General purpose non-C-like, not OO language
  . Related languages : haskell, OCAML

. Why study ML?
  . Learn an important language that's different
  . Discuss general programing laguages issues
  . types and type checking
     . general issues in static/dynamci typing
     . type inference
     . polymorphism and generic porgramming
  . Memory management
     . static scope and block structure
     . function activation records, higher-order functions
  . Contrl
     . Froce and delay
     . Exceptions
     . Tail recursion and continuations
  . 교과서 저자가 ML을 좋아함.

. History of ML = Meta language
  . http://en.wikipedia.org/wiki/ML_programming_language
  . Robin Milner
  . Logic for Computable functions
  . Meta langage of the LCF system(목적)
  . Theorem proving
  . Type system
  . Higher-order functions
  . LCF : Logic for Computable Function
  http://en.wikipedia.org/wiki/LCF_theorem_prover

. Logic for computable functions
  . Dana scoot, 1969 - recursive call의 converge를 증명(?)
  . Formulate logic for proving properties of typed functional programs
  . Milner
  . Project to automate logic
  . Notation for programs
  . Notation for assertions and proofs
  . Need to write programs that find proofs
     . Too much work to construct full formal proof by hand
  . Make sure proofs are correct

. LCF proof search
  . Tactic : function that tries to find proof
  tactic(formula) =
  1. succeed and return proof
  2. search forever(solution space가 infinite하게 크기 때문)
  3. fail

. Express tactics in the Meta-language(ML)
. use type system to facilitate correctness
  (type이 매우 유용하더라.)

. logic에서 중요한 것.
  . 어떤 formula가 이미 주어진 axiom과 theorem으로부터 항상 true임을 증명하는 것.
  . proof를 automatic하게 해보자.

. Tactics in ML type system
  . Tactic has a functional type
  . tactic : formula -> proof
  . type system mush allow "failure"
  . Tactic : function that tries to find proof
  tactic(formula) =
  1. succeed and return proof
  2. search forever(solution space가 infinite하게 크기 때문)
  3. fail and raise exception(!!)
 
. type system이 logic formula에 매우 편하다.

. Higher-order functions
  . Tactic is a function
  . Method for combining tactics is a function on functions

. Basic overview of ML
  . Interactive compiler : read-eval-print
  . Compiler infers type before compiling or executing
  . type system does not allow casts or other loopholes.

. Compound types
  . Tuples - Heterogeneous fixed size
  . (4, 5, "Hi") : int * int * string
  . Lists - Homogeneous, not fixed size
  . nil
  . 1::[2,3,4]
  . Record
  . {name = "Fido", hungry=true}
     : {name : string, hungry : bool}

. Patterns and declarations
  . patterns can be used in place of variables
  <pat> ::= <var> | <tuple> | <cons> | <record>
  . value declarations
  . general form
    val <pat> = ,exp>

. Functions and pattern matching
  . Anonymous function
  fn x => x+1; Like lisp lambda

. list reverse
  . stack에 넣고 다시 꺼내면 된다.

. variable and assignment
  . General terminology : l-values and r-values
  . assignment
  . identifier on left refers to a memory location, called l-value
  . identifier on right refers to contents, called r-value
  . variables
  . Most languages
     . A variable names a stroage location
     . Contents of location can be rea, can be changed
  . ML reference cell
     . A mutable cell is another type of value
     . Explicit operations to read contents or change contents
     . seperates naming(declaration of identifiers) from variables

  . ML imperative constructs
  . ML reference cells
     . Different types for location and contents
       x : int , non-assignable integer value
       y : int ref, location whose contents must be integer
       !y , the contents of location y
       ref x , expression creating new cell initialized to x
  . ML assignment
     . operator := applied to memory cell and new contents
  . ex)
     y := x+3, place value of x + 3 in celly; requires x:int
     y := !y + 3, add 3 to contents of y and store in location y
  . 모든 variable은 initialize 되어야 한다.

. Core ML
  . Patterns
  . Declarations
  . Functions
  . Polymorphism
  . Overloading
  . Type declarations
  . Exceptions
  . Reference cells

. General discussion of types
  . What is a type?
  . compile-time vs run-time checking
  . conservative program analysis
  (조금만 이상하면 그냥 틀렸다고 한다.)
  compile time에 모든 것을 알 수는 없다.
  (halting problem과 동치?)

. Type inference
  . Good example of static analysis algorithm
  . Will study algorithm and examples

. Polymorphism
  . Polymorphism vs overloading
  . Uniform vs non-uniform impl of polymorphism

. Type
  . Semantic analysis에서 가장 먼저하는 것
  . 최근 PL의 가장 큰 break through
  . A type is a collection of computable values that share some structural property.
  . well-define되는 것만 type이고 well defined 안되면 type이 아니다.
  . type : well define된 value의 set과 그것들에 가능한 operation을 모은 것.
  . 어떤 언어든 manual 처음은 각 언어의 primitive type을 설명함.
  (그만큼 type이 중요하다는 뜻.)

. Uses for types (type check)
  . Program organization and documentation
  . seperate types for separate concepts
     . represent concepts from problem domain
  . Indicate intended use of declared identifiers
     . Types can be checked, unlike program comments

  . Identify and prevent errors
  . Compile-time or run-time checking can prevent
     meaningless computations such as 3 + true

  . support optimization
  . ex : short integers require fewer bits
  . access record component by known offset
  . type이 틀렸다면 아마 error일 것이다.
  . type이 정해지면 field(layout)이 정해져서 structure에서 offset을 정할 수 있다.
  . bit-pattern(binary representation)이 type이 있어야 의미가 결정된다.
      
. Type erros
  . Hardware error
  . Fuction call x() where x is not a function
     (x가 적절한 address가 아니고 엉뚱한 instruction이다.)
  . May cause jump to instruction that does not contain a legal op code

  . Unintended semantics
  . int_add(3, 4.5) - 다른 representation을 연산하면 당연히 이상한 값이 나온다.
  . Not a hardware error, since bit pattern of float 4.5
     can be interpreted as an integer
  . Just as much a program erros as x() above

. General definition of type error
  . A type error occurs when execution of program
  is not faithful(충실하지 않음) to the intended(의도한) semantics
  . Do you like this definition?
  . Store 4.5 in memory as a floating-point number
     location contains a particular bit pattern
  . to interpret bit pattern, we need to know the type
  . If we pass bit pattern to integer addition function,
     the pattern will be interpreted as an integer pattern
  . type error if the pattern was intended to represent 4.5

. Type system : type check를 하는 systme
. Type system을 통과했다. = type error가 없다.
  = 우리가 원하는 semantic대로 움직인다.
  물론 logic이 틀렸으면 다른 값이 나올 것이다.

. Compile-time(static check)
. run-time checkcing(dynamic check)

. Lisp uses run-time type checking
  . (car x) make sure x is list before taking car of x

. ML uses compile-time type checking
  . f(x) must have f:A->B and x:A

. Basic tradeoff
  . Both prevent type errors
  . Runtime checking slows down execution
  . Compile-time checking restricts program flexibility
  . Lisp list : elements can have different types
  . ML list : all elements must have same type
  . variable이 runtime에 type이 바귈까? 언어에 따라 다르다.

. Expressiveness(표현력)
  . In Lisp, ew can write function like
  (lambda(x) (cond ((less x 10) x) (T (car x))))
  => x가 10보다 크거나 같으면 9car 10)이 안되므로 type error
  . some uses will produce type error, some will not
  . dynamic하면 run-time check이면 expressiveness는 커지지만
  어떻게 될지 모른다.

. Static typing always conservative(soundness)
  . Cannot decide at compile time if run-time error will occur
  (halting problem의 undecidability와 관련있다.)
  . sound < A < completeness < U
  . A : 우리가 check하는 성질
  . sound and complete = A

. type check를 통과한 program
  1. 내가 원하는 결과가 나오거나(옳은 결과)
  2. 영원히 끝나지 않음.

. soundness : yes라고 말하면 반드시 yes
. completeness : yes인 것은 항상 yes라고 대답, no인 것도 가끔 yes로 대답할 수 있음.

. relative type-safety of languages
  (type-safe language = sound = strongly typed)
  . Not safe : BCPL family, including C and C++
  . BCPL : 거의 type이 없다.
  . Cast, pointer arithmetic(가장 악명높다.)
  . Almost safe : Algol family, pascal, Ada.
  . Dangling pointers (allocate는 문제 없으나 free가 문제)
     . Allocate a pointer p to an interger, deallocate the memory
       referenced by p, then later use the value pointed to by p
     . No language with explicit deallocation of memory is fully type-safe
  . Safe : Lisp, ML, Samlltalk, and Java
  . Lisp, Smalltalk : dynamiclly typed(run-time)
  . ML, Java : statically typed(compile-time)
  . ML, Java는 pointer가 없고 reference만 있다.

. Type checking and type inference
  . Standard type checking
  . Look at body of each function and use declared types of identifies to check aggrement.
  . Type inference
  . Type을 안 적어도 알아냄.
  . Look at code without type information and figure out what types could have been declared.
  . ML is designed to make type inference tractable.

. Motivation
  . Types and type checking
  . Type systems have improved steadily since algol 60
  . Important for modularity, compilation, reliability
  . Type inference
  . Cool algorithm
  . widely regarded as important language innovation
  . ML type inference gives you some idea of how many
     other static analysis algorithms work

. Application
  f(x)
  @(f(x)) : r  (parent)
  f : s (left-child)
  x : t (right-child)

  s = t -> r

  t : domain
  r : range(codomain)

. Abstraction
  lx.e

  l : s->t (parent)
  x : s (left-child)
  e : t (right-child)
 
. Types with type variables
  . Assign tpes to leaves
  . Propagate to internal nods and generate constraints
  (위로 propagete한다.)
  . solve by substitution

. Use of Polymorphic function
  . argument type에 따라 return type이 결정됨, 여러 종류를 넣을 수 있다.
  . most general form - 더 general하게 적을 수 없다.
  ex)
  (int -> t) -> t : general form: 가장 simple하고 모든 것을 나타냄.
  : (int -> int) -> int
  : (int -> (s->t->r)) -> (s->t->r)

. Main points about type inference
  . Compute type of expression
  . Does not require type declarations for variables
  . Find most general type by solving constraints
  . leads to polymorphism
  . Static type chcking without type specifications
  . May lead to better error detection than ordinary type checking
  . Type may indicate a programming error even if there is no type error

. ML에서는 type inference가 잘 되게 type system이 define되있다.
  (C는 그렇지 않다.)

. Polymorphism vs overloading
  . Parametric polymorphism(같은 algorithm)
  . single algorithm may be given may types
  . Type variable may be replaced by any type
  . Overloading (다른 algorithm)
  . A single symbol may refer to more than one algorithm
  . Each algorithm may have different type
  . Choice of algorithm determined by type context
  . Types of symbol may be arbitrarily different

. Parametric Polymorphism : ML vs C++
  . ML polymorphic function (implicit polymorphism)
  . Declaration has no type information
  . Type inference : type xpression with variables
  . Type inference : substitute for variables as needed
  . C++ function template(explicit polymorphism)
  . Declaration gives type of function arg, result(type parameter의 name을 줌)
  . Place inside template to define type variables
  . Function application : type checker does instantiation

. ML also has module system with explicit type parameters

. Example : swap two values(polymorphism)
  . ML : 모든 변수는 pointer임. (function이 1 copy면 됨.)
  . swap is compiled into one function
  . typechecker determines how function can be used

  . C++ : stack에 들어가는 변수가 있기 때문에 swap function의 size가 달라짐.
  . 그래서 type에 따라 function이 여러 copy가 필요함.
  . swap is compiled into linkable format
  . linker duplicates code for each type of use

  . Why the difference
  . ML ref cell is passed by reference(pointer), but
     local x is on stack, size depends on type

. Another example
  . C++ polymorphic sort function
  . What parts of implementation depend on type?
  . Indexing into array(type의 size가 다름)
  . Meaning and implementation of <
  . Swap

. ML Overloading
  . Some predefined operators are overloaded
  . User-defined functions must have unique type
  (User defined는 polymorphic일 수는 있으나, overloading은 안됨)
  . Why is a unique type needed?
  . Need to compile code => need to know which +
  . Efficiency of type inference
  . Aside : general overloading is NP-complete

. Summary
  . Types are important in modern languages
  . Program organization and documentation
  . Prevent program errors
  . Provide important information to compiler
  . Type inference
  . Determine best type for an expression, based on
     known information about symbols in the expression
  . Polymorphism
  . Single algorithm (function) can have many types
  . Overloading
  . Smbol with multiple meanings, resolved at compile time

. type
  . a collection of computational entities that share some common property
  . naming and organizing concepts
  . making sure that bit sequences in computer memory are interpreted consistently.
  . providing information to the compiler about data manipulated by the program

. type inference하는 법
  . 일단 lambda calculus로 바꾼다.

  . lambda lx.y
  l이 parent가 됨 : s
  left child는 bound variable(x) : t - node를 그리는 것이 아니라 leaf node와 잇는 다.
  right child는 function body(y) : u
  s = t -> u

  . function : f(x) =>  f = x -> f(x)  => lx.(f x)
  @이 parent가 됨 f(x) : s
  left child는 f : t
  right child는 x : u
  t = u -> s

  . + : int -> int -> int

  . recursive function의 경우 argument가 여러번 쓰이는 경우 lambda에서 여러개 잇고 각 node들을 같은 type variable로 적는 다.