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.
document.querySelector('video').playbackRate = 1.2
Note: Cahoot questions for today are easy gimmies, just to get you used to the system.
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!
https://en.wikipedia.org/wiki/Software
https://en.wikipedia.org/wiki/Programming_language
https://en.wikipedia.org/wiki/Comparison_of_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.
Machine code:
* 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.
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:
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
This is a simple bash program (interpreted):
01-Computation/00_hello_world.sh
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
and everything kind-of in-between
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.
This process produces binary code in a file, a.k.a, “a binary”.
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.
Sometimes the interpreter is doing just-in-time compilation…
There are more than these:
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.
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.
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.
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
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):
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
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.
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
;)
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.
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.
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.
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.
And many more features!
++++++++++++++++++
Cahoot-01.3
What is a program?
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.
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!
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.
What are the basic constructs of pseudocode?
Three high level constructs for flow of control are sufficient to
implement any “proper” algorithm:
Although these constructs are sufficient, it is often useful to include three more constructs:
More primitively,
1) sequence,
2) test, and
3) conditional jump suffice,
but that’s a discussion for another day!
Problem: find the largest number in a list of random
numbers
Solution: learn how to think linearly and
squentially
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
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)
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?
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.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:
A version generated by my project py2cfg:
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))
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
Assuming a complied language:
Spend time actually solving the problem be specifying the algorithm
BEFORE you write the code!
Today, I hope that I inspired more questions than I answered, and that you feel intrigued, but unsatisfied!
Next: 02-GitLinuxBash.html