Lean으로 배우는 함수형 프로그래밍

1.1. 표현식 평가🔗

Lean을 배우는 프로그래머가 이해해야 할 가장 중요한 것은 평가가 어떻게 이루어지는지입니다. 평가란 산술에서와 마찬가지로 표현식의 값을 구하는 과정입니다. 예를 들어, 15 - 6의 값은 9이고 2 × (3 + 1)의 값은 8입니다. 뒤의 표현식의 값을 구하려면 먼저 3 + 1을 4로 바꾸어 2 × 4를 얻고, 이는 다시 8로 간약될 수 있습니다. 때로는 수학적 표현식에 변수가 포함되기도 합니다. x + 1의 값은 x의 값이 무엇인지 알기 전까지는 계산할 수 없습니다. Lean에서 프로그램은 무엇보다도 표현식이며, 계산을 생각하는 주된 방식은 표현식을 평가하여 그 값을 구하는 것입니다.

대부분의 프로그래밍 언어는 명령형입니다. 명령형 언어에서 프로그램은 결과를 얻기 위해 순서대로 실행해야 하는 일련의 문장(statement)으로 이루어집니다. 프로그램은 변경 가능한 메모리에 접근할 수 있으므로, 변수가 가리키는 값은 시간이 지나면서 바뀔 수 있습니다. 가변 상태 외에도 프로그램에는 파일 삭제, 외부로 나가는 네트워크 연결 생성, 예외 발생 또는 처리, 데이터베이스에서 데이터 읽기와 같은 다른 부수 효과가 있을 수 있습니다. "부수 효과"는 본질적으로 프로그램에서 일어날 수 있는 일 중 수학적 표현식을 평가하는 모델을 따르지 않는 것들을 통틀어 가리키는 포괄적인 용어입니다.

그러나 Lean에서 프로그램은 수학적 표현식과 같은 방식으로 동작합니다. 변수에 한 번 값이 주어지면 다시 할당할 수 없습니다. 표현식을 평가해도 부수 효과가 발생할 수 없습니다. 두 표현식의 값이 같다면 한쪽을 다른 쪽으로 바꾸어도 프로그램이 다른 결과를 계산하지 않습니다. 그렇다고 Lean으로 콘솔에 Hello, world!를 출력할 수 없다는 뜻은 아니지만, Lean을 사용하는 경험에서 I/O 수행은 다른 언어에서만큼 핵심적인 부분이 아닙니다. 따라서 이 장에서는 Lean에서 표현식을 대화형으로 평가하는 방법을 중점적으로 다루고, 다음 장에서는 Hello, world! 프로그램을 작성하고 컴파일하고 실행하는 방법을 설명합니다.

Lean에게 표현식을 평가하도록 요청하려면 편집기에서 표현식 앞에 #eval을 작성하십시오. 그러면 편집기가 결과를 보고합니다. 일반적으로 결과는 커서나 마우스 포인터를 #eval 위에 올려 확인할 수 있습니다. 예를 들어,

3#eval 1 + 2

다음 값을 산출합니다.

3

Lean은 산술 연산자에 대해 일반적인 우선순위 및 결합성 규칙을 따릅니다. 즉,

11#eval 1 + 2 * 5

15가 아니라 11이라는 값을 산출합니다.

일반적인 수학 표기법과 대부분의 프로그래밍 언어는 함수를 인자에 적용할 때 괄호를 사용하지만(예: f(x)), Lean에서는 함수를 인자 옆에 나란히 쓰기만 하면 됩니다(예: f x). 함수 적용은 가장 흔히 쓰이는 연산 중 하나이므로 간결하게 표기하는 편이 유리합니다. 다음과 같이 쓰는 대신

#eval String.append("Hello, ", "Lean!")

"Hello, Lean!"을 계산하려면 대신 다음과 같이 작성합니다

"Hello, Lean!"#eval String.append "Hello, " "Lean!"

여기서 함수의 두 인자는 공백으로 구분하여 함수 바로 옆에 적기만 하면 됩니다.

산술의 연산 순서 규칙 때문에 표현식 (1 + 2) * 5에 괄호가 필요한 것처럼, 함수의 인자를 다른 함수 호출로 계산해야 할 때에도 괄호가 필요합니다. 예를 들어, 다음 식에서는 괄호가 필요합니다.

"great oak tree"#eval String.append "great " (String.append "oak " "tree")

그렇지 않으면 두 번째 String.append가 "oak "와 "tree"를 인자로 받는 함수가 아니라 첫 번째 함수의 인자로 해석되기 때문입니다. 안쪽 String.append 호출의 값을 먼저 구해야 하며, 그런 다음 그 값을 "great " 뒤에 이어 붙여 최종 값 "great oak tree"를 얻습니다.

명령형 언어에는 흔히 두 종류의 조건 구문이 있습니다. 불리언 값에 따라 어떤 명령을 실행할지 결정하는 조건 문과, 불리언 값에 따라 두 표현식 중 어느 것을 평가할지 결정하는 조건 표현식입니다. 예를 들어 C와 C++에서 조건문은 if와 else를 사용해 작성하고, 조건 표현식은 ?와 :가 조건과 분기를 구분하는 삼항 연산자로 작성합니다. Python에서 조건문은 if로 시작하고, 조건 표현식은 if를 가운데에 둡니다. Lean은 표현식 중심의 함수형 언어이므로 조건문은 없고 조건 표현식만 있습니다. 조건 표현식은 if, then, else를 사용해 작성합니다. 예를 들어,

String.append "it is " (if 1 > 2 then "yes" else "no")

다음으로 평가됩니다

String.append "it is " (if false then "yes" else "no")

이는 다음과 같이 평가됩니다

String.append "it is " "no"

이는 최종적으로 "it is no"로 평가됩니다.

간결하게 나타내기 위해, 이와 같은 일련의 평가 단계를 단계 사이에 화살표를 넣어 표기하기도 합니다:

String.append "it is " (if 1 > 2 then "yes" else "no")String.append "it is " (if false then "yes" else "no")String.append "it is " "no""it is no"

1.1.1. 마주칠 수 있는 메시지🔗

인자가 누락된 함수 적용을 Lean에게 평가하도록 요청하면 오류 메시지가 발생합니다. 특히, 다음 예제

Could not synthesize a `ToExpr`, `Repr`, or `ToString` instance for type String → String#eval String.append "it is "

꽤 긴 오류 메시지가 출력됩니다:

Could not synthesize a `ToExpr`, `Repr`, or `ToString` instance for type
  String → String

이 메시지가 나타나는 이유는 Lean 함수를 인자 중 일부에만 적용하면 나머지 인자를 기다리는 새로운 함수가 반환되기 때문입니다. Lean은 함수를 사용자에게 표시할 수 없으므로, 함수를 표시하라는 요청을 받으면 오류를 반환합니다.

1.1.2. 연습 문제🔗

다음 표현식의 값은 무엇입니까? 먼저 손으로 직접 계산해 본 다음, Lean에 입력하여 답이 맞는지 확인하십시오.