식
식 (Expressions)
Haskell로 "프로그래밍 작게(in the small)" 할 때의 핵심 축, 바로 식(expression)을 다루는 장이에요. 식의 문법부터 조건문·리스트·튜플·리스트 컴프리헨션·패턴 매칭까지, Haskell 코드를 이루는 모든 조각의 의미가 여기 정의돼요. 대부분의 구문은 더 단순한 Haskell 커널로의 번역(translation)으로 설명되는데, 이 장이 바로 그 번역 규칙의 본고장이에요.
본문
이 장에서는 Haskell 식의 문법과 비형식적 의미론, 그리고 적절한 곳에서 Haskell 커널로의 번역을 설명해요. let 식의 경우를 빼면, 이런 번역은 정적·동적 의미론을 모두 보존해요. 번역에서 쓰는 자유 변수와 생성자는 항상 Prelude가 정의한 개체를 가리켜요. 예를 들어 리스트 컴프리헨션 번역(3.11절)에 쓰이는 concatMap은, 리스트 컴프리헨션이 쓰인 곳에서 식별자 concatMap이 스코프 안에 있는지(그리고 있다면 무엇에 바인딩돼 있는지)와 무관하게, 항상 Prelude가 정의한 concatMap을 의미해요.
exp → infixexp :: [context =>] type (expression type signature)
| infixexp
infixexp → lexp qop infixexp (infix operator application)
| - infixexp (prefix negation)
| lexp
lexp → \ apat1 … apatn -> exp (lambda abstraction, n ≥ 1)
| let decls in exp (let expression)
| if exp [;] then exp [;] else exp (conditional)
| case exp of { alts } (case expression)
| do { stmts } (do expression)
| fexp
fexp → [fexp] aexp (function application)
aexp → qvar (variable)
| gcon (general constructor)
| literal
| ( exp ) (parenthesized expression)
| ( exp1 , … , expk ) (tuple, k ≥ 2)
| [ exp1 , … , expk ] (list, k ≥ 1)
| [ exp1 [, exp2] .. [exp3] ] (arithmetic sequence)
| [ exp | qual1 , … , qualn ] (list comprehension, n ≥ 1)
| ( infixexp qop ) (left section)
| ( qop⟨-⟩ infixexp ) (right section)
| qcon { fbind1 , … , fbindn } (labeled construction, n ≥ 0)
| aexp⟨qcon⟩ { fbind1 , … , fbindn } (labeled update, 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에서 유일한 전위(prefix) 연산자예요. Prelude에 정의된 중위 - 연산자와 같은 우선순위를 가져요(4.4.2절, 그림 4.1).
문법은 람다 추상화·let 식·조건문의 범위(extent)에 대해 모호해요. 이 모호함은 각 구조가 가능한 한 오른쪽으로 멀리 확장된다는 메타 규칙(meta-rule)으로 해소돼요.
샘플 파싱은 아래와 같아요:
This Parses as
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)
명확성을 위해, 이 절의 나머지는 중위 연산자를 포함하는 식이 연산자의 fixity에 따라 이미 해소된 것으로 가정해요.
3.1 오류 (Errors)
식 평가 중의 오류, 즉 ⊥("바텀, bottom")로 표시되는 오류는, Haskell 프로그램에서 비종료(non-termination)와 구별할 수 없어요. Haskell은 비엄격(non-strict) 언어이기 때문에 모든 Haskell 타입이 ⊥를 포함해요. 즉 어떤 타입의 값이라도, 요구(demanded)될 때 오류를 결과로 내는 계산에 바인딩될 수 있어요. 오류는 평가될 때 즉시 프로그램 종료를 일으키며 사용자가 잡을 수 없어요. Prelude는 이런 오류를 직접 일으키는 두 함수를 제공해요:
error :: String -> a
undefined :: a
error를 호출하면 프로그램 실행이 종료되고 적절한 오류 표시를 운영 체제에 돌려줘요. 또한 시스템 의존적 방식으로 그 문자열을 표시해야 해요. undefined가 쓰일 때 오류 메시지는 컴파일러가 만들어요.
Haskell 식의 번역은 실행 시 오류가 발생할 수 있는 지점을 명시적으로 가리키기 위해 error와 undefined를 써요. 오류가 발생했을 때의 실제 프로그램 동작은 구현에 달려 있어요. 이런 번역에서 error 함수에 전달되는 메시지는 그저 제안일 뿐이에요. 구현체는 오류 발생 시 더 많거나 더 적은 정보를 표시하기로 선택할 수 있어요.
3.2 변수, 생성자, 연산자, 리터럴 (Variables, Constructors, Operators, and Literals)
aexp → qvar (variable)
| gcon (general constructor)
| literal
gcon → ()
| []
| (,{,})
| qcon
var → varid | ( varsym ) (variable)
qvar → qvarid | ( qvarsym ) (qualified variable)
con → conid | ( consym ) (constructor)
qcon → qconid | ( gconsym ) (qualified constructor)
varop → varsym | ` varid ` (variable operator)
qvarop→ qvarsym | ` qvarid ` (qualified variable operator)
conop → consym | ` conid ` (constructor operator)
qconop→ gconsym | ` qconid ` (qualified constructor operator)
op → varop | conop (operator)
qop → qvarop | qconop (qualified operator)
gconsym → : | qconsym
Haskell은 중위 표기를 지원하는 특별한 문법을 제공해요. 연산자(operator)는 중위 문법(3.4절)으로 적용하거나 섹션(3.5절)으로 부분 적용할 수 있는 함수예요.
연산자는 +나 $$ 같은 연산자 기호이거나, `op`처럼 그레이브 액센트(backquote)로 감싼 일반 식별자예요. 예를 들어 전위 적용 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라이브러리에 정의된 대로 두 정수로 rational을 만드는 함수예요. 정수n과d는n∕d = f가 되도록 고른 값이에요.
3.3 커리 적용과 람다 추상화 (Curried Applications and Lambda Abstractions)
fexp → [fexp] aexp (function application)
lexp → \ apat1 … apatn -> exp (lambda abstraction, 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 (prefix negation)
| lexp
qop → qvarop | qconop (qualified operator)
형태 e1 qop e2는 이항 연산자 qop를 식 e1과 e2에 중위 적용한 거예요. 특수 형태 -e는 전위 부정, Haskell의 유일한 전위 연산자를 나타내고, negate (e)의 문법이에요. 이항 - 연산자는 반드시 Prelude의 - 정의를 가리키는 건 아니에요. 모듈 시스템으로 다시 바인딩될 수 있어요. 그러나 단항 -는 항상 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 ) (left section)
| ( qop⟨-⟩ infixexp ) (right section)
섹션(section)은 ( op e )나 ( e op )로 써요. 여기서 op는 이항 연산자, e는 식이에요. 섹션은 이항 연산자의 부분 적용을 위한 편리한 문법이에요.
섹션에는 다음과 같이 구문 우선순위 규칙이 적용돼요. (op e)는 (x op e)가 (x op (e))와 같은 방식으로 파싱될 때에만 유효해요. (e op)도 마찬가지예요. 예를 들어 (*a+b)는 구문적으로 유효하지 않지만, (+a*b)와 (*(a+b))는 유효해요. +가 좌결합이므로 (a+b+)는 구문적으로 맞지만 (+a+b)는 아니에요. 후자는 (+(a+b))로 쓸 수 있어요. 또 다른 예로, 식:
(let n = 10 in n +)
은 유효하지 않아요. let/lambda 메타 규칙(3절) 때문에, 식:
(let n = 10 in n + x)
는 다음과 같이 파싱되기 때문이에요:
(let n = 10 in (n + x))
다음처럼이 아니라요:
((let n = 10 in n) + x)
-는 문법에서 특별히 취급되므로, (- exp)는 섹션이 아니라 전위 부정의 적용이에요(앞 절에서 설명). 다만 Prelude에 subtract 함수가 정의돼 있어서 (subtract exp)가 허용되지 않는 섹션과 동등해요. (+ (- 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의 값을, e1이 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장 9.1절).
번역: 다음 항등식이 성립해요:
[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 tuple)"로 생각할 수 있어요(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 ] (list comprehension, n ≥ 1)
qual → pat <- exp (generator)
| let decls (local declaration)
| exp (boolean guard)
리스트 컴프리헨션은 형태 [ e | q1, …, qn ], n ≥ 1이에요. 여기서 qi 한정자(qualifier)들은 다음 중 하나예요:
- 생성자(generator):
p <- e형태.p는 타입t의 패턴(3.17절),e는 타입[t]의 식. - 지역 바인딩(local binding): 생성된 식
e나 이후의 부울 가드·생성자에서 쓸 새 정의를 제공. - 부울 가드(boolean guard): 타입
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으로 바인딩된 변수는 완전 다형성(fully polymorphic) 타입을 가지는 반면, <-로 정의된 변수는 람다 바인딩이라 단형성(monomorphic)이에요(4.5.4절).
3.12 let 식 (Let Expressions)
lexp → let decls in exp
let 식은 일반적인 형태 let { d1 ; … ; dn } in e를 가지며, 중첩·어휘 스코프·상호 재귀적인 선언 리스트를 도입해요(let은 다른 언어에서 종종 letrec이라 불려요). 선언의 스코프는 식 e와 선언들의 오른쪽 변이에요. 선언은 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 (p의 어떤 변수도 e1에 자유로 나타나지 않을 때)
let p = e1 in e0 = let p = fix ( \ ~p -> e1) in e0
여기서 fix는 최소 고정점(minimum fixpoint) 연산자예요. 불반박 패턴 ~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]
| (empty alternative)
gdpat → guards -> exp [ gdpat ]
guards→ | guard1, …, guardn (n ≥ 1)
guard → pat <- infixexp (pattern guard)
| let decls (local declaration)
| infixexp (boolean guard)
case 식은 일반적인 형태를 가져요:
case e of { p1 match1 ; … ; pn matchn }
여기서 각 matchi는 일반적인 형태:
| gsi1 -> ei1
…
| gsimi -> eimi
where declsi
(가드의 문법 규칙에서 |는 종단 기호(terminal)이지, 택일을 뜻하는 구문 메타기호가 아니라는 점을 유의해요.) 각 대안 pi matchi는 패턴 pi와 그 매치들 matchi로 이뤄져요. 각 매치는 차례로 가드 gsij와 본문 eij(식들)의 쌍들의 시퀀스, 그리고 그 대안의 모든 가드·식에 스코프되는 선택적 바인딩(declsi)으로 이뤄져요.
가드(guard)는 다음 형태 중 하나를 가져요:
- **패턴 가드(pattern guard)**는
p <- e형태. 여기서p는 타입t의 패턴(3.17절),e는 타입t1의 식. 식e가 패턴p와 매칭되면 성공하고, 패턴의 바인딩을 환경에 도입해요. - **지역 바인딩(local binding)**은
let decls형태. 항상 성공하고,decls에 정의된 이름을 환경에 도입해요. - **부울 가드(boolean guard)**는 타입
Bool의 임의의 식. 식이True로 평가되면 성공하고, 환경에 새 이름을 도입하지 않아요. 부울 가드g는 의미론적으로 패턴 가드True <- g와 동등해요.
형태 pat -> exp where decls의 대안은 다음의 약어로 취급돼요:
pat | True -> exp
where decls
case 식은 적어도 하나의 대안을 가져야 하고 각 대안은 적어도 하나의 본문을 가져야 해요. 각 본문은 같은 타입이어야 하고, 전체 식의 타입이 그 타입이에요.
case 식은 식 e를 개별 대안들에 대해 패턴 매칭함으로써 평가돼요. 대안들은 위에서 아래로 순차적으로 시도돼요. e가 어떤 대안의 패턴과 매칭되면, 그 대안의 가드 식들이 위에서 아래로 순차적으로 시도돼요. 이때 환경은 case 식의 환경에, 먼저 패턴 매칭 동안 만들어진 바인딩을 추가하고, 이어 그 대안과 연관된 where 절의 declsi를 추가한 확장이에요.
각 가드 식에 대해, 콤마로 구분된 가드들은 왼쪽에서 오른쪽으로 순차적으로 시도돼요. 전부 성공하면 대응하는 식이, 가드들이 도입한 바인딩으로 확장된 환경에서 평가돼요. 즉 let 절이나 패턴 가드로 도입된 바인딩은 그 뒤의 가드들과 대응 식에 스코프돼요. 가드 중 하나라도 실패하면 이 가드 식은 실패하고 다음 가드 식이 시도돼요.
한 대안의 가드 식이 하나도 성공하지 못하면 매칭은 다음 대안으로 계속돼요. 어떤 대안도 성공하지 못하면 결과는 ⊥예요. 패턴 매칭은 3.17절에서, case 식의 형식적 의미론은 3.17.3절에서 설명해요.
파싱에 관한 메모. 식:
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 expression)
stmts → stmt1 … stmtn exp [;] (n ≥ 0)
stmt → exp ;
| pat <- exp ;
| let decls ;
| ; (empty statement)
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 function)로 쓰여요. 변수로 쓰일 때 필드 레이블은 객체에서 필드를 추출하는 함수 역할을 해요. 선택자는 최상위 바인딩이므로 지역 변수로 가릴(shadow) 수 있지만, 같은 이름의 다른 최상위 바인딩과 충돌할 수 없어요. 이 가림은 선택자 함수에만 영향을 줘요. 레코드 구성(3.15.2)·갱신(3.15.3)에서 필드 레이블은 일반 변수와 혼동될 수 없어요.
번역: 필드 레이블 f는 다음과 같이 정의된 선택자 함수를 도입해요:
f x = case x of { C1 p11 … p1k -> e1 ; … ; Cn pn1 … pnk -> en }
여기서 C1 … Cn은 f 레이블이 붙은 필드를 포함하는 데이터타입의 모든 생성자, pij는 f가 Ci의 j번째 성분에 레이블되면 y, 아니면 _, ei는 Ci의 어떤 필드가 레이블 f를 가질 때 y, 아니면 undefined예요.
3.15.2 필드 레이블을 쓴 구성 (Construction Using Field Labels)
aexp → qcon { fbind1 , … , fbindn } (labeled construction, n ≥ 0)
fbind → qvar = exp
레이블 필드를 가진 생성자는, 위치가 아니라 이름으로 성분을 지정해 값을 구성하는 데 쓰일 수 있어요. 선언 리스트에 쓰이는 중괄호와 달리 이 중괄호는 레이아웃의 적용을 받지 않아요. {와 } 문자는 명시적이어야 해요. (필드 갱신·필드 패턴도 마찬가지예요.) 필드 레이블을 쓴 구성은 다음 제약을 받아요:
- 지정된 생성자로 선언된 필드 레이블만 언급될 수 있어요.
- 필드 레이블은 두 번 이상 언급될 수 없어요.
- 언급되지 않은 필드는 ⊥로 초기화돼요.
- 엄격(strict) 필드(선언된 타입이
!로 접두되는 필드)를 구성 중 생략하면 컴파일 시 오류가 나요. 엄격 필드는 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 } (labeled update, n ≥ 1)
필드 레이블을 가진 데이터타입에 속하는 값은 비파괴적으로(non-destructively) 갱신될 수 있어요. 이는 지정된 필드 값이 기존 값의 그것을 대체하는 새 값을 만드는 거예요. 갱신은 다음 방식으로 제한돼요:
- 모든 레이블은 같은 데이터타입에서 가져와야 해요.
- 적어도 하나의 생성자가 갱신에서 언급된 모든 레이블을 정의해야 해요.
- 어떤 레이블도 두 번 이상 언급될 수 없어요.
- 갱신되는 값이 지정된 레이블을 모두 포함하지 않으면 실행 오류가 나요.
번역: 앞선 pick의 정의를 사용해:
e { bs } = case e of
C1 v1 … vk1 -> C1 (pick1C1 bs v1) … (pickk1C1 bs vk1)
...
Cj v1 … vkj -> Cj (pick1Cj bs v1) … (pickkjCj bs vkj)
_ -> 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
필드 f1은 T의 두 생성자에 공통이에요. 이 예는 필드 레이블 표기의 생성자를 쓰는 식을, 같은 생성자를 필드 레이블 없이 쓰는 동등한 식으로 번역해요. 갱신에 쓰인 필드 레이블 집합을 정의하는 생성자가 하나도 없으면(예: x {f2 = 1, f3 = 'x'}) 컴파일 시 오류가 나요.
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 (infix constructor)
| lpat
lpat → apat
| - (integer | float) (negative literal)
| gcon apat1 … apatk (arity gcon = k, k ≥ 1)
apat → var [ @ apat] (as pattern)
| gcon (arity gcon = 0)
| qcon { fpat1 , … , fpatk } (labeled pattern, k ≥ 0)
| literal
| _ (wildcard)
| ( pat ) (parenthesized pattern)
| ( pat1 , … , patk ) (tuple pattern, k ≥ 2)
| [ pat1 , … , patk ] (list pattern, k ≥ 1)
| ~ apat (irrefutable pattern)
fpat → qvar = pat
생성자의 항수는 연관된 하위 패턴(sub-pattern)의 개수와 일치해야 해요. 부분 적용된 생성자에는 매칭할 수 없어요.
모든 패턴은 선형이어야 해요 — 어떤 변수도 두 번 이상 나타나면 안 돼요. 예를 들어 이 정의는 불법이에요:
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 }
_ 형태의 패턴은 **와일드카드(wildcard)**예요. 패턴의 어떤 부분이 오른쪽 변에서 참조되지 않을 때 유용해요. 마치 다른 곳에서 쓰이지 않는 식별자가 그 자리에 놓인 것과 같아요. 예:
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)
패턴은 값에 대해 매칭돼요. 패턴을 매칭하려는 시도는 세 결과 중 하나를 가질 수 있어요: 실패하거나, 패턴의 각 변수에 대한 바인딩을 돌려주며 성공하거나, 발산(즉 ⊥ 반환)할 수 있어요. 패턴 매칭은 왼쪽에서 오른쪽으로, 바깥에서 안쪽으로 다음 규칙에 따라 진행돼요:
- 패턴
var를 값v에 매칭하는 것은 항상 성공하고var를v에 바인딩해요. - 패턴
~apat를 값v에 매칭하는 것은 항상 성공해요.apat의 자유 변수는,apat를v에 매칭하는 것이 그렇지 않으면 성공할 때 적절한 값에,apat를v에 매칭하는 것이 실패하거나 발산하면 ⊥에 바인딩돼요. (바인딩은 평가를 의미하지 않아요.)- 작동적으로 이는
~apat패턴에서는apat의 변수 중 하나가 사용될 때까지 어떤 매칭도 수행되지 않음을 의미해요. 그 시점에 전체 패턴이 값에 대해 매칭되고, 매칭이 실패하거나 발산하면 전체 계산도 그렇게 돼요.
- 작동적으로 이는
- 와일드카드 패턴
_를 어떤 값에 매칭하는 것은 항상 성공하고 바인딩은 수행되지 않아요. newtype으로 정의된 생성자con인 패턴con pat를 값에 매칭하는 것은 값에 따라 달라져요:- 값이
con v형태면pat가v에 매칭돼요. - 값이 ⊥면
pat가 ⊥에 매칭돼요. - 즉
newtype과 연관된 생성자는 값의 타입을 바꾸는 역할만 해요.
- 값이
data로 정의된 생성자con인 패턴con pat1 … patn를 값에 매칭하는 것은 값에 따라 달라져요:- 값이
con v1 … vn형태면 하위 패턴들이 데이터 값의 성분에 대해 왼쪽에서 오른쪽으로 매칭돼요. 모두 성공하면 전체 매칭이 성공하고, 처음 실패하거나 발산하는 것이 전체 매칭을 각각 실패시키거나 발산시켜요. - 값이
con′ v1 … vm형태이고con이con′와 다른 생성자면 매칭이 실패해요. - 값이 ⊥면 매칭이 발산해요.
- 값이
- 레이블 필드를 쓰는 생성자에 매칭하는 것은, 필드가 필드 리스트에서 이름이 붙은 순서로 매칭된다는 점을 빼면 일반 생성자 패턴 매칭과 같아요. 나열된 모든 필드는 생성자가 선언한 것이어야 하고, 필드는 두 번 이상 이름 붙여질 수 없어요. 패턴이 이름 붙이지 않은 필드는 무시돼요(즉
_에 매칭). - 숫자·문자·문자열 리터럴 패턴
k를 값v에 매칭하는 것은v == k일 때 성공해요. 여기서==는 패턴의 타입에 기반해 오버로드돼요. 이 검사가 발산하면 매칭도 발산해요.- 숫자 리터럴의 해석은 3.2절에서 설명한 것과 정확히 같아요. 즉 오버로드된 함수
fromInteger나fromRational이Integer나Rational리터럴에 적용되어 적절한 타입으로 변환돼요.
- 숫자 리터럴의 해석은 3.2절에서 설명한 것과 정확히 같아요. 즉 오버로드된 함수
- as-패턴
var@apat를 값v에 매칭하는 것은apat를v에 매칭한 결과에var를v에 바인딩하는 것을 더한 것이에요.apat의v에 대한 매칭이 실패하거나 발산하면 전체 매칭도 그러해요.
명백한 정적 타입 제약(예: 문자를 부울에 매칭하는 것은 정적 오류) 외에도 다음 정적 클래스 제약이 성립해요:
- 정수 리터럴 패턴은
Num클래스의 값에만 매칭할 수 있어요. - 부동소수점 리터럴 패턴은
Fractional클래스의 값에만 매칭할 수 있어요.
때로 두 종류의 패턴을 구분하는 것이 유용해요. **불반박 패턴(irrefutable pattern)**을 매칭하는 것은 비엄격(non-strict)이에요: 매칭할 값이 ⊥여도 패턴이 매칭돼요. **반박 패턴(refutable pattern)**을 매칭하는 것은 엄격이에요: 매칭할 값이 ⊥면 매칭이 발산해요. 불반박 패턴은 다음과 같아요: 변수, 와일드카드, N apat(여기서 N은 newtype으로 정의된 생성자이고 apat는 불반박, 4.2.3절), var@apat(여기서 apat는 불반박), ~apat 형태(파악 apat가 불반박인지와 무관). 다른 모든 패턴은 반박이에요.
여기 몇 가지 예시가 있어요:
- 패턴
['a','b']를['x',⊥]에 매칭하면'a'가'x'에 매칭에 실패하고 결과는 매칭 실패예요. 그러나['a','b']를[⊥,'x']에 매칭하면'a'를 ⊥에 매칭하려는 시도가 매칭을 발산시켜요.
이 예시들은 반박 대 불반박 매칭을 보여줘요:
(\ ~(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) ⊥ ⇒ ⊥:⊥:⊥
다음 선언들을 고려해 보죠:
newtype N = N Bool
data D = D !Bool
이 예시들은 data와 newtype으로 정의된 타입 사이의 패턴 매칭 차이를 보여줘요:
(\ (N True) -> True) ⊥ ⇒ ⊥
(\ (D True) -> True) ⊥ ⇒ ⊥
(\ ~(D True) -> True) ⊥ ⇒ True
추가 예시는 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에 주어져요. 어떤 구현도 이 항등식들이 성립하도록 동작해야 해요. 이것들을 직접 쓰리라고 기대되진 않는데, 그러면 꽤 비효율적인 코드를 만들 테니까요.
그림 3.1: Case 식의 의미론, 1부
(a) case e of { alts } = (\v -> case v of { alts }) e
where v is a new variable
(b) case v of { p1 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
그림 3.2: Case 식의 의미론, 2부
(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
그림 3.3: Case 식의 의미론, 3부
(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)
- 4장 선언과 바인딩 (Declarations and Bindings) — fixity 선언과 타입 클래스 등 식이 쓰는 선언들을 다뤄요.
- 6장 미리 정의된 타입과 클래스 (Predefined Types and Classes) —
Num,Enum,Monad등 식 번역이 의존하는 클래스들이 여기 있어요. - 10장 구문 참조 (Syntax Reference) — 10.6절에서 중위 연산자 해석 알고리즘을 봐요.