기말4] 함수형 프로그래밍

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

 

 함수형 프로그래밍에서,
  함수는 입력(Domain)을 출력(Range)으로 변환하는 것,
  변수는 메모리를 가리키지 않고 수학적 기호로 사용된다.

 Pure Functional Programming 에서는 상태의 개념이 없고(State-free) 이에 따라 저장문도 필요하지 않다.
변수가 존재하지 않으므로 루프의 상태를 이루는 변수의 증감이 불가능하므로, 루프는 재귀에 의해 표현된다.
또한, 함수형 언어는 함수의 출력값이 인수값에만 의존하는 참조 투명성을 가지므로, 프로그램의 작동을 증명하기 쉽다.

※ 최근의 함수형 언어는 실용성을 위해 변수, 저장, 루프를 지원하므로 순수하지 않다(Impure).

 

---

 

람다식

 

람다식은 매개변수와 함수의 정의는 명세하지만 이름은 명시하지 않는다.

 

• Square(n) = n * n; 함수를 람다식으로 표현하면 ( λx ˑ x * x )이다.
  - 이 때, Square 함수는 실수 집합에 대해 모두 정의된 'total 함수'다. // Square: R -> R || R은 실수집합
  - 람다식에서 사용되는 변수는 bound 변수, 사용되지 않는 변수는 free 변수이다.
  - 람다식은 계산 과정은 포함되지 않으나, 함수형 언어에서는 계산 과정까지 포함된다.
  
  
• 순수 람다 계산식의 구문 구조
  - LambdaExpression → variable // 임의의 식별자는 람다식이다.
  - LambdaExpression → ( M N ) // M과 N이 람다식이면, M을 N에 적용(applicaiton)한다.
  - LambdaExpression → ( λ Variable ˑ M ) // 식별자가 있고, M이 람다식이면, 이렇게 추상화(abstraction)된다.
  
  
• M의 변수 x를 계산식 N으로 대치(Substitution)
  
  • 람다식 '( ( λx ˑ M ) N )'의 의미는 베타 축약(Beta-reduction)에 따라 'M[x ← N]'으로 간략화할 수 있다.
    - 이 때, N의 모든 free 변수는 M의 같은 이름의 free 변수로 대체한다.
    - M의 bound 변수는 μ로 대체한다.
    
  • LambdaExpression → variable // x [ x ← y ] = y,  xz [ x ← y ] = yz
    
  • LambdaExpression → ( λ Variable ˑ M ) // (λx ˑ (zx)) [x←y] = (λμ ˑ (zμ)) [x ← y] = (λμ ˑ (zμ))
    
    
• 인수가 계산되는 시점
  - 적극적 계산법(Eager Evaluation) : 인수가 호출될 때 계산된다. ( = call by Value )
  - 지연 계산법(Lazy Evaluation) : 인수가 사용될 때 계산된다. ( = call by Name )
  
  
• 함수의 상태
  - 명령형, 객체지향형 언어에서의 함수는 변수보다 낮은 다양성을 가진다.
  - 함수형 언어에서의 함수는 변수와 같이 일반적인 값으로 취급된다.
    고차함수(Functional) : 함수 이름이 인수로 전달될 수 있으며, 함수가 함수를 결과로 반환할 수도 있다.
    ex] g(square, [2, 3, 5]) = [4, 9, 25]; // 뒤 쪽 배열([2, 3, 5])에 대해, 앞의 함수(square)를 실행한다.

 

 

 

---

 

스킴 ( Scheme )

 

  스킴은 Lisp의 변종 언어로, 지정문이 있기 때문에 순수한 함수형 언어는 아니다. Turing Complete하다.

 함수형 프로그래밍과 절차적 프로그래밍을 지원하는 다중 패러다임 프로그래밍 언어다.

 

---

 

1. 스킴의 실행

 

스킴의 식에서는 캠브리지 전위 표기법을 사용한다.
스킴에서 주석(Comment)은 ; 로 구분한다.

 

• 스킴의 식 ( Expression )
  • Expression Examples
    - ( + 2 2 )  // 2 + 2
    - ( + ( * 5 4 ) ( - 6 2 ) )  // (5 * 4) + (6 - 2)
    - ( define ( Square x ) (* x x ) ) // 함수 선언, Square(x) = x*x;
    - ( define f 120 )  // 전역 변수 선언, f = 120;
    
    
• 스킴의 식 계산법 ( Expression Evaluation )
  - 변수는 활성 레코드에 검사해 값으로 변환한다.
  - 함수는 전위 표기법으로 해석해 실행한다. 이 때, 연산자도 함수로 취급한다. // ( * 5 4 )의 *는 곱하기 함수
  - 상수는 그 자체로 실행된다.
  
  
  • Expression Evaluation Examples ( x = 5 )
    - x  // = 5 
    - ( + ( * x 4 ) ( - 6 2 ) )  // ( 5 * 4 ) + ( 6 - 2 ) = 24
    - 5  // type Int, value 5
    - '5  // type String, value "5", 앞의 '표시가 문자열을 알리는 표시다.
    
    
• 스킴의 배열 ( Lists )
  - 배열은 소괄호에 의해 감싸지며, 함수와 데이터의 형태를 모두 정의할 수 있다. // 데이터는 앞에 '가 붙는다.
  - 빈 배열은 ( ) 로 표기한다.
  - 각 배열의 항목은 값과 그 다음 항목의 포인터를 가진다.
  
  
  • List Example]  '( 0 2 4 6 8 )
    
    
  • 배열과 관련된 연산 ( List Transforming Functions )
    - ( define evens '(0 2 4 6 8) ) // [함수 선언] evens = {0, 2, 4, 6, 8};
    - ( car evens ) // [배열의 첫 원소]  0
    - ( cdr evens ) // [첫 원소를 제외한 배열]  (2 4 6 8)
    - ( cadr evens ) // [cdr -> car] 2
    - ( cons 1 ( cdr evens ) ) // [배열 앞에 상수 넣기] (1 2 4 6 8)
    - ( null? '() ) // [리스트가 비었는가?] #t  (True)
    - ( equals? 5 '(5) ) // [두 개가 같은가?] #f  (False) ( 5 = int, '(5) = list )
    - ( append '(1 3 5) evens ) // [두 배열을 합친다] (1 3 5 0 2 4 6 8)
    - ( list '(1 3 5) evens ) // [배열을 만든다] ( (1 3 5) (0 2 4 6 8) )
    
    
• 스킴의 기본 값 ( Elementary Values )
  - Numbers // 숫자  [ integers = 정수형, floats = 실수형, rationals = 분수형 ]
  - Symbols // 변수
  - Characters, Strings // 문자열
  - Functions // 함수
  ※ (list? value) // value가 list인가?
  ※ (symbol? name) // name이 변수인가?
  
  
• 스킴의 제어 흐름 ( Control Flow )
  
  
  • 조건문 ( Conditional )
    (if ( < x 0 ) ( - 0 x )) // [ if cond then-part ] cond가 #t면 then-part를 실행한다.
    (if ( < x y ) x y ) // [ if cond then-part else-part ] cond가 #t면 then-part, #f면 else-part를 실행한다.
    
    
  • Case Selection
    (case (% x 2) ((0) 'even) ((1) 'odd) (else 'err))
    // [ case variable case1 case2 ... else-case ], each case = [ cases value ]
    // variable이 각 case의 cases list에 들어있으면, 해당 case의 value를 반환한다.
    
    
• 스킴의 함수 정의 ( Defining Functions )
  - ( define ( name arguments ) body )
  - 소괄호의 짝이 모두 맞는지 유의할 것.
  
  
  • Function Example] Subst(v1, v2, list) // list의 모든 원소에 대해 v2를 v1으로 대체한다.
    

// subst(y, x, alist)를 선언한다.
(define (subst y x alist)
// alist는 null인지 검사한다. #t일시 빈 배열을 반환한다.
	(if (null? alist) '()
    // #f일시, alist의 첫 번째 원소가 x와 같은지 검사한다.
		(if (equal? x (car alist))
			// #t일시, y + 뒤쪽 배열을 subst한 결과
			(cons y (subst y x (cdr alist)))
			// #f일시, 첫 번째 원소 + 뒤쪽 배열을 subst한 결과를 반환한다.
			(cons (car alist) (subst y x (cdr alist)))
		)
	)
)
// (subst 'x 2 '(1 (2 3) 2)) = (1 (2 3) x)

 

 

• 스킴의 Let 식 ( Let Expression )
  - 지역변수와 비슷하며, 공통으로 사용되는 계산식에 이름을 붙여준다.
  - 위의 subst 함수의 예시에서, ( let ( (head (car alist)) (tail (cdr alist)) function-body)라고 정의하면,
    (cons y (subst y x (cdr alist))) → ( cons y (subst y x tail) )
    (cons (car alist) (subst y x (cdr alist))) → ( cons head (subst y x tail) )
    로 변경하여 가독성을 높일 수 있다.
  
  

 

 

 

---

 

 

2. CLite의 의미구조 ( with Scheme )

앞에서 Java로 만들었던 CLite Semantics를 Scheme로 정의해보자.

 

• [Java] State = {<var1, val1>, <var2, val2>, ..., <vark, valk>};
  - [Scheme] State = ( (var1 val1) (var2 val2) ... (vark valk) )
  
  
• [Java] State.get(id);
  - [Scheme]

(define (get id state)
	// car state = (var, val) | caar state = var [ => state[0][0].equals(id) ]
	(if (equal? id (caar state))
		// #t -> car state = (var, val) | cdar state = (val) | cadar state = val
		// [ => return state[0][1]; ]
		(cadar state)
		// #f -> state[1] 탐색
		(get id (cdr state))
	)
)

 

• [Java] State.onion(id, val);
  - [Scheme]

(define (onion id val state)
	// car state = (var, val) | caar state = var [ => state[0][0].equals(id) ]
	(if (equal? id (caar state))
		// #t -> ( (id val) state[1]... ) 
		(cons (list id val) (cdr state))
		// #f -> ( state[0] onionResultList... )
		(cons (car state) (onion id val (cdr state)))
	)
)

 

•  [CLite] Statements -> Skip | Block | Assignment | Conditional | Loop
  - [Scheme]

// Statement * State -> State
(define (m-statement statement state)
	(case (car statement)
		( (skip) (m-skip statement state) )
		( (block) (m-block statement state) )
		( (assignment) (m-assignment statement state) )
		( (conditional) (m-conditional statement state) )
		( (loop) (m-loop statement state) )
		( else () )
	)
)

// Skip * State -> State
(define (m-skip statement state) state)

// Block * State -> State
(define (m-block statement state)
	(if (null? statement)
		// statement가 빈 리스트면 state 반환
		state
		// 빈 리스트가 아니라면 statement[0]을 실행한 후,
		// 그 결과 state와 statement[1]로 m-block을 실행한다. (재귀로 반복)
		(m-block (cdr statement) (m-statement (car statement) state))
	)
)

// Assignment * State -> State
(define (m-assignment statement state)
	// id = statement[0], val = expr(statement[1]) 을 state와 onion한다.
	(onion (car statement) (m-expression (cadr statement) state)) state)
)

// Conditional * State -> State
(define (m-conditional statement state)
	// statement[0] (= cond)를 계산해서, true면 statement[1], false면 statement[2]를 실행한다.
	(if (m-expression (car statement) state)
		(m-statement (cdr statement) state)
		(m-statement (cddr statement) state)
	)
)

// Loop * State -> State
(define (m-loop statement state)
	// statement[0] (= cond)를 계산해서, #t면 재귀, #f면 탈출
	(if (m-expression (car statement) state)
		(m-loop statement (m-statement (cdr statement) state))
		state
	)
)

 

• [CLite] Expression -> Value | Variable | Binary | Unary
  - [Scheme]

// Unary 연산에 대해서는 생략됬다.
(define (m-expression expr state)
	(case (car expr)
		( (value) (cadr expr) ) // expr = <value, val>
		( (variable) (get (cadr expr) state) ) // expr = <variable, name>
		( else (applyBinary (car expr) (cadr expr) (caddr expr) state) )
	)
)

// 이항 연산의 정의
(define (applyBinary op left right state)
	// 식의 좌항과 우항을 연산한 후 let 식을 이용해 단순화한다.
	(let ( (leftVal (m-expression left state)) (rightVal (m-expression right state)))
	// 연산자 op와 case문을 이용해 연산결과를 반환한다.
		(case op
			// 산술 연산자 - Arithmetic
			( (plus) (+ leftVal rightVal) )
			( (minus) (- leftVal rightVal) )
			( (times) (* leftVal rightVal) )
			( (div) (/ leftVal rightVal) )
			// 관계 연산자 - Relational
			( (lt) (< leftVal rightVal) )
			( (le) (<= leftVal rightVal) )
			( (eq) (equals? leftVal rightVal) )
			( (ne) (not (equals? leftval rightVal)) )
			( (gt) (> leftVal rightVal) )
			( (ge) (>= leftVal rightVal) )
		) // case end
	) // let end
) // define end
// lt = less than, le = less equals, gt = greater than, ge = greater equals

 

---

스킴으로 미분(Differential) 함수를 만들어 보자.
'2x+1'의 미분 결과는 '2 * 1 + 1 * 0'

 
[ define 'diff(x expr)' function ]

// x는 미분 대상 변수, expr은 미분 대상 식
(define (diff x expr)
	// [if-01] expr가 list가 아닐 때, x == expr이라면 1, 아니라면 0을 반환한다.
	(if (not (list? expr)) 
		(if (equals? x expr) 1 0)
		// [if-01] expr가 list일 때, op = expr[0], u = expr[1], v = expr[2] 
		(let ( (u (cadr expr)) (v (caddr expr)) )
			(case (car expr)
				( (+) (list '+ (diff x u) (diff x v) )
				( (-) (list '- (diff x u) (diff x v) )
				( (*) (list 
					'+ 
					(list '* u (diff x v))
					(list '* v (diff x u))
				) )
				( (/) (list
					'div
					(list '- (list '* v (diff x u)) (list '* u (diff x v)))
					(list '* u v)
				) )
			) // case end
		) // let end
	) // if-01 end
) // define end

[ Tracing : 2x² - 3x + 1 ]

• 전위 표기법으로 변환
  ( + ( - ( * 2 ( * x x ) ) ( * 3 x  ) ) 1 )
  
  
• diff(x, (+ (- (* 2 (* x x)) (* 3 x)) 1)
  • [IF-0] (+ (- (* 2 (* x x)) (* 3 x)) 1) 는 list인가? #t
    • [ u = (- (* 2 (* x x)) (* 3 x)) ] [ v = 1 ]
      - (car expr) = +
      
      • diff(x, (- (* 2 (* x x)) (* 3 x))) // (diff x u)
        • [IF-0-1] (- (* 2 (* x x)) (* 3 x)) 는 list인가? #t
          • [ u = (* 2 (* x x)) ] [ v = (* 3 x) ]
            - (car expr) = -
            - list
            • '-
              
            • diff(x, (* 2 (* x x))) // (diff x u)
              • [IF-0-1-2] (* 2 (* x x)) 는 list인가? #t
                • [ u = 2 ] [ v = (* x x) ]
                  - (car expr) = *
                  - list
                  • '+
                  • (list '* 2 diff(x, (* x x))) // (list '* u (diff x v))
                    
                    • [IF-0-1-2-3] (* x x)는 list인가? #t
                      
                      • [ u = x ] [ v = x ]
                        - (car expr) = *
                        - list
                        • '+
                        • (list '* x diff(x, x)) // (list '* u (diff x v))
                          
                          • [IF-0-1-2-3-4] x 는 list 인가? #f
                            - (x == x) #t : return 1;
                            ∴ (* x 1) [/IF-4]
                        • (list '* x diff(x, x)) // (list '* v (diff x u))
                          • [IF-0-1-2-3-4] x 는 list 인가? #f
                            - (x == x) #t : return 1;
                            ∴ (* x 1) [/IF-4]
                            
                      • ∴ (* 2 (+ (* x 1) (* x 1)) [/IF-3]
                        
                  • (list '* (* x x) diff(x, 2)) // (list '* v (diff x u))
                    • [IF-0-1-2-3] 2 는 list인가? #f
                      - (x == 2) #f : return 0
                      ∴ (* (* x x) 0) [/IF-3]
              • ∴ (+ (* 2 (+ (* x 1) (* x 1)))(* (* x x) 0)) [/IF-2]
            •  diff(x, (* 3 x)) // (diff x v)
              
              • [IF-0-1-2] (* 3 x) 는 list인가? #t
                
                • [ u = 3 ] [ v = x ]
                  - (car expr) = *
                  - list
                  
                  
                  • '+
                    
                    
                  • (list '* 3 diff(x, x)) // (list '* u (diff x v))
                    • [IF-0-1-2-3] x 는 list인가? #f
                      - (x == x) #t : return 1
                      ∴ (* 3 1) [/IF-3]
                      
                      
                  • (list '* x diff(x, 3)) // (list '* v (diff x u))
                    • [IF-0-1-2-3] 3 은 list인가? #f
                      - (x == 3) #f : return 0
                      ∴ (* x 0) [/IF-3]
                      
                      
              •  ∴ (+ (* 3 1) (* x 0)) [/IF-2]
                
                
          •  ∴ (- (+ (* 2 (+ (* x 1) (* x 1))) (* (* x x) 0)) (+ (* 3 1) (* x 0)) ) [/IF-1]
            
        • diff(x, 1) // (diff x v)
          • [IF-0-1] 1 은 list인가? #f
            - (x == 1) #f : return 0
            ∴ 0 [/IF-1]
            
            
    • ∴ (+ (- (+ (* 2 (+ (* x 1) (* x 1))) (* (* x x) 0)) (+ (* 3 1) (* x 0)) ) 0 ) [/IF-0]
      
      
      
  • diff 함수의 실행 결과는
    (+ (- (+ (* 2 (+ (* x 1) (* x 1))) (* (* x x) 0)) (+ (* 3 1) (* x 0)) ) 0 ) 다.
    
    • 검증 ( 기대 값 : 4x - 3 )
      - ■ (+ (- (+ (* 2(+ (x) (x))) (* (* x x) 0)) (+ (* 3 1) (* x 0)) ) 0 )
      - ■ (+ (- (+ (4x) (0)) (+ (3) (0)) ) 0 )
      - ■ (+ (- (4x) (3) ) 0 )
      - ■ (+ (4x-3) 0 )
      - ■ 4x-3

 

 

---