[PLT/프로그래밍언어론] 11. Functional Programming(1)

 

11. functional1

#PLT

함수형 프로그래밍 (Functional Programming)

프로그래밍 언어 이론 (Programming Language Theory)

목차 (Topics)

• 함수형 언어 기초 (Functional Language Fundamentals)
• 함수형 패러다임 개요 (Functional Paradigm Overview)
• 표현식 평가 (Expression Evaluation)
• Scala에서의 함수형 언어 주제 (Functional Language Topics in Scala)
• 블록과 스코프 (Blocks and Scope), 패턴 매칭 (Pattern Matching), 커링 (Currying)
• λ-계산 (λ - Calculus)

---

함수형 패러다임 개요 (Functional Paradigm Overview)

폰 노이만 머신 (von Neumann Machine)

• 헝가리계 미국인 수학자 존 폰 노이만(John von Neumann)이 개발함
• 그는 튜링 머신(Turing Machine)을 보고 이를 물리적 기계로 구현할 수 있다고 생각함
• 이 기계의 계산 모델은 상태 변환(state transformation)에 기반함

지금까지의 프로그래밍 언어들 (PLs So Far...)

• 전통적인 언어들은 상태(state) 변환을 계산 모델로 삼음
• 모델의 핵심은 수정 가능한 변수(modifiable variables)임
  • 변수는 이름과 연관된 컨테이너로, 다른 값으로 할당될 수 있음
• 자연스럽게, 언어의 핵심 구조는 변수의 값을 수정하는 할당(assignment)임

함수형 패러다임 (Functional Paradigm)

• 수정 가능한 변수 없이도 계산을 수행할 수 있음
• 상태(state)를 수정하는 대신, 표현식을 재작성하여(rewriting expression) 계산할 수 있음
• 이는 변경이 프로그램 상태가 아닌 환경(environment)에서만 발생함을 의미함
  • 변수 대신 불변 객체(immutable objects)를 사용함
• 따라서 계산은 환경의 수정 측면에서 표현될 수 있음

역사 조금 (Little Bit of History)

• 함수형 패러다임은 최근에 개발된 새로운 개념이 아님
• 1930년대에 튜링 머신(Turing Machine)과 함께, Alonzo Church가 발명한 추상적인 계산 가능한 함수 모델인 λ-계산(λ-calculus)이 있었음
• Alonzo Church는 미국의 수학자였음
• 그는 Alan Turing, Stephen C. Kleene, Michael O. Rabin 등의 많은 학생을 두었음
  • 이들은 다양한 코스에서 만날 수 있는 인물들임

인기 있는(?) 함수형 언어들 (Popular(?) Functional Languages)

• LISP는 λ-계산(λ-calculus)에서 명시적으로 영감을 받은 최초의 프로그래밍 언어이며, 이 패러다임을 따르는 다른 많은 언어들이 있음
• LISP의 여러 방언(dialect)도 인기 있음
  • Common Lisp, Racket, Scheme, Clojure
• ML
  • Standard ML, OCaml, F#
• 순수 함수형 언어
  • Miranda, Haskell
• C++11과 Java 8은 람다 표현식(lambda expressions)과 같은 제한된 함수형 기능을 지원함
  • 많은 언어들이 점점 더 많은 함수형 기능을 도입하고 있음

특성 (Characteristics)

• 프로그램과 데이터의 동질성 (Homogeneity of programs and data)
  • 함수형 언어에서는 함수가 표현 가능한 값이며, 복잡한 표현식을 평가하여 얻을 수 있음
• 자기 정의 (Self-Definition)
  • 함수형 언어의 동작적 의미론(operational semantics)은 종종 언어로 작성된 인터프리터로 정의될 수 있음
• Read-Eval-Print Loop (REPL)을 통한 상호작용

val과 fun (val and fun)

• 다음 강의에서는 함수형 개념을 설명하기 위해 간단한 ML 구문을 사용할 것임
• 키워드 val은 선언이다. 대입이 아님.

  val three = 1 + 2;
  val f = fn x => x * x;
  

  x는 파라미터, x * x는 함수의 body 이다.
• 키워드 fn은 함수를 나타냄
• 함수의 적용(application)은 여러 가지 방식으로 쓸 수 있음
  • f(2), (f 2), 또는 f 2

  val four = f 2;
  

• f는 fn x => x * x 이고, argument가 2이라서 결과가 4가 된다.
  • (fn x => x * x) 2

val과 fun (val and fun)

• 키워드 fun은 함수 정의의 구문적 설탕(syntactic sugar)임

  fun f x = x * x;  => val f = fn x => x * x;
  

  fun {함수 이름} {파라미터} {함수 바디}
• 일반적으로,

  fun F x1 x2 ... xn = body;
  --> val F = fn x1 => (fn x2 => ... (fn xn => body)...);
  

  F(x1, x2, x….. xn)

조건문과 재귀 (Conditionals & Recursion)

• 조건식은 if then else로 작성할 수 있음

  fun fact n = if n = 0 then 1 else n * fact(n - 1);
  

• 여기서 재귀도 사용할 수 있음
• 함수형 언어에는 상태(state)가 없기 때문에 반복(iteration)이 없음
• 대신, 반복을 위해 재귀를 사용할 수 있음

축약에 의한 계산 (Computation by Reduction)

• Computation(계산, or evaluation)은 축약(reduction)으로 수행할 수 있음
• Evaluation은 복잡한 표현식을 그 값으로 변환하는 과정임
• 축약은 표현식을 재작성하여 그 값을 얻는 과정임
  • 축약을 위해 ⟶ 기호를 사용함
  • ex) x + 2 + 3 ⟶ x + 5

추상화와 적용 (Abstraction and Application)

• 표현식의 두 가지 핵심 구조
• 추상화(abstraction): fn x => expr는 함수가 형식적 매개변수 x를 표현식 expr으로 변환함을 나타냄
  • expr은 x에 바인딩된 특정 값에서 "추상화"됨
  • fn x => x + 3
• 적용(application): f_expr a_expr는 표현식 f_expr를 다른 표현식 a_expr에 적용함을 나타냄
  • 이는 함수 f_expr을 인수 a_expr에 적용하는 것을 의미함
  • (fn x => x + 3) 4
    • 7

계산 예제 (Computation Example)

• 다음과 같은 함수 정의가 있을 때,

  fun fact n = if n = 0 then 1 else n * fact(n - 1);
  

  val fact = fn n => if n = 0 then 1 else n * fact(n - 1);
• fact 2의 계산 과정:

  fact 2 ⟶ (fn n => if n = 0 then 1 else n * fact(n - 1)) 2
      ⟶ if 2 = 0 then 1 else 2 * fact(2 - 1)
      ⟶ 2 * fact(1)
      ⟶ 2 * ((fn n => if n = 0 then 1 else n * fact(n - 1)) 1)
      ⟶ 2 * fact(0)
      ⟶ 2 * (fn n => if n = 0 then 1 else n * fact(n - 1) 0)
      ⟶ 2 * 1 ⟶ 2
  

용어 정리 (Terminology)

• Redex: 축약 가능한 표현식 (reducible expression), ((fn x => body) arg) 형태의 적용
  • 예: ((fn x => x * x) 2)
• Reductum: redex ((fn x => body) arg)의 reductum은 body에서 x를 arg로 대체한 표현식
  • 예: ((fn x => x * x) 2)의 reductum = 2 * 2
  • application of function이다.

𝛽-규칙 (β-Rule)

• 표현식 expr에서 redex rx가 부분 표현식으로 나타날 때,
  • expr을 expr1로 축약할 수 있음
  • 이는 redex rx를 reductum rt로 대체함으로써 이루어짐
• 이를 β-규칙이라 함
• 표기법: expr ⟶ expr1
• 예:

  (fn x => (fn y => x)) a ⟶ fn y => a
  

  최종적으로 a로 축약된다.

값 (Values)

• 값은 더 이상 축약할 수 없는 표현식, 불변임
• 값은 두 가지 종류가 있음:
  • 원시 타입의 값 (Values of primitive types)
  • 함수 (Functions)
• 예를 들어,

  val G = fn x => ((fn y => y + 2) 1);
  

  • fn x => expr 형태의 모든 표현식은 값임
    • (fn y => y + 2) 얘도 value
    • fn x => ((fn y => y + 2) 1) 얘도 value

종료와 발산 (Termination vs. Divergence)

• 표현식의 평가는,
  • 값으로 종료될 수 있음
  • 또는 발산(diverges), 이는 표현식의 값이 정의되지 않음을 나타냄
• 예:

  fun r x = r(r(x))
  

reduction 마다 r이 늘어난다.

평가 문제 (Evaluation Issues)

• 축약의 종료 조건은 무엇인가?
  • 값이란 무엇인가?
• 동일한 표현식에 여러 redex가 있을 때, 어떤 순서로 축약할 것인가?
  • 평가 순서(order of evaluation)는 중요함

변수 캡처 없는 치환 (Capture-Free Substitution)

• 변수 캡처(variable capture): 변수를 치환할 때 다른 변수가 "캡처"될 수 있음
  • val f = fn x => (fn y => xy)
    • f z fn y => zy
    • 만약 fn t => xt이고 x가 t라면 tt이다.
  • variable capture에 따라 결과가 달라진다.
    • 이름이 어디서 왔는지 환경이 필요하다.
• Evaluation은 서로 다른 환경에서 정의된 변수 이름에 의존함
  • 이를 위해 이름뿐만 아니라 바인딩(binding)도 포함하는 클로저(closure)를 제공해야 함
• 여기서는 간단한 구문 규칙을 사용함
  • 모든 표현식에서, 동일한 이름을 가진 formal parameter가 두 개 이상 없음
  • 가능한 argument들은 formal parameter들과 모두 다름
  • 따라서 이 강의에서는 변수 캡처를 고려하지 않음

표현식 평가 (Expression Evaluation)

평가 전략 (Evaluation Strategies)

• 값에 의한 평가 (Evaluation by Value)
• 이름에 의한 평가 (Evaluation by Name)
• 지연 평가 (Lazy Evaluation)

값에 의한 평가 (Evaluation by Value)

인수부분에 redex가 오면 evaluation을 해서 값으로 축약한 뒤 원래 redex를 축약한다.

• 응용 순서 적용법 (applicative-order), eager, 또는 innermost 평가라고도 함
• redex는 인수 부분이 값일 때만 평가됨
  • ((fn x => body) arg)
  • redex를 만나면, 먼저 인수 부분을 평가하여 값으로 축약함
  • 그 다음에 redex를 축약함

알고리즘

• 표현식을 왼쪽에서 오른쪽으로 스캔하며, 첫 번째 application을 선택함 (예: (f_expr a_expr))
• 이 방법을 적용하여 f_expr을 함수 형태인 (fn x => ...)의 값으로 축약함
  • We have a redex after f_expr turns into a value of a function.
• 그런 다음 인수 a_expr을 값 val으로 축약함
• redex ((fn x => ...) val)을 축약하고 처음으로 돌아감

값을 구하고 축약한다.

값에 의한 평가 (Evaluation by Value) 예제

fun K x y = x;
fun r z = r(r(z));
fun D u = if u = 0 then 1 else u;
fun S v = v + 1;
val v = K (D (S 0)) (r 2);

• K (D (S 0)) (r 2);
• K (D (S 0)) 축약:
  

  K (D (S 0)) ⟶ K (D ((fn v => v + 1) 0))
                ⟶ K (D 1)
                ⟶ K ((fn u => if u = 0 then 1 else u) 1)
                ⟶ K 1
                ⟶ (fn x => (fn y => x)) 1 ⟶ fn y => 1
  

K를 적용하려고 하니 인수를 평가해야 한다 (D (S 0)) 평가
D를 적용하려고 하니 또 인수를 평가해야 한다 (S 0)를 평가
S의 인수로 0이 오니 축약할 수 있다

이를 거꾸로 올라가면 최종적으로 K 1이 나옴.

• K (D (S 0)) (r 2) ⟶ (fn y => 1) (r 2)

---

(r 2) ⟶ ((fn z => r(r(z))) 2) ⟶ r(r(2))
        ⟶ (fn z => r(r(z))) r(2) ⟶ r(r(r(2))) ⟶ ...

(r 2)를 Application 해보자. —> 발산한다.

• 이는 발산함 (diverges)
• 따라서 val v는 정의되지 않음
  • 지금까지 한 게 너무 아깝다~
  • 먼저 이 부분을 평가했다면 낭비를 하지 않았을텐데…

이름에 의한 평가 (Evaluation by Name)

• Normal-order 또는 outermost 평가라고도 함
• redex는 인수 부분보다 먼저 평가됨
  • ((fn x => body) arg)
  • Evaluate the redex first using the argument arg.
• 표현식을 왼쪽에서 오른쪽으로 스캔하며, 첫 번째 적용을 선택함 (예: (f_expr a_expr))
• 이 방법을 적용하여 f_expr을 함수 형태인 (fn x => ...)의 값으로 축약함
• 그런 다음 redex ((fn x => ...) a_expr)을 β-규칙을 사용하여 축약하고 처음으로 돌아감

위에서는 값을 구하고 축약했지만, 여기서는 축약하고 값을 넣는다.

이름에 의한 평가 (Evaluation by Name) 예제

fun K x y = x;
fun r z = r(r(z));
fun D u = if u = 0 then 1 else u;
fun S v = v + 1;
val v = K (D (S 0)) (r 2);

• K (D (S 0)) ⟶ (fn x => (fn y => x)) (D (S 0)) ⟶ fn y => D (S 0)

K x y = x이므로 y인 (r 2)는 무시할 수 있다.

• (fn y => D (S 0)) (r 2) ➞ arg
  • 여기서 (r, 2)는 y와 무관하다 무시한다.
  ⟶ D (S 0) ⟶ (fn u => if u = 0 then 1 else u) (S 0)<br> ⟶ if (S 0) = 0 then 1 else (S 0)<br> ⟶ if 1 = 0 then 1 else (S 0) ⟶ (S 0) ⟶ 1
• (S 0) ⟶ (fn v => v + 1) 0 ⟶ 1

지연 평가 (Lazy Evaluation)

• 이전의 이름에 의한 평가 예제에서, redex (S 0)을 두 번 축약해야 했음

  ⟶ if (S 0) = 0 then 1 else (S 0)
      ⟶ if 1 = 0 then 1 else (S 0)
      ⟶ (S 0) ⟶ 1
  

• 이번에는 그렇게 복잡하지 않았지만, redex가 상당한 계산을 요구할 경우 매우 비쌀 수 있음
• 함수의 적용 후까지 인수의 평가를 미룸으로써,
  • 값에 의한 평가가 발산할 때도 값을 얻을 수 있음 (장점)
  • 이는 상당한 계산을 요구하는 redex에 대해 매우 비쌀 수 있음 (단점)
• 이를 해결하기 위해 Lazy Evaluation는 Evaluation by name에 메모이제이션(memoization)을 사용함
  • redex의 첫 번째 복사본을 평가한 다음, 다음 복사본에서는 첫 번째에서 얻은 값을 단순히 사용함

의문이 생김 (A Question Arises)

• 동일한 표현식에 대해,
  • 두 가지 다른 평가 전략을 사용하여 두 가지 다른 결과를 얻었음
  • 다른 표현식에도 이런 일이 발생하는가?
• 두 전략이 동일한 표현식에 대해 서로 다른 값을 생성하는지 알아야 함

닫힌 표현식 (Closed Expressions)

• 닫힌 표현식 expr은 모든 변수들이 어떤 fn에 의해 바인딩된 표현식임
  • fn x => (fn y => x + y)
• fn x => (fn y => x + z) 는 closed expression이 아님. z가 outside variable 이기 때문이다.
• 다음과 같은 특성을 만족함:
  • 위에서 3가지 평가 전략 어떤 걸 사용하든, expression이 primitive value인 val로 축약된다면, 이름에 의한 평가(strategy by name)로도 val로 축약됨
  • expression이 evaluation by name으로 발산한다면, 다른 두 전략으로도 발산함
• 닫힌 표현식은 한 전략에서 val로 축약하고 다른 전략에서는 val2로 축약하지 않음
  • 같은 값으로 축약된다는 거임.
• 따라서 다음과 같은 속성을 의존할 수 있음:
  • 주어진 환경에서 전략이 고정되면, 동일한 단일 표현식의 모든 발생이 항상 동일한 값으로 축약됨
  • 이는 순수 함수형 언어의 기준임 - side-effect이 있을 경우 이 속성은 깨짐
    • side effect ex) evaluation 중에서 env가 바뀌는 경우
      • i++
  • 지연 평가는 이 property 덕분에 올바름을 유지함
  • 순수 함수형 언어가 아닌 경우에는 사이드 이펙트 때문에 lazy evaluation을 위한 키워드가 존재한다.

값에 의한 평가 전략의 장점 (What is Good for by-value Strategy?)

• 이름에 의한 평가 전략(strategy by name)이 잘 작동하는 것처럼 보임
• 왜 값에 의한 평가 전략(by-value strategy)이 필요한가?
  • 이름에 의한 평가 전략을 구현하는 것은 더 비쌈
  • argument 부분이 계산되지않고 먼저 축약되니까 당연한 말
• Evaluation by Value: LISP, Scheme, ML에서 사용
• Lazy Evaluation: Miranda와 Haskell에서 사용

요약 (Summary)

• 함수형 패러다임 개요
• 표현식 평가 방법
• 이름에 의한 평가(by Name), 값에 의한 평가(by Value), 그리고 지연 평가(Lazy Evaluation)

---