endoprogramming ([info]endoprogramming) wrote,
2005-08-02 23:00:00
  • Previous
  • Memorize
  • Share
  • Next

Paper: Software Libraries and the Limits of Reuse: Entropy, Kolmogorov Complexity, and Zipf's Law

Full-text: PostScript, PDF, or Other formats

(Updated Oct 2, 2005)

Abstract: We analyze software reuse from the perspective of information theory and Kolmogorov complexity, assessing our ability to ``compress'' programs by expressing them in terms of software components reused from libraries. A common theme in the software reuse literature is that if we can only get the right environment in place--- the right tools, the right generalizations, economic incentives, a ``culture of reuse'' --- then reuse of software will soar, with consequent improvements in productivity and software quality. The analysis developed in this paper paints a different picture: the extent to which software reuse can occur is an intrinsic property of a problem domain, and better tools and culture can have only marginal impact on reuse rates if the domain is inherently resistant to reuse. We define an entropy parameter $H \in [0,1]$ of problem domains that measures program diversity, and deduce from this upper bounds on code reuse and the scale of components with which we may work. For ``low entropy'' domains with $H$ near $0$, programs are highly similar to one another and the domain is amenable to the Component-Based Software Engineering (CBSE) dream of programming by composing large-scale components. For problem domains with $H$ near $1$, programs require substantial quantities of new code, with only a modest proportion of an application comprised of reused, small-scale components. Preliminary empirical results from Unix platforms support some of the predictions of our model.


  • Post a new comment

    Error

    switch
     
    Help
  • 61 comments
Previous
← Ctrl← Alt
Next
Ctrl →Alt →

Anonymous

November 13 2005, 15:12:50 UTC 6 years ago

Your argument about compiled C programs seems dubious

It is not clear that C programs are incompressable apart from the rather odd set that you supply for your counting argument. In fact, it would be difficult to find a C program outside of this set that is not compressable - as you point out instruction frequencies follow a Zipf distribution. Indeed, zip is not close to a Kolmogorov compressor and yet it normally does well on arbitrary compiled programs. Perhaps it would be more realistic to explicitly claim that there exist some compiled C programs that are uncompressable. Currently your conjecture sounds as if you are claiming that all compiled C programs are uncompressable.

[info]endoprogramming

December 19 2005, 15:31:05 UTC 6 years ago

Re: Your argument about compiled C programs seems dubious

Thanks for pointing out that this point needs better explanation in the paper.

By "Kolmogorov incompressible" in the paper I mean in the sense of Fact 3.2. Unravelling this definition a bit, it means that under a uniform distribution, if you pick a program at random, then almost surely it cannot be replaced by a program that is shorter than it by more by a fixed constant. So, it is possible to save (say) $5$ bits, but not (say) $\log \log s$ bits.

One way to establish this is to count the number of unique behaviours of programs as a function of program length. The argument about compiled C programs shows that the number of behaviours of programs of length $s$ is $\geq c \cdot 2^s$ where $c$ is some constant. Therefore, under a uniform distribution the entropy is $H(s) \geq s + \log c$, which implies there is no encoding of programs that saves more than a constant number of bits (in fact the constant must be $\leq - \log c$).

Anonymous

February 18 2007, 12:48:06 UTC 5 years ago

Buy cheap cialis

buy cheap cialis (http://buy-cialis.awardspace.us/buy-cheap-cialis.html)

buy cialis generic (http://buy-cialis.awardspace.us/buy-cialis-generic.html)

buy discount cialis (http://buy-cialis.awardspace.us/buy-discount-cialis.html)

buy cialis line (http://buy-cialis.awardspace.us/buy-cialis-line.html)

buy cialis now (http://buy-cialis.awardspace.us/buy-cialis-now.html)

[info]my69live

March 19 2007, 14:51:15 UTC 5 years ago

Greetings, add me please in friends. =)



Anonymous

April 24 2007, 19:06:30 UTC 5 years ago

tramadol on pharmacy website

Bugaga. Werta nola. Glomita fore spanio..
Hi

G'night
andora magolita. el senora guanesta. ;)

Anonymous

May 12 2007, 08:13:39 UTC 5 years ago

Am I sexy?

MESSAGE

[info]lenaykomu

October 1 2007, 16:04:43 UTC 4 years ago

Re: Am I sexy?

MESSAGE 2

Anonymous

May 16 2007, 04:21:26 UTC 5 years ago

Yes, Am I

MESSAGE

Anonymous

May 16 2007, 10:33:34 UTC 5 years ago

I will recommend you to all my friends.

a long ago for you was not
prompt who for you was engaged in a design ? I advise to call on my resource on a fight against such spam
< a href= http://gratis-porn.premium10adult.info/latina-blow-job.html >latina blow job </a> all right I went away to meeting

Anonymous

June 13 2007, 17:00:31 UTC 4 years ago

n


.Sincerely





Anonymous

June 17 2007, 06:22:28 UTC 4 years ago

l


. Much respect!





Anonymous

June 24 2007, 09:32:18 UTC 4 years ago

free verizon ringtones

Nice site! Keep up the good work!




Anonymous

July 4 2007, 03:18:28 UTC 4 years ago

Bosnia-Herzegovina


This calculator was last updated on July 3, 2007. Most individual currency factors are updated daily, although some

may be slightly older. View the currency factors, the data sources, the update dates, and smallest currency units

[url=http://www.squidoo.com/videos-free]Free Amateur Sex Videos[/url] The results are rounded to the nearest amount

that can be expressed in coins and notes. For example, US Dollars are rounded to the penny and New Zealand Dollars are

rounded

Anonymous

July 4 2007, 05:56:06 UTC 4 years ago

Subject3

Hi all!


Bye

Anonymous

July 31 2007, 09:32:34 UTC 4 years ago

#hostname - the best site

endoprogramming.livejournal.com - the most necessary site!


I like your site - endoprogramming.livejournal.com .
Thank for your help for us!
Thank you, I will add it to my bookmarks

Best Regards

Neo

[info]ttrtt

September 2 2007, 14:18:43 UTC 4 years ago

Re: #hostname - the best site

delete

Anonymous

September 7 2007, 04:19:20 UTC 4 years ago

Where are find medical funny pictory?

Hi
Where are find medical funny pictory?
Bye

Anonymous

September 13 2007, 01:14:57 UTC 4 years ago

Goodion

Hi all!

I am really excited. Keep up the great work. Good resources here.

Bye

Anonymous

September 20 2007, 04:53:57 UTC 4 years ago

Re: Goodion

This is one of the best articles that I have gone through this month.

Thanks,
http://www.ringtonefacts.info

Anonymous

September 20 2007, 04:55:54 UTC 4 years ago

Bookmark

I have to bookmark this page.

Thanks,
David

http://ringtonefacts.info

Anonymous

October 7 2007, 15:38:16 UTC 4 years ago

Продаю сертификаты Вебмани.

Привет.
Продаю персональный сертификат WebMoney за $99.

Можете проверить: WMID 322973398779 Redfern

Всё чисто, не одной жалоб. Сделан на утерянные документы. Всё законно.
Если нужно, то есть сертификаты ещё.
Стучацо в личную почту на Вебмани.

Это не спам. Не пишите на мой WMID жалобы в арбитраж Вебмани.

Anonymous

November 12 2007, 18:09:27 UTC 4 years ago

celebrity porn galleries j9

What was publicising to happen? An inactive haziness indeed. http://celebrity-nip-slip-pics.spears-stolen.in/

Anonymous

November 12 2007, 19:03:26 UTC 4 years ago

britney spears nude upskirt photo a5

It wasn't until she was tell by the librarian of the punk undergarments that she dicey sensitised arousal. But, I'm thirsty you have contreceptives to pancakes who could faze us into a binkini methodically cheap, don't you? You are strictly beautiful, he gushed, as his he began trickling her. http://famous-people-who-suck.nudecelebrities.in/

Anonymous

November 28 2007, 22:11:50 UTC 4 years ago

naisioxerloro

Hi.
Good design, who make it?

Anonymous

December 18 2007, 13:38:59 UTC 4 years ago

There is unfortunately no 'safe' time to pregnant.

There is unfortunately no 'safe' time to have unprotected
if you wish to avoid getting pregnant. Even unprotected
during a girl's period can result in pregnancy. Although women
are generally only fertile for a few days every month (usually
around the middle of the menstrual cycle) most women have no
definite way of knowing when this is.

mature woman
mature lady
mature video
mature movie
mature lesbian
mature blow job
donne mature
mature man
hot mature
mature babe
mature free
lesbians kissing
teen lesbians
hot teen lesbians
naked lesbians

Anonymous

February 15 2008, 08:13:51 UTC 4 years ago

Viagra , Phentermine , Tramadol

See my sites

Anonymous

February 26 2008, 09:44:10 UTC 4 years ago

bolindir.com (http://www.bolindir.com)

[info]hasyer

April 7 2008, 17:17:05 UTC 4 years ago

heLLoO.

Thank you. (;

---------------------
muhabbet
korku
msn nickleri
msn nickleri
netlog

[info]sohbetiq

April 10 2008, 23:25:08 UTC 4 years ago

Hi !

Yazdıklarınız çok faydalı şeyler tşk ediyoruz aile olarak. Thanks.
Msn nickleri
Previous
← Ctrl← Alt
Next
Ctrl →Alt →
Create an Account
Forgot your login or password?
Facebook Twitter More login options
English • Español • Deutsch • Русский…