ITIC:Software and programming introduction

From Juneday education
Jump to: navigation, search
TODO

Reading instructions

Before this module, you should read the Swedish compendium, chapters Dator and Programmering; and Kernigan, Inside the CPU and Part II - Software, pages 35-116.

Programming

CPU

The central part of a computer, is the CPU (Central Processing Unit). The CPU isn't really that fancy, it can do basically a few simple things (albeit very fast). It can do arithmetic (add, subtract, multiply and divide numbers). In order to e.g. add two numbers, it can also fetch numbers from the memory (by specified memory locations). The CPU is also responsible for controlling various hardware connected to the computer (mouse, keyboard etc). But not only can the CPU calculate with numbers it fetches, it can also do some basic decisions based on comparisons of numbers and decide what to do depending on the outcome. This is the fascinating part! Once we have loaded a bunch of operations and conditionals into the CPU, it can run independently and do different things depending on the outcome of comparisons.

The Toy Computer

Here's a simulator of the Toy Computer from Kernigan's book, which demonstrates this basic behavior of a CPU.

Let's say we want to read numbers from the user and add all numbers up until the user enters a zero. You can try with the following Toy program, and run the simulator:

Main get
 ifzero End
 add sum
 store sum
 goto Main
End load sum
 print
 stop
sum 0

This is how the small program for the Toy Computer works:

  • Main is a labeled instruction with the predefined operation get which prompts the user for a number and stores it in the accumulator memory location
  • ifzero is a predefined operation which checks if there is a zero in the accumulator location, and if so jumps to the labeled instruction End
  • add sum uses the predefined operation add and the memory location called sum, which reads the value from sum and adds it to the current value of the accumulator which now gets bigger
  • store sum uses the predefined operation store and overwrites the memory location sum with whatever is currently in the accumulator
  • goto Main uses the goto instruction to jump to the labeled instruction Main
  • End load sum is a labeled instruction with the predefined operation load sum which overwrites the accumulator with the value currently in the memory location called sum
  • print is a predefined operation which prints the value of the accumulator
  • stop is a predefined operation which ends the execution
  • sum 0 creates the memory location called sum and loads it with the value 0 before the program starts

In other words, the program actually starts with the last line, creating the memory location called sum and stores the initial value 0 into it. Then the execution begins from the top. There we find the labeled instruction Main get. So here the program runs the predefined instruction get which simply prompts the user for a number, which is then stored in the accumulator (a special memory location). Next, the program continues with the next line, ifzero End, which will conditionally jump to the instruction with label End if the current value in the accumulator is zero. Let's say the user has entered 10 which is now stored in the accumulator. The conditional jump will not execute, since the accumulator has the value 10 and not 0. So the program continues with the next instruction, add sum, which will read the value from the memory called sum which still is zero, and add that value to the accumulator, which now will have the value 10+0.

After this, the next instruction is store sum, which reads the current value of the accumulator (10) and overwrites the current value in the memory called sum. After this, the sum memory location has the value 10, which is also what the accumulator has. Next, the instruction goto Main is executed, and the program jumps back to the instruction labeled Main.

This time, the user enters 20, which is then stored in the accumulator. The ifzero conditional jump is not executed, because 20 isn't 0, so the execution moves on to the next instruction. Now, the program changes the value of the accumulator (20) by adding the value stored in sum (10), so the accumulator gets updated to 30. After this, the sum memory location is overwritten with the current accumulator value, so it becomes 30. Then we jump up to Main again, and another value from the user is gotten. This time, the user enters 0 (because she is tired of playing), so the accumulator is updated to 0. Now, finally, the ifzero conditional check is executing its jump to End, because the accumulator had value 0. This means that we have broken out of the loop.

At label End we have the instruction load sum, which reads the memory at sum (30) and puts that value in the accumulator. After that, the predefined instruction print prints the value of the accumulator (30) and then the execution ends.

Thanks to the ifzero conditional jump, we can continue to read and add numbers until the value read is 0. Another way of expressing this (in programmer terms) is while the number read is not zero, add the number to the current sum. This is called a loop.

Try to use the program above in the Toy Simulator linked above.

Same program in Bash

In Bash, the same program would look like this (using the while loop construct):

sum=0
read num
while ((num != 0))
do
  sum=$((sum + num))
  read num
done
echo "Sum is: $sum";

When the bash script is executed, this is what it looks like:

sum=0; read num; while ((num != 0)); do sum=$((sum + num)); read num; done; echo "Sum is: $sum"; 
10
20
0
Sum is: 30

You can try by pasting the command line above into your terminal: sum=0; read num; while ((num != 0)); do sum=$((sum + num)); read num; done; echo "Sum is: $sum"; .

Same program in Java

Start by installing Open JDK 9 on your computer. In Ubuntu or Debian, that's done like this:

$ sudo apt-get update && sudo apt-get install openjdk-9-jdk

Enter your user password when promted to.

Put the following text in a plain text file (use an editor) which you save as "Adder.java":

public class Adder {
  public static void main(String[] args) {
    int num;
    int sum = 0;
    while ( (num = Integer.parseInt(System.console().readLine())) != 0 ) {
      sum += num;
    }
    System.out.println("Sum: " + sum);
  }
}

The above works on Linux systems. If you are running Cygwin on Windows, you don't have a "console" object, so you need to use a slightly more verbose version of the reading of a number:

public class Adder {
  public static void main(String[] args) {
    int num;
    int sum = 0;
    java.util.Scanner console = new java.util.Scanner(System.in);
    while ( (num = Integer.parseInt(console.nextLine())) != 0 ) {
      sum += num;
    }
    System.out.println("Sum: " + sum);
  }
}

You are not supposed to understand the details here! We just wanted to show you what a simple Java program doing the adding of numbers could look like.

When you have pasted or typed the program (exactly as above) into the text file Adder.java, you must translate the text file to a file in a language that the java interpreter can understand. That is done using the compiler javac:

$ javac Adder.java

The compiler (if it accepts your code) will then create the file Adder.class from your Java source code file Adder.java. You can now tell the java interpreter to run this class file:

$ java Adder

As usual, when we show you bash command lines, the leading dollar sign represents the bash prompt, and is not part of what you should type in.

Here's a sample run of the program:

$ java Adder
10
20
0
Sum: 30

If you want a simpler version of the program, you can try this:

public class Adder {
  public static void main(String[] args) {
    int num;
    int sum = 0;
    String sNum = System.console().readLine();
    num = Integer.parseInt(sNum);
    while ( num != 0 ) {
      sum += num;
      sNum = System.console().readLine();
      num = Integer.parseInt(sNum);
    }
    System.out.println("Sum: " + sum);
  }
}

Same program in Python

Using another programming language, Python, the program could look like this:

import sys
num = int(input())
sum = 0
sum += num

while num != 0:
  num = int(input())
  sum += num

print ("Sum: ", sum )

Disclaimer: Rikard doesn't really speak Python, so please see this as an example and not as exemplary Python.

To run the python code, save the program in a file called adder.py, and run it on the command line invoking the python3 interpreter:

$ python3 adder.py 
10
20
0
Sum:  30
$

If you need to install Python, this is how you could do that in Ubuntu/Debian:

$ sudo apt-get update && sudo apt-get install python3

Revisiting the Toy Computer

Here's a challenge for you. Write a Toy Computer program, that reads a number from the user. It should then calculate the sum of all numbers up to and including this number. Or, perhaps easier, calculate all numbers from this number down to zero.

If the user enters 5, the program should print the sum of 5 + 4 + 3 + 2 + 1 + 0 = 15. If the user enters 0, it should print 0. If the user enters 1, it should print 1 (1 + 0). If the user enters 2 it should print 3 (2 + 1 + 0). If the user enters 10 it should print 55 (10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0).

Hints:

  • Declare two variables (memory locations) at the end of the program
    • i 0
    • sum 0
  • start by getting the number from the user
  • store this number in location i
  • start a labeled instruction called Loop and load the value from i to the accumulator
  • check if the accumulator is 0, if so jump to label End
  • otherwise (accumulator wasn't 0) add value from sum to the accumulator
  • store the new value in the accumulator to location sum
  • load i to the accumulator
  • subtract 1 from the accumulator
  • store the value of the accumulator to location i
  • jump back to Loop
  • declare a labeled instruction called End with the instruction to load the value of sum into the accumulator
  • print the value of the accumulator
  • stop the execution

Remember that the program comes before the declaration and initialization of the locations (variables) i and sum. Remember that instructions start with a space. Remember that labels don't start with a space.

The variable (location) declarations at the end don't have a leading space either.

The predefined instructions to use are:

  • get - read a value from user to accumulator
  • store M - store the current value to location M
  • load Val - update the accumulator with value Val (or value from location Val)
  • ifzero L - if the accumulator is zero, jump to label L
  • add Val - update the accumulator by adding Val to it (or adding value from location Val)
  • sub Val - update the accumulator by subtracting Val from it (or subtracting value from location Val)
  • goto L - jump to label L
  • print - print the contents of the accumulator
  • stop - end execution

Click on "expand" to see a suggested solution

 get
 store i
Loop load i
 ifzero End
 add sum
 store sum
 load i
 sub 1
 store i
 goto Loop
End load sum
 print
 stop
i 0
sum 0

Software

Software is the programs we write to be executed by a computer. A program is written in some programming language as a sequence of instructions to be executed by the CPU, much like the examples above.

There are generally two kinds of programming languages. To understand why, it is important to first realize that the actual instructions for a CPU are just binary numbers. It is extremely hard for humans to write instructions in binary format (or to read such instructions). That's why programming languages were invented. Programming languages are for humans, so that we can write instructions in a language closer to how we think, as opposed to how a computer operates. So programs are written in a programming language by humans and for humans. As a programmer, you will spend lots of time reading other programmers code (and trying to understand what they are supposed to do) as well as reading your own code.

But computers don't speak programming languages. So, we need to translate the programming language code to code that the computer's CPU can understand. This is basically done in two main ways:

  1. Compiled languages - a special program translates the programming language code to "machine code" that the CPU can execute
  2. Interpreted languages - a special program reads the programming language code line by line and executes the instructions

Then, there's Java. Java is special. The programming language code written in Java, needs to be translated (compiled) to a different format (byte code). But the computer can't execute the byte code either. Java comes with two major programs:

  • The compiler - translates Java source code to byte code
  • The virtual machine - acts like a computer and can interpret and execute byte code

So, in order to program using a programming language, you need to install that language in your computer. If you are using a compiled language like C, C++, Ada or Pascal, you will install a compiler and some other tools. Often you will also install a lot of useful code in what is called libraries so that you get access to predefined functions and functionality.

In order to program using an interpreted language, like Bash, Python, or Perl, you need to install an interpreter (and other tools for your language).

And for Java, you need to install a compiler (for creating byte code from your code) and a virtual machine (capable of running the byte code) and some other tools.

To compile and run a C program (compiled program), you will first write your code and save it in a plain text file. You will then use the compiler to create an executable program from your source code. The executable program will now be able to be run on your platform. If you are on Windows, you can run your program on Windows. But it won't run on a macOS or GNU/Linux computer. The compiler translates the C source code to machine code for your CPU and operating system.

With interpreted languages, every computer that has e.g. a Python interpreter, can run the same program, since it is interpreted directly from the source code. It is the interpreter itself that is created for the various platforms and operating systems. The same can be said about a compiled Java program (translated to byte code). Every computer that has a Java Virtual Machine (JVM) compiled (created) for its system, can run every Java byte code compiled anywhere.

Java is sometimes referred to as platform independent. Write once, run everywhere was once how this concept was marketed. It's not entirely true, however. Compiled Java code can only be run where there's a JVM created for the platform where the program is to be run.

Algorithms

An algorithm is a careful, precise and unambiguous description of how to solve a (also carefully, precise and unambiguous description of a) problem. You can think of it as a step-wise description of how to go about solving a class of problems. An algorithm can be implemented in a programming language, so that computers can use the algorithm to solve the problem.

An algorithm must be guaranteed to terminate, according to many definitions. That means ending up in a state where the problem actually is solved (even if it may take a very long time).

Typical computer algorithms involve sorting some set of objects, and searching through a set of objects.

There are often many competing algorithms for solving the same problem. So you might hear stuff like an effective algorithm for sorting lists. This implies that there are many algorithms for sorting and they are not all as efficient.

When you have a sorted list of objects, like numbers or words for instance, there are some efficient ways to find an element of the list.

As an example, we'll describe here the binary search algorithm for finding a word in a dictionary. We'll take a Swedish dictionary as an example (Stora ordboken). The language doesn't really matter. A dictionary has all its words sorted alphabetically. The dictionary has 600 pages. Let's say we want to find the page where the word ekvation (Eng.: equation) is listed.

Rather than starting from the beginning and scanning every page, the binary search algorithm prescribes the following strategy. Start at the middle. This removes half of the pages, because now you know in what half the word must be. Find the new middle in this half, until you have found the element you are looking for.

Every time we don't find the word, we have removed half of the remaining pages to search.

  • Find the middle page (page 300)
  • Is the word alphabetically before this page, find the middle page between 1 and 300, otherwise the middle page between 300 and 600
  • Page 300 is the last page of words starting with K, so we should look at page 150 (e is before (less than) k).
  • Page 150 contains words starting with f, so we should take the middle again between 1 and 150
  • Page 75 lists words starting with b, so we should look for the page between 75 and 150 (page (75+150)/2)
  • Page 112 has words starting with d, so we should look for the page between 112 and 150 (page (112+150/2)
  • Page 131 has words from ep... through er..., so before this - page (112+131)/2
  • Page 121 has words from 'E' throug eg..., so after this - page (121+131)/2
  • Page 126 has em... through en, so before this - page (121+126)/2
  • Page 123 indeed has the word ekvation, so we found it by looking at only eight pages

You will never need more than 10 lookups for lists up to 1024 elements, because you can only divide 1024 ten times:

  • 512
  • 256
  • 128
  • 64
  • 32
  • 16
  • 8
  • 4
  • 2
  • 1

Do the numbers above remind you of anything? They are powers of 2. So, using the binary search will guarantee Log2(N) lookups for N elements. That is to say, if we have a sorted list of N elements, what number should we use as the exponent to two, to get at least this number?

If we have 600 pages, the answer is 10, since 210 is 1024 which is more than enough.

For a book of 10 000 pages, how many look-ups do we need? 14! Because 214 is 16 384 (more than enough).

Now, if we have a book of 1 000 000 pages, how many look-ups do we need? Think about it.

Bonus material for the ambitious student

We've included a page from another part of the wiki below. It has videos too, so please check those out.

Note: below is an inclusion of Chapter:Programming_introduction

Programming introduction

Meta information about this chapter

Expand using link to the right to see the full content.

Introduction

In this presentation we will be introduced to programming by comparing programming to normal everyday actions, such as washing clothes.

We will also get a better understanding of the compiler and the steps performed when compiling source code.

Purpose

The purpose of this presentation is to make it easier for the student to understand the following lectures.

Writing software in languages such as C, C++ and Java means you at some point must transform your source, which is in text form, into a form executable by either the operating system or a virtual machine.

Requirements

It is assumed that the student is familiar with OS (operating system), program, file system, file and file types.

No other previous programming knowledge is required.

Goal

After this lecture the student shall have basic understanding of what a program is, how it is written and how it relates to everyday actions we humans do.

The student should:

  • understand the role of a compiler

Instructions to the teacher

Common problems

Make sure the students understand the edit - compile - run workflow. This chapter is however mostly a chapter to introduce programming by showing some examples.

All videos

All English videos in this chapter:

All Swedish videos in this chapter

Note that some videos are in English but included here for completeness.

See below for individual links to the videos and slides.

Introduction to programming

Description

Programming is the practice of writing text files (so called source code files) where you express instructions to be performed by a computer. You express these instructions using a so called programming language, which is a set of rules for how to write said instructions.

The product of programming is a set of source code text files which typically are transformed into a a file or several files in language which is also understood by the computer or some existing computer program. This transformation from source code to files that are meaningful to the computer (or some existing computer software) is generally referred to as compiling.

Further on in this book, we will also address different ways to analyse what we want our programs to do, as well as different ways to accomplish that. Those activities may also be seen as activities belonging to the practice of programming.

Programming language

Programmer

A programmer is a person who develops (creates/writes) computer software. A programmer can be specialised in many different fields of programming: web, system, embedded, real-time, test and so on. In this course we will give the basics of Java programming. Enough to get you started to become a programmer and also enough for you to take on other roles in system development, such as project manager or product owner.

Videos (introduction)

  1. Introduction to programming (eng) (sv) (download presentation)

Links

  • No links here

Program examples

Description

We will show you some examples of programs, how we write them and the different procedures to get them to be executed. See the video lectures below for some examples of programs in various programming languages.

Videos for examples in various languages

These videos contain examples of programs not written in Java. You will most likely not be able to compile and execute these. We provide these videos and source code as examples. If you still want to compile and execute them, we provide links to pages of how to set up your environment for these languages. (no additional setup needed)

Compiler

Description

A program that transforms (or transform) software written in one programming language to another programming language. It will take an entire course to give you enough information about compilers and how to write them but in our courses this will do fine.

Examples of compilers are Java Compiler which translates from Java source code to Java byte code (to be executed by the Virtual Machine) and C Compiler which translates from C source code to machine code.

Expand using link to the right to see an example of compilation of a C program.

C compilation

Let's give an example in C. Here's the source of a file called hello.c:

#include <stdio.h>

int main(void)
{
  printf("Hello world\n");
  
  return 0;
}

Source code can be found at github: hello.c (download with curl: curl -O https://raw.githubusercontent.com/progund/junedaywiki/master/compiler/hello.c).

To compile the file above you type the following:

$ gcc hello.c -o hello

Now we have transformed hello.c (yet kept the original) into a program called hello.

To execute the program (as result from compiling hello.c you can type the following:

$ ./hello
Hello world

If we want to check the file type we can do the following:

$ file hello
hello: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=59c0391f9cb05af1e15cf6f96db55b6bf141ad8b, not stripped

Note: the printout from file is from the author's laptop running GNU/Linux. The printout may differ on your computer.

Expand using link to the right to see an example of compilation of a Java program.

Java compilation

Let's give an example in Java. Here's the source of a file called Hello.java:

public class Hello {

  public static void main(String[] args) {
    System.out.println("Hello world");
  }

}

Source code can be found at github: Hello.java (download with curl: curl -O https://raw.githubusercontent.com/progund/junedaywiki/master/compiler/Hello.java).

To compile the file above you type the following:

$ javac Hello.java

Now we have transformed Hello.java (yet kept the original) into a file called Hello.class.

To execute the program (as result from compiling Hello.java you can type the following:

$ java Hello 
Hello world

If we want to check the file type we can do the following:

$ file Hello.class 
Hello.class: compiled Java class data, version 52.0 (Java 1.8)

Note: the printout from file is from the author's laptop running GNU/Linux. The printout may differ on your computer.

Videos

  1. Compiler (eng) (sv) (download presentation)

Questions and Answers

Expand using link to the right to see the full content.

Q: “There seems to be many different programming languages. Do we need so many?”
A: Luckily, we only need to learn one language in order to learn how to program. But there are many languages being used for programming and, of course, all programming languages differ more or less from each other. After learning on language, it is wise to at least gain some basic knowledge of a few other common languages. Reasons for learning any particular language may range from career decisions (some languages are more common on the job market than others) to reasons based on curiosity. If the languages differ, there must be reasons for this! What makes any one particular language different from the rest? Beware that if you ask any proponent (or sales representative, or member of the fan club etc) for one programming language, they will tell you that the language in question solves all problems with the rest of the programming languages in existence. However, there are some main differences between at least families of programming languages, which stem from the fact that different families of language take different approaches to describe the task for the program to be written together with different approaches for how the task should be solved and executed. For this reason, there is much to be gained from learning a few languages (at least on a basic level) from different families of languages, because that might help you gain insights about how to think about the practice of programming - modelling the components that are part of the task for a program and also how to solve problems or perform the tasks using the modelled components.

Other reasons for needing different programming languages could be the domain for the programs to be written. There are languages that are more suitable for writing software that is very close to the hardware the program is running on (like programs that are part of an operating system, or programs that are running on some small piece of hardware perhaps even without an operating system). There are other languages that are specialized on solving problems of a mathematical nature, languages specialized for statistical analysis and visualization, languages more targeted at the world wide web etc.

Programming has been around for quite some time now, so this could also help explain why there are so many languages for this activity. Languages of course evolve over time and it is not uncommon for the industry to take part in the creation of new languages. Often there are competing languages from different vendors, where the languages do not differ all that much, but that’s not what the vendors’ marketing departments will tell you!

Q: “Is a program really nothing but a sequence of instructions?”
A: At least to the computer, it is! As you have learnt from the previous answer, there are many different families of programming languages which all take a different approach to how to organize the instructions and how to express what the program should do. But in the end, the computer is the one responsible to do the actual work that the program describes, and the computer will do this in a way that very well might be described as executing a sequence of instructions. Java is a so called Object Oriented programming language. As we will learn throughout the course, the ‘Java way’ of describing what the program deals with and what to to with that, is focused around the notion of objects representing the stuff our program deals with, and what those objects can do (to help us get our program to do what we want). For this reason, programs written in Java don’t lend themselves as easily as programs written other languages, to the idea of “programs as sequences of instructions”. As you will discover, however, when we write the code describing what our objects can do, we express that behaviour in the form of “sequences of instructions”.

Q: “What are the steps to create and execute a Java program?”
A: You will learn this throughout the course, but it is really simple and only three steps:

  1. Create the program using a text editor by typing in valid Java code and save the file (according to some file naming conventions).
  2. Compile the file using the javac compiler (javac is the name of the Java Compiler) giving your source code file as the argument to javac.
  3. Run the Java program using the java command (java invokes the Java Virtual Machine and takes the class name of your program as an argument).

Q: “There are naming conventions for the Java source code files? And what did you mean by ‘class name’?”
A: All this will become clear in coming chapters of this course! In short, every Java program has at least one ‘class’ which is a kind of unit for your programs. A class you define has a name (that you choose). The file must be saved using the name of the class followed by the suffix ‘.java’. When you run the program, the java command expects as an argument the name of the class and nothing else. But don’t worry if this sounds complicated! It will be clear in a chapter coming soon!


End inclusion of Chapter:Programming_introduction

Links

Navigation

The next page is Software_and_programming_introduction_-_Exercises.

« PreviousBook TOCNext »