그래프 감소
Graph reduction컴퓨터 공학에서, 그래프 감소는 어떤 기능에 대한 논거가 즉시 평가되지 않는 평가 전략인 비강제적 평가의 효율적인 버전을 구현한다.이러한 형태의 엄격하지 않은 평가는 게으른 평가라고도 하며 기능 프로그래밍 언어에도 사용된다.이 기술은 1971년 크리스 워즈워스에 의해 처음 개발되었다.
동기
산술 식을 평가하는 간단한 예는 다음과 같다.
위의 감소 순서는 가장 바깥쪽 나무 감소라고 알려진 전략을 사용한다.가장 안쪽 트리 감소를 사용하여 동일한 식을 평가할 수 있으며, 감량 순서는 다음과 같다.
축소 순서는 괄호를 추가하여 명시적으로 작성된다는 점에 유의하십시오.덧셈은 연관 연산이기 때문에 이 표현은 단순히 오른쪽에서 왼쪽으로 평가될 수도 있었다.
나무로 표현되어 위의 표현은 다음과 같다.
나무감축이라는 말이 여기서 비롯된다.나무로 표현될 때, 우리는 가장 안쪽의 축소가 가장 아래로부터 위로 작용하는 반면, 가장 바깥쪽은 위에서 아래로 작용하는 것으로 생각할 수 있다.
이 표현식은 또한 지시된 순환 그래프로 나타낼 수 있으며, 하위 표현들을 공유할 수 있다.
나무의 경우, 가장 바깥쪽과 가장 안쪽의 감소도 그래프에 적용된다.그래서 우리는 그래프를 줄였다.
이제 가장 바깥쪽 그래프 감소를 통한 평가는 다음과 같이 진행될 수 있다.
이제 평가에는 4단계만 필요하다는 점에 유의하십시오.가장 바깥쪽 그래프 감소를 게으른 평가라고 하며 가장 안쪽 그래프 감소를 열성 평가라고 한다.
결합기 그래프 감소
결합기 그래프 감소는 기능 프로그래밍 언어의 기본 구현 기법으로서, 프로그램이 컴퓨터 메모리에서 지시된 그래프 데이터 구조에 매핑되는 결합기 표현으로 변환되고, 프로그램 실행은 이 그래프의 일부를 다시 쓰는 것으로 구성된다("축소").유익한 결과
역사
평가된 값을 공유할 수 있는 그래프 감소의 개념은 크리스 워즈워스가 1971년 박사학위 논문에서 처음 개발했다.[1]이 논문은 1976년 피터 헨더슨과 제임스 H. 모리스 주니어가 게으른 평가 개념을 도입한 '게을러 평가자'[2]라는 논문에서 인용한 것이다.1976년에 David Turner는 결합기를 이용한 SASL에 게으른 평가를 통합했다.[3]SASL은 1972년 터너에 의해 처음 개발된 초기 기능 프로그래밍 언어였다.
참고 항목
메모들
- ^ Hudak, Paul (September 1989). "Conception, evolution, and application of functional programming languages". ACM Computing Surveys. 21 (3): 359–411. CiteSeerX 10.1.1.83.6505. doi:10.1145/72551.72554.
- ^ 게으른 평가자
- ^ Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip. "A History of Haskell: Being Lazy with Class". History of Programming Languages Conference 2007.
참조
- Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.
추가 읽기
- 사이먼 페이튼 존스, 프렌티스 홀의 기능 프로그래밍 언어 구현, 1987.전체 텍스트 온라인.[1]
