OpenEuphoria

2. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 13, 2014
• 1988 views

While I agree with "you should require the caller validates the parameters of a called function", I don't think this is a good example.

No, it does not modify it's parameters.

	lo = max(sp, 1)              -- lo could be > N 
	hi = min(N, ep)              -- hi could be < lo 
	hi = (lo > hi && N) ? N : hi -- hi could be > N  

Agreed, a sanity bounds check here would not hurt - but if sp or ep is out of bounds, it's an error. (Ideally, it'd be an exception or a flag, not an uncatchable run-time error.)

	mid = sp                     -- this is unwise 

That is harmless, as in the case where lo <= hi, mid is immediately reset without the old value being used. So this is for the case where lo > hi, in which case the function returns immediately, stating that the record would be inserted into the first position. (Actually, maybe this only makes sense when dealing with the empty sequence?)

	c = 0                        -- the match (set to 0 - found) 

Again, harmless. In the case where lo <= hi, c is immediately reset without the old value being used as well. Where lo > hi, c=0 is still harmless, it just means we don't adjust the offset returned by 1 (as we would do in the case where lo<=hi but the item was not found and the last object in the haystack search range < needle).

--  at this point consider 
--     if lo > hi   we have mid = sp, c = 0, a return of -sp (sp may be -ve) 

What the heck is ve? Anyways, this case is designed for the empty sequence. I concede that if sp and ep are both longer than the length of the sequence, the return value here may be weird, causing logic errors or a run-time crash later on.

--     if N = 0 then  
--        if lo <= hi     we have a crash. 

If both sp and ep are out of bounds. Conceded. Maybe this is the right thing to do, though, since we normally crash on out of bounds errors and it's better to fail early.

--     if N != 0 then 
--           if lo > N     we have a crash. 
--           if lo <= N then 
--              if hi > N  we have a potential crash. 

So if either sp or ep are out of bounds, we could have a crash. I don't like the 'potential crash' here, I think if it's out of bounds, we should detect it early and report back on it somehow.

So, that's definitely a bug. Conceded.

--     if N = 0 then  
--        if lo > hi      we have mid = sp, c = 0, a return of -sp (sp may be -ve) 

Didn't you already say this?

No, you've definitely found something here. 'almost always' is not good enough in this case.

"A was null" means "A = {}" ? Assuming that this is what you mean,

Yeah, I need to think about this one some more.

Yes, that definitely needs to be checked. But what to do if there's an out-of-bounds error?

Just one - lack of proper bounds checking.

4. Re: binary search with reference to append

• Posted by jaygade Jun 13, 2014
• 1967 views

Untested:

-- Precondition: haystack is a list sorted in ascending order. 
--               If provided, startp and endp are less than or equal to 
--               haystack length and startp is less than or equal to endp. 
-- Returns: Index of needle in haystack, or 0 if not found. 
 
function bsearch(object needle, 
                 sequence haystack, 
                 integer startp=1, 
                 integer endp=0) 
 
    integer nItems, lo, hi, midp 
    --------------------- 
    nItems = length(haystack) 
    lo = max({1, startp}) 
 
    if endp > 0 and endp <= nItems then 
        hi = min({endp, nItems}) 
    else 
        hi = nItems 
    end if 
 
    -- We should provide a useful error message here, but crash is good 
    -- enough. 
    if hi > nItems or lo > hi then abort(1) end if 
 
    --------------------- 
 
    while lo <= hi do 
        midp = floor((lo + hi) / 2) 
        switch eu:compare(needle, haystack[midp]) do 
          case -1 then hi = midp - 1 
          case 0 then return midp 
          case +1 then lo = midp + 1 
        end case 
    end while 
 
    -- Not found. 
    return 0 
 
end function 

6. Re: binary search with reference to append

• Posted by jaygade Jun 13, 2014
• 1959 views

I've edited my code several times but I think it's still not perfect.

This is better. Still untested.

-- Precondition: haystack is a list sorted in ascending order. 
--               If provided, startp and endp are less than or equal to 
--               haystack length and startp is less than or equal to endp. 
-- Returns: Index of needle in haystack, or 0 if not found. 
 
function bsearch(object needle, 
                 sequence haystack, 
                 integer startp=1, 
                 integer endp=0) 
 
    integer nItems, lo, hi, midp 
 
    nItems = length(haystack) 
 
    if endp = 0 then 
        hi = nItems 
    else 
        hi = endp 
    end if 
 
    if hi <= nItems and startp <= hi then 
        lo = startp 
    else 
        abort(1) 
    end if 
 
    while lo <= hi do 
        midp = floor((lo + hi) / 2) 
        switch eu:compare(needle, haystack[midp]) do 
          case -1 then hi = midp - 1 
          case 0 then return midp 
          case +1 then lo = midp + 1 
        end case 
    end while 
 
    -- Not found 
    return 0 
 
end function 

If startp > endp, but both are less than nItems, I think that either failure OR returning 0 is a valid response so long as it's documented. Failure could be better during debugging in order to catch invalid inputs when reasonable.

In this case it is reasonable to check the boundaries of the search, but it is not necessarily reasonable to check to see if the haystack is sorted.

This illustrates that the caller should validate the data before sending it to the bsearch function, and that the bsearch function should reject invalid inputs.

8. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 13, 2014
• 1943 views

For the usage case that you've written this for, it looks good.

However, binary_search() has an extra requirement:

-- # a negative integer, ##-i##, with ##i## between adjusted start and end 
--    points. This means that ##needle## is not in the searched slice of 
--    ##haystack##, but would be at index ##i## if it were there. 
-- # a negative integer ##-i## with ##i## out of the searched range. This 
--   means than ##needle##might be either below the start point if ##i## 
--   is below the start point, or above the end point if ##i## is. 

So it might return, say, -5, if the needle is not in the haystack but index 5 is where the needle should be sorted into.

I guess, sometimes you just can't have it all.

10. Re: binary search with reference to append

• Posted by petelomax Jun 13, 2014
• 1912 views

I'd never seen this before. Can someone please enlighten me. In std/search.e I find:

public function binary_search(object needle, sequence haystack, integer start_point = 1, integer end_point = 0) 

In std/primes.e I find:

public function next_prime(integer n, object fail_signal_p = -1, atom time_out_p = 1) 
    ... 
    -- Assumes that most searches will be less than about 1000 
    if n<1009 and 1009<=list_of_primes[$] then 
        i = binary_search(n, list_of_primes, 1 ,169) 
    else 
        i = binary_search(n, list_of_primes) 
    end if 

Is that like a major win in some benchmark or something? Even if list_of_primes almost fills available memory, we're talking like 32 or 64 chops max, so my gut feeling is those "1009" tests are an overhead many more times than a saving, though I could well be wrong. Otherwise I cannot see why there is an end_point, and given that the above is all I could find, I see absolutely no reason whatsoever to have a start point.

Pete

12. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 14, 2014
• 1869 views

I attempted to trace the history of primes.e back, to find the culprit who changed this from the sequential search to a ranged search.

But, this is the earliest version I can find: http://scm.openeuphoria.org/hg/euphoria/file/d0ab9cc672b8/include/primes.e

14. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 14, 2014
• 1847 views

No, I haven't.

Agreed.

This is complicated by the requirement to return a "potential" position for the new item. I'll call this the jaygade point, in honor of the recent work jaygade has done in this area.

Agreed. Thinking it over, for the empty sequence case, the result should laways be -1, as any item inserted into an empty sequence will be inserted into the first position. The way the default parameters are set up, this is what actually happens, but it could be made more explicit I suppose.

Now, if the user specifies an empty sequence and an invalid range (e.g. 5..9) then it gets weirder. I'm still not sure what to do here.

Non sequitor?

GIGO?

Sounds like GIGO.

See the jaygade point above.

You might have a point here. I have to think about this some more.

Perhaps in this case, a NOTFOUND/INVALID/NOTARESULT/NOTAPOSITION return value would make sense. Like

public constant NOTAPOSITION = ""

I see where the idea to return -sp came from though. If we return -1 for an empty sequence searching over the entire range, then conceptually {}[5..4] is still an empty sequence, and returning -sp (or -5 in this example) just signifies that if you filled the sequence up to the starting point of the range, then you'd want to insert this item at position 5.

Again you have a good point here. If only for one minor hiccup, I'd completely agree with you here.

I hate how euphoria's error handling works. No way to catch exceptions. It's embarrassing. Hence, I like to promote the idea that the stdlib return a INVALID_RESULT in place of crashing.

In lieu of being able to throw a catchable ArrayOutOfBoundsException here, I think I've settled on favoring returning NOTFOUND/NOTAPOSITION/INVALIDPARAMETERS or something in this case.

lo/hi are not parameters. sp and ep are parameters. Thus your basic premises are wrong.

I also concur.

I find it odd that you say this but then have the callee check bounds in your later examples in the same post.

   A[lo] < x < A[hi]         -- lo < hi 
   m = mid(lo,hi) 
-- We have one of 
   A[m] = x 
   A[lo] < x < A[m] 
   A[m] < x < A[hi] 

That's only true if it's sorted in a particular direction. Here's a counterexample:

   -- lo = 1 
   -- hi = 3 
   -- x = 2 
   -- A = {3, 1.5, 1} 
   A[lo] < x < A[hi]         -- lo < hi 
   -- but this is not true! 
   -- A[lo] = A[1] = 3 
   -- A[hi] = A[3] = 1 
   -- 3 < 2 -- false! 
   -- 2 < 1 -- false! 
   m = mid(lo,hi) 
   -- m now equals 2 
-- We have one of 
   A[m] = x -- false, A[m] = A[2] = 1.5 != 2 
   A[lo] < x < A[m] -- also false 
   A[m] < x < A[hi] -- also false 

But it already does! It's only the invalid input cases that are being argued!

I wonder if you have a legitmate point, or you are simply just trying to get functionality removed from the stdlib.

16. Re: binary search with reference to append

• Posted by jaygade Jun 14, 2014
• 1823 views

I can't argue for or against sending a slice to the function. However, sp and ep ARE optional arguments which will probably not be used most of the time.

In addition, nothing prevents you from sending a slice to the function as written. It should work just fine with a slice.

So call the function with a slice and skip using sp and ep. Problem solved.

I'm not entirely convinced on the added functionality of returning a "possible" index as a negative number though. It almost seems like the job of another function, that should return a euphoria tuple sequence such as {index, FOUND} or {index, NOT_FOUND}.

The more I read about other languages and learn about tuples, the more I can relate them to Euphoria's sequences and find the long-proposed idea of the {A, B} = {val1, val2} syntax.

[EDIT] Nice with the edit history.

18. Re: binary search with reference to append

• Posted by gimlet Jun 14, 2014
• 1837 views

I wasn't addressing that to you, more to Jaygade.
However you have not demonstrated that you understand.

I said: if you haven't searched.

1 It is not possible to search an empty sequence.
2 Therefore you can't return a position except one arbitrarily decided.
3 Therefore you should return NOT FOUND/NO POSITION.

-1 is as arbitrary as any other value. Consider what the logic may have done. What relation there might be between lo and sp. -1 doesn't work any better than -sp.

Exactly. Just accept that if you don't know, a library function can't know. Arbitrary decisions are in general wrong. So accept empty sequence or sp > ep => NOT FOUND/NO POSITION

A point which you seem to have missed. If an empty sequence is passed to bsearch: besearch does not know anything about the sequence, whether it is the whole thing or a slice. If sp and ep have values bsearch cannot know anything about those values except in relation to the (empty) sequence and each other.

You are allowing impossible requirements to tie you in knots.

No. Design by contract

Design by contract

That is last part is silly. You can't seriously mean that.
You are saying bsearch is a mind reader.

In the examples at the end I am returning 0 to stand for NOTFOUND/NOPOSITION. This functions perfectly well.

Have your way if you like. My premises stand.

The boundary checking is to ensure that a valid position is returned. A position value outside of the searched range is not acceptable as it implies the value was not in the range A[sp] <= x <=A[ep]. It only happens in the case of a failed search.

   A[lo] < x < A[hi]         -- lo < hi 
   m = mid(lo,hi) 
-- We have one of 
   A[m] = x 
   A[lo] < x < A[m] 
   A[m] < x < A[hi] 

   -- lo = 1 
   -- hi = 3 
   -- x = 2 
   -- A = {3, 1.5, 1} 
   A[lo] < x < A[hi]         -- lo < hi 
   -- but this is not true! 
   -- A[lo] = A[1] = 3 
   -- A[hi] = A[3] = 1 
   -- 3 < 2 -- false! 
   -- 2 < 1 -- false! 
   m = mid(lo,hi) 
   -- m now equals 2 
-- We have one of 
   A[m] = x -- false, A[m] = A[2] = 1.5 != 2 
   A[lo] < x < A[m] -- also false 
   A[m] < x < A[hi] -- also false 

Not a counter example:

You invalidate the start condition A[lo] < x < A[hi]
and then claim that because binary search fails with an
invalid start condition that it would fail with valid
start conditions!

Well: passing a slice rather than a sequence and start and end points is cleaner, lays the responsibility for bounds checking on the caller and, loses no functionality.

One still has to deal with passing in an empty sequence.
(I don't think this is an error).

and returning a valid position value in the case x is not found.

Those issues are determinate within bsearch.

Sounds like a win to me.

Regardless of of the details, I think that what I have shown is:

1 the logic was incorrect.

2 the handling of empty sequences, sp and ep was incorrect.

3 that you, jaygade and many others have trouble with the way bsearch in its original form works.

This is not surprising as bsearch was written with assumptions about all kinds of things built in which need to untangled.

If the end result is that the library function is changed so it doesn't make assumptions I will be very happy. Just as I will be very happy when load_map() is fixed.

20. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 15, 2014
• 1992 views

What makes you think that it is (still) broken? Do you have examples to demonstrate this?

I disagree. An empty sequence is the fastest to search. Just like searching an empty box.

Agreed. There's no existing position to return.

Negative numbers are not valid positions. The existing function already conveys this information, one just has to check if the result is <= 0.

But, as per the jaygade point above, it also attempts to return extra information.

It would seem to work best when sp = 1. Anyways, conceded.

Undecided != Don't know.

Irrelevant. bsearch should not care about this.

Agreed ... but what of it?

[quote gimlet] No. Design by contract

No. Under design by contract, the called function should be checking those conditions using an assertion an throwing an error or something if they aren't validated.

Quoting wikipedia:

Specifically, this

violates design by contract.

Yes, I do.

It's following certain rules to produce a result which logically follow from those rules.

Agreed. Other than the jaygade point (and the drop in slicing functionality), this works perfectly.

Fine. Here are the premises:

1. Messing with parameters causes the culprit function to fail in MWP-style. 2. bsearch messes with lo/hi. 3. lo/hi are not parameters. 4. sp/ep are parameters.

How do you reach the conclusion:

1. bsearch fails in MWP-style?

Yes, this makes sense and is reasonable. However, you have not resolved the contradiction or stated that this case is one (of many?) possible exceptions to your rule:

   A[lo] < x < A[hi]         -- lo < hi 
   m = mid(lo,hi) 
-- We have one of 
   A[m] = x 
   A[lo] < x < A[m] 
   A[m] < x < A[hi] 

   -- lo = 1 
   -- hi = 3 
   -- x = 2 
   -- A = {3, 1.5, 1} 
   A[lo] < x < A[hi]         -- lo < hi 
   -- but this is not true! 
   -- A[lo] = A[1] = 3 
   -- A[hi] = A[3] = 1 
   -- 3 < 2 -- false! 
   -- 2 < 1 -- false! 
   m = mid(lo,hi) 
   -- m now equals 2 
-- We have one of 
   A[m] = x -- false, A[m] = A[2] = 1.5 != 2 
   A[lo] < x < A[m] -- also false 
   A[m] < x < A[hi] -- also false 

Yes it is. It is a counter-example to what you said:

Yes, I did that. Because that start condition is a veiled form of saying that the array must be sorted. (I guess it's possible to have a sequence that's not completely sorted, which for the right x would still work correctly, as long as all other values touched coincidently happen to have the right order. But sorting is generally the only way to guarantee this for any arbiturary sequence/array/list/etc.)

I never said this, I just said that binary search fails with invalid start conditions (one of which is the array being sorted). Now, I never said that binary search would fail with valid start conditions.

Agreed, so far.

I disagree. bsearch is losing the functionality to do slicing on behalf of the caller, and potentially the chance to do bounds checking and the life on behalf of the caller.

You may argue that bsearch should not be responsible for this sort of functionality ... and you may be right. We already have other stdlib functions that could do this anyways.

Anyways, I figured that there was probably a good reason for bsearch to work this way, but as original author of the code seems to have changed this mind about it, I'll defer to him: http://openeuphoria.org/forum/m/124611.wc

(Actually, I'm now wondering if the main reason for binary_search() to have slice() functionality was for next_prime() - http://scm.openeuphoria.org/hg/euphoria/file/d0ab9cc672b8/include/primes.e )

You have not demonstrated this, except in cases where sp/ep are invalid.

Again, only in cases where sp/ep are invalid.

Agreed. No one seems to like how the function handles the cases where sp/ep are invalid. In addition, there's some wavering on the support for the jaygade point as well.

Actually, I think most of the disagreement stands on the jaygade point. This is a design/functionality issue rather than a logical point.

Now, I trust that there was a good reason to have it in the first place, but I'll let the original author explain: http://scm.openeuphoria.org/hg/euphoria/rev/2036d2a1151f

This is just a veiled way of stating that I do not understand.

I contend that I have demonstrated that I understand.

In fact, I could go further, and claim that, by your missteps (not understanding binary search and sorting arrays, advocating and then contradicting design by contract) that you understand less.

But this is all besides the point. You are saying that binary_search() is fine, except we should drop the slicing functionality and the jaygade point, as you think that seem to overcomplicate things.

I don't have a strong opinion either way, so I'm more than happy to let the original author make the call.

22. Re: binary search with reference to append

• Posted by gimlet Jun 15, 2014
• 1784 views

Derek,

This is the last I will say on this as it is getting personal.

What I objected to in the first place was the logical prelude in binary_search which:

1 was erroneous.

2 was making inferences about the call which went beyond what was reasonable.

It seems to me that the prelude code is defensive programming with a vengeance. It seems to be trying to make sense of start_points and end_points which are invalid, returning positions which do not make good sense and so on.

Your code is not correct, sorry.

I think what Jaygade wrote or the first of mine (with sp and ep) are both simpler and better.

sp = start_point  
    if end_point <= 0 then  
        -- End point specified is relative to the end of the sequence.  
        ep = length(haystack) + end_point  
    else  
        ep = end_point             -- ep=3 => length?? (G) 
    end if  
      
    if ep > length(haystack) then  -- this cannot happen (G) 
        ep = length(haystack)  
    end if  
    if sp < 1 then  
        sp = 1  
    end if  
    if sp > ep then  
        if sp = ep + 1 then        -- if ep = length??   (G) 
            return -sp  -- Obviously the needle is never in an empty sequence/slice.  
                        -- if sp > ep then why assume the slice starts at sp? 
                        -- with ep = length -sp is out of range. (G) 
        end if  
        return 0  -- Slice starts after the end.  
    end if  

Look it's hard to write this kind of code because you are forever faced with questions:

What do I do in this particular situation?,
Have I covered every possible case?,
What is the meaning of all this?
Should I even try to cover this?

24. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 15, 2014
• 1765 views

Wow! Your skills are older than BSD UNIX!

• jaw and pants drop to the floor*

26. Re: binary search with reference to append

• Posted by petelomax Jun 15, 2014
• 1761 views

It seems perfectly reasonable to me, if everyone else agrees, to remove them. Of course that would be with a suitable entry in the release notes and both the manual and bsearch.e containing something like

-- Compatibility Note: 
--  Prior to 4.2 bsearch() allowed the start and end points to be specified. This was agreed to be removed (http://openeuphoria.org/forum/124592.wc),  
--   if necessary replace eg res = bsearch(needle,haystack,5,10) with res = bsearch(needle,haystack[5..10]), remembering to add 4 to abs(res). 

Obviously, that is, if appropriate code changes to manage without them do not adversely affect the performance of next_prime().

Pete

28. Re: binary search with reference to append

• Posted by jaygade Jun 15, 2014
• 1770 views

I'm okay with breaking user APIs; we're talking about Euphoria not Unix. Programming languages do this all the time with major releases.

The key would be to deprecate the parameters for at least one point release, then ignore them going forward. If that's what you wanted to do.

However, the function works as-is, the documentation can state that the parameters are deprecated and to pass a slice instead, and defer the code change indefinitely.

30. Re: binary search with reference to append

• Posted by andi49 Jun 15, 2014
• 1695 views

Isn't there a 'deprecated' keyword in eu4.1 for this kind of situation?

deprecate public procedure say_hello(sequence name) 
    printf(1, "Hello, %s\n", { name }) 
end procedure 

Isn't this a good reason to release 4.1 as fast as possible?

Andreas

32. Re: binary search with reference to append

• Posted by andi49 Jun 16, 2014
• 1661 views

It's a kind of funny. My Version of Eu4.1 has support for the 'deprecated' keyword and it works. It's also in the Doc's for 4.1.

Section: 4.2.4 Deprecation

http://euphoria.indonesianet.de/eu4zip/doc41/html/lang_decl.html#_140_deprecation

Andreas

34. Re: binary search with reference to append

• Posted by jaygade Jun 16, 2014
• 1660 views

I don't think that the deprecate keyword would work in this case however, since we're deprecating optional parameters and not an entire routine.

Unless deprecate works in the formal parameter declaration?

I would think that editing the doc comment of the function to mention that the sp and ep parameters are deprecated would be sufficient. "Don't use these, use a slice instead. These optional parameters will no longer be valid at some future point."

36. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 22, 2014
• 1801 views

I made a few quick fixes to deal with all the warts I knew of. You're right that libraries shouldn't ship with broken functions.

I think Derek has a better handle on the internals of the library and he is working on a proper rewrite. I trust him to resolve any potential issues the cosmetic fixes I appled would not (e.g. any performance issues, for example). In the meantime, I applied those quick fixes to prevent the issues you reported from holding up the release.

Do you have any examples where load_map() still breaks? This is the third time I have asked you for this.

38. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 22, 2014
• 1661 views

Like I said, I fixed the issues in functionality. Most of what you wrote is a critique of the algorithms used in the code. These I left to Derek to address.

I didn't ignore anything. I just took the easy part and left the hard stuff to Derek.

I have and it works fine for what I need.

This sounds more like a personal problem than anything to do with us. Still, whatever floats your boat.

I applied a fix to load_map(), and then you say I don't want to fix things?

I agree with Derek here - constructive criticism is good. It improves the language and the standard library.

However, I confess that I do want to defend against unconstructive and unproductive criticism.

I won't ask again. Since you can't point to a single example where load_map(), given valid input, fails to produce valid output, I maintain my confidence that load_map() is not functionally broken.

Anyways, this load_map() argument is becoming quite repetitive. Unless you (or anyone else) has any new evidence, I think we should just agree to disagree and drop the subject.

I welcome constructive criticism. Generally, I only want to drive trolls away.

40. Re: binary search with reference to append

• Posted by jimcbrown (admin) Jun 22, 2014
• 1660 views

Agreed. Where did that come from?

But it does! http://algorithms.openmymind.net/search/binarysearch.html http://en.wikipedia.org/wiki/Binary_search_algorithm

Yes, it is.

Sort of. Everyone seems to agree with it theoretically, but due solely to backwards compatibility concerns, this change won't happen.

If I ban everyone who's ever disagreed with me? Agreed. I'd have to ban Derek and Matt and Shawn and euphoric and Jeremy and ... dang, probably the entire community. Almost everyone who has ever posted on the forum!

Of course, I have no desire to ban people who merely disagree with me on an academic subject. That would just be plain silly. So, what's your point?

When did I say this? I did suggest extended moderation may be in the offing, but that's not the same thing as a ban.

This has nothing to do with it.

42. version policy of EUPHORIA

• Posted by SDPringle Jun 24, 2014
• 1441 views

This is exactly the way we have been doing things. When it comes to deciding what the required version of a library you are using, you cannot count on others to behave so well. Another dev group can decide to change the meaning of alpha channel from 1 means full transparency to 1 means full opacity in a patch version. This kind of thing happened in a game library I tried. I believe we should look to this example, as a guide of what not to do.

Patch level changes mean you may have to put namespaces on symbols that conflict with new library routines. Minor release changes mean you may have rename a symbol because it may conflict with a builtin. Major release means you will have to overhaul the code to get it up to the newest version.

Shawn