속눈썹맨의 블로그

. 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한 방법은 없다.

. 오늘 소개한 논문 2편
Yin Li, Jian Sun, Chi-Keung Tang and Heung-Yeung Shum. Lazy Snapping. SIGGRAPH 2004. (ACM Transaction on Graphics)  (Video 19M)
http://research.microsoft.com/research/pubs/view.aspx?pubid=1266
http://research.microsoft.com/~jiansun/papers/LazySnapping_SIGGRAPH04.pdf
http://research.microsoft.com/~jiansun/videos/ImageCompletion_tiny.wmv

Jian Sun, Lu Yuan, Jiaya Jia and Heung-Yeung Shum. Image Completion with Structure Propagation. SIGGRAPH 2005 (Video 56M).
http://research.microsoft.com/~jiansun/papers/ImageCompletion_SIGGRAPH05.pdf

. 참석자
신성용, 좌경룡, 홍세준, 최성희, 한환수, 김진수 교수님을 포함한
10여명의 CS 교수님들과 터만홀을 가득 채운 학생들.

. 관련 분야
Signal processing, Image processing, Computer Vision, Computer Graphics

. MSRA 소개
1998년 베이징에 설립, 200여명의 researchers, 2,000명의 intern students.
거기 있는 유명한 사람들 : SGI 설립자, IBM Deepblue 설계자 등..
주로 computer Graphics관련 분야를 집중적으로 연구함.
(UI, Digital Media, Digital Entertainment, Networking and systems, searching and mining)
중국 학생이 70%이상, official language는 english
2005년 Siggraph에 9편, SIGIR에 12편이 실림.
(전체 논문의 10%에 해당하는 엄청난 양임.)
World's hottest lab 등으로 잡지에 소개됨.

. TTG(Technology Transfor Group) : Parachut group
  Research를 product로 바꿈.                                  

. Dr. Harry Shum
CMU Robotics 전공, 4년전 신성용 교수님초대로 KAIST 방문
Managing Director MSRA(1999~2006)

. Prior, Context and Interactive Computer Vision
  완전 자동이 아니라 약간 step back해서 User의 입력을 약간 받아서
  쉽게 feedback해주고 잘 해보자.

. IBM : Image Based Modeling

. Lazy Snapping
Just draw two lines
In line와 out line만 그리면 됨.
Red line : What you want
Blue line : What you don't want
Lazy : 부지런하게 모든 boundary를 그리지 않고 선만 대충 그음.
Interactive Graph Cut

Divide and Conquer : Input -> Coarse Boundary -> Refine Boundary
Stroke Drawing <-> Graph cut Algorithm
Graph cut problem -> Per-Pixel Graph cut 대신 Pre-segmentation first
Energy Minimization E(x) = E1(Xi) + lE2(Xi, Xj)
E1 : difference
E2 : Similarity

Noting new algorithm, Present New system.

. 논문 잘 쓰는 법
Write -> Intoducting, Abstract, Summary -> Title
Good title is short title => 2 words, end with ing

. Image completion
Small Missing : Pixel-level, PDE based
Large Missing : how?
Curve-based : BP(Belief propagation) Algorithm
Our Motivation : Missing salient structures, fill-in
Abstract window, curve - a few curves - human specify that.
Structures completion befor texture complete
Fragment-based Image completion, Image Repairing, object Removal

Node Energy, Coherence Energy => Dynamic Programming
Graph Labeling, discretize nodes
Decouple Image into two part

Multiple Intersecting Curves
Loopy Belief Propagation
Tour Into pictures도 쉽게 가능

사진을 2장 찍은 것이 아니라 object를 지우고 그 부분을 메꿈.
자세히 비교하면 이상할 수도 있지만 결과 사진만 보면 매우 그럴듯 함.
걸리적거리는 사람이나 물체를 깔끔하게 지워버릴 수 있다.
Boundary를 바꾸고 싶을 때 가리고 새로 그리기만 하면 된다.

. 감상
마치 무슨 마법이나 장난을 보는 것 같다.
이런 신기한 툴이라면 누구나 써보고 싶어할만한 것 같다.
연구자나 사용자 모두 직관적이고 매우 재미있어할 수 밖에 없겠다.

지겨운 algorithm이나 math가 이런 멋진 결과들을 가져오다니.

. 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

. 조원 : (주한별, Linda), (김지혜, 이춘석 tclab)
. Color2gray : Salience-Preserving color removal
  . gray로 바꾸면 intensity만 남아 안 보이게 되는 것이 있다.
  (Intensity가 같고 chrominance만 다른 경우)
  . Intensity를 희생하더라도 차이가 구분되게 한다.
  . Chrominance difference -> luminance
  . f(g) = sigma((i,j) in k, ((gi - gj) - dij)^2)
  . d : chrominance difference
  . f(g)를 minimize하는 g를 찾으면 된다.(optimization)
  . 색, 인지과학이용.(human visual sensitivity)

. 조원 : (김윤영 tclab)
. Feature Preserving Regular Remeshing
  . surface remeshing : 3D mesh를 remesh해서 다시 3D로 만듬.
  . mesh : polygon으로 정의된 연결 집합
  . Regular remeshing
  . Regular remesh : 모든 vertex가 같은 valence를 가짐.
  . Valence : vertex에 연결된 edge의 수
  . Connectivity가 좋다. 압축률이 좋다.
  . Goal : feature를 잘 보존하면서 remesh
  . Segmentation : 3D를 자름
  . Parameterization : 3D를 2D에 펼침 => feature preserving
  . least square conformal Map => regular remeshing

  . Parameterization
  . 각도 보존(Conformal map, angle-preserving)
  . 경위도 보존
  . 넓이 보존
  . Contribution - 기존방법의 단접 - 삼각형이 매우 찌그러짐.

. 조원 : 공내진
. Fast bilateral filtering for the display of high-dynamic range
  . HDR : High-dynamic-range
  . device들보다 인간이 보는 contrast range가 훨씬 넓다.
  따라서 완벽하게 표현하지 못한다.
  . 선형으로 변환하면 대비가 분명하지 않다.
  . 영화가 너무 어두울 때
  . 밝은 것(오랜노출)부터 어두운 것(짧은 노출)순으로 16장을 찍고 합쳐서 만든다.
  . Tone reproduction problem : contrast를 잘 맞추기
  = Tone mapping operator 찾기
  . Anisotropic diffusion : 가까운 pixel의 영향을 더 많이 받음.
  . Bilateral filter : contrast를 잘 변환

  . bilateral : 쌍방의, 좌우 양측의
  . anisotropic : directionally dependent
  . have different characteristic in different direction
  . ex) polarising lens, polaroid sunglasses

  . isotropic : directionally independent
  . diffusion : spotaneous spreading of matter, heat or momentum

  . layes
  . base layer : operation을 함
  . Detail layer : 보존
  . Color layer : 안씀

  . Bilateral mask
  . f : 관심 pixel의 주변만 봄
  . g : edge에서는 intensity가 달라지는 속성을 이용,
         너무 intensity가 커지면 중단.

. 조원 : (최영남 AI, 김효실 GC), (양형진)
. A new voronoi based surface reconstruction algorithm
  . Laser scan으로 물체를 sampleing하여 point를 얻음.
  . Surface reconstruction : surface 위의 점을 sampling하고
  그것을 다시 construct해서 surface를 만듬.

  . Delaunay triangle : 점들을 이어 삼각형으로 만듬.
  . edge property : 어느 삼각형의 외접원도 그 세 점 외에 다른 점을 포함하지 않음.
  . http://www.ics.uci.edu/~eppstein/gina/delaunay.html

  . Mesh : simple element로 discretization

  . Voronoi diagram : R^d를 point로 cell로 나눔. (decomposition)
  . closest point에 의해 분할되는 공간

  . Medial Axis
  . voronoi diagram의 edge의 boundary
  . tree-like skeleton
  . continuous cousin of the Voronoi diagram
  . http://www.cs.utexas.edu/users/amenta/powercrust/tools.html#mat
 
  . Power crust
  . Medial axis transform을 이용한 3D surface reconstruction algorithm

  . Clakrson's hull
  . n-d Delaunay triangulation을 위한 Exact arighmetic을 해준다.

  . Geodesic distance와 euclidean distance가 다른 것을 구별하기 위해
  axis를 사용한다.

. Surface reconstruction algorithm
  . CGAL library 이용
  . Improve : handling sharp edge
  . Compression 해보기

. 조원 : 유상욱
. Realistic 3D face construction
  . Final fantasy : Model의 사진을 기반으로 만듬
  . 사진 + camera parameter
  . 3D face Model construction - 사용자가 feature point 추가가능
  . Image Texturing
  . Virtual Boundary
  . Matching
  . Embedding
  . Smoothing

. 조원 : 서원필(VR), 이용준
. Sequential Point trees
  . Point based rendering (삼각형이 아닌 point cloud를 이용하자.)
  . Inefficient when all vertices are rendered
  . Hole problem
  . Qsplat - Octree처럼 공간을 나눔
  . tree라서 array보다 느리다.
  . CPU + GPU를 모두 쓰므로 bottleneck이 있다.

. 조원 : 이지현
. Making paper craft toys from meshes using strip-based approximate unfolding
  . Paper craft
  . Unfolding : Mesh -> 전개도

  . 기존의 방법
  . Unrealistic to assemble
  . simplify-smoothness 보존
  . Triangle strip : 언제나 unfold가능, loop도 ㅣㅇㅆ을 수 있음.
  . Zonal region : 띠를 만듬.

. 조원 : (주현성, 이지원), (이정환 CG)
. Particle system
  . 20년이 넘어 이미 모두 상업화됨.
  . Research topic이 없음.
  . 최초의 motion blur 작품(streaks of lights)

. Digital Photography of flash and no-flash image pairs
  . flash : High-frequency, red-eye, harsh shadow
  . No-flash : Ambient illumination, noise
  . 동일한 카메라 위치에서 찍은 두 사진을 합성하고 장점만 취해 더 좋은 이미지를 얻는 다.

. Art-based rendering of fur, grass and trees

. Stanford computer Graphics Laboratory
http://www-graphics.stanford.edu/
-> Data archives
The digital michelangelo project의 일환으로 status scanner가 있어서
데이터가 많음 point set sample data를 얻을 수 있음.
Bunny, Lion, Happy Buddha, Dragon, Lucy 등이 있다.

3.5. Parametric curves
. x(t), y(t)에 대해 각각 풀면 된다.
. Bezier curve : guide point 2개를 이용하여 cubic Hermite를 푼다.
  . Hermite를 위한 x'(t), y'(t)는 guide point를 이용한 numerical difference formula를 이용한다.
  . Guide point의 부호가 반대이므로 주의
. (x0, y0), guide point1, guide point2, (x1, y1)

4. Numerical Differentiation and Integration
4.1. Forward difference formula
  f'(x) = 1/h * (f(x+h) - f(x))
. backward difference formula
  f'(x) = 1/h * (f(x) - f(x-h))

. centered formula
  f(x+h), f(x-h), f(x) 등이 symmetric(대칭적)으로 들어간다.

. n-th order : 에러 term이 h의 h-th order이면 된다.
  . 1th order : h*f''(x) + 등..
  . 2th order : h^2*f''(x) +  등..

. 식 유도 방법
  방법1) Lagrange를 이용한 후 미분한다. - 책에 소개된 방법
  x0 ~ xn의 점을 이용하여 n-th lagrange interpolation을 이용하면
  (n+1)-point formula가 된다.

  방법2) Taylor series를 이용한 후 error order를 잘 소거하는 방향으로 더하거나 뺀다.
  - 수업시간과 시험에 나오는 방법
 
4.2. Richardson's Extrapolation(R.E)
  . Low-order formula를 잘 이용해서 high-accuracy를 구하는 방법
  . function evaluation보다 사칙연산의 cost가 훨씬 적다고 가정한다.
  . h -> h/2 등으로 step size를 줄이면서 계산
  (연습 문제에서는 h/3 씩 줄이기도 함.)
  . M = N(h) + k1h + k2h^2 + k3h^3 + k4h^4 +
  . M : 참값
  . N(h) : 근사식
  . N1(h), N1(h/2)을 이용하여 N2(h)를 만듬.
  . N1(h/(2^n))이 있으면 Nn(h)까지 만들 수 있음.
  . Simple averaging process

4.3. Numerical Integration
  . Quadrature = Integration = Numerical Integration
  . Quadrature은 integration의 옛날 이름이다.
  . Deviation은 역사가 몇백년이지만 Integration은 역사가 수천년이다.

  . Trapezoidal Rule(TR, T.R)
  . first Lagrange Polymial로 유도가능
  . h/2 * (f(a) + f(b))
  . h = (b-a)
  . error : h^3/12*f''(x)

  . Simpson's Rule(SR, S.R)
  . second Lagrange Polymial로 유도가능
  . h/3 * (f(a) + f((a+b)/2) + f(b))
  . h = (b-a)/2
  . error : h^5/90*f(4)(x)

  . Degree of accuracy = precision
  . Undetermined coefficient와 관련있다.
  . degree가 k이면 각 degree polynomial에서 formula가 정확하다.
  . Trapezoidal Rule은 1, Simpson's Rule은 3이다.
  . TR은 1차식, SR은 3차식에 대해 각각 exact solution을 준다.

  . Undetermined coefficient
  . 구간이 -1, 1처럼 숫자일때는 c0, c1이 1/2, 1/2 같은 수로 나오지만
     x0, x1일 때는 c0 = c1 = (x1-x0)/2로 나온다. (test2에서 내가 실수한 문제)

  . Newton-Cotes formulas
  . TR, SR의 일반식, lagrange를 이용.
  . Open Newton-Cotes formulas
  . boundary a,b가 포함됨
  . closed Newton-Cotes formulas
  . boundary a,b가 포함 안됨

4.4 Composite Numerical Integration
  . High-order는 oscillatory nature가 있으므로 piece-wise로 한다.

  . Composite Trapezoidal Rule(CTR, C.T.R)
  . error : (b-a)*h^2/12*f''(x)

  . Composite Simpson's Rule(CSR, C.S.R)
  . error : (b-a)*h^4/180*f(4)(x)

4.5 Romberg Integration
  . Composite Trapezoidal Rule + Richardson's Extrapolation
  . R1,1 = TR
  . R2,1 = 1/2(R1,1 + h * 1개)
  . R3,1 = 1/2(R1,1 + h/2 * 2개)
  . R4,1 = 1/2(R1,1 + h/2 * 4개)

  . R1,1, R1,2 => R2,2 (R2,1은 없으므로 주의 항상 k>=j)
  . Rk,2 = Rk,1, Rk-1, 1을 이용해서 구한다.
  . Rk,j = Rk,j-1 + (Rk,j-1 - Rk-1,j-1)/(4^(j-1)-1)

  . Rk, j : k : h를 1/2씩 줄인다, j : RE의 항
  . Rn, n : TR일때 h^(2*n)의 accuracy(order)를 가진다.

4.6 Adaptive Quadrature Methods
  . 1/2, 1/4로 step을 줄여 계산하고 값의 오차가 큰 경우 그 구간은 다시 1/2로 나눈다.
  . 오차가 만족스럽거나 구간이 충분이 좁을 때까지 반씩 나누면서 연산을 계속한다.
  . 변화량이 큰 구간은 잘게 쪼개고, 변화가 없는 구간은 적게 쪼개는 계산법.

4.7 Gaussian Quadrature
  . 구간을 잘 쪼게거나 하는 것이 아니라 구간의 boundary의 점이 아닌
  가운데 있는 점들을 선택해보자. 어떤 것이 optimal point일까?
  (choose the points for evaluation in an optimal)
. Gaussian Quadrature
  . http://en.wikipedia.org/wiki/Gaussian_quadrature
  . Newton-Cotes formulas의 error term은 n+1 derivative로 정의되므로
  polynomial of degree n에 대해서는 exact하다.
  . Newton-Cotes formulas : equally spaced points 사용
  . composite시 편하지만 accuracy가 떨어진다.
  . Optimal placement를 해보자.

  . Undetermined Coefficient constant를 구하는 방법으로
  c1, c2, ..., cn, x1, x2, ..., xn을 구한다.

. Legnedre polynomials
  . P0(x) = 1
  . P1(x) = x
  . P2(x) = x^2 - 1/3
  . P3(x) = x^3 - 3/5x
  . Monic polynomial : have leading coefficient 1
  . Orthogonal polynomials
  . intgral(-1 to 1, P(x)Pn(x)dx) = 0 where P(x) is a polynomial of degree less than n.
  . xi를 알면, xi를 lagrange interpolate한 후 -1 to 1으로 적분하면 ci를 구할 수 있다.

. Multiple Integrals
  . Region이 rectangle일 때
   x축에 대해서 한 번 계산하고 y축에 대해서 또 계산하면 된다.

. Improper Integral
  . I = int(a..b, f(x))
  . lim x->a, f(x) = inf
  . a에서 diverge하지만 area는 converge한다고 가정하자.
  . TR, SR 등 기존의 방법은 사용할 수 없다.
   왜냐하면 f(a) = inf 이기 때문에 값이 inf(nan : not a number)로 나온다.
  . Gaussian Quadrature는 가능할 수도 있다. (f(a)를 얻지 않으므로)
   하지만 운이 좋을 때 뿐이고 값이 커지면 이상해 질 수 있다.

  . int(a..b, 1/(x-a)^p) = (b-a)^(1-p)/(1-p) (0<p<1 iff converge)
  . f(x) = g(x)/(x-a)^p로 쓸 수 있으면
  . P4(x) = 4th taylor Polynomial of f(x)
  . P4(x) = g(a) + (x-a)g'(a) + 1/2*(x-a)^2*g''(a) + 1/6*(x-a)^3*g'''(a)
           + 1/24*(x-a)^4*g''''(a)
  . int(a..b, f(x))
   = int(a..b, g(x)/(x-a)^p)
   = int(a..b, (g(x)-P4(x))/(x-a)^p) + int(a..b, (P4(x))/(x-a)^p)
  . G(x) = (g(x)-P4(x))/(x-a)^p  (a<x<=b)
        = 0  (x = a)
  . int(a..b, (P4(x))/(x-a)^p) 부분은 CSR로 푼다.

  . Why 4th taylor Polynomial?
   . CSR과 P4(4)의 error term의 order를 같게 맞추기 위해서이다.
   . 5th order로 같아진다.

생각나는 대로 적어봤음.

시험시간 : 2시간 (1시간이면 충분한 내용이었음.)
자리배치 : 학번 마지막 자리로 hash해서 두 숫자씩 한 공간을 정해줌.
시험인원 : 대략 90명
분량 : 7장, 6문제 - 시험지에 바로 답을 적어서 냄.

. 용어 설명하기(3줄 이내) - 족보와 거의 일치했음.
  type error
  type system
  polymorphism
  Overloading
  type check를 하면 어떤 이득이 있나?

. CFG보고 parse tree 그리기, ambiguous 판별하기
  . ambiguous 함

. Compile과정 적기
  . source code
  . lexical anaylsis
  . parse tree
  . Abstract syntax tree
  . intermediate code
  . optimization
  . machine code

. Denomational semantic가 주어지고 해석하기
  . binary, xor(#), and(@)
  우리말로 적기
  Binary의 마지막 한 자리만 봄

. Lambda calculus 풀기 2개
  . c h h 3 = c(h(h(3))) => (3+3)+(3+3)
  . 길지않았으나 헷갈림.

. Type inference tree 분석하기
  . type inference tree가 이미 주어져 있었음.
  . equation을 새우고 풀면 됨.

알면 다 풀고 모르면 못 푸는 그런 시험이었음.
lambda calculus 외에 머리 복잡한 계산, 정리 하나도 없었음.
실수를 안했으면 거의 85~95점 나오리라고 봄.

. 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로 적는 다.

. Syntax and semantics of programs
  . syntax : the symbols used to write a program
  . semantics : the actions that occur when a program is executed
  . programming language implementation
  . syntax -> semantics
  . tranform program syntax into machine instructions
     that can be executed to cause the correct sequence
     of actions to occur

. Interpreter vs Compiler
  . Interpreter : 느리다. 컴파일이 따로 필요없어서 간편하다.
  source 코드를 바로 읽는 다.
  . Compiler : 여러 translation을 해서 복잡하지만 빠르다.
  target program으로 먼저 번역한다.

. Typical compiler
  1. source program

  2. lexical analyzer(lexer, scanner)
    http://en.wikipedia.org/wiki/Lexical_analyzer
    Regular expression, finite automata, lex
    keyword, variable 등을 나눔(lexical token을 구함)
    쓸데 없는 blank도 제거

  3. syntax analyzer(parsing, parser)
    http://en.wikipedia.org/wiki/Syntax_analysis
    http://en.wikipedia.org/wiki/Yacc
    Context free grammar, BNF, yacc(yet another compiler compiler)
    parse tree를 만듬.
    terminal node를 모으면 program이 된다.
    nonterminal node도 이ㅆ음.

  4. semantic analyzer - PL에서 다룸
    Abstract syntax tree(AST) : parse tree에서 중요한 것만 남김
    augmented parse tree : type와 declare된 장소에 관한 정보를 더함.(annotation)
    type system
    Annotation : symbol table을 이용해서 각 variable이 어디에 쓰이는 지 type등을 적음.

  5. intermediate code generator - OS, architecture에서 다룸
    function_start(), computer_expr(), assing() ...
    AST를 tree traverse하여 depth first search하면 intermediate code가 된다.
    Virtual Machine, 3-address instructions

  6. code optimizer - OS, architecture에서 다룸
    Common subexpression elimination : 한번만 계산하고 저장해뒀다가 사용
    copy propagation : 같은 value 한번만 assign
    dead-code elimination : 실행 안되는 코드 제거
    loop optimizations : loop 밖으로 최대한 꺼냄
    function in-lining : 함수 호출을 줄임, 프로그램 크기가 증가함.

  7. code generator
    Machine architecture
    Register allocation
    Optimization
    reuse registers efficiently

  8. target program - machine code

. Brief look at syntax
  . Grammar
  e ::= n | e+e | e-e
  n ::= d | nd
  d ::= 0|1|2|3|4|5|6|7|8|9
  . expressions in language
  e -> e-e -> e-e+e -> n-n+n -> nd-d+d -> dd-d+d -> .. -> 27-4+3

. Derivation represented by tree
  Tree shows parenthesization of expression

. Parsing
  . Given expression find tree
  . Ambiquity
  . Expression 27-4+3 can be parsed two ways
  . Problem : 27-(4+3) != (27-4)+3
  . Ways to resolve ambiquity
  . Precedence(다른 operator일때) - high or low
     . Group * befor +
     . Parse 3*4+2 as (3*4)+2
  . associativity(equal precedence일때) - left or right
     . parenthesize operators of equal precedence to left(or right)
     . (3-4)+5 : left-associative
     . 3-(4+5) : right-associative

. Theoretical foundatinos
  . many foundational system
  . computability theory
  . Program logics
  . Lambda calculus
  . denotational semantics : PL의 semantics
  . operational semantics : PL의 manual 같은 것
  . Tyep theory

  . consider these methods
  . Lambda calculus(syntax, operational semantics)
  . computability theory
  . denotational semantics

. lambda calculus
  . 가장 primitive하지만 모든 것이 표현가능, theoretical한 증명이 쉽다.
  . formal system with three parts
  . Notation for function expressions
  . proff system for qeuations
  . calculation rules called reduction
  . additional topics in lambda calculus
  . mathematical semantics
  . type systems

. history
  . original intention
  . formal theory of substitution
  . more successful for computablel functions
  . substitution -> sybolic computation
  . church/turing thesis
  . influenced design of Lisp, ML, other languages
  . See boost lambda library for C++ function objects
     http://www.boost.org/libs/lambda/index.html
  . important part of CS history and foundations

. Why study this now?
  . Basic syntactic notions
  . Free variables : global variable
  . Bound variable : function argument
  . functions
  . declarations - 선언과 정의

  . Calculation rule(매우 간단하다) - 단 1개의 symbolic substitution
  . Symbolic evaluation useful for discussing programs
  . Used in optimization (in-lining), macro expansion
     . correct macro processing requires variable renaming
       (Name conflict control)
  . Illustrates some ideas about scope of binding
     . Lisp originally departed from standard lambda calculus,
       returned to the fold through Scheme, Common Lisp

. Lambda expression
  . Symbolic computation, pattern matching을 잘해서 reduction

. BNF
  . M :: = x (variables)
     | M1 M2 (application), M1: function, M2: function의 actual parameter
     | lx.M (abstraction), M:function body, x : M의 formal parameter
ex)
lx.x = identity function의 abstraction form
lx.(f (g x))
(lx.x)5
lx.x y == lx.(x y) : 최대한 길게 뒤로 가서 parsing
application, abstration 모두 되므로 ambiguous grammar

. ambiguous grammar
  . if there si some string that it can generate in more than one way.
  . http://en.wikipedia.org/wiki/Ambiguous_grammar
  ex) CFG, A->A+A|A-A|a, is ambiquous.

. expression
  x + y

. functions
  lx.(x+y)

. application
  (lx.(x+y))3 = 3+y

. Higher-order functions
  . Given function f, return funcition f.f
  . lf. lx.f(f x)
  . How does this work?
     (lf. lx. f(f x))(ly.y+1)
    => lx.(ly.y+1)((ly.y+1) x)
    => lx.(ly.y+1)(x+1)
    => lx.x+1+1

. Free and Bound Variables
  . Bound variable is "placeholder" - 따라서 항상 rename 가능
  . Variable x is bound in lx.(x+y)
  . function lx.(x+y) is same function as lz.(z+y)
  . Name of free(=unbound) variable does matter
  . variable y is free in lx.(x+y)
  . function lx.(x+y) is not same function as lx.(x+z)
  . Occurrence
  . y is freee and bound in lx((ly.y+2) x) + y
  . scope
  . bound variable : 이름 바꾸기 가능(local이므로)
  . free variable : 이름 바꾸기 불가능(global이므로)
  . lambda calulus는 static scope이다.

. alpha-reduction : varialbe rename

. beta-reduction : substitution
  . (lx.e1)e2 -> [e2/x]e1
  . e1의 free variable x를 e2로 clghks
  . where substitution involves renaming as needed
  (name conflict를 피하려면 renmaing해야 한다.)

. reduction
  . apply basic computation rule to any subexpression
  . repeat

. confluence : 맘대로 evaluation해도 결과는 같다.
  . final result (if there is one) is uniquely determined
. Redex : reducable expression

. Substitution
  . [N/x]x = N
  . [N/x]y = y where y is different from x
  . [N/x](M1 M2) = ([N/x]M1 [N/y]M2)
  . [N/x](lx.M) = lx.M (헷갈리는 부분, 두 x의 scope가 다르다.)
  . [N/x](ly.M) = ly.([N/x]M) where y is not free in N
  (free y를 bound y로 만들면 안된다.)
  ex.1)
  (lx.(ly.(x+y+1))(y+1)
  => (lx.(lz.(x+z+1))(y+1) (rename을 먼저해야 한다.)
  => lz.(y+1+z+1)
  != ly.(y+1+y+1) (free y를 bound y로 만들면 안된다.)

  ex.2)
  (lx.(lx.x+1))5
  => [5/x](lx.(x+1))
  => lx.(x+1)
  혹은
  => (lx.(ly.y+1))5
  => ly.y+1
  != 5+1

  . FV(x) = {x}
  . FV(M N) = FV(M) U FV(N)
  . FV(lx.M) = FV(M) - x

. function with several arguments(argument가 여러개 일때)
  . curried form
  . http://en.wikipedia.org/wiki/Currying
  . ex) f(g,x) = g(x)
  . f curry = lg.lx.g x
  . f curry g x = g x = g(x) = f(g,x)
  . pair notation = curried form
     . f=l(g,x).g x

. Recursion and fixed Point
  . factorial function
  function f(n) { if n = 0 then 1 else n*f(n-1)};
  -> 이것은 f의 definition이 아니라 equation이다.
  . Equation with recursive definition
  f(n) = if n = 0 then 1 else n * f(n-1)
  . Get the solution f with above equation, Let
  G = lf.ln.if n=0 then 1 else n*f(n-1)
  . f is the fixed point of function G, ex f = G(f)

. Fiexed point operator = Y-combinator, domain theory로 증명가능
  . http://en.wikipedia.org/wiki/Fixed_point_operator
  . fixed point combinator allow the definition of anonymous recursive functions
  . a fixed point operator Y
  Y = lf.(lx.f(x x))(lx.f(x x))
  . Show that Yf = f(Yf)
  Yf = (lf.(lx.f(x x))(lx.f(x x)))f
  => (lx.f(x x))(lx.f(x x))
  => f((lx.f(x x)) (lx.f(x x)))
  => f(Yf)

. original motivation for topic
  . denotational semantics를 배우는 이유
  . Precision
  . Use mathematics instead of english
  . avoid details of specific machines
  . Aim to capture "pure meaning" apart from implementation details
  . Basis for program analysis
  . Justify program proof methods
     . soundness of type system, control flow analysis
  . Proof of compiler correctness
  . Language comparisons

. Why study this?
  . Look at programs in a different way
  . Program analysis
  . Initialize befor use
  . Introduce historical debate: functional vs imperative programming
  . program expressiveness : what does this mean?
  . theory vs practice : we don't have a doog theoretical understanding of programming language "usefulness"

. Basic Principle of denotational semantics
  . compositionality
  . The meaning of a compound program must be defined from the meanings of its parts (not the syntax of its parts)
  . Exmaples
     . P; Q
       composition of two functions, state -> state
     . letrec f(x) = e1 in e2
       meaning of e2 where f denotes function

. Trivial example : binary numbers
  . syntax
  b ::= 0|1
  n ::= b|nb (binary number)
  e ::= n|e+e (e: starting symbol)

  . semantics value fuction E : exp -> numbers
  E[[0]] = 0
  E[[1]] = 1
  E[[nb]] = 2*E[[n]] + E[[b]]
  E[[e1+e2]] = E[[e1]] + E[[e2]]

  E : syntatic element를 mathematical(semantic) entity로 mapping
  무한한 mapping을 유한하게 describe해보자.(structural induction)

. Second ex : expressions
 
  . syntax
  b ::= 0|1|...|9
  n ::= b|nb (decimal number)
  e ::= s|n|e+e (e: starting symbol)

  . semantics
  value E : exp -> numbers
  state s : vars -> numbers

  E[[x]]s = s(x) : variable namve -> value
  E[[0]]s = 0
  E[[1]]s = 1
  E[[nb]]s = 2*E[[n]]s + E[[b]]s
  E[[e1+e2]]s = E[[e1]]s + E[[e2]]s

  E[[x]]s -> E[[x,s]] : argument가 2개로 늘어난 셈

  . x : variable - 어떤 state function s가 name x를 받으면 value를 return
  E[[x+z]]는 syntactic element뿐만 아니라 state에 따라 의미가 달라진다.
  S0 = {x->4, y->7, z->8}
  E[[x+4+y]]S0
  = E[[e1+e2]]S0
  = E[[e1]]S0 + E[[e2]]S0
  = E[[e3+e4]]S0 + E[[e2]]S0
  = E[[e3]]S0 + E[[e4]]S0 + E[[e2]]S0
  = E[[x]]S0 + E[[4]]S0 + E[[y]]S0
  = 4 + 7 + 4

. Semantics of imperative programs
  . Syntax
  . P ::= x:=3 | if B then P else P | P; P | while B do P
  . Semantics
  . C : Programs -> (State -> State)
  . State = Variables -> Values
     would be locations -> values if we wanted to model aliasing
. C: P의 semantic function
. Program : Initial state -> final state
. C[[P]]S0 = S1

. Semantics of Assignment
  . C[[x:=e]]
  is a function states -> states
  . C[[x:=e]]s = s'
  where s':variables->values is identical to s except
  s'(x) = E[[e]]s gives the value of e in state s

. Semantics of Conditional
  C[[if B then P else Q]]
  C[[if B then P else Q]]s
  = C[[P]]s if E[[B]]s is true
  = C[[Q]]s if E[[B]]s is false

. Semantics of iteration
  C[[while B do P]]
  is a function states -> states

  C[[while B do P]] = the function f such that
  f(s) = s if E[[B]] is false
  f(s) = f(C[[P]](s)) if E[[B]] is true

  f is recursively defined(사실 define이 아니라 equation)

  C[[P1;P2]]S0 = C[[P2]](C[[P1]]S0)
  C[[P1]]S0 = S1
  C[[P2]]S1 = S2

. Perspective
  . Denotational semantics
  . Assign mathematical meanings to programs in a
     structured, principled way
  . Imperative programs define mathematical functions
  . Can write semantics using lambda calculus, extended with operators like
     modify:(state x var x value) -> state
  . Impact
  . Influential theory
  . Application via
     abstraction interpretation, type theory
  C[[x:=e]]S0 = S1
  modify(S0, x, e) = S1

. What is a functional language?
  . No side effects = pure(LISP)
  . OK, we have side effects, but we also have higher-order functions

. No-side-effects language test
  = Referential transparency
  . within the scope of specific declarations of x1, x2, ..., xn
  all occurrences of an expression e containing only
  variables x1, x2, ..., xn must have the same value.
 
. Example languages
  . Pure Lisp
  atom, eq, car, cdr, cons, lambda, define
  . Impure Lisp: rplaca, rplacd
  . Common procedural languages are not functional
  . Pascal, C, Ada, C++, Java, Modula

. Backus' Turing Award
  . John Backus was designer of Fortran, BNF, etc.
  . Turing Award in 1977
  . Turing Award Lecture
  . functional prog better than imperative programming
  . Easier to reason about functional programs
  . More efficient due to parallelism
  . Algebraic laws
     . reason about programs
     . Optimizing compilers(translate가 쉽다.)

. Reasoning about programs
  . To prove a program correct
  . Must consider everything a program depends on
  . In functional programs
  . dependence on any data structure is explicit
  . therefore
  . easier to reason about function programs
  . Do you believe this?
  . This thesis must be tested in practice
  . Many who prove properties of programs believe this
  . Not many people really prove their code correct

. Haskell Quicksort
  . Very succinct program(5줄 밖에 안된다.)
  . This is the whole thing
  . No assignment - just write expression for sorted list
  . No array indices, no pointers, no memory management

. Compare : C quicksort 14줄

. Interesting case study
  . Abstraction이 잘 될수록 high-level이고 사람을 efficient하게 만든다.
  . Haskell이 가장 짧고 C++이 가장 길다.
  . Relational Lisp이 가장 시간이 적게 걸렸다.

. Disadvantages of functional prog
  . Assign이 없으므로 copy를 너무 자주한다.

. Von Neumann bottleneck = stored program
  . Von numann - data의 절반이 instruction
  . Mathematician responsible for idea of stored program
  . Von numann Bottleneck
  . Backus' term for limitation in CPU-memory transfer
  . Related to sequentiality of imperative langauges

. Eliminating VN bottleneck
  . No side effects
  . Evaluate subexpressions independently => parallel하게 계산가능
  . Does this work in practice? good idea but
  . Too much parallelism
  . Little help in allocation of processors to processes
  . Scheduling overhead가 크다.
  . communication overhead가 크다.
  . David shaw promised to build the non-Von
  . Effective, easy concurrency is a hard problem

. Functional vs Imperative programs
  . Denotational semantics shows
  . Every imperative program can be written as a
     functional program, using a data structure to
     represent machine states
  . This is a theoretical result
  . I guess "theoretical" means "it's really true"
  . What are the practical implications?
  . Can we use functional programming languages for practical application?
     compilers, graphical user interfaces, network routers.
     => I/O, meta circular evaluation이 중요

. Summary
  . parsing
  The real program is the disambiquated parse tree
  . lambda calculus
  Notation for functions free and bound variables
  Calculate using substitution, rename to avoid capture
  . Pure functional program
  May be easier to reason about
  Parallelism : eay to find, too much of a good thing
  . computability
  Halting problem makes some error reporting, optimization impossible

. Formal languages
  . language - a set of strings
  L = {if, while, for, then, else ...}
  . string - a finite sequence of symbols from some alphabet
  . alphabet - a finite set of symbols
  {a,b,c, ..., z}, {0, 1, ... , 9}
  . A generator generates members of the set
  . A recognizer recognizes members of the set

. Regular expressions
  . symbols, empty string, alternation, concatenation, repetition

. Context-free Grammars
  . S : statement
  . E : expression
  . Language : 우리가 작성한 모든 program의 set
  . S -> S;S
  . S -> id:=E
  . E -> num
  . E -> E + E
  . terminals - tokens :  최종적으로 program에 나오는 것
  . Nonterminal - symbols used in grammar (S, E)
  . Start symbol - a nonterminal
  . Derivation - generating phrases of language by replacing
  nonterminals with r.h.s of productions
  . 무한개를 생성할 수 있는 이유 : S와 E가 자기자신으로 정의된다.
  . Nested structures require recursion

. BNF(Backus Naur Form)
  . 1958년 algol의 syntax define시 사용
  . CFG define productions
  . Each production consists of a
  . left-hand side non-terminal, and a
  . right-hand side sequence of terminals and non-terminals
  . A grammar also defines a non-terminal start symbol

. BNF ex
  . Notation typically used for defining languages
  <statement> ::= <statement> ; <statement>
  <statement> ::= <identifier> := <expression>
  <expression> ::= <number>
  <expression> ::= <expression> + <expression>

  <statement>, <expression>, <identifier>, <number> : non-terminal(<   >로 기술)
  ;, :=, + : terminal

. Extended BNF
  . optioanl syntax : [] : 0 or 1번
  . Repeated syntax : {} : RE의 *와 비슷

. syntax diagrams

. Derivations
  . Begin with start symbol, replace any nonterminal with the rhs of some production for that nonterminal
  . leftmost - pcik leftmost nonterninal to expand
  . rightmost - pcik rightmost nonterninal to expand
  . ex) leftmost
  S -> id:= E
  -> id:= E + E
  -> id:= E + E + E
  -> id:= num + E + E
  -> id:= num + num + E
  -> id:= num + num + num

. Derivation algorithm
  1. Begin with the start symbol nonterminal
  2. Replace the non-terminal with the right-hand side of a matching production
  3. Choose a non-terminal from the resulting sequence
  4. repeat steps 2 and 3 until no non-terminals remain

. This algorithm includes two choices
  step2. choice of matching production
  step3. choice of non-terminal

. Parse tree
  . a tree representaion of a derivation
  . connect a symbol to the one from which it was derived
  . leaf node = treminal
  . left most derivation이면 left child들이 더 풍성하다.

. Ambiquity - syntax에는 문제가 없으나 semantics(evaluation)에서는 문제가 있다.
  . a grammar is ambiguous if a phase has two different derivations.
  . equivalently, two parse trees
  . example (rightmost derivation)

. Problems with ambiquity(= grammar의  므ㅠㅑ벼ㅑ쇼)
  . If the shape of the parse tree conveys meaning, then ambiquity in a language's grammar(syntax) translates into ambiquity in the language's meaning (semantics)
  . Problematic grammar
  <statement> :: <condition> | <assignment> | begin { <statement> } end

  해결책
  1. grammar를 다시 쓴다.(Unambiquous grammars) (C언어의 방법 - 가까운 곳에 match)
  2. endif를 도입
  3. then다음에 if가 올 수 없고 반드시 begin-end가 와야 한다.

. Denotational semantics
  http://en.wikipedia.org/wiki/Denotational_semantics
  formalizeing the semantics of system by constructing mathematical objects with express the semantics of these systems.

. Axiomatic semantics
  http://en.wikipedia.org/wiki/Axiomatic_semantics
  mathematical logic에 따라 program의 correctness를 따짐.

. Operational semantics
  http://en.wikipedia.org/wiki/Operational_semantics
  give meaning to computer programs in a mathematically rigorous ywa

. semantics of initialize-before-use

. single assignment
  . can bind a value to a name at most once.
  . oftern function languages.
  . Erlang, Haskell, SISAL