技术控

    今日:133| 主题:49390
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] Program development by stepwise refinement

[复制链接]
别瘠薄闹 发表于 2016-10-14 13:35:09
115 9

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
Program development by stepwise refinement Wirth, CACM 1971
   This is the second of Barbara Liskov’s 7 ‘must-read’ CS papers . Wirth’s main point is that we have a tendency to focus far too much on mastering the syntax and style associated with a particular programming language, and nowhere near enough time on the process by which new programs are designed in the first place.
   … active programming consists of the design of new programs, rather than contemplation of old programs… Clearly, programming courses should teach methods of design and construction, and the selected examples should be such that a gradual development can be nicely illustrated.
   By far the bulk of the paper though, is dedicated to one worked example of this principle, introducing the idea of stepwise refinement .  The goal is to write a program to solve the eight-queens problem .
   
Program development by stepwise refinement-1 (particular,designed,examples,programs,selected)
Picture credit: Wikipedia
  Wirth starts out with a very high level sketch of a solution, and gradually fills in the details to make both a more concrete and a more efficient implementation over time.
  In each step, one or several instruction of the given program are decomposed into more detailed instructions. This successive decomposition or refinement of specifications terminates when all instructions are expressed in terms of an underlying computer or programming language, and must therefore be guided by the facilities available on that computer or language.
   It’s not just about refinement of the tasks involved in the program; crucially the data and data representations may also need to be refined. “ It is natural to refine program and data specifications in parallel .” It’s interesting to think about the task-based decomposition that naturally arises from this method, and contrast it with Parnas’ advice in “ On the criteria to be used in decomposing systems into modules “. The stepwise refinement example in this paper though is ‘in the small,’ and really about the stepwise refinement of an algorithm as much as anything.
   Reading through the worked example, I’m glad we have higher-level programming languages to work with these days! (The paper uses Algol 60). There are a few too many global variables and pointers for modern tastes.  The thinking process is still valuable though.
  A guideline in the process of stepwise refinement should be the principle to decompose decisions as much as possible, to untangle aspects which are only seemingly interdependent, and to defer those decisions which concern details of representation as long as possible.
  Here are the steps in Wirth’s refinement:
  Up-front thinking…

  
       
  • Start out with a very simple brute force algorithm that tries all possible placements until it finds one that works.   
  • Realise that this would be highly inefficient (about 7 hours on the technology of the day), and thus we need to find a shortcut…   
  • Reduce the number of candidate solutions that must be generated and tried, using a little domain knowledge: in this case, that there must be one queen in every column. This process would find an answer in about 100 seconds on the technology of the day.   
  • Realise that we can do better by being systematic about the way we generate trial solutions via stepwise construction of trial solutions .  That is, we start out by placing a queen in the first column, and then adding a queen in successive columns at each next step. If at any point in this process one or more queens conflict with each other we know there is no point going any further, so instead we can backtrack and try again from there.  This version generates 876 partial solutions before finding a complete one, and takes about 0.09 seconds on the technology of the day.  
  Development of the program…

  Only at this point does Wirth think about moving into code. The first version is expressed in terms of a number of high-level procedures, whose details have yet to be filled in:

Program development by stepwise refinement-2 (particular,designed,examples,programs,selected)

  The next step is to begin to fill-in the details of those procedures, at which point we can no longer defer any decision about data representation.
  A common difficulty in program design lies in the unfortunate fact that at the stage where decisions about data representations have to be made, it often is still difficult to foresee the details of the necessary instructions operating on the data, and often quite impossible to estimate the advantages of one possible representation over another. In general, it is therefore advisable to delay decisions about data representation as long as possible…
   (Or as Parnas would advise us, to hide information about data representation from the rest of the program).
   With a little thought, Wirth rejects the straightforward 8×8 boolean matrix in favour of an array of columns.  Analysing the efficiency of the resulting structure, Wirth then introduces auxiliary variables that make it more computationally efficient to determine whether or not a given square is safe to place a queen on.
  Upon every introduction of auxiliary data, care has to be taken of their correct initialization…
  The final version of the program still displays the structure of the version designed in the first step… “other, equally valid solutions can be suggested and be developed by the same process of stepwise refinement.
  Wirth concludes with five remarks about the process:
  
       
  • Program construction consists of a sequence of refinement steps   
  • The degree of modularity obtained during the refinement will determine the ease or difficulty with which a program can be adapted to changes or extensions   
  • During stepwise refinement, a notation natural to the problem in hand should be used as long as possible… “the direction in which the notation develops during the process of refinement is determined by the language in which the program must ultimately be specified.”   
  • Each refinement implies a number of design decisions based on a set of design criteria.   
  • Even the small example program in the paper requires quite a lengthy explanation, indicating that careful programming is not a trivial subject!  
  Among these criteria [for the design decisions] are efficiency, storage economy, clarity, and regularity of structure. Students must be taught to be conscious of the involved decisions and to critically examine and to reject solutions, sometimes even if they are correct as far as the result is concerned; they must learn to weigh the various aspects of design alternatives in the light of these criteria. In particular, they must be taught to revoke earlier decisions and to back up, if necessary, even to the top.
友荐云推荐




上一篇:Spring Data (Part 5): Paging and Sorting
下一篇:Gradient Descent Learns Linear Dynamical Systems
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

龙海鹰 发表于 2016-10-14 17:10:56
楼上长在线啊?
回复 支持 反对

使用道具 举报

iwyd0qFo 发表于 2016-10-17 15:41:47
一脸的虚假繁荣。
回复 支持 反对

使用道具 举报

李孟桃 发表于 2016-10-20 10:52:16
以后要跟别瘠薄闹好好学习学习!
回复 支持 反对

使用道具 举报

zvex5299 发表于 2016-10-25 06:03:28
会发帖就交得起电费
回复 支持 反对

使用道具 举报

段能凤 发表于 2016-10-31 19:07:16
阅!谢谢分享
回复 支持 反对

使用道具 举报

黄兰蕊 发表于 2016-11-16 19:04:15
出问题先从自己身上找原因,别一便秘就怪地球没引力.
回复 支持 反对

使用道具 举报

-_L_._c_. 发表于 2016-11-18 21:45:51
路过,我是来打酱油的!
回复 支持 反对

使用道具 举报

没有他不习惯 发表于 2016-11-20 14:46:42
别瘠薄闹就是这么任性
回复 支持 反对

使用道具 举报

李曼 发表于 2016-11-21 08:38:49
瞄瞄,不忍直视
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表