속눈썹맨의 블로그

. 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

. 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은
  실패하게 된다.

. 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

. 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 함

. 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