amaranth.log
💻 개발

[기술부채] 커링의 어원과 함수형 프로그래밍

서론

이전에 스터디를 하다가 자바스크립트의 커링에 대해 학습을 했다. 여러 번 봐 왔던 개념이지만 매번 잊어버리기 일쑤여서, 잊어버리지 않기 위해 커링의 어원을 찾아봤다.
notion image
그랬더니 Haskel Brooks Curry라는 이름의 아저씨가 나오는 것이 아닌가. 지피티가 해주는 설명을 읽고 있자니 프로그래밍 언어론 시간에 배웠던 내용이 새록새록 떠올랐고, 복기하기 좋은 소재인 것 같아 정리해봤다.

Haskell Brooks Curry

Haskell Brooks Curry는 수리논리학과 이론 컴퓨터 과학의 기초를 세운 학자 중 한 명으로, 특히 조합 논리를 발전시키고 함수형 프로그래밍과 타입 이론의 이론적 기반에 큰 영향을 준 인물이다.
그의 연구는 이후 Curry–Howard correspondence(대응)이라는 이론으로 이어져 논리학과 프로그램의 관계를 설명하는 중요한 토대를 제공했다.

수리논리학(Mathematical Logic)

수리논리학은 논리적 추론을 수학적으로 형식화하여 연구하는 학문이다.
즉, 인간의 논리적 사고를 기호와 형식적 규칙으로 표현해 계산 가능한 형태로 만드는 분야이다.
수리 논리학은 보통 다음의 네 가지 분야로 나뉜다.
  1. Proof theory (증명 이론)
    1. → 어떤 방식으로 논리적 증명이 구성되는가
  1. Model theory (모델 이론)
    1. → 논리식이 어떤 구조에서 참이 되는가
  1. Recursion theory / Computability theory (계산 가능성 이론)
    1. → 무엇이 계산 가능한가
  1. Set theory (집합론)
    1. → 수학의 기초 구조를 연구하는 분야
수리논리학은 대표적으로 다음과 같은 질문을 다룬다.
  • 어떤 명제가 참인지 거짓인지 어떻게 판단할 수 있는가?
  • 어떤 명제로부터 다른 명제를 논리적으로 증명할 수 있는가?
  • 수학 전체를 논리 규칙만으로 표현할 수 있는가?
  • 계산 가능한 것과 불가능한 것의 경계는 어디인가?
이러한 연구는 이후 계산 이론, 프로그래밍 언어론, 타입 시스템과 같은 컴퓨터과학의 기반이 되었다.

술어 논리

술어 논리는 대상(object)과 그 대상의 성질(property) 또는 관계(relation)를 논리적으로 표현하는 체계(system)이다.

명제논리와의 비교

ㅤ
명제 논리
술어 논리
설명
명제 전체를 하나의 기호로 보는 체계
문장을 구조적으로 표현하는 체계
예시
A: 모든 사람은 죽는다 B: 소크라테스는 사람이다 논리식: A, B
x가 사람이라면 x는 죽는다 술어: Human(x) → Mortal(x)
명제 논리에서는 문장의 내부 구조를 표현할 수 없지만, 술어 논리에서는 객체와 그 관계를 명확히 표현할 수 있다.

술어 논리의 기본 구성

  • 변수(대상): x, y, z
  • 상수(특정 객체): Socrates, 3
  • 술어(객체의 성질이나 관계): Human(x), Loves(x, y)
  • 논리 연산: ∧, ∨, →
  • 양화사(quantifier): ∀, ∃
예를들어 다음과 같은 논리식이 있을 때,
∀x (Human(x) → Mortal(x))
이는 다음과 같이 해석된다.
모든 x에 대해, x가 사람이면 x는 죽는다.
또한 다음과 같은 표현도 가능하다.
∃x Human(x) // 해석: 어떤 x는 사람이다

실제 추론 예

다음과 같은 두 명제가 있다고 하자.
∀x (Human(x) → Mortal(x)) // 모든 사람은 죽는다 Human(Socrates) // 소크라테스는 사람이다
이 두 명제로부터 다음 결론을 얻을 수 있다.
Mortal(Socrates)
*이러한 추론 규칙을 Modus Ponens라고 한다.

컴퓨터 과학에서의 활용

술어 논리는 여러 컴퓨터 과학 분야의 기반이 된다.
예를 들어 데이터베이스의 SQL은 사실상 술어 논리에 기반한 질의 언어라고 볼 수 있다.
다음 SQL 문을 보자.
SELECT * FROM student WHERE age > 20
이는 논리적으로 다음과 같은 조건과 유사하다.
Student(x) ∧ Age(x) > 20
또한 프로그램 검증에서도 논리식을 사용한다.
∀x (x > 0 → f(x) > 0)
이는 모든 입력 x가 양수라면 함수의 결과도 양수라는 사실을 증명한다는 의미이다.

람다 계산(Lambda Calculus)

함수 계산을 형식적으로 연구하기 위해 등장한 대표적인 이론이 람다 계산(lambda calculus)이다.
람다 계산은 1930년대 Alonzo Church가 제안한 계산 모델로, 모든 계산을 함수의 정의와 적용으로 표현할 수 있다는 아이디어에 기반한다.
람다 계산은 단 세 가지의 요소를 가진다.(변수, 함수 정의, 함수 적용)
예를 들어 다음과 같은 표현이 있다고 하자.
λx. x
이는 입력 값을 그대로 반환하는 함수이다.
프로그래밍 언어(JavaScript)로 표현하면 다음과 비슷하다.
x => x
함수를 실제로 적용하면 다음과 같은 계산이 이루어진다.
(λx. x) 5 → 5
이처럼 람다 계산은 함수와 함수 적용만으로 모든 계산을 표현할 수 있는 매우 단순한 계산 모델이다.

조합 논리(Combinatory Logic)

람다 계산은 강력한 계산 모델이지만 변수 관리와 관련된 문제가 존재한다. 예를 들어 변수 이름 변경이나 변수 충돌과 같은 문제가 발생할 수 있다.
이러한 문제를 해결하기 위해 Moses Schönfinkel이 제안하고 Haskell Brooks Curry가 발전시킨 이론이 바로 조합 논리(Combinatory Logic)이다.
조합 논리는 변수를 제거하고 함수의 조합만으로 계산을 표현한다.

기본 조합자

조합논리에서는 몇 개의 기본 함수(조합자)를 사용한다.
  • I combinator(identity): 입력을 그대로 반환한다.
    • I 5 -> 5
  • K combinator: 두 번째 인자를 버리고 첫 번째 인자를 반환한다.
    • K 3 10 -> 3
  • S combinator
    • S x y z = x z (y z)
  • 실제 계산의 예시
    • S K K 5 // 1. S의 정의를 적용: S x y z = x z (y z) -> K 5 (K 5) // 2. K의 정의를 적용: K x y = x -> 5 => S K K = I
여기서 중요한 점은 S와 K 두 개로 모든 계산을 표현할 수 있다(⇒ 튜링 완전성)는 것이다.
즉, 모든 람다식은 조합 논리로 변환할 수 있다.
💡
튜링 완전성
튜링 완전성(Turing Completeness)은 어떤 계산 체계가 이론적으로 모든 계산을 표현할 수 있는 능력을 의미한다.
이 개념은 수학자 앨런 튜링이 제안한 튜링 머신을 기준으로 정의된다. 튜링 머신은 무한한 길이의 테이프와 이를 읽고 쓰는 장치를 가진 매우 단순한 이론적 계산 모델로, 일정한 규칙에 따라 기호를 읽고 쓰는 과정을 반복함으로써 계산을 수행한다. 이 모델은 실제 컴퓨터를 단순화하여 ‘계산이란 무엇인가’를 수학적으로 설명하기 위해 만들어졌다.
어떤 시스템이 튜링 머신이 수행할 수 있는 모든 계산을 표현할 수 있다면, 그 시스템은 튜링 완전하다고 말한다.
람다 계산, 조합 논리는 매우 단순한 규칙으로 이루어져 있지만, 이론적으로 모든 계산을 표현할 수 있기 때문에 튜링 완전한 계산 모델로 알려져 있다.

Curry–Howard correspondence(대응)

이러한 연구는 논리와 프로그램 사이의 관계를 발견하는 데까지 이어졌다. 그 대표적인 결과가 바로 Curry–Howard correspondence이다.
이 이론의 핵심 아이디어는 다음과 같다.
논리 명제는 타입에 대응하고, 논리 증명은 프로그램에 대응한다.

대응 관계

논리
프로그래밍
명제 (Proposition)
타입 (Type)
증명 (Proof)
프로그램 (Program)
증명 과정
프로그램 실행
증명 존재
프로그램이 타입을 가진다
예를 들어 논리 명제 A → B는 프로그래밍에서 A -> B와 같은 함수 타입에 대응한다.
이를 실제 코드로 표현하면 다음고 ㅏ같다.
function f(a: A): B
Curry–Howard 대응에 따르면, 이 함수가 존재한다는 것은 A → B라는 논리를 증명할 수 있다는 의미가 된다.

커링(Currying)

커링은 함수를 여러 개의 단일 인자 함수로 변환하는 기법이다. 이름은 Haskell Brooks Curry의 이름에서 유래했다.
일반 함수 f(x, y)가 있을 때 커링을 통해 f(x)(y)의 형태로 변환할 수 있다.
예) f: (x, y) -> z
⇒ f: x -> (y -> z)
function add(x, y) { return x + y }
일반 함수
function add(x) { return function(y) { return x + y } }
커링을 거친 함수
이러한 변환은 함수의 구조를 단순하게 만들고, 함수 계산을 더 통일된 방식으로 다룰 수 있게 해 준다.

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

이러한 수리논리학적 연구는 실제 프로그래밍 언어 설계에도 영향을 주었다.
특히 람다 계산과 타입 이론을 기반으로 발전한 프로그래밍 패러다임이 바로 함수형 프로그래밍(functional programming)이다.
함수형 프로그래밍은 계산을 함수의 적용(application)으로 표현하는 프로그래밍 패러다임이다. 프로그램은 상태를 변화시키는 명령들의 집합이라기보다, 함수들을 조합하여 결과를 계산하는 과정으로 볼 수 있다.
대표적인 함수형 언어로는 Lisp, Haskell, OCaml, F# 등이 있다.

함수형 프로그래밍의 핵심 특징

1. 순수 함수 (Pure Function)

함수형 프로그래밍에서 가장 중요한 개념은 순수 함수이다.
순수 함수는 다음 두 가지 조건을 만족한다.
  1. 같은 입력에 대해 항상 같은 결과를 반환한다.
  1. 함수 실행이 외부 상태를 변경하지 않는다.
예를 들어 다음과 같은 함수는 순수 함수이다.
function add(a,b) { return a+b }
이 함수는 입력이 동일하면 결과도 항상 동일하며, 프로그램의 다른 상태를 변경하지 않는다.
반대로 다음 함수는 순수 함수가 아니다.
let count = 0 function increment() { count++ }
이 함수는 외부 변수의 값을 변경하기 때문에 부수 효과(side effect)를 가진다.
순수 함수를 사용하면 프로그램의 동작을 수학적 함수처럼 분석할 수 있다는 장점이 있다.

2. 불변성 (Immutability)

함수형 프로그래밍에서는 데이터가 생성된 이후 변경되지 않는 것(immutable)을 기본 원칙으로 한다.
예를 들어 배열을 수정하는 대신 새로운 배열을 만든다.
const numbers = [1,2,3] const newNumbers = [...numbers, 4]
기존 배열을 변경하지 않고 새로운 값을 만든다.
이러한 불변성은 다음과 같은 장점을 만든다.
  • 프로그램의 상태 변화가 예측 가능
  • 동시성 문제 감소
  • 디버깅 용이

3. 고차 함수 (Higher-Order Function)

함수형 프로그래밍에서는 함수가 다른 함수를 인자로 받거나 반환할 수 있다.
이러한 함수를 고차 함수라고 한다.
예)
function apply(f, x) { return f(x) }
여기서 f는 함수이다.
대표적인 고차 함수는 다음과 같다.
  • map
  • filter
  • reduce
예) 다음 코드는 각 요소에 함수를 적용하여 새로운 배열을 만든다.
const numbers = [1,2,3,4] numbers.map(x => x * 2)

4. 함수 합성 (Function Composition)

함수형 프로그래밍에서는 여러 함수를 조합하여 새로운 함수를 만든다.
예)
f(g(x))
이 구조는
const h = x => f(g(x))
와 같은 함수 합성이다.
이 방식은 복잡한 계산을 작은 함수들의 조합으로 구성할 수 있게 한다.

5. 커링과 부분 적용

앞서 설명한 커링(currying)은 함수형 프로그래밍에서 매우 중요한 역할을 한다.
function add(x) { return function(y) { return x + y } }
사용 예시)
const add3 = add(3) add3(10)
이 구조를 통해 부분 적용(partial application)이 가능해진다.
이는 함수 재사용성을 높이고 프로그램을 더 선언적으로 작성하게 만든다.

명령형 프로그래밍과의 차이

함수형 프로그래밍은 전통적인 명령형 프로그래밍(imperative programming)과 큰 차이가 있다.
명령형 프로그래밍
함수형 프로그래밍
상태 변경 중심
함수 계산 중심
변수 변경 가능
불변성
반복문 사용
재귀 또는 고차 함수
명령 순서 중요
수식 계산 구조
예를 들어 배열의 합을 계산할 때
  • 명령형 방식
    • let sum = 0 for (let i=0; i<numbers.length; i++) { sum += numbers[i] }
  • 함수형 방식
    • numbers.reduce((a,b) => a + b)
함수형 방식은 무엇을 계산할지를 표현하고, 명령형 방식은 어떻게 계산할지를 표현한다.

정리

지금까지의 흐름을 정리하면 다음과 같다.
수리논리학은 논리적 추론을 형식적으로 연구하는 학문이며, 그 과정에서 계산의 본질을 설명하기 위해 람다 계산이 등장하였다. 람다 계산은 모든 계산을 함수의 적용으로 표현할 수 있다는 사실을 보여주었고, 조합 논리는 이를 변수 없이 표현하는 방법을 제시하였다. 이후 Curry–Howard correspondence는 논리 명제와 프로그램 타입 사이의 구조적 대응 관계를 설명하였다.
이러한 이론적 기반 위에서 발전한 프로그래밍 패러다임이 바로 함수형 프로그래밍이다. 함수형 프로그래밍은 계산을 순수 함수와 함수의 조합으로 표현하며, 프로그램을 보다 수학적인 구조로 이해하려는 접근 방식이라고 할 수 있다.
 
📚 기술 부채29 / 31
  1. 1편[기술부채] 우테코 5기 레벨1 - 6주차: 블랙잭 미션, RDD와 try-with-resources2023년 3월 20일
  2. 2편[기술부채] 우테코 5기 레벨1 - 7주차: 체스 미션, 방어적 복사와 커맨드 패턴2023년 3월 27일
  3. 3편[기술부채] 우테코 5기 레벨1 - 8주차: 체스 미션, 테스트 더블과 커넥션 풀2023년 4월 14일
  4. 4편[기술부채] 우테코 5기 레벨2 - 1주차: 웹 자동차 경주, 스프링 MVC 매핑과 DI2023년 4월 16일
  5. 5편[기술부채] 우테코 5기 레벨2 - 2주차: @Valid와 Dirty Checking2023년 5월 1일
  6. 6편[기술부채] 우테코 5기 레벨2 - 3주차: 장바구니 미션, MockMvc vs RestAssured와 PRG 패턴2023년 5월 3일
  7. 7편[기술부채] 우테코 5기 레벨2 - 5주차: Mockito와 동적 쿼리2023년 5월 14일
  8. 8편[기술부채] 우테코 5기 레벨2 - 6주차: 지하철 미션, Profile과 JPA 연관관계2023년 5월 23일
  9. 9편[기술부채] 우테코 5기 레벨2 - 9주차: CORS Preflight와 멱등성, 필드 주입2023년 6월 12일
  10. 10편[기술부채] 우테코 5기 레벨2 - 8주차: 장바구니 협업 미션, LocalDateTime 직렬화와 시맨틱 버저닝2023년 6월 12일
  11. 11편[기술부채] 우테코 5기 레벨2 - 7주차: OSIV와 영속성 컨텍스트, CORS 인증2023년 6월 30일
  12. 12편[기술부채] 우테코 5기 레벨3 - 3주차: 오프셋·커서 페이지네이션과 @ElementCollection2023년 7월 18일
  13. 13편[기술부채] 우테코 5기 레벨3 - 7주차: Batch Insert와 @EventListener2023년 8월 12일
  14. 14편[기술부채] 우테코 5기 레벨3 - 8주차: JPQL Distinct와 MultipleBagFetchException2023년 8월 31일
  15. 15편[기술부채] 우테코 5기 레벨3 - 6주차: 동시성 이슈와 @Transient2023년 8월 31일
  16. 16편[기술부채] 우테코 5기 레벨3 - 1주차: 무결성과 정합성, Elastic Beanstalk2023년 8월 31일
  17. 17편[기술부채] 우테코 5기 레벨4 - 1주차: @TransactionalEventListener와 트랜잭션 전파2023년 9월 10일
  18. 18편[기술부채] 우테코 5기 레벨4 - 2주차: 톰캣 만들기와 Location 헤더2023년 9월 11일
  19. 19편[기술부채] 우테코 5기 레벨4 - 3주차: 로드밸런서, CQRS와 커버링 인덱스2023년 9월 18일
  20. 20편[기술부채] 우테코 5기 레벨4 - 4주차: @MVC 구현하기 미션2023년 9월 24일
  21. 21편[기술부채] 우테코 5기 레벨4 - 5주차: @MVC 구현하기 3단계와 JSON 응답2023년 10월 2일
  22. 22편[기술부채] 우테코 5기 레벨4 - 6주차: JDBC 라이브러리 구현하기 1~3단계2023년 10월 9일
  23. 23편[기술부채] 우테코 5기 레벨4 - 7주차: JDBC 라이브러리 구현하기 3단계2023년 10월 16일
  24. 24편[Spring] Spring DTO의 데이터 바인딩과 직렬화2023년 12월 5일
  25. 25편[기술부채] 클라이언트 사이드 라우팅2026년 2월 5일
  26. 26편[기술부채] 왜 리액트는 클래스를 버리고 함수를 선택했을까(feat. React Hooks)2026년 2월 12일
  27. 27편[기술부채] iframe과 postMessage2026년 2월 20일
  28. 28편[기술부채] Service Worker(서비스 워커)2026년 2월 24일
  29. 29편[기술부채] 커링의 어원과 함수형 프로그래밍2026년 3월 12일
  30. 30편[기술부채] AG-UI와 CopilotKit - 12026년 3월 27일
  31. 31편[기술부채] AG-UI와 CopilotKit - 22026년 3월 29일