[oop] 함수형 프로그래밍 언어는 어떻게 작동합니까?

Program / 글쓴이

함수형 프로그래밍 언어가 상태를 저장할 수없는 경우 사용자의 입력을 읽는 것과 같은 간단한 작업을 어떻게 수행합니까? 어떻게 입력을 “저장”합니까 (또는 해당 문제에 대한 데이터를 저장합니까?)

예를 들어,이 간단한 C가 어떻게 Haskell과 같은 함수형 프로그래밍 언어로 번역 될까요?

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

(제 질문은 “명사의 왕국에서의 실행”이라는 훌륭한 게시물에서 영감을 받았습니다.이 글을 읽으면 정확히 객체 지향 프로그래밍이 무엇인지, Java 가이를 극단적 인 방식으로 구현하는 방법, 함수형 프로그래밍 언어가 대조.)

답변

함수형 프로그래밍 언어가 상태를 저장할 수없는 경우 사용자로부터 입력을 읽거나 (이를 “저장”하는 방법) 그 문제에 대한 데이터를 저장하는 것과 같은 간단한 작업을 어떻게 수행합니까?

수집 한대로 함수형 프로그래밍에는 상태가 없지만 그렇다고 데이터를 저장할 수 없다는 의미는 아닙니다. 차이점은 내가 (Haskell) 문장을 다음과 같이 쓰면

let x = func value 3.14 20 "random"
in ...

의 값 x은 항상 동일 하다는 것을 보장 합니다 .... 아무것도 변경할 수 없습니다. 마찬가지로 함수 f :: String -> Integer(문자열을 가져와 정수를 반환하는 함수)가있는 경우 f인수를 수정하거나 전역 변수를 변경하거나 파일에 데이터를 쓰는 등의 작업을 수행하지 않을 것이라고 확신 할 수 있습니다 . sepp2k가 위의 주석에서 말했듯이,이 불변성은 프로그램에 대한 추론에 정말 도움이됩니다. 데이터를 접고, 회전시키고, 절단하는 함수를 작성하고, 함께 연결할 수 있도록 새 복사본을 반환하고, 이러한 함수 호출 중 “유해한”작업을 수행 할 수 있습니다. 당신은 그것이 x항상 있다는 것을 알고 있으며 x, 누군가 x := foo bar가 선언 사이 어딘가에 썼다고 걱정할 필요가 없습니다.x 불가능하기 때문입니다.

이제 사용자의 입력을 읽으려면 어떻게해야합니까? KennyTM가 말했듯이, 불순한 함수는 전 세계를 인수로 전달하고 그 결과와 세계를 모두 반환하는 순수 함수라는 아이디어입니다. 물론 실제로이 작업을하고 싶지는 않습니다. 한 가지는 끔찍하게 투박하고 다른 한 가지는 동일한 월드 객체를 재사용하면 어떻게 될까요? 그래서 이것은 어떻게 든 추상화됩니다. Haskell은 IO 유형으로 처리합니다.

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

이것은 main아무것도 반환하지 않는 IO 액션 임을 알려줍니다 . 이 동작을 실행하는 것은 Haskell 프로그램을 실행한다는 의미입니다. 규칙은 IO 유형이 IO 작업을 벗어날 수 없다는 것입니다. 이 맥락에서 우리는 do. 따라서 두 가지 방식으로 생각할 수 getLine있는를 반환합니다 IO String. 첫째, 실행시 문자열을 생성하는 작업으로; 둘째, 불순하게 획득 되었기 때문에 IO에 의해 “오염 된”문자열입니다. 첫 번째가 더 정확하지만 두 번째가 더 도움이 될 수 있습니다. (가) <-소요 String의 외부 IO String에 저장 그것을 str우리가 IO 작업에있어 이후 -하지만, 우리는 그래서 “탈출”할 수 없습니다, 그것은 백업 포장해야합니다. 다음 줄은 정수 ( reads) 읽기를 시도 하고 첫 번째 성공한 일치 항목 (fst . head); 이것은 모두 순수 (IO 없음)이므로 let no = .... 우리는 모두 사용할 수 있습니다 no및 str에를 .... 따라서 우리는 불순한 데이터를 저장 (에서 한 getLine에 str) 순수 데이터 ( let no = ...).

IO 작업을위한이 메커니즘은 매우 강력합니다. 프로그램의 순수하고 알고리즘적인 부분을 불순한 사용자 상호 작용 측면에서 분리하고이를 유형 수준에서 적용 할 수 있습니다. 귀하의 minimumSpanningTree기능은 가능성이 코드에서 다른 곳에서 뭔가를 변경하거나 사용자에게 메시지를 작성하고, 등등 수 없습니다. 안전합니다.

이것이 Haskell에서 IO를 사용하기 위해 알아야 할 전부입니다. 그게 전부라면 여기서 멈출 수 있습니다. 그러나 그것이 작동 하는 이유 를 이해하고 싶다면 계속 읽으십시오. (또한이 내용은 Haskell에만 해당됩니다. 다른 언어는 다른 구현을 선택할 수 있습니다.)

그래서 이것은 아마도 약간의 속임수처럼 보였고 어떻게 든 순수한 Haskell에 불순물을 추가했습니다. 그러나 그렇지 않습니다. 순수 Haskell 내에서 IO 유형을 완전히 구현할 수 있습니다 (를 제공하는 한 RealWorld). 아이디어는 이것이다 : IO 액션 IO type은 RealWorld -> (type, RealWorld)실제 세계를 취하고 유형의 객체 type와 수정 된 객체를 모두 반환 하는 함수와 동일 합니다 RealWorld. 그런 다음 몇 가지 함수를 정의하여 정신 나간 일없이이 유형을 사용할 수 있습니다.

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

첫 번째는 우리가 아무것도하지 않는 IO 액션에 대해 이야기 할 수있게합니다 : return 3IO 액션은 실제 세계를 쿼리하지 않고 3. >>=“bind”라고 발음 하는 연산자를 사용하면 IO 작업을 실행할 수 있습니다. IO 액션에서 값을 추출하고 함수를 통해 실제 세계에 전달하고 결과 IO 액션을 반환합니다. >>=IO 작업의 결과는 절대 탈출 할 수 없다는 규칙 을 적용합니다.

그런 다음 위 main를 다음과 같은 일반적인 기능 응용 프로그램 집합으로 바꿀 수 있습니다 .

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

Haskell 런타임 main은 초기 RealWorld에서 시작 하여 설정되었습니다! 모든 것이 순수하고 멋진 구문이 있습니다.

[ 편집 : @Conal이 지적했듯이 이것은 실제로 Haskell이 IO를 수행하는 데 사용하는 것이 아닙니다. 이 모델은 동시성을 추가하거나 실제로 IO 작업 중에 세계가 변경되는 방식을 추가하면 중단되므로 Haskell이이 모델을 사용하는 것은 불가능합니다. 순차 계산에만 정확합니다. 따라서 Haskell의 IO는 약간의 닷지 일 수 있습니다. 그렇지 않더라도 확실히 이렇게 우아하지는 않습니다. @Conal의 관찰에 따르면, Tackling the Awkward Squad [pdf] , 섹션 3.1 에서 Simon Peyton-Jones의 말을 참조하십시오 . 그는 이러한 라인을 따라 대체 모델에 해당 할 수있는 것을 제시하지만 복잡성 때문에이를 삭제하고 다른 방법을 사용합니다.]

다시 말하지만, 이것은 IO와 일반적으로 변경 가능성이 하스켈에서 어떻게 작동하는지 (거의) 설명합니다. 경우 이 당신이 알고 싶은 모든 것입니다, 당신은 여기 읽는 중지 할 수 있습니다. 마지막으로 한 번의 이론을 원하신다면 계속 읽으십시오. 그러나이 시점에서 우리는 귀하의 질문과는 거리가 멀었습니다.

마지막으로 한 가지 :이 구조 ( returnand가 있는 매개 변수 유형) >>=는 매우 일반적입니다. 그것은 모나드라고 불리며, do표기법 return, 그리고 >>=그들 중 하나와 함께 작동합니다. 여기에서 보셨 듯이 모나드는 마법이 아닙니다. 마법의 전부는 do블록이 함수 호출로 바뀌는 것입니다. RealWorld유형은 우리가 어떤 마법을 볼 수있는 유일한 장소입니다. []목록 생성자 인, 같은 유형 도 모나드이며 불순한 코드와 관련이 없습니다.

이제 모나드의 개념에 대한 모든 것을 (거의) 알고 있지만 (만족해야하는 몇 가지 법칙과 공식적인 수학적 정의를 제외하고) 직관이 부족합니다. 온라인에는 엄청나게 많은 모나드 자습서가 있습니다. 내가 좋아하는 이 하나 ,하지만 당신은 옵션이 있습니다. 그러나 이것은 아마도 당신에게 도움이되지 않을 것입니다 ; 직관을 얻는 유일한 방법은 그것들을 사용하고 적시에 몇 개의 튜토리얼을 읽는 것입니다.

그러나 IO를 이해하기 위해 직감이 필요하지는 않습니다 . 전체적으로 모나드를 이해하는 것은 매우 중요하지만 지금 당장 IO를 사용할 수 있습니다. 첫 번째 main기능을 보여 드린 후에 사용할 수 있습니다 . IO 코드를 불순한 언어로 취급 할 수도 있습니다! 그러나 근본적인 기능적 표현이 있다는 것을 기억하십시오. 아무도 속임수를 쓰지 않습니다.

(추신 : 길이에 대해 죄송합니다. 조금 멀리갔습니다.)

답변

여기에 좋은 답변이 많지만 길다. 도움이되는 짧은 대답을하려고합니다.

  • 기능적 언어는 C와 동일한 위치 (명명 된 변수 및 힙에 할당 된 객체)에 상태를 둡니다. 차이점은 다음과 같습니다.

    • 함수형 언어에서 “변수”는 범위에 들어 오면 (함수 호출 또는 let-binding을 통해) 초기 값을 가져오고 그 값은 나중에 변경되지 않습니다 . 마찬가지로 힙에 할당 된 객체는 모든 필드의 값으로 즉시 초기화되며 이후에는 변경되지 않습니다.

    • “상태 변경”은 기존 변수 나 개체를 변경하는 것이 아니라 새 변수를 바인딩하거나 새 개체를 할당하여 처리합니다.

  • IO는 트릭으로 작동합니다. 문자열을 생성하는 부작용 계산은 World를 인수로 사용하고 문자열과 새 World를 포함하는 쌍을 반환하는 함수에 의해 설명됩니다. The World에는 모든 디스크 드라이브의 내용, 지금까지 보내거나받은 모든 네트워크 패킷의 기록, 화면의 각 픽셀의 색상 등이 포함됩니다. 트릭의 핵심은 세계에 대한 접근이 신중하게 제한되어

    • 어떤 프로그램도 세계의 복사본을 만들 수 없습니다 (어디에 두시겠습니까?).

    • 어떤 프로그램도 세상을 버릴 수 없습니다

    이 트릭을 사용하면 시간이 지남에 따라 상태가 진화하는 하나의 고유 한 World가있을 수 있습니다. 기능적 언어로 작성 되지 않은 언어 런타임 시스템 은 새 World를 반환하는 대신 고유 한 World를 제자리에 업데이트하여 부작용 계산을 구현합니다.

    이 트릭은 Simon Peyton Jones와 Phil Wadler가 획기적인 논문 “Imperative Functional Programming” 에서 아름답게 설명합니다 .

답변

더 많은 공간을 제공하기 위해 새 답변에 대한 댓글 답글을 끊습니다.

나는 썼다 :

내가 말할 수있는 한,이 IO이야기 ( World -> (a,World))는 Haskell에 적용될 때 신화입니다. 그 모델은 순전히 순차 계산만을 설명하고 Haskell의 IO유형은 동시성을 포함합니다. “순수 적으로 순차”라는 것은 세계 (우주)조차도 그 계산으로 인한 것 외에 명령형 계산의 시작과 끝 사이에 변경 될 수 없다는 것을 의미합니다. 예를 들어 컴퓨터가 흔들리는 동안 뇌 등은 그렇게 할 수 없습니다. 동시성은 World -> PowerSet [(a,World)]비결 정성과 인터리빙을 허용하는 보다 유사한 것으로 처리 할 수 ​​있습니다 .

노먼은 다음과 같이 썼습니다.

@Conal : IO 이야기가 비결정론과 인터리빙에 대해 꽤 잘 일반화되었다고 생각합니다. 제 기억이 맞다면 “Awkward Squad”논문에 꽤 좋은 설명이 있습니다. 그러나 진정한 병렬성을 명확하게 설명하는 좋은 논문을 모르겠습니다.

@Norman : 어떤 의미에서 일반화합니까? 나는 일반적으로 주어진 표현 모델 / 설명 이 비결 정성과 동시성을 고려하지 않기 때문에 World -> (a,World)Haskell과 일치하지 않는다고 제안 IO합니다. 과 같이 적합하는 더 복잡한 모델이있을 수 World -> PowerSet [(a,World)]있지만 그러한 모델이 제대로 작동하고 적절하고 일관되게 표시되었는지는 모르겠습니다. 나는 개인적으로 그러한 짐승을 찾을 수 있을지 의문이다. IO수천 개의 FFI에서 가져온 명령형 API 호출로 채워져 있기 때문 이다. 따라서 IO그 목적을 달성하고 있습니다.

열린 문제 : IO모나드는 하스켈의 죄악이되었습니다. (뭔가를 이해하지 못할 때마다 IO 모나드에 던져 넣습니다.)

(Simon PJ의 POPL 토크 에서 헤어 셔츠 입고 헤어 셔츠 입고 : Haskell 회고전 .)

Tackling the Awkward Squad 의 섹션 3.1 에서 Simon은 type IO a = World -> (a, World)“동시성을 추가 할 때 접근 방식이 제대로 확장되지 않음”을 포함하여 작동하지 않는 부분을 지적합니다 . 그런 다음 가능한 대안 모델을 제안하고 표시 설명 시도를 포기하며 다음과 같이 말합니다.

그러나 우리는 대신 프로세스 계산의 의미론에 대한 표준 접근 방식을 기반으로 운영 의미론을 채택 할 것입니다.

정확하고 유용한 표시 모델을 찾지 못한 것은 내가 Haskell IO를 “기능적 프로그래밍”이라고 부르는 것의 정신과 깊은 이점에서 벗어나거나 Peter Landin이 더 구체적으로 “표현 프로그래밍”이라고 부르는 것의 근원이라고 생각하는 이유입니다. . 여기에서 의견을 참조하십시오.

답변

함수형 프로그래밍은 람다 미적분에서 파생됩니다. 기능 프로그래밍을 진정으로 이해하고 싶다면 http://worrydream.com/AlligatorEggs/를 확인하세요 .

람다 미적분을 배우고 흥미 진진한 함수 프로그래밍 세계로 안내하는 “재미있는”방법입니다!

함수형 프로그래밍에서 Lambda Calculus를 아는 것이 얼마나 도움이되는지 알아보십시오.

따라서 Lambda Calculus는 Lisp, Scheme, ML, Haskell 등과 같은 많은 실제 프로그래밍 언어의 기초입니다 ….

입력에 3을 더하는 함수를 설명하고 싶다고 가정 해 보겠습니다.

plus3 x = succ(succ(succ x))

“plus3은 임의의 숫자 x에 적용될 때 x의 후속 작업의 후속 작업을 생성하는 함수입니다.”

숫자에 3을 더하는 함수는 plus3으로 이름을 지정할 필요가 없습니다. “plus3″라는 이름은이 함수의 이름을 쉽게 지정할 수 있습니다.

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

함수에 람다 기호를 사용한다는 점에 유의하십시오 (악어 알에 대한 아이디어가 어디에서 왔는지 짐작할 수있는 악어처럼 보입니다.)

람다 기호는 악어입니다. (함수)이고 x는 색상입니다. x를 인수로 생각할 수도 있습니다 (Lambda 미적분 함수는 실제로 하나의 인수 만 있다고 가정합니다). 나머지는 함수의 본문으로 생각할 수 있습니다.

이제 추상화를 고려하십시오.

g ≡ λ f. (f (f (succ 0)))

인수 f는 함수 위치 (호출시)에서 사용됩니다. 다른 함수를 입력으로 사용하기 때문에 ga 고차 함수를 호출합니다. 다른 함수 호출 f를 ” eggs ” 라고 생각할 수 있습니다 . 이제 두 가지 기능 또는 “ 우리가 만든 악어 “를 사용하여 다음과 같이 할 수 있습니다.

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x))))
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

λ f Alligator가 λ x Alligator를 먹고 λ x Alligator를 먹고 죽는 것을 볼 수 있습니다. 그런 다음 λ x Alligator가 λ f의 Alligator 알에서 다시 태어납니다. 그런 다음 프로세스가 반복되고 왼쪽의 λ x Alligator가 이제 오른쪽의 다른 λ x Alligator를 먹습니다.

그러면 문법을 디자인하기 위해 ” Alligators “먹는 ” Alligators ” 의이 간단한 규칙 세트를 사용할 수 있습니다. 따라서 함수형 프로그래밍 언어가 탄생했습니다.

따라서 Lambda Calculus를 알고 있으면 함수형 언어의 작동 방식을 이해할 수 있습니다.

답변

Haskell에서 상태를 처리하는 기술은 매우 간단합니다. 그리고 모나드를 이해할 필요가 없습니다.

상태가있는 프로그래밍 언어에서는 일반적으로 어딘가에 일부 값이 저장되고 일부 코드가 실행 된 다음 새 값이 저장됩니다. 명령형 언어에서이 상태는 “배경”어딘가에 있습니다. (순수한) 기능적 언어에서는 이것을 명시 적으로 만들므로 상태를 변환하는 함수를 명시 적으로 작성합니다.

따라서 X 유형의 상태를 갖는 대신 X를 X에 매핑하는 함수를 작성합니다. 그게 다입니다! 상태에 대한 생각에서 상태에 대해 수행하려는 작업에 대한 생각으로 전환합니다. 그런 다음 이러한 기능을 함께 연결하고 다양한 방법으로 결합하여 전체 프로그램을 만들 수 있습니다. 물론 X를 X에 매핑하는 데만 국한되지는 않습니다. 다양한 데이터 조합을 입력으로 취하고 끝에 다양한 조합을 반환하는 함수를 작성할 수 있습니다.

모나드는이를 구성하는 데 도움이되는 도구 중 하나입니다. 그러나 모나드는 실제로 문제의 해결책이 아닙니다. 해결책은 상태 대신 상태 변환에 대해 생각하는 것입니다.

이것은 I / O에서도 작동합니다. 실제로 발생하는 일은 다음과 같습니다. 사용자로부터 직접를 입력 받아 scanf어딘가에 저장하는 대신, 그 결과로 무엇을 할 것인지를 말하는 함수를 작성한 scanf다음 전달합니다. I / O API에 대한 기능. 이것이 바로 Haskell >>=에서 IO모나드 를 사용할 때 하는 일 입니다. 따라서 I / O 결과를 어디에도 저장할 필요가 없습니다. 변환 방법을 알려주는 코드를 작성하기 만하면됩니다.

답변

(일부 기능 언어는 불순한 기능을 허용합니다.)

대한 순수 기능 언어, 현실 세계의 상호 작용은 일반적으로이 같은 함수 인수 중 하나로 포함되어 있습니다 :

RealWorld pureScanf(RealWorld world, const char* format, ...);

다른 언어는 프로그래머로부터 세계를 추상화하기위한 다른 전략을 가지고 있습니다. 예를 들어 Haskell은 모나드를 사용하여world 인수 .

그러나 기능적 언어 자체의 순수한 부분은 이미 Turing이 완성되었습니다. 즉, C로 할 수있는 모든 것은 Haskell에서도 가능합니다. 명령형 언어의 주요 차이점은 상태를 수정하는 대신 다음과 같습니다.

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

수정 부분을 함수 호출에 통합하여 일반적으로 루프를 재귀로 전환합니다.

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}

답변

기능적 언어 는 상태 저장할 ! 그들은 일반적으로 그렇게하는 것에 대해 당신이 명시 적으로 격려하거나 강요합니다.

예를 들어 Haskell의 State Monad를 확인하십시오 .