1 01-Computation


Previous: 00-Inspiration.html

If you give someone a program, you will frustrate them for a day;
if you teach them to program, you will frustrate them for a lifetime.

1.1 Screencasts

Note: Cahoot questions for today are easy gimmies, just to get you used to the system.

1.2 Today’s objectives

1.3 Introduction

1.3.1 What is a shell and an interactive command interpreter?

This is the standard bash shell interpreter’s prompt:
$
It is just awaiting your command!

This is the standard fish shell interpreter’s prompt:
user@domain ~>
It is just awaiting your command!

This is the standard c-python interpreter’s prompt:
>>>
It is just awaiting your command!

This is the iPython interpreter’s prompt:
In [1]:
It is just awaiting your command!

This is the pypy interpreter’s prompt:
>>>>
It is just awaiting your command!
This is meta-python humor… a python interpreter kind-of written in python.

An interpreter has a memory of stuff, and can “store” things in it.

Demo: Open a terminal and send commands back and forth with a couple interpreters manually!

1.3.2 What is a computer program?

1.3.3 What is a computer system?

1.4 Hardware

1.5 Software and programming languages

https://en.wikipedia.org/wiki/Software
https://en.wikipedia.org/wiki/Programming_language
https://en.wikipedia.org/wiki/Comparison_of_programming_languages

1.5.1 Non-programming languages

https://en.wikipedia.org/wiki/Markup_language

These are not programming languages:
* Markup language allows a developer to describe a document’s content, desired formatting, or other features.
* HTML
* HTML (hyper-text markup language) allows a developer to describe the text, links, images, and other features of a web page.
* Latex, markdown, etc.

1.5.2 Low level languages

Machine code:
01-Computation/machinecode.png
* Computers understand language that consists of sets of instructions made of ones and zeros.
* This computer language is often called machine code.
* Programming a computer directly in machine language using only ones and zeros is very tedious and error prone.

1.5.3 High level languages

https://en.wikipedia.org/wiki/High-level_programming_language
* To make programming easier, high level languages can be used.
* A computer can only understand machine language
* Humans wish to write in high level languages
* High level languages have to be re-written (translated) into machine language
* Done by special programs called compilers, interpreters, and/or assemblers

This is a simple flowchart:
01-Computation/00_hello_world_cfg.svg
Note: the part at left is the flowchart, the right box is just the key/legend.

This is a simple python program (interpreted):
01-Computation/00_hello_world.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

print("Hello world!")

2 is usually comments not interpreted by the computer

This is a simple bash program (interpreted):
01-Computation/00_hello_world.sh

#!/bin/bash

echo "Hello world!"

3 is usually comments not interpreted by the computer

This is a simple C++ program (compiled):
01-Computation/00_hello_world.cpp

// Compile C++ with: g++ 00_hello_world.cpp
#include <iostream>

int main()
{
    std::cout << "Hello world!" << std::endl;
    return 0;
}

// is comments not compiled by the computer

Remember,

This is the bash interpreter:
$
Just awaiting your command!

This is the python interpreter:
>>>
Just awaiting your command!

The interpreter has a memory and can store stuff.

Demo: run and compile and run the above, and then send commands back and forth with a couple interpreters manually!

++++++++++++++++++
Cahoot-01.1

3.0.1 Interpreted and compiled languages

and everything kind-of in-between

3.0.1.1 Compiled

https://en.wikipedia.org/wiki/Compiler
* compiled language
* A program written in a compiled language is first converted by a tool (compiler) into machine code, which can run on a particular machine.
* compiler
* A program written in a compiled language is first converted by a tool (compiler) into machine code, which can run on a particular machine.
01-Computation/compiled.png
This process produces binary code in a file, a.k.a, “a binary”.

3.0.1.2 Interpreted

https://en.wikipedia.org/wiki/Interpreter_(computing)
https://en.wikipedia.org/wiki/Scripting_language
* interpreted language (with interpreters)
* An interpreted language (aka scripting language) is a language that is run one statement at a time by another program called an interpreter.
01-Computation/interpreted.png
Sometimes the interpreter is doing just-in-time compilation…

3.0.2 Some other language features

There are more than these:

3.0.2.1 Typing

https://en.wikipedia.org/wiki/Type_system
https://en.wikipedia.org/wiki/Strong_and_weak_typing
* statically typed
* Most compiled languages are statically typed, meaning each variable’s type must be declared and cannot change while the program runs.
* dynamically typed
* Many interpreted languages are dynamically typed, meaning a variable’s type may change while a program executes, usually based on what is assigned to the variable.

3.0.2.2 Paradigms

One of numerous paradigms:
https://en.wikipedia.org/wiki/Programming_paradigm
* object
* In a program, an object consists of some internal data items plus operations that can be performed on that data.
* object-oriented language
* An object-oriented language supports decomposing a program into objects.

3.1 Libraries

https://en.wikipedia.org/wiki/Library_(computing)
* A library is a set of pre-written functions (and other items) that carry out common tasks, that a programmer can use to improve productivity.
* Also known as a module, which you can “import” to stand on the shoulders of coding giants.

3.2 Parts of the development tool-chain

01-Computation/editors_compilers.png

3.2.1 Compilers

https://en.wikipedia.org/wiki/Compiler
* A compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language).
* The name compiler is primarily used for programs that translate source code from a high-level programming language to a lower level language (e.g., assembly language, object code, or machine code) to create an executable program.

Simplified steps of a compiler

  1. Checking the syntax:
  2. Produce the executable file:

The target code may be the machine language for a particular platform or embedded device.

We don’t usually think about a pre-processor, compiler, and linker working as three separate programs (although they are):

3.2.2 Interpreters

https://en.wikipedia.org/wiki/Interpreter_(computing)
* An interpreter is a computer program that directly executes instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program.
* An interpreter generally uses one of the following strategies for program execution:
* Parse the source code and perform its behavior directly;
* Translate source code into some efficient intermediate representation and immediately execute this;
* Explicitly execute stored pre-compiled code made by a compiler which is part of the interpreter system.

There are numerous types of interpreters:
https://en.wikipedia.org/wiki/Interpreter_(computing)#Variations

++++++++++++++++++
Cahoot-01.2

3.2.3 Text editors

https://en.wikipedia.org/wiki/Comparison_of_text_editors
https://en.wikipedia.org/wiki/Comparison_of_integrated_development_environments
* Allows the user to enter the program source code and save it to files.
* Increase programmer productivity by using colors to highlight language features.
* Syntax of a language refers to the way pieces of the language are arranged to make well-formed sentences.
* “The tall boy runs quickly to the door.” uses proper English syntax.
* “Boy the tall runs door to quickly the.” is not correct syntactically, though has correct words.
* Syntax-aware editors can use colors or other special annotations to alert programmers of syntax errors before the program is compiled.

3.2.4 Debuggers (code tracing)!!!

https://en.wikipedia.org/wiki/Debugger
* A debugger allows a programmer to more easily trace a program’s execution in order to locate and correct errors in the program’s implementation.
* With a debugger, a developer can simultaneously run a program and see which line in the source code is responsible for the program’s current actions.
* The programmer can watch the values of variables and other program elements to see if their values change as expected.
* Debuggers are valuable for locating errors (also called bugs) and repairing programs that contain errors.
* Learning to debug and troubleshoot on your own may be one of the most important skills of a good programmer.

I will relentlessly badger you to use one of these (don’t resist, and give it a try)!
Start by RTFM for pudb and spyder ;)

3.2.5 Profilers

https://en.wikipedia.org/wiki/Profiling_(computer_programming)
* A profiler collects statistics about a program’s execution allowing developers to tune appropriate parts of the program to improve its overall performance.
* A profiler indicates how many times a portion of a program is executed during a particular run, and how long that portion takes to execute.
* Profilers also can be used for testing purposes to ensure all the code in a program is actually being used somewhere during testing.
* The main purpose of profiling is to find the parts of a program that can be improved to make the program run faster.
* We cover this stuff later in the curriculum.

3.2.6 Linters

https://en.wikipedia.org/wiki/Linter_(software)
A linter, is a tool that analyzes source code to flag programming errors, bugs, stylistic errors, and suspicious constructs.

3.2.7 Code auto-formating

https://duckduckgo.com/?q=code+auto+formatters
These take linting another step forward, not just harassing you about code style, but fixing it for you.

3.2.8 Integrated Development Environment

https://en.wikipedia.org/wiki/Integrated_development_environment
* An IDE combines many of the above programming tools, linters, debuggers, syntax highlighters, profilers, etc.
* I suggest that for NEW programmers, that you use a nice, fully featured IDE, like Scientific PYthon Development EnviRonment (SPYDER), which will be in your class VM.
* As an experienced programmer you may find simpler command line tools more efficient for producing lots of code.

01-Computation/IDE.png
And many more features!

++++++++++++++++++
Cahoot-01.3

3.3 Computational thinking

What is a program?

3.3.1 Algorithms and computational problem solving

https://en.wikipedia.org/wiki/Algorithm

Our goals for the second half of today include:
* learn how to break apart a big problem into several smaller problems
* Create a sequence of steps for automatically solving these problems
* Pattern these small solutions together in such a way that together, they automatically solve the large problem

What is an algorithm?
* Algorithm is a concise, correct step-by-step sequence of steps to solve a problem.
* Algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.
* Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks.

Algorithms resemble recipes.
* Recipes tell you how to accomplish a task by performing a number of steps.
* For example, to bake a cake the steps are: preheat the oven; mix flour, sugar, and eggs thoroughly; pour into a baking pan; and so forth.

And why do we care to discuss algorithms here?
* To be successful in writing programs, you need to write, or at least think, algorithms.

3.3.2 Pseudocode

https://en.wikipedia.org/wiki/Pseudocode
* Step-by-step verbal outline of your code that you can gradually transcribe into programming language.
* Many programmers use it to plan out the function of an algorithm before setting themselves to the more technical task of coding.
* Informal guide, a tool for thinking through program problems
* Shows how a computing algorithm should and could work.
* Intermediate step in programming, in between the initial planning stage and the stage of writing actual, executable code.
* Allows the designer to focus on the logic of the algorithm without being distracted by details of language syntax.

Good pseudocode practices
* Pseudocode needs to be complete.
* It describes the entire logic of the algorithm so that implementation becomes a rote mechanical task of translating line by line into source code.
* In general, the vocabulary used in the pseudocode should be the vocabulary of the problem domain, not of the implementation domain.
* Problem-focused process, not code-focused process!

3.3.2.1 Flowcharts

https://en.wikipedia.org/wiki/Flowchart
* A flowchart is a type of diagram that represents a work-flow or process.
* A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task.

3.3.2.2 Basic elements

What are the basic constructs of pseudocode?
Three high level constructs for flow of control are sufficient to implement any “proper” algorithm:

  1. SEQUENCE is a linear progression where one task is performed sequentially after another.
  2. WHILE is a loop (repetition) with a simple conditional test at its beginning.
  3. IF-THEN-ELSE is a decision (selection) in which a choice is made between two alternative courses of action.

Although these constructs are sufficient, it is often useful to include three more constructs:

  1. REPEAT-UNTIL is a loop with a simple conditional test at the bottom.
  2. CASE is a multi-way branch (decision) based on the value of an expression. CASE is a generalization of IF-THEN-ELSE.
  3. FOR is a “counting” loop.

More primitively,
1) sequence,
2) test, and
3) conditional jump suffice,
but that’s a discussion for another day!

3.3.2.3 Example 1: find the largest number

Problem: find the largest number in a list of random numbers
Solution: learn how to think linearly and squentially

3.3.2.3.1 Iterative solution

A simple algorithm describes how to find the largest number in a list of numbers of random order.
Finding the solution requires looking at every number in the list.
From this, follows a simple algorithm, which can be stated in a high-level description in English prose, as:

High-level description:
* If there are no numbers in the list then there is no highest number.
* Assume the first number in the list is the largest number in the list, remember only it.
* For each remaining number in the list:
* if this number is larger than the current largest number, consider this number to be the largest number in the list, then remember only that one instead.
* When there are no numbers left in the set to iterate over, consider the current largest number you’re remembering to be the largest number of the list.

Pseudo-code
~~~
Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L
~~~

`<-` denotes assignment
`"return"` terminates the algorithm
`.` denotes a property of an object

Steps:
if L.size == 0, then
    return null
largest <- L[0]
for each item in L, do
    if item > largest, then
        largest <- item
return largest

Similar flow-chart
01-Computation/find-largest-number.png
Note: how does this differ from the pseudo-code above?

How to learn to solve such a problem algorithmically?
Break it down into smaller steps, sequential linear, and elemental progress.
https://fiftyexamples.readthedocs.io/en/latest/algorithms.html (below)

Problem:
* Given a list of positive numbers, return the largest number in the list.

Inputs:
* A list L of positive numbers.
* This list must contain at least one number.
* Asking for the largest number in a list of no numbers is not a meaningful question.

Outputs:
* A number n, which will be the largest number of the list.

Algorithm:
1. Set max to 0.
2. For each number x in the list L, compare it to max. If x is larger, set max to x.
3. At the end of the list, max is now set to the largest number in the list.

Note: don’t expect to understand the syntax of the below code yet; it’s just a preview example.
One reason people like python is because it reads like pseudo-code (easy to read program logic).
You may actually find this somewhat readable.

Flowchart for below code (auto-generated by a project of mine, py2cfg)
01-Computation/01_find_max_iter_cfg.svg
Python code, where find_max() is like a named algorithmic process:
01-Computation/01_find_max_iter.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

from typing import List

def find_max(L: List[int]) -> int:
    max = 0
    for x in L:
        if x > max:
            max = x
    return max

print(find_max([11, 23, 58, 31, 56, 77, 43, 12, 65, 19]))

Does this meet the criteria for being an algorithm?
* Is it unambiguous?
* Yes. Each step of the algorithm consists of primitive operations, and translating each step into Python code is very easy.
* Does it have defined inputs and outputs?
* Yes.
* Is it guaranteed to terminate?
* Yes. The list L is of finite length, so after looking at every element of the list the algorithm will stop.
* Does it produce the correct result?
* Yes.
* In a formal setting you would provide a careful proof of correctness.
* In the next section I’ll sketch a proof for an alternative solution to this problem.

What inputs, if any, could cause the last algorithm above to fail?
What is the fix?

3.3.2.3.2 Recursive solution

Algorithms can reference themselves!

Note: don’t expect to understand this code yet; it’s just a preview for the principles!

There can be many different algorithms for solving the same problem.
Here’s an alternative algorithm for find_max():
1. If L is of length 1, return the first item of L.
2. Set a variable, v1 to the first item of L.
3. Set another variable, v2, to the output of performing find_max() on the rest of L.
4. If v1 is larger than v2, return v1. Otherwise, return v2.

Flowchart for below code (auto-generated)
01-Computation/02_find_max_rec_cfg.svg
01-Computation/02_find_max_rec.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

from typing import List

def find_max(L: List[int]) -> int:
    if len(L) == 1:
        return L[0]
    v1 = L[0]
    v2 = find_max(L[1:])
    if v1 > v2:
        return v1
    else:
        return v2

print(find_max([11, 23, 58, 31, 56, 77, 43, 12, 65, 19]))

Note: This procedure calling itself might seem mind-bending now, but we’ll teach you how to imagine the operation of this algorithm later in the semester!

https://en.wikipedia.org/wiki/Linear_search
In computer science, a linear search or sequential search is a method for finding an element within a list.
It sequentially checks each element of the list until a match is found or the whole list has been searched.

Ask:
What is an algorithm for this problem?
What does the pseudocode look like?

Flowchart and code:
01-Computation/search-flow-chart.png
A version generated by my project py2cfg:
01-Computation/03_seq_search_cfg.svg
01-Computation/03_seq_search.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

from typing import List, Tuple

def sequential_search(dlist: List[int], item: int) -> Tuple[bool, int]:
    pos = 0
    found = False

    while pos < len(dlist) and not found:
        if dlist[pos] == item:
            found = True
        else:
            pos = pos + 1

    return found, pos

print(sequential_search([11, 23, 58, 31, 56, 77, 43, 12, 65, 19], 31))

3.3.3 Some big questions?

3.3.4 Overview of the problem solving process

The whole process
* Someone has a problem
* They write an algorithmic solution to the problem
* They translate that solution into code (Python, C, C++, Bash, Rust, Julia, …), a solution to the problem
* The compiler or interpreter translates their source code into machine code
* The program you write will demand memory space for variables, communication from and to the keyboard and monitor, and possibly other uses of peripherals.
* The OS will schedule the use of these resources of the computer.
* The CPU, RAM, disk drives, etc follow those instructions

3.3.4.1 Wrapping it up

Assuming a complied language:
01-Computation/Development.png
Spend time actually solving the problem be specifying the algorithm BEFORE you write the code!

3.4 Review

Today, I hope that I inspired more questions than I answered, and that you feel intrigued, but unsatisfied!

Next: 02-GitLinuxBash.html