감명 깊었던 programming language principles 5- 값 중심의 언어

지금까지 프로그래밍 언어가 어디서 시작되어 어떻게 만들어 졌는지에 대해서 언급했습니다.

현재 프로그래밍 언어가 나아가는 방향은 시스템(기계) 을 다루는 단계에서 점점 본연의 목적을 향해 가고 있습니다.

그 본연의 방향이라는 것은 적어도 "기계를 편하게 다루는 것"은 아닙니다. 

"기계의 편리한 사용" 이라는 슬로건으로는 달성할 수 없었던 결과를 향하는 것입니다.

다시한번 처음에 언급했던, 프로그래밍 언어가 컴퓨터를 구동시키기 위해 만들어 졌는가?에 대해서 되세겨봅시다.

프로그래밍 언어는 컴퓨터를 동작시키기 위해서 만들어진 것이 아닙니다. 프로그래밍 언어가 있었고(수학적 증명을 위해서 만들어진), 이것을 동작시키기 위해서 컴퓨터가 탄생했습니다. 

1930-40 년대에 이미 논리학자와 수학자들은 기계적으로 계산가능한 것이 무엇인지 고민하기 시작했습니다.

괴델은 부분 재귀 함수(Partial Recursive Function)꼴로 정의 되는 함수들을 기계적으로 계산 가능한 것들이라고 정의했습니다.

처치는 람다 계산법(Lambda Calculus)으로 계산될 수 있는 것들이가고 정의 했고,

튜링은 튜링 기계(Turing Machine)가 실행할 수있는 것들이라고 정의 했습니다.

그런데, 세 가지가 모두 같은 정의였습니다. 부분 재귀 함수는 람다 계산법으로 계산될 수 있고, 람다 함수는 튜링 기계로 실행할 수 있고, 튜링 기계가 실행하는 함수는 부분 재귀 함수 꼴로 정의 할 수 있습니다.

그러고 나니 사람들은 기계적으로 계산 가능한 함수가 그게 다가 아닐까 믿고 있습니다. 세사람이 독자적으로 정의한 것들이 결국 다르지 않은 것으로 미루어 , 이것을 "Turing-Church Thesis"라고 부릅니다.

이 셋중에 람다 계산법( Lambda Calculus)이 문법과 의미정의를 가춘 언어의 모습을 하고 있습니다.

람다 계산법 Lambda Calculus

이 람다 계산법이라는 언어를 기초로 프로그래밍 언어를 디자인해가면 , 이 언어의 표현력이 완전하기 때문에 , 기계적으로 계산 가능한 모든 것이 이 언어로 작성할 수 있기에, 든든해집니다.

기계적으로 계산 가능한 모든 것을 표현할 수 있는 언어 "Turing-Complete"이라 합니다.

언어의 이름을 람다(Lambda)라고 합시다.

람다의 문법구조 Syntax 다음과 같습니다.(매우 간단하죠)

                                       

1. x는 이름입니다.

2. 는 함수를 뜻합니다. x는 함수의 인자 이고, E는 함수의 몸통입니다. x의 유효범위는 E입니다. E에 나타난 "x를 묶어준다고(binding)" 표현합니다.

3.E E를 다시 적어보면, E1 E2 로 표현된  함수를 적용하는 식입니다.  

      E1은 계산하면 함수 가 되어야 하고 E2는 그함수의 인자 x의 실체가 됩니다.

     (이 과정을 Beta-reduction이라고 합니다.)

풀이 과정은 주로 Beta-reduction으로 정리 되는데, 즉 람다 함수의 인자인 x에 대입하는 과정이라고 이해하면 되겠습니다.

문맥구조( context) C 는 빈칸[]을 딱 하나 품고있는 람다식입니다.

                                     

아래의 간단한 수식(?) 들을 이용하여 표현해 개념을 이해하고 넘어가겠습니다.

  

(1을 더하는 함수)

(2를  곱하는 함수 )

덧셈 (A) 곱셈 (M)  제곱(P)

(Am)n = m+n

(Mm)n = m*n

(Pm)n=n^m

실제 처치가 람다 계산법에서 연산식을 정의 해 놓은 내용입니다.

처치의 2와 3 같은 숫자는 두번 ,세번 과 같은 의미를 갖습니다.

그래서 

2 =  λfx.f(fx)

3 =  λfx.f(f(fx))

1 =  λfx.fx

0 =  λfx.x

와 같습니다. 

즉 f를 몇번 반복했는가가 의미가 있는 것입니다. 마치 숫자를 연산자나 함수처럼 다루는 것이죠.

예제로 3에 2승 을 계산 해봅시다. 

(P2)3 = ((λfg.fg)2)3

           = (λg.2g)3                         ----------  2g = (λfx.f(fx))g 2g는 g를 2번 수행하는 것 

           = (λg.(λfx.f(fx))g)3   = λfx.f(fx)3

           = λx.3(3x)  ------ (3x) 를 y로 치환하면, 3(3x) = 3y , 즉 y를 3번 수행하는 식이 필요함. (λfy.f(f(fy)))(3x)

           = λx.(λfy.f(f(fy))(3x))

           = λx.(λy.(3x)( (3x)( (3x)y) ) )

           = λxy. (3x)( (3x)( (3x)y) )

           = λxy. (3x)( (3x)( (x(x(xy)) ) )

           = λxy. (3x)( (x(x(x (x(x(xy))))) ) )

           = λxy. (x(x(x(x(x(x (x(x(xy))))))))) = 9 = 3^2

(3x)y  =  (&fz.f( f( fz ) ) x )y= (&z.x(x(xz)))y = x(x(xy)))

이런 Beta-reduction 과정에서   (λx.E)E1 과 같이 연산( 대입) 이 가능 한 부분을 레덱스 (redex)라고합니다.( reducible expression)

이 Beta-reduction 은 어떤 식에 따라서 영원히 계속될 수도 있습니다.

더이상 레덱스가 없을때 연산은 끝납니다. 이런 람다식을 정상식(normal term)이라고 부릅니다.

이 Beta-reduction 과정도 어떤 순서로 하는가에 따라, (즉, 어떤 레덱스 부터 바꾸는가에 따라) 결과가 달라집니다.

그래서 순서가 중요합니다.

정상순서로 계산하는 것은 normal-order reduction 이라고 하고, 제일 왼쪽 제일 위의 레덱스를 계산해가는 것입니다.

이 순서로 진행하면, normal term이 있는 람다식은 항상 그 정상식에 도달합니다.

여기서 의문점이 있을것인데요.

람다로 과연 프로그램 다운 프로그램을 짤 수 있을까요?

이 의문은 지금까지 다룬 식들이 대부분 산술 연산이었기 때문에 나오는 질문일 것입니다.

우리가 흔히 프로그래밍 이라고 하는것은,

1. 어떤 조건에 따라 분기를 해야 하고, 조건에 따라 다른 기능이 수행 되는 것을 의미할 것입니다.

C 코드로 보면,

if (a==10)

    {c=20;} 

else 

    {c=0;} 

흔히 이런 코드를 

    1+1 

보다 프로그램 답다고 생각 할 것입니다.

(당연하죠. 조건문이 논리식이고 그 논리 식에 따라 코드가 분기 되는 것이지만, 그것은 매우 저 수준의 생각이고, 흔히 조건 자체를 논리로 보기 보다는 어떤 상황이나 상태로 보는 경향이 있기 때문일 것입니다. 뭐 여하튼, 우리가 언어의 base를 다루기 때문에 이런 것도 짚어봐야겠죠.)

다시 예기 하면, 논리 식에 따라 코드 분기가 가능한가? 라는 질문으로 단순화 시켜볼 수 있을것입니다.

그 식을 if e1 e2 e3  라고 하고, e1이 true이면 e2를 아니면 e3를 처리하면 되겠군요.

그전에 람다 언어에서 true 와 false에 대해서 정의가 필요합니다.

true = λx.λy.x

false = λx.λy.y

입니다.

하는김에 몇개 더 가져와 보겠습니다.

not = λb.λx.λy.byz

and = λb.λb'.λx.λy.b(cxy)y

iszero = λn.λx.λy.n(λz.y)x  or  λn.n (λx.FALSE) TRUE

succ = λn.λf.λx.f(nfx)

자 이제 준비가 되었습니다.

if e1 e2 e3  -> (e1 e2) e3

                  -> e1' e2 e3

                          1)  -> true e2 e3

                          2)  -> false e2 e3

1) true e2 e3  = (λx.λy.x)e2 e3

                  = (λy.e2) e3  ----> beta reduction 수행을 위해서 e3를 y에 집어넣으려 하지만 몸체에는 y가 없기 때문에 사라짐.

                  = e2

2) false e2 e3 = ( λx.λy.y) e2 e3  ------------> e2를 x에 대입. 그러나 x가 없음 e2는 사라짐

                  = (λy.y)e3

                  = e3

if e1 e2 e3 --> iszero e1 e2 e3

이렇게 해보니 그럴듯 하죠 . 언어같죠.. 람다 문법은 굉장히 단순하면서 프로그래밍 언어가 가지는 요소들을 다 품고 있습니다.

loop 을 구현하기 위해서는 기본적으로 재귀호출이 되어야 합니다.

아래와 같은 형식으로 람다에서 구현이 가능합니다.

In ML, C, Java & etc.

fun fac(n) = 

          if n=0 then 1

          else n*fac(n-1)

In λ-Calculus

      fac = Y(λf.λn. if n=0 1 n*f(n-1) )

      Y = λf.(λx.f(x x))(λx.f(x x))

Then 

     fac  n -> n!

언어 키우기.. M0

람다를 프로그래밍 언어로 바라봅시다. (이글 초반에 이미 그러자고 예기 했었죠? ^^)

λx.E 는 함수 정의로 봅시다. 그런데 함수 이름은 없습니다. 인자가 x이고 몸통이 E인 함수입니다. E1 E2는 함수를 적용하는 식입니다.

람다에서 계산과 프로그램에서의 실행은 조금 다릅니다. 람다에서 계산의 끝은 식의 모든 구석구석에 레덱스가 없는 경우입니다. 

함수식 λx.E 의 몸통 식 E에도 레덱스가 있다면 몸통식은 계산이 됩니다.

프로그램 에서는 λx.E 가 최종 값입니다. 몸통 E의 실행은 그 함수가 호출될때 비로소 시작됩니다.

이 최종값인  λx.E를 기준식 (canonical term)이라고 부릅니다.

기준식이 값이기 때문에 종종 υ("value" : upsilon)로 표기 합니다. 

소극적 실행 Lazy evaluation 과 적극적 실행 Eager evaluation

앞에서 β- reduction 과정에서 순서가 중요하다는 예기를 했었는데, 그것과 관련 있는 예기입니다.

프로그램이 실행되면서 함수는 자체로 값이 됩니다.  함수의 몸통은 그 함수가 호출될때 비로소 실행될 뿐입니다.

여기서 함수가 호출될때 E1 E2 ,  인자식 E2를 언제 실행해주기로 해야 할까요?

두가지 선택이 있을 것입니다. 몸통을 실행하면서 인자 값이 필요할 때에 인자 식을 실행하거나, 몸통을 실행하기 전에 인자 식을 실행해서 인자 값을 구한 후에 몸통을 실행하거나. 이 두가지 선택을 할 수 있을 것입니다.

첫번째 경우를 소극적 실행 Lazy evaluation, normal-order evaluation , 또는 식 전달 호출 방식 call-by-name, call-by-need 라고 합니다.

두번째 방식을 적극적 실행 Eager evaluation 혹은 값 전달 방식 call-by-value 라고 합니다.

람다 언어(우리가 람다 계산식을 바탕으로 키워가고 있는 언어) 에서 실행 방식을 정의하는 규칙은 다음과 같습니다.

Lazy evaluation	Eager evaluation

각각의 장단점이 있습니다.

소극적인 실행으로 적극적인 실행 보다 빨리 계산 되는 경우가 있고, 반대의 경우도 있습니다.

소극적으로 실행하면

   (λx.7)((λx.x x)(λx.x x)) =>N 7

이지만 적극적으로 실행하면

(λx.7)((λx.x x)(λx.x x)) =>E (λx.7)((λx.x x)(λx.x x))

                                   =>E :

영원히 돌게 됩니다.(무한 루프)

반면,

아래를 소극적으로 실행하면,

   ((λx.(x..x))E =>N (E..E) =>N .....

E를 두번 실행해야 하지만,적극적으로 실행하면, 한번만 실행됩니다.

((λx.(x..x))E =>E (λx.(x..x)) υ =>E ( υ.. υ) =>E ...

람다언어의 문법을 시작합시다.

                

1. 이 언어에서 이름 지을 수 있는 것은 값 뿐입니다. 이것을 변수라고 합니다.

2. 변수 x 의 유효범위는 그 이름을 묶은 함수 λx.E 의 몸통 E입니다.

3. 각 변수가 무슨값을 뜻하는지는 그 변수를 묶은 함수가 호출될 때 전달되는 인자 값이 그 변수가 뜻하는 값이 됩니다.

의미 정의는 프로그램 텍스트를 변화시키지 않으면서 정의합시다.

                    

"환경 σ(sigma) 에서 식 E는 값 υ를 계산한다" 는 뜻힙니다.

의미정의에서 환경을 따로 가지는 이유는 프로그램 식을 변경하지 않기 때문입니다.

변수는 그대로 프로그램에 남아 있는 것이죠. 예전처럼 프로그램 이름이 텍스트에서 해당 값으로 바꿔써지는 방식이 아닙니다.

값은 정수와 함수 뿐입니다. 

함수 값을 클로져(closure)라고 하는데, 함수  λx.E 텍스트 자체와 그 함수가 정의될 때 (static scope)의 환경입니다.

환경의 역할은  λx.E에서 자유로운 변수들의 값을 결정해주는 것입니다.

           

의미 규칙들은  적극적인 실행 규칙(Eager evaluation)을 같습니다.

언어키우기 M1

M0 를 가지고 모든 프로그램을 짤 수 있지만 불편합니다.

프로그래밍의 편의를 위해서 설탕을 좀 첨가할 필요가 있습니다. 설탕구조(syntactic sugar)

 

정수, 참/거짓

추가하고 싶은것들은 정수, 참/거짓, 재귀함수 rec f λx.E, 조건식 if E E E, 그리고 덧셈식 E+E

동치식  E=E. 등입니다.

                               

가령 let x=E1 in E2  의 경우  (λx.E2)E1 이지만 사용하기 편리하게 그 자체로 그대로 둡시다.

이제 값들은 세종류가 되었습니다. 함수값과 정수 그리고 참/거짓

                               

 구조가 있는 값 : 쌍 pair

구조를 가진 데이타를 프로그래밍하기 쉽게 하자.

쌍을 만들고 사용하는 방식을 제공합니다.

                                           

이제 값들은 세가지 종류가 있습니다. 함수값, 정수, 참/거짓,혹은 두값의 쌍

쌍을 M0로 표현하면

(E1,E2) =  λm.(mE1)E2

E.1 = E( λx. λy.x)

E.2 = E( λx. λy.y)

로 풀어서 쓸수 있습니다.

이 쌍을 이용해서 리스트, 나무구조(tree), 그래프도 표현할 수 있고 함수나 테이블도 표현할 수 있습니다.

리스트를 구현해보면 다음과 같습니다.

     λx.λlst.(x,lst)

"link 1 nil" 은 1 하나있는 리스트[1]

"link 1 (link 2 nil)" 은 [1,2]인 리스트를 만듭니다.

isNil?                              head                   tail           

λlst.(lst=nil)                    λlst.(lst.1)          λlst.(lst.2)

두갈래 나무구조 binary tree 를 구성해봅시다.

empty                     leaf              node

0                              λx.x                λlt. λrt.(link lt rt)

isEmpty?                 left                right

 λt.(t=empty)         λt.(t.1)          λt.(t.2)

다음 >> 값 중심의 언어- 메모리 주소 값 : 명령형 언어의 모습