www.digitalmars.com         C & C++   DMDScript  

D - Strategic Programming

reply Mark Evans <Mark_member pathlink.com> writes:
A short paper, worth a read (esp. for language designers).  Possibly some
relation to the success/failure (goal-directed) paradigm of Icon, but stated in
language-independent fashion.

Mark

http://www.cs.uu.nl/~visser/ftp/eosp.pdf

Strategic Programming

"Abstract. ... A strategy is a generic data-processing action which can traverse
into heterogeneous data structures while mixing uniform and type-specific
behaviour. ... Using a combinator style ... actual traversals are obtained by
passing the problem-specific ingredients as parameters to suitable [traversal]
schemes. The prime application domain for strategic programming is program
transformation and analysis. In this paper, we provide a language-independent
definition that generalises over existing incarnations of this idiom in term
rewriting, functional programming, and object-oriented programming."

"The key idea underlying strategic programming is the separation of
problem-specific ingredients of traversal functionality (i.e., basic actions)
and reusable traversal schemes (i.e., traversal control)."

"Depending on the incarnation of strategic programming within a certain
programming paradigm, strategies might correspond to pure functions, impure
functions, objects, and others. Further strategies might be statically typed,
dynamically typed and others.  We would first like to provide an abstract notion
of strategy that is not bound to any particular programming language or
paradigm, nor do we want to include unnecessary requirements."

"The strategic programming idiom encompasses both expressiveness and a method
for designing and implementing traversal functionality. The 'strategic'
expressiveness is basically that strategies are first-class citizens, and that
recursive traversal schemes can be composed in all kinds of ways from primitive
one-layer traversal combinators."

"Strategic programming is general-purpose generic programming since the
implementation of traversal functionality is a recurring theme. The more complex
the traversed data structures are ... the more substantial are the benefits one
can expect from strategic application development. This motivates the typical
application domains for strategic programming: language processing, document
processing, program transformation and analysis."

"The separation of basic actions and traversal control is at the very heart of
strategic programming, and it makes it easy to alter the design of a traversal.
These are some variation points for traversal control:

– transformation vs. query,
– top-down vs. bottom-up traversal,
– depth-first vs. breadth-first traversal,
– left-to-right traversal and vice versa,
– single vs. nested or cascaded traversal,
– local choice vs. cut vs. full backtracking,
– optimised variations on traversal schemes,
– full vs. one-hit vs. cut-off vs. path traversal,
– fixpoint by failure vs. fixpoint by equality test,
– effectfull [sic] traversal (accumulation, binding, etc.),
– type-specific vs. generic problem-specific ingredients."
Feb 21 2003
parent reply Bill Cox <bill viasic.com> writes:
Hmm... Is it my imagination, or is Strategic Programming mostly just 
really fancy iterators?

I'd love a good iterator mechanism in D, but "Strategic Programming" 
sounds more like a way to get research funding than a way to develop 
real applications...

Once again, thanks for the link!

Bill

Mark Evans wrote:

 A short paper, worth a read (esp. for language designers).  Possibly some
 relation to the success/failure (goal-directed) paradigm of Icon, but stated in
 language-independent fashion.
 
 Mark
 
 http://www.cs.uu.nl/~visser/ftp/eosp.pdf
 
 Strategic Programming
 
 "Abstract. ... A strategy is a generic data-processing action which can
traverse
 into heterogeneous data structures while mixing uniform and type-specific
 behaviour. ... Using a combinator style ... actual traversals are obtained by
 passing the problem-specific ingredients as parameters to suitable [traversal]
 schemes. The prime application domain for strategic programming is program
 transformation and analysis. In this paper, we provide a language-independent
 definition that generalises over existing incarnations of this idiom in term
 rewriting, functional programming, and object-oriented programming."
 
 "The key idea underlying strategic programming is the separation of
 problem-specific ingredients of traversal functionality (i.e., basic actions)
 and reusable traversal schemes (i.e., traversal control)."
 
 "Depending on the incarnation of strategic programming within a certain
 programming paradigm, strategies might correspond to pure functions, impure
 functions, objects, and others. Further strategies might be statically typed,
 dynamically typed and others.  We would first like to provide an abstract
notion
 of strategy that is not bound to any particular programming language or
 paradigm, nor do we want to include unnecessary requirements."
 
 "The strategic programming idiom encompasses both expressiveness and a method
 for designing and implementing traversal functionality. The 'strategic'
 expressiveness is basically that strategies are first-class citizens, and that
 recursive traversal schemes can be composed in all kinds of ways from primitive
 one-layer traversal combinators."
 
 "Strategic programming is general-purpose generic programming since the
 implementation of traversal functionality is a recurring theme. The more
complex
 the traversed data structures are ... the more substantial are the benefits one
 can expect from strategic application development. This motivates the typical
 application domains for strategic programming: language processing, document
 processing, program transformation and analysis."
 
 "The separation of basic actions and traversal control is at the very heart of
 strategic programming, and it makes it easy to alter the design of a traversal.
 These are some variation points for traversal control:
 
 ? transformation vs. query,
 ? top-down vs. bottom-up traversal,
 ? depth-first vs. breadth-first traversal,
 ? left-to-right traversal and vice versa,
 ? single vs. nested or cascaded traversal,
 ? local choice vs. cut vs. full backtracking,
 ? optimised variations on traversal schemes,
 ? full vs. one-hit vs. cut-off vs. path traversal,
 ? fixpoint by failure vs. fixpoint by equality test,
 ? effectfull [sic] traversal (accumulation, binding, etc.),
 ? type-specific vs. generic problem-specific ingredients."
Feb 21 2003
parent reply Mark Evans <Mark_member pathlink.com> writes:
Bill Cox says...

Hmm... Is it my imagination, or is Strategic Programming mostly just 
really fancy iterators?


Read the paper and find out.  I tried to make it clear with excerpts.  Feel free
to contact the authors.

Mark
Feb 21 2003
next sibling parent Mark Evans <Mark_member pathlink.com> writes:
The motivation for Strategic Programming is not necessarily enhancement of D,
but help with the compiler.  In other words, even if SP adds nothing to D the
language, it can ease the implementation.  That is important when we talk about
supporting various features and paradigms which we *would* like in the language
itself.

http://www.program-transformation.org/twiki/bin/view/Transform/ProgramTransformation

http://www.stratego-language.org/twiki/bin/view/Stratego/StrategoLanguage

http://www.csg.is.titech.ac.jp/~chiba/openc++.html

Mark
Feb 21 2003
prev sibling parent reply bill viasic.com writes:
In article <b368st$2mla$1 digitaldaemon.com>, Mark Evans says...

Bill Cox says...

Hmm... Is it my imagination, or is Strategic Programming mostly just 
really fancy iterators?


Read the paper and find out.  I tried to make it clear with excerpts.  Feel free
to contact the authors.

Mark


Ok... I read it again.  It still looks like fancy iterators to me.

I can't help but poke some fun at these guys...  They've come up with a whole
new vocabulary.  Here are two of my favorites:

"Strategic Programming" - "Programming with the use of Stragegies".  I swear I
copied and pasted that.

"Partiality" -  "The application of a strategy to a given datum may fail, and
recovery from failure is feasible."

Here's where they explain what stragegic programming is for:

"The abstract notion of strategy serves two purposes. Firstly, it corresponds to
a requirement specification for incarnating strategic programming in a given
programming language or paradigm."

Whoa!

"Secondly, it is a useful reference chart to assess other generic programming
approaches."

If my job were funding people who were a whole lot smarter than me, these guys
would definately get some serious cash :-)

Bill
Feb 21 2003
next sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
Here's an application of the techniques.  No language designer worth his salt
today can ignore partial specialization.  These slides are from a university
course.

Mark

http://www.cs.uu.nl/groups/ST/twiki/pub/Ist/ProgramTransformation/IST-PT2.pdf
http://www.cs.uu.nl/groups/ST/twiki/pub/Ist/ProgramTransformation/IST-PT3.pdf
http://www.cs.uu.nl/groups/ST/twiki/bin/view/Pt/CourseDescription
Feb 21 2003
parent bill viasic.com writes:
In article <b36scp$6j9$1 digitaldaemon.com>, Mark Evans says...

Here's an application of the techniques.  No language designer worth his salt
today can ignore partial specialization.  These slides are from a university
course.

Mark

http://www.cs.uu.nl/groups/ST/twiki/pub/Ist/ProgramTransformation/IST-PT2.pdf
http://www.cs.uu.nl/groups/ST/twiki/pub/Ist/ProgramTransformation/IST-PT3.pdf
http://www.cs.uu.nl/groups/ST/twiki/bin/view/Pt/CourseDescription


Hi, Mark.

These are nice links.  Thanks for posting them.  Sorry about poking fun at the
Strategic guys.

Bill
Feb 21 2003
prev sibling parent bill viasic.com writes:
"Strategic Programming" - "Programming with the use of Stragegies".  I swear I
copied and pasted that.


Grr!  How did Strategies get mispelled?  The spelling error must be mine since
it's spelled right in the paper.

Bill
Feb 21 2003