[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: The subsetting has begun


c square root algorithm
On Monday 24 February 2003 00:36, Karl Waclawek wrote:
> > Well, in Java, an exception handler is executed in the environment it is
> > declared in, rather than where it's thrown. That means that if you
> > rethrow an exception from a catch block, the catching of that exception
> > begins in the stack frame of the try statement, not of the original
> > throw.
>
> Throwing it back, so to speak - cool!
>
> <snip good stuff/>
>
> Thanks for taking the time to write such a detailed reply!

Wierd languages are my hobby ;-)

> > > How fast can they be - if the problem is inherently more complex,
> > > then implementations tend to be more complex and slower too.
> >
> > I think the runtime algorithm required to match the thrown exception to
> > the correct handler is probably the most inherently complex part. The
> > actual control transfer can be done most efficiently with a stored
> > failure continuation.
>
> The question is: at what cost does on get efficient exception handling?
> Are continuation languages slower and/or more complex to implement?

The main cost is that you can't use a stack, it has to be a linked list 
instead, with garbage collection.

But there are various cheats to get around this; highly generational GC can 
reduce the cost somewhat, and there are hybrid approaches where you do lots 
of inlining to reduce the number of call frames you need, or use stacks for 
bits of code that are always jumped across in one fell swoop (eg, between a 
try clause and the throw clause, many nested calls can be handled on a stack).

Research, as they say, is still in progress.

> > Indeed, for a specific case like stopping SAX processing, you
> > could just put an 'abort' continuation in thread-local storage before
> > starting the SAX parser, and just invoke it when needed in the SAX
> > handler :-)
>
> Now I am getting even more dissatisfied. In addition to genericity
> I also want continuations in Delphi/Java/C#/C++. (it's probably possible
> in C++, but I am no expert in it). ;-)

Well C kind of had a limited form of continuations in setjmp / longjmp... 
just you could mess the stack up with them. You could only ever jump *up* the 
stack, never down, so you could use them to escape to an error handler but 
they couldn't handle such continuation tricks as nondeterminstic algorithms.

Nondeterministic algorithms, I hear you ask? Well...

Imagine a function like 'square root'. Mathematicall, every number has two 
square roots; 2*2 = 4, (-2)*(-2)=4, so sqrt(4) = 2 and -2.

Needless to say, you can't really express that easily in software. You could 
have sqrt return a list of two numbers, but that's missing the point in a way.

What you could do, in C for example, is to have the sqrt function call fork() 
and return a different number in each fork. If this were part of an equation 
solver, you would have to try both possible return values every time you got 
to sqrt() or a similar function; some branches would return no solutions and 
thus would give up, others would yield results.

But doing it with lots of forks can consume an exponentially growing number 
of OS resources. What you can do instead is to, every time you encounter a 
sqrt(), preserve a 'retry continuation' in a global list that, if invoked, 
will restart execution from the sqrt but return the negative root. Having 
saved that continuation, return the positive root.

Then you can define the 'abort' function (called when a line of enquiry 
fails) to pop the top off of the list of retry continuations and invoke it.

When the computation returns with an actual value, if there are still untried 
retry continuations, then there may be more solutions available, so you can 
output the solution you have found and try another retry.

In a way, you are modelling the many worlds interpretation of quantum 
mechanics...

Don't get me started on how different programming languages model time! C has 
time implicitly handled by an advancing instruction pointer and a mutable 
world-state, whereas Concurrent Clean programs model time by having a World 
object and methods such as 'sleep' that accepts a World and a number of 
seconds, and returns a World like the one passed in except that many seconds 
have passed...

> Karl

ABS

-- 
A city is like a large, complex, rabbit
 - ARP

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
 

Stylus Studio has published XML-DEV in RSS and ATOM formats, enabling users to easily subcribe to the list from their preferred news reader application.


Stylus Studio Sponsored Links are added links designed to provide related and additional information to the visitors of this website. they were not included by the author in the initial post. To view the content without the Sponsor Links please click here.

Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.