Re: deductive databases

Christopher Browne wrote:
> Oops! "ken quirici" <kquirici_at_yahoo.com> was seen spray-painting on a
wall:
> > Christopher Browne wrote:
> >> And while recursion is an abstraction that can cause confusion to
> >> those new to it, the ways of hiding it tends to lead to code that
is
> >> more opaque than straightforward recursion would have been.
> >
> > I have seen recursive algorithms that certainly left ME tangled up;
> > I can't remember what they were but they were the
A->B;C->A;B->C;D->C;
> > A->D type of thing. I have a feeling that people sometimes try to
do
> > everything by the most compact recursion possible and end up with
> > monstrously difficult programs (where by 'program' I mean the main
> > routine and all subroutines). In the world of commercial
programming
> > that I inhabit code readability and maintainability and
> > understandability count for more than recursive compactness. I
> > hesitate actually to call it elegance, which was my first choice,
> > because the kind of thing I sketched out above is not really
> > elegant, is it?
>
> In mathematics, it is entirely common for proofs to use recursion.
>
> "Proof by induction" is heavily used.
>
> Once someone is familiar with that, the use of recursion becomes just
> another technique, and the result is both compact and readable.
>
> If the inductive proof that your algorithm works has 4 statements,
> then a recursive implementation is quite likely to have somewhere
> around 4 statements.
>
> Adding in a stack will make it WAY more complicated, and hide the
> similarities between the proof and the implementation, thereby making
> it enormously more difficult to be confident that you got it right.
>
> > Would it be fair to say that recursion uses the subroutine call
> > arguments to replace stack entries? If so, I would prefer the stack
> > as a kind of universally available (let's just say for now)
> > state-descriptor, rather than carrying the info around in my
> > routine-travel-bag. Although if there is a text floating around
> > somewhere that goes into more detail about recursion vs.
non-recursion,
> > I would appreciate knowing about it. Always willing to turn the
page.
>
> No, the converse is what is true.
>
> Recursion is the more basic notion.
>
> In many languages, stacks are used in either representation. In ML,
> it is common to use heap-based allocation in lieu of stacks; were it
> not for that, I'd be able to call it "virtually universal" for them
to
> be essentially synonymous.
>
> > There of course are arguments about whether recursion is more
> > expensive of computer time than non-recursion - I won't weigh in on
> > that argument
>
> That falls TOTALLY into the realm of "implementational details."
>
> If your favorite compiler implements one or the other badly, then one
> will be massively less efficient than the other.
>
> In Scheme, the language design _requires_ handling tail recursive
> functions efficiently with the result that coding using a "manual
> stack" is quite likely to be MASSIVELY less efficient than utilizing
> tail recursion. With tail recursion, the function is known to be
> "eating" arguments as fast as they are being generated, such that the
> recursive call can be treated as a GOTO, and there is no need for any
> stack.
>
> Thus, faking recursion using a stack would consume ENORMOUS amounts
of
> additional resources for the (rather common) case of tail recursion.
>
> In FORTRAN, the opposite is likely to be true.
> --
> output = ("cbbrowne" "_at_" "gmail.com")
> http://linuxdatabases.info/info/postgresql.html
> Rules of the Evil Overlord #73. "I will not agree to let the heroes
go
> free if they win a rigged contest, even though my advisors assure
me
> it is impossible for them to win." <http://www.eviloverlord.com/>

Thanks for the reply.

Would the Aho book on Foundations of computer science be a good place to find out some of the stuff you were talking about?

Thanks.

Ken Received on Tue May 17 2005 - 16:42:33 CEST