These notes provide a guide to some of the things that you might find useful before you start writing your own programs. It's possible to learn programming without knowing any of what follows and it's quite normal to learn by picking up new knowledge as you go along. As with many other fields lots of things don't make complete sense until you know some other stuff too and so it is with programming. Which comes first? For those people that want to learn some basic stuff first...
'Computer architecture' refers to the overall design of computer hardware. In particular, a computer has some key pieces of hardware that are organised in a specific way so that it can execute instructions:
This is a basic model of how a computer works.
| Hardware | Building a PC Part 1 | Building a PC Part 2 |
| Building a PC Part 3 | CPU |
Web site: How a PC works
Tasks
List and describe the function of the parts of hardware that make up a modern PC, including input, output, storage and processing. You should be able to get at least 10.
In a spreadsheet:
List the components of three types of a PC: could be for business, gaming and a server
List the software needed for a working PC: OS, applications, security, internet connection
Find examples of computer components on web sites; write the name of the item in one column followed by manufacturer, component type, price. Add the software and other items you require. Calculate the total price it costs to build a PC. Add a percentage profit margin to get a sale price (e.g. 20%). Find the profit in £ per PC built. Enter sales totals for each PC in ratio 3:2:1 for business, gaming and server PCs. Find the number of PCs you need to sell to make £40,000 total profit.
| Choose a video card | 3D graphics (UCB CS10) | Rango Characters |
Inside a computer all data are in binary form: numbers, which is why we call computers digital.
Details here
Computers are machines that run or execute instructions. An instruction is a command to do something. You may have learned about commands when studying foreign languages where the term imperative mood is used, as in the following example (any excuse to show a clip from one of the funniest films ever):
The imperative: Romanes Eunt Domus
Computers are even dumber than Brian! Computer instructions are limited to operations like LOAD, STORE, ADD, SUBTRACT, COMPARE and JUMP. At the lowest level that we humans can see a computer instruction looks something like this:
LOAD #20 //load something in the computer with number 20
At machine level this instruction is a number of binary digits; the binary digits are translated into a small number of steps that involve opening and closing 'gates' or transistors inside the computer that produce the desired result. Computers have no understanding of what they are doing, they just obey blindly.
Dumb or not, the programming language Python is eponymous: named after Monty Python, creators of Brian; Python reference works use spam and eggs as sample variable names (another excuse to look at a funny sketch: this one gave the us the name for junk email - can you see why?)
Python is just one example of a family of programming languages called the imperative languages, so-called because they tell the computer what to do (add, compare, load, store and so on).
We can find out more about this level of computers by looking at the Little Man Computer. Details here.
List ten instructions that you can give to a computer, a person or an animal.
Some people use 'data' as the plural of datum and say"data are" rather than "data is".
Data are pieces of information that computing machines process in some way. We say "computing machines" rather than "computer" here because it is not only computers that compute: brains do it too.
When brains computer they process data or information like computers do, though not in the same way. Computation takes place in the natural world:
Computers take data such as input from a user, from a file or from a sensor. There is a lot of interest in the similarities and differences between brains and computers. Information science and computation reach out into many more disciplines than just computer science.
Film: How is Your Brain Wired?
Film: New Brain Agenda
Film: DNA Visualised
Film: SatNav vs Cabbie
While humans take in information about the weather or food or terrain, computers deal with numbers: we call them digital computers because everything inside them has been converted to numbers. This makes them different to even the simplest organic brain, which relies on chemical transmitters and complex webs of neurons to make sense of sensory information.
Computers execute instructions that operate on data. We generally divide data into a range of types, the most basic of which are numbers and characters. Numbers divide into integers and fractional numbers and characters are defined as either single ('a') or grouped into 'strings' ('David'). Another basic data type in programming is Boolean, which has two states, true and false.
List 10 examples of data items that can be processed by a computer.
Hans Rosling: No More Boring Data (TED Talk)
A variable in a program is something that varies: its value can change according to user input, file input or input from something like a sensor. Many variables are encountered in everyday life e.g. daily temperature, prices on the stock exchange, fuel in a tank. Variables in programming are generally defined with a specific type such as integer or string, though this does depend on the programming language: Pascal, Java and C, for example, are strongly typed so an integer can never have a fractional part or be used as a character while PHP and Javascript are loosely typed and the types of variables is fluid.
A constant is a property that does not change e.g. pi=3.14159. Constants are used when we know that something won't change in the course of a program.
Name five variables encountered in everyday life and state what type of values they take (numeric, string, Boolean).
Name five constants encountered in everyday life and state what type of values they take (numeric, string, Boolean).
You often get more than one instruction at a time: "sit down and shut up!" If there is more than one instruction then we say that the instructions form a sequence. This is a basic feature of computer programs, doing one thing after another, for example LOAD #20; ADD #5 (answer = 25).
When you look at the headings of this page you can see that they form a sequence, as do the chapters in a book, the acts and scenes in a play and the tracks on a CD. Perhaps sequences are less important in the modern world: movie directors often reorganise books, starting with the end and presenting the story as a series of puzzles that only make sense when all the action has been removed (Emily Bronte did this rather well in 1847 and clearly knew how to scramble a sequence into a good story).
Our brains remember the various fragments of the story and assemble them into the sequence that lets us understand it as a whole. In music CD players and music streaming allow us to reorganise sequences of songs to suit our own tastes (Pink Floyd claim that their work should be heard as complete pieces, not separately and they use this as a reason for not allowing their music to be streamed; but does listening to this undermine artistic integrity?)
Give 10 examples of sequences that are found in either writing or everyday life.
Brian was told to write out the correct version of his slogan one hundred times - an ironic tribute to the Latin teachers of yore who would punish misdemeanours such as incorrect declension with "lines". To some extent the rules of Latin have been replaced by a different, more modern agenda: the '21st century skills' of collaboration, communication, creativity, critical thinking, problem solving and self direction.
A modern pupil, at least one schooled in computer programming, would ask if he could produce the lines with a line or two of code: we call this "thinking computationally" or thinking about how the computer would do it. Some say that computer programming is the 'new Latin', a lingua franca that is known by a wide range of educated people.
Say that a program wants to read a number of numerical data values and find their sum. The steps for this:
More formally:
We can convert this to a flowchart, which shows us another way of thinking computationally.
In a high level language we can do a loop more concisely:
set total=0
set counter=0
while not end of list do
add number[counter] to total
Or:
for counter = 1 to length(list) do
total = total + number[counter]
Scratch and BYOB provide a rich set of loop structures. The three main loop types are:
repeat <statements> until <condition> - do one or more things until a condition is met (Scratch: forever as well as repeat)
while <condition> do <statements> - test the condition then do things if it is met (Scratch: forever if)
for counter := 1 to 10 do <statements> - do one or more things a specific number of times (Scratch: repeat n times)
Give five examples of loops or repetitions of the same thing from everyday life.
The third and final technique is control, which refers to the computational action of making a decision. It's hard to go far in computer programming without control: as we saw in the last section, the simple act of adding up a series of numbers requires the program to check whether it has reached the end of the list of numbers.
The most common control structure in a program is the if..then..else structure, for example:
if Brian has done wrong then he must be punished, otherwise he can have a reward
or:
if up-arrow-key is pressed then move up screen 5 pixels
or:
if x-position > 200 then turn around else move 5 pixels right
or:
if button is pressed and sprite-1 is touching sprite-2 then sprite-2 is destroyed
Write out ten sentences that use an if..then statement to introduce a decision.
Write out five sentences that use and if..then..else statement to provide two possible outcomes to a decision.
Another way of making a decision is to act on the value of an item chosen from a list. The items in the list should be part of an ordered set such as the integers from 1 to 5 or the letters from a to g. Many languages then provide the case statement to provide alternative courses of action for each choice. This is often used with menus where the choices are given a letter or number:
Enter your choice from the following:
case choice of:
1 : play_computer
2 : play_human
3 : play_self
4 : exit
end;
Write out three situations where you have multiple choices of actions.
In programming the mathematical symbols +, -, x and / are called operators; the things that operators work on are called operands (which, if you enjoyed our earlier study of the imperative, is the gerund of the Latin operare; an operand is something that is operated on; learning about operands may help you remember what a gerund is).
Thus in the expression 2 + 2 there are two operands and one operator. Other operators include mod or modulus or the remainder after integer division, as in 12 mod 5 = 2. The mod operator appears as % in many languages.
Some languages include an operator for power but others do not. If a language does not include a power operator you have to write your own.
Mathematical operations are basic to computers as they were first seen as calculating machines and as replacements for the human computers that preceded them. This might be the moment for an account of the development of computers.
All the operators considered so far are binary in the sense that they operate on two operands; plus and minus may also be unary, as in +5 or -5.
We often give operands names so that they are more abstract and can take on any value in a valid range.
Give ten examples of things from everyday life that vary and can be given names.
Assignment is such a basic operation in programming that it is easy to take it for granted. Assignment is where you link a value to a variable or constant, for example:
x = 1
first_name="David"
found:=false
In some languages we can read the value of a variable from the user's keyboard input and assign it to a variable in the same statement:
last_name = ask "What is your last name?"
But in other languages this is not possible:
writeln('Enter your last name);
readln (last_name);
As well as arithmetic, which is pretty useful, computers also perform a particular type of logic which is largely derived from the work of George Boole (1816-1864). Boolean logic is distinct because it is based on the possibility of just two outcomes for each proposition: true or false. This translates readily into the binary number system used by computers and allows computers to perform many of their actions, in particular the control and iterative operations described above.
The Boolean operators are used in Boolean expressions and include:
= : equals e.g. if x = 0 then... (does x equal zero?)
> : greater than e.g. if x > 10 then... (is x greater than 10?)
< : less than e.g. if x < 10 then...
>= : greater than or equal to e.g. in if x >= 10 then...
<= : less than or equal to e.g. in if x <= 10 then...
<> : not equal to (can also be !=) e.g. if x <> 1 then...
not : inverts the result e.g. if not (x > 10) then... - this means the same as if x <= 10 then...
or: links two or more expressions: the output is true if any part is true e.g. if (x > y) or (y > 10) then... - if either x or y is > 10 then
and: links two or more expressions: the output is true only if both or all parts are true e.g. if button is pressed and sprite-1 is touching sprite-2 then sprite-2 is destroyed
Give five examples of statements that include the not operator.
Give five examples of statements from everyday life that include two or more expressions linked by Boolean or.
Give five examples of statements from everyday life that include two or more expressions linked by Boolean and.
Data can be classified as scalar or structured. A scalar variable can take on just one value at a time, for example 'last name' can have just one value - it wouldn't make sense to put two names into it. A data structure, on the other hand, can have more than one value because there is more than one place to store them.
A shopping list, for example, usually has more than one item in it and it can certainly store more than one thing. In fact the list is a fundamental data structure in programming and is included as the main data structure available in Scratch.
Many programming languages include the array as a way of storing more than one item of the same type such as a list of names. Arrays have properties such as an index to each item so that the position of individual items can be tracked and a size limit. The record structure is available in some languages to store items of different types e.g. name (string) and date of birth (3 numbers).
Arrays tend to have a fixed size, which makes them inflexible for some applications. Some types of data structure are dynamic and can expand or contract while a program is running. Lists can be implemented using pointers to make linked lists and pointers can be used to make more complex structures such as queues and trees.
Give five examples of everyday objects that are structured in some way - they could be physical objects or on paper or some other media.
It probably helps, before learning to program, to have some practice at solving puzzles and problems. Puzzles and problems can be solved without reference to programming but to implement a solution using a computer program will require detailed knowledge of program and data structures, which is why we are considering some of those things before we attempt real programming.
Details here.
Algorithms provide a formal account of the solution to a problem. Solving problems and defining the algorithms is good practice for solving and documenting computer programs. It is tempting to start writing code before understanding the problem that the program will solve but this often leads to failure. It is important to provide documentation of algorithms so that others can understand, use and extend them.
Details here.
The ability to break problems into smaller ones is a key part of 'computational thinking'. Programmers do this all the time, sometimes by writing functions or procedures and sometimes by writing classes or event handlers: these are all small units of code that can be assembled into bigger ones. The process of breaking problems into sub-problems is sometimes called 'modularisation' or breaking into modules.
Modules can be linked together to solve the bigger problem. Some of the modules may exist already in code libraries so the programmer does not need to solve these and he can concentrate on what is new or difficult in the current project. Breaking a problem into modules is also called the 'top-down' approach and this can be represented in a hierarchy diagram with the most general level at the top and the more specific elements at the bottom. Modularisation is also a form of abstraction as problems are recognised and given names but their details are left undefined until some later stage.
The opposite approach to 'top-down' is 'bottom-up', where problems are solved by starting with the detail at the bottom and working up to the finished solution. Both these approaches to problem solving have application outside of computing and programming.
Another important feature of modules is that, when coded, they can be used as often as required without having to repeat the code itself: they can be 'called' when needed. Thus a module that opens a file or sorts an array or calculates a square root can be used over and over again and does not have to be rewritten or copied multiple times into the code. Modules can be assembled into libraries and included in a program so that the code is ready to use. In literature, art or music one does not expect an author, artist or composer to copy chunks of previous works into new ones (though they may 'quote' small bits). In programming the opposite applies: programmers are free to include code (subject to copyright) that they or someone else already wrote. As they say, why re-invent the wheel? The Open Source coding movement encourages this.
(See here for an example of where a political speech was copied: Joe Biden copied a speech by Neil Kinnock almost word for word and, as a result of the furore that followed, lost the democratic nomination for president in 1988. Biden's career was renewed when Barack Obama chose him as running mate for Vice President in 2008. A programmer would not suffer the same consequences for copying code, perhaps because code is largely unseen.)
Who owns a dog? What's the first thing you think of when you see a dog?
There are at least six layers of abstraction when thinking about dogs: write them down in order of generality.
This is called abstraction by generalisation and it is found in biological taxonomy.
How many layers of abstraction can you think of for cars? Write them down.
Humans use abstraction in language all the time, going from the general to the particular and back to the general without thinking much about it. You have probably learned about abstract nouns: no prizes for guessing that that comes into abstraction too. Write down 10 abstract nouns and concrete examples of each one.
We just heard about two levels of a computer: the level of the transistors that make up the circuitry where the most basic instructions are executed; and the level of machine code where humans can issue machine level commands (through programs) such as LOAD and STORE. Where there are two or more levels of understanding we can use the term abstraction as one is a more abstract or general view than the other: the layer of LOAD and STORE is more abstract than that of transistors.
There are further layers of abstraction in computing; one scheme of abstraction is that of programming languages:
Abstraction is also used when considering interfaces such as the GUI (graphical user interface). A GUI allows a computer user to interact with the computer through symbols such as icons and menus and to use more than one program at a time in separate windows; a pointer, often controlled by a mouse, allows the user to select and manipulate these objects. The four parts of a GUI listed here spell the term WIMP. Before GUIs were developed users were more likely to use a command line interface or CLI - there's that word 'command' again.
If you ask someone how to drive a car they will probably talk about the steering wheel, the accelerator and break pedals and the clutch and gearstick. They are unlikely to start with how an engine or gearbox works and this too is a form of abstraction: car manufacturers have provided a layer of abstraction above the mechanical parts that allows humans to drive a car in a way that makes sense to them.
Abstraction is one of the skills and techniques included in what has become known as 'computational thinking'. Computational thinking is almost any form of thought that is derived from computation, which is to say that it is derived from the design and operation of computers.
| CT in Education | Computational Neuroscience | Neuroscience & Computing |
Name five practices that are included in computational thinking.
You probably think you know what a computer is: a collection of hardware and software, right? Up to the 1930s computers were people who computed. There were some mechanical machines that computed, that is performed calculations that were tedious and slow for humans to perform. Here are some key people and dates in the development of computers:
Babbage is credited with one of the first designs for a mechanical computer:
"In 1812 he was sitting in his rooms in the Analytical Society looking at a table of logarithms, which he knew to be full of mistakes, when the idea occurred to him of computing all tabular functions by machinery. The French government had produced several tables by a new method. Three or four of their mathematicians decided how to compute the tables, half a dozen more broke down the operations into simple stages, and the work itself, which was restricted to addition and subtraction, was done by eighty computers who knew only these two arithmetical processes. Here, for the first time, mass production was applied to arithmetic, and Babbage was seized by the idea that the labours of the unskilled computers could be taken over completely by machinery which would be quicker and more reliable." (see Wikipedia)
Babbage designed the Analytical Engine and then the Difference Engine, neither of which were completed in his lifetime but a working model of Difference Engine Number 2 was completed in 1991 and can be seen at the Science Museum. Notice that even 200 hundred years ago information science was an important resource in economic development and international rivalries.
Alan Turing devised a theoretical, imaginary computer on paper and did not plan to build a working machine, though this has subsequently been done - see here. Turing stumbled upon a definition of a computing machine whilst working on a mathematical problem: the 'Entscheidungsproblem' or 'decision problem' of David Hilbert. Turing's work on this problem is technical but the gist of it is:
Turing was so engaged with the mathematics that he did not realise that he had devised a blueprint for the electronic computer that would appear a few years later: a universal machine that would run any valid Turing machine; in the modern world computers or universal machines, are running valid programs to process words, sounds, images and much else besides.
Claude Shannon was another key figure in the development of computing for it was he who, at the age of 21, first recognised (in his master's thesis in 1937) that Boolean logic could be performed electronically by binary devices such as valves. Some have called this the most important master's thesis of the 20th century. This led directly to the development of the electronic computer because it was seen that logical and arithmetic operations could now be performed by electronic circuits having just two states.
In 1948 Claude Shannon published 'A Mathematical Theory of Communication', which was another key work in the development of computing as it dealt with the question of encoding information prior to transmitting it. Shannon is said to have invented the field of information theory.
Amongst his many other achievements John Von Neumann, a Hungarian/American mathematician, was the designer of the modern central processing unit of a computer. Around 1945 there were at least two designs for the organisation of the computer's processor and memory. The Harvard design placed instructions in one area of memory and data in another so there were separate buses (links between memory and CPU) for each; von Neumann's design put instructions and data in the same area of memory so there was just one bus to link memory to the CPU. Von Neumann's design proved more durable and it has been the prevailing model for computers ever since.
A computer fetches an instruction from memory, executes it and fetches any required data for the instruction from memory as well. Thus instructions are interleaved with data items in memory. This model of computation is different from both the Turing model (which we didn't examine in detail) and an animal's brain. The brain executes many 'instructions' simultaneously to create thought and the processes are chemical. Humans have long dreamed of creating intelligent machines and the field of artificial intelligence is an important one.
| Royal Institute Christmas Lectures 2011 | Introduction to Neuroscience | Stephen Wolfram |