Saturday, September 19, 2015

Scheme Sucks

You will never get read without an eye-grabbing headline.

My beef with Schema arose while working through a set of programming problems that are published online. I was interested in using those problems to familiarize myself with the idioms of Scheme and Haskell, with which I am less familiar. The exercise in question asks for the sum of all Fibonacci numbers that do not exceed 10000 and are divisible by 2. For the purposes of this post, the Fibonacci sequence is defined by a recurrence relation: \[ \begin{align} F(0) &= 0 \\ F(1) &= 1 \\ F(n) &= F(n - 2) + F(n - 1). \\ \end{align} \] In an imperative language such as C, this problem can be solved with a program similar to the following one. The logic of this program mimics how a person might solve the problem with a pencil, paper, and a pocket calculator: it keeps a running total of the even Fibonacci numbers as they are computed.

This is the kind of code I could write in my sleep, which is why I am interested in exploring the functional languages. In a purely functional language such as Haskell, there is (loosely speaking) no state. Consequently, the standard looping construct is recursion. The code example below makes use of the convenient fact that the even Fibonacci numbers can be described by a recurrence relation of their own:
\[ \begin{align} F(0) &= 0 \\ F(3) &= 2 \\ F(n) &= F(n-6) + 4F(n-3). \\ \end{align} \] It will be helpful to discuss this function line-by-line.
  1. Base case. The sum of Fibonacci numbers divisible by 2 and not exceeding 0 is 0.
  2. Base case. The sum of Fibonacci numbers divisible by 2 and not exceeding 1 is 0.
  3. Recursive case. For limits greater than 1, uses a helper function to accumulate the sum.
  4. Definition of the helper function that accumulates the sum. The arguments to the helper function are the previous even Fibonacci number $F(n-6)$, the current even Fibonacci number $F(n-3)$, and the sum up to this point.
  5. If the next even Fibonacci number exceeds the limit, then the sum of the sequence is the sum up to this point.
  6. If the next even Fibonacci number does not exceed the limit, then the accumulator function is invoked recursively with the current Fibonacci number, the next Fibonacci number, and the new total.
  7. Recurrence relation for the even Fibonacci numbers, as above.
I can write a very similar algorithm in Scheme. Like in Haskell, the function uses a helper function to accumulate the sum of the sequence recursively.

So far, so good. I've worked out how to code a the solution to the problem recursively in two different functional programming languages. Now, let's get to the fun stuff. The solution to this problem can be expressed much more succinctly by defining a sequence of even Fibonacci numbers and using the takeWhile function to get the entries that do not exceed the limit.

The list of even Fibonacci numbers evenFibs is constructed beginning with the first two even Fibonacci numbers: $F(0)=0$ and $F(3)=2$. Once the first two members of the sequence are present, the rest of the sequence is populated using zipWith. In functional programming, the zip function takes two lists and returns the corresponding pairs in the list. For example, zip([1, 2], ['a', 'b']) returns [(1, 'a'), (2, 'b')]. The function zipWith calls a projection function on each corresponding pair and adds the result of the projection function to the list instead. For example, zipWith (+) [1, 4] [3, 2] returns [4, 6], with the projection function being addition ($+\colon \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$). The list evenFibs is constructed by zipping the list with itself so that each element is paired with its previous element. All you need to do is specify the recurrence relation for even Fibonacci numbers as the projection function to zipWith, and you can generate as many items in the sequence as are needed.

Once the sequence of even Fibonacci numbers has been defined, the takeWhile function can be used to pull numbers from the sequence while they do not exceed the limit. The first parameter to takeWhile, <= limit, is a predicate to check that an entry in the sequence does not exceed the limit. The sum function is then used to compute the sum of the entries extracted by takeWhile.

This approach works for many programming languages that draw on the functional tradition, including ones like C# and Python that are more often used in an imperative style.

Now, let's try writing this in Scheme. Unfortunately, in Scheme sequences of undefined size (like the Haskell lists and C# and Python generators) are a different data type than sequences of defined size. The latter are called lists, and are the most common data structure in Scheme. The former are called streams. I expected I could just define a Fibonacci stream and apply the Scheme take-while function to it. MIT Press has a nice article explaining how to define a Fibonacci stream, so I stole some code from there.

Unfortunately, the many functions in Scheme that operate on lists will not work on streams, so you have to use the stream versions instead (stream-take-while, stream-fold, etc.).
karl@adenauer$ racket -f bad-fibo-sum-stream.scm
null-list?: argument out of domain #<stream>
This is quite disappointing. Unlike Haskell, Python, and C#, Scheme needs to define two libraries with identical semantics depending on whether you need to work with a sequence of determinate or indeterminate length. Consider this the first reason that scheme sucks. The second reason is the ubiquitous linked list data structure. Adding an item to the end of a linked list is an $\Theta(n)$ operation. This means that building a list like the Fibonacci sequence from a recurrence relation is a $\Theta(n^2)$ operation. To get around this limitation, you have to construct the sequence backwards, and then reverse it.

Wednesday, February 4, 2015

Rhetorical bestiary: Survey data

Survey data is well known to be an imperfect measure of the truth. The many pitfalls of survey data mean that the numbers must be taken with some healthy skepticism.
Evidence-free assertions that black people are three times more dishonest than white people in answering surveys about drug use do not a healthy skepticism make.

Sunday, December 14, 2014

Drivers Obeying the Law, Part II

I was biking South down Ladd towards the stoplight at Division, when I heard the Suburban behind me pull around to try a pass. I was going at 25 mph, and there was another car that had just turned off of Division and was heading North in the opposing lane. Once I saw that there was oncoming traffic, I knew there was no way the Suburban could make the pass without causing a head-on collision. But he made the pass anyway! The other car had to slam on their brakes; the right taillight of the Suburban passed a foot from my handlebars.

The stoplight at Division was red, so I caught him seconds after he passed me. I tapped on his window and said that he had passed too close. He had given me only a foot, and the minimum passing distance is my fall height (6 ft). He said that he had been "completely in the other lane," and that I should ride further over. Again, I was riding 25 mph--the speed limit--and had I been riding any further over I would have risked getting doored by a person stepping out of a parked car. He then said to me:

If you want to be a stickler for the rules, just remember that I'm driving a 7,000 pound vehicle, and you weigh maybe 180 pounds. That's your choice.

Remember, I did not slow him down in any way. The light was red while he was passing me. It remained red long enough for me to catch him and exchange several sentences at the stoplight. He gained no time whatsoever. He broke at least two laws and put my body and my life in danger--and the bodies and lives in the car coming towards us--for literally no reason at all. When called out on it insisted that it is my responsibility to stay out of his way.
Tonight's incident won't be in any crash statistics, but that doesn't mean that Clinton and Ladd are safe places to bike. This guy's attitude is too common on Portland bikeways. Drivers almost never allow enough travel distance to complete a pass safely, and end up risking head-on collisions, almost sideswiping bike riders, or both.
You would think that riding the speed limit would stop unsafe passes, but it doesn't. I routinely get honked at, passed too closely, or brake checked. I've even had to endure all three in close succession! I've been honked at going 20 in a 20 on Clinton and on NE 37th; I've been honked at doing 30 in a 30 on SW Steele. I've been passed too closely on the big hill on Woodstock Blvd., while biking 10 over the speed limit! I can't even imagine what it is like out there for people who ride at a gentler pace than I do.

Saturday, December 13, 2014

Alan Dershowitz is an America-hating Bleeding-heart Liberal

About 8 years ago, I remarked to my eye doctor that maybe Alan Dershowitz's torture warrant idea wasn't such a bad one if the alternative was no accountability at all. Apparently he thought Dershowitz was an America-hating bleeding heart liberal, though, because he launched into a rant about how the CIA isn't stupid, they know that torture can produce unreliable information, and they always verify torture intelligence against other information gathered. (Other highlights: the ticking bomb scenario proves that using torture to gather intelligence is always justified; we don't know what is going on, so therefore no one should oppose it.)
Now that we have the Senate report, we know that my eye doctor was hopelessly naive. The CIA did indeed take intelligence gathered under torture as gospel, sometimes to disastrous ends—nearly letting bin Laden's driver get away, torturing innocent people whose names were given up under torture, etc.
I guess I shouldn't be surprised. What would an eye doctor from Bend, Oregon know about the CIA's torture program?

Torture vs. American Exceptionalism

Mitt Romney, in No Apology: The Case for American Greatness:
I make no apology for my conviction that America's economic and military leadership is not only good for America but also critical for freedom and peace around the world. (Page 2)
... What's chilling to consider is that if America is not the superpower, others will take our place. What nation or nations would rise, and what would be the consequences for our safety, freedom, and prosperity?
The world is a safer place when America is strong....
... The very existence of American power helps to hold tyrants in check and reduces the risk of precipitous war. (Page 10)
... No nation has shed more blood for more noble causes than the United States. Its beneficence and benevolence are unmatched by any nation on earth, and by any nation in history.
Abraham Lincoln understood that the destiny of the world was twined to the destiny of America. It is why he called the United States the "last, best hope of earth." It is still so. As citizens of America, we should be filled with love and gratitude for what this country has been, for what it is, and for what it can still be. (Page 33)
... I'm one of those who believe America is destined to remain as it been [sic] since the birth of the Republicthe brightest hope of the world. And for that belief I do not apologize. (Page 34)
Findings from the recently released torture report, as summarized by the Washington Post (emphasis added):
[A]ccording to CIA records, seven of the 39 CIA detainees known to have been subjected to the CIA's enhanced interrogation techniques produced no intelligence while in CIA custody. CIA detainees who were subjected to the CIA's enhanced interrogation techniques were usually subjected to the techniques immediately after being rendered to CIA custody. Other detainees provided significant accurate intelligence prior to, or without having been subjected to these techniques. While being subjected to the CIA's enhanced interrogation techniques and afterwards, multiple CIA detainees fabricated information, resulting in faulty intelligence. Detainees provided fabricated information on critical intelligence issues, including the terrorist threats which the CIA identified as its highest priorities.
... CIA officers regularly called into question whether the CIA's enhanced interrogation techniques were effective, assessing that the use of the techniques failed to elicit detainee cooperation or produce accurate intelligence.

The CIA never conducted a credible, comprehensive analysis of the effectiveness of its enhanced interrogation techniques....
There are no CIA records to indicate that any of the reviews independently validated the "effectiveness" claims presented by the CIA, to include basic confirmation that the intelligence cited by the CIA was acquired from CIA detainees during or after the use of the CIA's enhanced interrogation techniques. Nor did the reviews seek to confirm whether the intelligence cited by the CIA as being obtained "as a result" of the CIA's enhanced interrogation techniques was unique and "otherwise unavailable," as claimed by the CIA, and not previously obtained from other sources.

More broadly, the program caused immeasurable damage to the United States' public standing, as well as to the United States' longstanding global leadership on human rights in general and the prevention of torture in particular.
Kevin Drum's summary of the torture program seems apt (emphasis added):
The torture was far more brutal than we thought, and the CIA lied about that. It didn't work, and they lied about that too. It produced so much bad intel that it most likely impaired our national security, and of course they lied about that as well. They lied to Congress, they lied to the president, and they lied to the media.
Dick Cheney has an entirely different take on the matter:
[T]he techniques used by the Bush White House—like water boarding—were “absolutely, totally justified,” and hardly akin to torture.
“They deserve a lot of praise,” [Cheney] said, referring to the CIA, The Hill reported. “As far as I’m concerned, they ought to be decorated, not criticized.”
He also said that waterboarding and similar tactics were the “right thing[s] to do, and if I had to do it over again, I would do it. When we had that program in place, we kept the country safe from any more mass casualty attacks, which was our objective,” The Hill reported.
Cheney's argument on torture is simple: America's first duty is to protect Americans, and that which protects American's is justified. Everyone should have a sliver of sympathy for this argument, even if they reject Cheney's conclusion that his torture program was justified. But this ends-justify-the-means reasoning undermines Mitt Romney's proclamation that "[America']s beneficence and benevolence are unmatched by any nation on earth, and by any nation in history." America tortured people, brutally, without gaining any useful intelligence. America tortured innocent people, brutally, because of faulty intelligence that came from torture. Is this beneficent? Is it benevolent? If you wonder why there are so many skeptics of American exceptionalism, the Senate's torture report might have some answers.

Monday, December 1, 2014

Solidarity for me, but not for thee

On November 14, Portland's KGW TV station reported that "Portland Police Chief [Mike Reese] on Monday ordered three officers to remove 'I am Darren Wilson' images from their Facebook pages." Reese's order was not without controversy:
Maybe the Portland officers where [sic] expressing their rights of free speech when showing solidarity with their brother? [1]

I think that what they are saying is that they don't support the lynching of a white police officer without benefit of due process, a trial or even charges being brought forward.... [2]
On November 30, six members of the St. Louis Rams entered the field with their hands up in the air, in the "don't shoot" position, protesting everything that has happened in Ferguson over the last few months. The St. Louis County Police Officers Association was not amused. From the official statement by the SLPOA:
The St. Louis Police Officers Association is profoundly disappointed with the members of the St. Louis Rams football team who chose to ignore the mountains of evidence released from the St. Louis County Grand Jury this week and engage in a display that police officers around the nation found tasteless, offensive and inflammatory…
From SLPOA Business Manager Jeff Roorda:
I know that there are those that will say that these players are simply exercising their First Amendment rights. [Blah blah blah]
Jamilah Lemieux of Ebony magazine has an excellent commentary on the statement issued by the SLPOA. Read the whole thing. I will merely remark on this: if you are a black person, showing solidarity with a boy who was killed is "tasteless, offensive, and inflammatory." Indeed, it is so far outside of the bounds of civilized discourse that not even invoking the First Amendment can justify it. By contrast, if you are a "white police officer," expressing solidarity with the man who killed that boy is not just understandable, but beyond criticism.
UPDATE: In addition to believing that the First Amendment does not allow for criticism of police officers, Jeff Roorda apparently also believes that the First Amendment allows police officers abuse their position to bully and intimidate their critics.

Wednesday, November 26, 2014

Two Shootings

On April 17, 2005, during an interrogation, Esteban Carpio shot and killed police detective James L. Allen of Providence, RI. Carpio was re-arrested 45 minutes later. He was punched in the face three times by police detective Christopher Zarella, breaking bones in Carpio's face.
Comments on Carpio:
  • The streets are not like a court room. There is such thing as street justice, which compensates for the crimes that are not paid for by the legal justice system.
  • That's what he fucking gets.
  • He brought that upon himself
  • Should have let the family's of the people he killed go at him, I promise it would have been much worse. Sympathy sorry we're all out here.
  • Cops should be commended. He walked into the court alive even after shooting a cop. Now that is something!
  • Bet the two people he killed are still dead...
  • Justice bitches...  maybe you shouldn't shoot people in the face
  • This dude took a mans life away. He desevered to be killed. Hopefully he looses sight, can't talk, and spends his life in jail.
  • Bet the cop still has no face and a family torn apart by this persons attempt at flight. What bothers me is now taxes have to pay to house this fool. He should have been taken out. Eye for an eye as in Old Testament fashion.
  • This footage makes me feel all warm inside.  I am so glad he got beat like that...yes, yes..yes... because he is an animal!!!!  Kill him, smash him tare him apart.  I hope the cops do this to all these scum bags!!!
  • He got A well deserved beating,they should have not stopped and finished him off'.I can't find one good reason for scum like this to be kept alive,let the taxpayer's money go to something worth while.
In Ferguson, Missouri, on August 9, 2014, police officer Darren Wilson shot and killed Michael Brown, an unarmed teenager. Evidence about the shooting was presented to a grand jury, which on November 24 decided not to indict officer Wilson of any crime. In the aftermath of the grand jury decision, residents of Ferguson protested, both violently and nonviolently:
  • National Review: There is clearly significant racial tension in Ferguson. But the best way to resolve it is... by working peacefully through the available democratic mechanisms.... [T]he grand jury resisted the mammoth political pressure to indict strictly to assuage racial grievances, instead opting to follow the evidence. When it comes to justice, that is as much as any American can hope for.
  • Ian Tuttle: There is in fact a law in Missouri that “protects and values” not just Michael Brown’s life but every life — namely, statutes that punish homicide and manslaughter. A grand jury, weighing the evidence, determined that Darren Wilson did not transgress those laws.... As a body politic, perhaps Ferguson should not “move on,” but, legally, Darren Wilson is not a criminal according to the law of his home state, and to punish him as if he were one would be to dismiss the law as illegitimate. That serves no one.
  • Jonah Goldberg: I can’t muster sympathy for the looters, car-burners, the dress-up Bolsheviks and that ilk.... Michael Brown’s family ... should be applauded for their honorable and responsible public statements against violence and rioting.
  • Kathleen Parker: We see in Ferguson, Mo., what happens when respect for our legal process is lost: Arsonists and looters expressed their outrage that a grand jury didn't act as they thought it should.... Ferguson is what you get when mob rule overwhelms the rule of law, which was created as the defense of civilized people against the mob.
  • David Koller: Michael Brown got what he deserved.  Justice was served.
  • The problem with protests in general is they do nothing but create inconvience...and in some cases damage and injury.   The real way to pressure for change is to work through the government, who were elected to govern and who can actually change things.
  • all I see is a bunch of troublemakers that cover their faces like it was Halloween.
  • Why is it that the lowest common denominator, the thugs, get so much press and support. Oh wait, it's other thugs and lowlifes who support them. My bad.
  • The Grand Jury heard the facts and read the testimony - that's law.  What we're now witnessing is criminal trespass, vandalism and maybe homicide. Lock em up!
  • Civil Disobediance used to mean something constructive, now it's just garden variety thuggery.
  • They didn't want justice. They wanted  a lynching. If they had gotten a lynching they would have demanded Wilson burned at the stake. If they had gotten that they would have rioted looted and burned anyway. It's what they do. It's all they can ever do.  What you saw on the streets of Ferguson is the uncivilized gutter trash of society.
  • The moral principle they're fighting for seems to be, if you don't like a justice system ruling, you have the right to act like a pack of insanely rabid jackals and loot burn and destroy everything you can to show your displeasure. The philosophy of the Ferguson maniacs is about as far from Dr Martin Luther King as Adolf Hitler but by the looks of the cowardly punks destroying private property in the name of justice, very few of them would even know who Dr King was, let alone be intelligent enough to emulate his methods.
  • For all the folks who are giving the “black community has no other voice other than to commit acts of senseless violence crowd”, anarchy is anarchy. What about the Caucasian community in California who are now technically a minority? If a Caucasian was shot by a latino officer under similar circumstances, is burn baby burn OK? If every aggrieved community is given the go ahead to burn down the town, that is what we will have. [1]
  • Let's all have a peaceful protest.  What is the protest about? Racism? Poverty? Rule of law?  Desire to loot a licka sto?