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