a defense of ad hoc software development
in [Lisp]
|
Prev: Some help with sort
Next: SBCL optimization
From: Peter J. Holzer on 17 Feb 2010 12:31 On 2010-02-17 07:21, Ron Garret <rNOSPAMon(a)flownet.com> wrote: > In article ><2f580d01-8f4c-4c08-a6a6-8fc84dd4658e(a)15g2000yqa.googlegroups.com>, > Mark Tarver <dr.mtarver(a)ukonline.co.uk> wrote: >> QUOTE >> You can't write specifications that say exactly what you want. If the >> specification were that precise, then they would be the program. >> UNQUOTE >> >> That's a very clever and profound observation from Paul Graham. > > It is also demonstrably false. [...] > You don't have to get anywhere near that esoteric. There are many > precise specifications that are nonetheless very hard or impossible to > render into code, the classic example being F(X,Y)=TRUE if and only if X > is the encoding of a program that halts when run on input Y. Imprecise > specifications are only one of many potential challenges to producing > code that does what you want. Inverting SHA1, factoring RSA1024, and > decrypting AES256 are all specifications that can be rendered with > absolute precision. They can also be coded almost as easily as specified. The program just won't complete in any reasonable time. > But that will not help you at all when it comes time to code them up. That's because you don't want just any code which solves the problem, you want fast code which solves it. And while it is easy to write into the specification "must finish within X seconds" it may be hard to find code which satisifies this constraint. IMHO that fits well with comment in the other posting: The specification is *a* program, but it is not *the* program, because even if a suitable interpreter exists (or translation into an existing programming language is straightforward) it would often be ridiculously inefficient. hp
From: Ron Garret on 17 Feb 2010 14:28 In article <slrnhno94r.num.hjp-usenet2(a)hrunkner.hjp.at>, "Peter J. Holzer" <hjp-usenet2(a)hjp.at> wrote: > On 2010-02-16 22:00, dan(a)telent.net <dan(a)telent.net> wrote: > > Mark Tarver <dr.mtarver(a)ukonline.co.uk> writes: > > > >> QUOTE > >> You can't write specifications that say exactly what you want. If the > >> specification were that precise, then they would be the program. > >> UNQUOTE > >> > >> That's a very clever and profound observation from Paul Graham. The > >> formal methods people might disagree though. > > > > So would I. > > > > I would like a program that calculates the number x for which x*x=52 > > > > That specification says exactly what I want, > > No. Most importantly it doen't say what the output should look like. > Mathematically, the result is 2*sqrt(13). But most likely you don't want > a symbolic result, but a floating point number with some number of > (binary or decimal) digits. > > > but it's of no help at all in creating an algorithm for how to get it. > > It is if your programming language includes a primitive or library > function for solving quadratic equations. > > I would like to change one word in PG's quip: > > You can't write specifications that say exactly what you want. If the > specification were that precise, then they would be *a* program. > > If the specification doesn't say how to solve a small, well-understood > subproblem, that's not very much different from calling a library > function in a program. As a different example, consider sorting: The > specification may specify the intended sort order but not the sorting > algorithm. In a similar way, many programming languages provide a sort > function. The programmer using this function typically doesn't care > whether that sort function implements a quickersort, heapsort or > mergesort, or some hybrid scheme. He just specifies an order (often in > the form of a comparison function) and leaves the details to the > implementation. > > The more I think about this the more I think PG has stumbled upon a > truth here: A specification really is a program. But the "programming > language" in which it is written is almost always declarative and not > imperative. There usually isn't any interpreter for the language except > the brains of the audience (although parts of the specification/program > may be written in a formal language). Ironically, it's PG's own lack of precision in specifying what he meant that is leading to confusion here. There are two fundamentally different kinds of specifications, those that specify WHAT the result should be, and those that specify HOW the result is to be obtained. Both of these can be either vague or specific. Notwithstanding PG's use of the phrase "what you want" it appears that he was actually talking about specifying how, not what. (This distinction is not unique to software. PG's own example of a piece of metal cut to a particular shape is a HOW specification. A WHAT specification would be something like: a bracket with a particular tensile strength...) The issue PG was addressing (and that this thread seems to be about) is the perennial debate about how specific a HOW spec should be before you make your first attempt to render it into a form that is suitable as input to a compiler. The right answer has a lot to do with how expensive it is to run your compiler. If compilation is expensive it makes sense to put more effort into making sure you've thought things through before you try to compile. If compilation (and more to the point, recompilation) is cheap then it makes less sense. Then there is the completely orthogonal issue of how to render WHAT specs into HOW specs, which is a fundamentally difficult problem. It has to be. If it weren't you could just take the following WHAT spec: * A program that takes a WHAT spec and renders it as a HOW spec and render *that* as a how spec and you'd never again have to write any code. In fact, just *writing down* a WHAT spec (let alone finding a corresponding HOW spec) is a fundamentally difficult problem. You want a program to compute the square root of 52? What does that actually mean? What form do you want the answer to take? Symbolic? Floating point? BCD? A drawing of the diagonal of a square with an area of 52? How long are you willing to wait for your answer? How many digits of precision do you want? How much are you willing to pay? rg --- Ron's second law: the hardest part of getting what you want is deciding what you actually want.
From: J�rgen Exner on 17 Feb 2010 17:06 Ron Garret <rNOSPAMon(a)flownet.com> wrote: >There are two fundamentally different kinds of specifications, those >that specify WHAT the result should be, Yes. >and those that specify HOW the >result is to be obtained. That would be over-specified. jue
From: Peter J. Holzer on 20 Feb 2010 12:25 On 2010-02-17 19:28, Ron Garret <rNOSPAMon(a)flownet.com> wrote: > In article <slrnhno94r.num.hjp-usenet2(a)hrunkner.hjp.at>, > "Peter J. Holzer" <hjp-usenet2(a)hjp.at> wrote: > >> On 2010-02-16 22:00, dan(a)telent.net <dan(a)telent.net> wrote: >> > Mark Tarver <dr.mtarver(a)ukonline.co.uk> writes: >> >> QUOTE >> >> You can't write specifications that say exactly what you want. If the >> >> specification were that precise, then they would be the program. >> >> UNQUOTE >> >> >> >> That's a very clever and profound observation from Paul Graham. The >> >> formal methods people might disagree though. >> > >> > So would I. >> > >> > I would like a program that calculates the number x for which x*x=52 >> > >> > That specification says exactly what I want, >> >> No. [...] >> >> > but it's of no help at all in creating an algorithm for how to get it. >> >> It is if your programming language includes a primitive or library >> function for solving quadratic equations. >> >> I would like to change one word in PG's quip: >> >> You can't write specifications that say exactly what you want. If the >> specification were that precise, then they would be *a* program. >> >> If the specification doesn't say how to solve a small, well-understood >> subproblem, that's not very much different from calling a library >> function in a program. As a different example, consider sorting: The >> specification may specify the intended sort order but not the sorting >> algorithm. In a similar way, many programming languages provide a sort >> function. The programmer using this function typically doesn't care >> whether that sort function implements a quickersort, heapsort or >> mergesort, or some hybrid scheme. He just specifies an order (often in >> the form of a comparison function) and leaves the details to the >> implementation. >> >> The more I think about this the more I think PG has stumbled upon a >> truth here: A specification really is a program. But the "programming >> language" in which it is written is almost always declarative and not >> imperative. There usually isn't any interpreter for the language except >> the brains of the audience (although parts of the specification/program >> may be written in a formal language). > > Ironically, it's PG's own lack of precision in specifying what he meant > that is leading to confusion here. > > There are two fundamentally different kinds of specifications, those > that specify WHAT the result should be, and those that specify HOW the > result is to be obtained. Both of these can be either vague or > specific. Notwithstanding PG's use of the phrase "what you want" it > appears that he was actually talking about specifying how, not what. Since I haven't read PG's book I can't comment on that. > The issue PG was addressing (and that this thread seems to be about) is > the perennial debate about how specific a HOW spec should be before you > make your first attempt to render it into a form that is suitable as > input to a compiler. The right answer has a lot to do with how > expensive it is to run your compiler. If compilation is expensive it > makes sense to put more effort into making sure you've thought things > through before you try to compile. If compilation (and more to the > point, recompilation) is cheap then it makes less sense. Compilation time is only one factor in this. You also need to consider the cost of testing, the cost of rewriting code, the cost of changing interfaces, the cost of missing deadlines, etc. And most importantly it misses the fact that the development of your HOW spec doesn't stop when "you make your first attempt to render it into a form that is suitable as input to a compiler", and the development of your WHAT spec doesn't stop when you start developing your HOW spec. Users often have only a very vague notion of what they need and they have poor imagination and abstraction facilities. When you show them your first prototype they will tell you that they wanted something completely different. > Then there is the completely orthogonal issue of how to render WHAT > specs into HOW specs, which is a fundamentally difficult problem. It > has to be. If it weren't you could just take the following WHAT spec: > > * A program that takes a WHAT spec and renders it as a HOW spec That's not a WHAT spec. It neither specifies the input nor the output. > and render *that* as a how spec and you'd never again have to write any > code. I think you missed my point: A formal WHAT spec *is* code. So if you have that translator you just write code in your declarative WHAT language instead of your imperative HOW language. And as you write yourself: > In fact, just *writing down* a WHAT spec (let alone finding a > corresponding HOW spec) is a fundamentally difficult problem. So you may have solved the simpler part of the problem and be left with the harder part. (this is not true in all cases - obviously there are problems which are simple to describe and hard to solve, but in my experience most of the time the really hard part is the WHAT, not the HOW). [rest deleted as it only repeats what I wrote before] hp
From: Ron Garret on 21 Feb 2010 02:47
In article <slrnho06o8.g8e.hjp-usenet2(a)hrunkner.hjp.at>, "Peter J. Holzer" <hjp-usenet2(a)hjp.at> wrote: > > The issue PG was addressing (and that this thread seems to be about) is > > the perennial debate about how specific a HOW spec should be before you > > make your first attempt to render it into a form that is suitable as > > input to a compiler. The right answer has a lot to do with how > > expensive it is to run your compiler. If compilation is expensive it > > makes sense to put more effort into making sure you've thought things > > through before you try to compile. If compilation (and more to the > > point, recompilation) is cheap then it makes less sense. > > Compilation time is only one factor in this. You also need to consider > the cost of testing, the cost of rewriting code, the cost of changing > interfaces, the cost of missing deadlines, etc. All true. If any of these are expensive it makes more sense to do more design up front. > And most importantly it misses the fact that the development of your HOW > spec doesn't stop when "you make your first attempt to render it into a > form that is suitable as input to a compiler", and the development of > your WHAT spec doesn't stop when you start developing your HOW spec. > Users often have only a very vague notion of what they need and they > have poor imagination and abstraction facilities. When you show them > your first prototype they will tell you that they wanted something > completely different. Yep. > > Then there is the completely orthogonal issue of how to render WHAT > > specs into HOW specs, which is a fundamentally difficult problem. It > > has to be. If it weren't you could just take the following WHAT spec: > > > > * A program that takes a WHAT spec and renders it as a HOW spec > > That's not a WHAT spec. It neither specifies the input nor the output. Sure it does. The input is a WHAT spec. The output is a HOW spec. I haven't gone into detail about what WHAT specs and HOW specs are and how they are represented, but I could. > > and render *that* as a how spec and you'd never again have to write any > > code. > > I think you missed my point: A formal WHAT spec *is* code. I didn't miss that point, I just disagree with it. There are lots of WHAT specs that are not and cannot be code. The halting problem. Computing Chaitin's omega. Even inverting SHA1 or factoring large RSA keys could be examples. > So if you > have that translator you just write code in your declarative WHAT > language instead of your imperative HOW language. And as you write > yourself: > > > > In fact, just *writing down* a WHAT spec (let alone finding a > > corresponding HOW spec) is a fundamentally difficult problem. > > So you may have solved the simpler part of the problem and be left with > the harder part. (this is not true in all cases - obviously there are > problems which are simple to describe and hard to solve, but in my > experience most of the time the really hard part is the WHAT, not the > HOW). They can both be hard. rg |