기타 업적

함수형 프로그래밍​¶¶​

1977년 튜링상 수상자로 선정된 존 배커스의 수상 기념 강연은 조금 충격적이다. 그가 선정된 이유 중 하나는 포트란 개발 때문이었다. 그간 튜링상 수상자는 선정 이유를 중심으로 강연했었다. 하지만 존 배커스는 완전히 다른 내용을 꺼내 들었다. 오히려 그가 했던 포트란을 부정하는 의도가 깔려 있었다. 강연의 제목은 “프로그래밍이 폰 노이만 스타일에서 벗어날 수 있을까?: 함수형 스타일과 그것의 대수​1​“이다.

그는 폰 노이만 스타일의 프로그래밍이 가지는 문제점들을 지적하면서 이를 극복하기 위한 방법으로 함수형 프로그래밍을 제안했다. 그렇다면 폰 노이만 스타일 프로그래밍이란 무엇인가? 그는 이렇게 설명했다.

폰 노이만 프로그래밍 언어는 컴퓨터의 저장 장소를 흉내 내기 위해 변수variable를 사용하고, 분기와 비교를 위해 제어문control statement을 사용하며, 값을 꺼내오고 저장하고 산술연산을 하기 위해 대입문assignment statement을 사용한다. 이 대입문이야말로 폰 노이만 병목지점이다.​1​

폰 노이만 구조란, 산술연산과 논리연산을 수행하는 중앙처리장치CPU가 있고, 프로그램 코드와 데이터를 저장한 메모리memory가 있어서, 중앙처리장치가 메모리에 접근하여 프로그램 코드를 하나씩 읽어가며 수행하는 방식의 컴퓨터 구조를 의미한다. 배커스는 중앙처리장치와 메모리 사이의, 코드 혹은 데이터 이동이 컴퓨터의 성능을 제한하는 요소라고 보았고, 이를 ‘폰 노이만 병목지점’이라고 불렀다. 아이러니하게도 포트란이 이런 문제를 가진 대표적인 프로그래밍 언어였다.

컴퓨터 프로그램이 하는 일이란, (결국) 어떤 주요한 방법을 써서 메모리의 내용을 바꾸는 것이다. 이 일은 순전히 중앙처리장치와 메모리 사이에서 뭔가가 왔다 갔다 하면서 이루어진다. 병목지점이라고 부르는 이유가 여기에 있다… 이 병목지점에서 발생하는 트래픽의 대부분은 실제 사용할 데이터 자체가 아니라, 우습게도 그 데이터의 이름(주소) 혹은, 그 이름(주소)을 계산하기 위해 사용되는 명령어와 데이터들이다. 예를 들어 어떤 값을 메모리에서 읽어오기 위해서는 그 값이 저장된 곳의 주소를 중앙처리장치가 알아야 한다. 그런데 이 주소가 메모리에 들어 있다면 이 주소값이 저장된 곳의 주소를 알아야 한다…​1​

그래서 배커스는 폰 노이만 병목지점의 문제를 회피할 수 있는 새로운 방식의 프로그래밍 언어를 고민했고 그 결과로 나온 것이 FP(Functional Programming) 시스템이다.

FP

배커스가 제안한 함수형 프로그래밍은 말 그대로 함수에 기반하고 있다. 대입문을 회피하기 위해서 변수는 사용되지 않으며 함수의 결과값이 바로 다른 함수의 입력값으로 사용된다.

행렬의 내적inner product을 계산하는 프로그램을 작성한다고 가정해보자. 전통적인(다시 말하자면 폰 노이만 스타일) 프로그래밍 언어인 알골 언어를 사용한 예가 아래와 같다.

c := 0;
for i:= 1 step 1 until 10 do
   c := c + a[i] x b[i]

a와 b라는 1차원 행렬의 내적을 구해서 그 결과를 c라는 변수에 저장하는 일을 한다. 행렬의 크기는 10이다. 이 프로그램에는 대입문이 여러 번 나온다. 대입문이 하는 일은 변수에 어떤 값을 넣어주는 것인데, 하드웨어적으로 보면 메모리의 특정 번지에 값을 저장하는 것이다. 변수 c와 i의 값이 계속 변하고 있다. 변수 c의 값을 결정하기 위해서는 행렬 a와 행렬 b의 값을 알아야 한다. 행렬 a와 행렬 b는 메모리에 저장되어 있으므로 메모리에 대한 접근이 계속 발생한다.

배커스의 FP를 사용하여 같은 일을 하는 코드를 작성하면 다음과 같다.

Def IP ≡ (/+)∘(αx)∘Trans

이것은 IP라는 함수를 정의한 것이고, 이것을 실제로 사용하려면 다음과 같이 입력값을 주어야 한다.

IP:<<1,2,3>, <6,5,4>>

전통적인 방식의 프로그래밍에 익숙해 있다면 이런 표기법이 쉽게 눈에 들어오지 않을 것이다. 이 함수형 프로그래밍을 이해하기 위해서는 특별한 기호들을 알아야 한다. 일단 < >는 벡터값(즉 배열)을 의미한다. <<1,2,3>, <6,5,4>>는 <1,2,3>과 <6,5,4>를 원소로 가지는 배열인 셈이다.

: 기호는 ‘함수를 적용하라’는 의미이다. f:x 라는 표기는, f라는 함수를 x라는 객체에 적용하라는 의미이다. 따라서 위의 코드는 IP라는 함수를 <<1,2,3>, <6,5,4>>라는 값에 적용하라는 의미이다.

Def는 함수 정의이다. 위에서는 IP라는 함수가 (/+)∘(αx)∘Trans로 정의되었다. 그런데 IP라는 함수가 (/+)∘(αx)∘Trans라고 해서 우리의 이해가 쉬워지지는 않는다. 왜냐하면 우리는 /, +, ∘, α, x, Trans가 각각 무엇인지 모르기 때문이다. 좀 더 들여다보자.

∘, /, α 는 단순히 알파벳 문자 중 하나가 아니다. 배커스의 FP에서 특별한 의미를 가지는 기호이다. 이것들은 함수적 폼 functional forms이라고 부르는데, 이미 있는 함수들을 결합해서 새로운 함수를 만들 때 사용된다. ∘ 기호는 두 개의 함수를 순서대로 수행하라는 의미이다. 오른쪽에 오는 함수가 먼저 수행된다는 점에 유의하자.​##​ 그러니까 위의 예에서는

IP:<<1,2,3>, <6,5,4>>
(/+)∘(αX)∘Trans:<<1,2,3>, <6,5,4>>
(/+):((αX):(Trans:<<1,2,3>, <6,5,4>>))

처럼 진행되는 셈이다. 즉 <<1,2,3>, <6,5,4>>라는 값에 대해서 Trans 라는 함수가 먼저 적용되고, 그 결과값에 αX 라는 함수가 적용되고, 다시 그 결과값에 /+ 라는 함수가 적용된다.

+ 기호는 덧셈 산술연산, X 기호는 곱셈 산술연산, Trans 기호는 행렬의 전치transpose 연산을 의미한다. 이 연산은 이미 FP가 기본적으로 지원하는 연산이다. 위의 예에서 Trans 함수를 제일 먼저 수행해야 한다. 그 결과는 다음과 같다.

(/+):((αX):<<1,6>, <2,5>, <3,4>>)

α 기호는 뒤에 오는 함수를 입력 배열의 모든 원소에 적용하라는 의미를 가지고 있다. 위의 예에서는 곱셈을 배열의 각 원소에 모두 적용하게 된다.

(/+):<X:<1,6>, X:<2,5>, X:<3,4>>
(/+):<6,10,12>

/ 기호는 뒤에 오는 함수를 입력 배열의 꼬리 원소에 적용하라는 의미이다. 예를 보면 이해가 쉬울 듯싶다.

+:<6,+:<10,12>>
+:<6,22>
28

언뜻 보면 전통적인 방식의 프로그래밍에 비해 더 복잡해 보인다. 하지만 대입문이 사라지고 임시 저장용으로 사용되는 변수들이 없어지면서 프로그램이 간결하고 명료해졌다. 전통적인 방식의 프로그래밍으로 작성된 앞의 예를 보면, 우리는 프로그램의 의도를 이해하기 위해 변수가 어떻게 이용되는지를 분석해야만 한다. 하지만 함수형 프로그래밍에서는 함수들이 어떻게 결합되었는지를 파악하면 된다.

배커스의 FP는 기본적인 함수들을 제공하고, 이 함수들을 결합하는 다양한 함수적 폼functional forms를 제공한다. 함수는 결과값만 돌려주면 역할이 끝나기 때문에 이른바 상태state를 가지지 않는다. 그렇기 때문에 부작용side effect도 발생하지 않는다.​***​

FP의 한계

배커스가 제안한 함수형 프로그래밍은 큰 반향을 일으켰고 많은 연구를 촉발했다. 하지만 FP(그리고 그 후속이었던 FL)는 연구실을 벗어나 현장을 파고드는 데 성공하지 못했다. 그 이유에 대해서는 배커스 본인이 이렇게 말했다.

그것을 실제 완전한 시스템으로 만드는 일은 아주 헷갈리고 지저분했습니다. 그 언어로는 표현할 수 없는 많은 이슈들이 있었습니다… 그리고 그 근본 패러다임 속에 실시간 처리 방법이 없었습니다. 뭔가를 다른 형태로 변형시키는 방법은 묘사할 수 있었지만 시간을 포함하는 요소가 없었습니다.​2​

프로세서 구조 – 미리보기 기능

폰 노이만 구조의 컴퓨터에서는 메모리가 전체 성능의 발목을 잡는 요소이다. 메모리 접근이 빠를 수록 컴퓨터 성능이 향상된다. 메모리 접근 속도는 물리적으로 결정된다. 메모리 접근 속도가 빠른 물리적 소자는 가격이 비싸다. 비용 대비 성능을 향상시키기 위해 가장 많이 사용되는 방식은 캐시cache 메모리이다. 그런데 캐시 메모리라는 방식은 1960년대가 되어서야 등장했다. 1950년대에 배커스는 다른 방식을 제안했고​10​ 지금도 고성능 마이크로프로세서에 사용되고 있다. 그것은 명령어 미리보기instruction lookahead이다. 그는 1955년에 진 암달과 함께 ANS(Asynchronous Non-Sequential) 제어라는 이름으로 이 방식을 제안했다.

명령어 미리보기란, 말 그대로 메모리에 있는 명령어를 미리 확인하는 것을 말한다. 일반적인 프로세서는 명령어를 메모리에서 가져온 후에 작업을 수행하고, 작업이 끝나면 다음 명령어를 메모리에서 가져온다. 하지만 ‘명령어 미리보기’ 방식에서는 아직 작업이 끝나기도 전에 메모리에서 다음 명령어를 가져온다. 메모리에서 명령어를 가져오는 시간이 줄어드는 효과를 가져온다.

이 방식이 실질적으로 동작하려면 미리 가져오는 명령어를 정확하게 선정할 수 있어야 한다. 무조건 다음 번지에 있는 명령어를 가져와서는 안 된다. 왜냐하면 현재 수행되는 명령어가 분기branch 명령이라면 다음에 수행될 명령어는 완전히 떨어져 있는 주소에 있을 수 있기 때문이다.

  1. ​*​
    출처: http://db.science.uoit.ca/library/teaching/programming-languages/1-computation/1-history
  2. ​†​
    출처: http://www.columbia.edu/cu/computinghistory/backus.html
  3. ​‡​
    그가 이곳을 방문하게 된 이유에 대해서는 두 가지 이야기가 있다. ACM Turing Award Laureate 사이트에서는 그가 우연히 건물을 지나치다가 SSEC 컴퓨터를 발견하고 건물에 들어갔다고 하고 있고, IBM Builders 사이트에서는 같은 과 친구로부터 이야기를 듣고 찾아갔다고 되어 있다.
  4. ​§​
    진 암달은 후에 IBM 360시리즈를 설계하였다.
  5. ​¶​
    3만 줄짜리 기계어 코드를 디버깅하는 일은 분명히 쉬운 일이 아니었을 듯 싶다.
  6. ​#​
    2005년에 튜링상을 수상했다. 덴마크의 컴퓨터 과학자이다. 덴마크에는 페테르 나우르라고 불리지만 영어권에서는 피터 나우어로 불렸다.
  7. ​**​
    이것은 순전히 예를 위하여 만든 가상의 프로그램이다. 실제로 이런 프로그램을 수행해주는 컴퓨터는 존재하지 않는다.
  8. ​††​
    이것은 저자가 설명을 위해 임의로 그렇게 만든 것이다. 실제로 이런 프로그램을 수행해주는 컴퓨터는 존재하지 않는다.
  9. ​‡‡​
    당시의 사람들은 이 정도만 되어도 자동으로 프로그래밍한다고 생각하였던 듯 싶다.
  10. ​§§​
    출처: https://en.wikipedia.org/wiki/Fortran#/media/File:FortranCardPROJ039.agr.jpg, CC BY-SA 2.5
  11. ​¶¶​
    존 배커스는 ‘functional programming’이라고 표현하기는 했지만, 일부에서는 function-level programming이라고 구별하기도 한다. 통상적으로 말하는 functional programming과는 약간의 차이가 있음에 유의하자.
  12. ​##​
    연산자의 적용방식이라든가 배열 처리 등을 보면 케네스 아이버슨의 APL과 유사하다는 느낌이 든다.
  13. ​***​
    프로그래밍 언어에서 부작용(side effect)란 함수가 결과값 이외에 다른 상태를 변경하는 현상을 말한다.

참고문헌

  1. 1.
    Backus J. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs. ACM Turing Award Lectures.:1977. doi:10.1145/1283920.1283933
  2. 2.
    John Backus Video Interview by Grady Booch. Computer History Museum; 2006:1-33.
  3. 3.
    John Backus. IBM Archives. Accessed August 9, 2022. https://www.ibm.com/ibm/history/exhibits/builders/builders_backus.html
  4. 4.
    ACM. John Backus. A.M. Turing Award Laureate. Accessed August 9, 2022. https://amturing.acm.org/award_winners/backus_0703524.cfm
  5. 5.
    어스프레이 윌리엄. 존 폰 노이만 그리고 현대 컴퓨팅의 기원. 지식함지; 2015.
  6. 6.
    그레이스 호퍼: 정보시대를 발명한 여인. 지식함지; 2017.
  7. 7.
    앨런 펄리스 – 튜링상 수상자 시리즈. 지식함지. Accessed February 14, 2023. https://knowledgebasin.com/archives/persons/%ec%95%a8%eb%9f%b0-%ed%8e%84%eb%a6%ac%ec%8a%a4
  8. 8.
    The FORTRAN Automatic Coding System for the IBM 704 EDPM: Programmer’s Reference Manual. IBM; 1956:1-54.
  9. 9.
    Fortran. Wikipedia. Accessed August 9, 2022. https://en.wikipedia.org/wiki/Fortran
  10. 10.
    Backus J. Computer System Design and ANS Control Techniques. IBM; 1955:1.

(c) 이재범, 2023
이 콘텐츠는 대한민국 저작권법의 보호를 받습니다. 작성된 모든 내용의 권리는 저자에게 있으며, 저자의 동의 없는 사용은 금합니다. 본 콘텐츠의 일부 혹은 전체 내용을 무단으로 전재/복제/배포하거나 2차적 저작물로 재편집하는 경우, 법적 책임을 지게 됩니다.

1 2 3 4 5