Chapter 1 Introduction to Computer Science & Programming

                       

1.1.     Declarative vs. Imperative

1.1.1.      Declarative knowledge

                        Declarative knowledge is about “what we want to achieve”. It’s composed by statements of fact [Declarative Programming]. Simple case, when we declare set of rules about what outputs should result from which inputs. In other words, if we have A, then the result must be B. An engine will apply these rules to inputs, and give us the proper output. The focus is on what the computer should do rather than how it should do it.

                        Example:

ü  “A good health care plan improves the quality of medical care while saving money” - declarative statement -

ü  “y is the square root of x if and only if y*y = x”  - declarative statement -

ü  SQL - declarative program -

1.1.2.      Imperative knowledge

                        Imperative knowledge is about “how to achieve our goal or accomplish something”. The focus is on what steps the computer should take rather than what the computer will do (ex. C, C++, Java). Case in computer science, when we specify a series of instructions that the computer executes in sequence (do this, and then do that). We can think of it as recipe [Imperative Programming]. Example, when we specify instruction to find approximation of square root (Heron of Alexandria method)[1]:

1)      Start with a guess, g

2)      If g*g is close enough to x, then g is a good approximation of the square root of x

3)      Otherwise, create a new guess by averaging g and x/g. I.e., g_new= (g_old+ x/g_old)/2

4)      Using this new guess, go back to step 2

5)      Converged (well done cook)

1.2.     Program

                        A computer program is a set of instructions for a computer to perform a specific task. Programming is about controlling the computer or what computer should do. And to control the compiler we give it a program [Beginner - Introduction to Programming]. To make a computer do anything, you have to write a computer program. To write a computer program, you have to tell the computer, step by step, exactly what you want it to do. The computer then "executes" the program, following each step mechanically, to accomplish the end goal [What is a computer algorithm?].

                        When you are telling the computer what to do, you also have to choose how it's going to do it. That's where computer algorithms come in [What is a computer algorithm?]. The algorithm is the basic technique used to get the job done, or the detailed sequence of steps for carrying out some process is called algorithm [What is the differences between algorithm and program?]. Algorithm composed by a finite set of instructions to solve a specific problem or class of problems [Algorithm Analysis]. It is about how to perform computation or how computer should perform a specific task.

                        So the computer program basically is the concrete expression of an algorithm in a particular programming language [Algorithm Analysis]. In other words a computer program is a specific implementation of an algorithm, or set of algorithms designed to be used in conjunction with computer hardware (and possibly other programs) to solve a problem whereas an algorithm does not define the way it is to be implemented (though specific algorithms might by their nature suggest specific implementations) [Algorithm vs. Computer Program]. Ex, approximation program using the same Heron of Alexandria algorithm written in C++ will differed than program written in Java.

                        A computer program usually consist of:

1.2.1.      Instructions

Instruction means steps that can be executed. The instruction is the key element in the computer, as it tells (orders) the processor which action should be performed. The instructions which are to be executed are indicated in the source file and the computer goes from one instruction to the next following the instructions from top to bottom (as a file is read in sequence from top to bottom) [Programming Languages - Instructions].

Figure 1. Operator and operand(s); [Operator, 2012]

An instruction is generally comprised of two elements:

      the operator        : the action that the processor is to carry out

      the operand(s)    : one or more pieces of data on which the operation is performed

For a better understanding, see Figure 1.

At the lowest level language, each instruction is a sequence of 0s and 1s that describes a physical operation the computer is to perform (such as "Add") and, depending on the particular instruction type, the specification of special storage areas called registers that may contain data to be used in carrying out the instruction, or the location in computer memory of data. [Rouse, 2005]

                        In a computer's assembler language, each language statement generally corresponds to a single processor instruction. In high-level languages, a language statement generally results (after program compilation) in multiple processor instructions [Rouse, 2005]. In other words, a macro instruction is one that, during processing by the assembler program, expands to become multiple instructions (based on a previously coded macro definition) in high-level language [Rouse, 2005]. Alan Touring, the British mathematician, says that with less than 7 ‘primitive instruction’ (single processor instruction), each operate on 1 bit information, you can do anything. It means you can build any kind of complex instruction with combine some of main/single processor instruction.

1.2.2.      Control Structure / Flow of Control / Control Flow

                        When we run through a list of instructions, normally, we go through them step by step. But what if that's not the case? What if we are to press the red button when a tone is heard and the green one when not? What if we are supposed to scream when a meltdown occurs but shout when a fire starts? That's where control flow comes in to change the course of the program. Control flow is necessary because we can't expect everything to be like a set of instructions. Changes have to be made. For example, we can say, "Jump off the building if it is on fire, else continue typing your report." The statement above accomplishes something a list of instructions just can't do - change the direction.  [Beginner - Introduction to Programming]

                        Flow of control: the order in which the individual statements, instructions or function calls of an imperative or a declarative program, are executed or evaluated. [Control flow]

1.2.3.      Terminating condition:

                        Without terminating condition, computer will run to infinity.

                         

1.3.     Computer

                        The word “computer” was recorded firstly in 1613 in a book called “The yong mans gleanings” by English writer Richard Braithwait: I haue read the truest computer of Times, and the best Arithmetician that euer breathed, and he reduceth thy dayes into a short number. It referred to a person who carried out calculations, or computations, and the word continued with the same meaning until the middle of the 20th century. From the end of the 19th century the word began to take on its more familiar meaning, a machine that carries out computations. [Computer]

                        Now days, to execute the program, we can design a circuit that do exactly what the program tells. This kind of device is called computer. Based on the flexibility of the program, we can classified computer in two main type. 

1.3.1.      Fixed program computers

The first kind computing machine was fixed program computer. It is design to do specific thing. Most of this early computer were tools to solve specific mathematic problem [Guttag, 2013]. Example:

ü  A revolutionary difference engine, designed to aid in navigational calculations, by Charles Babbage, an English mechanical engineer and polymath, in early 19th century (1833).  [Computer]

ü  In 1941, built by Atanasoff and Berry Computer (ABC) to solve system of linear equation only. [Guttag, 2013]

ü  Alan Turing bombe machine, (during World War II), design strictly for breaking German Enigma Code. [Guttag, 2013]

ü  ENIAC (Electronic Numerical Integrator and Computer)

ü  (Now day) A four-function calculator only to solve basic mathematics only. (+, –, ×, ÷ ) [Guttag, 2013]

1.3.2.      Stored program computers

                        The theoretical basis for the stored-program computer was laid by Alan Turing in his 1936 paper, On Computable Numbers, with an Application to the Entscheidungsproblem [Computer]. In 1945 Turing joined the National Physical Laboratory and began work on developing the principle of electronic stored-program digital computer. His 1945 report ‘Proposed Electronic Calculator’ was the first specification for such a device. In that proposal he described a hyphothetical computing device that has come to be called a Universal Turing machine. The machine had an unbounded memory in the form of tape on which one could write zeros, ones and some primitive instruction such as moving, reading and writing to the tape. (remember, Turing machine is not the same as Universal Turing Machine).

                        The difference in stored program computer and fixed program computer rest not only in hardware but also in the programming and use of machines [Olley, 2010]. With Universal Turing Machine, Turing proposed that program can be treated and stored as data. Now, data and program are the same, and because of program can produce data, it means program can produce program.

                        It is still debated until now about the first stored program computer. And John von Neumann, a leader in continuum research at Princeton University, was offered a post-doctoral position to Turing. But Turing decide to go back to England, help his state in war with Nazi. Neumann see the idea of Universal Turing Machine and circulated his First Draft of a Report on the EDVAC in 1945  [Computer]. Neumann success to put instruction and data in the same memory. This architecture is use widely in the CPU now day (See Figure 3). Consequently, this principle can be used to describe and accomplish anything you can do with computer, by executes any legal set of instruction.

                         

                         

Figure 2. Stored program computer Architecture;

                        The first truly modern computer was The Manchester Mark 1, that built at the University of Manchester, and its first programe in 1949. It implemented ideas previously describe by John Von Newmann and Alan Turing.

                         

1.4.     Programming Language

                        From section 1.2, we see that, programming language provide a set of primitive instruction and primitive control structure. The natural language which can be directly understood by the system is a machine language. In machine language, a program is written in 1s and 0s (binary code). So, a set of instruction in binary pattern is associated with each computer. It is difficult to human like us to communicate with computer in term of binary code. Hence, writing a program with a machine language is very difficult. Moreover speed of writing, testing and debugging is very slow in machine language. Changes of making careless error are bound to be there in this language. Each type of hardware platform design, define a different type of machine language. So, machine language is tedious and time consuming. [Kamthane, 2011]

                        To cope with that, people try to create other type of languages. All other languages are said to be high level or low level according to how closely they can be said to resemble machine code.

                        These type of language are classification as follows:

1.4.2.      Assembly Language

                        Instead of using a string binary bits in a machine language, computer manufacturers started to providing something that more easy to interpreted by programmers. So, the computer manufacturers started providing mnemonics (English-like word abbreviated) that are similar to binary instruction in machine languages. The program is in alphanumeric symbols like ADD, SUB, MUL, DIV, RCL and RAL, called mnemonics. The designer chooses easy that are to be remembered by the programmer, so that the programmer can easily develop the program in assembly language. [Kamthane, 2011]

                        Here are some characteristics of the assembly languages:

-        Less time consuming for an assembler to write and then test the program, rather than in machine language.

-        Assembly languages programs are not portable, cause each type of processor has its own assembly language. For example, 8085 CPU has its own assembly language, CPUs such as 8086, 80186, 80286 have their own assembly languages.

-        Assembly language is a low-level language corresponds closely to machine code, so that a single low-level language instruction translates to a single machine-language instruction.

-        Efficient (optimum use of both computer memory and processing time) for short and simple program, cause to write a low-level program takes a substantial amount of time.

-        It is necessary to remember and understand inner workings of the processor, the registers of CPU and mnemonic instructions by the programmer.

                         

1.4.3.      High-level Language

                        As we see before, some assembly languages characteristics are disadvantages for programmer. Don’t worry, because high-level languages will overcome this problem. High-level languages are build base on procedure oriented languages. These languages are employed for easy and speedy development of a program. Examples of high-level language are COBOL, FORZTRAN, BASIC, C and C++. [Kamthane, 2011]

                        Following are some characteristics of high-level languages:

+        Less time consuming for program development than assembly language.

+        Several mnemonic instructions are needed to write in assembly language than a single line in high-level language. Thus, high language programs are shorter than the assembly language programs.

+        Testing and debugging a program is easier than in the assembly language

+        Portability of a program from one machine to other

                         

1.5.     Programming Translator

                        A program can be written in assembly language as well as in high-level language. This written program is called the source program. The source program is to be converted to the machine language, which is called an object program. All computer programs run on machine code that is executed directly on computer architecture. Machine code is not easily read or programmed directly by humans. Essentially, machine code is a long series of bits (i.e. ones and zeroes). In order to program, humans write code in a language that is then translated in to machine code.

                        Program translator translates source code of programming language into machine language-instruction code. Generally, computer programs are written in languages like COBOL, C, BASIC and ASSEMBLY LANGUAGE, which should be translated into machine language before execution. Programming language translators are classified as follows [Kamthane, 2011]:

Figure 3. Programming language translator classification;

1.5.1.      Assembler

                        The translation job is performed either manually or with a program called assembler. In hand assembly, the programmer uses the set of instructions supplied by the manufacturer. In this case, the hexadecimal code for the mnemonic instruction is searched from the code sheet. This procedure is tedious and time-consuming.

                        Alternate solution to this is the use of assemblers, the program that provides the codes of the mnemonics. An assembler translates the symbolic codes of programs of an assembly language into machine language instructions (see Figure 4a). The reasons why assembly language is efficient for small program because, with assembler, assembly language is translated in the ratio of one to one. It mean one mnemonics instructions will translate to one machine code instructions.  [Kamthane, 2011]

Figure 4a. Assembler translation process;

1.5.2.      Compiler

                        Compilers are the translators for high-level languages. Compile is a process to translate all the instructions of the program into machine codes, which can be used again and again (see Figure 4b). The source program is input to the compiler. The object code is output for the secondary storage device. The entire program will be read by the compiler first and then generates the object code. It is different from interpreter process, which we will see in the next section. High-level languages such as C, C++ and Java use compiler as the translator. The compiler also displays the list of errors and warnings for the statements violating the syntax rules of the language. Compilers also have the ability of linking subroutines of the program.  [Kamthane, 2011]

Figure 4b. Compiler translation process;

1.5.3.      Interpreter

                        Interpreters also come in the group of translators for high-level languages. Same with compiler, the interpreter source program is just like English statements. But interpreter have different in translate process. The interpreter generates object codes by reads and translate the source program line by line. Interpreter directly executes the program from its source code. Due to this, every time the source code should be inputted to the interpreter. In other words, each line is converted into the object codes. It takes very less time for execution because no intermediate object code is generated.  [Kamthane, 2011]

                        M-BASIC, Python are examples of interpreter.

Figure 4c. Interpreter translation process;

                         

1.6.     Programming Language Aspects/Elements – an English sentence analogy

                        Just like natural languages (ex, English, Chinese, Indonesian, etc), each programming languages has a set of primitive construct. The aim of this construct is to produce well form program, that has exactly only one meaning. This set of construct consist of:

1.6.1.      Syntax

                        The Syntax of a language refers to the spelling of the program, which strings/sequences of characters and symbols are well formed. For example, in English the string "ball shirt boy" is not a syntactically valid sentence, because the English grammar does not accept sentences in the form of . In Python syntax chart, the sequence of primitive 3.5 + 3.5 is syntactically well form, but the sequence 3.5 3.5 is not.

                        We discuss syntax first, because syntax errors are the most common kind of error, but it is the least dangerous kind of error. A good programming language does a complete job of detecting syntactic errors, and will not allow users to execute a program with even one syntactic error. Furthermore, in most cases the language system gives a sufficiently clear indication of the location of the error that it is obvious what need to be done to fix it. [Guttag, 2013]

                         

                         

1.6.2.      Static semantics

                        The static semantics refer to syntactically valid strings that have a meaning. For example, the English string "I are big" is of the form , which is syntactically acceptable sequence. However, it is a static semantic error, because the noun "I" is singular and the verb "are" is plural. So it doesn’t have a real meaning. In Python, the sequence 3.7/'abc' is syntactically well formed ( ), but produce a static semantic error, because dividing a number by a string of characters is not meaningful.

                        Semantic errors, is a bit more complex than syntax. Static semantic error makes program behavior become unpredictable, so it is important to do static semantic checking. Some programming languages, e.g., java, do a good job on static semantic checking before allowing a program to be executed. Others, e.g., C and Python, do relatively less static semantic checking. Python does do a considerable amount of static semantics checking while running a program. However, it does not catch all static semantic errors.  [Guttag, 2013]

                         

1.6.3.      Semantics

                        Semantics is talk about, what that meaning of the program. The special in programming language is that every well-formed program, which free of syntax and static semantics error, will only has exactly one meaning. Different with, natural languages, e.g., English, can be ambiguous. For example, the sentence "I cannot praise this student too highly" can be either flattering or damning. [Guttag, 2013]

                         

                         

                         

1.7.     Paradox of computer program

                        As we see before, program has no syntactic error and no static semantic error, it has a meaning, i.e., it has semantics and computer will do exactly what you tell it to do. This is good news. But semantic doesn’t mean that computer will do exactly as what the programmer want it to do. When a program done something other than what its creator thinks it means, bad things can happen. Now we see the paradox.

                        The following are what happen when a computer do something other than programming meaning, in order of badness:

1.7.1.      Crash

                        At the lowest level, it might crash, or in other words, it stops running and produces some sort of indication. In a properly designed computing system, when a program crashes it doesn’t damage to the overall system. Of course, some very popular computer systems don't have this nice property. Almost everyone who uses a personal computer has run a program that has managed to make it necessary to restart the whole computer. [Guttag, 2013]

1.7.2.      Never stop

                        Next level, it might keep running, and running, and running, and never stop (or called infinity loop). This situation is hard to recognize if we have no idea about how long the program is supposed to take to do its Job. [Guttag, 2013]

1.7.3.      Run to completion but produce wrong answer

                        The worst thing can happen is when the program run to completion and produce an answer that might be correct, or might not. This is very bad, cause when a program appear to be doing the right thing but isn't, disaster can follow. Example: fortunes can be lost, patients can receive fatal doses of radiation therapy, airplane can crash, etc. So it is important to programmer when they write a program, it should be written in such a way that when it doesn't work properly, it is self-evident. [Guttag, 2013]

1.8.     Why we use python in learning computer science???

                        There are many sources and reasons for us to use python as a programming learning tool. These are some conclusions of the reasons we choose Python:

·         Medioker

·         Easy to use

·         Widely use

·         Easy to debug

·         Interpreter (we can compile python but it is unusual & un-efficient)

·         Better learning curve

Bibliography

Algorithm Analysis. (n.d.). Retrieved June 12, 2013, from http://courses.cs.vt.edu/: http://courses.cs.vt.edu/cs2604/spring04/Notes/C04.AlgorithmAnalysis.pdf

                        Algorithm vs. Computer Program. (n.d.). Retrieved June 12, 2013, from http://www.coderanch.com/: http://www.coderanch.com/t/396727/java/java/Algorithm-computer-program

                        Beginner - Introduction to Programming. (n.d.). Retrieved January 31, 2013, from library.thinkquest.org: http://library.thinkquest.org/15375/b01.htm

                        Computer. (n.d.). Retrieved February 19, 2014, from wikipedia.org: http://en.wikipedia.org/wiki/Computer

                        Control flow. (n.d.). Retrieved January 8, 2013, from en.wikipedia.org: http://en.wikipedia.org/wiki/Control_flow

                        Declarative Programming. (n.d.). Retrieved January 8, 2013, from en.wikipedia.org: http://en.wikipedia.org/wiki/Declarative_programming

                        Guttag, J. V. (2013). Introduction to Computation and Programming Using Python (spring 2013 ed.). Cambridge, Massachusetts: The MIT Press.

                        Imperative Programming. (n.d.). Retrieved January 8, 2013, from en.wikipedia.org: http://en.wikipedia.org/wiki/Imperative_programming

                        Kamthane, A. (2011). PROGRAMMING IN C (2nd Edition ed.). (R. Sachdev, Ed.) India: Pearson Education India.

                        Olley, A. (2010). Existence Precedes Essence - Meaning of the Stored-Program Concept*. IHPST, University of Toronto , 10.

                        Programming Languages - Instructions. (n.d.). Retrieved June 14, 2013, from http://en.kioskea.net/: http://en.kioskea.net/contents/313-programming-languages-instructions

                        Rouse, M. (2005, September). DEFINITION - Instruction. Retrieved June 9, 2013, from http://searchcio-midmarket.techtarget.com: http://searchcio-midmarket.techtarget.com/definition/instruction

                        What is a computer algorithm? (n.d.). Retrieved June 12, 2013, from http://www.howstuffworks.com: http://www.howstuffworks.com/question717.htm

                        What is the differences between algorithm and program? (n.d.). Retrieved June 12, 2013, from http://wiki.answers.com/: http://wiki.answers.com/Q/What_is_the_differences_between_algorithm_and_program

                         

---

                        [1] Many believe that Heron was not Inventor of this method, and indeed there is some evidence that it was well known to the ancient Babylonians.  [Guttag, 2013]