2017-06-04 - Computers were Created by Us
The problem with a lot of scientific disciplines is that they are trying to understand and rationalize the universe and the universe has very little interest in being understood. Every time we think we have it figured out something new comes up and turns everything upside down. Isaac Newton figured he had a good handle on the whole gravity thing. He said it was the attraction between objects with mass. That worked rather well to explain the orbits of the planets. Albert Einstein thought about it and decided that didn't quite work. He figured gravity was actually just an imaginary force caused by the curving of space-time due to massive objects. Now physicists are working to come up with a quantized model of gravity which fits into our current understanding of quantum mechanics. The more we learn about the universe the more complicated our models become.
Computer science on the other hand is about understanding things we ourselves have built. Computers are as simple as we want them to be because we built them to be that way. There's also really handy manuals and diagrams to explain how things work. If worse comes to worse and you still don't understand something there's a chance you can track down the person who's responsible for it and ask them why.
The benefit of this difference is that computer science is a lot more accessible than other fields. We are in control of every concept and idea which exists in computer science. We decide how things work. Now that's not to say computer scientists can't be weird and come up with weird concepts. It's just that there's usually an easier to find explanation. Instead of questions like "Why can particles jump through walls?" we have questions like "Why are the keys on a keyboard arranged the way they are?" which are a lot easier to answer.
This is one of the reasons I find working with computers to be appealing. I know that whatever I am trying to figure out it made sense to someone. If they can understand it enough to build it then I can understand it well enough to use it.
2017-05-08 - Parts of Speech: Verbs
Last time I said we were going to look at pronouns next, but I've decided it's better to look at verbs first. Verbs usually have a subject which is a noun identifying what is doing the verb. Verbs can also have an object which is a noun identifying what the verb is being done against. The subject/object difference has the most impact on pronouns which is why I wanted to mention verbs first.
Verbs are action words. They describe what something is doing. Words like "walk", "think", and "imagine" are verbs. Verbs are one of the most complicated parts of speech and they can have many forms. because of this the inflections of a verb are special and called conjugations.
Verb forms are constructed from several principal parts. The infinitive is the base form of a verb. The past participle is formed by adding -ed to the base form and the present participle is formed by adding -ing to the base form. A gerund is the form of a verb when used as a noun and usually matches the infinitive.
Verbs are mainly conjugated to indicate the time period over which the action is occurring. Tense describes the point in time at which the action is happening. Past tense means an action occurred in the past, present tense means an action is occurring in the present and future tense means it is occurring in the future.
Aspect is used to indicate when the action started and ended. Simple aspect indicates an action occurring regularly in the time frame indicated by its tense. Perfect aspect indicates an action starting before the time frame indicated by its tense but completed by that time. Progressive aspect indicates an action started before and continuing after the time frame indicated by its tense. Perfect Progressive aspect indicates an action started before but ending at the time frame indicated by its tense. Aspects can be thought of as modifications of tenses and so the term tense is sometimes used to refer to a specific combination of tense and aspect. The following list shows tenses and examples.
Tense | Example | Part | Description |
---|---|---|---|
Simple Past | I walked | Past Participle | An action occurred in the past |
Past Perfect | I had walked | Past Participle | An action occurred and ended before a specific point in the past |
Past Progressive | I was walking | Present Participle | An action was occurring at a specific point in the past |
Past Perfect Progressive | I had been walking | Present Participle | An action was occurring and had just stopped at a specific point in the past |
Simple Present | I walk | Infinitive | An action occurs in the present |
Present Perfect | I have walked | Past Participle | An action occurred and ended before the present |
Present Progressive | I am walking | Present Participle | An action is occurring in the present |
Present Perfect Progressive | I have been walking | Present Participle | An action was occurring and had just stopped before the present |
Simple Future | I will walk | Infinitive | An action will occur in the future |
Future Perfect | I will have walked | Past Participle | An action occurred in the future and ended before a specific point in the future |
Future Progressive | I will be walking | Present Participle | An action will be occurring at a specific point in the future |
Future Perfect Progressive | I will have been walking | Present Participle | An action will have been occurring and will have stopped just before a specific point in the future |
Note that not all verbs follow the rules. Irregular verbs are those which have unusual participles or tense forms. Tenses themselves are also used in a variety of ways which makes it difficult to give them exact definitions. We may talk more about verbs at a later date since they are one of the most complicated parts of language.
Next time we will talk about pronouns, for real this time.
2017-03-18 - In IL: Prize Calculator (switch-2)
Last time we looked at a switch statement in C# which was implemented in IL by the switch instruction. The IL switch instruction is a lot more restrictive than the C# switch statement, for example the instruction expects its options to be continuous and only supports integers. The statement on the other hand can have large gaps between its options and also supports strings. So what happens when we have a switch statement that can't easily be implemented using the instruction?
The following program determines a user's prize based on a number. Only specific numbers get prizes and there's large gaps between winning numbers.
Their are 12 options with a range of 3009. That would require the switch instruction to have an array with 3009 addresses where 2997 of them point to the default case. Let's see what the compiler generates for us.
The compiler generated a ton of branching statements but no switch instructions. So what are those branching instructions doing? Let's map them out.
- Line 68: Branch if Position > 1054
- Line 104: Branch if Position > 2513
- Line 122: Branch if Position = 2668
- Line 171: Print "You win a toque"
- Line 126: Branch if Position = 2998
- Line 175: Print "You win a pot of gold"
- Line 130: Branch if Position = 3054
- Line 179: Print "You win a mouse"
- Line 132: Branch
- Line 183: Print "You win nothing"
- Line 122: Branch if Position = 2668
- Line 108: Branch if Position = 2045
- Line 159: Print "You win a carrot"
- Line 112: Branch if Position = 2012
- Line 163: Print "You win a teddy bear"
- Line 116: Branch if Position = 2513
- Line 167: Print "You win a double cheeseburger"
- Line 118: Branch
- Line 183: Print "You win nothing"
- Line 104: Branch if Position > 2513
- Line 72: Branch if Position > 513
- Line 90: Branch if Position = 668
- Line 147: Print "You win a hat"
- Line 94: Branch if Position = 998
- Line 151: Print "You win a potted plant"
- Line 98: Branch if Position = 1054
- Line 155: Print "You win a house"
- Line 100: Branch
- Line 183: Print "You win nothing"
- Line 90: Branch if Position = 668
- Line 76: Branch if Position = 45
- Line 135: Print "You win a car"
- Line 80: Branch if Position = 102
- Line 139: Print "You win a TV"
- Line 84: Branch if Position = 513
- Line 143: Print "You win a cheeseburger"
- Line 86: Branch
- Line 183: Print "You win nothing"
It starts by branching if the number is greater than 1054. This is the middle option of our switch statement. If it is greater than 1054 it then branches if the value is greater than 2513, else it continues on and branches if the value is greater than 513. 2513 is the middle option of the block greater than 1054 and 513 is the middle option of the block less than or equal to 1054. You may recognize this process of repeatedly dividing the options in half and checking if the value is greater than or less than the half way value as binary search. Instead of checking every value it checks ranges and focuses in on the value. It only checks for equality when it gets down to a few remaining options. This way it only takes 5 comparisons to get to the largest value of 3054 instead of 12. Now let's go a step further and see what happens if we use strings instead of integers.
As you can see this program is similar to the first except it uses a string variable and string case statements. Let's see what it compiles into.
That's follows the same basic flows as the integer case but with a few differences. Firstly on line 68 the compiler used an internal function to generate a hash value for the string which is a unsigned integer and then it compares the computed hash against the pre-computed hashes for the string cases. Secondly instead of branching directly to the print statements it branches to a call to the string's equality function. This is to ensure that string actually matches the desired value and doesn't just have the same hash value.
Next time we will look at the Visual Basic .NET Select statement and see how it handles even more complicated cases.
2017-02-26 - Computer Engineering is Weird
Computer engineering is weird compared to other engineering disciplines. Engineers mainly work on the design part of a project. They come up with specifications that get approved by the client and then sealed by the engineer to indicate that they are ready to be used. Then the plans are given to other people who construct the project under the supervision of the engineer. In computer engineering there is rarely a separate build time or a complete specification. This is largely because programming is both harder and easier than other disciplines.
Building a program is a fair bit easier than building other things. Maybe not in terms of complexity but at least in terms of resources and personnel. You need carpenters, electricians, plumbers, painters and many other trades people along with wood, wiring, piping, and heavy equipment to build a house. In contrast you just need programmers and computers to build a program. Programming teams also tend to be a lot smaller compared to construction crews.
On the other hand designing a program can be quite complicated. There tends to be a large number of distinct parts of a program which can interact with each other in a variety of ways. These parts can also be created and destroyed many times throughout the life-cycle of the application. Modeling these details in a simple way can be almost impossible. There's also the problem that the design and implementation of a program can be very similar. A specification is a set of instructions that describes how something should be built but a program is also a set of instructions. So it becomes difficult to write a specification that is detailed enough to be useful but not too detailed that it's basically the program written in another language.
Because of the ease of building a program and the comparable difficulty of designing teams will often skip the formal specification in favour of just building the program and the program becomes its own specification. Since the main focus is on building the project there's no need for a separate design group or a formal approval processes. Specifications are going to be created and used by the same people and change as the program is developed and details get fleshed out.
Now likely computer engineering would benefit from having more formal specification and approval processes but it requires tools specificity designed to make it practical to do so.