AlriC's CS Diary AlriC's CS Diary

카테고리

• [프언] #19. Continuations

  2023-2학기/프로그래밍언어 2023. 12. 13. 22:05

  Redex와 Continuation (1 + 2) + (3 + 4) 위 Expression을 계산한다고 가정합시다. 그럼 아래와 같은 순서로 계산이 진행됩니다. Expression 1을 계산해 1을 얻습니다. Expression 2를 계산해 2를 얻습니다. 1과 2를 더해 3을 얻습니다. Expression 3을 계산해 3을 얻습니다. Expression 4를 계산해 4를 얻습니다. 3과 4를 더해 7을 얻습니다. 3과 7을 더해 10을 얻습니다. 이 과정 중 어떤 과정을 기준으로 저희는 과정 전체를 두 부분으로 쪼갤 수 있습니다. 이렇게 어떤 과정을 기준으로 그전에 시행된 작업을 Redex, 그 이후에 시행될 작업을 Continuation이라고 합니다. 계산 과정을 기술할 때, 저희는 Continuat..

  Read More
• [프언] #18. Algebraic Data Type

  2023-2학기/프로그래밍언어 2023. 12. 13. 19:16

  지금까지 저희는 Type을 약식으로 정의해 왔었는데요, 지금부터는 Type을 변수들과 Expression의 계산값이 들어가 있는 집합의 이름으로서 다루겠습니다. List를 정의할 때, 보통 빈 리스트와 원소가 하나인 리스트, 그리고 이것들의 합. 이렇게 정의하는게 일반적입니다. 비슷하게 이진트리를 정의할 때도 빈 트리와 Root, 2개의 Child로 구성된 단순한 트리, 그리고 이것들의 합. 이렇게 정의합니다. 이런 식으로 정의되는 Type, 혹은 Set을 Sum Type이라고 합니다. 반면, 프로시져를 정의할 때 저희는 변수 x, expression b, environment e에 대해 (x, b, e)와 같은 식으로 정의를 합니다. 이렇게 정의되는 Type 혹은 Set을 Product Type이라고 ..

  Read More
• [프언] #17. Lambda Calculus

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

  프로그래밍 언어를 디자인할 때, 모든 Expression이 꼭 필요한 것은 아닙니다. 무슨 뜻이냐? 위 Expression은 필수적으로 존재할 필요가 없습니다. 왜냐? 아래 Expression으로 대체 가능하거든요. 이렇게 다른 문법으로 대체 가능한 Syntax를 Syntactic Sugar라고 합니다. 그리고 이 Sugar를 전부 없애 만들어낸 무가당 프로그래밍 언어를 Lambda Calculus라고 합니다. Lambda Calculus Lambda Calculus에는 단 3개의 Expression이 존재합니다. Variable, Abstraction, Application이 그것입니다. Variable의 경우는 딱히 설명할 게 없겠죠. Abstraction과 Application은 프로시져의 정의와 ..

  Read More
• [프언] #16. Procedure Overloading and Parametric Polymorphism

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

  Type Annotation을 사용할 때, 일반적인 방법으로는 Polymorphic Procedure를 사용할 수 없습니다. 변수의 Type이 고정되어 있기 때문이죠. Polymerphic Procedure를 사용하기 위해서, 함수가 실제로 호출될 때 Type을 정해주는 방식을 사용합니다. 이를 Type Abstraction이라고 합니다. let f = proc[A](x: A) (x 1) in ... 예시를 통해 좀 더 설명해 보겠습니다. let f = typeAbst[A] ( proc(a: A) a } in ( if (f[bool](true)) f[int](11) else f[int](12) ) 이 코드에서 f는 어떤 값을 받아 그 값을 그대로 출력하는 프로시져입니다. 이 프로시져의 타입은 이 프로시져..

  Read More
• [프언] #15. Subtype Polymorphism

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

  이번 글에서는 Type System을 Record에도 적용되도록 확장해 보겠습니다. 편의성을 위해, 프로시져에 대해서는 Type Annotation을 사용하도록 하겠습니다. 이 2개의 Expression에 대한 Typing Rule을 적용하는 것 자체는 정말 간단합니다. Limitation 하지만 역시 이도 한계점이 존재합니다. 먼저 이렇게 만들어진 Type System은 Sound입니다. let f = proc x: {z: int} x.z in (f {z = 10, y = 9}) 위 코드에서 프로시져 f는 Record를 하나 받아 그 Record의 z값을 리턴합니다. 따라서 위 코드는 10으로 계산되지만, Type System은 프로시져 f의 입력값을 {z: int} 형태의 Record로 특정하기 때문..

  Read More
• [계산이론] #16. Chomsky Normal Form

  2023-2학기/계산이론 2023. 12. 11. 21:58

  Chomsky Normal Form이란? 어떤 Context-Free Grammar의 $R$이 아래 조건을 만족하는 Rule로만 구성되어 있을 경우, Chomsky Normal Form이라고 합니다. $A\to BC$, where $A, B, C\in V$, $B \neq S$, $C \neq S$ $A \to a$, where $A \in V$ and $a \in \Sigma$ $S \to \epsilon$ Chomsky Normal Form으로의 변형 어떤 임의의 Context-Free Language가 있을 때, 이 Language에 대한 Chomsky Normal Form인 Context-Free Grammar가 항상 존재합니다. 다시 말해, 임의의 Context-Free Grammar는 Chom..

  Read More
• [계산이론] #15. Context-Free Language

  2023-2학기/계산이론 2023. 12. 11. 21:22

  이전까지의 글에서 저희는 Complexity Theory에 대해 알아보았습니다. 이번 글에서는 다시 Regular Language로 살짝 돌아와 보도록 하겠습니다. Context-Free Language 이번 글에서 저희는 Context-Free Language에 대해 알아볼 것입니다. Context-Free Language는 $\textbf{P}$의 부분집합이며, Regular Language의 상위 집합입니다. 즉, 아래가 성립합니다. $$Regular\; Language \subseteq Context-Free\; Language \subseteq \textbf{P}$$ 지난번에 다루었던 가장 대표적인 Nonregular Languge로는 $\left\{0^n1^n:n\geq 0 \right\}$ ..

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

  2023-2학기/계산이론 2023. 12. 11. 19:14

  지난 글에서 NP-Complete가 무엇인지, 그리고 어떤 언어가 NP-Complete임을 어떻게 증명할 수 있는지에 대해 알아보았었습니다. 이 글에서는 NP-Complete에 속하는 언어의 예시에 대해 좀 더 알아보겠습니다. SAT Problem 지난 글에서 간단하게 다루었던 문제이지만 다시 설명하고 넘어가겠습니다. 이 문제에는 $m$개의 Boolean, $x_1,x_2, \cdots, x_m$이 존재합니다. 이들은 0 혹은 1의 값을 가지며 0은 False를, 1은 True를 의미합니다. 그리고 $x_j$의 Negation은 $\neg x_j=1-x_j$로 정의됩니다. 이 둘을 합쳐서 Literal, $l$ 이라고 부릅니다. 그리고 몇 개의 Literal을 논리합 (OR) 연산한 것을 Clause라고..

  Read More