[PL]Ch.5 - The algol Family adn ML

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[PL]Ch.6 - Types

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  s = t -> r

  t : domain
  r : range(codomain)

. Abstraction
  lx.e

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

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

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

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

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

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

. ML also has module system with explicit type parameters

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

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

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

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

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

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

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

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

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

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

  . + : int -> int -> int

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

[소설]토마스 하디 - 아내를 위하여

. 토마스 하디
  1840년 영국의 건축가, 소설가.
  테스, 귀향, 아내를 위하여 등의 소설을 씀.
  문학은 독학으로 공부함.
  영국 남서부 웨섹스 지방을 배경으로 함..
  공동체의 붕괴, 계급간의 갈등, 종교적 회의 등.
  사회 계량주의자
  기독교 신앙에 회의를 느낌.
  개인의 의지와 선택의 폭이 그리 크지 않고 환경이 주인공을 지배함.
  내재적 의지 - 우주의 맹목적 의지

. 배경 : 바닷가 마을

. 등장인물
  쉐이드릭 - 주인공, 작은 배의 선장, 종교적이고 고지식함.
  에밀리 - 첫번째 여자친구, 내성적, 부자 상인과 결혼
  조안나 - 두번째 여자친구(아내), 질투심이 강함, 쉐이드릭과 결혼

. 내용
  두 여자와 갈등하다가 결국 조안나와 결혼함.
  조안나의 집은 점점 가난해지고, 에밀리는 점점 부자가 됨.
  쉐이드릭은 장사에 전혀 소질이 없었고 뱃일 밖에 몰랐음.
  조안나는 에밀리의 집안을 엄청나게 질투하게 되고 돈에 대한 욕심이 매우 커짐.
  결국 조안나와 쉐이드릭은 위험하지만 두 아들과 전재산을 걸고
  다시 바다로 나가게 됨.
  결국 조안나는 늙고 병들어 버리고 에밀리의 집에서 얹혀 살게 됨.
  쉐이드릭과 그 아들들은 영영 돌아오지 않음.

  조안나의 야심은 쉐이드릭의 성격과 어울리지 않음.
  조안나는 자신과 사실 관련이 없는 에밀리를 질투하여 평생 고통을 겪게 됨.
  조안나는 과거만 생각하면서 현실을 받아들이지 못함. 비극적 결말

[PL]Ch.4 - Fundamentals

. 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

bidet(비데)

CT 대학원이 생긴지 얼마 안되서 interior가 화려한 편이다.
원래 산디과에 있던 학제전공이라서 더 그런것 같다.
아무튼 화장실도 꽤 깔끔하고 신기한 편인데,
들어가보니 비데가 있었다.
(돈많은 전자과, 일부 화장실에만 있다는 그 물건;)

heating기능이 있어서 의자도 따뜻하게 데우고 있었다.
그냥 버튼만 이리저리 눌러봤는 데, 반응이 없었다.

센서가 있어서 사람이 앉아있지 않으면 동작이 되지 않는 모양이다.
그래서 센서를 손으로 가리고 버튼을 눌렀더니,
숨겨져있는 분수꼭지가 나와서는 폭포수처럼 물을 뿌리고는 사라졌다.
(그럴 줄 알고 옆으로 피해 있었다.;)

드라이 기능, 온도 조절기능, 물 세기 조절 기능 등 많은 기능이 있더군.
다음번에는 진짜로 써봐야지..

----------------------------
비데는 원래 중세 시대(십자군 시대)에 피임용, 의료용 등으로 고안되었다고 한다.
좌욕기와 거의 비슷했나보다.

[Math]Gradient, curl, divergence

. 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

[PL]Ch.3 - LISP

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