전체 글
-
[프언] #09. Records & Pointers2023-2학기/프로그래밍언어 2023. 11. 20. 15:27
이번 글에서는 C에서의 Struct와 Pointer와 유사한 기능을 한번 추가해보겠습니다. Record Record는 어떤 데이터가 특정한 형태를 가질 때, 이를 묶어서 편리하게 처리할 수 있도록 만들어진 데이터 형식 중 하나입니다. C의 구조체, 오브젝트 등이 바로 Record입니다. 먼저 저희가 제작하고 있는 언어에서 Record를 어떻게 정의하고 호출해야 할 지를 정해야 합니다. 이 언어에서 변수를 정의할 때는 let을 사용했었습니다. let x = 10 in x + 2 이와 비슷하게 아래와 같이 Record를 정의하고 호출하는 방법을 생각할 수 있겠네요. let student = {id := 20231111, age := 20} in student.id + student.age Syntax를 조금..
-
[계산이론] #10. P-NP (1)2023-2학기/계산이론 2023. 11. 13. 06:42
지금까지 저희는 무슨 문제가 계산 가능한지에 대해 중점적으로 알아보았습니다. 지금부터는, 이런 문제들이 얼마나 빠른 시간 내에 계산 가능한지에 대해 알아보도록 하겠습니다. 이런 문제를 우리는 Complexity Theory라고 합니다. Running Time Turing Machine $M$에 Input $w$를 집어넣었을 때, 실행되는 Computation Step의 개수를 Running Time이라고 하며 $t_M\left ( w \right )$라고 표시합니다. 여기서 $\mathbb{N}_0$에서 $\mathbb{N}_0$로의 함수 $T$를 아래와 같이 정의합니다. $$t_M\left ( w \right )\leq T\left ( \left|w \right| \right )$$ 이 함수는 특정 길..
-
[계산이론] #09. Non-Enumerability2023-2학기/계산이론 2023. 11. 13. 02:01
Enumerable한 언어의 집합은 Countable인가? 지난 글에서 Enumerable한 언어에 대해 알아보았습니다. Binary Language (0과 1로만 이루어진 언어) 중 Enumerable한 모든 언어의 집합 $ \varepsilon $을 정의하겠습니다. 그러면 이 집합 $ \varepsilon $은 Countable입니다. (Countable이 무엇인지에 대해서는 이 글을 참고하세요.) 어떤 언어 $A$가 Enumerable이라면, $A$의 원소인 문자열이 들어오면 Accept하고 $A$의 원소가 아닌 문자열이 들어오면 Reject하거나 Terminate하지 않는 TM $T_A$가 존재한다는 성질이 있었죠. 이 성질을 사용해 위의 $ \varepsilon $이 Countable임을 증명해..
-
[프언] #08. States2023-2학기/프로그래밍언어 2023. 10. 19. 07:58
이번 글에서는 저희 언어에 State를 한번 추가해 볼 겁니다. let f = proc x x in f (f 1) 이런 프로그램을 실행할 때, 저희는 f가 2번 호출된다는 사실을 알 수 있습니다. 하지만 프로그램은 f가 몇 번 호출되는지 알 길이 없습니다. 왜냐하면 Procedure는 Caller에게 결괏값만을 제공할 뿐, 그 외의 행동은 하지 않기 때문입니다. let count = 0 in let f = proc x (let count = count + 1 in x) in let a = f (f 1) in count 따라서 이런 식으로 변수를 따로 만들어서 f가 호출된 횟수를 세는 것은 가능하지 않습니다. 이번 글에서는 이것이 가능하도록, Procedure가 Procedure 외부에 있는 값들을 수정할..
-
[컴구] #04. MIPS에서의 사칙 연산2023-2학기/컴퓨터구조 2023. 10. 18. 22:33
이번 글에서는 컴퓨터 내부에서 사칙 연산이 실제로 어떻게 계산되는지에 대해 좀 더 자세히 알아보도록 하겠습니다. 덧셈과 뺄셈 덧셈, 뺄셈은 컴퓨터와 사람의 계산 방법이 크게 다르지 않습니다. 손으로 계산할 때처럼 가장 오른쪽에 있는 수부터 더하고, 올림이 발생하면 올려주고, 왼쪽으로 계산을 이어나갑니다. 저희가 주목해야 할 부분은 바로 Overflow(오버플로우)입니다. 계산의 결과가 사용 가능한 하드웨어 (이 경우에서는 32비트겠죠)로 표현할 수 없는 경우입니다. 부호가 있는 수의 경우에는 오버플로우가 일어났음을 쉽게 감지할 수 있습니다. 두 양수를 더했는데 그 결과가 음수가 되었다던가, 두 음수를 더했는데 결과가 양수가 되었다던가.. 이런 경우는 부호 비트로 올림이 진행된 것이므로 오버플로우가 일어났..
-
[컴구] #03. Procedure2023-2학기/컴퓨터구조 2023. 10. 18. 20:05
Procedure 프로시저는 특정 작업을 수행하는 프로그램의 묶음을 말합니다. 프로그램을 짜다 보면 특정 작업을 반복해서 수행해야 할 때가 있잖아요? 작업 A를 100번 해야 한다고 할 때 A를 해야 할 때마다 A의 코드를 작성하지 말고, A라는 작업을 하는 프로시저를 하나 만들고 A를 해야 할 때마다 프로시저를 그냥 호출해주기만 하면 됩니다. 프로그램은 프로시져가 필요할 때 프로지서에 값을 보내고 계산된 값을 받아오는데요, 이 일을 하는 것을 Parameter(인수)라 부릅니다. 프로그램이 프로시저를 실행할 때 아래와 같은 단계를 거칩니다. 프로시저가 접근할 수 있는 곳에 인수를 넣어둔다. 프로시저로 제어를 넘긴다. 프로시저가 필요로 하는 메모리를 프로시저에게 제공한다. 필요한 작업을 수행한다. 프로시..
-
[프언] #07. Lexical Scoping of Variables2023-2학기/프로그래밍언어 2023. 10. 17. 00:14
Static Scope 이전 글에서 Static Scoping을 사용해 정의된 Procedure에서 Environment는 Procedure가 정의된 시점의 Environment를 따른다고 했었습니다. 이렇게 Static Scoping을 사용하면, 어떤 변수에 대한 Scope는 Static 한 성질을 가집니다. 갑자기 모르는 말이 나와서 당황하셨을 분들을 위해 설명드리겠습니다. 어떤 변수의 Scope라는 것은, 이 변수를 사용할 수 있는 범위라는 뜻을 가집니다. 모든 변수는 자기 자신만의 Scope를 가집니다. 프로그램 전체에서 사용 가능한 변수도 있고, 특정 Expression 내부에서만 사용할 수 있는 변수도 있는 법이니깐요. 어떤 성질이 Static 하다는 것은, 그 성질은 프로그램을 굳이 돌려보지..
-
[프언] #06. Procedures2023-2학기/프로그래밍언어 2023. 10. 16. 22:20
저번 글에서 프로그래밍 언어를 하나 설계하는 것을 시작했고 Value, Environment, Expression 등을 정의해보았습니다. 이번 글에서는 이를 더 확장해서 Procedure라는 것을 한번 정의해보겠습니다. Procedure Procedure란, 다른 프로그래밍 언어에서 함수의 역할을 하는 Value입니다. let f = proc (x) (x - 11) Procedure를 정의하기 위해서 "proc"이라는 단어를 사용하며 첫번째 괄호에는 이 함수의 입력값을, 두번째 괄호에는 출력값을 적어줍니다. 위의 예시에서 $f$라는 Procedure는 x를 받아 x-11을 출력하는 함수와 같이 작동합니다. let f = proc (x) (x - 11) in (f 77) 이 Procedure를 Call하기..