source.md

Themes

Set your presentation theme:
Black (default) - White - League - Sky - Beige - Simple
Serif - Blood - Night - Moon - Solarized

H:

Structured programming overview

by Jean Pierre Charalambos
Universidad Nacional de Colombia
Presentation best seen online
See also the source code

H:

Index

1. Introduction: Program paradigms
2. Structured programming elements
3. Basic data structures

H:

Introduction

1. Program paradigms
2. Turing completeness

V:

Introduction: Program paradigms

Computational paradigm

Computing problem -> Programming -> Executable

Program paradigm -> Style of programming

V:

Introduction: Turing Machines

A turing machine (TM[I,O]) is an 'abstract' machine such:

Input string (I) -> TM -> Output (O)

O: Output string & halts; or, Calculates forever

You may think of a TM like a program

V:

Introduction: Universal Turing Machine

A universal turing machine (UTM) is a TM'[I',O'] (input string (I') -> TM' -> Output (O')):

where,

I': [TM,I]

O': O

for any TM[I,O]

hence TM'[[TM,I],O]

You may think of a UTM like a computer

V:

Introduction: Turing completeness

A programming language (or a cellular automaton) is said to be Turing complete (or "computationally universal") if it can be used to simulate any Turing machine

V:

Introduction: Program paradigms

A fundamental style of computer programming, serving as a way of building the programs

V:

Introduction: Program paradigms

Machine code

A set of instructions executed directly by a computer's central processing unit (CPU)

Computer lowest-level programming language

Turing complete

N:

Verify machine code Turing completeness, by mapping TM informal description and machine code 'instructions'

V:

Introduction: Program paradigms

Asembly language

Very strong (one-to-one) correspondence between the language and the architecture's machine code instructions

Provides little or no abstraction from machine code

V:

Introduction: Program paradigms

Structured Programming (SP)

Langs that describe, the step-by-step procedure that according to a particular programmer's view, should be followed to solve a specific problem

The efficacy and efficiency of any such solution are both therefore entirely subjective and highly dependent on that programmer's experience, inventiveness and ability

V:

Introduction: Program paradigms

SP: features

Turing completeness (see the [structured program theorem](https://en.wikipedia.org/wiki/Structured_program_theorem))

Elements 1. Control structures: assignments, selection and iteration 2. Functions (subroutines, method, or procedure, etc)

Data structures: (multi-dimensional) Arrays

V:

Introduction: Program paradigms

SP: examples

COBOL

FORTRAN

[C](https://en.wikipedia.org/wiki/C_(programming_language)

V:

Introduction: Program paradigms

Object Oriented Programming (OOP)

Langs that described programs as a group of mutually interactive objects

An object is a _data structure_ for storing user-defined _attributes_ (data or fields), and _methods_ to manipulate them

V:

Introduction: Program paradigms

OOP examples

C++

[C#](https://en.wikipedia.org/wiki/C_Sharp_(programming_language)

[Java](https://en.wikipedia.org/wiki/Java_(programming_language)

[Ruby](https://en.wikipedia.org/wiki/Ruby_(programming_language)

V:

Other paradigms

Declarative programming

Functional programming

Logic programming

Symbolic programming

Multi-paradigm

H:

Structured programming (SP) elements

Control structures ([statements](https://en.wikipedia.org/wiki/Statement_(computer_science)) 1. Assignments 2. Selection: simple and multiple choice 3. Iteration

Functions (subroutines, method, or procedure, etc)

V:

SP elements: Assignments

What is?

A process in imperative programming in which different values are associated with a particular variable name as time passes

V:

SP elements: Assignments

In order to:

The program, in such model, operates by changing its state using successive assignment statements

V:

SP elements: Assignments

// const should be preferred over let (unless the
// variable is expected to change) and var never used
let <variable-name>;
let <variable-name> = <value>;
// const is always to be preferred
const <variable-name> = <value>;

V:

SP elements: Assignments

Examples:

const x = 10; 
let y;
x = 23;//error
y = 32.4;

V:

SP elements: Assignments

Type checking

Use typeof to know the type of variable.

console.log(typeof 42);
// expected output: "number"

console.log(typeof 'poo');
// expected output: "string"

console.log(typeof true);
// expected output: "boolean"

console.log(typeof undeclaredVariable);
// expected output: "undefined"

Closely related is instanceof which will be studied once objects are introduced.

V:

SP elements: Assignments

Augmented assignment: ```a = 2*a;``` can be written as: ```a *= 2;```

Chained assignment: ```a = b = c = d = f = 5;```

V:

SP elements: Simple choice

An "If-then-else" flowchart

V:

SP elements: Simple choice

by example the following code:

for (let i = 5; i < height; i += 5) {
  stroke(255);   // Set the color to white
  if (i < 35) {  // When 'i' is less than 35...
    stroke(0);   //...set the color to black
  }
  line(30, i, 80, i);
}

N:

Blocks ({}) is a section of code which is grouped together. Blocks consist of one or more declarations and statements.

V:

SP elements: Simple choice

produces:

V:

SP elements: Multiple choice

A switch flowchart

V:

SP elements: Multiple choice

For example:

let num = 1;

switch(num) {
  case 0: 
    console.log("Zero");  // Does not execute
    break;
  case 1: 
    console.log("One");  // Prints "One" on the console
    break;
}

V:

SP elements: Multiple choice

second example:

let letter = 'N';

switch(letter) {
  case 'A': 
    console.log("Alpha"); // Does not execute
    break;
  case 'B': 
    console.log("Bravo"); // Does not execute
    break;
  default:                // Default executes if the case labels
    console.log("None");  // don't match the switch parameter
    break;
}

V:

SP elements: Multiple choice

third example:

// Removing a "break" enables testing
// for more than one value at once

let letter = 'b';

switch(letter) {
  case 'a':
  case 'A': 
    console.log("Alpha");  // Does not execute
    break;
  case 'b':
  case 'B': 
    console.log("Bravo");  // Prints "Bravo"
    break;
}

V:

SP elements: For loops

for (INITIALIZATION; CONDITION; AFTERTHOUGHT) 
{
    // Code for the for-loop's body goes here
}

V:

SP elements: For loops

The following code:

for (let i = 0; i < 80; i = i+5) {
  line(30, i, 80, i);
}

V:

SP elements: For loops

produces:

V:

SP elements: For loops

The following code:

let a = [5, 20, 25, 45, 70]; 
    
function setup() {
  createCanvas(400, 400);
  noLoop();
}
    
function draw() { 
  background(255,255,0);
  for (let i=0; i < a.length; i++) {
    line(0, a[i], 50, a[i]);
  }
}

V:

SP elements: For loops

produces:

V:

SP elements: While loops

A while flowchart

V:

SP elements: While loops

while (true) 
{
    //do complicated stuff
    if (someCondition) break;
    //more stuff
}

V:

SP elements: While loops

The following code:

let i = 0;
while (i < 80) {
  line(30, i, 80, i);
  i = i + 5;
} 

V:

SP elements: While loops

produces:

V:

SP elements: Functions

A sequence of program instructions that perform a specific task, packaged as a unit

This unit can then be used in programs wherever that particular task should be performed

Subprograms may be defined within programs, or separately in libraries that can be used by multiple programs

V:

SP elements: Functions

Features

Decomposing a complex programming task into simpler steps

Enabling reuse of code across multiple programs

Dividing a large programming task among letious programmers, or letious stages of a project

Hiding implementation details from users of the subroutine

Improving traceability

V:

SP elements: Functions

Conventions for passing arguments

Convention	Description
Call by value	Argument is evaluated and copy of value is passed to subroutine
Call by reference	Reference to argument, typically its address is passed
Call by sharing	References are passed by value

V:

SP elements: Functions

The following:

/*
Esta funcion retorna el n-simo termino de la serie de fibonacci
*/
function fibonacci(n) {
  let x = 0, y = 1, z = 1;
  for (let i = 1; i < n; i++) {
    x = y;
    y = z;
    z = x + y;
  }
  return x;
}

let squares = 5; 

function setup() {
  createCanvas(400, 400);
  noLoop();
}
    
function draw() {
  background(255,0, 255);
  let w = width / squares;
  for(let i = 0; i < squares; i++) {
    fill(map(fibonacci(i+1), fibonacci(squares), 0, 0, 255));
    rect(i*w,0,w,50);
  }
}

V:

SP elements: Functions

produces:

V:

SP elements: Recursive functions

The following:

/*
Esta funcion retorna el n-simo termino de la serie de fibonacci
*/
function fibonacci(n) {
  // salida de la recursion
  if(n == 1)
    return 0;
  if(n == 2)
    return 1;
  // avance de la recursion:
  if( n > 2)
    return fibonacci(n-2) + fibonacci(n-1);
  // si n es negativo o 0
  return -1;
}

let squares = 5; 
    
function setup() {
  createCanvas(400, 400);
  noLoop();
}
    
function draw() {
  background(255,0, 255);
  let w = width / squares;
  for(let i = 0; i < squares; i++) {
    fill(map(fibonacci(i+1), fibonacci(squares), 0, 0, 255));
    rect(i*w,0,w,50);
  }
}

V:

SP elements: Recursive functions

produces:

H:

Arrays

excerpt from p5.js

An array is a list of data. Each piece of data in an array is identified by an index number representing its position in the array. Arrays are zero based, which means that the first element in the array is [0], the second element is [1], and so on.

more details here

V:

Arrays

The following code:

let coswave = [];
    
function setup() {
  createCanvas(720, 360);
  for (let i = 0; i < width; i++) {
    let amount = map(i, 0, width, 0, PI);
    coswave[i] = abs(cos(amount));
  }
  background(255);
  noLoop();       
}
    
function draw() {
  let y1 = 0;
  let y2 = height/3;
  for (let i = 0; i < width; i+=3) {
    stroke(coswave[i]*255);
    line(i, y1, i, y2);
  }
        
  y1 = y2;
  y2 = y1 + y1;
  for (let i = 0; i < width; i+=3) {
    stroke(coswave[i]*255 / 4);
    line(i, y1, i, y2);
  }
        
  y1 = y2;
  y2 = height;
  for (let i = 0; i < width; i+=3) {
    stroke(255 - coswave[i]*255);
    line(i, y1, i, y2);
  }        
}

V:

Arrays

produces:

V:

Arrays

A multi-dimensional array is an array of arrays

See the coding train tutorial

V:

Arrays

The following code:

let distances = [];
let maxDistance;
let spacer;
    
function setup() {
  createCanvas(720, 360);
  maxDistance = dist(width/2, height/2, width, height);
  for (let x = 0; x < width; x++) {
    distances[x] = []; // create nested array
    for (let y = 0; y < height; y++) {
      let distance = dist(width/2, height/2, x, y);
      distances[x][y] = distance/maxDistance * 255;
    }
  }
  spacer = 10;
  noLoop();  // Run once and stop
}
    
function draw() {
  background(0);
  // This embedded loop skips over values in the arrays based on
  // the spacer variable, so there are more values in the array
  // than are drawn here. Change the value of the spacer variable
  // to change the density of the points
  for (let x = 0; x < width; x += spacer) {
    for (let y = 0; y < height; y += spacer) {
      stroke(distances[x][y]);
      point(x + spacer/2, y + spacer/2);
    }
  }        
}

V:

Arrays

produces:

H:

References

Language theory

• Introduction to automata theory, languages, and computation

Stack-overflow

• Can all iterative algorithms be expressed recursively?
• Can every recursion be converted into iteration?

Wikipedia

• Turing completeness
• Programming paradigm
• Structured programming

Processing

• P5.js