AlriC's CS Diary AlriC's CS Diary

카테고리

• [프언] #14. Let-Polymorphic Type System

  2023-2학기/프로그래밍언어 2023. 12. 10. 15:24

  Limitation of Our Type System 지금까지 구현한 저희의 Type System은 Polymorphism을 지원하지 않습니다. Polymorphism이란, 프로그램의 특정 부분이 서로 다른 부분에서 다른 Type으로 사용되는 일종의 메커니즘입니다. let f = proc (x) x in if (f (iszero (0))) then (f 11) else (f 22) 위 코드에서 f는 어떤 값을 받아 그 값을 그대로 리턴하는 프로시져입니다. 두 번째 줄에서, ITE (If Then Else)의 조건부에 f (iszero (0))이 들어갔는데 이때 f는 Bool을 입력받아 Bool을 출력하는 프로시져입니다. 그러나 다음에 f는 Int를 받아 Int를 출력하는 프로시져로 사용되었죠. 이런 것이..

  Read More
• [프언] #13. Automatic Type Inference

  2023-2학기/프로그래밍언어 2023. 12. 10. 02:29

  지난 글에서 Type Checker를 구현하는 과정에서, Proc Expression을 단순 Recursion으로 구현할 수 없는 문제가 있었습니다. 그 문제를 해결하기 위해 프로시져를 정의할 때, 프로시져에 들어가는 인수의 Type을 미리 지정하는 방식인 Type Annotation을 사용했었고요. 이번 글에서는 다른 방식인 Type Inference를 이용해 이 문제를 해결해보도록 하겠습니다. Automatic? Type Annotation은 프로그래머가 필요한 Type을 직접 지정하도록 하는 방식이었다면, Type Inference는 알려지지 않은 Type을 프로그램이 자동으로 추리해 내는 방식입니다. Examples of Type Inference if x then x-1 else 0 위와 같은 ..

  Read More
• [프언] #12. Manual Type Annotation

  2023-2학기/프로그래밍언어 2023. 12. 5. 01:37

  지난 글에서 다루었던 Type Checker를 Scala에서 구현한다고 생각해봅시다. def typeOf(env: Env, expr: Expr): Tpe = { expr match { case _: IntVal => IntType case v: Var => env.get(v) match {...} 이런 식으로 작성을 시작하겠죠. expr가 Add일 경우는 Recursion을 사용해서 구현할 수 있습니다. case Add(l, r) => (typeOf(l), typeOf(r)) match { case (IntType, IntType) => IntType case _ => throw new TypeError(...) } 이렇게요. 그런데 문제가 있습니다. 바로 Proc Expression의 경우 단순 Rec..

  Read More
• [프언] #11. Type System

  2023-2학기/프로그래밍언어 2023. 12. 4. 20:57

  Safe / Unsafe 소스 코드를 받아 그 코드를 실행하는 프로그램, 혹은 환경을 Interpreter, 인터프리터라고 부릅니다. 지금까지 저희가 개발한 프로그래밍 언어는 소스 코드를 인터프리터에 넣었을 때 정상적으로 실행될지, 실행에 실패할지 판단할 수 있는 능력이 없습니다. 인터프리터가 실행할 수 없는 소스 코드를 Unsafe Program이라고 합니다. 예를 들어, 아래와 같은 프로그램들은 전부 Unsafe Program입니다. if 3 then 88 else 99 위 프로그램은 3이 Boolean이 아니기 때문에 실행될 수 없습니다. Let x = iszero 0 in (3 - x) 위 프로그램은 - 기호가 Boolean에 대해 정의되어 있지 않기 때문에 실행될 수 없습니다. 어떤 프로그램이 ..

  Read More
• [계산이론] #13. NP-Complete

  2023-2학기/계산이론 2023. 11. 29. 18:50

  NP-Complete란? 지난 글에서 $\textbf{P}$는 $\textbf{NP}$에서 가장 쉬운 언어들의 집합임을 보았습니다. 이번에는 반대로 $\textbf{NP}$에서 가장 어려운 언어들의 집합인 $\textbf{NP-complete}$에 대해 알아보겠습니다. 만약 $\textbf{P}=\textbf{NP}$일 경우, $\textbf{P}$와 $\textbf{NP}$, $\textbf{NP-complete}$는 전부 동치입니다. 만약 $\textbf{P}\neq \textbf{NP}$일 경우, $\textbf{P}$와 $\textbf{NP-complete}$는 서로 Disjoint (공통된 원소가 없음) 입니다. 그림으로 정리하면 이런 느낌이겠죠. 어떤 Language $B$가 아래 조건을 만족..

  Read More
• [계산이론] #12. Knapsack, Clique, 3SAT Problem

  2023-2학기/계산이론 2023. 11. 29. 04:03

  Running Time의 비교 $\textbf{P}$에 속하는 Language들은 전부 Polynomial Time에 해결 가능하기 때문에, 어떻게 보면 이들을 해결하기 "쉽다"고 말할 수 있습니다. 이렇게 어떤 Language가 얼마나 쉬운지는 이 Language의 Running Time에 의해 결정됩니다. 더 나아가서, 어떤 두 Language의 Running Time을 비교해서 어떤 Language가 더 쉬운지, 어려운지를 결정할 수 있습니다. 언어 $A$가 언어 $B$보다 쉬울 경우, 이를 $A\leq_{P}B$ 라고 표현합니다. 아랫첨자 $P$는 Running Time에서 Polynomial 한 변수는 무시하겠다는 의미로 붙인 것입니다. 이를 수학적으로 표현하자면, 두 언어 $A, B\subse..

  Read More
• [계산이론] #11. P-NP (2)

  2023-2학기/계산이론 2023. 11. 28. 01:05

  이전 글에서 어떤 문제가 $\textbf{P}$이고 어떤 문제가 $\textbf{NP}$인지 알아보았습니다. 이번 글에서는 이 두 집합 간의 관계에 대해 중점적으로 살펴보도록 하겠습니다. P는 NP의 부분집합이다. 직관적으로 알 수 있듯, $\textbf{P}$는 $\textbf{NP}$의 부분집합입니다. 어떤 문제가 $\textbf{P}$라는 것은 그 문제의 정답을 Polynomial Time에 계산할 수 있다는 것인데, 이러면 당연히 어떤 정답이 진짜 정답인지 확인하는 것도 Polynomial Time에 가능하기 때문에 $\textbf{NP}$에 속하기 때문이죠. EXP 지난 글에서 보았듯 $NPrime$ (2 이상의 정수 중 소수가 아닌 수를 이진법으로 나타낸 문자열의 집합)은 2002년에 $\te..

  Read More
• [프언] #10. Concrete/Abstract Syntax

  2023-2학기/프로그래밍언어 2023. 11. 20. 16:10

  Concrete Syntax 모든 문자열의 집합 $S$를 생각해보겠습니다. "1123aaaaa5"도 $S$의 원소일 것이고, "let x = 10 in x + 2"도 $S$의 원소일 것이고, 제가 쓰고 있는 이 글도 $S$의 원소일 것입니다. 어떤 프로그래밍 언어의 Syntax를 정의할 때 보통 $S$의 부분집합 $P$를 정의하는 방식을 사용합니다. 어떤 문자열이 $P$의 원소이면 프로그램인 것이고, $P$의 원소가 아니라면 프로그램이 아닌 것이죠. Syntax의 정의에서 짐작할 수 있듯, 어떤 문자열이 $P$의 원소라는 것을 확인함으로서 이 문자열이 프로그램이라는 사실을 입증해줄 수는 있지만 이 프로그램이 어떤 동작을 하는지는 알 수 없습니다. 이를 Concrete Syntax라 합니다. Abstrac..

  Read More