13. FPL(1)

Functional Programming Languages

imperative 언어의 설계
- von Neumann architecture 기반
- 명령과 데이터가 분리되지 않으며, 순차적인 명령어 실행
- 개발자 입장에서는 효율성(효과적인 소프트웨어 개발보다는 실행 성능) 중시
- 프로그램 상태(state) 변화 추적이 어려움
functional 언어의 설계
- 수학적 함수 기반
  $(\text{입력}) \rightarrow (\text{함수}) \rightarrow (\text{출력})$ 의 관계로 상태 변경 없이 결과 계산
- 수학적 이론(예: $\lambda$ -calculus)에 기반한 명확한 의미 체계 제공
- 명령형보다 추상화와 재사용, 검증 가능성 측면에서 유리
- 명시적으로 상태를 추적하지 않아도 됨
주요 함수형 언어들
- LISP: 1950년대 등장한 순수 함수형 언어
  - 이후 반복문, 변수 대입 등 명령형 요소도 일부 도입
- Common Lisp: 다양한 Lisp 방언의 통합형
- Scheme: 간결한 Lisp의 정제된 서브셋
- ML, Haskell, OCaml, F#: 정적 타입 기반 함수형 언어

수학적 함수의 정의
- 정의역(domain)과 치역(range) 사이의 명확한 매핑
- 표현식(expression) 또는 테이블(table)로 정의 가능
- 평가 과정은 재귀(recursion)와 조건 표현식(conditional expression)에 기반
- 반복 대신 재귀 사용
- 함수는 side-effect가 없음 (같은 입력 → 같은 출력)
- 참조 투명성(referential transparency) 보장
- 함수는 이전 상태(stage)를 기억하지 않음
예시: 함수 정의와 평가
$\text{cube}(x) = x \times x \times x$ $\text{cube}(2) = 2 \times 2 \times 2 = 8$
위 정의에서 $x$ 는 평가 시점에 $2$ 로 바인딩됨
함수 정의 안에는 자유 변수(free variable)가 없어야 함
무명 함수(nameless function)와 람다 표현식
$\lambda x.\, x \times x \times x$
$(\lambda x.\, x \times x \times x)(2) = 8$
$\lambda x.\lambda y.\, x + y$
$(\lambda x.\lambda y.\, x + y)(1)(2) = 3$
- 중첩된 람다 표현은 $n$ 개의 매개변수를 순차적으로 받을 수 있음
- 리스트에도 적용 가능: 예) $map(\lambda x.\, x \times 2,\ \text{numbers})$

람다 계산법( $\lambda$ -calculus)은 함수형 언어의 계산 모델
- 튜링 기계와 동등한 계산 능력을 가짐
- 수식 기반 형식 언어로, 변수 바인딩과 함수 응용으로 모든 계산 수행 가능
함수 응용 예시
$(\lambda x.\, x \times x)(3) = 9$
언타입드 람다 계산법: 예) Scheme
타입드 람다 계산법: 예) ML, Haskell

고차함수(higher-order function) 또는 함수형 형태(functional form)
- 함수를 인자로 받을 수 있음
- 함수를 반환할 수 있음
- 또는 둘 다 가능
고차 함수는 함수형 프로그래밍의 핵심 도구
코드 재사용성과 유연성 향상

두 개의 함수를 입력받아 첫 번째 함수를 두 번째 함수에 적용하는 새로운 함수를 생성
$h = f \circ g \Rightarrow h(x) = f(g(x))$
예시:
$f(x) = x^2,\quad g(x) = x + 2 \Rightarrow h(x) = f(g(x)) = (x+2)^2$

하나의 함수와 리스트를 입력받아, 리스트의 각 원소에 함수를 적용한 결과 리스트를 반환
일반형:
$\text{map}(f, (x_1, x_2, ..., x_n)) = (f(x_1), f(x_2), ..., f(x_n))$
예시:
$f(x) = x^2,\quad \text{map}(f, (2, 3, 4)) = (4, 9, 16)$

함수형 언어의 설계 목표: 수학적 함수 모방
명령형 언어와의 본질적 차이:
- 명령형: 계산 방법(how)을 지시함 (예: $x = x + 1$ )
- 함수형: 선언적 방식으로 계산 대상(what)을 표현
표현식 기반 구성:
$(x+y)+(a-b)$
상태(state)나 변수의 직접 조작을 최소화
재귀(recursion)를 주요 반복 구조로 사용

Lisp의 기본 데이터 타입: atom과 list
- atom: 숫자, 기호 등 단일 값
- list: 원소가 리스트 또는 atom일 수 있음
리스트 표현 예시:
$(A\ B\ C\ D\ E\ F\ G)$
- 리스트는 중첩 가능: $((A\ B)\ (C\ D))$
- sublist 표현 가능
Lisp는 typeless 언어
- 모든 데이터는 리스트 또는 atom으로 표현
- Common Lisp은 다양한 타입을 지원 (정수, 실수, 문자열 등)
- 단일 연결 리스트 형식으로 내부 구현:
  $(A\ B\ C) \Rightarrow [A] \rightarrow [B] \rightarrow [C] \rightarrow \text{NIL}$