. 2005년 중간고사 족보
3. 다음 용어를 설명하라.
1. Imperative programming language
statement(instruction)들이 줄지어 있어서 어떤 일을 할 지 sequential하게 적는 다.
assignment statement가 있다. (side-effect가 있다.)
Von neumann architecture에서 기본적으로 나온다.
2. Binding and binding time
binding : value와 identifier를 연결한다.
binding time에는 static(early, compile time)과
dynamic(late, virtual, run-time)이 있다.
binding을 언제 결정할지 정하는 것.
3. Parse tree
formal grammar에 따라 string을 sytatic structure를 가진 tree로 나타낸 것.
parser에 의해 generate된다.
4. Derivation
parse tree로 나타낼 수 있는 방법의 한 종류,
left-derivation과 right-derivation이 있다.
left-derivation에서는 항상 left child쪽으로 derivation을 하고
right-derivation에서는 항상 right child쪽으로 derivation을 한다.
5. LR(k)
LR parser : CFG의 bottom-up parser의 일종
left에서 right로 읽어 right-derivation을 한다.
k는 unconsumed look ahead input symbol의 갯수
6. ambiguity of grammars(ambiguous grammar)
parse tree를 한 가지 이상의 방법으로 generate할 수 있을 때
어떤 방식을 선택할 지 ambiguity가 발생한다.
해결을 위해서는 grammar를 ambiguity없이 다시 쓰거나
precedency나 associativity를 정해 준다.
7. dynamic scope
runtime에 bing이 결정됨.
함수 call 순서의 영향을 받음.
perl, common lisp등에서 사용.
8. virtual machine
http://en.wikipedia.org/wiki/Java_virtual_machine
언어와 실제 machine의 중간 쯤 되는 가상적인 것.
중간코드와 실제 machine사이에서 돈다.
Portability 등을 위해 사용되기도 한다.
Java virtual machine 같은 예가 있다.
9. Overloading
함수나 operator의 argument(input, operand) type에 따라
각자에 맞는 알고리즘(다른 알고리즘)을 적용하여 계산한다.
같은 name을 가졌지만 type에 따라 다른 일을 한다.
10. aliasing
memory 장소(값)을 하나 이상의 변수로 가리키는 것
11. value model of variabls
http://en.wikipedia.org/wiki/Variable
12. referentially transparent (referential transparency)
subexpression을 의미의 변화없이 value로 substitute할 수 있음.
13. polymorphism
여러 type에 대해 동일한 algorithm을 적용해서 각 input type과 관련된 output을 줄 수 있음.
14. Short-circuiting
필요하지 않은 것은 evaluation하지 않음.
boolean or : e1이 true이면 e2는 eval하지 않고 true를 return함 e2가 undefined라도 상관없음.
15. side effect
어떤 function이 return value외에 다른 값을 바꿀 때.
assigment statement가 있으면 side effect가 발생한다.
일반적으로 imperative programming language는 side effect가 있고
functional language는 side effect를 최소화하려고 한다.
Pure lisp의 경우 side effect가 없다.
16. tail recursion
recursion을 iteration으로 쉽게 바꿀 수 있는 special case
stack에 값을 누적하지 않으므로 spack space를 줄일 수 있다.
17. type system
type check를 하는 system
type간의 관계를 정의하고 각 변수, input, output type을 검사한다.
type inference, casting, coercion을 할 수도 있다.
http://en.wikipedia.org/wiki/Type_checking
value와 variable을 type으로 classify한다.
각 type들을 어떻게 manipulate하고 그들이 어떻게 interact하는 지 정의한다.
18. strong typing
conservative하게 type을 check함(sound)
이것을 통과한 것에 대해서는 항상 type-safe하다고 할 수 있다.
영원이 돌거나 의도한 결과를 준다.
19. coercion vs casting
http://en.wikipedia.org/wiki/Type_casting
coercion : implicit type conversion
compiler가 automatic하게 바꾼다.
casting : expilcit type conversion
checked : type을 바꾸기전에 가능한 것인지 확인한다.
unchecked : check를 안한다.
bit pattern : bit representation이 그냥 복사된다.
20. control flow statement 중 selection statement의 종류를 나열하라.
. control flow statement
http://en.wikipedia.org/wiki/Control_flow
sequential order에 변화를 줄 수 있는 statement
labels, goto, subroutines, if then else, loop, conditions, exception, nonlocal goto
. selection statement
if then, if then else, else if, switch-case, computed goto, arithmetic if,
21. subroutine closure
http://en.wikipedia.org/wiki/Closure_%28computer_science%29
. a subroutine bundled together with a referencing environment
. a closure is a function that refers to free variables in its lexicla context.
22. applicative-order evaluation
http://en.wikipedia.org/wiki/Applicative-order_evaluation
evaluation strategy의 하나.
function의 argument가 left to right 순의 post-order traversal로 reduce됨.
function bod에서 가능한한 많은 evaluation을 reduce함.
23. Name equivalence of type checking
name이 같을 때 같은 type으로 본다.
C의 record, ada, modula-2
structural equivalence : structure가 같으면 같은 type으로 본다.
24. derived type vs subtype in ADA
25. Module type
. 2004년 중간고사 족보
1. 다음 용어를 설명하라.
1. type inference
strongly statically typed programing lagnuages의 특성
값에 type이 annotation되어 있지 않아도 자동으로 값의 type을 추론해냄.
각 값의 관계에 따라 type에 관한 equation을 만드록
그 equation을 풀면 된다.
2. coercion
3. virtual machine
http://en.wikipedia.org/wiki/Virtual_machine
User와 platform 환경 사이를 virtualize함.
4. type compatibility by name
5. overloaded operator (operator ad-hoc polymorphism)
http://en.wikipedia.org/wiki/Operator_overloading
operator의 argument의 type에 따라 다른 implementation을 사용하는 것
6. dangling pointer
http://en.wikipedia.org/wiki/Dangling_pointer
적절한 type의 object를 가리키고 있지 못하는 pointer,
잘못된 공간을 가리키고 있는 pointer
unpredictable한 결과를 초래할 수 있다.
7. axiomatic semantics
수학 logic을 이용하여 computer program의 correctness을 prove하는 것
8. interpreter
http://en.wikipedia.org/wiki/Interpreter_%28computing%29
a computer program that executes other programs.
source code를 바로 실행시킴.
반면에 compiler는 translate만 하고 execution은 안함.
prototyping이나 test시에 간편하게 쓰임.
9. aliasing
하나의 값을 2개 이상의 변수가 가리키는 것.
10. stack-dynamic array
http://www2.hawaii.edu/~cheungca/ICS313/hw6/2031.txt
Stack-dynamic array have dynamically bound subscript ranges and dynamic storage allocation at run time and have greater flexibility not requiring array size until used.
Fixed heap-dynamic array have dynamically bound subscript ranges and dynamic storage allocation, but are static after storage allocation on a heap, rather than stack, and are bound when at user-program request. Heap-dynamic array have dynamic binding of subscript ranges and storage allocation, can change, if flexible, and can adapt to the size required.
11. orthogonality in programming language
어떤 조합이든 valid하게 정의되어 사용될 수 있는 것,
record의 array, int array, float array, array의 record 등이 모두 가능.
primitive type과 combination, operator와 operand 등.
12. enumeration type (enumerated type)
http://en.wikipedia.org/wiki/Enumerated_type
programmer가 a finite list로 data type의 value를 정의한 것.
C언어에서는 enum으로 정의가능.
13. reference count for memory management
각 memory cell이 자신을 가리키고 있는 reference(pointer)의 갯수를
가지고 있음. reference count가 0이 되면 garbage collect됨.
14. grammar가 ambiguous하다.
http://en.wikipedia.org/wiki/Ambiguous_grammar
어떤 string이 여러가지 방법으로 parse tree가 생성될 수 있다.
2. subtype and derived type
http://en.wikipedia.org/wiki/Subtype
supertype에 관련되어 만들어진 type.
derived type
original type과 구조적으로 같지만 다른 type으로 정의된 것.
의도적으로 두 개를 별개의 type으로 보기 위해 이름을 다르게 붙인 것.
subtype과 derived type의 공통점 : 원래 type으로 부터 나온다.
원래 type의 구조를 포함하고 있다.
차이점 : derived type은 원래 type과 구조가 같지만
subtype은 원래 type에 일부 구조를 더 할 수 있다.
3. 각 binding time에 일어나는 binding을 여러분이 아는 language에서 예를 하나씩 들어라.
1. language design time
2. language impelmentation time
3. compile time by translator(compiler)
4. runtime on entry of subprogram
5. runtime at arbitrary point of execution
4. static array int A[LB1:UB1, LB2:UB2]가 있을 때
어떤 array element A[i,j]를 access하는 공식을 i, j의 함수로 나타내라.
필요한 상수는 정의하여 사용하고 그 값을 구하는 방법을 명기하라.
(row-major로 나열하라.)
row-major order
http://en.wikipedia.org/wiki/Row_major
NUMROWS = LB1 - UB1 + 1
NUMCOLS = LB2 - UB2 + 1
A[i, j]
row-major일 때
offset = (i - LB1) * NUMCOLS + (j - LB2)
column-major일 때
offset = (j - LB2) * NUMROWS + (i - LB1)
5. BNF로 정의된 grammar에 대하여 답하라.
<S> -> a <S> a | b <S> b | c
(1) parse tree 그리기
(2) grammar로 정의된 L를 우리말로 쓰기
(3)
. denotational semantics
M('c') = 0
M(a <S> a) = 2 * M(<S>)
M(b <S> b) = 2 * M(<S>) + 1
'babcbad'의 의미는 무엇인가?
2 * (2 * (2 * (0) + 1)) + 1 = 5
0을 2배해서 1 더하고 그것을 2배하고 다시 2배해서 1을 더한다.
=> 5
(4) <S> -> (a|b)<s>(a|b) | c
이 grammar는 원래 grammar와 같은 가?
다르다.
'bca'라는 string의 경우 원래 grammar에서는 안되지만
이 grammar에서는 된다.
증명) 원래 grammar에서는 a,b가 항상 짝수개만 올 수 있다.
6.
(1) union이란 무엇인가?
http://en.wikipedia.org/wiki/Union_%28computer_science%29
여러 종류의 type을 하나의 장소에 넣을 수 있다.
(2) 다음과 같은 program segment가 있을 때, 이 언어는 왜 compile time에
type compatibility를 check 할 수 있는 지/없는 지 이유를 말하라.
union (real, int) chameleon;
int intvar;
real reavar;
chameleon = intvar;
............
realvar = chameleon;
프로그램을 직접 수행하지 않고는 언제 chameleon이 int나 real로 되는 지
예측할 수 없다.
(3) 이러한 union type의 변수가 포함된 statement에서 type이 일치하는 지를
runtime에는 check할 수 있게 하는 방안을 설명하라.
union type의 변수에 tag를 달아서 현재 어떤 type의 값을 저장했는 지 기록한다.
assign시마다 assign하는 값의 type을 적어둔다.
