2023-2학기/프로그래밍언어
-
[프언] #19. Continuations2023-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..
-
[프언] #18. Algebraic Data Type2023-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이라고 ..
-
[프언] #17. Lambda Calculus2023-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은 프로시져의 정의와 ..
-
[프언] #16. Procedure Overloading and Parametric Polymorphism2023-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는 어떤 값을 받아 그 값을 그대로 출력하는 프로시져입니다. 이 프로시져의 타입은 이 프로시져..
-
[프언] #15. Subtype Polymorphism2023-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로 특정하기 때문..
-
[프언] #14. Let-Polymorphic Type System2023-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를 출력하는 프로시져로 사용되었죠. 이런 것이..
-
[프언] #13. Automatic Type Inference2023-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 위와 같은 ..
-
[프언] #12. Manual Type Annotation2023-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..