1 INTRODUCTION 2 6 Deterministic concurrent programming Avoiding nondeterminism in a concurrent language Declarsive concurren

Size: px

Start display at page:

Download "1 INTRODUCTION 2 6 Deterministic concurrent programming Avoiding nondeterminism in a concurrent language Declarsive concurren"

霜如汪
7 years ago
Views:

1 Programming Paradigms for Dummies: What Every Programmers Should Know : : Peter Van Roy : sudayly@gmail.com 1 Introduction 2 2 Languages, paradigms, and concepts Taxonomy of programming paradigms Observable nondeterminsim Named state Computer programming and system design Creative extension principle Designing a language and its problems 7 4 Programming concepts Record Lexically scoped closure Indepence(concurrency) Named State Named state and modularity Data Abstraction Objects and abstract data types Polymorphism and the responsability principle Inheritance and the substitution principle

............... 6 2.3 Creative extension principle........................ 6 3 Designing a language and its problems 7 4 Programming concepts 7 4.1 Record.................................... 7 4.2 Lexically scoped closure.

2 1 INTRODUCTION 2 6 Deterministic concurrent programming Avoiding nondeterminism in a concurrent language Declarsive concurrency Constraint Programming Some applications of constraint programming How the constraint solver works Conclusion and suggestion for going further 22,, ( ).,. 30,.,., : (dual-paradigm languages) (definitive language). :,, ( )..,,.,, : (eager,lazy ),,.,.,. 1 Introduction,.,..,.,. ( ),.....,.,... Java, Prolog Esterel. Java C++.,,,

2 How the constraint solver works...................... 21 8 Conclusion and suggestion for going further 22,,

3 1 INTRODUCTION 3.,,. (multiparadigm programming),,...,,, C. [50], CTM,., CTM. Oz, CTM. Oz,,.,,. Languages, paradigms, and concepts, 2. ( Java ),.,.,,!,. :, (, ).,. Designing a language and its programs 3.. :..,.,... Programming concepts 4 4 :,, ( ).,.. Data abstraction 5. :,,.,,.,.. Deterministic concurrent programming 6,.

. :..,.,... Programming concepts 4 4 :,, ( ).,.. Data abstraction 5. :,,.,,.,.. Deterministic concurrent programming 6,.

4 2 LANGUAGES, PARADIGMS, AND CONCEPTS 4,.,,.,.,., /,.,,,. /,.. Constraint programming 7, :..,,. 1970,... Conclusions and suggestions for going further 8.,,.. Oz[50] Alice[38]. 2 Languages, paradigms, and concepts,,.,.., Java, Javascript, C#, Ruby Python :,,. 1..,,.,. 27.., :.,. 2.1 Taxonomy of programming paradigms 2,, [55].,. 27,,.. (

2 Languages, paradigms, and concepts,,.,.., Java, Javascript, C#, Ruby Python :,,.

5 2 LANGUAGES, PARADIGMS, AND CONCEPTS 5 ),.,. n 2 n.,, ( ).. :, λ,. 2 n,. n. 2, ( ),....,..,. 2 : Observable nondeterminsim. 2.,.,.., ( )..,..., Java, ( ). Java [29].,, Named state.,,.. 3,, ;. Dijkstra guraded command language (GCL) [14].,., ( ) (, Prolog DCG, monads:, ). ports cells,, (,

Java [29].,,. 6 7 4. 2.1.2 Named state.,,.. 3,,. 8... 3 ;.

6 2 LANGUAGES, PARADIGMS, AND CONCEPTS 6 ). ( client/server). ( 4.4 )., ( )., Computer programming and system design 4. Winberg[56],. : ( ) ( ). : (, ) (, ).. :.., 50.,,.,,.,..,,. the creative extension principle. 2.3 Creative extension principle. the creative extension. Felleisen[18], [50].,.,,,.,.,. 3, :,,.,.,,,..,. :.,,,

. :.., 50.,,.,,.,..,,. the creative extension principle. 2.

7 3 DESIGNING A LANGUAGE AND ITS PROBLEMS 7,,. : ( ),, ( ).,.,,.. 2 [50] the creative extension. 3 Designing a language and its problems,... 4 Programming concepts.,,, ( ) Record :,. : R=chanson(nom:``Le Roi des Aulnes'' artiste:``dietrich Fischer-Dieskau'' compositeur:``franz Schubert'' langue:allemand) R., R.nom ``Le Roi des Aulnes''.. :,.,,,,. ( ),. 4.2 Lexically scoped closure,.,, ( 2)., ( )., :,..

: R=chanson(nom:``Le Roi des Aulnes'' artiste:``dietrich Fischer-Dieskau'' compositeur:``franz

8 4 PROGRAMMING CONCEPTS 8 9. P. ( D), P., x., P ( ). (C ), P D. 10 :., <stmt>., <stmt>, ( ), P ( Oz )., P. <stmt>.,, if while : ( ) ( ). (, Pascal C) : ; ; ; ;. :,,.,,.,,., Erlang client/server.,. Pierre Cointe[9]. ( weaving ),. AspectJ. weaving, : ( ).,.,,..,... Erlang. : 100 Erlang (, AXD-301 ATM [57]).,,.,.

9 4 PROGRAMMING CONCEPTS Indepence(concurrency) :..,,.,.,., 1. (, ).,..,.. : ( ), ( ). 38. :.. : :.. Internet. :....,....,.. :.. :,.,.. : moniters,.., Java C#. :.. : agents. CSP(Communicating Sequential Processes) [25] Erlang[6]. CSP ( ), Erlang ( )., moniters [29].,. : ( ),.,,. 6 7,,. 1,,

10 4 PROGRAMMING CONCEPTS Named State (Named State)..,. :,....,.?, ( ),.,.,,.. (monads DCGs, 2.1 ),. 11, A B, A ( ), B. B :,. A,....,.,,.,., : Named state and modularity. (,, ),..,. 3, P, U1 U2. P M, F G. U1 U2 M : M. M : fun {ModuleMaker} fun {F.. }.. % D e f i n i t i o n o f F fun {G.. }.. % D e f i n i t i o n o f G in themodule ( f : F g :G) M={ModuleMaker} % Creation o f M ModuleMaker,. ModuleMaker. M.,,. M F G. U2. U2

11 4 PROGRAMMING CONCEPTS 11,. U2 F,. U2 M, F. U2 P, P M, ( M ), U2 ( U1!).!. F,.,,. F ( ): fun {F.. Fin Fout} Fout = Fin F, Fin Fout. F, Fin F, F Fin 1, Fout. F,., F : A = {F.. F1 F2} B = {F.. F2 F3} C = {F.. F3 F4} F1. F2,,. F4.,, U2 F. : U1, U1. M, U1,,,.. M. Oz, cell cell.. : fun {ModuleMaker} X={NewCell 0} % Create c e l l r e f e r e n c e d by X fun {F.. } X + 1 % New Content o f X i s o l d p l u s 1.. % O r i g i n a l d e f i n i t i o n o f F fun {G.. }.. % O r i g i n a l d e f i n i t i o n o f G fun % Return content o f X in themodule ( f : F g :G c : Count ) M={ModuleMaker} M cell. F, cell. Count( M.c ) cell. F G. : U2,, F G.

. : fun {ModuleMaker} X={NewCell 0} % Create c e l l r e f e r e n c e d by X fun {F.. } X := @X + 1 % New Content o f X i s o l d p l u s 1.

12 5 DATA ABSTRACTION 12...? 2, :.. 5 Data Abstraction,.,.., : 1..,. 2...,,., : :..,.,,.,,. 5.1 Objects and abstract data types,. :. bundling: ( (PDA)), ( (ADT))., 14.., Java. Java (1, 2, 3 ) (+, -, * ).,.. Java ( ) ( )..,,.. 2. Altshuller Theory of Inventive Problem Solving (TRIZ) a technical contradiction, TRIZ [2].

13 5 DATA ABSTRACTION Polymorphism and the responsability principle,.,,.,,.,,,..., :!.,. GetCured :,.!. :,,..,. 15.,.. CompoundFigure. (!). CompoundFingure draw., draw... class Figure.. class.. C i r c l e class Line attr x1 y1 x2 y2 meth draw.... class CompoundFigure attr f i g l i s t meth draw f o r F f i g l i s t do {F draw}..

, draw... class Figure.. class.. C i r c l e class Line attr x1 y1 x2 y2 meth draw.

14 6 DETERMINISTIC CONCURRENT PROGRAMMING Inheritance and the substitution principle.,,.,. :,.,,.. A B: A B,. A.,,.,. B B. B. bugs..,. Java final.. :..,.. 16.,. A B,, O A O B., B O B, A O A.,. A B.. 80,.,.. :..,. bugs. bugs, bugs,, bugs.,,,, bugs. 6 Deterministic concurrent programming.,. :,.,,. ;.,..,, : d e c l a r e C={NewCell 0} thread C:=1 thread C:=2

, B O B, A O A.,. A B.. 80,.,.. :..,. bugs. bugs, bugs,, bugs.,,,, bugs.

15 6 DETERMINISTIC CONCURRENT PROGRAMMING 15, C 1 2.., Avoiding nondeterminism in a concurrent language.,.,? 3,,,. : ,,.?. Java C#, Erlang,.,. ( ). 1.. Concurrent Races Inputs can be paradigms possible? nondeterm.? Example languages Declarative concurrency No No Oz[34], Alice[38] Constraint programming No Yes Gecode[43], Numerica[48] Functional reactive programming No Yes FrTime[12], Yampa[27] Discrete synchronous programming No Yes Esterel[7], Lustre[21], Signal[26] Message-passing concurrency Yes Yes Erlang[6], E[32] 1: Four determinstic concurrent paradigms and one that is not Declarative concurrency( monotonic dataflow),..,,, (,, ). Oz[50,34] Alice[38]. lazy. 6.2 lazy. Constraint Programming, 7. 3 technical contradiction

? Example languages Declarative concurrency No No Oz[34], Alice[38] Constraint programming No Yes Gecode[43], Numerica[48] Functional reactive programming No Yes FrTime[12], Yampa[27]

16 6 DETERMINISTIC CONCURRENT PROGRAMMING 16 nonmonotonic dataflow,. dataflow tokens., ( glitch ).. Functional reactive programming nonmonotonic dataflow, glitches. Functional reactive programming( continous synchronous programming),,,.,.,, (, time size).. [16].,.,., x+(x*y), x=3, y=4, 15. x 5, , agent agent,. glitch, x. 17,. Glitches,, ( ). Yampa( Hashell)[27] FrTime( Scheme)[12]. Discrete synchronous programming,,,. (reactive system). :. functional reactive programming,, 4., :.. 5. : instantaneous ( ), take times : ( ).. reactive system., (be trivially composed):,. Esterel[7], Lustre[21], Signal[26]. Esterel, Lustre, Signal. discrete synchronous concurrent constraint. Timed CC, Carlo Olarte et al[35].,..,, declarative concurrency, 6.2.,. : 4, 5, Esterel, Mealy machine,,.

Yampa( Hashell)[27] FrTime( Scheme)[12]. Discrete synchronous programming,,,. (reactive system). :. functional reactive programming,, 4., :.. 5. : instantaneous ( ), take times : ( ).

17 6 DETERMINISTIC CONCURRENT PROGRAMMING 17 The OpenMusic music composition stdio [1]. ( patches ). discrete synchronous programming...,. (lazy) :,. :. The Antescofo score follower [11]. ( ) (tempo, i.e., beats per minute). Antescofo,. discrete synchronous programming,,., Antescofo tempo oscillator, fractional notes. Antescofo. Yann Orlary et al Faust, [37]. discrete synchronous, Lustre[36]. Faust :, C++. Max/MSP, [39]. Max/MSP, Max,, MSP,, Jitter, 3D. OpenMusic,. Max, eager (metronomes). (, functional reactive programming ), 6.,.,., : (OpenMusic), (, Max/MSP Antescofo), (, Max/MSP Fault). OpenMusic, Max/MSP Antescofo 1. OpenMusic, :,,. Max/MSE,. Antescofo :,,. Hermes/dl, Alexandre Francois, [19]. 6.2 Declarsive concurrency, ( [50] 4 )., 6 Max/MSP., glitches., synchronous programming.

Faust :, C++. Max/MSP, [39]. Max/MSP, Max,, MSP,, Jitter, 3D. OpenMusic,. Max, eager (metronomes). (, functional reactive programming ), 6.,.,., : (OpenMusic), (, Max/MSP Antescofo), (, Max/MSP Fault).

18 6 DETERMINISTIC CONCURRENT PROGRAMMING 18 confluence,.,,. :.,. : {NewThread P}:, 0 P.,. : X={NewVar}:, X. {Bind X V}: X V, V. {Wait X}: X.,,,., Add, PrimAdd: proc {Add X Y Z} {Wait X} {Wait Y} l o c a l R in {PrimAdd X Y R} {Bind Z R} Z={Add 2 3} Z 5( )., (if) ( ) ( ).. Lazy declarative concurrency lazy, confluence. lazy,,.,,.. Lazy., (by-need synchronization) lazy, : {WaitNeeded X}: {Wait X}. lazy,. 7. WaitNeeded Add lazy : proc {LazyAdd X Y Z} thread {WaitNeeded Z} {Add X Y Z},, Mozart[34]. Z={LazyAdd 2 3} Z. lazy suspension. Z2={Add Z 4}, suspension, Z 5. Z2={LazyAdd Z 4}, lazy suspension. Z2,. 7,.

. Lazy declarative concurrency lazy, confluence. lazy,,.,,.. Lazy., (by-need synchronization) lazy, : {WaitNeeded X}: {Wait X}. lazy,. 7.

19 7 CONSTRAINT PROGRAMMING 19 Declartive concurrency and multi-core processors,. ( ),., (on-chip chche memory)., (, 2020 )[33],.,. :...., Java C++,,. [53].. :, ( ). :.,.,. ( ), ( ). agents. agents,. 7 Constraint Programming, (CSP). CSP :,, ( ),..,. (harnesses blind chance)?, :. Philippe Codognet [8].,.., (global condition):,.,,,..,,,., [3,41].., :,,,.,., (heuristic),.,.., Sarawat s [42].,.

agents. agents,. 7 Constraint Programming, (CSP). CSP :,, ( ),..,. (harnesses blind chance)?, :.

20 7 CONSTRAINT PROGRAMMING 20 :,.,.,., X=V, : X V., :, agent, (propagator)( 7.2 ) Some applications of constraint programming, (combinatorics), (planning), (scheduling), (optimization), (goal-oriented programming)... (finite domain),.,, x {0,, 9}, x {0,,9}. 8, s, e, n, d, m, o, r, y, {0,,9}, SENT+MORE=MONEY 8 ( ), 1000s+100e+10n+d+1000m+100o+10r +e = 10000m+1000o+100n+10e+y. s > 0 m > 0, alldiff(s, e, n, d, m, o, y, y)., :, ( 7.2 )., heuristic first-fail..., Numerica, [48]. Numerica (, Runge-Kutta predictor-corrector methods) : :,.,. Graph constraints and computer music 2006, (directed graph).,.,., (transitive closure),, (subgraph isomorphisms)[15,40,58].. Gecode MANCOOSI [20,43].. MANCOOSI. Spiessens (authority propagation)[46]. (subject) (object). :. :,.., :,. 8, SENT+MORE=MONEY, 0 9, 0,,.

8, s, e, n, d, m, o, r, y, {0,,9}, SENT+MORE=MONEY 8 ( ), 1000s+100e+10n+d+1000m+100o+10r +e = 10000m+1000o+100n+10e+y. s > 0 m > 0, alldiff(s, e, n, d, m, o, y, y)., :, ( 7.2 ).

21 7 CONSTRAINT PROGRAMMING 21..,.,..,,, How the constraint solver works, CSP :,.., (Philippe Codognet[8]) ( ). ( [47], Gecode ): :. agent,.,.., ( ). :, ( ),. :, C, P, P C P C., (C C),...., ( 17):. ( ). :.,., A*B:=C. A B, A*B=:12 A, B {1,..., 12} A, B {1, 2, 3, 4, 6, 12},. ( ), ( ).,.. C. C., first-fail,...,, A*,,. A* :.., 1,., (, ).

22 8 CONCLUSION AND SUGGESTION FOR GOING FURTHER 22 8 Conclusion and suggestion for going further.,. :,.,..,., lazy Hashkell[28], Erlang[6], SQL, Esterel[7], Oz[50]., Oz[34], Alice[38], Curry[4], CIAO[23]. ;! Oz,,, [50,51]. ( Oz) ( Common LISP). :,. Acknowledgements IRCAM. SELF- MAN (sixth framework programme contract 34084) MANCOOSI (seventh frame programme grant aggrement ). Arshia Cont, Antescofo, Gerard Assayag, IRCAM RepMus,.

Microsoft Word - 11900電腦軟體設計.doc

Microsoft Word - 11900電腦軟體設計.doc 技能檢定規範之一一九電腦軟體行政院勞工委員會職業訓練局編印軟體技術士技能檢定規範目錄一軟體技術士技能檢定規範說明... 1 二丙級軟體技術士技能檢定規範... 3 三乙級軟體技術士技能檢定規範... 5 四甲級軟體技術士技