Haskell 2010 표현식

Haskell 2010 표현식 (Expressions)

이 장은 Haskell 프로그래밍 언어에서 표현식(expression) 이 어떻게 생겼고, 어떤 의미를 갖는지 다루는 핵심 장이에요. 언어의 문법(syntax)을 정의하는 것에서 시작해, 각 표현식이 어떤 의미(semantics)를 갖는지, 또 필요할 때마다 Haskell의 핵심 언어(haskell kernel)로 어떻게 번역되는지까지 설명해요. 문법만 달랑 나열하는 게 아니라 "이게 실제로 계산에서 무엇을 뜻하는가"까지 잡아주니, 읽다 보면 Haskell의 계산 모델이 하나씩 그려지는 느낌을 받게 될 거예요.

출처: https://www.haskell.org/onlinereport/haskell2010/haskellch3.html

본문

이 장에서는 Haskell 표현식의 문법과 비공식적 의미론을 설명하고, 적절한 경우에는 Haskell 커널 언어로의 번역(translation)까지 함께 다뤄요. let 표현식의 경우를 빼면, 이러한 번역들은 정적 의미(static semantics)와 동적 의미(dynamic semantics)를 모두 보존해요. 번역에 사용되는 자유 변수와 생성자(constructor)는 항상 Prelude에 정의된 개체를 가리켜요. 예를 들어 리스트 컴프리헨션(List comprehension)의 번역(3.11절)에 쓰인 concatMap은, 해당 리스트 컴프리헨션이 쓰이는 자리에서 concatMap이라는 식별자가 스코프 안에 있든 없든, 그리고 (스코프 안에 있다면) 무엇에 묶여 있든 관계없이, 항상 Prelude가 정의한 concatMap을 뜻해요.

exp → infixexp :: [context =>] type (표현식 타입 시그니처)
| infixexp
infixexp → lexp qop infixexp (중위 연산자 적용)
| - infixexp (접두 부정)
| lexp
lexp → \ apat1 … apatn -> exp (람다 추상, n ≥ 1)
| let decls in exp (let 표현식)
| if exp [;] then exp [;] else exp (조건문)
| case exp of { alts } (case 표현식)
| do { stmts } (do 표현식)
| fexp
fexp → [fexp] aexp (함수 적용)
aexp → qvar (변수)
| gcon (일반 생성자)
| literal
| ( exp ) (괄호친 표현식)
| ( exp1 , … , expk ) (튜플, k ≥ 2)
| [ exp1 , … , expk ] (리스트, k ≥ 1)
| [ exp1 [, exp2] .. [exp3] ] (산술 수열)
| [ exp | qual1 , … , qualn ] (리스트 컴프리헨션, n ≥ 1)
| ( infixexp qop ) (왼쪽 섹션)
| ( qop⟨-⟩ infixexp ) (오른쪽 섹션)
| qcon { fbind1 , … , fbindn } (레이블 생성, n ≥ 0)
| aexp⟨qcon⟩ { fbind1 , … , fbindn } (레이블 갱신, n ≥ 1)

중위 연산자가 섞인 표현식은 연산자의 결합성/우선순위(fixity) 에 따라 모호함이 풀려요(4.4.2절 참고). 같은 우선순위를 가진 연산자들이 연속해서 괄호 없이 쓰이면, 문법 오류를 피하려면 반드시 전부 왼쪽 결합이거나 전부 오른쪽 결합이어야 해요. 괄호 없는 표현식 "x qop(a,i) y qop(b,j) z" (여기서 qop(a,i)는 결합성 a·우선순위 i를 가진 연산자)가 주어졌을 때, i = j라면 a = b = l(왼쪽 결합)이거나 a = b = r(오른쪽 결합)이 아닌 한, x qop(a,i) y 또는 y qop(b,j) z 중 하나에 괄호를 붙여야 해요.

중위 연산자를 포함한 표현식을 해석하는 예시 알고리즘은 10.6절에 나와 있어요.

부정(negation)은 Haskell에서 유일한 접두 연산자예요. Prelude에 정의된 중위 - 연산자와 같은 우선순위를 가져요(4.4.2절, 그림 4.1 참고).

문법은 람다 추상, let 표현식, 조건문의 범위(extent)에 대해 모호해요. 이 모호함은 "이 구성 각각은 가능한 한 오른쪽으로 멀리 확장된다" 는 메타 규칙에 의해 해소돼요.

해석(parse) 예시를 몇 가지 보여줄게요.

이 식이 이렇게 해석돼요
f x + g y (f x) + (g y)
- f x + y (- (f x)) + y
let { ... } in x + y let { ... } in (x + y)
z + let { ... } in x + y z + (let { ... } in (x + y))
f x y :: Int (f x y) :: Int
\ x -> a+b :: Int \ x -> ((a+b) :: Int)

명확성을 위해, 이 절의 나머지 부분에서는 중위 연산자가 포함된 표현식이 이미 연산자의 우선순위에 따라 해석되었다고 가정할게요.

3.1 오류 (Errors)

표현식 평가 중 발생하는 오류는 ⊥("바닥", bottom)로 표기하며, Haskell 프로그램 입장에서는 종료되지 않음(non-termination)과 구분할 수 없어요. Haskell은 비엄격(non-strict) 언어이므로, 모든 Haskell 타입에는 ⊥가 포함돼요. 다시 말해 어떤 타입의 값이든, 요구(demand)될 때 오류를 내는 계산에 묶일 수 있다는 뜻이에요. 오류는 평가되면 프로그램이 즉시 종료되고, 사용자가 잡을(catch) 수 없어요. 직접 이런 오류를 일으키는 함수 두 개를 Prelude가 제공해요:

error     :: String -> a
 
undefined :: a

error를 호출하면 프로그램 실행이 종료되고 운영체제에 적절한 오류 표시를 반환해요. 그리고 문자열을 시스템에 따라 어떤 방식으로든 표시해야 해요. undefined를 쓰면 오류 메시지는 컴파일러가 만들어 줘요.

Haskell 표현식의 번역에서는 실행 중 오류가 발생할 수 있는 지점을 명시적으로 표시하기 위해 error와 undefined를 사용해요. 오류 발생 시 실제 프로그램이 어떻게 동작할지는 구현에 달려 있어요. 이런 번역에서 error 함수에 전달되는 메시지는 단지 제안일 뿐이고, 구현은 오류 발생 시 더 많거나 적은 정보를 보여주도록 선택할 수 있어요.

3.2 변수, 생성자, 연산자, 리터럴 (Variables, Constructors, Operators, and Literals)

aexp → qvar (변수)
| gcon (일반 생성자)
| literal
gcon → ()
--- --- --- ---
| []
| (,{,})
| qcon
var → varid | ( varsym ) (변수)
qvar → qvarid | ( qvarsym ) (한정 변수)
con → conid | ( consym ) (생성자)
qcon → qconid | ( gconsym ) (한정 생성자)
varop → varsym | varid (변수 연산자)
qvarop → qvarsym | qvarid (한정 변수 연산자)
conop → consym | conid (생성자 연산자)
qconop → gconsym | qconid (한정 생성자 연산자)
op → varop | conop (연산자)
qop → qvarop | qconop (한정 연산자)
gconsym → : | qconsym

Haskell은 중위 표기법(infix notation)을 지원하기 위해 특별한 문법을 제공해요. 연산자(operator) 는 중위 문법(3.4절)으로 적용하거나, 섹션(3.5절)을 통해 부분 적용할 수 있는 함수예요.

연산자는 +나 $$ 같은 연산자 기호이거나, op처럼 역따옴표(백쿼트)로 둘러싼 보통 식별자예요. 예를 들어 접두 적용 op x y를 쓰는 대신 중위 적용 x op y라고 쓸 수 있어요. op에 대한 우선순위(fixity) 선언이 없으면 가장 높은 우선순위와 왼쪽 결합으로 기본값을 가져요(4.4.2절 참고).

그 반대로, 연산자 기호는 괄호로 감싸면 보통 식별자로 바꿀 수 있어요. 예를 들어 (+) x y는 x + y와 같고, foldr (⋆) 1 xs는 foldr (\x y -> x⋆y) 1 xs와 같아요.

몇몇 내장 타입의 생성자에 이름을 붙이기 위해 특별한 문법이 쓰이는데, gcon과 literal의 생성 규칙에서 찾을 수 있어요. 이것들은 6.1절에서 설명해요.

정수 리터럴은 fromInteger 함수를 적절한 Integer 타입 값에 적용한 것을 나타내요. 마찬가지로 부동소수점 리터럴은 fromRational을 Rational 타입 값(즉 Ratio Integer)에 적용한 것을 뜻해요.

번역: 정수 리터럴 i는 fromInteger i와 동등해요. 여기서 fromInteger은 Num 클래스의 메서드예요(6.4.1절 참고). 부동소수점 리터럴 f는 fromRational (n Ratio.% d)와 동등해요. fromRational은 Fractional 클래스의 메서드이고, Ratio.%는 두 정수로 유리수를 만들어 주는 함수로 Ratio 라이브러리에 정의돼 있어요. 정수 n과 d는 n∕d = f가 되도록 선택돼요.

3.3 커리 적용과 람다 추상 (Curried Applications and Lambda Abstractions)

fexp → [fexp] aexp (함수 적용)
lexp → \ apat1 … apatn -> exp (람다 추상, n ≥ 1)

함수 적용은 e1 e2로 써요. 적용은 왼쪽 결합이므로 (f x) y에서 괄호를 생략할 수 있어요. e1은 데이터 생성자가 될 수 있기 때문에, 데이터 생성자의 부분 적용도 허용돼요.

람다 추상은 \ p1 … pn -> e로 쓰고, 여기서 pi는 패턴이에요. \x:xs->x 같은 표현식은 문법상 올바르지 않아요. \(x:xs)->x처럼 쓰는 건 합법적이에요.

패턴의 집합은 선형(linear) 이어야 해요. 즉 같은 변수가 집합 안에 두 번 이상 나타나면 안 돼요.

번역: 다음 항등식이 성립해요.

\ p1 … pn -> e = \ x1 … xn -> case (x1, …, xn) of (p1, …, pn) -> e

여기서 xi는 새로운 식별자예요. 이 번역을 3.17.3절의 case 표현식 의미론 및 패턴 매칭과 결합하면, 패턴이 매칭에 실패하면 결과는 ⊥가 돼요.

3.4 연산자 적용 (Operator Applications)

infixexp → lexp qop infixexp
| - infixexp (접두 부정)
| lexp
qop → qvarop | qconop (한정 연산자)

e1 qop e2 형태는 이진 연산자 qop를 표현식 e1, e2에 중위 적용한 거예요.

특별한 형태 -e는 접두 부정(prefix negation)으로, Haskell에서 유일한 접두 연산자이며 negate (e)의 문법이에요. 이진 - 연산자는 반드시 Prelude의 - 정의를 가리키는 게 아니에요. 모듈 시스템에 의해 다시 묶일(rebind) 수 있어요. 하지만 단항 -는 항상 Prelude에 정의된 negate 함수를 가리켜요. 지역적으로 쓰인 - 연산자의 의미와 단항 부정 사이에는 아무 연관이 없어요.

접두 부정은 Prelude에 정의된 중위 연산자 -와 같은 우선순위를 가져요(표 4.1 참고). e1-e2는 이진 연산자 -의 중위 적용으로 해석되므로, 다른 해석을 원하면 e1(-e2)라고 써야 해요. 마찬가지로 (-)는 다른 중위 연산자처럼 (\ x y -> x-y)의 문법이지, (\ x -> -x)를 뜻하지 않아요. 그건 negate를 써야 해요.

번역: 다음 항등식이 성립해요.

e1 op e2 = (op) e1 e2
-e = negate (e)

3.5 섹션 (Sections)

aexp → ( infixexp qop ) (왼쪽 섹션)
| ( qop⟨-⟩ infixexp ) (오른쪽 섹션)

섹션은 ( op e ) 또는 ( e op )로 쓰는데, op는 이진 연산자이고 e는 표현식이에요. 섹션은 이진 연산자의 부분 적용을 위한 편리한 문법이에요.

섹션에는 문법적 우선순위 규칙이 적용돼요. (x op e)가 (x op (e))와 같은 방식으로 해석될 때에만 (op e)는 합법적이에요. (e op)도 마찬가지예요. 예를 들어 (⋆a+b)는 문법적으로 유효하지 않지만, (+a⋆b)와 (⋆(a+b))는 유효해요. (+)는 왼쪽 결합이므로 (a+b+)는 문법적으로 맞지만 (+a+b)는 아니에요. 후자는 (+(a+b))라고 쓰면 합법적이 돼요. 또 다른 예로, 다음 표현식은

  (let n = 10 in n +)

유효하지 않아요. 왜냐하면 let/람다 메타 규칙(3절)에 의해 다음 표현식이

  (let n = 10 in n + x)

이렇게 해석되기 때문이에요.

  (let n = 10 in (n + x))

다음처럼 해석되는 게 아니라요.

  ((let n = 10 in n) + x)

-는 문법에서 특별하게 취급되므로 (- exp)는 섹션이 아니라 앞 절에서 설명한 접두 부정의 적용이에요. 하지만 Prelude에는 (subtract exp)가 금지된 섹션과 동등하도록 만드는 subtract 함수가 정의돼 있어요. (+ (- exp)) 표현식도 같은 목적을 수행할 수 있어요.

번역: 다음 항등식이 성립해요.

(op e) = \ x -> x op e
(e op) = \ x -> e op x

여기서 op는 이진 연산자, e는 표현식, x는 e에 자유롭게 나타나지 않는 변수예요.

3.6 조건문 (Conditionals)

lexp → if exp [;] then exp [;] else exp

조건문은 if e1 then e2 else e3 형태를 가지며, e1의 값이 True면 e2의 값을, False면 e3의 값을, 그 외에는 ⊥를 반환해요.

번역: 다음 항등식이 성립해요.

if e1 then e2 else e3 = case e1 of { True -> e2 ; False -> e3 }

여기서 True와 False는 Prelude에 정의된 Bool 타입의 두 nullary 생성자예요. e1의 타입은 Bool이어야 하고, e2와 e3는 같은 타입이어야 해요. 그 타입이 곧 전체 조건문의 타입이 돼요.

3.7 리스트 (Lists)

infixexp → exp1 qop exp2
aexp → [ exp1 , … , expk ] (k ≥ 1)
| gcon
gcon → []
| qcon
qcon → ( gconsym )
qop → qconop
qconop → gconsym
gconsym → :

리스트는 [e1, …, ek]로 쓰고, 여기서 k ≥ 1이에요. 리스트 생성자는 :이고, 빈 리스트는 []로 나타내요. 리스트의 표준 연산들은 Prelude에 나와 있어요(6.1.3절, 그리고 특히 9.1절을 포함한 9장 참고).

번역: 다음 항등식이 성립해요.

[e1, …, ek] = e1 : (e2 : ( … (ek : [])))

여기서 :과 []는 Prelude에 정의된 리스트 생성자예요(6.1.3절 참고). e1부터 ek까지의 타입은 모두 같아야 하고(그 타입을 t라고 해요), 전체 표현식의 타입은 [t]가 돼요(4.1.2절 참고).

생성자 :은 리스트 생성 전용으로 예약되어 있어요. []처럼 언어 문법의 일부로 간주되며 숨기거나 재정의할 수 없어요. 우선순위 5의 오른쪽 결합 연산자예요(4.4.2절 참고).

3.8 튜플 (Tuples)

aexp → ( exp1 , … , expk ) (k ≥ 2)
| qcon
qcon → (,{,})

튜플은 (e1, …, ek)로 쓰며 임의의 길이 k ≥ 2를 가질 수 있어요. n-튜플의 생성자는 (,…,)로 나타내는데, 여기에는 쉼표가 n − 1개 있어요. 따라서 (a,b,c)와 (,,) a b c는 같은 값을 나타내요. 튜플의 표준 연산들은 Prelude에 나와 있어요(6.1.4절과 9장 참고).

번역: k ≥ 2인 (e1, …, ek)는 Prelude에 정의된 k-튜플의 인스턴스이므로 번역이 필요 없어요. t1부터 tk가 각각 e1부터 ek의 타입이라면, 결과 튜플의 타입은 (t1, …, tk)가 돼요(4.1.2절 참고).

3.9 유닛 표현식과 괄호친 표현식 (Unit Expressions and Parenthesized Expressions)

aexp → gcon
| ( exp )
gcon → ()

형태 (e)는 단순히 괄호 친 표현식이고 e와 동등해요. 유닛 표현식 ()은 타입 ()을 가져요(4.1.2절 참고). ⊥를 제외하면 그 타입의 유일한 멤버이고, "nullary 튜플"로 생각할 수 있어요(6.1.5절 참고).

번역: (e)는 e와 동등해요.

3.10 산술 수열 (Arithmetic Sequences)

aexp → [ exp1 [, exp2] .. [exp3] ]

산술 수열 [e1, e2 .. e3]은 타입 t의 값들의 리스트를 나타내요. 각 ei는 타입 t이고, t는 Enum 클래스의 인스턴스예요.

번역: 산술 수열은 다음 항등식을 만족해요.

[ e1.. ] = enumFrom e1
[ e1,e2.. ] = enumFromThen e1 e2
[ e1..e3 ] = enumFromTo e1 e3
[ e1,e2..e3 ] = enumFromThenTo e1 e2 e3

여기서 enumFrom, enumFromThen, enumFromTo, enumFromThenTo는 Prelude에 정의된 Enum 클래스의 클래스 메서드예요(그림 6.1 참고).

따라서 산술 수열의 의미론은 전적으로 타입 t의 인스턴스 선언에 달려 있어요. 어떤 Prelude 타입이 Enum에 속하고 그 의미가 무엇인지에 대한 자세한 내용은 6.3.4절을 참고해요.

3.11 리스트 컴프리헨션 (List Comprehensions)

aexp → [ exp | qual1 , … , qualn ] (리스트 컴프리헨션, n ≥ 1)
qual → pat <- exp (제너레이터)
| let decls (지역 선언)
| exp (부울 가드)

리스트 컴프리헨션은 [ e | q1, …, qn ], n ≥ 1 형태를 가지며, 여기서 qi 한정자(qualifier)는 다음 중 하나예요.

  • 제너레이터: p <- e 형태. p는 타입 t의 패턴(3.17절 참고)이고 e는 타입 [t]의 표현식이에요.
  • 지역 바인딩: 생성된 표현식 e 또는 이후의 부울 가드·제너레이터에서 쓸 새로운 정의를 제공해요.
  • 부울 가드: 타입 Bool의 임의의 표현식이에요.

이런 리스트 컴프리헨션은, 한정자 목록에 있는 제너레이터들을 중첩·깊이 우선(depth-first)으로 평가해 만든 연속적인 환경에서 e를 평가해 얻은 원소들의 리스트를 반환해요. 변수 바인딩은 일반적인 패턴 매칭 규칙(3.17절 참고)에 따라 발생하고, 매칭이 실패하면 그 리스트의 원소는 그냥 건너뛰어져요. 그래서:

[ x |  xs   <- [ [(1,2),(3,4)], [(5,4),(3,2)] ],
 
     (3,x) <- xs ]

이 리스트 [4,2]를 만들어요. 한정자가 부울 가드라면, 이전 패턴 매칭이 성공하려면 True로 평가되어야 해요. 평소처럼 리스트 컴프리헨션의 바인딩은 바깥 스코프의 것을 가릴(shadow) 수 있어요. 예를 들어:

[ x | x <- x, x <- x ] = [ z | y <- x, z <- y]

번역: 리스트 컴프리헨션은 다음 항등식을 만족하며, 이를 커널 언어로의 번역으로 쓸 수 있어요.

[ e | True ] = [e]
[ e | q ] = [ e | q, True ]
[ e | b, Q ] = if b then [ e | Q ] else []
[ e | p <- l, Q ] = let ok p = [ e | Q ]
ok _ = []
in concatMap ok l
[ e | let decls, Q ] = let decls in [ e | Q ]

여기서 e는 표현식, p는 패턴, l은 리스트 값 표현식, b는 부울 표현식, decls는 선언 목록, q는 한정자, Q는 한정자 수열을 범위로 삼아요. ok는 새로운 변수예요. 함수 concatMap과 부울 값 True는 Prelude에 정의돼 있어요.

리스트 컴프리헨션의 번역에서 알 수 있듯이, let이 묶은 변수는 완전히 다형적(polymorphic)인 타입을 갖는 반면, <-로 정의된 변수는 람다에 묶여 있어서 단형적(monomorphic)이에요(4.5.4절 참고).

3.12 let 표현식 (Let Expressions)

lexp → let decls in exp

let 표현식은 일반적인 형태 let { d1 ; … ; dn } in e를 가지며, 중첩되고 어휘적 스코프를 가지며 상호 재귀적인 선언 목록을 도입해요(다른 언어에서는 let을 흔히 letrec이라고 불러요). 선언의 스코프는 표현식 e와 선언들 자신의 우변(right hand side)이에요. 선언에 대한 설명은 4장에 있어요. 패턴 바인딩은 게으르게(lazily) 매칭돼요. 암묵적 ~가 이 패턴들을 기각 불가능(irrefutable)하게 만들어요. 예를 들어

let (x,y) = undefined in e

는 x나 y가 평가되기 전까지는 실행 시간 오류를 일으키지 않아요.

번역: 표현식 let { d1 ; … ; dn } in e0의 동적 의미는 이 번역으로 포착돼요. 모든 타입 시그니처를 제거한 뒤, 각 선언 di는 4.4.3절의 번역을 사용해 pi = ei 꼴의 방정식으로 번역되는데, pi와 ei는 각각 패턴과 표현식이에요. 그다음 다음 항등식이 성립하며, 이를 커널 언어로의 번역으로 쓸 수 있어요.

let {p1=e1; ... ; pn=en} in e0 = let (~p1, ... ,~pn) = (e1, ... ,en) in e0
let p = e1 in e0 = case e1 of ~p -> e0
where no variable in p appears free in e1
let p = e1 in e0 = let p = fix ( \ ~p -> e1) in e0

여기서 fix는 최소 고정점 연산자예요. 기각 불가능한 패턴 ~p의 사용에 주목해요. 이 번역은 정적 의미를 보존하지 않는데, case의 사용이 묶인 변수의 완전한 다형적 타입을 배제하기 때문이에요. let 표현식 바인딩의 정적 의미는 4.4.3절에 설명돼 있어요.

3.13 case 표현식 (Case Expressions)

lexp → case exp of { alts }
alts → alt1 ; … ; altn (n ≥ 1)
alt → pat -> exp [where decls]
| pat gdpat [where decls]
| (빈 대안)
gdpat → guards -> exp [ gdpat ]
guards → | guard1, …, guardn (n ≥ 1)
guard → pat <- infixexp (패턴 가드)
| let decls (지역 선언)
| infixexp (부울 가드)

case 표현식은 일반적인 형태가 다음과 같고,

case e of { p1 match1 ; … ; pn matchn }

각 matchi는 일반적인 형태가 다음과 같아요.

| gsi1 -> ei1
…
| gsimi -> eimi
where declsi

가드(guard)는 다음 형태 중 하나를 가져요.

  • 패턴 가드는 p <- e 형태예요. p는 타입 t의 패턴(3.17절 참고)이고 e는 타입 t1의 표현식이에요. 표현식 e가 패턴 p와 매칭되면 성공하고, 패턴의 바인딩을 환경에 도입해요.
  • 지역 바인딩은 let decls 형태예요. 항상 성공하고, decls에 정의된 이름을 환경에 도입해요.
  • 부울 가드는 타입 Bool의 임의의 표현식이에요. 표현식이 True로 평가되면 성공하고, 환경에 새 이름을 도입하지 않아요. 부울 가드 g는 의미상 패턴 가드 True <- g와 동등해요.

다음 형태의 대안은

pat -> exp where decls

다음의 축약으로 취급돼요.

pat | True -> exp
where decls

case 표현식은 최소한 하나의 대안을 가져야 하고, 각 대안은 최소한 하나의 본문(body)을 가져야 해요. 각 본문은 같은 타입이어야 하고, 전체 표현식의 타입이 바로 그 타입이 돼요.

case 표현식은 표현식 e를 개별 대안들에 패턴 매칭함으로써 평가돼요. 대안들은 위에서 아래로 순서대로 시도돼요. e가 어떤 대안의 패턴과 매칭되면, 그 대안의 가드 표현식들이 case 표현식의 환경에서 위에서 아래로 순서대로 시도돼요. 이 환경은 먼저 패턴 매칭 중 만들어진 바인딩으로, 그다음 그 대안에 딸린 where 절의 declsi로 확장된 것이에요.

각 가드 표현식에 대해, 쉼표로 구분된 가드들은 왼쪽에서 오른쪽으로 순서대로 시도돼요. 전부 성공하면 해당 표현식이, 가드가 도입한 바인딩으로 확장된 환경에서 평가돼요. 즉 가드가 도입한 바인딩(let 절이나 패턴 가드를 통해서든)은 뒤따르는 가드들과 해당 표현식에서 스코프 안에 있어요. 가드 중 하나라도 실패하면 이 가드 표현식은 실패하고 다음 가드 표현식이 시도돼요.

주어진 대안의 가드 표현식이 하나도 성공하지 못하면, 매칭은 다음 대안으로 계속돼요. 어떤 대안도 성공하지 못하면 결과는 ⊥예요. 패턴 매칭은 3.17절에 설명되고, case 표현식의 형식적 의미론은 3.17.3절에 있어요.

해석(parsing)에 대한 주의사항 하나. 다음 표현식은

  case x of { (a,_) | let b = not a in b :: Bool -> a }

정확히 해석하기 까다로워요. 단 하나의 모호하지 않은 해석이 있는데, 바로 이거예요.

  case x of { (a,_) | (let b = not a in b :: Bool) -> a }

그런데 Bool -> a라는 말은 타입으로서 문법적으로 유효하기 때문에, 제한된 lookahead를 가진 파서는 이 선택지에 잘못 빠져서 프로그램을 거부할 수 있어요. 따라서 프로그래머는 타입 시그니처로 끝나는 가드를 피하는 것이 좋아요. 사실 그래서 가드에는 exp가 아니라 infixexp가 들어가는 거예요.

3.14 do 표현식 (Do Expressions)

lexp → do { stmts } (do 표현식)
stmts → stmt1 … stmtn exp [;] (n ≥ 0)
stmt → exp ;
| pat <- exp ;
| let decls ;
| ; (빈 문장)

do 표현식은 모나딕 프로그래밍을 위한 더 전통적인 문법을 제공해요. 다음 같은 표현식을

  putStr "x: "    >>
 
  getLine         >>= \l ->
 
  return (words l)

더 전통적인 방식으로 이렇게 쓸 수 있게 해줘요.

  do putStr "x: "
 
     l <- getLine
 
     return (words l)

번역: do 표현식은 (빈 stmt을 제거한 뒤) 다음 항등식을 만족하며, 이를 커널 언어로의 번역으로 쓸 수 있어요.

do {e} = e
do {e;stmts} = e >> do {stmts}
do {p <- e; stmts} = let ok p = do {stmts}
ok _ = fail "..."
in e >>= ok
do {let decls; stmts} = let decls in do {stmts}

생략 부호 "..."는 컴파일러가 생성한, fail에 전달되는 오류 메시지를 뜻해요. 가능하면 패턴 매칭 실패가 발생한 위치를 알려 주는 것이 좋아요. 함수 >>, >>=, fail은 Prelude에 정의된 Monad 클래스의 연산이고, ok는 새로운 식별자예요.

do의 번역에서 알 수 있듯이, let이 묶은 변수는 완전히 다형적인 타입을 갖는 반면 <-로 정의된 변수는 람다에 묶여 있어서 단형적이에요.

3.15 필드 레이블을 가진 데이터 타입 (Datatypes with Field Labels)

데이터 타입 선언은 선택적으로 필드 레이블(field label)을 정의할 수 있어요(4.2.1절 참고). 이 필드 레이블은 데이터 타입의 전체 구조와 무관하게 필드를 생성·선택·갱신하는 데 쓸 수 있어요.

서로 다른 데이터 타입은 같은 스코프에서 공통 필드 레이블을 공유할 수 없어요. 필드 레이블은 한 생성자에서 최대 한 번만 쓸 수 있어요. 다만 한 데이터 타입 안에서는, 필드가 모든 생성자에서 같은 타입을 가진다면, 한 필드 레이블을 여러 생성자에서 쓸 수 있어요. 마지막 요점을 설명하기 위해 다음을 보게요.

  data S = S1 { x :: Int } | S2 { x :: Int }   -- OK
 
  data T = T1 { y :: Int } | T2 { y :: Bool }  -- BAD

여기서 S는 합법적이지만 T는 아니에요. 후자에서 y에 일관되지 않은 타입이 주어졌기 때문이에요.

3.15.1 필드 선택 (Field Selection)

aexp → qvar

필드 레이블은 선택자(selector) 함수로 쓰여요. 변수로 쓰일 때 필드 레이블은 객체에서 필드를 추출하는 함수 역할을 해요. 선택자는 최상위 바인딩이라서 지역 변수에 의해 가려질(shadow) 수 있지만, 같은 이름의 다른 최상위 바인딩과 충돌할 수는 없어요. 이 그림자는 선택자 함수에만 영향을 줘요. 레코드 생성(3.15.2절)과 갱신(3.15.3절)에서는 필드 레이블이 일반 변수와 혼동될 수 없어요.

번역: 필드 레이블 f는 다음과 같이 정의된 선택자 함수를 도입해요.

f x = case x of { C1 p11 … p1k -> e1 ;… ; Cn pn1 … pnk -> en }

여기서 C1 … Cn은 레이블 f가 붙은 필드를 포함하는 데이터 타입의 모든 생성자이고, f가 Ci의 j번째 성분에 붙어 있으면 pij는 y, 그렇지 않으면 _이며, Ci의 어떤 필드에 레이블 f가 있으면 ei는 y, 그렇지 않으면 undefined예요.

3.15.2 필드 레이블로 생성 (Construction Using Field Labels)

aexp → qcon { fbind1 , … , fbindn } (레이블 생성, n ≥ 0)
fbind → qvar = exp

레이블이 있는 필드를 가진 생성자는, 성분을 위치가 아니라 이름으로 지정해 값을 생성하는 데 쓰일 수 있어요. 선언 목록에 쓰는 중괄호와 달리 이것들은 레이아웃(layout)의 대상이 아니에요. {와 } 문자는 명시적이어야 해요. (필드 갱신과 필드 패턴도 마찬가지예요.) 필드 레이블로 생성하는 데는 다음 제약이 적용돼요.

  • 지정된 생성자로 선언된 필드 레이블만 언급할 수 있어요.
  • 필드 레이블은 한 번 이상 언급될 수 없어요.
  • 언급되지 않은 필드는 ⊥로 초기화돼요.
  • 생성 중에 어떤 엄격 필드(strict field, !가 붙은 선언 타입을 가진 필드)를 생략하면 컴파일 시간 오류가 발생해요. 엄격 필드는 4.2.1절에서 다뤄요.

F {} 표현식은 F가 레코드 문법으로 선언되었는지와 무관하게(단 F에 엄격 필드가 없어야 해요 — 위 네 번째 항목 참고) 합법적이에요. 그리고 F ⊥1 … ⊥n을 나타내는데, n은 F의 인자 수(arity)예요.

번역: 바인딩 f = v에서 필드 f는 v에 레이블을 붙여요.

C { bs } = C (pick1C bs undefined) … (pickkC bs undefined)

여기서 k는 C의 인자 수예요.

보조 함수 pickiC bs d는 다음과 같이 정의돼요. 생성자 C의 i번째 성분이 필드 레이블 f를 갖고, f = v가 바인딩 목록 bs에 나타나면 pickiC bs d는 v예요. 그렇지 않으면 pickiC bs d는 기본값 d예요.

3.15.3 필드 레이블로 갱신 (Updates Using Field Labels)

aexp → aexp⟨qcon⟩ { fbind1 , … , fbindn } (레이블 갱신, n ≥ 1)

필드 레이블을 가진 데이터 타입의 값은 비파괴적으로(non-destructively) 갱신될 수 있어요. 지정된 필드 값이 기존 값의 그것을 대체하는 새 값을 만들어요. 갱신은 다음 방식으로 제한돼요.

  • 모든 레이블은 같은 데이터 타입에서 가져와야 해요.
  • 적어도 하나의 생성자가 갱신에 언급된 모든 레이블을 정의해야 해요.
  • 어떤 레이블도 한 번 이상 언급될 수 없어요.
  • 갱신되는 값이 지정된 레이블을 모두 포함하지 않으면 실행 오류가 발생해요.

번역: 앞서 정의한 pick을 사용해,

e { bs } = case e of
C1 v1 … vk1 -> C1 (pick1C1 bs v1) … (pickk 1C1 bs v k1)
...
Cj v1 … vkj -> Cj (pick1Cj bs v1) … (pickk jCj bs v kj)
_ -> error "Update error"

여기서 {C1,…,Cj}는 bs의 모든 레이블을 포함하는 생성자들의 집합이고, ki는 Ci의 인자 수예요.

필드 레이블을 사용하는 예시 몇 가지를 보게요.

data T    = C1 {f1,f2 :: Int}
 
          | C2 {f1 :: Int,
 
                f3,f4 :: Char}
표현식 번역
C1 {f1 = 3} C1 3 undefined
C2 {f1 = 1, f4 = 'A', f3 = 'B'} C2 1 'B' 'A'
x {f1 = 1} case x of C1 _ f2 -> C1 1 f2
C2 _ f3 f4 -> C2 1 f3 f4

3.16 표현식 타입 시그니처 (Expression Type-Signatures)

exp → exp :: [context =>] type

표현식 타입 시그니처는 e :: t 형태를 가지며, e는 표현식이고 t는 타입이에요(4.1.2절 참고). 표현식에 타입을 명시적으로 붙이기 위해 쓰이며, 오버로딩으로 인한 모호한 타입을 해소하는 데 쓸 수 있어요(4.3.4절 참고). 표현식의 값은 그냥 exp의 값이에요. 일반적인 타입 시그니처(4.4.1절 참고)처럼, 선언된 타입은 exp에서 유도 가능한 주 타입(principal type)보다 더 구체적일 수 있지만, 주 타입보다 더 일반적이거나 비교할 수 없는 타입을 주는 것은 오류예요.

번역:

e :: t = let { v :: t; v = e } in v

3.17 패턴 매칭 (Pattern Matching)

패턴은 람다 추상, 함수 정의, 패턴 바인딩, 리스트 컴프리헨션, do 표현식, case 표현식에 나타나요. 하지만 이 중 앞의 다섯 가지는 궁극적으로 case 표현식으로 번역되므로, case 표현식에 대한 패턴 매칭의 의미론을 정의하는 것으로 충분해요.

3.17.1 패턴 (Patterns)

패턴은 다음과 같은 문법을 가져요.

pat → lpat qconop pat (중위 생성자)
| lpat
lpat → apat
| - (integer | float) (음수 리터럴)
| gcon apat1 … apatk (arity gcon = k, k ≥ 1)
apat → var [ @ apat] (as 패턴)
| gcon (arity gcon = 0)
| qcon { fpat1 , … , fpatk } (레이블 패턴, k ≥ 0)
| literal
| _ (와일드카드)
| ( pat ) (괄호친 패턴)
| ( pat1 , … , patk ) (튜플 패턴, k ≥ 2)
| [ pat1 , … , patk ] (리스트 패턴, k ≥ 1)
| ~ apat (기각 불가능 패턴)
fpat → qvar = pat

생성자의 인자 수(arity)는 그와 연관된 하위 패턴의 수와 일치해야 해요. 부분 적용된 생성자에 대해 매칭할 수는 없어요.

모든 패턴은 선형이어야 해요. 즉 같은 변수가 두 번 이상 나타날 수 없어요. 예를 들어 다음 정의는 불법이에요.

f (x,x) = x     -- ILLEGAL; x used twice in pattern

var@pat 형태의 패턴은 as 패턴이라고 부르며, pat에 의해 매칭되는 값을 가리키는 이름으로 var를 쓸 수 있게 해줘요. 예를 들어

case e of { xs@(x:rest) -> if x==0 then rest else xs }

는 다음과 동등해요.

let { xs = e } in
 
  case xs of { (x:rest) -> if x==0 then rest else xs }

_ 형태의 패턴은 와일드카드이며, 패턴의 어떤 부분이 우변에서 참조되지 않을 때 유용해요. 다른 곳에서 쓰이지 않는 식별자가 그 자리에 놓인 것과 같아요. 예를 들어

case e of { [x,_,_]  ->  if x==0 then True else False }

는 다음과 동등해요.

case e of { [x,y,z]  ->  if x==0 then True else False }

3.17.2 패턴 매칭의 비공식적 의미론 (Informal Semantics of Pattern Matching)

패턴은 값에 대해 매칭돼요. 패턴을 매칭하려는 시도는 세 가지 결과 중 하나를 가질 수 있어요. 실패하거나, 패턴의 각 변수에 대한 바인딩을 반환하며 성공하거나, 발산할(divergence, 즉 ⊥ 반환) 수 있어요. 패턴 매칭은 왼쪽에서 오른쪽으로, 바깥에서 안쪽으로 다음 규칙에 따라 진행돼요.

  1. 값 v에 대해 패턴 var을 매칭하는 것은 항상 성공하고 var을 v에 바인딩해요. 값 v에 대해 패턴 ~apat을 매칭하는 것은 항상 성공해요. apat을 v에 매칭하는 것이 성공했다면 apat의 자유 변수들은 각각의 값에, 그 매칭이 실패하거나 발산한다면 ⊥에 바인딩돼요. (바인딩이 평가를 의미하지는 않아요.)
  2. 연산적으로 말하면, ~apat 패턴에 대해서는 apat의 변수 중 하나가 사용될 때까지 매칭이 수행되지 않아요. 그 시점에 전체 패턴이 값에 대해 매칭되고, 매칭이 실패하거나 발산하면 전체 계산도 그렇게 돼요.
  3. 값에 대해 와일드카드 패턴 _을 매칭하는 것은 항상 성공하고, 바인딩은 이루어지지 않아요. newtype으로 정의된 생성자 con을 포함하는 패턴 con pat을 값에 대해 매칭하는 것은 값에 따라 달라져요.
    • 값이 con v 형태이면, pat을 v에 대해 매칭해요.
    • 값이 ⊥이면, pat을 ⊥에 대해 매칭해요. 즉 newtype과 연관된 생성자는 값의 타입을 바꾸는 역할만 해요. data로 정의된 생성자 con을 포함하는 패턴 con pat1 … patn을 값에 대해 매칭하는 것은 값에 따라 달라져요.
    • 값이 con v1 … vn 형태이면, 하위 패턴들을 데이터 값의 성분들에 대해 왼쪽에서 오른쪽으로 매칭해요. 전부 성공하면 전체 매칭이 성공하고, 첫 번째 실패하거나 발산하는 것이 전체 매칭을 각각 실패시키거나 발산시켜요.
    • 값이 con′ v1 … vm 형태이고 con이 con′와 다른 생성자이면, 매칭은 실패해요.
    • 값이 ⊥이면, 매칭은 발산해요.
  4. 레이블이 붙은 필드를 사용한 생성자 매칭은, 필드가 필드 목록에 이름이 붙은 순서대로 매칭된다는 점을 제외하면 일반적인 생성자 패턴 매칭과 같아요. 나열된 모든 필드는 생성자가 선언한 것이어야 해요. 필드는 한 번 이상 이름이 붙을 수 없어요. 패턴이 이름을 붙이지 않은 필드는 무시돼요(_에 매칭됨). 리터럴 패턴(숫자·문자·문자열) k를 값 v에 매칭하는 것은 v == k이면 성공해요. 여기서 ==는 패턴의 타입에 기반해 오버로딩돼요. 이 검사가 발산하면 매칭도 발산해요.
  5. 숫자 리터럴의 해석은 정확히 3.2절에 설명된 대로예요. 즉 오버로딩된 함수 fromInteger 또는 fromRational을 Integer 또는 Rational 리터럴에 적용해 적절한 타입으로 변환해요.
  6. as 패턴 var@apat을 값 v에 매칭하는 것은, var을 v에 바인딩하는 것을 더한 apat을 v에 매칭한 결과예요. apat을 v에 매칭하는 것이 실패하거나 발산하면 전체 매칭도 그러해요.

명백한 정적 타입 제약(예: 부울에 문자를 매칭하는 것은 정적 오류) 외에도, 다음과 같은 정적 클래스 제약이 성립해요.

  • 정수 리터럴 패턴은 Num 클래스에 있는 값에만 매칭할 수 있어요.
  • 부동소수점 리터럴 패턴은 Fractional 클래스에 있는 값에만 매칭할 수 있어요.

때로는 두 종류의 패턴을 구분하는 것이 도움이 돼요. 기각 불가능한(irrefutable) 패턴을 매칭하는 것은 비엄격해요. 매칭할 값이 ⊥라도 패턴이 매칭돼요. 기각 가능한(refutable) 패턴을 매칭하는 것은 엄격해요. 매칭할 값이 ⊥이면 매칭이 발산해요. 기각 불가능한 패턴은 다음과 같아요. 변수, 와일드카드, N apat(여기서 N은 newtype으로 정의된 생성자이고 apat은 기각 불가능, 4.2.3절 참고), var@apat(여기서 apat은 기각 불가능), 또는 ~apat 형태(apat이 기각 불가능한지와 무관). 그 외의 모든 패턴은 기각 가능해요.

예시 몇 가지를 보게요.

  1. 패턴 ['a','b']를 ['x',⊥]에 매칭하면, 'a'가 'x'에 매칭에 실패해서 결과는 매칭 실패예요. 하지만 ['a','b']를 [⊥,'x']에 매칭하면, 'a'를 ⊥에 매칭하려 시도하다가 매칭이 발산해요.

이 예시들은 기각 가능 vs 기각 불가능 매칭을 보여줘요.

(\ ~(x,y) -> 0) ⊥ ⇒ 0
(\ (x,y) -> 0) ⊥ ⇒ ⊥
(\ ~[x] -> 0) [] ⇒ 0
---
(\ ~[x] -> x) [] ⇒ ⊥
(\ [x,(a,b)] -> x) [(0,1),⊥] ⇒ (0,1)
---
(\ ~[x, (a,b)] -> x) [(0,1),⊥] ⇒ ⊥
(\ (x:xs) -> x:x:xs) ⊥ ⇒ ⊥
---
(\ ~(x:xs) -> x:x:xs) ⊥ ⇒ ⊥:⊥:⊥
  1. 다음 선언들을 생각해 보게요.
  newtype N = N Bool
 
  data    D = D !Bool

이 예시들은 data와 newtype으로 정의된 타입 사이의 패턴 매칭 차이를 보여줘요.

(\ (N True) -> True) ⊥ ⇒ ⊥
(\ (D True) -> True) ⊥ ⇒ ⊥
(\ ~(D True) -> True) ⊥ ⇒ True
  1. 추가 예시는 4.2.3절에서 찾을 수 있어요.

case 표현식의 최상위 패턴과 함수·패턴 바인딩의 최상위 패턴 집합은 0개 이상의 연관 가드를 가질 수 있어요. 가드의 문법과 의미론은 3.13절을 참고해요.

가드 의미론은 함수나 case 표현식의 엄격성 특성에 영향을 줘요. 특히, 그 외에는 기각 불가능했을 패턴이 가드 때문에 평가될 수 있어요. 예를 들어

f :: (Int,Int,Int) -> [Int] -> Int
 
f ~(x,y,z) [a] | (a == y) = 1

에서는 a와 y 둘 다 가드의 ==에 의해 평가될 거예요.

3.17.3 패턴 매칭의 형식적 의미론 (Formal Semantics of Pattern Matching)

case 표현식 이외의 모든 패턴 매칭 구성의 의미론은, 그 구성들을 case 표현식에 관련짓는 항등식을 제공함으로써 정의돼요. case 표현식 자체의 의미론은 다시 그림 3.1–3.3의 일련의 항등식으로 주어져요. 어떤 구현이든 이 항등식들이 성립하도록 동작해야 해요. 하지만 구현이 이 항등식들을 직접 사용할 것이라고 기대하지는 않아요. 그렇게 하면 상당히 비효율적인 코드가 생성되기 때문이에요.

(a) case e of { alts } = (\v -> case v of { alts }) e
where v is a new variable
(b) case v of { p 1 match1; … ; pn matchn }
= case v of { p1 match1 ;
_ -> … case v of {
pn matchn ;
_ -> error "No match" }…}
where each matchi has the form:
| gsi,1 -> ei,1 ; … ; | gsi,mi -> ei,mi where { declsi }
(c) case v of { p | gs1 -> e1 ; …
| gsn -> en where { decls }
_ -> e′ }
= case e′ of { y ->
case v of {
p -> let { decls } in
case () of {
() | gs1 -> e1;
_ -> … case () of {
() | gsn -> en;
_ -> y } … }
_ -> y }}
where y is a new variable
(d) case v of { ~p -> e; _ -> e′ }
= (\x1 … xn -> e ) (case v of { p-> x1 })… (case v of { p -> xn})
where x1,…,xn are all the variables in p
(e) case v of { x@p -> e; _ -> e′ }
= case v of { p -> ( \ x -> e ) v ; _ -> e′ }
(f) case v of { _ -> e; _ -> e′ } = e
(g) case v of { K p1…pn -> e; _ -> e′ }
= case v of {
K x1…xn -> case x1 of {
p1 -> … case xn of { pn -> e ; _ -> e′ } …
_ -> e′ }
_ -> e′ }
at least one of p1,…,pn is not a variable; x1,…,xn are new variables
(h) case v of { k -> e; _ -> e′ } = if (v==k) then e else e′
where k is a numeric, character, or string literal
(i) case v of { x -> e; _ -> e′ } = case v of { x -> e }
(j) case v of { x -> e } = ( \ x -> e ) v
(k) case N v of { N p -> e; _ -> e′ }
= case v of { p -> e; _ -> e′ }
where N is a newtype constructor
(l) case ⊥ of { N p -> e; _ -> e′ } = case ⊥ of { p -> e }
where N is a newtype constructor
(m) case v of { K { f1 = p1 , f2 = p2 , … } -> e ; _ -> e′ }
= case e′ of {
y ->
case v of {
K { f1 = p1 } ->
case v of { K { f2 = p2 , … } -> e ; _ -> y };
_ -> y }}
where f1, f2, … are fields of constructor K; y is a new variable
(n) case v of { K { f = p } -> e ; _ -> e′ }
= case v of {
K p1 … pn -> e ; _ -> e′ }
where pi is p if f labels the ith component of K, _ otherwise
(o) case v of { K {} -> e ; _ -> e′ }
= case v of {
K _… _ -> e ; _ -> e′ }
(p) case (K′ e1 … em) of { K x1 … xn -> e; _ -> e′ } = e′
where K and K′ are distinct data constructors of arity n and m, respectively
(q) case (K e1 … en) of { K x1 … xn -> e; _ -> e′ }
= (\x1 … xn -> e) e1 … en
where K is a data constructor of arity n
(r) case ⊥ of { K x1 … xn -> e; _ -> e′ } = ⊥
where K is a data constructor of arity n
(s) case () of { () | g1, …, gn -> e; _ -> e′ }
= case () of {
() | g1 -> … case () of {
() | gn -> e;
_ -> e′ } …
_ -> e′ }
where y is a new variable
(t) case () of { () | p <- e0 -> e; _ -> e′ }
= case e0 of { p -> e; _ -> e′ }
(u) case () of { () | let decls -> e; _ -> e′ }
= let decls in e
(v) case () of { () | e0 -> e; _ -> e′ }
= if e0 then e else e′

그림 3.1–3.3에서: e, e′, ei는 표현식이고, gi와 gsi는 각각 가드와 가드의 수열이며, p와 pi는 패턴이고, v, x, xi는 변수이며, K와 K′는 대수적 데이터 타입(data) 생성자(튜플 생성자 포함)이고, N은 newtype 생성자예요.

규칙 (b)는 가드가 실제로 포함되었는지와 무관하게 일반적인 소스 언어 case 표현식을 매칭해요. 가드가 쓰이지 않았다면 matchi 형태의 가드 gsi,j 자리에 True가 대입돼요. 이후의 항등식들은 결과 case 표현식을 점점 더 단순한 형태로 다듬어요.

그림 3.2의 규칙 (h)는 오버로딩된 연산자 ==를 포함해요. 오버로딩된 상수에 대한 패턴 매칭의 의미를 정의하는 것이 바로 이 규칙이에요.

이 항등식들은 모두 정적 의미를 보존해요. 규칙 (d), (e), (j), (q)는 let 대신 람다를 사용하는데, 이는 case가 묶은 변수가 단형적으로 타입이 매겨진다는 것을 나타내요(4.1.4절).

더 알아보기 (Learn more)