Blue-Maned_Hawk <bluemanedhawk@invalid.invalid> writes:
> Richard Kettlewell wrote:
>> It’s more than 20 years since I last had to integrate a C library which
>> reported errors via longjmp() and I’m still bitter about it.
>
> I have never encountered a library which does that. Which library was
> that?

libpng

>> As a matter of API design, I’d rather C library communicated errors
>> via return values (and pointer parameters, where more complex error
>> information is required).
>
> Personally, i think that, at least for a library, an error should
> _only_ be communicated by return value. If more complex information
> is required, then the return value can be made more complex. I don't
> think i've ever used a library that communicates information via a
> pointer parameter.

Return value plus a pointer to additional information can certainly be
transformed into a struct containing both, though there’s an impact on
source code verbosity, object code size and performance.

For example if the extra information goes up to, say, 64 bytes, putting
it in a return value commits you to a 64-byte copy on every
return. However if it’s a pointer parameter, you only need to fill in
the fields relevant to the error that actually happened. In the happy
path, where there’s no error, that’s none of them.

--
https://www.greenend.org.uk/rjk/

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>> [..how should errors be handled..]
>>>
>>>> How would you prefer these sorts of thing to be signalled?
>>>
>>> Let me give just one example.
>>>
>>> I wrote some code not long ago to add a value to a set of values,
>>> where the set is represented using a recursive binary tree structure
>>> (like red-black trees, but a little different). Usually we may
>>> expect that a request to add a value would offer a value not already
>>> included in the set, but certainly it can happen that there is a
>>> call to add a value that is already included, in which case the top
>>> level return value should be the original tree structure.
>>>
>>> I thought it would be easier to write a simple recursive routine
>>> that assumes the to-be-added value is not yet included in the set,
>>> and if that assumption is violated raise an exception that is caught
>>> at the outermost level and simply returns the original argument tree
>>> value. Certainly the code could have been written to handle the
>>> already-present situation at each level of the recursion, but it was
>>> much easier and much cleaner to handle it by raising an exception.
>>
>> This is one of those cases where I just have to take your word for it,
>> (and I am happy to do that).
>
> Responding here to just this one part.
>
> Here is a simpler version of the code, for an ordinary
> binary tree, and without any rebalancing:
>
> module TreeSet = struct
> type 'a treeset = Empty | Node of 'a treeset * 'a * 'a treeset
> exception Present
>
> let add tree element =
> let rec add t e =
> match t with
> | Empty -> Node( Empty, e, Empty )
> | Node( a, v, b ) ->
> if e < v then Node( add a e, v, b ) else
> if e > v then Node( a, v, add b e ) else
> raise Present
> in
> try add tree element with Present -> tree
>
> end

I'm not getting it. I'd write 'else t' rather than 'else raise Present'
and I could then do away with the wrapping 'add' function.

I worry we are getting away from C, but the point is likely to be much
simpler to make in OCaml (or Caml).

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>
>>>> [..how should errors be handled..]
>>>>
>>>>> How would you prefer these sorts of thing to be signalled?
>>>>
>>>> Let me give just one example.
>>>>
>>>> I wrote some code not long ago to add a value to a set of values,
>>>> where the set is represented using a recursive binary tree structure
>>>> (like red-black trees, but a little different). Usually we may
>>>> expect that a request to add a value would offer a value not already
>>>> included in the set, but certainly it can happen that there is a
>>>> call to add a value that is already included, in which case the top
>>>> level return value should be the original tree structure.
>>>>
>>>> I thought it would be easier to write a simple recursive routine
>>>> that assumes the to-be-added value is not yet included in the set,
>>>> and if that assumption is violated raise an exception that is caught
>>>> at the outermost level and simply returns the original argument tree
>>>> value. Certainly the code could have been written to handle the
>>>> already-present situation at each level of the recursion, but it was
>>>> much easier and much cleaner to handle it by raising an exception.
>>>
>>> This is one of those cases where I just have to take your word for it,
>>> (and I am happy to do that).
>>
>> Responding here to just this one part.
>>
>> Here is a simpler version of the code, for an ordinary
>> binary tree, and without any rebalancing:
>>
>> module TreeSet = struct
>> type 'a treeset = Empty | Node of 'a treeset * 'a * 'a treeset
>> exception Present
>>
>> let add tree element =
>> let rec add t e =
>> match t with
>> | Empty -> Node( Empty, e, Empty )
>> | Node( a, v, b ) ->
>> if e < v then Node( add a e, v, b ) else
>> if e > v then Node( a, v, add b e ) else
>> raise Present
>> in
>> try add tree element with Present -> tree
>>
>> end
>
> I'm not getting it. I'd write 'else t' rather than 'else raise
> Present' and I could then do away with the wrapping 'add' function.

Doing that would result in returning a valid tree, but it would also
needlessly replicate all nodes starting from the point where the
match was found and going up to the root. The consequence is more
cycles used and more demand on the memory allocator. The technique
of raising an exception avoids those shortcomings (and also it
preserves tree identity, which can be important in some situations).

> I worry we are getting away from C, but the point is likely to be
> much simpler to make in OCaml (or Caml).

I have another example. The example doesn't include any C code, but
I will talk about some concerns that pertain to C.

Suppose we are writing a compiler for a large programming language.
The compiler should make use of available resources, especially
memory resources, when it can, but also should be able to compile
large programs even when the amount of memory available is much more
limited. How much memory is available is not known in advance; we
find out when a call to malloc() or realloc() returns NULL. I note
in passing that the PL/I(F) compiler from IBM could translate full
PL/I even if limited to only 44 K bytes of user memory; to do that
it needed 110 physical passes over source text or structures created
and stored in disk files.

The idea in essence is to have two compilers in one: one taking a
conventional approach using regular dynamic memory allocation (in
other words malloc() etc), and the other using an IBM-style multiple
passes scheme that stores intermediate data in disk files. To
compile a program we start the first compiler under an umbrella of
setjmp(), which going forward assumes all memory allocations will
succeed. To allocate memory we call wrapper functions for malloc()
or realloc(), which will do a longjmp() if an allocation fails.
Upon receipt of the longjmp() "exception" the outer setjmp() call
starts over using the second approach, which is of course much
slower but also much less demanding of main memory.

To make this work we might have to track malloc()'s and free()'s so
that any not-yet-released memory can be reclaimed before beginning
the alternate system, but I think that is straightforward and not in
need of any further explanation.

I admit this example isn't very compelling given that even small
computers today have multiple gigabytes of RAM. But I think it
isn't hard to imagine an analogous problem in a more limited
environment, for example running in a VM on a co-located server.
(I have run out of "RAM" when running a program on my colo server
here. It was quite confusing when it first happened.)

Anton Shepelev <anton.txt@gmail.moc> writes:

> Tim Rentsch:
>
>> I wrote some code not long ago to add a value to a set of
>> values, where the set is represented using a recursive
>> binary tree structure (like red-black trees, but a little
>> different). Usually we may expect that a request to add a
>> value would offer a value not already included in the set,
>> but certainly it can happen that there is a call to add a
>> value that is already included, in which case the top
>> level return value should be the original tree structure.
>
> Returning an error flag (or code) all the way up the call
> stack may seem (and be) slow and cumbersome. If that case,
> one can rewrite the recursive function iteratively, with an
> explicit stack. I, however, think that an extra `if' in the
> recursive function is so much less fuss

Besides making the code slower and substantially longer,
the resulting code would take a lot more effort to read
and understand. In most cases lots of if()'s means the
code is poorly written and should be re-thought.

In this particular case re-writing the code to be iterative
rather than recursive, and using an explicit stack, is a
total non-starter. It's good to know the theoretical result
that recursion can be turned into iteration, but in practice
the two approaches are often not interchangeable.

Tim Rentsch to Anton Shepelev:

> > Returning an error flag (or code) all the way up the
> > call stack may seem (and be) slow and cumbersome. If
> > that case, one can rewrite the recursive function
> > iteratively, with an explicit stack. I, however, think
> > that an extra `if' in the recursive function is so much
> > less fuss
>
> Besides making the code slower and substantially longer,

Substantially slower along the unhappy path only.
Substantially lobger -- I don't think so, because regardless
of recursion depth, there is just one recursive function,
and if you want to handle a single type of error, you would
need a single extra `if' in it.

> the resulting code would take a lot more effort to read
> and understand.

Explicit control of execution flow is clearer for several
reasons:

1. No out-of-bandwith signalling.

2. Errors are handled uniformly with any other condigions
in the program using the same basic facilities.

3. Errors are handled where they occur, in a manner
visible to the programmer reading the piece code that
may produce errors.

> In most cases lots of if()'s means the code is poorly
> written and should be re-thought.

Programms are all about logic, making decisions. It is not
the quantity, but the quality of `if's that may indicate a
flaw in coding, e.g. because of the failure to use dependeny
injection correctly, passing many flags into called
functions, &c. The if-else-if-else... chain discussed in a
parallel thread is itself a set of many nested if
statements, but it is not considered good or bad coding
based on its length.

> In this particular case re-writing the code to be
> iterative rather than recursive, and using an explicit
> stack, is a total non-starter.

Perhaps, I have not tried it. When, however, I rewrote
quicksort in a interative manner I actually like the result!

> It's good to know the theoretical result that recursion
> can be turned into iteration, but in practice the two
> approaches are often not interchangeable.

Indeed. Recursion for readability, iteration with a stack
for performance.

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

Tim Rentsch:

> The idea in essence is to have two compilers in one: one
> taking a conventional approach using regular dynamic
> memory allocation (in other words malloc() etc), and the
> other using an IBM-style multiple passes scheme that
> stores intermediate data in disk files. To compile a
> program we start the first compiler under an umbrella of
> setjmp(), which going forward assumes all memory
> allocations will succeed. To allocate memory we call
> wrapper functions for malloc() or realloc(), which will do
> a longjmp() if an allocation fails. Upon receipt of the
> longjmp() "exception" the outer setjmp() call starts over
> using the second approach, which is of course much slower
> but also much less demanding of main memory.
> [...]
> I admit this example isn't very compelling given that even
> small computers today have multiple gigabytes of RAM.

No, the availablity of lots of RAM in modern computers in
mere incidental to your example and in no way affects it.

How about this example: a recursive-descent parser for a
deeply nested grammar. How does one handle and reort an
error encountered ten invocations underground? Is it a
simpler example of the same problem?

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>>
>>>>> [..how should errors be handled..]
>>>>>
>>>>>> How would you prefer these sorts of thing to be signalled?
>>>>>
>>>>> Let me give just one example.
>>>>>
>>>>> I wrote some code not long ago to add a value to a set of values,
>>>>> where the set is represented using a recursive binary tree structure
>>>>> (like red-black trees, but a little different). Usually we may
>>>>> expect that a request to add a value would offer a value not already
>>>>> included in the set, but certainly it can happen that there is a
>>>>> call to add a value that is already included, in which case the top
>>>>> level return value should be the original tree structure.
>>>>>
>>>>> I thought it would be easier to write a simple recursive routine
>>>>> that assumes the to-be-added value is not yet included in the set,
>>>>> and if that assumption is violated raise an exception that is caught
>>>>> at the outermost level and simply returns the original argument tree
>>>>> value. Certainly the code could have been written to handle the
>>>>> already-present situation at each level of the recursion, but it was
>>>>> much easier and much cleaner to handle it by raising an exception.
>>>>
>>>> This is one of those cases where I just have to take your word for it,
>>>> (and I am happy to do that).
>>>
>>> Responding here to just this one part.
>>>
>>> Here is a simpler version of the code, for an ordinary
>>> binary tree, and without any rebalancing:
>>>
>>> module TreeSet = struct
>>> type 'a treeset = Empty | Node of 'a treeset * 'a * 'a treeset
>>> exception Present
>>>
>>> let add tree element =
>>> let rec add t e =
>>> match t with
>>> | Empty -> Node( Empty, e, Empty )
>>> | Node( a, v, b ) ->
>>> if e < v then Node( add a e, v, b ) else
>>> if e > v then Node( a, v, add b e ) else
>>> raise Present
>>> in
>>> try add tree element with Present -> tree
>>>
>>> end
>>
>> I'm not getting it. I'd write 'else t' rather than 'else raise
>> Present' and I could then do away with the wrapping 'add' function.
>
> Doing that would result in returning a valid tree, but it would also
> needlessly replicate all nodes starting from the point where the
> match was found and going up to the root. The consequence is more
> cycles used and more demand on the memory allocator.

How can OCaml avoid making the allocations until it knows the exception
won't be raised? Are they not all still being done?

> The technique
> of raising an exception avoids those shortcomings (and also it
> preserves tree identity, which can be important in some situations).

I agree about the identity. I am not used to relying on the identity in
situations like this (probably because of Haskell!) but I might find
some time to work out how to preserve identity without an exception. I
fear it will be messier that your simple solution.

>> I worry we are getting away from C, but the point is likely to be
>> much simpler to make in OCaml (or Caml).
>
> I have another example. The example doesn't include any C code, but
> I will talk about some concerns that pertain to C.
>
> Suppose we are writing a compiler for a large programming language.
> The compiler should make use of available resources, especially
> memory resources, when it can, but also should be able to compile
> large programs even when the amount of memory available is much more
> limited. How much memory is available is not known in advance; we
> find out when a call to malloc() or realloc() returns NULL. I note
> in passing that the PL/I(F) compiler from IBM could translate full
> PL/I even if limited to only 44 K bytes of user memory; to do that
> it needed 110 physical passes over source text or structures created
> and stored in disk files.
>
> The idea in essence is to have two compilers in one: one taking a
> conventional approach using regular dynamic memory allocation (in
> other words malloc() etc), and the other using an IBM-style multiple
> passes scheme that stores intermediate data in disk files. To
> compile a program we start the first compiler under an umbrella of
> setjmp(), which going forward assumes all memory allocations will
> succeed. To allocate memory we call wrapper functions for malloc()
> or realloc(), which will do a longjmp() if an allocation fails.
> Upon receipt of the longjmp() "exception" the outer setjmp() call
> starts over using the second approach, which is of course much
> slower but also much less demanding of main memory.
>
> To make this work we might have to track malloc()'s and free()'s so
> that any not-yet-released memory can be reclaimed before beginning
> the alternate system, but I think that is straightforward and not in
> need of any further explanation.

I am not convinced it's neater to use longjmp here. I prefer to write
code where allocation failures just propagate up the call stack. That
would give me a top-level failure return from the try_fast_compile()
function call.

> I admit this example isn't very compelling given that even small
> computers today have multiple gigabytes of RAM. But I think it
> isn't hard to imagine an analogous problem in a more limited
> environment, for example running in a VM on a co-located server.
> (I have run out of "RAM" when running a program on my colo server
> here. It was quite confusing when it first happened.)

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>
>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>>
>>>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>>>
>>>>>> [..how should errors be handled..]
>>>>>>
>>>>>>> How would you prefer these sorts of thing to be signalled?
>>>>>>
>>>>>> Let me give just one example.
>>>>>>
>>>>>> I wrote some code not long ago to add a value to a set of values,
>>>>>> where the set is represented using a recursive binary tree structure
>>>>>> (like red-black trees, but a little different). Usually we may
>>>>>> expect that a request to add a value would offer a value not already
>>>>>> included in the set, but certainly it can happen that there is a
>>>>>> call to add a value that is already included, in which case the top
>>>>>> level return value should be the original tree structure.
>>>>>>
>>>>>> I thought it would be easier to write a simple recursive routine
>>>>>> that assumes the to-be-added value is not yet included in the set,
>>>>>> and if that assumption is violated raise an exception that is caught
>>>>>> at the outermost level and simply returns the original argument tree
>>>>>> value. Certainly the code could have been written to handle the
>>>>>> already-present situation at each level of the recursion, but it was
>>>>>> much easier and much cleaner to handle it by raising an exception.
>>>>>
>>>>> This is one of those cases where I just have to take your word for it,
>>>>> (and I am happy to do that).
>>>>
>>>> Responding here to just this one part.
>>>>
>>>> Here is a simpler version of the code, for an ordinary
>>>> binary tree, and without any rebalancing:
>>>>
>>>> module TreeSet = struct
>>>> type 'a treeset = Empty | Node of 'a treeset * 'a * 'a treeset
>>>> exception Present
>>>>
>>>> let add tree element =
>>>> let rec add t e =
>>>> match t with
>>>> | Empty -> Node( Empty, e, Empty )
>>>> | Node( a, v, b ) ->
>>>> if e < v then Node( add a e, v, b ) else
>>>> if e > v then Node( a, v, add b e ) else
>>>> raise Present
>>>> in
>>>> try add tree element with Present -> tree
>>>>
>>>> end
>>>
>>> I'm not getting it. I'd write 'else t' rather than 'else raise
>>> Present' and I could then do away with the wrapping 'add' function.
>>
>> Doing that would result in returning a valid tree, but it would also
>> needlessly replicate all nodes starting from the point where the
>> match was found and going up to the root. The consequence is more
>> cycles used and more demand on the memory allocator.
>
> How can OCaml avoid making the allocations until it knows the exception
> won't be raised? Are they not all still being done?

No, no allocations are done if the to-be-added element is found
(and so an exception is raised). Consider one of the lines where a
Node is being constructed (which is synonymous with an allocation
occurring):

if e < v then Node( add a e, v, b ) else

The call to the Node() constructor doesn't take place until the
recursive call to 'add' returns. But if an equal value is found,
then an exception is raised, and the call to 'add' does not /ever/
return. No return from 'add' means no Node() is constructed.

To say this another way, looking for a point where an insertion
should take place, or where there is an equal value, happens going
/down/ the call chain. Node() allocations, however, happen only
when we are coming back /up/ the call chain. Raising an exception
"short circuits" all of those pending returns: they never happen,
and so no Node()s are constructed.

>> The technique
>> of raising an exception avoids those shortcomings (and also it
>> preserves tree identity, which can be important in some situations).
>
> I agree about the identity. I am not used to relying on the identity in
> situations like this (probably because of Haskell!) but I might find
> some time to work out how to preserve identity without an exception. I
> fear it will be messier that your simple solution.

SPOILER ALERT - at the end of this posting I am including code
for a version of add (called add') that does not use exceptions
and preserves identity when the "new" element is already present.

>>> I worry we are getting away from C, but the point is likely to be
>>> much simpler to make in OCaml (or Caml).
>>
>> I have another example. The example doesn't include any C code, but
>> I will talk about some concerns that pertain to C.
>>
>> Suppose we are writing a compiler for a large programming language.
>> The compiler should make use of available resources, especially
>> memory resources, when it can, but also should be able to compile
>> large programs even when the amount of memory available is much more
>> limited. How much memory is available is not known in advance; we
>> find out when a call to malloc() or realloc() returns NULL. I note
>> in passing that the PL/I(F) compiler from IBM could translate full
>> PL/I even if limited to only 44 K bytes of user memory; to do that
>> it needed 110 physical passes over source text or structures created
>> and stored in disk files.
>>
>> The idea in essence is to have two compilers in one: one taking a
>> conventional approach using regular dynamic memory allocation (in
>> other words malloc() etc), and the other using an IBM-style multiple
>> passes scheme that stores intermediate data in disk files. To
>> compile a program we start the first compiler under an umbrella of
>> setjmp(), which going forward assumes all memory allocations will
>> succeed. To allocate memory we call wrapper functions for malloc()
>> or realloc(), which will do a longjmp() if an allocation fails.
>> Upon receipt of the longjmp() "exception" the outer setjmp() call
>> starts over using the second approach, which is of course much
>> slower but also much less demanding of main memory.
>>
>> To make this work we might have to track malloc()'s and free()'s so
>> that any not-yet-released memory can be reclaimed before beginning
>> the alternate system, but I think that is straightforward and not in
>> need of any further explanation.
>
> I am not convinced it's neater to use longjmp here. I prefer to write
> code where allocation failures just propagate up the call stack. That
> would give me a top-level failure return from the try_fast_compile()
> function call.

There was a time when I would normally handle unusual conditions
locally, and pooh-poohed using exceptions (and setjmp()/longjmp()).
Working in OCaml has caused me (I speculate) to revise my thoughts
on the question.

SPOILER ALERT - continue scrolling only when ready to see the code
for an exception-free version of the add function...

Here it is...

let add' tree element =
let rec add t e =
match t with
| Empty -> Some (Node( Empty, e, Empty ))
| Node( a, v, b ) ->
if e < v then (
match add a e with
| None -> None
| Some a' -> Some( Node( a', v, b ) )
) else if e > v then (
match add b e with
| None -> None
| Some b' -> Some( Node( a, v, b' ) )
) else None
in
match add tree element with
| Some t -> t
| None -> tree

The original version is 10 lines, the revised version 18 lines.

That ratio is higher than what I would expect for an analogous
change to the full version (which is much longer than the simple
non-rebalancing version, because it has more cases to deal with,
and needs to keep the tree balanced), but not a lot higher - maybe
only 40 or 50% longer instead of 80% longer.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>>
>>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>>>
>>>>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>>>>
>>>>>>> [..how should errors be handled..]
>>>>>>>
>>>>>>>> How would you prefer these sorts of thing to be signalled?
>>>>>>>
>>>>>>> Let me give just one example.
>>>>>>>
>>>>>>> I wrote some code not long ago to add a value to a set of values,
>>>>>>> where the set is represented using a recursive binary tree structure
>>>>>>> (like red-black trees, but a little different). Usually we may
>>>>>>> expect that a request to add a value would offer a value not already
>>>>>>> included in the set, but certainly it can happen that there is a
>>>>>>> call to add a value that is already included, in which case the top
>>>>>>> level return value should be the original tree structure.
>>>>>>>
>>>>>>> I thought it would be easier to write a simple recursive routine
>>>>>>> that assumes the to-be-added value is not yet included in the set,
>>>>>>> and if that assumption is violated raise an exception that is caught
>>>>>>> at the outermost level and simply returns the original argument tree
>>>>>>> value. Certainly the code could have been written to handle the
>>>>>>> already-present situation at each level of the recursion, but it was
>>>>>>> much easier and much cleaner to handle it by raising an exception.
>>>>>>
>>>>>> This is one of those cases where I just have to take your word for it,
>>>>>> (and I am happy to do that).
>>>>>
>>>>> Responding here to just this one part.
>>>>>
>>>>> Here is a simpler version of the code, for an ordinary
>>>>> binary tree, and without any rebalancing:
>>>>>
>>>>> module TreeSet = struct
>>>>> type 'a treeset = Empty | Node of 'a treeset * 'a * 'a treeset
>>>>> exception Present
>>>>>
>>>>> let add tree element =
>>>>> let rec add t e =
>>>>> match t with
>>>>> | Empty -> Node( Empty, e, Empty )
>>>>> | Node( a, v, b ) ->
>>>>> if e < v then Node( add a e, v, b ) else
>>>>> if e > v then Node( a, v, add b e ) else
>>>>> raise Present
>>>>> in
>>>>> try add tree element with Present -> tree
>>>>>
>>>>> end
>>>>
>>>> I'm not getting it. I'd write 'else t' rather than 'else raise
>>>> Present' and I could then do away with the wrapping 'add' function.
>>>
>>> Doing that would result in returning a valid tree, but it would also
>>> needlessly replicate all nodes starting from the point where the
>>> match was found and going up to the root. The consequence is more
>>> cycles used and more demand on the memory allocator.
>>
>> How can OCaml avoid making the allocations until it knows the exception
>> won't be raised? Are they not all still being done?
>
> No, no allocations are done if the to-be-added element is found
> (and so an exception is raised). Consider one of the lines where a
> Node is being constructed (which is synonymous with an allocation
> occurring):
>
> if e < v then Node( add a e, v, b ) else
>
> The call to the Node() constructor doesn't take place until the
> recursive call to 'add' returns. But if an equal value is found,
> then an exception is raised, and the call to 'add' does not /ever/
> return. No return from 'add' means no Node() is constructed.

Ah, yes. I was thinking in a lazy language (Haskell) whilst looking at
code in a strict one.

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>
>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
[...]
>>>>>> [..example to illustrate using exceptions..]
>>>>>>
>>>>>> module TreeSet = struct
>>>>>> type 'a treeset = Empty | Node of 'a treeset * 'a * 'a treeset
>>>>>> exception Present
>>>>>>
>>>>>> let add tree element =
>>>>>> let rec add t e =
>>>>>> match t with
>>>>>> | Empty -> Node( Empty, e, Empty )
>>>>>> | Node( a, v, b ) ->
>>>>>> if e < v then Node( add a e, v, b ) else
>>>>>> if e > v then Node( a, v, add b e ) else
>>>>>> raise Present
>>>>>> in
>>>>>> try add tree element with Present -> tree
>>>>>>
>>>>>> end
>>>>>
>>>>> I'm not getting it. I'd write 'else t' rather than 'else raise
>>>>> Present' and I could then do away with the wrapping 'add' function.
>>>>
>>>> Doing that would result in returning a valid tree, but it would also
>>>> needlessly replicate all nodes starting from the point where the
>>>> match was found and going up to the root. The consequence is more
>>>> cycles used and more demand on the memory allocator.
>>>
>>> How can OCaml avoid making the allocations until it knows the exception
>>> won't be raised? Are they not all still being done?
>>
>> No, no allocations are done if the to-be-added element is found
>> (and so an exception is raised). Consider one of the lines where a
>> Node is being constructed (which is synonymous with an allocation
>> occurring):
>>
>> if e < v then Node( add a e, v, b ) else
>>
>> The call to the Node() constructor doesn't take place until the
>> recursive call to 'add' returns. But if an equal value is found,
>> then an exception is raised, and the call to 'add' does not /ever/
>> return. No return from 'add' means no Node() is constructed.
>
> Ah, yes. I was thinking in a lazy language (Haskell) while looking at
> code in a strict one.

Right. I was wondering if that might be the source of the
confusion. Now that the question has come up, I don't know what
it means to raise an exception in a language like Haskell where
lazy evaluation is always in force. Does Haskell have exceptions?

C is like OCaml in this respect in that lazy eval is possible but
it needs to be explicit rather than just happening everywhere
automatically.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>>>
>>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> [...]
>>>>>>> [..example to illustrate using exceptions..]
>>>>>>>
>>>>>>> module TreeSet = struct
>>>>>>> type 'a treeset = Empty | Node of 'a treeset * 'a * 'a treeset
>>>>>>> exception Present
>>>>>>>
>>>>>>> let add tree element =
>>>>>>> let rec add t e =
>>>>>>> match t with
>>>>>>> | Empty -> Node( Empty, e, Empty )
>>>>>>> | Node( a, v, b ) ->
>>>>>>> if e < v then Node( add a e, v, b ) else
>>>>>>> if e > v then Node( a, v, add b e ) else
>>>>>>> raise Present
>>>>>>> in
>>>>>>> try add tree element with Present -> tree
>>>>>>>
>>>>>>> end
>>>>>>
>>>>>> I'm not getting it. I'd write 'else t' rather than 'else raise
>>>>>> Present' and I could then do away with the wrapping 'add' function.
>>>>>
>>>>> Doing that would result in returning a valid tree, but it would also
>>>>> needlessly replicate all nodes starting from the point where the
>>>>> match was found and going up to the root. The consequence is more
>>>>> cycles used and more demand on the memory allocator.
>>>>
>>>> How can OCaml avoid making the allocations until it knows the exception
>>>> won't be raised? Are they not all still being done?
>>>
>>> No, no allocations are done if the to-be-added element is found
>>> (and so an exception is raised). Consider one of the lines where a
>>> Node is being constructed (which is synonymous with an allocation
>>> occurring):
>>>
>>> if e < v then Node( add a e, v, b ) else
>>>
>>> The call to the Node() constructor doesn't take place until the
>>> recursive call to 'add' returns. But if an equal value is found,
>>> then an exception is raised, and the call to 'add' does not /ever/
>>> return. No return from 'add' means no Node() is constructed.
>>
>> Ah, yes. I was thinking in a lazy language (Haskell) while looking at
>> code in a strict one.
>
> Right. I was wondering if that might be the source of the
> confusion. Now that the question has come up, I don't know what
> it means to raise an exception in a language like Haskell where
> lazy evaluation is always in force. Does Haskell have exceptions?

Yes it does, but I have not really wrapped my head around them. They
throw you into the IO monad.

> C is like OCaml in this respect in that lazy eval is possible but
> it needs to be explicit rather than just happening everywhere
> automatically.

I knew OCaml was strict, I just had the wrong head on because the type
system and matching are so similar.

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

[..setjmp()/longjmp() in other languages..]

>>> Ah, yes. I was thinking in a lazy language (Haskell) while
>>> looking at code in a strict one.
>>
>> Right. I was wondering if that might be the source of the
>> confusion. Now that the question has come up, I don't know what
>> it means to raise an exception in a language like Haskell where
>> lazy evaluation is always in force. Does Haskell have exceptions?
>
> Yes it does, but I have not really wrapped my head around them.
> They throw you into the IO monad.

I see. :) Thank you for the info.

It might be interesting to speculate what C would be like
if it were lazy rather than eager. Maybe a lazy C could
have the property that undefined behavior wouldn't happen
unless it became essential to producing an output. Hmmm..