17패턴 매칭

패턴 매칭은 값이 특정한 형태를 갖추었는지 검사하고, 검사에 성공하면 필요한 부분에 이름을 붙입니다. tag를 확인한 다음 payload를 꺼내는 두 단계를 하나로 합치므로, tag가 다른 값에서 payload를 읽는 실수가 원천적으로 생기지 않습니다. 구조체, tagged union, 튜플, 리터럴에 사용할 수 있습니다. 이 장은 BSV Language Reference Guide 제11장을 따라 상수·패턴 변수·와일드카드, 구조체와 tagged union 패턴의 중첩, &&& 필터가 붙는 case ... matches, if 조건과 rule 조건 안의 패턴 검사, match 선언을 다룹니다.

먼저 알아 두면 좋은 것. 사용자 정의 타입 장의 구조체, tagged union, 튜플과 선택·case·don't-care 값 장의 일반 case, if를 알고 있어야 합니다. Bool·Bit와 순수 함수 장에서 배운 비트 선택은 이 장의 필터에서 다시 사용합니다.

이 장의 동작은 모두 조합 논리입니다. case ... matches는 사용되는 사이클에 평가되는 비교기와 멀티플렉서로 합성되며 상태를 만들지 않습니다.

1. 패턴의 구성 요소

1.1 말단의 세 종류

패턴은 검사할 값과 같은 모양으로 씁니다. 패턴의 말단에는 다음 세 가지가 옵니다.

형식

식 matches 패턴

if (packet matches tagged Data .request)
  $display("payload %h", request.payload);

1.2 패턴 변수의 규칙

• 타입은 위치가 정합니다. Bit#(8) 필드 위치의 .value는 타입이 Bit#(8)입니다. 따로 선언하지 않습니다.
• 한 패턴 안의 이름은 서로 달라야 합니다. 같은 이름이 두 번 나오면 두 값이 같은지 검사하는 것처럼 보이지만, 패턴은 그런 검사를 하지 않습니다.
• 이름은 매칭이 성공한 범위에서만 존재합니다. 선택된 case 항목, 또는 매칭에 성공한 if의 then 분기가 그 범위입니다.

주의. 현재 bsc는 이름이 겹치는지 모든 위치에서 검사하지는 않습니다. match {.a, .a} = t;는 컴파일되며 a에는 두 번째 원소가 조용히 결합됩니다. 이름이 겹치지 않게 직접 관리하세요.

1.3 ? 자리가 있는 리터럴 패턴

Bit#(n) 값에 리터럴 패턴을 쓰면 비트 단위로 비교합니다. 리터럴 안의 ? 자리는 0과 1 어느 쪽과도 일치합니다.

case (instruction) matches
  8'b1010_????: return 1;   // 상위 4비트가 1010인 모든 바이트
  default: return 0;
endcase

2. 구조체 패턴과 tagged union 패턴

2.1 tagged union 패턴

tagged union 패턴은 먼저 활성 tag를 검사합니다. tag가 일치할 때만 안쪽 패턴을 payload에 적용합니다.

형식

tagged 멤버_이름
tagged 멤버_이름 패턴

아래의 Flush처럼 payload가 void인 멤버는 tag만으로 매칭합니다.

2.2 구조체 패턴

구조체 패턴은 검사하거나 결합할 필드만 이름으로 적습니다. 필드 순서는 결과와 관계가 없고, 적지 않은 필드는 검사하지 않습니다.

형식

구조체_이름 { 필드1: 패턴1, 필드2: 패턴2 }

tagged Data (Request { payload: .value })   // payload만 결합합니다
tagged Data (Request { channel: 1, payload: .value })   // channel이 1이어야 합니다

중첩은 타입 구조를 그대로 따릅니다. 바깥 패턴이 tag를 검사하고 안쪽 패턴이 payload 내부를 검사합니다.

2.3 예제: 바깥 tag에서 안쪽 필드까지

NestedPattern.bsv의 Packet은 Request 구조체를 담은 Data이거나 아무것도 담지 않은 Flush입니다. 두 타입을 먼저 읽고 payloadOrZero의 두 항목을 읽으세요.

mkTop이 만드는 값은 Request { channel: 2, payload: 8'ha5 }입니다.

1. tagged Data request가 case에 들어옵니다. 첫 항목의 tag 검사는 Data이므로 성공합니다. 이어서 payload가 Request 구조체인지 검사하고 성공합니다. 필드 목록에는 payload만 있으므로 value에 8'ha5가 결합되고 channel은 검사하지 않습니다. 첫 항목은 8'ha5를 반환합니다.
2. tagged Flush는 첫 항목의 tag 검사에서 실패하므로 payload는 검사 대상이 되지 않습니다. 두 번째 항목이 Flush와 일치하여 0을 반환합니다.

실행하기 전에 예측해 보세요.

1. 출력될 16진수 값 두 개는 무엇일까요?
2. channel 값 2가 두 결과 가운데 어느 쪽에 영향을 줄까요?

package NestedPattern;

typedef struct {
  Bit#(2) channel;
  Bit#(8) payload;
} Request deriving (Bits, Eq, FShow);

typedef union tagged {
  Request Data;
  void Flush;
} Packet deriving (Bits, Eq, FShow);

function Bit#(8) payloadOrZero(Packet packet);
  // 중첩된 구조체 패턴이 함수에 필요한 필드만 결합한다.
  case (packet) matches
    tagged Data (Request { payload: .value }): return value;
    tagged Flush: return 0;
  endcase
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    Request request = Request { channel: 2, payload: 8'ha5 };
    $display("data=%02h flush=%02h",
             payloadOrZero(tagged Data request),
             payloadOrZero(tagged Flush));
    $finish(0);
  endrule
endmodule

endpackage

결과 확인.

직접 바꿔 보세요.

1. 첫 패턴을 Request { channel: 1, payload: .value }로 바꾸어 보세요. 요청의 channel은 2이므로 Data 패킷은 두 항목 어느 쪽과도 일치하지 않습니다. 출력되는 바이트가 0이라는 보장은 없습니다. 일치하는 항목이 없는 case를 지나 함수가 끝나지만 bsc는 이를 오류로 처리하지 않고, 결과는 컴파일러가 선택한 정해지지 않은 값입니다. default: return 0; 항목을 추가하면 결과가 정해집니다.

2. .value를 .*로 바꾸고 상수를 반환하게 해 보세요. 패턴은 여전히 tag와 구조체를 검사하지만 이름은 결합하지 않습니다.

3. 패턴 매칭 case

3.1 case ... matches와 처음 일치한 항목

case (식) matches의 각 항목은 패턴입니다. 항목을 위에서부터 차례로 검사하고 처음 일치한 항목을 선택합니다.

형식

case (식) matches
  패턴1: 문장
  패턴2 &&& 조건: 문장
  default: 문장
endcase

3.2 &&& 필터

&&& 뒤의 필터는 패턴이 이미 일치한 경우에만 평가됩니다. 그래서 패턴이 결합한 이름과 원래 식을 필터에서 쓸 수 있습니다. 필터가 거짓이면 다음 항목으로 넘어가 검사를 계속합니다.

패턴은 서로 겹칠 수 있으므로 항목 순서가 결과를 바꿉니다. 세부 조건이 있는 항목은 같은 값을 받아들이는 넓은 항목보다 위에 두세요. 넓은 항목이 위에 있으면 그 값을 먼저 가져가므로 세부 항목은 실행되지 않습니다.

3.3 예제: 패턴 성공과 필터 실패의 구분

FilteredCase.bsv는 명령어 바이트를 해석합니다. 필터가 붙은 항목, default 항목, show의 세 호출 순서로 읽으세요. 리터럴 8'b1010_????는 상위 4비트를 1010으로 고정하고 하위 4비트는 무시합니다.

실행하기 전에 예측해 보세요.

1. small, large, other 가운데 필터 항목에서 나오는 값은 어느 것일까요?
2. large와 other는 같은 수를 출력합니다. 두 값이 0이 된 이유는 어떻게 다를까요?

package FilteredCase;

function Bit#(4) decodeSmall(Bit#(8) instruction);
  // 상위 비트가 1010인 모든 명령어가 이 리터럴 패턴과 일치한다.
  case (instruction) matches
    // 필터는 리터럴 패턴이 일치한 뒤에만 평가된다.
    8'b1010_???? &&& (instruction[3:0] < 10): return instruction[3:0];
    default: return 0;
  endcase
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    $display("small=%0d large=%0d other=%0d",
             decodeSmall(8'ha7), decodeSmall(8'hac), decodeSmall(8'h37));
    $finish(0);
  endrule
endmodule

endpackage

결과 확인. 필터 항목에서 나온 값은 small=7뿐입니다. large=0은 패턴은 일치했지만 필터가 거부한 결과이고, other=0은 패턴 자체가 실패한 결과입니다. 출력만으로는 두 0을 구분할 수 없으므로 위와 같은 추적 표를 적어 두세요.

직접 바꿔 보세요.

1. 필터의 경계를 10에서 13으로 바꾸어 보세요. 선택 항목이 바뀌는 입력은 8'hac 하나이므로 large는 12가 되고 small과 other는 7과 0 그대로입니다.
2. 경계는 10으로 두고, 필터 항목 위에 넓은 항목 8'b1010_????: return 4'hf;를 추가해 보세요. 8'ha7과 8'hac가 모두 넓은 항목에서 멈추어 15를 출력하므로 필터 항목은 가려집니다. 넓은 항목을 필터 항목 아래로 옮기면 small=7이 복구되고 8'hac만 15를 출력합니다.

3.4 case 식

패턴 매칭 case는 값을 만드는 식으로도 쓸 수 있습니다. 이때 각 항목은 문장 대신 식으로 끝납니다.

Bit#(8) size = case (packet) matches
                 tagged Data .request: request.payload;
                 tagged Flush: 0;
               endcase;

두 형태 모두 항목이 모든 입력을 처리하는지 검사하지 않습니다. 중첩 패턴 예제의 변형에서 본 것처럼 bsc는 불완전한 항목 집합을 그대로 컴파일하고, 일치하는 항목이 없으면 정해지지 않은 값을 만듭니다. 모든 case의 끝에 default를 두거나, 모든 멤버를 처리하는 항목을 두세요.

아래 함수를 읽고 결과가 정해지지 않는 입력을 찾아 보세요.

typedef union tagged { void Idle; Bit#(8) Load; Bit#(8) Store; } Op deriving (Bits, Eq);

function Bit#(8) opData(Op op);
  case (op) matches
    tagged Idle: return 0;
    tagged Load .v: return v;
  endcase
endfunction

4. 조건 안의 패턴 검사

4.1 if와 rule 조건의 matches

if 문, 조건 식, rule 조건, method 조건에는 패턴 검사를 쓸 수 있고, 그 뒤에 &&&로 조건을 더 이을 수 있습니다.

형식

if (식 matches 패턴 &&& 조건) 문장
rule 이름 (식 matches 패턴 &&& 조건);

if (request matches tagged Write .address &&& address < 16)
  accept(address);

&&&로 이은 항은 왼쪽부터 평가하며, 앞의 항이 모두 성공해야 다음 항을 평가합니다. address < 16을 평가하는 시점에는 tag가 Write로 확인되었고 address에 값이 결합되어 있습니다. 결합된 이름은 then 분기에서 쓸 수 있지만, 매칭이 실패했을 수 있는 else 분기에서는 쓸 수 없습니다. else에서 쓰면 T0004("Unbound variable") 오류가 발생합니다.

4.2 &&로 &&&를 대신할 수 없는 이유

일반 &&는 이미 존재하는 Bool 값 두 개를 결합합니다. 오른쪽 식에 패턴 변수를 제공할 방법이 없습니다. 문법도 이를 막습니다. matches 패턴 바로 뒤에 &&를 쓰면 구문 오류 P0005가 발생하고, bsc는 &&&나 )가 와야 할 위치라고 보고합니다. &&& 뒤의 필터 안에서는 일반 &&를 써도 됩니다.

5. match 선언

5.1 형태가 정해진 값 분해하기

match 패턴 = 식;은 패턴의 변수를 같은 블록의 이후 문장에서 쓸 수 있게 결합합니다. 튜플과 구조체처럼 타입이 형태를 보장하는 값에 사용합니다. 고를 분기가 없으므로 case를 쓰면 코드만 길어집니다.

형식

match 패턴 = 식;

match {.quotient, .remainder} = divide(a, b);   // 튜플: 위치로 결합
match Pair { lo: .x, hi: .y } = p;              // 구조체: 필드 이름으로 결합

5.2 예제: 위치에 따른 결합

MatchAssignment.bsv는 Tuple2를 4비트 이름 두 개로 나눈 뒤 다시 연결합니다. fields의 타입, match 줄, 이어지는 연결 연산 순서로 읽으세요.

fields에는 tuple2(4'ha, 4'h5)가 전달됩니다. 패턴 {.upper, .lower}는 위치로 결합하므로 첫 번째 원소 4'ha가 upper에, 두 번째 원소 4'h5가 lower에 결합됩니다. 두 이름의 타입은 각 위치의 타입인 Bit#(4)입니다. { upper, lower }는 upper를 비트 7–4에 놓습니다.

실행하기 전에 예측해 보세요.

1. 출력되는 바이트는 무엇일까요?
2. 원소를 꺼내는 데 tpl_1이나 tpl_2가 필요했을까요?

package MatchAssignment;

function Bit#(8) joinFields(Tuple2#(Bit#(4), Bit#(4)) fields);
  // match 선언이 이후 문장에서 쓸 튜플 원소 두 개를 결합한다.
  match {.upper, .lower} = fields;
  return { upper, lower };
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    $display("joined=%02h", joinFields(tuple2(4'ha, 4'h5)));
    $finish(0);
  endrule
endmodule

endpackage

결과 확인. joined=a5는 첫 번째 원소가 상위 4비트에 놓였음을 확인해 줍니다. tpl_1이나 tpl_2를 호출하지 않았고, 두 이름은 다음 문장에서도 4비트 타입을 유지했습니다.

직접 바꿔 보세요.

1. 연결 연산은 그대로 두고 패턴의 이름만 {.lower, .upper}로 바꾸어 보세요. 결과는 5a가 됩니다. 튜플 패턴은 위치로 결합하므로 이름은 위치에 붙이는 표시일 뿐 원소를 찾는 열쇠가 아닙니다.
2. 비교를 위해 Pair { lo: .x, hi: .y } 같은 구조체 패턴을 생각해 보세요. 구조체 패턴은 필드 이름으로 결합하므로 항목 순서를 바꾸어도 결과가 같습니다.

6. 자주 하는 실수

6.1 넓은 항목을 세부 항목 위에 두기

// 잘못된 코드: 필터 항목에 도달하지 못합니다
8'b1010_????: return 4'hf;
8'b1010_???? &&& (instruction[3:0] < 10): return instruction[3:0];

// 바른 코드: 세부 항목을 먼저 둡니다
8'b1010_???? &&& (instruction[3:0] < 10): return instruction[3:0];
8'b1010_????: return 4'hf;

처음 일치한 항목이 선택됩니다. 넓은 항목이 위에 있으면 세부 항목이 처리해야 할 입력을 모두 가져가며, bsc는 경고하지 않습니다.

6.2 기본 항목 빠뜨리기

// 잘못된 코드: channel이 2인 Data 패킷은 어느 항목과도 일치하지 않습니다
case (packet) matches
  tagged Data (Request { channel: 1, payload: .value }): return value;
  tagged Flush: return 0;
endcase

// 바른 코드: 나머지 입력의 결과를 명시합니다
case (packet) matches
  tagged Data (Request { channel: 1, payload: .value }): return value;
  default: return 0;
endcase

입력 처리 범위는 검사되지 않습니다. 기본 항목이 없으면 일치하지 않는 입력의 결과가 정해지지 않습니다.

6.3 패턴 뒤에 && 쓰기

// 잘못된 코드: 구문 오류 P0005
if (request matches tagged Write .address && address < 16) ...

// 바른 코드: 매칭 뒤에 조건을 잇습니다
if (request matches tagged Write .address &&& address < 16) ...

address는 매칭이 성공한 뒤에야 존재하며, 그 시점을 기다리는 연산자는 &&&뿐입니다.

6.4 else에서 결합된 이름 쓰기

// 잘못된 코드: else에서는 address가 결합되지 않습니다(T0004)
if (request matches tagged Write .address) accept(address);
else log(address);

// 바른 코드: 그 경로에 존재하는 이름만 씁니다
if (request matches tagged Write .address) accept(address);
else log(0);

else 분기에서는 요청이 Write가 아닐 수 있으므로 address에 값이 없습니다.

6.5 한 패턴에서 같은 이름 다시 쓰기

// 잘못된 코드: 컴파일되지만 a에는 두 번째 원소가 들어갑니다
match {.a, .a} = pair;

// 바른 코드: 위치마다 이름 하나
match {.first, .second} = pair;

현재 bsc는 잘못된 코드를 받아들입니다. 뒤의 결합이 남고, 두 원소가 같은지는 검사하지 않습니다.

7. 정리

8. 확인 문제

1. payloadOrZero에서 channel 필드는 어떻게 처리되며, 와일드카드가 필요 없는 이유는 무엇일까요?

   정답 보기

   검사되지 않습니다. 구조체 패턴은 적은 필드만 검사하므로 channel을 적지 않는 것으로 충분합니다.

2. 필터 예제에서 0을 출력한 두 입력 가운데 패턴과 일치한 입력은 어느 쪽일까요?

   정답 보기

   8'hac입니다. 패턴 8'b1010_????와 일치했지만 필터 12 < 10이 거짓이었습니다. 8'h37은 패턴 자체가 실패했습니다. 두 입력 모두 그 뒤 default에 도달했습니다.

3. 넓은 항목은 필터 항목의 위와 아래 가운데 어디에 두어야 하며, 반대로 두면 어떻게 될까요?

   정답 보기

   아래에 두어야 합니다. 넓은 항목이 위에 있으면 필터 항목이 받아야 할 입력을 모두 먼저 처리하므로 필터 항목은 실행되지 않습니다.

4. &&& 뒤의 address < 16이 address를 쓸 수 있는 이유는 무엇이며, &&를 쓰면 어떻게 될까요?

   정답 보기

   &&&는 매칭이 성공하여 address가 결합된 뒤에 오른쪽을 평가합니다. &&를 쓰면 bsc가 &&&를 기대한다는 구문 오류 P0005로 중단됩니다.

5. case ... matches보다 match 선언이 알맞은 경우는 언제일까요?

   정답 보기

   튜플이나 구조체처럼 타입이 형태를 이미 보장하는 경우입니다. 고를 분기가 없으므로 선언으로 각 부분에 이름만 붙이면 됩니다.