[CS] 1. Programming Language, Compiler

이재호·2025년 2월 13일

cs

목록 보기

1/3

KAIST 전산한부 입시문제를 기반으로 하여 CS 공부를 시작하였다.
모든 문제의 출처: KAIST
https://docs.google.com/document/d/1ebOe9TvEFWVpae8cszHVoptYxwn8QACE/edit#heading=h.l0uypk9a8mxi

자바에서 public, protected, private 키워드가 있는데 아무것도 안 쓸 경우 default로 적용되는 범위는? 그렇게 디자인된 이유는?

자바에서 접근 제한자를 적용하지 않을 경우 즉, default로 적용되는 경우에 같은 패키지 내에서만 클래스, 변수, 메서드 등의 접근이 가능하다. 이는 protected 키워드와 마찬가지이며, 이렇게 적용되는 이유는 자바의 모듈성을 해치지 않기 위해서이다. 자바의 경우, 모듈화된 설계와 유지보수의 이점을 중점적으로 디자인되었다. 그렇기 때문에 default의 경우 동일한 패키지 내에서만 접근이 가능하도록 하고, 외부에서는 접근이 불가능하도록 하여 캡슐화 정책을 보장한다.
C++에서 서로 다른 타입의 오브젝트를 가리키는 포인터를 사용할 수 있나?

C++의 void* 타입의 경우 여러 타입의 할당이 가능하다. 즉, 이를 통해 서로 다른 타입의 오브젝트를 가리키는 포인터로 사용할 수 있다. 코드의 예시는 다음과 같다.
```
void* ptr;
int x = 10;
double y = 5.0;
ptr = &x; // void* <- int
ptr = &y; // void* <- double
```
또한 void* 를 제외하고 polymorphism을 통해서도 한 포인터가 서로 다른 오브젝트를 가리키도록 할 수 있다. 예시로 부모-자식 클래스 간의 polymorphism을 활용한 경우이다. 예시 코드는 다음과 같다.
```
class Parent {};
class Child: public Parent {};
Parent* ptr;
ptr = new Child(); // Parent* <- Child*
```
Higher-order function이 무엇인지 설명하고, 현대 프로그래밍에서 이 개념을 활용하여 쓰이는 대표적인 함수를 제시하시오.

직관적으로 설명하면 함수의 파라미터로 다른 함수를 받거나 다른 함수를 반환하는, 고차원 함수를 의미한다. 대표적으로 Python의 map 함수를 예시로 들 수 있다. 그리고 이를 설명하는 예시 코드는 다음과 같다.
```
def func_1(func, value):
	return func(value)
    
def func_2(value):
	return value ** 2
    
 print(func_1(func_2, 5)) # 출력 결과: 25
```
이처럼 func_1을 호출할 때 func_2라는 함수를 인자로 넣어주었고, func_1에서는 func라는 명으로 인자를 받아서 func(value)를 호출한 값을 반환한다.
파라미터 패싱 방식에는 eager evaluation 방식과 lazy evaluation 방식이 있다. 두 방식 의 차이점을 비교 설명하세요. call-by-value와 call-by-name 파라미터 패싱 방식은 각 각 어느 방식에 속하는지 구분하세요.

eager evaluation은 파라미터 전달 시 즉각적으로 평가가 되며, 파라미터를 호출하지 않아도 평가가 된다. 반면에 lazy evaluation은 피호출자가 파라미터를 사용하지 않으면 평가가 되지 않으며 사용할 때만 평가가 된다.
call-by-value가 eager evaluation에 해당하며, call-by-name은 lazy evaluation에 해당된다. 보통 JAVA, Python 등에서 call-by-value 방식을 사용하며, Rust와 같은 함수형 프로그래밍 언어에서 call-by-name을 사용한다. 각각의 파라미터 예시를 들면, eager evaluation의 경우 문자열, 숫자 등을 예시로 들 수 있으며, lazy evaluation의 경우 무한 값(무한 배열)을 예시로 들 수 있다.
Rust와 Java는 C/C++를 대체하여 시스템 프로그래밍을 쉽게 하기 위해 대두된 대표적인 언어들이다. 메모리 관리 측면에서 기존 C/C++의 한계를 제시하고, 두 언어가 그 한계를 각각 어떻게 극복했는지 설명하고, 어떤 장단점이 있는지 설명하시오.

C/C++의 경우, 사용자가 프로그램을 작성할 때 malloc과 free같은 함수를 통해서 할당 및 반환 과정을 명시적으로 작성해야 한다. 이를 지키지 않을 경우, 메모리 누수 문제가 발생할 수 있다. 따라서 메모리 유지보수 및 관리가 힘들다는 한계가 존재한다. 반면에 자바의 경우 Garbage Collection 시스템을 도입하여 사용되지 않는 객체에 대해서 자동으로 메모리를 반환하도록 디자인되었다. 이를 통해 C/C++이 갖는 메모리 관리 측면의 한계를 극복하였다. 각각의 장단점은 다음과 같다.
1. C/C++: 메모리 유지보수 및 관리가 힘들다는 단점이 존재하지만, 메모리를 직접 관리할 수 있어 프로그램 최적화 관련 이점이 존재한다.
2. Java: 메모리 유지보수 및 관리가 편하다는 장점이 존재하지만, Garbage Collection의 overhead 발생 시 프로그램 효율이 떨어진다는 단점이 존재한다.
RAII(Resource acquisition is initialization)가 무엇이고, 어느 상황에서 사용하면 좋을지 설명하시오.

객체 생성과 동시에 리소스가 할당되고 소멸과 동시에 리소스가 반환되는 것을 의미한다. C/C++의 std:unique_ptr를 통해 예시를 설명할 수 있다.
```
#include <iostream>
#include <memory>

class Resource() {
	public:
    	Resource(){ std::cout << "생성\n"; }
        ~Resource(){ std::cout << "소멸\n"; }
};

void useResouce() {
	std::unique_ptr<Resource> ptr = std:make_unique<Resource>();
    std:cout << "메모리 사용 중\n";
}

int main() {
	useResource();
    std::cout << "종료";
    return 0;
}
```
위 코드를 실행할 경우,
생성
메모리 사용 중
소멸
종료
이렇게 출력이 될 것이다. 이유는 useResource 함수를 통해서 객체가 생성이 되었으며, 해당 함수가 종료하게 되면 객체가 소멸되기에 이때 리소스가 반환될 것이기 때문이다. 이와 같은 특징을 활용하여 데이터베이스 등에 활용할 수 있다. 예를 들어 디비에 연결하면서 리소스를 할당받고 디비 작업이 끝나면 연결이 끊기며 자동으로 반환되도록 말이다.

가비지 컬렉션을 위해 Mark and Sweep 기법이 크게 어떻게 이루어지는지 간단히 설명하고, 이 기법의 장단점을 설명하시오.

가비지 컬렉션은 루트에서부터 도달 가능한 객체를 탐색한다. 그리고 각 객체를 돌면서 현재 사용 중인 객체인지 확인하다. 만약 사용되는 객체라면 마킹을 해놓는다. 이 과정이 Mark에 해당한다. 그리고 마킹이 되어 있지 않은 객체에 대해서 삭제하여 메모리를 반환한다. 이 과정이 Sweep에 해당한다. 그리고 마킹된 객체는 유지하고 메모리 공간을 정리한다. 이 과정을 통해서 효율적인 메모리 관리가 가능하다는 장점이 있다. 반면에, 메모리 반환 후 메모리 공간에 할당된 객체들이 지역적으로 존재하지 않아 메모리 성능이 떨어진다는 단점이 존재한다. 따라서 이를 위해 메모리 Compacting 작업 등이 필요하다.
Type system이 sound하다는 것, 그리고 complete하다는 것의 의미를 각각 설명하시오.

타입 추론을 통해 프로그램의 타입이 안전하다는 것을 보장하는 경우를 타입 시스템이 사운드하다고 한다. 예를 들어 다음과 같은 java 코드가 있다고 가정해본다.
```
int func(int x, int y) {
	return x + y;
}

func("10", "5");
```
이 경우 func의 호출자가 넘겨주는 파라미터와 func의 파라미터 타입이 일치하지 않는다는 문제가 있다. 따라서 이를 런타임 전에 확인하여 즉, 컴파일을 통해서 타입 추론을 하여 오류를 발견함으로써 타입 시스템이 타입 오류를 발생시킨다.
그리고 타입 시스템이 컴플릿하다는 것은 모든 표현식에 대해 적합한 타입을 부여한다는 것을 의미한다. 예를 들어 다음과 같은 java 코드가 있다고 가정하자.
```
int x = 10;
x = "hello";
```
이 경우 정수형에 문자형 타입을 부여하는 부적합한 타입 부여를 확인할 수 있다. 따라서 타입 시스템이 정수형 타입에 문자형 타입을 부여할 수 없다는 것을 알고 타입 오류를 발생시킨다.
프로그램 실행 전 컴파일 시에 타입을 정적으로 검사하는 프로그래밍 언어가 그렇지 않은 프로그래밍 언어에 비해 갖는 장점을 설명하시오. 또한, 그럼에도 불구하고 그렇지 않은 언어가 사용되는 이유를 설명하시오.

대표적으로 전자에 해당하는 언어로 C/C++을, 후자에 해당하는 언어로 Python을 꼽을 수 있다. 전자의 경우, 컴파일을 통해 타입 에러를 조기에 발견할 수 있다는 장점이 있다. 즉, 런타임 전에 에러를 발견할 수 있다는 장점이 있다. 또한, 최적화 측면에서도 이점을 보여준다. 정적으로 타입을 정하기 때문에 런타임 중에 타입 검사를 위한 연산이 필요가 없다. 하지만 이러한 장점에도 불구하고 동적 타입 검사 프로그래밍 언어가 사용되는 가장 큰 이유로, 코드 작성의 편리함을 꼽을 수 있다. 타입을 명시적으로 작성하지 않아도 되며, 이러한 유연성덕분에 코드를 편리하게 작성할 수 있다. 또한 타입 변환이 자유로워, 다양한 데이터 구조를 쉽게 다룰 수 있다는 장점도 존재한다.
Static typing과 dynamic typing의 차이점은? C++/JAVA은 어떤 typing을 사용하는가?

정적 타이핑은 타입을 명시적으로 지정해야 하며, 변수의 타입이 컴파일 시에 결정된다. 엄격한 문법으로 인해 코드의 에러 가능성이 낮으며, 실행 속도가 동적 타이핑보다 빠르다는 장점이 존재한다. 반면 동적 타이핑은 타입을 명시적으로 지정하지 않아도 되며, 변수의 타입이 런타임에 결정된다. 타입이 명시되지 않아 에러를 발생시킬 가능성이 높지만, 여러 데이터 타입을 유연하게 사용 가능하다는 장점이 존재한다. C++/JAVA 모두 Static typing을 사용한다.
Option type이 무엇이고, 어느 상황에서 사용하면 좋을지 설명하시오.

값이 있을 수도 있고 없을 수도 있는 타입을 의미한다. 보통 null 값에 대한 예외처리를 할 때 유용하게 사용된다.
중간 표현(Intermediate Representation, IR)은 컴파일러 설계에서 매우 중요한 요소이다. IR이 사용되는 이유를 간단히 설명하라.

IR은 "소스 코드 -> 기계어" 과정의 중간 과정에서 사용된다. 컴파일러는 소스코드를 기계어로 직접 변환하지 않고, 먼저 IR을 통해서 최적화 및 코드 생성 과정을 수행한다. 또한 여러 프로그래밍 언어에 대해서도 동일 IR로 변환하는 과정을 거치면, 여러 기계어를 변환하는 과정이 단순해진다는 장점이 존재한다. 결론적으로 최적화 측면 및 이식성 측면의 장점이 존재한다.
아래 두 Javascript 코드(code1.js 및 code2.js)의 실행 결과가 다른 원인을 설명하고, 그 원인 각각의 장단점을 설명하시오.
```
// code1.js
let l1 = [1, 2];
let l2 = [100, 200];

let s = 0;
for (var x of l1) {
    for (var x of l2) {
    }
    s += x;
}
console.log(s)
// Result: 400

// code2.js
let l1 = [1, 2];
let l2 = [100, 200];

let s = 0;
for (let x of l1) {
    for (let x of l2) {
    }
    s += x;
}
console.log(s)
// Result: 3
```
두 코드의 for 문의 x의 타입을 지정하는 부분에서 실행 결과가 달라진다.
code1.js의 경우 x를 var로 지정하는데 보통 var는 함수 혹은 전역 범위라는 의미를 지닌다. 즉, 첫 번째 반복문에서 x의 값은 1, 두 번째 반복문에서 1->100->200이 된다. s+=x; 부분에서의 x 값은 200이 된다. 그리고 다음 반복에서 x의 값은 2, 내부 반복문에서 2->100->200이 되며, s+=x;에서의 x 값은 200이 된다.
code2.js의 경우 x를 let 타입으로 지정하고, let은 블록 범위라는 의미를 지닌다. 즉, 첫 번째 반복문과 두 번째 반복문의 x는 공유되지 않는다. 따라서 두 번째 반복문과 상관없이 s += x;에서의 x 값은 순서대로 1, 2가 되어 총 합인 3이 결과로 나오게 된다.
var의 경우 코드가 짧고 전역 접근이 가능하지만, 중첩 반복문에서 변수가 덮여질 수 있다는 단점이 존재한다. let의 경우 코드가 길어진다는 단점이 있지만, 중첩 반복문에서 변수의 독립성을 유지할 수 있다는 장점이 있다.
간단한 표현식 1 + 2 * 3 을 중심으로, Operational semantics와 Denotational semantics의 차이를 설명하시오.

오퍼레이셔널 시멘틱스는 연산자 우선순위에 따라 연산이 진행된다. 즉, 2*3이 계산되고, 1+6이 진행되어 7이라는 값이 나온다. 반면, 디노테이셔널 시멘틱스는 수학적 함수에 따라 연산이 진행된다. 즉 add(1, mul(2, 3))과 같은 방식으로 진행된다. 즉 add(1, mul(2,3)) --> add(1, 6) --> 7이 된다.
아래의 코드에서 sum 변수에 배열 array의 모든 요소를 더하는 작업을 수행한다. 컴파일러가 이 루프를 최적화할 수 있는 방법을 제안하고, 이 방법이 성능 향상에 어떻게 기여하는지 설명하라.
```
int sum = 0;
for (int i = 0; i < 1000; i++) {
    sum += array[i];
}
```
루프 언롤링(loop unrolling)을 통해서 루프를 최적화할 수 있다. 즉 위 코드의 경우 i가 1씩 증가하여 배열에서 하나의 요소씩만 접근하지만, for(int i = 0; i < 1000; i += 4) { sum += array[i] + array[i+1] + array[i+2] + array[i+3]과 같이 루프 언롤링 과정을 통해서 총 1000번의 연산을 250번의 연산으로 줄일 수 있다. 이를 통해 좀더 빠른 속도로 연산이 가능하다.
다음은 프로시저 read(a, b)의 의사코드이다.
```
c := 3.0 * a + b;
if c = 0 { a := 1; } else { a := 1.0/c + 1.0/b; }
```
이 프로그램은 특정 조건을 만족하는 a값과 b값이 들어오면 오류를 일으킨다. 다음 중 프로그램의 오류를 막을 수 있는 가장 약한 조건은?
1) b > 0
2) a>0 and b>0
3) a ≠ -b/3
4) b ≠ 0
5) 3.0*a ≠ 0 and b ≠ 0

c가 0인 경우에는 a := 1로 큰 문제가 없어 보인다. 하지만 c가 0이 아닌 경우에는 1.0/b 연산이 존재하며, 이때 b가 0일 경우 division by zero 에러가 발생할 가능성이 있다. 따라서 b != 0의 조건이 필요하다.
그리고 각 조건별로 분석해보면,

1번, 2번: b가 0보다 크므로 1.0/b의 에러 가능성이 낮아 강한 조건.
3번: b가 0이 아닌 경우를 보장하지 못하므로 불충분한 조건.
4번: b가 0이 아니므로 1.0/b의 에러를 막을 수 있지만 가장 약한 조건.
5번: b가 0이 아니므로 1.0/b의 에러를 막을 수 있지만 3.0*a는 불필요한 조건으로, 불필요하게 강한 조건.
으로 4번이 오류를 막을 수 있는 가장 약한 조건에 해당한다.

이재호

천천히, 그리고 꾸준히.

다음 포스트

[CS] 1. Programming Language, Compiler

cs

[CS] 2. Architecture

0개의 댓글