표현 문제

Expression problem

표현문제는 정적으로 입력된 데이터 추상화의 확장성과 모듈화에 관한 프로그래밍 언어의 난제 문제다.목표는 데이터 추상화에 새로운 표현과 새로운 동작을 추가할 수 있고 기존 코드를 재구성하지 않고 정적 유형 안전성을 유지할 수 있는 데이터 추상화(예: 캐스트 없음)를 정의하는 것이다.프로그래밍 패러다임과 프로그래밍 언어의 결함을 노출시켰고, 제안된 해결책이 많지만 여전히 확실하게 해결되지 않고 있다.

역사

필립 와들러는 라이스 대학의 프로그래밍 언어 팀(PLT)과의 토론에 응하여 이 도전을 공식화하고 "표현 문제"[1]라고 명명했다.그는 또한 자신의 도전에 대한 맥락을 규정하는 세 가지 출처를 언급했다.

이 문제는 1975년 존 레이놀즈가 처음 발견한 것이다.[2]레이놀즈는 다음과 같은 두 가지 형태의 데이터 추상화에 대해 논의했다.현재 추상 데이터 유형(ADT)으로 알려진 사용자 정의 유형(대수 데이터 유형과 혼동되지 않음), 절차 데이터 구조(Procedure Data Structures)는 이제 하나의 방법만으로 원시 형태의 개체로 이해된다.그는 사용자 정의 형식이 새로운 동작으로 확장될 수 있고 절차적 데이터 구조가 새로운 표현으로 확장될 수 있다는 점에서 이러한 유형은 보완적이라고 주장했다.그는 또한 1967년으로 거슬러 올라가 관련 업무를 논의하였다.그러나 이러한 초기 분석을 바탕으로 한 레이놀드의 결론은 완전히 틀린 것으로 판명되었는데, 그는 어떤 물체에 두 번째 방법을 추가하는 것은 "명확한 프로그래밍의 표본이라기보다 투어의 디포스"라고 썼는데, 이는 객체 지향 패러다임과 그 큰 성공을 완전히 놓친 것이다.그는 또한 두 가지 형태의 데이터 추상화는 "본질적으로 구별되고 보완적인 것"이라고 믿었다.

15년 후인 1990년에 윌리엄 쿡은[3] 레이놀드의 정석적인 아이디어를 Objects와 Obstract Data Type의 맥락에서 적용했는데, 둘 다 광범위하게 성장했다.쿡은 데이터 추상화에 내포된 표현과 행동의 매트릭스를 식별하고 ADT가 어떻게 행동 축에 기반하는지, 반면 오브젝트는 표현 축에 기반하는지 논의했다.그는 문제와 관련된 ADT와 오브젝트에 대한 광범위한 논의를 제공한다.그는 또한 두 가지 스타일 모두에서 구현을 검토하고, 양방향에서 확장성을 논의했으며, 정적 타이핑의 중요성도 파악했다.가장 중요한 것은 레이놀즈가 고려하는 것보다 유연성이 높은 상황에 대해 내부화와 방법의 최적화 등 논의했다는 점이다.

ECOP '98년, 슈리람 크리슈나무르티 외.[4]는 표현 중심의 프로그래밍 언어와 도구 세트를 동시에 확장하는 문제에 대한 설계 패턴 솔루션을 제시하였다.그들은 그것을 "표현성 문제"라고 불렀다. 왜냐하면 그들은 프로그래밍 언어 디자이너들이 이 문제를 자신들의 창작물의 표현력을 보여주기 위해 사용할 수 있다고 생각했기 때문이다.PLT의 경우, 현재 DrRacket인 DrScheme의 건설에 문제가 나타났고, 그들은 혼합물의 재발견으로 그것을[5] 해결했다.[6][7]프로그래밍 언어에 관한 논문에서 프로그래밍 언어 문제를 사용하지 않기 위해 크리슈나무르티 외 연구진.패턴 중심의 솔루션을 설명하기 위해 오래된 지오메트리 프로그래밍 문제를 사용했다.ECOP 발표 후 펠레리센과 크리슈나무르티와의 대화에서 와들러는 문제의 PL 중심적 성격을 이해하고 크리슈나무르티의 솔루션이 자바의 유형 체계를 우회하기 위해 깁스를 사용했다고 지적했다.코키 카트라이트(Rice)와 김 브루스(Williams)가 OO언어의 형식 시스템이 어떻게 이 배역을 없앨 수 있는지를 보여주는 메일링 유형 목록에 대한 토론이 계속되었다.이에 대해 와들러는 자신의 에세이를 공식화하고 "언어가 표현 문제를 해결할 수 있을지는 표현 능력을 보여주는 중요한 지표"라고 과제를 밝혔다.표현에 대한 "표현 문제"라는 꼬리표는 "언어를 얼마나 표현할 수 있는가"와 "표현하려고 하는 용어는 언어 표현이다"라고 말한다.

다른 이들은 라이스 대학의 PLT와 거의 동시에 표현 문제의 변형을 발견했는데, 특히 그의 논문에서는 토마스 쿤네[8], 그리고 스마래그다키스와 바토리를[9] 병행 ECOP 98 기사에서 공동 발견하였다.

일부 후속 작업은 표현 문제를 이용해 프로그래밍 언어 디자인의 위력을 발휘했다.[10][11]

표현 문제는 또한 다차원 소프트웨어 제품군 설계에서, 특히 FOSD 프로그램 큐브의 응용 프로그램 또는 특수 사례로서 근본적인 문제가 된다.[citation needed]

해결 방법

표현 문제에는 다양한 해결책이 있다.각 솔루션은 사용자가 코드를 구현하기 위해 작성해야 하는 코드의 양과 필요한 언어 기능에 따라 다르다.

예

문제 설명

우리는 C#로 작성된 다음 라이브러리의 소스 코드가 없다고 상상할 수 있으며, 이를 확장하고자 한다.

공중의 접점 IEvalExpans {     인트로 평가(); }  공중의 계급 불을 켰다.: IEvalExpans {     공중의 불을 켰다.(인트로 n)     {         N = n;     }      공중의 인트로 N { 얻다; }      공중의 인트로 평가()     {         돌아오다 N;     } }  공중의 계급 추가하다: IEvalExpans {     공중의 추가하다(IEvalExpans 남겨진, IEvalExpans 맞다)     {         왼쪽 = 남겨진;         맞다 = 맞다;     }      공중의 IEvalExpans 왼쪽 { 얻다; }      공중의 IEvalExpans 맞다 { 얻다; }      공중의 인트로 평가()     {         돌아오다 왼쪽.평가() + 맞다.평가();     } }  공중의 정태의 계급 예제원 {     공중의 정태의 IEvalExpans 애드원앤드투() => 새로운 추가하다(새로운 불을 켰다.(1), 새로운 불을 켰다.(2));     공중의 정태의 인트로 평가하다TheSumOfOneAndTwo() => 애드원앤드투().평가(); }

이 라이브러리를 사용하여 우리는 산술적 표현을 표현할 수 있다.1 + 2에 있어서와 같이ExampleOne.AddOneAndTwo()그리고 전화해서 그 표현을 평가할 수 있다..Eval()이제 우리가 이 라이브러리를 확장하기를 원한다고 상상해 보십시오. 새로운 유형을 추가하는 것은 우리가 개체 지향 프로그래밍 언어로 작업하고 있기 때문에 쉽다.예를 들어 다음 클래스를 만들 수 있다.

공중의 계급 여러 개: IEvalExpans {     공중의 여러 개(IEvalExpans 남겨진, IEvalExpans 맞다)     {         왼쪽 = 남겨진;         맞다 = 맞다;     }      공중의 IEvalExpans 왼쪽 { 얻다; }      공중의 IEvalExpans 맞다 { 얻다; }      공중의 인트로 평가()     {         돌아오다 왼쪽.평가() * 맞다.평가();     } }

그러나 유형(C# 용어의 새로운 방법)에 대해 새로운 기능을 추가하려면, 그 기능을 변경해야 한다.IEvalExp인터페이스를 구현하는 모든 클래스를 수정한다.또 다른 가능성은 새로운 인터페이스를 만드는 것이다.IEvalExp인터페이스 및 하위 인터페이스 생성Lit,Add그리고Multclasses, 그러나 그 표현은 다시 돌아왔다.ExampleOne.AddOneAndTwo()이미 컴파일되었기 때문에 우리는 구형보다 새로운 기능을 사용할 수 없을 것이다.F#와 같은 기능 프로그래밍 언어에서는 주어진 유형에 걸쳐 기능을 추가하기 쉽지만, 유형을 확장하거나 추가하는 것은 어려운 문제가 역전된다.

개체대수를 이용한 문제해결 방법

"Extensibility for the Mass"라는 논문의 아이디어를 활용하여 확장성을 염두에 두고 원래의 라이브러리를 재설계합시다.[17] 

공중의 접점 ExpAlgebra<T> {     T 불을 켰다.(인트로 n);     T 추가하다(T 남겨진, T 맞다); }  공중의 계급 ExpFactory: ExpAlgebra<IEvalExpans> {     공중의 IEvalExpans 불을 켰다.(인트로 n)     {         돌아오다 새로운 불을 켰다.(n);     }      공중의 IEvalExpans 추가하다(IEvalExpans 남겨진, IEvalExpans 맞다)     {         돌아오다 새로운 추가하다(남겨진, 맞다);     } }  공중의 정태의 계급 예제투<T> {     공중의 정태의 T 애드원토투(ExpAlgebra<T> ae) => ae.추가하다(ae.불을 켰다.(1), ae.불을 켰다.(2)); }

우리는 첫 번째 코드 사례에서와 동일한 구현을 사용하지만, 이제는 대수학용 공장뿐만 아니라 형식에 걸쳐 함수를 포함하는 새로운 인터페이스를 추가한다.이제 다음 식을 생성한다는 점에 주목하십시오.ExampleTwo.AddOneToTwo()을 이용하여ExpAlgebra<T>유형에서 직접 가져오는 대신 인터페이스.이제 더 나아가서 기능을 추가할 수 있다.ExpAlgebra<T>인터페이스, 다음 식을 인쇄하기 위해 기능을 추가한다.

공중의 접점 IPrintExpans: IEvalExpans {     끈을 매다 인쇄하다(); }  공중의 계급 인쇄 가능불을 켰다.: 불을 켰다., IPrintExpans {     공중의 인쇄 가능불을 켰다.(인트로 n): 밑의(n)     {         N = n;     }      공중의 인트로 N { 얻다; }      공중의 끈을 매다 인쇄하다()     {         돌아오다 N.토스트링();     } }  공중의 계급 인쇄 가능한 추가: 추가하다, IPrintExpans {     공중의 인쇄 가능한 추가(IPrintExpans 남겨진, IPrintExpans 맞다): 밑의(남겨진, 맞다)     {         왼쪽 = 남겨진;         맞다 = 맞다;     }      공중의 새로운 IPrintExpans 왼쪽 { 얻다; }      공중의 새로운 IPrintExpans 맞다 { 얻다; }      공중의 끈을 매다 인쇄하다()     {         돌아오다 왼쪽.인쇄하다() + " + " + 맞다.인쇄하다();     } }  공중의 계급 프린트팩토리: ExpFactory, ExpAlgebra<IPrintExpans> {     공중의 IPrintExpans 추가하다(IPrintExpans 남겨진, IPrintExpans 맞다)     {         돌아오다 새로운 인쇄 가능한 추가(남겨진, 맞다);     }      공중의 새로운 IPrintExpans 불을 켰다.(인트로 n)     {         돌아오다 새로운 인쇄 가능불을 켰다.(n);     } }  공중의 정태의 계급 예제3 {     공중의 정태의 인트로 평가하다() => 예제투<IPrintExpans>애드원토투(새로운 프린트팩토리()).평가();     공중의 정태의 끈을 매다 인쇄하다() => 예제투<IPrintExpans>애드원토투(새로운 프린트팩토리()).인쇄하다(); }

에 주의하십시오.ExampleThree.Print()우리는 이미 편집된 표현을 인쇄하고 있다.ExampleTwo, 우리는 기존의 코드를 수정할 필요가 없었다.또한 이것은 여전히 강하게 타이핑되어 있으므로, 우리는 반사나 주물이 필요하지 않다.만약 우리가 그것을 교체한다면PrintFactory()…과 함께ExpFactory()에서ExampleThree.Print()우리는 컴파일 에러를 받을것이다..Print()방법은 그 맥락에서 존재하지 않는다.

참고 항목

참조

  1. ^ "The Expression Problem".
  2. ^ Reynolds, John C. (1975). "User-defined Types and Procedural Data Structures as complementary approaches to Data Abstraction.". New Directions in Algorithmic Languages (PDF). IFIP Working Group 2.1 on Algol. pp. 157–168.
  3. ^ Cook, William (1990). "Object-Oriented Programming versus Abstract Data Types". In Bakker, J.W. de; Roever, W.P. de; Rozenberg, G. (eds.). Foundations of Object-Oriented Languages (FOOL), REX School/Workshop. Noordwijkerhout, The Netherlands: Springer Berlin Heidelberg. pp. 151–178. ISBN 978-3-540-46450-1.
  4. ^ "Synthesizing Object-Oriented and Functional Design to Promote Re-Use".
  5. ^ "Modular object-oriented programming with units and mixins".
  6. ^ Cook, William (1989). A Denotational Semantics of Inheritance (PDF) (PhD). Brown University.
  7. ^ Flatt, Matthew; Krishnamurthi, Shriram; Felleisen, Matthias (1998). "Classes and Mixins". Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '98. pp. 171–183. doi:10.1145/268946.268961. ISBN 978-0897919791.
  8. ^ Kühne, Thomas (1999). A Functional Pattern System for Object-Oriented Design. Darmstadt: Verlag Dr. Kovac. ISBN 978-3-86064-770-7.
  9. ^ Smaragdakis, Yannis; Don Batory (1998). "Implementing Reusable Object-Oriented Components". Lecture Notes in Computer Science. 1445.
  10. ^ Zenger, Matthias; Odersky, Martin (2001). "Extensible Algebraic Datatypes with Defaults": 241–252. CiteSeerX 10.1.1.28.6778. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  11. ^ Zenger, Matthias; Odersky, Martin (2005). "Independently extensible solutions to the expression problem". Foundations of Object-Oriented Languages (FOOL). ACM SIGPLAN. CiteSeerX 10.1.1.107.4449. {{cite web}}:누락 또는 비어 있음 url=(도움말)
  12. ^ Chambers, Craig; Leavens, Gary T. (November 1995). "Type Checking and Modules for Multi-Methods". ACM Trans. Program. Lang. Syst. (17): 805–843.
  13. ^ Clifton, Curtis; Leavens, Gary T.; Chambers, Craig; Millstein, Todd (2000). "MultiJava: Modular Open Classes and Symmetric Multiple Dispatch for Java" (PDF). Oopsla '00.
  14. ^ Wouter Swierstra (2008). "Data Types à La Carte". Journal of Functional Programming. Vol. 18, no. 4. Cambridge University Press. pp. 423–436. doi:10.1017/S0956796808006758. ISSN 0956-7968.
  15. ^ Wehr, Stefan; Thiemann, Peter (July 2011). "JavaGI: The Interaction of Type Classes with Interfaces and Inheritance". ACM Trans. Program. Lang. Syst. (33).
  16. ^ Carette, Jacques; Kiselyov, Oleg; Chung-chieh, Shan (2009). "Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages" (PDF). J. Funct. Program.
  17. ^ a b Oliveira, Bruno C. d. S.; Cook, William R. (2012). "Extensibility for the Masses: Practical Extensibility with Object Algebras" (PDF). Ecoop '12.
  18. ^ Garrigue, Jacques (2000). "Code Reuse Through Polymorphic Variants". CiteSeerX 10.1.1.128.7169. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

외부 링크