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