"I have a mind like a steel... uh... thingy." Patrick Logan's weblog.

Search This Blog

Tuesday, June 06, 2006

Integers

Tim Bray wonders about Java and binary search...

If we can’t get binary search right, what chance do we have with real software?
Psst... look at the code. You *did* get binary search right.

The problem is you got integers wrong.

Real programmers use the *complete* numeric tower.

Update: Troy makes a point in the comments that there are many basic algorithms that are easy to get wrong when the foundation is weak.

Without having to think about integer overlow you are free to think more mathematically and less mechanically. Here is an unusual (to most) definition of factorial. This is iterative using the "let-loop" syntax which can be added trivially to Scheme since it has lambda and tail recursion. OK -- C# and Java have a new iteration syntax the compiler writers added for you. Can you iterate on multiple parameters? Can you invoke the next iteration even in a non-tail-recursive position?

Ha! We *still* win! But you still have more programmers.

But we still have the complete numerical tower!!! Yea!

> (define (fact n)
    (if (< n 0) (error "fact n, n >= 0")
        (if (< n 2)
            1
            (let loop ((result n) (n (- n 1)))
               (if (< n 2)
                   result
                   (loop (* result n) (- n 1)))))))
> (fact -1)
*** ERROR IN (console)@52.1 -- fact n, n >= 0
1> ,t
> (fact 0)
1
> (fact 2)
2
> (fact 6)
720
> (fact 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
> (time (fact 1000))
(time (fact 1000))
    25 ms real time
    30 ms cpu time (30 user, 0 system)
    8 collections accounting for 3 ms real time (0 user, 0 system)
    1230816 bytes allocated
    no minor faults
    no major faults
40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696940480047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950595099527612087497546249704360141827809464649629105639388743788648733711918104582578364784997701247663288983595573543251318532395846307555740911426241747434934755342864657661166779739666882029120737914385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155861103697680135730421616874760967587134831202547858932076716913244842623613141250878020800026168315102734182797770478463586817016436502415369139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535340819890138544248798495995331910172335555660213945039973628075013783761530712776192684903435262520001588853514733161170210396817592151090778801939317811419454525722386554146106289218796022383897147608850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403127462228998800519544441428201218736174599264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026517048330422614397428693306169089796848259012545832716822645806652676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946595513115655203609398818061213855860030143569452722420634463179746059468257310379008402443243846565724501440282188525247093519062092902313649327349756551395872055965422874977401141334696271542284586237738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179970235619389701786004081188972991831102117122984590164192106888438712185564612496079872290851929681937238864261483965738229112312502418664935314397013742853192664987... 
(goes on for several more lines)

Orchestration Patterns

Dragos and Boris have a new draft of their Orchestration Patterns book. There is a discussion list as well. One thing I am on the lookout for was mentioned in an ealier post today... Ralph Johnson's point about structure *and* process. Beyond the question of what is an "orchestration" vs. some other kind of programming... what is the process for adopting one when it is called for.

One thing I like about orchestration tools is support for increasingly transparent reliability across long-running, asynchronous operations. I don't see how this would ever become completely transparent, but on the one hand most programming languages offer nothing by default, while orchestration tools try to offer something by default.

Other than that the current tools I am familiar with leave much to be desired in terms of programmer comfort... at least this programmer is not fond of "programming via property boxes". Perhaps we need something like Rails, but rather more for long-running, asynchronous process steps.

Atom Over XMPP

Peter Saint-Andre has a new draft in the works for Atom Over XMPP. The previous draft is still available.

This memo describes a method for notifying interested parties about changes in syndicated information encapsulated in the Atom feed format, where such notifications are delivered via an extension to the Extensible Messaging and Presence Protocol (XMPP) for publish-subscribe functionality.

Structure and Process in Patterns

Ralph Johnson delivers more goods...

A lot of people seem to follow the errors of Design Patterns and focus on structure to the exclusion of process. A pattern description should tell the reader how to create the pattern in a system where it doesn't exist, and many pattern descriptions do not.

One of the things that helps me think about process is to imagine a system without the pattern. What would I do to use the pattern in the system? What alternatives are there to the pattern?

Sunday, June 04, 2006

WS-SUV

Stefan Tilkov exposes yet another useless analogy in the land of WS-SUV's.

Maybe some people also choose which cigarette to smoke based on the cowboy who promotes it.

Influence: The Psychology of Persuasion

Tim Bray has an item on the anniversary of the Tiananmen Square massacre.

The book Influence: The Psychology of Persuasion explains how the Chinese government used subtle and simple techniques to help the population conform following the massacre. Those same techniques, according to the book, were used by the Chinese on prisoners of war during the Korean War.

The book is a really good one. When I mentioned some aspects that lend themselves to agile development, someone on the XP mailing list responded the book is his favorite from the last ten years. High praise, but I can see why.

The information is of practical use every day in this market-driven and political society. With many less dramatic, but more commonplace, stories I can't imagine most people not recognizing situations from their own lives.

I think the book should be required reading for high school students. May as well go into life somewhat prepared for the onslaught.

Blog Archive

About Me

Portland, Oregon, United States
I'm usually writing from my favorite location on the planet, the pacific northwest of the u.s. I write for myself only and unless otherwise specified my posts here should not be taken as representing an official position of my employer. Contact me at my gee mail account, username patrickdlogan.