. 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
댓글 없음:
댓글 쓰기