속눈썹맨의 블로그

. dot product(inner product)
  . http://en.wikipedia.org/wiki/Dot_product
  . (vector * vector) -> scalar
  . lengths and angles (projection)
  . a.b = |a||b|cos(theta)

. cross product(outer product)
  . vector * vector -> vector
  . area of parallelogram, perpendicular
  . a x b = n|a||b|sin(theta)

. Scalar triple product
  . http://en.wikipedia.org/wiki/Triple_product
  . V = |a.(bxc)|

. Vector triple product
  . ax(bxc)

. del
  . differential operator del
  . nabla(역삼각형 모양)
   http://en.wikipedia.org/wiki/Nabla_symbol

. flux
  . http://en.wikipedia.org/wiki/Flux
  . the magnitude of a river's current
  . the amount of water that flows through a cross-section of the river each second

. Gradient
  . http://en.wikipedia.org/wiki/Gradient
  . Measure of the slope(steepness, fall, incline) of a straight line
  . Whose magnitude is the greatest rate of change
  . the direction of the greatest rate of increase of the scalar field
  . f(x) : scalar function (vector -> scalar)
  . x : vector variable
  . grad(f) = (af/ax1, ... af/axn) : (vector -> scalar) -> vector
  . a : partial derivatives
  . invariant under orthogonal transformations

. Divergence
  . F = (F1, F2, .. Fn)
  . div F : (aF1/ax1 + aF2/ax2 + .. + aFn/xn) : vector -> scalar
  . div = nabla inner-product
  . linear operator
  . vector field's tendency to originate from or converge upon a give point
  . flux density
  . derivative of the net flow of the vector field
  . div F(x0, y0) > 0 : source, expand
  . div F(x0, y0) < 0 : sink, shrink

. Curl
  . http://en.wikipedia.org/wiki/Curl
  . vector operator
  . F : vector
  . curl(F) : vector -> vector
  . curl = nable cross-product
  . vector fields's rate of rotation
  . the direction of the axis of rotation
  . the magnitude of the rotation
  . circulation density

. LISP - 1960년대 John MCcathy가 개발
  . elegant하고 minimalist language, mathematically well-defined
  . Not C, C++, Java : a chance to think differently
  . AI, symbolic programming (예 - 미적분)
  . prefix format - easy to parse -> program 자체가 data로 사용가능
  -> LISP program을 짜는 LISP program
  . illustrate general themes in language design
  . Stems from interest in symbolic computation(math, logic)
  . dynamically scoped languae

. Many different dialects
  . Lisp, CommonLisp, Scheme, Lisp 1.5

. John McCarthy
  . Pioneer in AI
  . Formalize common-sense reasoning
  . Proposed timesharing
  . Mathematical theory

. S-expression = symbolic expression
. Both code and data in LISP
. Semi-structured data in human-readable textual form
ex) 3, 4, (3. 4), ((x. 3), (3. 5)), nil, (3 . nil), . (2. (3. nil))
. S-expression 중 list는 .을 생략가능
http://en.wikipedia.org/wiki/S-expression
ex) (+ . (1 . (2 . (3 . nil)))) = (+ 1 2 3)
. interactive optlevel
. interactive computer programming environment
. (cons 3 4) => (3 . 4)
. (cons (+ 4 7) (* 4 7)) => (11 . 28)
. (quote A) - A를 eval하지 말고 A라고 찍어라
. (quote (+ 1 2)) => (+ 1 2) - 계산 끝 (더 이상 eval 안함)
. (car '(3 . 4)) => 3
. (car (cons 3  4) => 3
. (cdr '(3 . 4)) => 4
. (cdr (cons 3  4) => 4
. (car (3 4)) => error : 3이라는 operator를 eval할 수 없음.
. (car 3 4) => error : car는 operand를 1개만 받음.

. Atoms include numbers, indivisible "strings"
<atom> ::= <smbl> | <number>
<smbl> ::= <char> | <smbl><char> | <smbl><digit>
<num> ::= <digit> | <num><digit>

. dotted pairs
  . LISP의 basic data structure
  . Write (A.B) for pair
  . Symbolic expressions, called S-expressions
  <sexp> ::= <atom> | (<sexp> . <sexp>)
. Note on syntax
  . Book uses some kind of pidgin(혼성어) Lisp
  . Will provide executable alternative, so examples run in scheme
  . In scheme, a pair prints as (A. B) but (A.B) is not an expression

. Basic functions
  . Functions on atoms and pairs
  cons, car, cdr, eq, atom
  . Declarations and control
  . cond, lambda, define, eval, quote
 
  . Example
  (lambda (x) (cond ((atom x) x) (T (cons 'A x))))
  function f(x) = if atom(x) then x else cons("A", x)
  . functions with side-effects
  rplaca, rplacd

. special form
  . cond, lambda, define, quote
  . 모든 expression part를 evalution하는 것이 아니므로 special form이라고 부름.

. pure LISP : side effects가 없음.
. impure LISP : side effects가 있음.

. Side-effect
  . http://en.wikipedia.org/wiki/Side_effect_%28computer_science%29
  . 어떤 함수가 return value가 아닌 다른 어떤 state를 바꿀 때.
  . global, static variable, arguments 등을 바군다.
  . Imperative program은 side-effect를 가진다.
  . Function programing은 side-effect를 최소화 하려고 한다.
  . referentially opague = Not referentially transparent
  . purely functional programming에서 없음.

. Referential transparency
  . http://en.wikipedia.org/wiki/Referential_transparency
  . 어떤 subexpression을 value로 meaning의 change없이 바꿀 수 있을 때
  . purely functional programming에서 가능

. read-eval-print loop(REPL)
  http://en.wikipedia.org/wiki/Read_Eval_Print_Loop
. Function call (function arg1 ... argn)
  . evaluate each of the arguments
  . pass list of argument values to function
. special forms do not eval all arguments
  . example (cond (p1 e1) ... (pn en))
  . cond에서는 lazy evaluation을 함
  . proceed from left to right
  . find the first pi with value true, eval this ei
  . example (quote A) does not evaluate A

. McCarthy's 1960 Paper
  . Interesting paer with
  . good language ideas, succinct(간결한, 간명한) presentation
  . Some feel for historical context
  . Insight into language design process
  . Important concepts
  . Interest in symbolic computation influenced design
  . Use of simple machine model
  . Attention to theoretical considerations
     Recursive functino theory, lambda calculus
  . Various good ideas : Programs as data, grabage collection

. Motivation for Lisp
  . Advice Taker
  . Process sentences as input, perform logical reasoning
  . Symbolic integration, differentiation
  . Expression for function -> expression for integral
     (Integral '(lambda (x) (times 3 (squeares x))))
  . Motivating application part of good lang design
  . Keep focus on most important goals
  . Eliminate appealing but inessential ideas
     . Lisp : symbolic computation, logic, expreimental prog.
     . C : Unix operating system
     . Simula : simulation(descrete simulation, C++과 비슷)
     . PL/1 : "Kitchen sink", not successful in long run
       . fortran + cobol을 하려고 함, 복잡해서 실패.

. Program Execution Model(abstract Machine)
  . Language semantics must be defined
  . Too concrete(hardware에 너무 가까움)
     . Programs not portable, tied to specific architecture
     . Prohibit optimization (ex - C eval order undefined in expn)
  . Too abstract
     . cannot easily estimate running time, space
       (User와 구현자의 입장차가 커짐)
  . LISP : IBM 704, but only certain ideas
  . Address, decrement registers -> cells with two parts(car, cdr)
  . Garbage collection provides abstract view of memory
  . LISP의 기본 memory model : cell(pair)
  . Evaluation order를 specify하면 optimization이 안된다.
  . car : contents of address register
  . cdr : contents of data register

. Abstract Machine
  . Concept of abstract machine
  . Idealized computer, executes programs directly
     (무한 용량, 무한 정확도)
  . Capture programmer's mental image of execution
  . Not too concrete, not too abstract
  . Example
  . Fortran
     . Flat register machine; memory arranged as linear array
       -> Von neumann architecture를 그대로 반영
     . No stack, no recursion
  . Algol family
     . Stack machine, contour model of scope
     . heap storage(memory allocation, C++의 new, delete)
     . Stack이 기본 memory structure
  . Smalltalk
     . Objects, communicating by messages.   
  . 심볼릭스 - Lisp 전용 machine
  . association list(A-list, run-time stack)
  . 현재 expression이나 다음에 사용될 변수의 값을 저장.

. Theoretical considerations
  . McCarthy's description
  . Scheme for representing the partial recursive functinos of a certain class of symbolic expressions
  . Lisp uses
  . Concept of computable(partial recursive) functions
     . Want to express all computable functions
  . Function expressions
     . Known from lambda calculus(eveloped A. Church)
     . lambda calculus equivalent to Turing Machines, but provide useful syntax and computation rules.

. Innovations in the design of Lisp
  . Expression-oriented
  . function expressions
     (lambda calculus를 기반으로 하고 있어 수학적이다.)
  . conditional expressions
  . Recursive functions - loop대신 사용
  . Abstract view of memory
  . Cells instead of array of numbered locations
  . Garbage collection
  . Programs as data
  . higher-order function : function을 parameter로 받고 return value로 넘김.
  . first-order function : argument와 function이 아닌 것.
  . second-order function : argument로 first-order function을 받는 것
  . third-order function : argument로 first-order function을 받는 것

. Algol : function이 nested define 가능하다.
. C의 scope : local or global, 2종류 밖에 없다.

. Parts of speech
  . statement - load 4094 r1
  . Imperative command
  . Alters the contents of previously-accessible memory
  . Expression - (x+5)/2
  . Syntactic entity that is evaluated
  . Has a value, need not change accessible memory
  . If it does, has a side effect
  . Declareation - integer x
  . Introduces new identifier - identifier의 atribute를 정의
  . May bind value to identifier, specify type

. expression과 statement의 차이점
  statement는 state를 바꾸지만 expression은 memory state를 바꾸지 않을 수도 있다.
  LISP은 statement based가 아니라 expression based이다.

. function expressions
  . Form
  . (lambda (parameters) (function_body))
  . Syntax comes from lambda calculus : lambda calculus에는 function이름이 없다.
  lf.lx.f (f x)
  (lambda (f) (lambda(x) (f (f x))))
  . Defines a function but does not give it a name t
  ((lambda (f) (lambda 9x) (f (f x))) (lambda(x) (+ 1 x)) )

  . (define twice (lambda (f) (lambda (x) (f (f x)))))
  . (define inc (lambda (x) (+ 1 x)))
  . ((twice inc) 2)

. Conditional expressions in Lisp
  . sequential conditional expression
  . Generalized if-them-else (lazy evaluation)
  . (cond (p1 e1) (p2 e2) ... (pn en))
  . evaluate conditions p1 ... pn left to right
  . if pi is first condition true, then evaluate ei
  . value of ei is value of expression
  No value for the expression if no pi true, or
     p1 ... pi false and pi+1 has no value, or
     relevant pi true and ei has no value
  . conditional statements in assembler
  . Conditional expression apparently new in Lisp
  . P1~Pn이 모두 true가 아닐 때
     . Scheme : null을 return
     . 아무것도 return 안하기도 함.

. strict ness
  . An operator or expression form is strict if it can have a value only if all operands or subexpression have a value
  . 모든 argument를 계산 후에 operator를 적용
  . Lisp cond is not strict, but addition is strict
  . (cond (true 1) (diverse 0))
  . (+ e1 e2)

. Lisp memory Model
  . Cons cells
  . Atoms and lists represented by cells

. Sharing
  . Both structures could be printed as ((A.B).(A.B))
  . Which is result of evaluating?
  . 단지 print만 해서는 internal representation을 알 수 없다. (구별안됨)
  . Imperative feature가 없으면 구별이 안된다. (replaca, replacd)

. Garbage collection
  . Garbage
  . At a given point in the execution of a program P
     a memory location m is garbage if no continued execution of P
     from this point can access location m.
  . 가만 놔둬도 되지만 memory가 부족할 때 machine이 run time에 함.
     programmer는 언제 수행될지 모름,
     execution time을 추정할 수 없음. - realtime에서 매우 중요
  . free list ( = free storage list)
  . the list of available memory location
  . Garbage collection
  . Detect garbage during program execution
  . GC invoked when more memory is needed
  . Decision made by run-time system, not program
  . This is can be very convenient. ex) in building text-formatting programming, ~40% of programmer time on memory management.
  . C에서는 string을 위해 매우 오랜시간을 쓴다.
  . Memory leak, dangling modifier

. Ex)
  car (cons (e1) (e2)))
: cells created in evaluation of e2 may be garbage, unless shared by e1 or other parts of program

. Mark-and-sweep algorithm
  . Assume tag bits associated with data
  . Need list of heap locations named by program
  . Algorithm
  . Set all tag bits to 0
  . Start from each location used directly in the program
     follow all links, changing tag ibt to 1
  . Place all cells with tag = 0 on free list

. Why garbage collection in Lisp?
  . McCarthy's paper says this is
  more convenient for the programmer than a system in which he has to keep track of and erase unwanted lists.
  . Does this reasoning apply equally well to C?
  (C에서는 왜 안했을 까?)
  . Is garbage collection "more appropriate" for Lisp than C? Why?
  (시험에 냄, 책 찾아보기, P.38)
  . LISP은 garbage가 필연적으로 생기지만
     C의 경우 간단한 프로그램의 경우 user-allocated memory를 안 써서, garbage가 안 생길 수도 있다.

. Programs as data
  . Programs and data have same representation
  . Eval function used to evaluate contents of list
  . substitute x for y in z and evaluate
  (define substitute (lambda (x y z)
     (cond ((null z) z)
           ((atom z) (cond ((eq z y) x) (true z)))
           (true (cons (substitute x y (car z))
                       (substitute x y (cdr z)))))))
  (define substitute-and-eval
     (lambda (x y z) (eval (substitute x y z))))
  (substitute-and-eval '3 'x '(+ x 1))

. Recursive functions
  . Want expression for function f such that
  (f x) = (cond ((eq x 0) 0) (true (+ x (f (- x 1)))))
  . Try
  (lambda (x) cond ((eq x 0) 0) (true (+ x (f (- x 1)))))
  . mcCarthy's 1960 solution was operator "label"
  (label f -> f가 recursive function임을 알려줌 (recfun 등도 씀)
     (lambda (x) cond ((eq x 0) 0) (true (+ x (f (- x 1))))))

. Recursive vs non-recursive declarations
  . Recursive definition
  (lambda (x) cond ((eq x 0) 0) (true (+ x (f (- x 1)))))
  . Legal scheme : treats inner f as function being defined
. Non-recursive definition
  . (define x (+ x 2))
  . Error if x not previously defined
  while evaluating arguments to + in expression (+ x 2)
  Unbound variable: x
  ABORT: (misc-error)
. Theory와 implementation입장에서 복잡함.(recursion 때문에)

. Higher-order functions
  . Function that either
  . takes a functino as an argument
  . returns a function as a result
  . Example: function composition f(g(x))
  . (define compose (lambda (f g) (lambda (x) (f (g x)))))
  . example : maplist -> 모든 원소에 function을 apply
  . (define maplist (lambda (f x)
        (cond ((null x) nil)
              (true (cons (f (car x)) (maplist f (cdr x)))))))

. Example
  . (define inc(lambda(x) (+ x 1))
     (maplist inc '(1 2 3))
     => (2 3 4 . nil) = (2 3 4)

. scheme preamble
  . (define true #t)
  . (define false #f)
  . (define eq eq?)
  . (define null null?)

. Efficiency and side-effects
. expression을 eval하면 value가 달라진다.
. Pure Lisp : no side effect
  . 대신 efficiency가 떨어짐, data copy를 너무 자주함.
. Additional operations added for "efficiency"
  (rplaca x y) replace car of cell x with y
  (rplacd x y) replace cdr of cell x with y
. What does "efficiency" mean here?
  . Is (rplaca x y) faster than (cons y (cdr x)) ?
  . Is faster always better? - 좋을 때도 있고 아닐 때도 있다. (yes or no)

. scheme preamble
  . (define rplaca set-car!)
  . (define rplaca set-cdr!)

. Summary : contributions of LISP
  . Successful language
  . Symbolic computation, experimental programming
  . Specific language ideas
  . Expression-oriented : functions and recursion
  . Lists as basic data structures
  . Programs as data, with universal function eval
  . Stack implementation of recursion via "public pushdown list"
  . Idea of garbage collection

. Exploratory programming
  . experimental evalutino에 따라 system이 radicall하게 바뀌는 것.

. Turing complete
  . Turing equivalent
  . Computationally universal
  . http://en.wikipedia.org/wiki/Turing_complete
  . Universal turing machine과 computational power가 같다.

. static scoping ( = lexical scoping)
  . http://en.wikipedia.org/wiki/Static_scoping
  . A variable always refers to its nearest enclosing binding.
  . ML, Haskell, scheme
  . unrelated to the runtime call stack
  . compile time에 binding 된다.
  int x = 0;
  int f () { return x; }
  int g () { int x = 1; return f(); }
  g()는 0을 retrun 함

. dynamic scoping
  . each identifier has a global stack of bindings
  . compile type이 아닌 runtime에 binding stack을 해야 한다.
  . Dangerous하므로 현대적 언어들은 쓰지 않는 다.
  . Perl, Common Lisp
  . run time에 binding 된다.
  int x = 0;
  int f () { return x; }
  int g () { int x = 1; return f(); }
  g()는 1을 retrun 함

. formal parameter
  . a placeholder in the funcion definition

. actual parameter
  . formal parameter에 값이 apply되었을 때.

. anonymous function
  . lambda를 이용하여 declared name이 없는 함수를 만들 수 있다.

. short-circuting
  . 필요하지 않ㅎ는 것은 evaluate하지 않음.
  . Scor(e1, e2), boolean or : e1이 true이면 바로 true를 return함, e2가 undefined라도 상관없음.
  . Por(e1, e2), parallel or : e1, e2가 side effect가 없고 둘 중 하나가 undefined라도 다른 하나가 ture이면 true를 return함.

. reference counting
  . a simple garbage-collection scheme
  . 각 메모리 공간이 자신을 가리키는 reference count를 가지고 있음.
  . impure Lisp에서는 cycle이 가능하기 때문에 그 경우 reference counting은
  실패하게 된다.

http://www.ebs.co.kr/HOMEPAGE/?progcd=0001327
EBS 오디오북 : 유료
라디오 문학관 : 무료
한국단편 50선 
세계단편 50선 
우리소설 100선 

베니스 상인 같은 경우 20분짜리 3편임.
대략 분량은 초등학교 6학년 수준이 읽는 책 정도 됨.
1시간만에 세세한 것까지 소화할 수 없으므로.
참고로 고우영 삼국지가 mp3로 20분짜리가 몇백회였던 것 같다.

TV나 책을 읽기는 쉽지 않을 때, 가볍게 들으면 좋겠다.

. Foundations : partial, total functions
  . Undefined operation(Error termination)
  ex) division by zero
  . 3/0 has no value - mathematically undefined
  . imprementation may halt with error condition
  . Evalutino of the expression cannot proceed because of a conflict between operator and operand.
  . Nontermination - 무한루프, divergenece 등
  . f(x) = if x = 0 then 1 else f(x -2)
  . This is a partial function : not defined on all arguments
  . cannot be detected at compile-time; This is halting problem
  . proceeds indefinitely

. These two cases are
  . Mathematically equivalent
  . Operationally different

. Partial and total functions
  . Total function : f(x) has a value for every x
  . Partial functino : g(x) does not have a value for every x
  . 우리가 푸는 것은 recursive partial function이므로 못 푸는 문제가 존재한다.

. Functions and graphs
  . mathematics : afunctions is a set of ordered pairs(graph of function)

. Partial and total functions
  . total function f: A->B is a subset f in AxB with
  . For every x in A, there is some y in B with (x,y) in f (total)
  . If (x,y) in f and (x, z) in f then y = z (single-valued)
  . partial function f: A->B is a subset f in AxB with
  . If (x,y) in f and (x, z) in f then y = z (single-valued)
  . programs define partial functions for two reasons
  . partial operations (like division) - 바로 termination가능
  . nontermination
     f(x) = if x = 0 then 1 else f(x-2)
 
. Halting problem
  . Computable
  . Partial recursive functinos(recursion을 허용하는 partial function)
  . = Lambda calculus
  . = Turing machine
     . symbol manipulating devices
     . Tape, head, state register, action table(transition function)으로 구성

. Halting problem(A noncomputable function)
  . Given a program P that requres exactly one string input and
  a string x, determine whether P halts on input x.
  (Say yes or no)
  . Undecidable -  dkanfl aksgdms tlrksdmf wnjeh dkf tn djqtek.

. Computability
  . Definition
  Function f is computable if some program P coumputes it:
     For any input x, the computation P(x) halts with output f(x)

. Terminology
  . Partial recursive functions
  = Partial functions (int to int) that are computable

. Halting function
  . Decide whether program halts on input
  . Given program P and input x to P
  . Halt(P, x) = yes if P(x) halts, no otherwise
  . Clarifications
  . Assume program P requires one string input x
     Write P9x) for output of P when run in input x
     Program P is string input to Halt
  . Fact : There is no program for Halt.

. Unsolvability of the halting problem
  . Suppose P solves variant of halting problem
  . On input Q, assume, P(Q) = yes if Q(Q) halts, no otherwise
  . Build program D - P로 D를 만들자
  . D(Q) = run forever if Q(Q) halts, if Q(Q) runs forever

. Does this make sense? What can D(D) do?
  . If D(D) halts, then D(D) runs forever.
  . IF D(D) runs forever, then D(D) halts
  . Contradiction : program P must not exist

. Main points about computability
  . Some functions are computable, some are not
  . Halting problem

. Programming langage implementation
  . Can report error if program result is undefined due to division by zero, other undefined basic operation
  . Cannot report error if program will not terminate

. RE(Regular expression) < CFG(Context Free Grammar)
  < TM (Turing Machine) != not computable
. RE = DFA, NFA, e-DFA
. RE + stack = Push-down automata = CFG
. CFG + Tape = TM = Computable

. Diversion
  . C : Kills the people once saved
  . C++ : The empire strikes back
  . Java - Don't drink don't smoke - what do you do?
  . C++이 복잡해서 필요한 것만 넣음.
     strong typed, 그런데 결국은 다시 복잡해짐.
  . Perl : Feel free to substitute your favorite error prone language

. scripting language
  . Automating simple computer tasks
  . Connecting diverse pre-existing components to accomplish a new related task
  . Rapid development

윈도우 미디어 플레이어(Window media player)에서
스트리밍(streaming)이 재생되지 않을 때.

시작 -> 프로그램 -> 윈도우 미디어 플레이어
-> 도구 -> 옵션 -> 네트워크 -> 스트리밍 프로토콜
-> 멀티캐스트, UDP, TCP, HTTP 모두 check

. scoping
  . 여러 scope에 같은 variable name이 출현할 때, 어디에 binding 할지 정하는 것

. static scoping
  . = lexical scoping
  . a variable always refers to its nearest enclosing binding
  . unrelated to the runtime call stack
  . compile time에 binding을 결정

ex)
int x = 0;
int f () { return x; }
int g () { int x = 1; return f(); }

g()는 0을 retrun 함

. dynamic scoping
  . control flow를 따라 global x stack에 값을 push, pop함.
  . run time에 binding을 결정

ex)
int x = 0;
int f () { return x; }
int g () { int x = 1; return f(); }

g()는 1을 retrun 함

. homomorphism
  . pi : X->Y
  . pi(u*v) = pi(u)+pi(v)
  . * : operation on X
  . + : operation on Y

. Morphism
  . two mathematical structure간의 structure-preseving process.
  . set theory에서는 functions
  . group theory에서는 group homomorphisms
  . topology에서는 continuous functions
  . universal algebra에서는 homomorphisms
  . category theory에서는 domain와 codomain의 relationship
  . identity morphism이 있어서 그것과 composite해도 자기 자신이 나온다.
  . associativity가 있어야 한다.
  x*(y*z) = (x*y)*z

. one-to-one(injective)
  일대일
  x의 모든 원소가 y에 대응됨.

. onto(surjective)
  y의 모든 원소가 x에 대응됨.

. bijective : injective and surjective
  일대일대응

. monomorphism
  . f*g1 = f*g2이면 g1 = g2 일 때, f는 monomorphism이다.
  . f : X->Y
  . g1, g2 : Z->X
  . f*g1, f*g2 : Z->Y
  . injective homomorphism

. split monomorphism
  . left-inverse를 가지는 monomorphism

. epimorphism
  . http://en.wikipedia.org/wiki/Epimorphism
  . g1*f = g2*f이면 g1 = g2 일 때, f는 epimorphism이다.
  . f : X->Y
  . g1, g2 : Y->Z
  . g1*f, g2*f : X->Z
  . right-cancellable
  . surjective homomorphism
  . monomorphism와 dual 관계

. bimorphism
  . epimorphism and monomorphism

. isomorphism
  . bijective homomorphism
  . morphism : f : X->Y 일때
  f*g = idY and g*f = idx인 g:Y->X가 존재한다.
  . morphism has both left-inverse and right-inverse, then
  left-inverse and right-inverse are equal.
  . http://en.wikipedia.org/wiki/Isomorphic
  . bijective(one-to-one and onto) map, f and f^-1이 homomorphism하다.
  . 두 structure가 isomorphic하면 structurally identical하다고 할 수 있다.
  . 한 structure에서 theorem이 증명되었으면
  새로운 structure와 isomorphism이라는 것만 증명하면
  그것들을 그대로 옮겨와서 사용할 수 있다.
  . 모든 isomorphism은 bimorphism이다. (역은 아님)

. endomorphism
  . http://en.wikipedia.org/wiki/Endomorphism
  . f:X -> X인 f를 endomorphism of X라고 함.

. automorphism
  . http://en.wikipedia.org/wiki/Automorphism
  . endomorphism and isomorphism
  . closure : 2개의 endomorphism의 composite는 또 다른 endomorphism이 됨.
  . associativity : morphism은 정의상 항상 associative하다.
  . identity : morphism은 정의상 항상 identity를 가진다.
  . inverses : 정의상 inverses를 가진다.

. antihomomorphism
  . http://en.wikipedia.org/wiki/Antiautomorphism
  . pi : X->Y
  . pi(xy) = pi(y)pi(x)
  . 곱셈의 순서를 reverse함.

. diffeomorphism
  . f:M->N이 bijective map이고
  f:M->N, f^-1:N->M 이 모두 dirrentiable할 때

. Polymorphism
  . http://en.wikipedia.org/wiki/Polymorphism_%28computer_science%29
  . single definision이 different types of data에 사용될 수 있을 때
  . ML에서 사용됨.

. holomorphism
  . http://en.wikipedia.org/wiki/Holomorphism
  . open subset of the complex number plane C 정의된 모든 값이
  differentiable할 때.
  . U : open subsete of C
  . f : U -> C, complex diffentiable at z0
  . f'(z0) = lim z->z0, (f(z)-f(z0))/(z-z0)

. isometry
  . isometric isomorphism
  . congruence mapping
  . disstance-preserving isomorphism
  . f : X->Y
  . X, Y be metric space with dx, dy
  . dy(f(x), f(y)) = dx(x, y)

. global isometry
  . bijective distance preserving map

. path isometry
  . arcwise isometry
  . preserve the lengths of curves

. idempotence
  . http://en.wikipedia.org/wiki/Idempotent
  . binary operation일때, 자기 자신을 연산하면 자신이 나옴.
   ex) binary number system의 multiplication
  . unary operation일때, 자기 자신에게 두번 연산을 apply하면 한번 연산했을 때와 같은 결과가 나옴.
   ex) min, max

. Text
  Concepts in programming languages, John C. Mitchell

. 교과서
. Computability
  어떤 문제가 계산가능하고 아닌지 판별함.
  컴퓨터가 풀 수 있는 문제의 영역을 정의함.
  예를들어 halting problem을 푸는 program은 undecidable하기 때문에 만들 수 없음.

. compile-time : program은 주어졌지만 input은 주어지지 않았음.
  (conservative, static)

. Run-time : program과 input 모두 주어져 있음.
  http://en.wikipedia.org/wiki/Runtime
  프로그램이 수행중인 상태(from beginning to termination)
  (dynamic)
  type check, array boundary check, garbage collection, exception handling 등을 할 수 있다.

. exception handling
  http://en.wikipedia.org/wiki/Exception_handling
  정상적인 excution flow에 영항을 주는 어떤 조건이 일어났을 때, 그것을 처리하기 위한 방법
  signal, event handler등을 사용할 수 있다.
  ex) page fault, divide by zero

. garbage collection
  http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29
  Automatic memory management
  더 이상 사용되지 않는(access되지 않는) memory space를 찾아내서 다른 곳에 이용할 수 있게 만듬.

. automatic method
  사용자가 신경을 덜 쓸 수 있게 해준다. 에러를 덜 내게 도와준다.
  실행 속도가 느려진다. (efficiency가 떨어진다.)

. Languages : Listp, ML, C, C++, Smalltalk, Algol, cobol, Fortran ..

. 1950년대 programming language를 만든 이유
  . computer instruction을 쉽게 적기 위해서
  . 당시에는 컴퓨터가 비싼 것이었으므로 small and efficiency가 매우 중요했음.

. BNF : Backus Naur Form, Fortran의 문법을 기술하기 위해 사용됨.

. Fortran
  . 최초로 ordinary mathematical notation을 expression에서 사용하게 됨.
  . subroutine, arrays, formatted input and output 지원
  . recursive call을 안됨.

. subroutine(procedure, function)
  큰 프로그램의 일부분으로 특정한 작업을 다른 곳과 비교적 독립적으로 수행한다.
  http://en.wikipedia.org/wiki/Subroutine

. array : 같은 type의 데이터를 담는 연속된 메모리 공간
  index(offset)을 통해 접근할 수 있다.
  multi-dimensional array도 가능하다.
  http://en.wikipedia.org/wiki/Array
  장점 : access가 O(1)에 가능, locality of reference(Sequential locality)가 있어서 좋다.
  단점 : 중간에 있는 원소를 insert, delete 할 때 O(n)

. locality of reference
  http://en.wikipedia.org/wiki/Locality_of_reference
  . Temporal locality : 한 곳이 reference되면 가까운 시간 내에 다시 그 곳이 reference된다.
  . Spatial locality : 한 곳이 reference되면 그 근처도 reference될 확률이 크다.
  . Sequential locality : memory는 sequential하게 access될 확률이 높다.

. formatted input and output
  변수를 받고 찍을 때 형식(format)을 정의할 수 있다.
  예를 들면 C에서 printf("%d", 변수)를 하면 정수형이 되고
  printf("%.3f", 변수)를 하면 소수 셋째짜리까지 출력한다.

. Cobol
  . business application을 위해 만들어짐.
  . common english와 비슷한 문법

. Lisp, Algol
  . stack memory management
  . recursive functions or procedures

. Lisp
  . higher-order function
  . http://en.wikipedia.org/wiki/Higher_order_function
  . Take one or more functions as an input
  . output a function
  . garbage collection

. Algol
  . type system
  . data structuring

. records(or structs, composition)
  http://en.wikipedia.org/wiki/Record_%28computer_science%29
  단순하고 관련있는 data, object를 모아서 함께 관리하는 것.
  관리하기 편해지고 spatial locality를 이용할 수 있어서 좋다.

. abstract data types(ADT)
  http://en.wikipedia.org/wiki/Abstract_data_types
  data들과 그 data들에 수행할 수 있는 operation들을 모은 것
  information hiding을 통해 user가 알지 않아도 되는 implementation detail을 숨긴다.
  ex) Java - List, Stack, Queue, Map, Priority Queue
     C++ - STL containers

. objects
  어떤 것(물건, 값의 덩어리). 특정한 크기로 특정한 곳에 있는 연속된 메모리 공간으로 관리된다.

. interoperability
  http://en.wikipedia.org/wiki/Interoperability
  공동의 작업을 위해 서로 다른 system이 같이 일할 수 있는 능력.

. global variable (free variable)
  http://en.wikipedia.org/wiki/Global_variable
  어떤 subroutine에도 속하지 않고 프로그램의 어느 context에서든 access될 수 있다.

. local variable
  local scope, function, block 내에서 자신이 declare된 것에서만 acess 될 수 있다.
  call stack에 주로 저장한다.
  recursive call을 할 경우 각 instance에 대해서만 local variable이 유효하다.
  (서로 다른 memory 공간을 이용한다.)

. static local variable
  local variable처럼 특정 function에서만 access되지만
  recursive call을 하거나 그 function을 다음번에 다시 call했을 때도
  같은 memory 공간을 이용한다.

. argument

. parameter

. expression
  evaluation이 가능한 단위, 대부분 evaluation value를 가진다.

. script language

. referential transparency

. side-effects

------------
. 강의노트
. Function call의 overhead는 얼마나 큰가?
. abstract을 위해 지불한 cost는 무엇인가?
. Lanugage
  . a conceptual universe
  . framework for problem-solving
  . useful conecpts and programming methods
. understand the languages you use, by comparison
. appreciate history, diversity of ideas in programming
. be prepared for new programming methods, paradigms

. critical thought
  . properties of languages, not syntax or sales pitch - syntax는 그리 중요하지 않다.
  . sales pitch : A salesperson's talk is what they say in order to persuade someone to buy something from them = sales talk

. lagnuage and implementation
  . every conveniecn has its cost

. value of language concepts
  . parable : a short story which is told in order to make a normal or religious point
  . 과거에는 recursive call, data structure는 없었지만 지금은 어디서나 쓴다.
. Moral - principles and beliefs concerning right and wrong behaviour
. current examples
  . function passing : STL functino objects 같은 걸로 C++에서도 구현되어 있다.
  . continuation : used in web languages for workflow processing
  . 앞으로 할 일을 function으로 define 한 것
  . representation of execution state

. function object = functor(class object에서 operator()를 overload함)
  . function object가 function의 pointer보다 나은 점
  1. result를 global, local variable이 아닌 member variable로 가질 수 있어 안전하다.
  2. inline이 가능하다.(compiler가 지원하면)

. Language in common use
  . C가 줄고 C++도 약간 줄었다.
  . Java가 많이 늘었다. (Sun microsystems) - OOP가 유행이다.
  . PHP가 늘었다. - 웹 프로그램을 많이 한다.(java, php의 증가)
  . Perl이 줄었다.
  . C#도 순위권에 들기 시작했다. - MS가 밀고 있음.

. Language groups
  . Multi-purpose languages
  . C, C++, Java
  . Visual Basic
  . Object pascal : Delphi, Kylix
  . Lisp, scheme, ML
  . Scripting languages
  . Perl, PHP
  . Tcl, Shell
  . Special-purpose languages
  . SQL
  . Prolog

. Commercial trend over past 5 years
  . Increasing use of type-safe languages : Java, C#
  (compile time에 에러잡기, type checking)
  . scripting languages, other languages for web applications
  . Perl is widely known as "the duct-tape of the Internet"

. Teaching trends
  . Java replacing C as most common intro language
  . Less emphasis on how data, control represented in machine

. Research and development trends
  . Modularity
  . Java, C++ : standardization of new module features
  . Program analysis
  . Automated error detection, programming env, compilation
  . isolation and security(특히 web에서)
  . sandboxing, language-based security

. sandbox
  . a security mechanism for safely running prrograms
  . Hydra라는 OS에서 나옴, OS가 특정 process의 resource를 제한함.

. What's worth studying
  . Dominant languages and paradigms
  . C, C++, Java
  . Imperative and object-oriented languages
  . Important implementation ideas
  . Performance challenges
  . Concurrency
  . Design tradeoffs
  . Concepts that research community is exploring for new programming languages and tools

. Programming Domains
  . Scientific applications - Fortran
  . Large number of floating point computations
  . Business applications
  . Produce reports, use decimal numbers and characters
  . 유효자리계산, truncation, 은행 등.
  . Arificial intelligence - prolog, lisp
  . smbols rather than numbers manipulated
  . system programming - C
  . Need efficiency because of continuous use
  . scripting languages - shell, JCL(Job control language), Perl
  . Put a list of commands in a file to be executed
  . Special-purpose languages - SQL

. floating point의 문제점
  . 너무 큰 수와 너무 작은 수를 곱하고, 나누었을 때
  . 계산속도(time complexity)
  . Overflow

. Language evaluation criteria
  . readability factors
  . the most important criterium
  . factors
     . overall simplicity
       . Too many features is bad
       . multiplicity of features is bad
     . Orthogonality
       . makes the language easy to learn and read
       . Meaning is context independent
       . A relatively small set of primitive constructs can be combined in a relatively small number of ways
       . Every possible combination is legal
         (모든 combination이 다 된다.)
       . Lack of orthogonality leads to exceptions to rules
       예) int 덧셈이 되면 float, struct도 더해진다.
     . Control statements - if, switch-case
     . Defining data types and structures
     . Syntax considerations
       . Identifier forms - 변수명 정하기
       . Special words - reserved word
       . form and meaning
  . Writerability
  . factors
     . simplicity and orthogonality
     . support for abstraction - function, abstract data type, class, object
     . Expressivity(표현력)
  . Reliability
  . Type checking
  . Exception handling - 코드의 80%는 error handling code
  . aliasing(2개 이상의 이름을 가짐), pointer
     . 한 메모리 공간을 여러방법으로 access해서 바꿀 수 있음.
  . Readability and writability
  . Cost
  . categories
     . training programmers to use language
     . writing programs
     . compiling programs
     . executing programs
     . language implementation system
     . reliability
     . maintaining programs
  . Others : portability, generality, well-definedness

. Influences on Language desing
  . computer architecture : Von Neumann
  . Stored Program Computer
  (Instruction과 data를 함께 다룸)
  . We use imperative languages, at least in part, because we use von Neumann machines. -> assignment statement가 생긴다.
  . Data and programs stored in same memory
  . Memory is seperatef from CPU
  . Instructions and data are piped from memory to CPU
  . Basis for imperative languages
  . Variable model memory cells
  . Assignment statements model piping, sequence가 있다.
  . Iteration is efficient
  . Von neuman bottle neck
  . http://en.wikipedia.org/wiki/Von_Neumann_bottleneck
  . 문제점 : processing element와 memory사이의 traffic을 instruction이 차지한다.

. Von Neumann Architecture가 아닌 것 중 살아남은 것이 없다.
. Optical computer - 2D 계산이 가능
. Bio computer

. Von neumann architecture
  . Memory stores both instructions and data
  . CPU -> memory : Results of operations
  . memory -> CPU : Instructions and data
  . CPU : ALU(Arithmetic and logic unit) + Control Unit

. Influences on Language Design
  . Programming methodologies
  . 1950s and earcly 1960s : Simple applications; worry about machine efficiency
  . Late 1960s : Prople efficiency became important; readability, better control structures
     . structured programming - goto를 안 쓰는 것, if, then, for, case 이용
       . Procedural programming
         . Goto, jump(spaghetti code) 대신 control statement를 쓴다.
         . program을 procedure로 잘 나눠서 copy하지 않고 reuse한다.
  . Top-down design and step-wise refinement
  . Late 1970 : Process-oriented to data-oriented
     . data abstraction
       . concept에 집중하게하고 내부 detail을 가린다.
  . Middle 1980s : Object-oriented proramming(OOP)
  . HIPO : Hierarchical Input Processing Output

. Imperative
  . Central features are variables, assignment statements, and iteration
  . C, Pascal

. Functional
  . Main means of making computations is by applying functions to given parameters
  . 수학에서는 문자의 값이 바뀌지 않음.
  . 모든 name은 1개의 value를 가진다.
  . LISP, Scheme, ML

. Logic(declarative language)
  . http://en.wikipedia.org/wiki/Special:Search?search=declarative+language
  . Rule-based
  . Rules are specified in no special order
  . Prolog, SQL
  . solution define하는 것이 아니라 problem을 describe함.
  . Say 'what'
  . Imperative language says 'how'

. Object-oriented
  . Encapsulate data objects with processing
  . Information hiding, separation of concerns.
  . http://en.wikipedia.org/wiki/Information_hiding
  . http://en.wikipedia.org/wiki/Separation_of_concerns
  . Inheritance and dynamic type binding
  . Grwe out of imperative languages
  . C++, Java

. Language design trade-offs
  . Reliability vs cost of execution
  . 어려 검사를 많이 하면 느려진다.
  . Readability vs writability
  . 읽기 쉬운 것은 쓰는 데 노력이 필요하다.
  . 쉽게 쓰면 읽기 어렵다.
  . Flexibility vs safety
  . 뭐든 다 허용하면 위험하다.
  . 아무것도 안되면 불편하다.

. Language-based organization
  . Algol 60, algol 68, Pascal
  . Modula, Clu, Ada
  . Additional languages grouped by paradigm
  . Lisp/Scheme/ML for functional languages
  . Prolog and Logic Programming
  . C++, Smalltalk and OOP
  . Concurrency via Ada rendez-vous
  . Author's opinion
  . Historical concepts are same across many languages
     . Block strcture, scope, memory management
  . OOP deserves greater emphasis
  . Concep-based organization
  . Use single language like List/Scheme
  . Present PL concepts by showing how to define them
  . Advantage : Uniform syntax, easy to compare features
  . Disadvantage
  . Miss a lot of the culture associated with languages
  . Some features hard to add
     . Type systems, program-structuring mechanisms
     . Approach works best for 'local' features, not global structure
  . Programming in the small
  . Cover traditional algol, pascal constructs in NL
  . Block structure, activation record
     . Activation record
       . http://en.wikipedia.org/wiki/Activation_record
       . execution stack, control stack, function stack
       . local data storage
       . Parameter passing
       . Evaluation stack
       . Other return state
       . stack pointer
       . frame pointer
  . Types and type systems.
  . Lisp/Scheme concepts in ML too
     . Higher order functions and closures, tail recursion
       . tail recursion
         . http://en.wikipedia.org/wiki/Tail_recursion
         . recursion의 special case로 iteration으로 쉽게 바꿀 수 있다.
         . 사용하는 stack space를 줄여서 efficiency를 높힌다.
     . Exceptions, continuations
       . continuations
         . http://en.wikipedia.org/wiki/Continuation
         . representation of the execution state of a program(ex. call stack)
         . save the current execution state into an object
         . and then restore the state from this object at a later point in time(thereby resuming its execution)
         . Scheme : call/cc
         . C : callcc
       . escape continuation
         . escape the current context to a surrounding one.
         . C : setjmp, longjmp
         . tail-call optimization, exception handling에 쓰임.
         . 단점 : Goto statement와 비슷하다. 코드가 따라가기 어려워진다.
  . Programming in the large
  . Modularity and program structure
  . Specific emphasis on OOP
     . Smalltalk vs C++ vs Java
     . Language design and implementation
    
  . Concurrent and distributed programming
  . General issues in concurrent programming
  . Actor languages : an attempt at idealization
  . Concurrent NL
  . Java threads

  . Do we emphasize C?
  . Important, practical language
  . We discuss other languages, compare to C as we go
     . Intro to C for Java programmers?
  . We do cover the ++ par of C++ in some detail

. First half of course
  . Lisp
  . Foundations
  . Lambda calculus
  . Denotational Semantics
  . Functional vs Imperative programming
  . Conventional programing language concepts
  . ML/Algol language summary
  . Types and type inference
  . Block structure and memory management
  . Control constructs
  . Other languages using same basic ideas
  . Scripting languages
  . Domain-specific languages

. Second half of course
  . Modularity, data abstraction, objects
  . Object-oriented languages
  . Smalltalk and Self
  . C++
  . Java
  . Concurrent and distributed programming
  . Interoperability
  . Conclusions and review

. coroutine
  . http://en.wikipedia.org/wiki/Coroutine
  . allow multiple entry points
  . suspending and resuming of execution at certain locations
  . More generic and flexible than subroutine
  . Less widely used in practice
  . return multiple times
  . Simula, Modula-2, C#, Python, stackless Python에서 이용
  . stack대신 continuations을 이용하여 다른 것을 call함.
  . state machine, cooperative multitasking

. lazy evaluation
  . http://en.wikipedia.org/wiki/Lazy_evaluation
  . delay computation of expressions until the results of the computation are known to be needed.
  . delayed evaluation, minimal evaluation
  . unnecessary calculation을 줄여 performance에 도움이 될 수도 있다.
  . 예를 들어 infinite data structures도 만들 수 있다.
  . infinite list = stream
  . call-by-need에 사용된다. ex) Haskell

. Minimal evaluation
  .evaluate until the point where its final value is known.
  ex) if (A & B)에서 A가 거짓이면 B는 evaluation하지 않는 다.

. Eager evaluation(strict evaluation)
. expression을 바로바로 evaluation함.
. 한 번 해두면 다시 하지 않아도 되서 빠를 수 있음.

. Strict programming language
  . strict evaluation을 함.
  . C, C++, Java, Perl 5, Ruby, Common Lisp, Scheme, ML

. Nonstrict programming language
  . lazy evaluation을 함.
  . 거의 반드시 functional language 이어야 한다.
  . Haskell, Miranda, clean

. 한글
  Alt + +(function key 아래 있는 것)
  function key 아래 있는 +가 없는 노트북 키보드에서는 누를 수 없다.

. MS word
  그냥 space bar를 누른다.

. transpose
  . aij와 aji을 바꾸는 연산

. Band matrix
  . 1 < p , q < n
  . aij = 0 if p <= j-i or q <= i-j
  . bandwidth : w = p + q - 1

. strictly diagonally dominant
  . A : n x n
  . |aii| > sigma((j = 1..n, j !=i), |aij|)

. Positive definite
  . It's symmetric
  . And x^T*A*x > 0 for every n-dimensional vector x != 0
  . x^T*A*x = sigma(i=1..n, sigma(j=1..n, aij*xi*xj))
  . Theorem : If A is positive definite matrix
   . A has an inverse
   . aii > 0
   . max 1<=k,j<=n |akj| <= max 1<=i<=n |aii|
   . (aij)^2 < aiiajj, for each i !=j

. leading principal submatrix
  . A : n x n일 때
  . 1<=k<=n 이면 Ak = 가장 처음 k x k 원소만 모은 Matrix

. Diagonal matrix
  . p = 1, q = 1인 band matrix
  . bandwidth = 1

. Tridiagonal matrix
  . p = 2, q = 2인 band matrix
  . bandwidth = 3

. cyclic tridiagonal matrix
  . Tridiagonal matrix에 [1,n], [n,1]에 값을 채워 넣은 것
  . 모든 row가 각각 3개의 원소, 모든 column이 각각 3개의 원소로 구성되어 있다.

. symmetric matrix
  A = A^T

. symmetric cyclic tridiagonal matrix
  ex) closed natural B-spline curve의 control vertex와 

. LU factorization
  . A = LU
  . L : lower triangular matrix
  . U : upper triangular matrix
  . Gaussian Elimination을 이용하면 구할 수 있다.
  . Crout Factorization for tridiagonal linear systems

Matlab에서 LU factorization(decomposition) 하기
X = [[4 1 0 0 1];[1 4 1 0 0];[0 1 4 1 0];[0 0 1 4 1];[1 0 0 1 4]]
[L,U] = lu(X)
inv(U)

maple에서 LU factorization(decomposition) 하기
with(linalg):
A := matrix([[4,1,0,0,1],[1,4,1,0,0],[0,1,4,1,0],[0,0,1,4,1],[1,0,0,1,4]]);
U:=LUdecomp(A);
L:=evalm(A&*inverse(U));
inverse(L);

. QR factorization
  . A = QR
  . R : upper triangular
  . Q^T * Q = I
  . Q^T : Transpose of Q
  . I : identity matrix

. LDL^T Factorization
  . A = LDL^T
  . L : lower triangular matrix with 1's along the diagonal
  . D : diagonal matrix with positive entries on the diagonal.

. Cholesky
  . A = L*L^T
  . L : lower triangular



. 참고서적
  . Linear algebra - 쉬운 것은 개론책 어려운 것은 일반 책을 본다.
  . Calculus, Numerical Analysis 책들에도 기본적인 것들은 언급된다.