On Syntax and Semantics

This is actually a post about combinatorics, but before we get there, I need to talk about languages. Every expression in any language has two important aspects: syntax-- the structure of the expression, and semantics-- the meaning of the expression. Let's see an example. I'll take Chomsky's; "Colorless green ideas sleep furiously." Syntactically this sentence is "adjective, adjective, noun (subject, plural) being modified by the adjectives, intransitive verb (present tense, active, third person plural) being modified by adverb, adverb." This sentence is what logicians call a "well-formed formula." A well formed formula is any formula which does not violate the grammar of the language. So, we could replace every word in the sentence with another which has the same part of speech, tense, mood, (and every other grammatical term they satisfy that I don't know) and still have a grammatically correct sentence. E.g. "soft deep swords read wildly."

On the other hand, I think we can all agree that without reading too far into either of the sentences, they are both meaningless-- semantically, they are both nonsense, despite their syntactic correctness. Then again, going a step farther we can milk meaning out of them, and I'm sure there's a Zen Koan hidden somewhere in one of those sentences if you know where to look. This search for an expression's meaning, oddly enough, captures the essence of combinatorics.

I'm going to take another detour. Let's look at algebra. Whatever level of algebra you have experience with, this should be true, although it may fall apart a little bit at the higher levels. When you have some statement such as "x+2=y" it means at any point you see y, you can replace it with x+2 and any time you see x+2, you can replace it with y. Equality in an algebraic sense is a rule of transformation. So when you get some long expression, such as "(x+2)*(x+2) + x-2", you can transform it to "y*y+y-2-2" From these transformation rules, you can show the equality of new expressions. So we can say that x*x+5*x+2 = x*x+4*x+4+x-2 = (x+2)*(x+2) + x-2 = y*y+y-2-2 = y*y-4. Notice that these transformations are syntactic changes. You are replacing one expression (which may be a variable, a literal [e.g. 1], or literals and variables combined by operators) with another expression. The semantics of your expression do not change: x+2 has the same value (semantics) as y. This is the idea behind algebraic manipulation: you never change the values, and so you show that the value of some expression whose value you know (e.g. x*x+5*x+2) is the same as the value of some expression whose value you want to know (e.g. y*y-4).

As I'm sure you've guessed, I'm going to assert that in combinatorics, we make semantic transformations. This may seem to be really dangerous at first: how does reinterpreting an expression give us something valuable? You can't just say that "x" means something different because you feel like it! So what's happening here?
To be precise, you don't actually make semantic transformations-- I lied. Instead, you're equating semantic interpretations of an expression. This may still seem problematic-- "colorless green ideas" can mean just about anything you want it to mean. The difference here is that math is significantly more precise. If you say x means y, you don't mean that x gives the emotionally impression that y does, you mean that under some reasonable interpretation of the system, x is interpreted as y. What constitutes a reasonable interpretation is a foundational issue that I'm not going to get into. So, "fine," you say. "I can accept that meaning is stronger in math than English; but what the hell are you talking about?"

Combinatorics works under the the assumption that mathematical expressions are representations of some sort of structural relationship-- some abstraction of a pattern or structure that is commonly found somewhere. And these expressions sometimes codify the same abstract structure. When we can find overlaps like these, we've found two things which are the same.

Ok. So, let's complete this thought with a classic theorem from the first week of any combinatorics course. Let C(n,k) be the number of ways of choosing k objects out of a set of n, without repetition, and where order doesn't matter-- so we want to know how many hands of k cards we can form out of a deck of n. Then C(n,0)+C(n,1)+...+C(n,n) = 2^n, whatever n happens to be.

The proof is as follows:

The right hand side: 2^n is obviously the number of bitstrings of length n: every bit is either 0 or 1 (2 choices) and we have n of them 2*2*...*2 = 2^n.

The left hand side: establish any ordering of the n objects. When we choose k elements, we mark the k we've chosen with a 1, and the rest with a 0. This gives us all bitstrings with k 1's. Now we sum this over all k, this gives us all bitstrings with any number of 1's of length n; in other words, all bitstrings. Since both the left hand side and the right hand side count the number of length n bitstrings, they are the same.

So, what are we doing? we're saying "what does this expression mean?" and finding something... and then finding another way of saying the same thing. It's a very weird way of doing math. A friend of mine once said combinatorial proofs almost seem more "subjective". There's a bit of truth in this.

One thing that combinatorics does is elucidate connections between expressions. Since you're looking at what an expression means, linking the two ideas comes naturally. An algebraic proof says "look you can use these interchangeably", but a combinatorial proof goes a step further, it says "these two concepts are actually the same." It provides a link in your mind between two things that aren't necessarily linked in an obvious way.

And this post happened because I was trying to find a combinatorial proof for C(n+1,2) = 1+2+..+n (which is trivial to prove algebraically).

Edit: The last sentence reminds me of trying to find meaning in "colorless green ideas sleep furiously." Perhaps there is no good reason they are equal. maybe it's a sentence which works, but there is no "deeper meaning". Is this possible? do mathematicians accept this possibility? I'm not sure if they do.

A Note to Most Christians (probably none of whom read this blog...)

Non-Christians-- especially non-theists and anti-theists are missing the point entirely. And it's our fault.

Well, they're getting the message we're sending, but we're not sending Jesus' message of Love and Truth; we're sending some butchered Pharisaic religion that is closer to the legalism Jesus fought against than what he fought for. We need to change that.

Here. Now.

Again I'm taking issue with a note in the Scofield Study Bible. On the whole, I like it, but it is very focused on the second advent. The note on Malachi 3:1-5 reads "[...] the next words [...] are nowhere quoted in the N.T. The reason is obviously that [...] the picture in vv. 2-5 of the Lord who suddenly comes to His temple (Hab. 2:20) is one of judgment, not of grace. Malachi [...] saw both advents of Messiah blended in one horizon, but did not see the separating interval described in Mt. 13 which followed the rejection of the King[.] The Church Age was even less in his vision [.] "My messenger" (v. 1) is John the Baptist; the "messenger of the covenant" is Christ in both of His advents, but with special reference to the events that are to follow his second coming."

I don't read the passage the same; and I think their reading, while not necessarily wrong, is liable to enforce the kind of attitude which Christians must fight, tooth and nail, if we are to be taken seriously, and if we want to glorify God; the attitude is the complacent attitude that God's tremendous work is to be saved for the second advent, so we can wait patiently and complacently, go to Church once a week, and seclude ourselves in little "Christian communities" and forget the outside world, and when Jesus comes back, "Hallelujah! We're saved!"

That's not good enough. I would go so far as to say that isn't Christianity; it isn't faith; consequently, it is not grounds for salvation. We are called by God to fight injustice. We are called to be like Him; to be of one will with Him. So if our Lord was "anointed to preach good news to the poor", we also are anointed to preach good news to the poor. We also have been sent to bind up the brokenhearted, to proclaim freedom for captives and a release from darkness for the prisoners. We are called to live as citizens of God's Kingdom, and to live God's justice, God's hope, and God's love. We cannot afford to be complacent when our faith, and the souls of those around us are at stake.

I'm not saying I don't often find myself being complacent: it's human nature. But we have to understand that we must at the very least strive to be above that. It isn't okay, although, thankfully, with God's Grace, it is acceptable; so long as there is genuine, true repentance.

Getting back to Malachi 3:1-5, the NIV reads "'See, I will send my messenger, who will prepare the way before me. Then suddenly the Lord you are seeking will come to his temple; the messenger of the covenant, whom you desire, will come' says the Lord Almighty.
"But who can endure the day of his coming? Who can stand when he appears? For he will be like a refiner's fire or a launderer's soap. He will sit as a refiner and purifier of silver; he will purify the Levites and refine them like gold and silver.
Then the Lord will have men who will bring offerings in righteousness, and the offerings of Judah and Jerusalem will be acceptable to the Lord, as in days gone by, as in former years.
"'So I will come near to you for judgment. I will be quick to testify against sorcerers, adulterers, and perjurers, against those who defraud laborers of their wages, who oppress the widows and the fatherless, and deprive aliens of justice, bud do not fear me,' says the Lord Almighty."
The middle paragraph, I assume, is where the Scofield editors get the impression that only the second coming is being discussed. But who among those who have been saved can say that the process of becoming saved does not burn? Isn't it nearly unbearable? Such warmth, such light, and after such numbing, cold darkness. And surely Christ's coming was shocking and "sudden" to the religious leaders, and surely it burned more than they could imagine; why else would they have him killed, despite the governor's doubts?
And the rest "I will send my messenger" ... "the Lord you are seeking will come to his temple" ... "Then the Lord will have men who will bring offerings in righteousness, and the offerings of Judah and Jerusalem will be acceptable to the Lord" ... "I will be quick to testify against sorcerers, adulterers, and perjurers, against those who defraud laborers of their wages, who oppress the widows and the fatherless, and deprive aliens of justice, bud do not fear me." Does that not sound like the call for justice that Christ placed on our hearts, that Christ made our mission?

We should be moving, acting-- here; now. And not waiting complacently. Hope does not sit by idly, hope acts and strives for the satisfaction of promises.

This is important... NCSoft is ripping off worlds.com

It appears video game company NCSoft has been making unauthorized use of a patent by worlds.com-- they have been maintaining a highly scalable architecture for a three-dimensional graphical, multi-user, interactive virtual world system. I am frankly disgusted that they would resort to stealing technology from anyone, no less, a reputable pioneer in the development of 3d internet technology. I hope they get what's coming to them...

*****
Seriously, though, what the hell? What is worlds.com? (Some random company that no one would know about if it weren't for this lawsuit) Why has no one heard of them? (Because they haven't done anything). It's infuriating that they would actually seek an injunction against a company for creating "a highly scalable architecture for a three-dimensional graphical, multi-user, interactive virtual world system." I think all game makers should be paying royalties to Atari, for creating "an imaginative system of interactive electronic entertainment" which includes a "software application to be installed on 'client' machines." You wrote a revenge novel? You owe money to the Dumas estate; you're capitalizing on his idea.

The SCO vs [whole free software community] cases were more specific than this, and SCO was standing on something that resembles ground, and they still lost. This suit is absurd. Worlds is scared about the economy, and sees the money pouring in to the MMO market and wants to sustain their livelihood, so they're trying to tap into that fund. It's shameless and awful. Is a lawsuit really what the industry (not to mention the economy) needs right now? 3d mmos have been out for 10 years, are you that dense that you are just now realizing they exist? Or are you wicked and conniving, trying to get some cash out of frivolous lawsuits? Or are you just desperate?

More importantly, who authorizes such bullshit patents? What jackass in the patent office is so busy daydreaming about being the next Einstein that he can't read through the crap and realize they've patented a genre. I need to talk to a patent lawyer here, but I just got a great idea to patent a scalable system of chemical combinations designed to alleviate symptoms of certain diseases. Of course, in a "preferred embodiment", the chemicals would interact with the patient's vital systems and each chemical would correct an abnormality in said systems. I can totally use the same patent, and just reword it a bit. Or would that be copyright infringement?

Why I don't think I'll read "The God Delusion"

There's a book which has been out for 2 years by Richard Dawkins called The God Delusion. It is, as its name implies, an attack on God. It is, in short, a polemic. I feel that I should read it for the sake of intellectual honesty, if nothing else. But the more I read about it, and the more short excerpts I read, and the more I hear/read from Dawkins, the less I care. And here's why.

Dawkins quite clearly rejects out of hand the possibility that any other world view than his is right. When I say "any other worldview" I don't mean the possibility of God-- that's what he's arguing against-- but any philosophical starting point besides logical positivism. He is a strict materialist, and a logical positivist, and everything else is flatly not worth mentioning.

He makes, I won't doubt (at least until I read his book... if I read it) a convincing argument that a l.p. framework implies that God is a god of the gaps, and that those gaps will quickly disappear, and God with them. But by doing this and only this, he sidesteps the issue completely. He misses the epistemology, which is the most important part in deciding the possibility of God. You cannot tell someone they have come to a false (moreover delusional) conclusion when you refuse to discuss the framework by which they establish truth. The utter arrogance and ignorance of trying to tell me I'm delusional without even so much as mentioning my epistemological groundings makes it impossible for me to take anything Dawkins says seriously.

He (sort of) rebuts such arguments in the preface with "Do you have to read up on leprechology before disbelieving in leprechauns?" This is a fantastic point, but few people are asking him to go through a detailed study of the theology of Aquinas, Luther, Calvin, Lewis and Chesterton to argue that God does not exist. What we are asking is for him to discuss their epistemological basis, rather than a priori tossing them aside. To quote Terry Eagleton "What, one wonders, are Dawkins’s views on the epistemological differences between Aquinas and Duns Scotus? Has he read Eriugena on subjectivity, Rahner on grace or Moltmann on hope? Has he even heard of them?" The question is not about theology, but about philosophy.

Let me expand upon that point; I don't care what Dawkins has to say about scriptural justifiability of The City of God, Fear and Trembling or Mere Christianity. I care about what he as to say about the way Augustine, Kierkegaard and Lewis establish Truth. What do they consider to be evidence of the truth of a statement? What grounds do they use to justify the existence and character of God? Why is this wrong?

Moving past his naive dismissal of several thousand years of epistemology, his caricature of religion shows how little he has even attempted to understand the religious mind. There is far too much to say on this topic, and I could hardly do it justice, so I will limit myself to a one sentence summary of his feelings on the morality of religion: He finds it to be dangerous and evil. If religion is defined to be "irrational, self-righteous, hate-filled zeal", I agree wholeheartedly. But in his religious (in that sense of the word) intolerance he refuses to accept that the source of such religion can be anything besides religion as it is normally defined and he also refuses to accept that religion (as it is normally defined) can create anything apart from such closed-mindedness.

By so vehemently rejecting everything that isn't is worldview, he is making the most absurd straw-man of himself. He claims that atheism will lead to a more peaceful society overall, but he proves himself, through his self-righteous intolerance, to be a poor example of this "truth". So, I'm not going to read The God Delusion unless someone convinces me that his argument does discuss the epistemological "failings" of a religious view, and that he doesn't caricature religion as I claim...

****
My first point reminds me of a quick exchange that was made a while ago... I tend to be bad at "arguing" points, so this is my esprit d'escalier. A friend of mine (who is also very logical positivist, and can't understand other worldviews-- although he tries, at least) made a comment about science solving some sort of subtle and difficult to determine system. Another friend responded with "that's assuming the scientific method is infallible, which it's not." to which the first friend responded "If it were possible to get machines, which cannot make the same mistakes we do, to do it, it would be." Before a rebuttal could be made (or at least before one was made) we got distracted with something else.

Besides the "you're assuming a logical positive, blah, blah..." I realized that the truth of this statement requires that the universe be objectively observable from within the universe-- otherwise there will always be irreconcilable error in any measurement, hence, science is limited. Given our current understanding of the universe, objective observability is absolutely impossible: "Einstein says so." Any observation can only be made with respect to a given object, and at a high enough resolution, everything about that observation is different for any other object.
Further, if we accept a logical positivist view on the universe, and hence, a Fregean view on math, it makes sense that the universe is governed by some mathematical system. I'm getting to a point I've made before, but.. If the universe is governed by a mathematical system, then we must accept Tarski's undefinability theorem and Gödel's incompleteness theorems. In other words, there are limits to how much we can mechanically discover about the universe. Hence, science has limits.

Developing in "impractical" languages

So... functional languages, in the case of ones I know, Scheme and Haskell, are often called "impractical" for real applications. Due to the small libraries, this is mostly true of scheme, but it is only because scheme libraries are small... It is not true of CommonLisp, or Haskell, or OCaml, or ...

The most common argument is that they run slower. This falls flat for OCaml, which outpaces basically everything (that means you, imperative language) except C; also, CL is one of the faster languages around. But everywhere I look in relation to Haskell has some sort of argument about it being "slow and impractical".

Let's look at the cost ($$) of developing and running a piece of software written in C vs one in Haskell. Also let's assume that it is computationally expensive (uses a lot of CPU power).

Now, everywhere I've looked, suggests developing in functional languages is at least 2 times (actually closer to 3 or 4 times...) as fast as developing in their imperative counterparts. But! We'll give C the benefit of the doubt, and say that developing in Haskell takes 2/3t (e.g. if a C program takes 3 months to develop, it will take 2 months to develop it in Haskell).

Now, we'll continue with a conservative estimate of $40000 a year for a programmer. For a job which requires a BS in CS and "several years" of experience... this is a modest (and, quite frankly, bad) pay... but programmers love their jobs, right?

Now, a decent (but not huge) project is going to take, say, 9 months for 5 programmers to write in C. So 6 months in Haskell. This means the development cost of the C program is 5*40000*(3/4) = $150000. The Haskell program? 5*40000*(1/2) = $100000. Obviously, since we're looking at 2/3 the cost.
Now, we've just saved ourselves $50000. That's more than the salary for a programmer for a year!

But! We've got to take into account the extra amount of computation required by the Haskell program. Since the differences are constant (not asymptotic), and Haskell is ~3 times more "expensive" than C, we're looking at just getting a better computer here... We'll say one that's "twice as good" (whatever that means), which isn't quite enough, but we've been giving C the benefit of the doubt this whole time...

So, getting a computer that's "twice" as good is going to cost the average person less than $1000 extra-- $150 for RAM, $150 for a CPU and $200-$300 for video card: less than $600. Let's say $750.

So, in order for the imperatave program to be more efficient, all around, economically, there need to be roughly 50000/750 = 75 copies...
Hmm... that's not too much, now, is it?

Giving programmers more money (hurray!) increases this number some, but not all that much... However, there are a few things to note:

(1)In reality, every study/anecdote suggests about 2x speed with functional development. This means we have ourselves $100000, so 150 copies... still small...

(2)Giving programmers $50000 a year (on average... this includes project managers, etc) means an extra $25000 (given (1), above)

(3)The cost of hiring good programmers is not decreasing very fast... the cost of upgrading computers is. So in 5 years, this whole thing is going to be stupid.

(4)Most substantial programs take closer to 10-20 people 1 to 2 years (in C). Given (1) and (2), that's at least 400000 (taking 15 for 1.5 years, that's 1.125Mil). In Haskell? For 15 people it will take .75 years, so that's 562500. We've saved just under one million. So we can now sell almost 1000 copies... still not much.

(5)This is Haskell vs C. In reality, development is done in a combination of C and C++. OCaml performs only moderately slower than C (and faster than C++), and CL is only slightly slower than C++. So, working in OCaml will save about the same amount of time, and won't cost much (any) more to run; developing in Lisp will only cost a tiny bit more to run, and won't be much (if any) more than OCaml... especially with Macros, and CLOS.

(6)There are very, very few applications where performance matters that much... Rendering is just about the only common task. So the "It's too slow" argument is dumb anyway.


My point is: People see that Functional Languages are experimental (theoretical) hotbeds, and say "Oh, they must only be good for language theory"... This is not the case. They are, mostly, only a tiny bit slower to run, and are significantly faster to develop in...
Also, pugs, and darcs

Edit: So, I got my orders mixed up... (Actually, I was looking at an incomplete ranking when I said OCaml and Lisp are fast). The best way to look at things is: The Computer Language Shootout! Look at rankings... play around with what does what... etc.

Euler and Haskell

I just started learning Haskell, which is a fun, and slightly ridiculous language-- it seems to be what happens when you let mathematicians design a programming language without supervision: It's too clever and uses way too much graduate level theory. Any language which makes frequent use of monads, functors and has a wikibook describing its relation to category theory is the result of an evil genius (or several, to be precise).

Anyway, I'm using Project Euler to learn it, at Anne's polite not-actually-a- suggestion. Which is to say, she brought up Project Euler, and I said "Oh! I can learn Haskell!" It's working rather well, and I recommend it.