la3wer09uasdfpj0239jasopiefjas0932jopasd09a
on
A Name for My Major?
·
· Score: 2
The subject of this post is H. Just H. One letter. H. Slashdot's lameness filter can go to hell.
Anyone with the gumption to tackle these three subjects for seven years doesn't need to impress the average PHB to find himself a job. There's an entire world out there, operating underneath the conventional balance sheet radar, of people tackling the really hard problems that will be making people rich ten years from now.
In "The Dynamics of Software Development" the author states, on hiring practices, that intelligence is the most important quality to hire, and that the salient feature of intelligence is individuation.
I've dabbled in all these areas myself. In the derby for the most useless possible suggestion, my vote is "H", Shannon's measure of entropy for information bearing systems.
The most telling statement was his reference to DoD as "organized crime". Before people start to wail about whether there was intent, benefit, the true nature of the victim (if any), the ass-in-the-fire repentence, or the hypocrisy of the system as a whole I'd like to point out two things: 1) the acts were illegal, 2) the acts were organized. Before you sit to compose ten giant paragraphs on the injustice of the situation, please clearly decide which of those two facts you are chosing to ignore.
If that's not enough of a cold shower, I recommend taking a long bath with Ronald Dworkin's "Law's Empire". Dworkin is a very good writer and he tackles all the difficult issues in an area of law known as jurisprudence.
The deep complexity in this matter is that the victim of this crime is the unborn child. Most software piracy consists of people with $30 budgets ripping off $300 or $3000 software packages to solve a $100 problem. The unborn child are the small companies that might exist--if software piracy didn't--that would sell $100 solutions as $30 software packages.
Just this morning I finally figured out why Slashdot sucks. I didn't have anything to say on this subject yesterday. It took me a day to organize my thoughts. Now I'm posting a day later and probably nobody even reads my post. The root problem with Slashdot is that it's the fast food outlet of discussion forums.
It really struck me looking at the responses to this item. Most of the people on Slashdot find sober second thoughts repugnant. It's true. 33 months is an awfully cold shower. We should interview him again when he gets out, after he's had such a long time to think about life. It'll be a whole new experience for the Slashdot crowd.
C++ offers a superset of C and Java programming styles. The only way you can dig yourself into the the FUD quagmire (which so impresses the author of the previous post) is to make bad choices about applying the appropriate C++ facility to the appropriate problem.
Before everyone jumps on the big crunch bandwagon, read Freeman Dyson on the subject of signal to noise ratios as physical systems, such as the universe, expand and cool. Believe the book was "Infinite in All Directions".
I once had a nice 25MHz 486DX TI TravelMate (Gateway branded) from the first laptop generation with tolerable hard drive capacity (120MB). On full power conservation, I could edit files within my text editor for nearly five hours on one charge (if I didn't save often).
Eventually the wires to the display became stretched through the hinge. The screen would go funny if you opened it up too far.
I took it through the airport once in Halifax where I had to open it up and show that it worked. I opened it up just past 90 degrees (the safe range) and then the security woman there grabbed the panel cranking it open all the way the final stop (nearly 135 degrees). I was actually holding the system in the air at the time with my hands so she could see it better. I'm 6'5" and I doubt she was ten cents over 5'0". Did she really need to break it's back just to see that there was text on the screen? Fragile? Let me adjust it!
That was an aggravating repair. Half a day running around Vancouver to find the replacement part, $90 for a thin wire bundle 12" long, and another half a day to thread the cable myself while not losing too many microscrews along the way.
I'd like to think that agent is now working at a poultry processing plant breaking limbs off of chickens with her bare hands.
I was in contact with the Twofish team during their candidacy concerning some work I had done on an improved instruction sequencing. One member of the team told me they figured rinjy was the most elegant proposal and that they would be very happy to see it prevail. Sure, they wanted to win. But more than that, they wanted the security industry to adopt a solid foundation.
There are times when Bruce has struck me as shrill or biased, but this isn't one of those times. What he's dealing with here is the very deep theme about whether the world's cryptographic fraternity is capable of sensing the right turn more often than not. If the wise men can't lead us to paradise, who can?
That reputation argument is a crock. It sounds like some kind of monetary surrogate in the minds of people who can't organize reality in any other way.
I participate in open source because I still believe in the tooth fairly. I put a tooth with a cavity under my pillow at night, I wake up the next morning and the cavity is gone.
Once upon a time it was possible to have incredible wealth, yet still have bad teeth. You don't brush your teeth to improve your reputation. Perhaps those who bleach their teeth are in it for personal profit, but the rest of us just want good teeth _without_ spending a fortune on dental work. Is it really that hard to understand?
All of the production costs, including the advertisements themselves, distribution costs (cable systems and satellite systems), plus exorbitant celebrity costs are being covered by consumers at large under the current business model.
This model exploits the network effect. A product heavily promoted on television will garner a larger display and back stock at the local retailer, because enough idiots out there think they are one glove or one shoe or one shirt away from being Tiger Woods or Michael Jordan. This reduces the stock of alternative products. If you don't want television, you just want the best shoe, there's a nice $50 shoe only they don't stock size 12. What happens? You walk out of the store with an $80 Nike, and one more slab of god awful television has just earned its commission.
It's not much different than the MS model. Those of us who don't watch television end up paying our tithes nevertheless. You can escape the net occassionally by buying your local eco soap, if you are spry enough to pull products off the floor shelf (which you have to crouch down to even see).
Let's suppose you set up a market to commission shows based on user contributed fees (supposing you can collect the $100,000 per episode it would take to make this work). In this model, the audience effectively owns the show. If the show ends up being really good, people who didn't participate in the commission will want to watch it. You would have to set up a fee system which returns profits to the original backers (the audience members with the foresight to commisssion the show).
Now we have a very interesting situation. Sally wants to see a show and she knows Bob is entitled to view the show because he participated in the initial round of funding. Sally asks Bob to tape the show so that she can avoid paying the fee. At one level this is ripping Bob off of a few microcents. On another level, if Sally bakes him a single chocolate muffin out of gratitude, he comes out ahead having ripped himself off.
What we have here is a P2P version of tragedy of the commons. It would be extremely difficult to make any system work where the backers of a show are not conceptually distinct from the audience of the show.
The reason the current system endures is because it creates a very high barrier to defection. Sure you can skip the commercials with a little bit of vigilance, but chances are you still get dinged at your local retail outlet, best intentions notwithstanding.
It internet groceries (and retail in general) had actually succeeded, it might have been possible to break this model. It would be great to be able to purchase dry goods via a web interface with user controlled filters. Transfatty oils? Click, gone. More sugar than fruit juice? Click, gone. MSG? Click, gone. Lifetime RDA for sodium in one sip? Click, gone. It would be like having your own supermarket with the top shelf on the bottom and the bottom shelf on top. That would have seriously impacted the existing television model. Which is precisely the reason this form of retail never had a snowball's chance in hell. If they nuked their ties to the marketrons, they would have to charge more up front to the end consumer than the same basket would cost in the grocery store. The average consumer is incapable of realizing that the average trip to the grocery store doesn't produce the same basket of goods (unless you spend an extra hour in the store filtering out all the surface crap).
There's a lot in life that gets paid for by nickle and diming people in subtle ways that are very difficult to add up at the end of the day. If you take the same sum of money, explain up front that they can direct this money to a project of their choosing (such as commissioning a television series of their favorite genre), or putting that same lump of money right back in their pocket, guess which choice people will make 90% of the time.
I think a narrow culture of micromedia will emerge for those of us willing to spend an hour with some content that some clever weirdo hacked together for $5000 on top of some open source modelling software, with all of the imperfection and absence of celebrity which that entails. Small groups of people will eccentric tastes are much more likely to succeed than large groups of people.
For example, I could see myself contributing $20/year to the Battlebot Foundation, which as just one of many activities, could put together a half dozen episodes a year of battlebot competitions. On the other hand, I doubt I would have forked over $20 to keep The Simpsons alive, even though I often find it entertaining.
One of the great advantages of the existing model is the absence of marginal cost. All you have to do is calculate your belt size and contribute that many dollars a month to your local cable company, which covers most viewing plans. Then you have a built in excuse for zoning out on the sofa whenever you feel like it: it isn't costing me anything.
Now think about a competing model where the content costs you real money every time you turn the TV on, and the double daggers you will have to endure from your spouse every time you collapse on the couch.
When it comes to apathy, narcissism, and denial (the three foodgroups of television) it really doesn't matter how many great minds you throw at the problem.
The best thing about having a working time machine would be pushing all who find this fascinating into it and sending them elsewhen.
If time proves to be a complex number, while I would find that fascinating I wouldn't tempted in the slightest to project the terms "backward" or "forward" into a polar coordinate system.
If there's any virtue at all to a discussion about time travel, it's that you can't determine whether mathematics or linguistics is taking the worst beating.
I dislike the politics of the content industry so much that I avoid full price movies and I mostly content myself with the music I already have. This is an effective form of protest which I would like to see more people employ.
Except. Except that the content industry is pointing to their loss of sales as evidence that everyone not giving them money is a crook and that they are therefore justified in destroying the PC as an open platform.
This is exactly the attitude that creates endless headaches mapping good concepts onto workable implementations, and results in systems becoming so convoluted by the time they work properly they are nearly impossible to maintain.
The principle of least surprise dictates that random orders of magnitude should not be sacrificed in your fundamental primitives.
It seems to me that if I spend $300 on my CPU and $600 on my GPU that I might want to be able fetch back what the GPU creates. What kind of idiot puts their most powerful processor at the end of a one way street?
There are endless reasons that could come up why this feature might need to be exploited. Just because you can't come up with them doesn't mean they don't exist. You are talking about 99.9 percent of your own creativity, which I assure you is a far sight less that the sum total of the creativity out there looking for cool new things to do.
It does make sense to consider cost/benefit here. The first observation here is that we are talking about a baseline primitive (texture returned to system memory), and that we are looking to recover a rough factor of ten, not a rough factor of 10 percent.
In the video card industry, things are designed to hit the 90 percent point. These days the GPU industry rivals the CPU industry in dollar value. I simply can't believe the graphics card companies can't afford to have someone sit down and crank this up to 50% bus utilization. I suspect they could do this without even scratching their head.
I've had to use many primitives over the years designed by this guy or his second cousin. If he only knew how much of the pain he experiences as a computer user is the result of good people bending over backwards to deal with unsuspected, arbitrary constraints when they could have been polishing the product interface instead. But some people have no imagination for these things.
Couldn't have said it better myself. I guess a lot of people haven't paid any attention to what Wolfram is trying to say in his new book: this kind of weird algorithmic pattern shit is as common as sand on a beach. Around 1983 people were playing around with wondrous numbers, which at least has the replayability advantage of not producing a monotonic sequence.
My first curse upon the world: this problem has a proof that involves analyzing 100,000 special cases producing 10,000 pages of dense results, and none of these cases can be reduced.
My second curse upon the world: some idiot bothers to find it.
The suggestion that no pure mathematician has any clue about where to begin is not equivalent to saying no pure mathematician has any clue about whether to begin. A proof is hardly worth the paper it gets published on if it doesn't reflect back on other branches of theory.
Anyone who has spent any time listening to the Technetcast archives will know that Tim O'Reilly is not someone you discard just because they are saying something you don't want to hear. He has better open source credentials than 99% of the people who will weigh into this discussion, even if we darkly suspect he is feeding his family on the side. I've done nothing in my life as a computer programmer to compare with what Tim has contributed.
And Tim is making a point here which is 100% correct. The label "open source" is not an acceptable substitute for what we are really trying to achieve. If it did happen that governments such as Peru enacted these policies, it would certainly be a victory for accountable government and the democratic process (at least between the state and its citizens, which is NOT the sum total of what democracy requires).
The lame argument here is the last paragraph of the slashdot submission. I know exactly what lame means in that paragraph: "I don't want to think that hard about difficult issues, so chalk it all up to hidden agendas, name the villians, and move along". If Tim O'Reilly's open source credentials are subject to this kind of aspersion, whose only sin so far is to give serious consideration to the political reality of taking an immoderate stance on the traditions of goverment since America was founded, there isn't a business person alive whose integrity means anything at all to the open source community.
Sure it's annoying to see Tim throw out these unpleasant thoughts half digested. But that's what he does: he creates forums for really smart people to think and speak about difficult issues.
I don't know the right answer to this question. The problem is too difficult to think through in one day, or even one year.
We need a notion along the lines of "government product" which encompasses everything they do on behalf of the public (memos, e-mail, publications, databases, registries, etc.) and mandates that all of this goverment product is fully exposed in representations supported and validated by freely available, open source code. Once you have this in place, the open source community can implement every system of government, and then we need to win the arguments over cost justification of taxpayer dollars. And maybe at the end of the day we find we are actually doing the right things for the right reasons after all.
I know that many people in this forum won't get past the fact that Tim has said something ugly. For those of you who sometimes stop to think about the unpleasant, this is one of those times to step back, take a hard look, and admit that the world doesn't always offer the easy paths we'd prefer to follow. Tim had the courage to do this, so should we.
I was a freshman at UW in 1981. Back then it was IBM playing these games. And they've always had the idea that you take what they tell you to take.
I travel 3000Km across Canada to go to the school regarded as having the best math/CS program and when I get there I discover that the CS faculity has been pillaged by the private sector, so the new rules are that first and second year CS majors can only take ONE course in computer science each term and that for that ONE course each term there is ONE choice. First year: FORTRAN and COBOL. Second year: 6809 assembly language and an introduction to data structures.
Back then Ontario had grade 13, which meant they often had a computer credit on their high school transcript. None of us from out of province had this credit. If you had this credit, you could elect to take Pascal instead of FORTRAN (but the problem assignments were the same). It cost the university an extra $10 a student/term in extra computer time.
The WIDJET terminal rooms we were given were the worst computing environment I've ever encountered. Waterloo Interactive Direct Job Entry Terminals. Ugh! A complete waste of phosphorous, although it did save trees.
IIRC there were four IBM mainframes clustered together in the big Red Room. The terminals were handled by minicomputers which gathered the jobs together and submitted them to the IBM cluster.
Some of the terminal rooms were worse than others. As a student you were given roughly 100K of storage area for your work in progress. In order to get a directory listing of the files you owned, you had to submit a job. This meant you had to sit there with your "give me a directory listing" job in the job queue. On any given night you could be stuck in the job queue for five to ten minutes. Then you had to submit a job to call up the desired file to edit. Another five to ten minutes. You couldn't do anything else on the terminal while you waited. Unless you were foolish: doing anything else cancelled the job you were waiting for!
Finally, you would submit you program to run. Upper year students had priority over freshmen. Sometimes you would submit a job that would start at queue position 7. Half an hour later you might be at queue position 30. You can't work on another assignment while you sit there. That would cancel your run job. Other people are lined up at the door waiting for a terminal, but the terminals never come free because the whole room is stuck in the run queue, and no one is getting anything done.
For one of my statistics courses I had the joy of using the IBM PC room. Brand spanking new 4.77MHz machines. We did our coursework for that course in APL in the greek/geek APL character set. I learned APL inside out in my highschool days so this was one course I enjoyed.
The IBM PCs were so unreliable that at any given time 25% of the systems would be unresponsive. You'd be standing there waiting for a system and one out of every four systems would be inoperative.
In an evil moment I discovered a way to reserve myself a keyboard. Take two systems set up back to back and reverse the keyboards. People would come up to the system, press a key see nothing on the screen. Then they would press CAPS lock and the keyboard light would toggle on and off. Obviously a dead system. Nothing to see here, move along! Too many hours at queue position 30 in that other terminal room, my survival instincts had taken over.
The 6809 room was mildly redeeming. They were crashed a lot, almost as much as the IBM PCs. But if you did get a system that worked, you could actually use your time well. We used a 6809 assembler known as WSL (Waterloo Systems Language). WSL was the most modern and well structured language I learned at Waterloo. It was an assembler where you could right proper block structured code with a while/if/then syntax. I think this was an offshoot of the Waterloo Systems Group that eventually spun off the excellent Watcom C/C++ compiler.
The only way to get a CS education at Waterloo at that time was to get a COOP assignment to the WSG. There you would meet real CS professors who would teach you real material like how to unroll conceptually nested iterators either forward or backwards.
The other nice thing about the 6809 terminals were all the bugs in the file system. You had very little storage for your own programs. Roughly 100K. Sometimes it was hard to save all your work for just one assignment there. If you wanted to keep your old assignments for reference, tough luck. It became common practice to compile your programs to the/tmp drive to preserve space in your home directory. Ocassionally if you wanted to keep a compiled output you would just mv/tmp/output/home/myname. mv had a bug where it forgot to adjust quota usage. If you then deleted this file from your home directory, it would add space to your home directory quota that had come from the/tmp directory! Many of us had megabytes of storage once this was discovered.
I explained this trick to a roommate of mine and went wild with it. He created such a huge file on/tmp that when he deleted it from his home directory, his quota wrapped to zero. Now he had an account where his home directory was frozen like ice and he was too afraid of confessing what he had done to ask the sysadmin to fix it.
The non geek faction at Waterloo was very small at the time. The math/CS dept. had 4000 undergrads, engineering was next, then science, then the arts the professional schools. Some of the non geek departments were so small they got stuck in cubbyholes. For example, the kinners and wreckers (Kinnesiology and Recreation) shared the fifth floor of the math building with the pure math dept.
There was this strange geek ordor that hung around campus and even pervaded the arts faculties. Over in the English dept. they had a required course in CS which Waterloo was teaching in PL/C of all god forsaken languages. One of the best jobs on campus was being the TA camped out in the corner of the PL/C terminal room. Half the females on campus were all in that one room, and they all needed help. Hmmm, perhaps there was a method to the cirriculum selection at Waterloo after all.
In my residence the students in Systems Design Engineering and Physics had access to better CS instruction and better CS systems than those of us majoring in CS. At that time you needed a 92% graduating average from high school just to apply to Systems Design. Where I went to high school I had an English lit teacher who said he had given out one grade higher than 90% in the last ten years. The school system in Ontario had suffered from massive grade inflation in the grade 13 school year so that Ontario students could get all the scholarships according to these insane admission requirements. The guy who got the 90% grade at my highschool graduated Summa Cum Laude from Harvard in world literature, but he wasn't smart enough to be admitted to many of the programs at Waterloo.
The other language I encountered at UW was Snobol, I think for one assignment in the second year introduction to structured programming. This was the one time Waterloo exposed me to something that really set me back. I didn't know what to make of Snobol. It had this weird PL/1-like puffy pastry syntax, yet under the hood it had this powerful string matching facility that reminded me a bit of APL's powerful array primitives. This was the first time I used a language that encouraged you to code only for the cases at hand. Your patterns weren't necessarily foolproof, but they worked for the cases the assignment required. It was my first exposure to a Perl-like environment.
One language they wouldn't teach at Waterloo at that time was C. I think some senior courses used C, but they didn't teach C even for those courses. Even at that time, if you met a person who impressed you as a lean mean programming machine, nine times out of ten they did their serious programming in C.
In second year I obtained a C compiler for my 26 pound Osborne. It came from Software Toolworks in a zip lock baggy. By the end of second year I was spending half my time programming in C on my Osborne at home, and half my time in the arcade. Much later I explained the consequences of this set of choices to my family this way: the arcade was the only place on campus where talent was rewarded with a good result.
On one assignment intended to teach programming efficiency I came up with a superior algorithmic solution. Under interpereted Pascal on a 2MHz class machine, my program ran in 10 seconds, of which 7 seconds was spent by the program listing the results to the console. The class average run time was 30 MINUTES for the brute force algorithm (coded according to the lecture's efficiency guidelines). I got a 6 out of 10 for inefficiency. In Pascal I had written a for loop where the end value was a complex expression. In Pascal the end value is evaluated once and then pushed onto the loop stack. The TA didn't know the difference between Pascal and C so he marked me down for writing a complex expression that was evaluated each time through the loop. Then he marked me down another point for multiplying the same two integers in two different expressions (and not manually creating creating a temporary variable to save an entire machine instruction). Of course, if I made that change my program ran slower due to interpretation overhead. I lost 40% of my grade for four different complaints, every one of which slowed my program down! And I didn't even get a point back for the algorithm two orders of magnitude supperior to the brute force solution. I appealed this injustice to the arcade, which awarded me with a high score for the week.
Back then IBM was the evil beyond evil. Waterloo had the same kind of relationship with IBM that they are forming with Microsoft now. And IBM had the same vision (and respect) for the minds of the future: whatever we pour in there they'll be stuck with forever. Only I think they got $5 million in kind from IBM in the form of vastly overpriced IBM equipment. And yes, it had a direct impact on Waterloo's CS cirriculum. The good news, in the case of IBM versus the free world, is that IBM was soon knocked off their arrogant throne.
Now let's step back and look at C# versus C++.
My understanding of C# is that it's a C/C++ like syntax on top of the CLR and that the CLR is a model in same general family as Visual Basic and Perl and Python and Java (to some degree): values are typed dynamically, and statically enforced type declarations are optional to the programmer. I could be all wet. I formed this impression by listening to TechNetCast archives, which is all the depth I want on C#.
It makes my job easier here that Dijkstra, sadly, was in the news this week. Try to imagine what Dijkstra would have to say about the CLR as an introduction to programming.
Many people seem to think that an introductory course has succeeded if the students can create a program, knows how to execute the program, and can debug it to the extent that it often produces a correct output. Students exposed to computers in this context come away with a runtime centric view of the programming process. If only they had more time to trace their values through the helpful and forgiving runtime, their programs would be correct more often.
This is not the lesson I would choose to teach first, and most definitely not at a university with pretensions to serious education.
There is another view of programming that what matters is the text of the program. That the text of the program has a significance far beyond the runtime nature of the code. That you refine your programming skills by learning to structure the text of your program until it convinces you of its logical integrity, to the extent that your mental model of the problem itself is correct. (If you have real talent, the process of writing the program text will debug your mental model long before you run your code for the first time.)
We often forget that the text of a program represents one instance of a larger conceptual family of programs. In a language such as BASIC the text to runtime correspondence is so dominant you can't help but forget this.
Languages with the concept of a type hierarchy and object derivation are a better introduction to programming because the idea that a program text belongs to a family of related programs is explicit in that construct.
Languages which also feature static polymorphism (Ada generics, C++ templates) are explicitly oriented toward the program text as being more fundamental than the program runtime.
At this point in my programming career manifest types don't seem any different to me than manifest constants. The real types that algorithms manipulate are sequences, arrays, and associative arrays, yet many languages still persist in having a notion of declared types which is directly equivalent to the language's runtime type layout. The CLR makes it explicit that the syntax of the language is just a different face on exactly the same runtime type model. What a strange way to introduce polymorphism to new programmers: surface syntax as a polymorphism on runtime object representation.
For all the things you can say about C++, it has at least the virtue that it makes explicit all the features of programming where the text of the program is of paramount importance.
It's hard for me to be objective, after 15 years of living with it, about the syntactic contortions of C++ and its split personality as a C impostor.
For the most part, the syntax is not so bad that you can't cut and paste from working code most of the bits and pieces required to assemble something of your own. I can write advanced HTML verbatim, but for CSS I've never managed to rise above grab, paste, and mutute. The first 30 lines of every Perl program I write I have to try three variations for the syntax of each construct until my eye for line noise returns to me.
There are a couple of areas where the syntax of C++ stoops to the unforgivable and these all have to do with irregular composition. Nesting a template type into a template can blow off your leg with the >> parsing anomoly. There is absolutely nothing worse you can do with a beginnning programmer than reward their first courageous foray into composition with a parse error from left field.
The syntax of a template function declared within the class scope is different than when the same function is declared outside of class scope, for reasons that take a long time to master. (The type of the function return is likely to be in scope in one context, out of scope in the other, requiring Byzantine changes to your function prototype declaration.)
In my view this is the tragic flaw in C++ as a teaching language. The syntax nests differently than the language semantics. The scope of the return value for a function should be a function of the scope of the function name, but it isn't because in the PARSE of the declaration the subordinate term happens to come first. You are trying to teach the principles of semantic nesting, but every time the student becomes brave enough to reform their syntactic structure basis on these insights, the syntax blows up horribly.
I think C++ can be an excellent teaching language if you have a mentor who can help you past the punishments you don't deserve before your nerve collapses.
The other point I should mention here, for people who had an impression of C++ once upon a time, is that modern C++ is not your father's C++. Now that the standard library is complete and fully integrated with the philosophy of the language and its type system, there is no difficulty teaching C++ at a level of abstraction suitable for geeky neophytes. Modern C++ is entirely unlike C and much the better for it.
Third on my list for C++ is the support environment, and by this I primarily mean the quality of the diagnostics that come from the compiler when your brave attempts to nest one working structure into another working structure fall flat. To put it bluntly, it horrifies me that a language with the complexity of C++ did not admit the quality of the diagnostics into consideration during the standardization process.
Yet C++ is not uniquely to blame here. Wouldn't it be cool if someone would sit down and classify all the kinds of mistakes that programmers make in translating their often imperfect mental model into working code, define a standard of acceptable diagnostics in all such cases, and then work backward toward a surface syntax which ensures that the compiler can achieve those diagnotics standards? (I think I was told that this was how PL/C became the supreme mess of all time and perhaps poisoned this well for all time.)
But in real languages, 90% of the mistakes one commonly makes are artifacts of the way the language has been structured.
More to the shame of the C++ community is that few (if any) C++ compilers see fit to offer a diagnostic listing in which the compiler identifies the fully qualified entity to which it binds each variable, function, and operator (or the selection procedure it used to admit or reject the available search scopes).
Suggesting that Turbo Basic would be an improvement over teaching C++ is like suggesting that the New Math was so badly flawed students would have been better off practicing sales tax calculations.
My opinion is that C++ contains more deep wisdom about the whole of the practice of programming than any other pair of langauges combined. The languages that set out to be languages universally disappoint me. In that family I would lump FORTRAN, COBOL, Pascal, PL/C, BASIC, Java, C#, and Python (my choice from this group when all I want is a language). The other family, languages with an internal vision I would lump LISP, APL, Snobol, Perl, Ruby, Prolog/Haskell/Scheme, and C++. These are the languages that can actually change the way you think. C++ stands out among this group as the language that least tries to simplify the world around it. All the other languages in this group have a strangely hypnotic character (even Snobol which I primarily included as an honour to its paternity).
As a calorie free course credit, judged either by the pantheon of languages or the nature of the institution, one could do a lot worse than C#.
In my mind the repugnance of this development has less to do with its affiliation to the Evil Empire Mark II (this too shall pass) than with the very real possibility that one could emerge from the University of Waterloo, after four years of study, and still have no idea what an intellectual calorie tastes like.
Two chapters from one of Dijkstra's books improved my program correctness by an order of magnitude, and this was after I had fully digested Bertrand Meyer on programming by contract. His notion of guards is the number one item on my top ten list of everything I know about writing correct code.
pow(2,-6) was meant to be pow (2,-64) which rounds to 1% a with a great deal more drama.
shining all the light onto just one bucket
on
Probing Hash Tables?
·
· Score: 4, Interesting
I hate to be churlish about this, but none of the early posts have addressed the core issues. Knuth's treatment is rather narrow. Buckets have very little to do with it.
The question to address is your key structure. Ideally you have the notion of your keys in cannonical representation. In object oriented contexts, the byte representation of your objects is not necessarily cannonical.
Next step is to analyze the size and distribution of your key space in cannonical representation, using as a function of some N which represents the scale of the problem instance.
At this point, if your the size of your key space is a weak function of N life is easy. Weak functions are where the average bit size of your cannonical keys is logarithmic in N or at worst sqrt(N). This represents the order of key entropy extraction.
A best case scenario is where all your keys are eight byte fully randomized GUIDs. Entropy extraction from your keys can be handled in just a few machine instructions. Worst case: you have to gather your key entropy by traversing deeply linked object hierarchies, in which case the efficiency of bucket access is swamped by the cost of constructing the bucket index.
When life is ugly, the games begin. There are no end of variations on how you can arrange to collect enough entropy (most of the time) for each key (most of the time) quickly enough (most of the time).
An extreme measure involves memoizing your key entropy with all the hassles that entails of making sure every modification to the key structure maintains key hash correspondence. If key modification is rare, you can really brute force this. If all your keys are always in the table, then keys can't change without rehashing (so one term starts to absorb another). On the other hand, if you have many keys to check, but few keys to check against, you might get sucked into finding clever and/or complicated methods for maintaining your key entropy memos.
If you have concocted a model with known degeneracies, who pays on the degenerate case? This is a game of hot potato, which again presents endless options, most of which are difficult to formally analyze (supposing you even have a sufficient model of your key space).
There are human hazards when you enter into this terrain not to be taken lightly. For some unknown reason a rather large slice of the population cannot comprehend any event more certain than 99% or less certain that 1%. pow(2,-6) is rounded up by these people to 1%, which in Murphy's calculas is as good as sunk. Nothing you can do about it. Sooner or later the pointy haired what-ifers will grind you down. Especially if they studied arithmetic for a couple of years as an undergraduate thinking it was mathematics.
Let's suppose now that you've done the dirty deed and concocted some method to extract at least log K bits of uniform key entropy (most of the time) where K somewhere between the total number of keys you might need to check and the total number of keys you might need to store. Only now does bucket management begin to matter.
Probably the best thing to do at this point is to slice the world into rough orders of magnitude: less than 10 CPU clock cycles to on-chip L1/L2 caches, 10-100 CPU clock cycles to on chip L3/off chip L3 cache, 100-1000 CPU cycles to external memory, 1000-10,000 cycles via interprocess communication/message passing, 10,000+ cycles for data structures not necessarily memory resident.
With a GHz class CPU, 1000 cycles still allows you to check one million keys per second. Do you really need to hone this down another 2.5 orders of magnitude? Sometimes you can if you really want to.
I could go on for a long time yet, but I've covered most of the ground that the rest of this thread has largely ignored.
On a more theoretical level, it is even possible to construct perfect hashing schemes with space efficiency near the Shannon limit for data sets where the average key entropy is less than one bit. Did someone mention Markov models for speech recognition? Forget Knuth volume 3. It has a lot more to do with Knuth volume 4.
Most of the checksum algorithms employed in that era were extremely light weight and not at all good by crytographic measures. The 6502 has a register set that makes x86 look positively beefy by comparison.
This could work against a simple reverse analysis. The algorithm might be table based to alleviate register pressure, and it's clear to me that the topic author is not up to the task of fleshing out such a table by differential techniques. If he had that kind of talent, he wouldn't be asking us.
On the other hand, working with a tool such as SoftIce, it's not at all difficult to capture the checksum code red handed. I used to play Falcon 3.0 under SoftIce so I could repair the system crashes on the fly (especially the guaranteed hang when you hit a ground target with one specific type of munition). "R2, see what you can to about the power."
And yes, I bypassed many kinds of crashes and checks using SoftIce. It was far easier than you would think and I enjoyed the small challenges as much as any game I played. Differential analysis is on a par with learning to play Go because you enjoy of the humility of probing your boundless incompetence.
At the other extreme, the 6502 instruction set can be learned in a couple of hours. People forget how simple things used to be. The 6502 is a four function calculator on steroids. The average configuration file these days (Apache, SMB) takes longer to master.
Thankfully, most of Canada has a thriving microbrew industry these days that makes the national brands taste like sour corn syrup by comparison. The occassional batch stands against the best German or British exports, though not with great consistency.
One strange thing is that the Guiness generally gets better the closer you get to Ireland. Once in a blue moon the Guiness on the west coast has a head you can properly sculpt. The Guiness in Halifax is generally reliable, and if you pick the right place, the Guiness in Montreal can often be excellent.
Quebec is an interesting place beer wise. The beer selection tends to be fairly cosmopolitan. If you do chose a Quebec beer, it'll likely grow some hair on your chest. Barly retisa by the jug.
Molsons primarily appeals to the kind of person were lack of surprise is the only requirement. There are so many good good beers and so many good bad beers, I can't understand why anyone would drink Molsons at all, but there's no explaining taste.
I can see how the judge would look askance at Molson's attempt to patent the Maple Leaf. These days Tim Hortons is a much stronger national brand. They probably ran into the same problem that Microsoft faced in the court room: the judge was all too familiar with their product line.
They attributed the affect to caffeine out the 200 odd akalines in coffee because they presume, by the celebrity effect, that caffeine has the highest muzzle velocity. Until this new coffee hits the market, they can't actually do a proper experiment to determine whether caffeine is the active ingredient.
Slashdot Mirror
The subject of this post is H. Just H. One letter. H. Slashdot's lameness filter can go to hell.
Anyone with the gumption to tackle these three subjects for seven years doesn't need to impress the average PHB to find himself a job. There's an entire world out there, operating underneath the conventional balance sheet radar, of people tackling the really hard problems that will be making people rich ten years from now.
In "The Dynamics of Software Development" the author states, on hiring practices, that intelligence is the most important quality to hire, and that the salient feature of intelligence is individuation.
I've dabbled in all these areas myself. In the derby for the most useless possible suggestion, my vote is "H", Shannon's measure of entropy for information bearing systems.
The most telling statement was his reference to DoD as "organized crime". Before people start to wail about whether there was intent, benefit, the true nature of the victim (if any), the ass-in-the-fire repentence, or the hypocrisy of the system as a whole I'd like to point out two things: 1) the acts were illegal, 2) the acts were organized. Before you sit to compose ten giant paragraphs on the injustice of the situation, please clearly decide which of those two facts you are chosing to ignore.
If that's not enough of a cold shower, I recommend taking a long bath with Ronald Dworkin's "Law's Empire". Dworkin is a very good writer and he tackles all the difficult issues in an area of law known as jurisprudence.
The deep complexity in this matter is that the victim of this crime is the unborn child. Most software piracy consists of people with $30 budgets ripping off $300 or $3000 software packages to solve a $100 problem. The unborn child are the small companies that might exist--if software piracy didn't--that would sell $100 solutions as $30 software packages.
Just this morning I finally figured out why Slashdot sucks. I didn't have anything to say on this subject yesterday. It took me a day to organize my thoughts. Now I'm posting a day later and probably nobody even reads my post. The root problem with Slashdot is that it's the fast food outlet of discussion forums.
It really struck me looking at the responses to this item. Most of the people on Slashdot find sober second thoughts repugnant. It's true. 33 months is an awfully cold shower. We should interview him again when he gets out, after he's had such a long time to think about life. It'll be a whole new experience for the Slashdot crowd.
For twenty minutes this morning my traffic to the east coast was being dropped at XL2.SEA.ALTER.NET
C++ offers a superset of C and Java programming styles. The only way you can dig yourself into the the FUD quagmire (which so impresses the author of the previous post) is to make bad choices about applying the appropriate C++ facility to the appropriate problem.
Before everyone jumps on the big crunch bandwagon, read Freeman Dyson on the subject of signal to noise ratios as physical systems, such as the universe, expand and cool. Believe the book was "Infinite in All Directions".
I once had a nice 25MHz 486DX TI TravelMate (Gateway branded) from the first laptop generation with tolerable hard drive capacity (120MB). On full power conservation, I could edit files within my text editor for nearly five hours on one charge (if I didn't save often).
Eventually the wires to the display became stretched through the hinge. The screen would go funny if you opened it up too far.
I took it through the airport once in Halifax where I had to open it up and show that it worked. I opened it up just past 90 degrees (the safe range) and then the security woman there grabbed the panel cranking it open all the way the final stop (nearly 135 degrees). I was actually holding the system in the air at the time with my hands so she could see it better. I'm 6'5" and I doubt she was ten cents over 5'0". Did she really need to break it's back just to see that there was text on the screen? Fragile? Let me adjust it!
That was an aggravating repair. Half a day running around Vancouver to find the replacement part, $90 for a thin wire bundle 12" long, and another half a day to thread the cable myself while not losing too many microscrews along the way.
I'd like to think that agent is now working at a poultry processing plant breaking limbs off of chickens with her bare hands.
I was in contact with the Twofish team during their candidacy concerning some work I had done on an improved instruction sequencing. One member of the team told me they figured rinjy was the most elegant proposal and that they would be very happy to see it prevail. Sure, they wanted to win. But more than that, they wanted the security industry to adopt a solid foundation.
There are times when Bruce has struck me as shrill or biased, but this isn't one of those times. What he's dealing with here is the very deep theme about whether the world's cryptographic fraternity is capable of sensing the right turn more often than not. If the wise men can't lead us to paradise, who can?
I'd say that's an issue worth talking about.
That reputation argument is a crock. It sounds like some kind of monetary surrogate in the minds of people who can't organize reality in any other way.
I participate in open source because I still believe in the tooth fairly. I put a tooth with a cavity under my pillow at night, I wake up the next morning and the cavity is gone.
Once upon a time it was possible to have incredible wealth, yet still have bad teeth. You don't brush your teeth to improve your reputation. Perhaps those who bleach their teeth are in it for personal profit, but the rest of us just want good teeth _without_ spending a fortune on dental work. Is it really that hard to understand?
All of the production costs, including the advertisements themselves, distribution costs (cable systems and satellite systems), plus exorbitant celebrity costs are being covered by consumers at large under the current business model.
This model exploits the network effect. A product heavily promoted on television will garner a larger display and back stock at the local retailer, because enough idiots out there think they are one glove or one shoe or one shirt away from being Tiger Woods or Michael Jordan. This reduces the stock of alternative products. If you don't want television, you just want the best shoe, there's a nice $50 shoe only they don't stock size 12. What happens? You walk out of the store with an $80 Nike, and one more slab of god awful television has just earned its commission.
It's not much different than the MS model. Those of us who don't watch television end up paying our tithes nevertheless. You can escape the net occassionally by buying your local eco soap, if you are spry enough to pull products off the floor shelf (which you have to crouch down to even see).
Let's suppose you set up a market to commission shows based on user contributed fees (supposing you can collect the $100,000 per episode it would take to make this work). In this model, the audience effectively owns the show. If the show ends up being really good, people who didn't participate in the commission will want to watch it. You would have to set up a fee system which returns profits to the original backers (the audience members with the foresight to commisssion the show).
Now we have a very interesting situation. Sally wants to see a show and she knows Bob is entitled to view the show because he participated in the initial round of funding. Sally asks Bob to tape the show so that she can avoid paying the fee. At one level this is ripping Bob off of a few microcents. On another level, if Sally bakes him a single chocolate muffin out of gratitude, he comes out ahead having ripped himself off.
What we have here is a P2P version of tragedy of the commons. It would be extremely difficult to make any system work where the backers of a show are not conceptually distinct from the audience of the show.
The reason the current system endures is because it creates a very high barrier to defection. Sure you can skip the commercials with a little bit of vigilance, but chances are you still get dinged at your local retail outlet, best intentions notwithstanding.
It internet groceries (and retail in general) had actually succeeded, it might have been possible to break this model. It would be great to be able to purchase dry goods via a web interface with user controlled filters. Transfatty oils? Click, gone. More sugar than fruit juice? Click, gone. MSG? Click, gone. Lifetime RDA for sodium in one sip? Click, gone. It would be like having your own supermarket with the top shelf on the bottom and the bottom shelf on top. That would have seriously impacted the existing television model. Which is precisely the reason this form of retail never had a snowball's chance in hell. If they nuked their ties to the marketrons, they would have to charge more up front to the end consumer than the same basket would cost in the grocery store. The average consumer is incapable of realizing that the average trip to the grocery store doesn't produce the same basket of goods (unless you spend an extra hour in the store filtering out all the surface crap).
There's a lot in life that gets paid for by nickle and diming people in subtle ways that are very difficult to add up at the end of the day. If you take the same sum of money, explain up front that they can direct this money to a project of their choosing (such as commissioning a television series of their favorite genre), or putting that same lump of money right back in their pocket, guess which choice people will make 90% of the time.
I think a narrow culture of micromedia will emerge for those of us willing to spend an hour with some content that some clever weirdo hacked together for $5000 on top of some open source modelling software, with all of the imperfection and absence of celebrity which that entails. Small groups of people will eccentric tastes are much more likely to succeed than large groups of people.
For example, I could see myself contributing $20/year to the Battlebot Foundation, which as just one of many activities, could put together a half dozen episodes a year of battlebot competitions. On the other hand, I doubt I would have forked over $20 to keep The Simpsons alive, even though I often find it entertaining.
One of the great advantages of the existing model is the absence of marginal cost. All you have to do is calculate your belt size and contribute that many dollars a month to your local cable company, which covers most viewing plans. Then you have a built in excuse for zoning out on the sofa whenever you feel like it: it isn't costing me anything.
Now think about a competing model where the content costs you real money every time you turn the TV on, and the double daggers you will have to endure from your spouse every time you collapse on the couch.
When it comes to apathy, narcissism, and denial (the three foodgroups of television) it really doesn't matter how many great minds you throw at the problem.
The best thing about having a working time machine would be pushing all who find this fascinating into it and sending them elsewhen.
If time proves to be a complex number, while I would find that fascinating I wouldn't tempted in the slightest to project the terms "backward" or "forward" into a polar coordinate system.
If there's any virtue at all to a discussion about time travel, it's that you can't determine whether mathematics or linguistics is taking the worst beating.
I dislike the politics of the content industry so much that I avoid full price movies and I mostly content myself with the music I already have. This is an effective form of protest which I would like to see more people employ.
Except. Except that the content industry is pointing to their loss of sales as evidence that everyone not giving them money is a crook and that they are therefore justified in destroying the PC as an open platform.
Who needs clever accounting with logic like that?
This is exactly the attitude that creates endless headaches mapping good concepts onto workable implementations, and results in systems becoming so convoluted by the time they work properly they are nearly impossible to maintain.
The principle of least surprise dictates that random orders of magnitude should not be sacrificed in your fundamental primitives.
It seems to me that if I spend $300 on my CPU and $600 on my GPU that I might want to be able fetch back what the GPU creates. What kind of idiot puts their most powerful processor at the end of a one way street?
There are endless reasons that could come up why this feature might need to be exploited. Just because you can't come up with them doesn't mean they don't exist. You are talking about 99.9 percent of your own creativity, which I assure you is a far sight less that the sum total of the creativity out there looking for cool new things to do.
It does make sense to consider cost/benefit here. The first observation here is that we are talking about a baseline primitive (texture returned to system memory), and that we are looking to recover a rough factor of ten, not a rough factor of 10 percent.
In the video card industry, things are designed to hit the 90 percent point. These days the GPU industry rivals the CPU industry in dollar value. I simply can't believe the graphics card companies can't afford to have someone sit down and crank this up to 50% bus utilization. I suspect they could do this without even scratching their head.
I've had to use many primitives over the years designed by this guy or his second cousin. If he only knew how much of the pain he experiences as a computer user is the result of good people bending over backwards to deal with unsuspected, arbitrary constraints when they could have been polishing the product interface instead. But some people have no imagination for these things.
Couldn't have said it better myself. I guess a lot of people haven't paid any attention to what Wolfram is trying to say in his new book: this kind of weird algorithmic pattern shit is as common as sand on a beach. Around 1983 people were playing around with wondrous numbers, which at least has the replayability advantage of not producing a monotonic sequence.
My first curse upon the world: this problem has a proof that involves analyzing 100,000 special cases producing 10,000 pages of dense results, and none of these cases can be reduced.
My second curse upon the world: some idiot bothers to find it.
The suggestion that no pure mathematician has any clue about where to begin is not equivalent to saying no pure mathematician has any clue about whether to begin. A proof is hardly worth the paper it gets published on if it doesn't reflect back on other branches of theory.
Anyone who has spent any time listening to the Technetcast archives will know that Tim O'Reilly is not someone you discard just because they are saying something you don't want to hear. He has better open source credentials than 99% of the people who will weigh into this discussion, even if we darkly suspect he is feeding his family on the side. I've done nothing in my life as a computer programmer to compare with what Tim has contributed.
And Tim is making a point here which is 100% correct. The label "open source" is not an acceptable substitute for what we are really trying to achieve. If it did happen that governments such as Peru enacted these policies, it would certainly be a victory for accountable government and the democratic process (at least between the state and its citizens, which is NOT the sum total of what democracy requires).
The lame argument here is the last paragraph of the slashdot submission. I know exactly what lame means in that paragraph: "I don't want to think that hard about difficult issues, so chalk it all up to hidden agendas, name the villians, and move along". If Tim O'Reilly's open source credentials are subject to this kind of aspersion, whose only sin so far is to give serious consideration to the political reality of taking an immoderate stance on the traditions of goverment since America was founded, there isn't a business person alive whose integrity means anything at all to the open source community.
Sure it's annoying to see Tim throw out these unpleasant thoughts half digested. But that's what he does: he creates forums for really smart people to think and speak about difficult issues.
I don't know the right answer to this question. The problem is too difficult to think through in one day, or even one year.
We need a notion along the lines of "government product" which encompasses everything they do on behalf of the public (memos, e-mail, publications, databases, registries, etc.) and mandates that all of this goverment product is fully exposed in representations supported and validated by freely available, open source code. Once you have this in place, the open source community can implement every system of government, and then we need to win the arguments over cost justification of taxpayer dollars. And maybe at the end of the day we find we are actually doing the right things for the right reasons after all.
I know that many people in this forum won't get past the fact that Tim has said something ugly. For those of you who sometimes stop to think about the unpleasant, this is one of those times to step back, take a hard look, and admit that the world doesn't always offer the easy paths we'd prefer to follow. Tim had the courage to do this, so should we.
I was a freshman at UW in 1981. Back then it was IBM playing these games. And they've always had the idea that you take what they tell you to take.
/tmp drive to preserve space in your home directory. Ocassionally if you wanted to keep a compiled output you would just mv /tmp/output /home/myname. mv had a bug where it forgot to adjust quota usage. If you then deleted this file from your home directory, it would add space to your home directory quota that had come from the /tmp directory! Many of us had megabytes of storage once this was discovered.
/tmp that when he deleted it from his home directory, his quota wrapped to zero. Now he had an account where his home directory was frozen like ice and he was too afraid of confessing what he had done to ask the sysadmin to fix it.
I travel 3000Km across Canada to go to the school regarded as having the best math/CS program and when I get there I discover that the CS faculity has been pillaged by the private sector, so the new rules are that first and second year CS majors can only take ONE course in computer science each term and that for that ONE course each term there is ONE choice. First year: FORTRAN and COBOL. Second year: 6809 assembly language and an introduction to data structures.
Back then Ontario had grade 13, which meant they often had a computer credit on their high school transcript. None of us from out of province had this credit. If you had this credit, you could elect to take Pascal instead of FORTRAN (but the problem assignments were the same). It cost the university an extra $10 a student/term in extra computer time.
The WIDJET terminal rooms we were given were the worst computing environment I've ever encountered. Waterloo Interactive Direct Job Entry Terminals. Ugh! A complete waste of phosphorous, although it did save trees.
IIRC there were four IBM mainframes clustered together in the big Red Room. The terminals were handled by minicomputers which gathered the jobs together and submitted them to the IBM cluster.
Some of the terminal rooms were worse than others. As a student you were given roughly 100K of storage area for your work in progress. In order to get a directory listing of the files you owned, you had to submit a job. This meant you had to sit there with your "give me a directory listing" job in the job queue. On any given night you could be stuck in the job queue for five to ten minutes. Then you had to submit a job to call up the desired file to edit. Another five to ten minutes. You couldn't do anything else on the terminal while you waited. Unless you were foolish: doing anything else cancelled the job you were waiting for!
Finally, you would submit you program to run. Upper year students had priority over freshmen. Sometimes you would submit a job that would start at queue position 7. Half an hour later you might be at queue position 30. You can't work on another assignment while you sit there. That would cancel your run job. Other people are lined up at the door waiting for a terminal, but the terminals never come free because the whole room is stuck in the run queue, and no one is getting anything done.
For one of my statistics courses I had the joy of using the IBM PC room. Brand spanking new 4.77MHz machines. We did our coursework for that course in APL in the greek/geek APL character set. I learned APL inside out in my highschool days so this was one course I enjoyed.
The IBM PCs were so unreliable that at any given time 25% of the systems would be unresponsive. You'd be standing there waiting for a system and one out of every four systems would be inoperative.
In an evil moment I discovered a way to reserve myself a keyboard. Take two systems set up back to back and reverse the keyboards. People would come up to the system, press a key see nothing on the screen. Then they would press CAPS lock and the keyboard light would toggle on and off. Obviously a dead system. Nothing to see here, move along! Too many hours at queue position 30 in that other terminal room, my survival instincts had taken over.
The 6809 room was mildly redeeming. They were crashed a lot, almost as much as the IBM PCs. But if you did get a system that worked, you could actually use your time well. We used a 6809 assembler known as WSL (Waterloo Systems Language). WSL was the most modern and well structured language I learned at Waterloo. It was an assembler where you could right proper block structured code with a while/if/then syntax. I think this was an offshoot of the Waterloo Systems Group that eventually spun off the excellent Watcom C/C++ compiler.
The only way to get a CS education at Waterloo at that time was to get a COOP assignment to the WSG. There you would meet real CS professors who would teach you real material like how to unroll conceptually nested iterators either forward or backwards.
The other nice thing about the 6809 terminals were all the bugs in the file system. You had very little storage for your own programs. Roughly 100K. Sometimes it was hard to save all your work for just one assignment there. If you wanted to keep your old assignments for reference, tough luck. It became common practice to compile your programs to the
I explained this trick to a roommate of mine and went wild with it. He created such a huge file on
The non geek faction at Waterloo was very small at the time. The math/CS dept. had 4000 undergrads, engineering was next, then science, then the arts the professional schools. Some of the non geek departments were so small they got stuck in cubbyholes. For example, the kinners and wreckers (Kinnesiology and Recreation) shared the fifth floor of the math building with the pure math dept.
There was this strange geek ordor that hung around campus and even pervaded the arts faculties. Over in the English dept. they had a required course in CS which Waterloo was teaching in PL/C of all god forsaken languages. One of the best jobs on campus was being the TA camped out in the corner of the PL/C terminal room. Half the females on campus were all in that one room, and they all needed help. Hmmm, perhaps there was a method to the cirriculum selection at Waterloo after all.
In my residence the students in Systems Design Engineering and Physics had access to better CS instruction and better CS systems than those of us majoring in CS. At that time you needed a 92% graduating average from high school just to apply to Systems Design. Where I went to high school I had an English lit teacher who said he had given out one grade higher than 90% in the last ten years. The school system in Ontario had suffered from massive grade inflation in the grade 13 school year so that Ontario students could get all the scholarships according to these insane admission requirements. The guy who got the 90% grade at my highschool graduated Summa Cum Laude from Harvard in world literature, but he wasn't smart enough to be admitted to many of the programs at Waterloo.
The other language I encountered at UW was Snobol, I think for one assignment in the second year introduction to structured programming. This was the one time Waterloo exposed me to something that really set me back. I didn't know what to make of Snobol. It had this weird PL/1-like puffy pastry syntax, yet under the hood it had this powerful string matching facility that reminded me a bit of APL's powerful array primitives. This was the first time I used a language that encouraged you to code only for the cases at hand. Your patterns weren't necessarily foolproof, but they worked for the cases the assignment required. It was my first exposure to a Perl-like environment.
One language they wouldn't teach at Waterloo at that time was C. I think some senior courses used C, but they didn't teach C even for those courses. Even at that time, if you met a person who impressed you as a lean mean programming machine, nine times out of ten they did their serious programming in C.
In second year I obtained a C compiler for my 26 pound Osborne. It came from Software Toolworks in a zip lock baggy. By the end of second year I was spending half my time programming in C on my Osborne at home, and half my time in the arcade. Much later I explained the consequences of this set of choices to my family this way: the arcade was the only place on campus where talent was rewarded with a good result.
On one assignment intended to teach programming efficiency I came up with a superior algorithmic solution. Under interpereted Pascal on a 2MHz class machine, my program ran in 10 seconds, of which 7 seconds was spent by the program listing the results to the console. The class average run time was 30 MINUTES for the brute force algorithm (coded according to the lecture's efficiency guidelines). I got a 6 out of 10 for inefficiency. In Pascal I had written a for loop where the end value was a complex expression. In Pascal the end value is evaluated once and then pushed onto the loop stack. The TA didn't know the difference between Pascal and C so he marked me down for writing a complex expression that was evaluated each time through the loop. Then he marked me down another point for multiplying the same two integers in two different expressions (and not manually creating creating a temporary variable to save an entire machine instruction). Of course, if I made that change my program ran slower due to interpretation overhead. I lost 40% of my grade for four different complaints, every one of which slowed my program down! And I didn't even get a point back for the algorithm two orders of magnitude supperior to the brute force solution. I appealed this injustice to the arcade, which awarded me with a high score for the week.
Back then IBM was the evil beyond evil. Waterloo had the same kind of relationship with IBM that they are forming with Microsoft now. And IBM had the same vision (and respect) for the minds of the future: whatever we pour in there they'll be stuck with forever. Only I think they got $5 million in kind from IBM in the form of vastly overpriced IBM equipment. And yes, it had a direct impact on Waterloo's CS cirriculum. The good news, in the case of IBM versus the free world, is that IBM was soon knocked off their arrogant throne.
Now let's step back and look at C# versus C++.
My understanding of C# is that it's a C/C++ like syntax on top of the CLR and that the CLR is a model in same general family as Visual Basic and Perl and Python and Java (to some degree): values are typed dynamically, and statically enforced type declarations are optional to the programmer. I could be all wet. I formed this impression by listening to TechNetCast archives, which is all the depth I want on C#.
It makes my job easier here that Dijkstra, sadly, was in the news this week. Try to imagine what Dijkstra would have to say about the CLR as an introduction to programming.
Many people seem to think that an introductory course has succeeded if the students can create a program, knows how to execute the program, and can debug it to the extent that it often produces a correct output. Students exposed to computers in this context come away with a runtime centric view of the programming process. If only they had more time to trace their values through the helpful and forgiving runtime, their programs would be correct more often.
This is not the lesson I would choose to teach first, and most definitely not at a university with pretensions to serious education.
There is another view of programming that what matters is the text of the program. That the text of the program has a significance far beyond the runtime nature of the code. That you refine your programming skills by learning to structure the text of your program until it convinces you of its logical integrity, to the extent that your mental model of the problem itself is correct. (If you have real talent, the process of writing the program text will debug your mental model long before you run your code for the first time.)
We often forget that the text of a program represents one instance of a larger conceptual family of programs. In a language such as BASIC the text to runtime correspondence is so dominant you can't help but forget this.
Languages with the concept of a type hierarchy and object derivation are a better introduction to programming because the idea that a program text belongs to a family of related programs is explicit in that construct.
Languages which also feature static polymorphism (Ada generics, C++ templates) are explicitly oriented toward the program text as being more fundamental than the program runtime.
At this point in my programming career manifest types don't seem any different to me than manifest constants. The real types that algorithms manipulate are sequences, arrays, and associative arrays, yet many languages still persist in having a notion of declared types which is directly equivalent to the language's runtime type layout. The CLR makes it explicit that the syntax of the language is just a different face on exactly the same runtime type model. What a strange way to introduce polymorphism to new programmers: surface syntax as a polymorphism on runtime object representation.
For all the things you can say about C++, it has at least the virtue that it makes explicit all the features of programming where the text of the program is of paramount importance.
It's hard for me to be objective, after 15 years of living with it, about the syntactic contortions of C++ and its split personality as a C impostor.
For the most part, the syntax is not so bad that you can't cut and paste from working code most of the bits and pieces required to assemble something of your own. I can write advanced HTML verbatim, but for CSS I've never managed to rise above grab, paste, and mutute. The first 30 lines of every Perl program I write I have to try three variations for the syntax of each construct until my eye for line noise returns to me.
There are a couple of areas where the syntax of C++ stoops to the unforgivable and these all have to do with irregular composition. Nesting a template type into a template can blow off your leg with the >> parsing anomoly. There is absolutely nothing worse you can do with a beginnning programmer than reward their first courageous foray into composition with a parse error from left field.
The syntax of a template function declared within the class scope is different than when the same function is declared outside of class scope, for reasons that take a long time to master. (The type of the function return is likely to be in scope in one context, out of scope in the other, requiring Byzantine changes to your function prototype declaration.)
In my view this is the tragic flaw in C++ as a teaching language. The syntax nests differently than the language semantics. The scope of the return value for a function should be a function of the scope of the function name, but it isn't because in the PARSE of the declaration the subordinate term happens to come first. You are trying to teach the principles of semantic nesting, but every time the student becomes brave enough to reform their syntactic structure basis on these insights, the syntax blows up horribly.
I think C++ can be an excellent teaching language if you have a mentor who can help you past the punishments you don't deserve before your nerve collapses.
The other point I should mention here, for people who had an impression of C++ once upon a time, is that modern C++ is not your father's C++. Now that the standard library is complete and fully integrated with the philosophy of the language and its type system, there is no difficulty teaching C++ at a level of abstraction suitable for geeky neophytes. Modern C++ is entirely unlike C and much the better for it.
Third on my list for C++ is the support environment, and by this I primarily mean the quality of the diagnostics that come from the compiler when your brave attempts to nest one working structure into another working structure fall flat. To put it bluntly, it horrifies me that a language with the complexity of C++ did not admit the quality of the diagnostics into consideration during the standardization process.
Yet C++ is not uniquely to blame here. Wouldn't it be cool if someone would sit down and classify all the kinds of mistakes that programmers make in translating their often imperfect mental model into working code, define a standard of acceptable diagnostics in all such cases, and then work backward toward a surface syntax which ensures that the compiler can achieve those diagnotics standards? (I think I was told that this was how PL/C became the supreme mess of all time and perhaps poisoned this well for all time.)
But in real languages, 90% of the mistakes one commonly makes are artifacts of the way the language has been structured.
More to the shame of the C++ community is that few (if any) C++ compilers see fit to offer a diagnostic listing in which the compiler identifies the fully qualified entity to which it binds each variable, function, and operator (or the selection procedure it used to admit or reject the available search scopes).
Suggesting that Turbo Basic would be an improvement over teaching C++ is like suggesting that the New Math was so badly flawed students would have been better off practicing sales tax calculations.
My opinion is that C++ contains more deep wisdom about the whole of the practice of programming than any other pair of langauges combined. The languages that set out to be languages universally disappoint me. In that family I would lump FORTRAN, COBOL, Pascal, PL/C, BASIC, Java, C#, and Python (my choice from this group when all I want is a language). The other family, languages with an internal vision I would lump LISP, APL, Snobol, Perl, Ruby, Prolog/Haskell/Scheme, and C++. These are the languages that can actually change the way you think. C++ stands out among this group as the language that least tries to simplify the world around it. All the other languages in this group have a strangely hypnotic character (even Snobol which I primarily included as an honour to its paternity).
As a calorie free course credit, judged either by the pantheon of languages or the nature of the institution, one could do a lot worse than C#.
In my mind the repugnance of this development has less to do with its affiliation to the Evil Empire Mark II (this too shall pass) than with the very real possibility that one could emerge from the University of Waterloo, after four years of study, and still have no idea what an intellectual calorie tastes like.
Two chapters from one of Dijkstra's books improved my program correctness by an order of magnitude, and this was after I had fully digested Bertrand Meyer on programming by contract. His notion of guards is the number one item on my top ten list of everything I know about writing correct code.
That would be bear paws not bear hands.
And get yourself a pet dog named Commodore. Tip: provide input at least once a day.
pow(2,-6) was meant to be pow (2,-64) which rounds to 1% a with a great deal more drama.
I hate to be churlish about this, but none of the early posts have addressed the core issues. Knuth's treatment is rather narrow. Buckets have very little to do with it.
The question to address is your key structure. Ideally you have the notion of your keys in cannonical representation. In object oriented contexts, the byte representation of your objects is not necessarily cannonical.
Next step is to analyze the size and distribution of your key space in cannonical representation, using as a function of some N which represents the scale of the problem instance.
At this point, if your the size of your key space is a weak function of N life is easy. Weak functions are where the average bit size of your cannonical keys is logarithmic in N or at worst sqrt(N). This represents the order of key entropy extraction.
A best case scenario is where all your keys are eight byte fully randomized GUIDs. Entropy extraction from your keys can be handled in just a few machine instructions. Worst case: you have to gather your key entropy by traversing deeply linked object hierarchies, in which case the efficiency of bucket access is swamped by the cost of constructing the bucket index.
When life is ugly, the games begin. There are no end of variations on how you can arrange to collect enough entropy (most of the time) for each key (most of the time) quickly enough (most of the time).
An extreme measure involves memoizing your key entropy with all the hassles that entails of making sure every modification to the key structure maintains key hash correspondence. If key modification is rare, you can really brute force this. If all your keys are always in the table, then keys can't change without rehashing (so one term starts to absorb another). On the other hand, if you have many keys to check, but few keys to check against, you might get sucked into finding clever and/or complicated methods for maintaining your key entropy memos.
If you have concocted a model with known degeneracies, who pays on the degenerate case? This is a game of hot potato, which again presents endless options, most of which are difficult to formally analyze (supposing you even have a sufficient model of your key space).
There are human hazards when you enter into this terrain not to be taken lightly. For some unknown reason a rather large slice of the population cannot comprehend any event more certain than 99% or less certain that 1%. pow(2,-6) is rounded up by these people to 1%, which in Murphy's calculas is as good as sunk. Nothing you can do about it. Sooner or later the pointy haired what-ifers will grind you down. Especially if they studied arithmetic for a couple of years as an undergraduate thinking it was mathematics.
Let's suppose now that you've done the dirty deed and concocted some method to extract at least log K bits of uniform key entropy (most of the time) where K somewhere between the total number of keys you might need to check and the total number of keys you might need to store. Only now does bucket management begin to matter.
Probably the best thing to do at this point is to slice the world into rough orders of magnitude: less than 10 CPU clock cycles to on-chip L1/L2 caches, 10-100 CPU clock cycles to on chip L3/off chip L3 cache, 100-1000 CPU cycles to external memory, 1000-10,000 cycles via interprocess communication/message passing, 10,000+ cycles for data structures not necessarily memory resident.
With a GHz class CPU, 1000 cycles still allows you to check one million keys per second. Do you really need to hone this down another 2.5 orders of magnitude? Sometimes you can if you really want to.
I could go on for a long time yet, but I've covered most of the ground that the rest of this thread has largely ignored.
On a more theoretical level, it is even possible to construct perfect hashing schemes with space efficiency near the Shannon limit for data sets where the average key entropy is less than one bit. Did someone mention Markov models for speech recognition? Forget Knuth volume 3. It has a lot more to do with Knuth volume 4.
Most of the checksum algorithms employed in that era were extremely light weight and not at all good by crytographic measures. The 6502 has a register set that makes x86 look positively beefy by comparison.
This could work against a simple reverse analysis. The algorithm might be table based to alleviate register pressure, and it's clear to me that the topic author is not up to the task of fleshing out such a table by differential techniques. If he had that kind of talent, he wouldn't be asking us.
On the other hand, working with a tool such as SoftIce, it's not at all difficult to capture the checksum code red handed. I used to play Falcon 3.0 under SoftIce so I could repair the system crashes on the fly (especially the guaranteed hang when you hit a ground target with one specific type of munition). "R2, see what you can to about the power."
And yes, I bypassed many kinds of crashes and checks using SoftIce. It was far easier than you would think and I enjoyed the small challenges as much as any game I played. Differential analysis is on a par with learning to play Go because you enjoy of the humility of probing your boundless incompetence.
At the other extreme, the 6502 instruction set can be learned in a couple of hours. People forget how simple things used to be. The 6502 is a four function calculator on steroids. The average configuration file these days (Apache, SMB) takes longer to master.
Thankfully, most of Canada has a thriving microbrew industry these days that makes the national brands taste like sour corn syrup by comparison. The occassional batch stands against the best German or British exports, though not with great consistency.
One strange thing is that the Guiness generally gets better the closer you get to Ireland. Once in a blue moon the Guiness on the west coast has a head you can properly sculpt. The Guiness in Halifax is generally reliable, and if you pick the right place, the Guiness in Montreal can often be excellent.
Quebec is an interesting place beer wise. The beer selection tends to be fairly cosmopolitan. If you do chose a Quebec beer, it'll likely grow some hair on your chest. Barly retisa by the jug.
Molsons primarily appeals to the kind of person were lack of surprise is the only requirement. There are so many good good beers and so many good bad beers, I can't understand why anyone would drink Molsons at all, but there's no explaining taste.
I can see how the judge would look askance at Molson's attempt to patent the Maple Leaf. These days Tim Hortons is a much stronger national brand. They probably ran into the same problem that Microsoft faced in the court room: the judge was all too familiar with their product line.
I've always thought that smoking in enclosed public spaces was the moral equivalent to peeing in a public swimming pool.
They attributed the affect to caffeine out the 200 odd akalines in coffee because they presume, by the celebrity effect, that caffeine has the highest muzzle velocity. Until this new coffee hits the market, they can't actually do a proper experiment to determine whether caffeine is the active ingredient.
Speak of the devil, Science Daily features a caffeine study today: Jolting Joe