[terminology] 기능적, 선언적 및 명령형 프로그래밍 [닫기]

이 글을 쓰는 시점에서이 페이지에서 가장 많이 투표 된 답변은 Wikipedia를 인용하는 답변을 포함하여 선언적 대 명령 적 정의에 대해 부정확하고 혼동됩니다. 일부 답변은 다른 방식으로 용어를 혼동하고 있습니다.

수식이 셀을 변경하는 것과 상관없이 스프레드 시트 프로그래밍이 선언적인 이유에 대한 설명 도 참조하십시오 .

또한 여러 답변은 함수형 프로그래밍이 선언의 하위 집합이어야한다고 주장합니다. 그 시점에서 우리는 “기능”과 “절차”를 구별 할 수 있는지에 달려 있습니다. 명령형 대 선언 형을 먼저 처리합니다.

선언적 표현의 정의

만 가능하게 차별화 할 수 속성 선언 에서 표현 필수적 표현은 하위 표현의 참조 투명성 (RT)입니다. 다른 모든 속성은 두 유형의 표현식간에 공유되거나 RT에서 파생됩니다.

100 % 선언적 언어 (즉, 가능한 모든 표현이 RT 인 언어)는 다른 RT 요구 사항 중에서 HTML과 Haskell의 대부분과 같은 저장된 값의 변형을 허용하지 않습니다.

RT 표현의 정의

RT는 종종 “부작용이 없다”고합니다. 효과 라는 용어 는 정확한 정의가 없으므로 어떤 사람들은 “부작용 없음”이 RT와 동일하다는 데 동의하지 않습니다. RT는 정확한 정의를 가지고 있습니다.

모든 하위 표현식은 개념적으로 함수 호출이므로 RT는 함수의 구현 (예 : 호출 된 함수 내부의 표현식)이 함수 외부 의 변경 가능한 상태에 액세스하지 않아야 합니다 ( 변경 가능한 로컬 상태에 액세스하는 것은 허용됨). 간단히 말해서 함수 (구현)는 순수 해야합니다 .

순수한 기능의 정의

순수한 기능은 종종 “부작용이 없다”고 말합니다. 효과 라는 용어 는 정확한 정의가 없으므로 일부 사람들은 동의하지 않습니다.

순수한 함수에는 다음과 같은 속성이 있습니다.

• 관찰 가능한 유일한 출력값은 반환 값입니다.
• 유일한 출력 종속성은 인수입니다.
• 인수는 출력이 생성되기 전에 완전히 결정됩니다.

RT는 표현식 (함수 호출 포함)에 적용되고 순도는 함수 (구현)에 적용됩니다.

RT 표현식을 만드는 불순한 함수의 모호한 예는 동시성이지만 인터럽트 추상화 계층에서 순도가 깨지기 때문입니다. 당신은 정말로 이것을 알 필요가 없습니다. RT 표현식을 작성하려면 순수한 함수를 호출하십시오.

RT의 파생 속성

선언적 프로그래밍에 인용 된 다른 속성, 예를 들어 Wikipedia에서 사용 된 1999 년 의 인용 은 RT에서 파생되거나 명령형 프로그래밍과 공유됩니다. 따라서 내 정확한 정의가 올바른지 증명합니다.

외부 값의 불변성은 RT 요구 사항의 일부입니다.

• 선언적 언어에는 루프 제어 구조가 없습니다 (예 : for및 while). 불변성으로 인해 루프 조건이 변경되지 않기 때문 입니다.

• 선언적 언어는 불변성으로 인해 평가 순서의 다른 선택이 결과를 변경하지 않기 때문에 중첩 함수 순서 (일명 논리적 종속성) 이외의 제어 흐름을 표현 하지 않습니다 (아래 참조).

• 선언적 언어는 논리적 “단계”(즉, 중첩 된 RT 함수 호출 순서)를 표현하지만 각 함수 호출이 더 높은 수준의 의미 론적 (즉, “할 일”)인지 여부는 선언적 프로그래밍의 요구 사항이 아닙니다. 명령형과 구별되는 점은 불변성 (즉, 일반적으로 RT)으로 인해 이러한 “단계”는 변경 가능한 상태에 의존 할 수없고 표현 된 논리의 관계 순서 (즉, 함수 호출의 중첩 순서, 일명 하위 표현식)에만 의존 할 수 없다는 것입니다. ).

  예를 들어 단락 <p>의 하위 표현식 (예 : 태그)이 평가 될 때까지 HTML 단락 을 표시 할 수 없습니다. 태그 계층 (논리적으로 중첩 된 함수 호출 인 하위 표현식의 중첩)의 논리적 관계로 인해 변경 가능한 상태는없고 순서 종속성 만 있습니다.

• 따라서 선언적 표현 은 변이 가능한 상태 관계가 아닌 구성 부분 (즉, 하위 표현 함수 인수) 의 논리적 관계 만 표현한다는 불변성의 파생 속성 (보다 일반적으로 RT)이 있습니다.

평가 순서

하위 표현식의 평가 순서를 선택하면 함수 호출이 RT가 아닌 경우 (즉, 함수가 순수하지 않은 경우), 예를 들어 함수 외부의 일부 변경 가능한 상태가 함수 내에서 액세스되는 경우에만 결과가 달라질 수 있습니다.

예를 들어, 일부 중첩 된 표현, 예를 들어 주어진 f( g(a, b), h(c, d) )기능이있는 경우, 함수 인수의 열망과 게으른 평가는 동일한 결과를 줄 것이다 f, g그리고 h순수를.

반면, 기능하는 경우 f, g그리고 h순수하지 않은, 다음 평가 순서의 선택은 다른 결과를 제공 할 수 있습니다.

식 연산자는 단항 접두사, 단항 접두사 또는 이진 접두사 표기법으로 가장하는 함수 호출이기 때문에 중첩 식은 개념적으로 중첩 된 함수입니다.

모든 식별자는, 예를 들어, 경우에 접선 방향으로는, a, b, c, d,이다 불변의 모든 곳에서, 프로그램의 외부 상태 (즉, I / O) 액세스 할 수 없습니다, 그리고 더 추상화 계층 파손이없는 다음 기능은 항상 순수하다.

그건 그렇고, Haskell은 다른 문법을 가지고 f (g a b) (h c d)있습니다.

평가 순서 세부 사항

함수는 입력에서 출력으로의 상태 전이 (변경 가능한 저장 값이 아님)입니다. 순수 함수 호출의 RT 구성의 경우 , 이러한 상태 전이의 실행 순서는 독립적입니다. 각 함수 호출의 상태 전이는 부작용이없고 RT 함수가 캐시 된 값으로 대체 될 수 있다는 원칙으로 인해 다른 함수와 독립적입니다 . 하기 위해 인기있는 오해를 수정 , 순수한 모나드 조성은 항상 선언 및 RT 하스켈의 사실에도 불구하고, IO모나드는 틀림없이 불순한 때문에 필수적 WRT World프로그램의 외부 상태 (그러나 아래의 경고의 의미에서, 부작용 격리되어 있습니다).

평가가 어렵다는 것은 함수가 호출되기 전에 함수 인수가 평가됨을 의미하며, 게으른 평가는 인수가 함수 내에서 액세스 될 때까지 평가되지 않음을 의미합니다 .

정의 : 함수 매개 변수 는 함수 정의 사이트 에서 선언 되고 함수 인수 는 함수 호출 사이트 에서 제공 됩니다. parameter 와 argument 의 차이점을 알아야합니다 .

개념적으로, 모든 표현은 예 (의 조성) 함수 호출, 상수 단항 연산자는 하나 개의 입력과 함수 입력없이 함수이다되는 이진 중위 연산자는 두 입력이 함수는, 생성자 함수, 심지어 제어 명령이다 (예이다 if, for, while) 기능으로 모델링 할 수 있습니다. 이 있도록 인수 평가 기능 (중첩 된 함수 호출 순서하지 혼동 할)은 예를 들면, 구문에 의해 선언되지 f( g() )열심히 평가할 수 g다음 f에 g‘의 결과 나에 대한 평가 할 수 f만 유유히 평가 g의 결과 내에서 필요할 때 f.

주의 사항, 튜링 완전 언어 없음 (즉, 무한한 재귀를 허용하는)은 완벽하게 선언적입니다. 그러나 평가 순서의 선택으로 인한 이러한 부작용은 메모리 소비, 실행 시간, 대기 시간, 비 종료 및 외부 히스테리시스로 제한 되므로 외부 동기화가 가능합니다.

기능적 프로그래밍

선언적 프로그래밍에는 루프를 사용할 수 없으므로 반복하는 유일한 방법은 함수 재귀입니다. 이런 의미에서 기능적 프로그래밍은 선언적 프로그래밍과 관련이 있습니다.

그러나 함수형 프로그래밍은 선언적 프로그래밍에만 국한되지 않습니다 . 기능적 구성은 특히 표현 문제 와 관련하여 하위 유형과 대조 될 수 있는데, 하위 유형이나 기능적 분해를 추가하여 확장을 수행 할 수 있습니다 . 확장은 두 가지 방법론 의 혼합 일 수 있습니다 .

함수형 프로그래밍은 일반적으로 함수를 일류 객체로 만듭니다. 즉, 함수 유형은 다른 유형이있는 곳이면 어디든지 문법에 나타날 수 있습니다. 결론은 함수가 함수를 입력하고 작동 할 수 있으므로 함수 구성을 강조함으로써 결정 분리, 즉 결정 론적 계산의 하위 계산 사이의 종속성을 분리함으로써 관심의 분리를 제공한다는 것입니다.

예를 들어, 컬렉션의 각 요소에 적용될 수있는 무한한 수의 특수화 된 액션 각각에 대해 별도의 함수를 작성하는 대신 (그리고 함수가 선언적이어야하는 경우 루프 대신 재귀를 사용하는 대신) 함수형 프로그래밍은 재사용 가능한 반복을 사용합니다. 기능, 예를 들면 map, fold, filter. 이 반복 함수는 일류 특수 액션 함수를 입력합니다. 이러한 반복 함수는 콜렉션을 반복하고 각 요소에 대해 입력 된 특수 조치 함수를 호출합니다. 이 조치 함수는 더 이상 콜렉션을 반복하기 위해 반복문을 포함 할 필요가 없기 때문에 더 간결합니다.

그러나 함수가 순수하지 않으면 실제로 절차입니다. 불순한 함수를 사용하는 함수형 프로그래밍은 실제로 절차 적 프로그래밍이라고 주장 할 수 있습니다. 따라서 선언적 표현이 RT라는 데 동의하면 절차 적 프로그래밍은 선언적 프로그래밍이 아니라고 할 수 있습니다. 따라서 함수형 프로그래밍은 항상 RT이며 선언적 프로그래밍의 하위 집합이어야한다고 주장 할 수 있습니다.

병행

일급 기능을 갖춘이 기능 구성 은 독립 기능을 분리 하여 병렬 처리 의 깊이를 표현할 수 있습니다 .

브렌트의 원리 : 작업 w 및 깊이 d를 사용한 계산은 시간 O (max (w / p, d))의 p- 프로세서 PRAM에서 구현 될 수 있습니다.

동시성과 병렬 처리 모두 선언적 프로그래밍 , 즉 불변성과 RT가 필요합니다.

그렇다면 Parallelism == 동시성이라는이 위험한 가정은 어디에서 왔습니까? 부작용이있는 언어의 자연스러운 결과입니다. 언어가 모든 곳에서 부작용이있는 경우 한 번에 여러 작업을 수행하려고 할 때마다 각 작업의 효과가 인터리빙되어 결정되지 않은 결과가 나타납니다 . 따라서 부작용이있는 언어에서 병렬 처리를 얻는 유일한 방법은 동시성입니다. 따라서 우리가 종종 두 가지가 얽힌 것을 본다는 것은 놀라운 일이 아닙니다.

FP 평가 순서

평가 순서는 또한 기능 구성의 종료 및 성능 부작용에 영향을 미칩니다.

Eager (CBV)와 Lazy (CBN)는 평가 순서가 역전되어 있기 때문에 범주 형 결투 [ 10 ]입니다. 즉, 외부 또는 내부 함수가 각각 먼저 평가되는지 여부입니다. 거꾸로 된 나무를 상상 해보면 함수 트리 분기 팁에서 분기 계층 구조까지 최상위 계층 함수 트렁크까지 간절히 평가합니다. 반면, 게으른 트렁크에서 분기 팁까지 평가합니다. 열망에는 결속 제품 ( “and”, a / k / 범주 적 “제품”)이없고 게으름 병에는 결속 coproducts ( “또는”, a / k / 범주 “합계”)가 없습니다 [ 11 ].

공연

• 심한

  비 종료와 마찬가지로, 열성적인 기능적 구성으로 열성적이다. 즉, 구성 적 제어 구조는 게으르지 않은 불필요한 작업을한다. 예를 들어 , 첫 번째 true 요소에서 끝나는 접기로 구성된 경우 전체 목록을 열성적으로 불필요하게 맵핑합니다.

  이러한 불필요한 작업은 순수한 기능을 갖는 열망과 지연의 순차 시간 복잡성에서 “최대”의 추가 로그 요소의 원인 이다. 해결책은 열악한 부정확 함이 내부 함수에서 시작되기 때문에 지연 생성자 (예 : 선택적 지연 제품에 대한 열망)가있는 펑터 (예 : 목록)를 사용하는 것입니다. 이는 제품이 건설적인 유형, 즉 초기 고정 점에 초기 대수를 갖는 유도 형이기 때문입니다 [ 11 ]

• 게으른

  비 종료와 마찬가지로, 게으른 기능적 구성으로 게으른 게으른 게으른 것입니다. 즉, 일치 성 최종성이 필요 이상으로 발생할 수 있으며, 불필요한 작업과 열등한 경우가 아닌 지체의 결정을 초래합니다 [ 10 ] [ 11 ] . 최종성의 예로는 상태, 타이밍, 비 종료 및 런타임 예외가 있습니다. 이것들은 필수적인 부작용이지만 순수한 선언적 언어 (예 : Haskell)에서도 공간 할당에 암시적인 IO 모나드 (주 : 모든 모나드가 반드시 필요한 것은 아닙니다!)의 상태가 있으며 타이밍은 명령적인 상태와 관련된 상태입니다. 현실 세계. 게으른 경우 게으름 이 외부 기능에서 발생 하기 때문에 선택적인 열악한 보조 제품과 함께 게으른 사용하면 게으름이 내부 보조 제품으로 누출 됩니다.(비 종료 섹션의 예를 참조하십시오. 여기서 ==는 외부 이진 연산자 함수입니다). 이는 공동 생산물이 최종성, 즉 최종 객체에 최종 대수를 갖는 일치 형 유형에 의해 제한되기 때문이다 [ 11 ].

  Lazy는 선언 된 함수 계층과 런타임 평가 순서 사이 의 불일치로 인해 대기 시간 및 공간에 대한 함수의 디자인 및 디버깅에 결정 성을 유발합니다. 디버깅은 대부분의 프로그래머의 기능을 능가 할 수 있습니다. 열성적으로 평가 된 게으른 순수 함수는 런타임에 이전에는 볼 수 없었던 종료되지 않을 수 있습니다. 반대로, 지연으로 평가 된 열악한 순수 함수는 런타임에 이전에 볼 수 없었던 공간 및 지연 시간 결정을 유발할 수 있습니다.

비 종료

컴파일 타임에 Halting 문제와 Turing 완전한 언어로의 상호 재귀로 인해 함수는 일반적으로 종료되지 않을 수 있습니다.

• 심한

  Head“and” 의 결합에 대해 간결하지만 게으르지 않은 경우, 왼쪽이 끝나지 않고 오른쪽이 끝나기 때문에 각각 또는 그렇지 않은 Tail경우 각각 또는 그렇지 않습니다.HeadTailList( Head(), Tail() ).tail == Tail()List( Head(), Tail() ).head == Head()

  반면에 게으른 양쪽은 종료됩니다. 따라서 열성적인 제품은 너무 열성적이며, 필요하지 않은 경우 종료되지 않은 (런타임 예외 포함) 제품에 너무 열심입니다.

• 게으른

  의 분리를위한, 게으른하지만 열망 있지 않은 상태 1“또는” 2경우, f종료하지 않는, 다음 List( f ? 1 : 2, 3 ).tail == (f ? List( 1, 3 ) : List( 2, 3 )).tail사실이 아니다 왼쪽 종료하고, 오른쪽은하지 않기 때문에.

  반면 열망이 없으면 어느 쪽도 종료되지 않으므로 평등 테스트에 도달하지 않습니다. 따라서 게으른 코디네이션에서는 너무 게으르고, 이러한 경우에는 열망하는 것보다 더 많은 작업을 수행 한 후 종료되지 않습니다 (런타임 예외 포함).

[ 10 ] 선언적 연속성 및 범주 적 이중성, Filinski, 섹션 2.5.4 SB에서 CBV와 CBN의 비교, 3.6.1 CBV와 CBN.

[ 11 ] 선언적 연속성 및 범주 적 이중성, Filinski, 섹션 2.2.1 제품 및 보조 제품, 2.2.2 터미널 및 초기 개체, 게으른 제품이있는 2.5.2 CBV 및 열성적인 보조 제품이있는 2.5.3 CBN

답변

   Take the next customer from a list.
   If the customer lives in Spain, show their details.
   If there are more customers in the list, go to the beginning

   Show customer details of every customer living in Spain