Introduction to Programming Languages - Chapter 05 ~ 06
date
Mar 29, 2024
slug
itpl-02
status
Published
tags
PL & Compiler
summary
동아리에서 진행하고 있는 PL 스터디입니다.
type
Post
Chapter 05
패턴 매칭 (Pattern Matching)
패턴 매칭 기능은 함수형 프로그래밍의 주요 기능 중 하나이다.
프로그래밍 언어에서는 모든 것에 타입이 존재하는데, 아래 사진과 같이 타입에 따라 다양한 형태를 포함하고 있다.
숫자의 경우 0 또는 natural한 숫자, 리스트의 경우 빈 리스트 혹은 한 쌍의 element,
산술식의 경우 숫자 자체(ex:
+2, -2), 두 숫자의 합(ex: 2 + 2) 등
또한 사용자 정의 타입을 만들 수도 있는데, Scala에서는
trait을 사용하여 만들 수 있다.
→ Java를 사용해봤다면 인터페이스를 생각하면 된다.Num, Add, Sub 클래스는 모두 AE 트레잇을 상속하기 때문에 위에서 선언한 4개의 변수처럼 AE 타입으로 설정이 가능하다.아까 설명했듯이
AE 라는 타입을 매개변수에서 받은 후 Num, Add , Sub 중에서 어떤 패턴에 매칭되는지 case문을 사용할 수 있다. → C, C++에서는 상상도 할 수 없는 일이다.패턴 매칭을 사용하지 않을 경우
isInstanceOf 를 사용하여 타입이 Num 인지, Add 인지 아니면 Sub 라고 판단한 후 동작을 수행한다. - 패턴 매칭을 사용하는 코드에 비해 매우 복잡한 것을 확인할 수 있다.만약 인스턴스의 타입이
Add 인지 체크 후 Sub 의 인스턴스를 사용하는 위의 코드처럼 개발자의 실수가 발생할 수 있는데, 패턴 매칭은 간결하고 실수의 가능성을 제거한다.그러나 위와 같이 eval 함수에서
Num 타입을 처리하지 않는데 매개변수로 들어오게 된다면 MatchError 가 뜨는데 이는 당연한 결과이다.Scala에서 위 함수를 정의해봤다면 알겠지만 컴파일러에서 패턴이 완전한지 여부를 확인한 후 그렇지 않다면 경고 문구를 출력한다.
결론: 인스턴스의 타입을 하나씩 비교하지 말고, match 문을 사용하여 간결하게 타입에 따라 적절한 동작을 정의하자. → 개발자의 실수를 컴파일러에게 질의해서 해결하자.
같은 패턴을 2번 정의했을 때도 컴파일러가 위와 같은 경고 문구를 출력한다.
만약 인스턴스의 타입을 비교하는 코드를 작성해서 같은 타입을 2번 정의해도 이는 컴파일러가 관리해주지 않는다. - 개발자가 직접 만든 조건이기 때문에 관리할 이유도 없다.
각 타입에 따라 예외 처리 혹은 잡다한 처리를 개발자가 해야 한다면 실수 혹은 버그 발생 가능성이 높아지게 되는 것이다.
그 외에 지원하는 다양한 패턴들
왼쪽이 Java, 오른쪽이 Scala로 만든 코드이며 두 코드는 같은 기능을 수행한다
또한 중첩된 패턴의 case도 작성할 수 있다.
위 코드의 2번째, 3번째 케이스를 보면
Add 안에서 Num 을 호출하고 있다.
해당 케이스를 추가하지 않았다면, Add(0, 3) 에서 덧셈 연산을 수행해야 하지만 0 + 3 은 단순히 오른쪽 값을 반환하면 되기 때문에 연산을 수행하지 않아 최적화된 Add라고 볼 수 있다.tuple 형태의 패턴도 사용할 수 있다.
위 예제 코드는
:: 을 사용하여 l0 과 l1 리스트의 첫 번째 값인 head를 비교하고, tail에 해당하는 t0 , t1 을 equal 함수에 재귀적으로 사용하여 두 리스트의 값이 동일한지 확인하고 있다.
→ 함수형 프로그래밍의 꽃이라고 볼 수 있는 재귀를 사용하여 별도의 변수(비교에 사용하기 위한 임시 변수)를 추가로 만들지 않고 간결하게 코드를 작성했다. Pattern Guards
TODO
Backtick?
TODO
Applications of Pattern Matching
- Variable Definition
- Anonymous Functions
- For Loops
- Options
개발자가 예외를 처리하고,
null을 관리하는 것은 매우 위험하며, 개발자는 실수를 하기 마련이다.
→ 개발자가 관련 코드를 작성할수록 언젠가 문제가 발생할 가능성이 높아진다.get 함수를 사용하는 코드를 보면 List(1, 2)에서 0번째, 1번째에 접근이 가능하지만 2에 접근을 시도하므로 예외 처리를 위해 try except 문을 사용해야 한다.그러나 이러한 코드는 컴파일러가 예외가 제대로 처리되었는지 확인하지 않으며, 예외가 발생할 가능성이 있더라도 컴파일 오류가 발생하지 않는다. - 패턴 매칭에서 컴파일러의 도움을 받았던 것을 생각하자.
또한 책에서 예외 처리는 코드 이해에 방해를 주기 때문에 예외 없이
get을 구현하는 것이 바람직하다고 한다.위 코드는 비정상적인 접근일 때
null을 반환하며, 이외에는 수행 결과를 반환하려고 한다.
그러나 null 은 get 의 반환 타입인 Int 가 아니므로 컴파일러에서 거부한다.
만약 null을 Int로 처리할 수 있더라도 null 은 NullPointerException 을 발생시키는 원인이 되기 때문에 예외를 사용하는 것보다 낫지 않다고 한다.두 번째 방법은 단순히
-1을 반환하는 방법이다. 그러나 해당 방법도 좋은 방법은 아니다.
예를 들어 get(List(1, -1), 1) 이라면? 비정상적인 동작일 때의 반환 값과 같다.그래서 Scala에서는 비정상적인 동작을 안전하게 처리할 수 있는 옵션을 제공한다. -
None, Some
Some이라는 타입은 value를 감싸고 있는 형태라고 생각하면 된다.
→ ex: Some(3) 에서 value는 3을 의미한다.
→ 제네릭(A)을 사용하여 다양한 타입이 Some 안에 들어갈 수 있다.
None 은 Option[Nothing], 아무 것도 없는 상태를 의미한다.리스트에서
headOption으로 첫 번째 값을 가져올 수 있는데 값이 없을 경우 None을 반환하기 때문에 null이나 -1 과 같은 특정 값을 반환하는 방법보다 안전하다고 볼 수 있다.실제로 Scala에 구현된 Map 자료구조도 위와 같은 방식으로 구현되어 있다.
함수형 프로그래밍의 핵심인 고차 함수(
map, flatMap 등)를 사용할 때도 None인 경우 pass, Some 타입인 경우 사용하는 식으로 동작할 수 있다.
책에서 주어진
getHeight, getStudent 함수를 보면 Option 타입으로 반환하기 때문에 이전 예제에서 봤던 별도의 예외 처리(try ~ except)를 하지 않고, 핵심 코드만 사용하여 결과를 반환하고 있다.
→ 해당 함수를 사용하는 입장에서는 반환 값이 None 인지 아닌지만 체크하면 된다.→ Java에서
Optional 기능이 위 설명과 동일한 포지션이다. (자바 Optional 기초 - 최범균)Chapter 06
6장은 프로그래밍 언어로 작성한 문자들의 의미를 어떻게 해석하여 동작을 결정하는지에 대한 설명을 하고 있다.
위 사진의 의미는 텍스트 문자의 조합으로 만들어진 코드가 어떻게 동작할지는 해석하기 나름이라는 것이다.
https://ropas.snu.ac.kr/~dreameye/PL/slide/PL0.pdf
구체적 문법 (Concrete Syntax)
작성한 코드, 문자열에 대한 규칙을 의미한다.
→ ex: C, Java 언어에서는 줄 바꿈이 중요하지 않지만 Python에서는 줄 바꿈 문자가 중요하다.
→ ex: “문자열은 큰따옴표로 시작한다”, “주석은 연속된 역슬래시(backslash) 두 개로 시작한다”, “모든 연산자는 중위 연산자이다.” - 참고
위 예시처럼 실제 코드를 작성하기 위한 규칙을 의미한다. 이러한 규칙들이 모여서 언어 명세(Spectification)가 만들어진다.
이렇게 만들어지는 문자들의 집합은 일반적으로 무한 집합이라는 것이다. 문자의 개수를 제한하지 않기 때문에 무한한 집합의 모든 요소를 열거할 수 없다.
→ 구체적인 구문, 무한 집합을 정의하는 방법이 필요하다.
가장 일반적으로 사용되는 BNF(Backus-Naur form), BNF에서 간결한 표현 방법을 추가한 EBNF(Extended BNF)가 있다.
digit은 숫자들의 집합을 의미한다.
nat 는 digit 또는 digit nat 로 표기되어 있는데, 이는 숫자 하나 또는 연속된 숫자를 의미한다. (nat안에서 nat를 다시 부르고 있다.)
num은 연속된 숫자인 nat에서 -가 있는지, 없는지 구분한다.expr은 num, (라는 문자 뒤에 expr 문법에 맞는 값이 들어오고 + 또는 -가 왔는지 확인하며, 마지막에는 ) 가 왔는지 확인한다.
예를 들어 (1 + 2) 는 expr의 원소이지만, 1 + 2는 expr의 원소가 아니다. 식에 부합하는 문법이 없기 때문이다.
num의 경우에도 2나 -2는 num 의 원소이지만 +2 는 num의 원소가 아니다.
각각의 값들을
terminal, 정의된 문자들의 집합을 nonterminal이라고 한다. nonterminal은 변수를 정의할 때 값을 할당하는 것처럼 문자들의 집합을 정의한다고 생각하면 되겠다.위 코드는 lex를 사용하여 각각의 문자에 의미를 부여한 코드이다 - num.l
요약 문법 (Abstract Syntax)
요약 문법은 코드를 표현하는 추상적인 자료 구조를 의미한다.
이렇게 같은 동작을 수행하는 코드를 작성했지만 언어에 따라서 형태나 작성하는 방식이 각각 다르다.
또한 지금까지 사용해왔던 Scala, C++, Java의 경우 매개변수의 타입을 지정해야 하는 등 다양한 패턴이 존재한다.
그러나 언어가 바뀌어도 코드의 구조, 수행할 동작은 바뀌지 않는다는 것이다. 구체적 문법은 언어마다 다르겠지만 이를 요약된 형태, 코드를 표현하는 추상적인 자료 구조를 요약 문법이라고 한다.
구체적 문법은 문자열로 설명했지만, 요약 문법은 트리(Abstract Syntax Tree)로 표현한다.
4 + (2 - 1) 을 Scala 코드로 표현한다면 Add(Num(4), Sub(Num(2), Num(1))) 이다.위 코드는 yacc를 사용하여 BNF 문법을 정의하고 문법에 따라 동작을 수행하는 코드이다. - expr-explicit.y
그러나 명시적인(explicit) 방법은 모호함이 존재한다는 것이다. 예를 들어 위 문법의 경우
3 + 1 * 2라는 계산 식을 판단할 때 (3 + 1) * 2 가 될 수도 있고, 3 + (1 * 2)가 될 수도 있다.그래서
%left 문법을 사용하여 곱셉, 나눗셈의 우선순위가 덧셈, 뺄셈보다 높다고 명시하고 있다.이를 BNF 문법에서 해결하는 방법은 다음과 같다. - expr.y
BNF 문법 자체에 우선순위가 적용된 것이다.
3 + 1 * 2 를 위 문법을 적용하여 트리를 그리면 곱셈의 트리가 더 깊어지는 것을 확인할 수 있다.이렇게 문자를 토큰화하고 BNF 문법에 따라서 동작하는 과정을 파싱(Parsing)이라고 한다.
Sementics
Syntactic Sugar
TODO
Exercise
