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