FIT2102
Programming Paradigms Workshop 1
Intro – Levels of Abstraction Models of Computation JavaScript and Functions
Faculty of Information Technology
FIT 2102 Structure
We will:
– learn to think about programming languages as providing different abstractions of computation and differentiate between syntax and semantics
– learn about important programming paradigms that provide different models
for computation – Imperative
– Functional – Declarative
– study several languages that are distinguished by the types of abstractions they provide
– study some theory (lambda calculus / a little bit of category theory) that allow us to think abstractly about programming
Schedule
Week 1:
– Intro
– Models of Computation
– JavaScript and functions
Week 2:
– JavaScript, objects and higher-order functions
Week 3:
– Compiled vs Dynamic Languages
– TypeScript
Week 4:
– Lazy lists, FRP, Assignment 1
Week 5:
– Higher-order Functions
– Combinators / Currying / Lambda Calculus
Week 6:
– Haskell
Week 7:
– Haskell – type-classes: Maybe
– Assignment 1 due
Week 8:
– Haskell – Functor and Applicative
– Assignment 2
Week 9:
– Haskell – Foldable and Traversable
Week 10:
– Haskell – Monad and IO
Week 11:
– Haskell – Parser Combinators
Week 12 (Guest lecture):
– Constraint Programming – MiniZinc
– Assignment 2 due
Why don¡¯t we study language X?
The most important part of this course is the concepts we learn, which should be transferable to lots of different languages
– i.e. semantics vs syntax
We can¡¯t study every popular language in 12 weeks. The ones we do look at are
chosen because, either:
– They are immensely popular, have interesting features, are used in interesting ways, and you will undoubtedly encounter them in the real world (JavaScript/TypeScript); or,
– They represent interesting examples of their paradigm (PureScript/Haskell/MiniZinc).
Syntax vs Semantics
# python code:
def sumTo(n):
sum = 0
for i in range(0,n):
sum = sum + i
return sum
// JavaScript code:
function sumTo(n) {
let sum = 0;
for(let i = 0; i < n; i++) {
sum += i; }
return sum; }
What is (and isn¡¯t) FIT2102
We are going to learn some important concepts that will give you a deeper understanding of:
- what programming is
- how to do it well
- where it comes from
- where it might be going in the future
FIT 2102 is not a complete ¡°Programming Languages¡± course. We are not learning how to:
- make a compiler (though we will discuss how compilers work to some degree)
- design a new language (though we will reflect on language design)
Pedagogy
Productive failure (PF) Active learning (AL)
Chowrira et al., ¡°Productive Failure¡±, Science of Learning, NPJ, 2019
Assessment
¡ñ Tutorial homework 40%
¡ð Tutorials will be completed in groups and assessed via in-class interviews
¡ð Your homework marks will be based on:
¡ö Timely task completion submitted via Moodle
¡ö Demonstrated understanding of the answers in interviews
¡ñ Assignment 1 30%
¡ñ Assignment 2 30%
¡ð Both assignments must be completed individually
¡ð The usual plagiarism checks will apply
Lab Assessment
- Most lab tasks require only a few lines of code
- No one problem should take more than around 30 minutes, most a lot less
- If you find you have not been able to progress on a particular problem after
significant time
- write down a question in a comment in the code
- try to break the question into sub-questions
- If still unable to make progress, bring the questions to the lab.
Learning Outcomes for Workshop 1
After Workshop 1 you should be able to:
- Explain the difference between Syntax and Semantics in programming languages
- Explain the need for abstraction from machine instructions to high-level languages
- Contrast imperative loops with recursive loops
- Explain how the stack is used in functions and how recursive functions can overflow the stack
- Create small JavaScript programs with functions
The Good Old Days
Margaret Hamilton
Lead Apollo flight software designer
Engineers built seriously complex software at the Machine level
Apollo 11 Source Code
INDEXI DEC 4 DEC 2 DEC 0 DEC 4
source
# **********
# **********
# **********
# ********** CONSTANTS *********
DON'T TOUCH THESE
***********
***********
***********
Levels of Abstraction
¡°High-Level¡± Languages - compiler or interpreter transforms human readable instructions to machine operations
Assembly Language - still requires a compiler, but operations correspond one-to-one with machine operations
Machine Language - operations and their arguments (operands) represented by binary numbers and executed either directly in hardware or by a microprogram embedded in the microprocessor
Basic computer architecture
ALU - Arithmetic Logic Unit CU - Control Unit
Clock - Synchronises CPU operations with other system components
Data bus - transfers instructions and operations between CPU and memory
Address bus - When the CPU needs to read or write to a memory location it specifies that location on the address bus
Data bus, I/O bus
Control bus
Registers
Central Processor Unit (CPU)
ALU
CU
Clock
Memory
I/O Devices
Registers Registers
Address bus
The von Neumann model
A model for computation closely matching actual computer architecture.
Has in common with the Turing Machine model an imperative, ¡°instruction following¡± paradigm.
We will be learning about an alternative model for computation: the Lambda Calculus
Input
Output
Control Unit
ALU Arithmetic Logic Unit
Memory
Not Examinable in 2019
Instruction Execution Cycle
1. CPU fetches instruction from instruction queue, increments instruction pointer
2. CPU decodes instruction and decides if it has operands
3. If necessary, CPU fetches operands from registers or memory
4. CPU executes the instruction
5. If necessary, CPU stores result, sets status flags, etc.
x86 Data Registers
Not Examinable in 2019
AH
AL
Just some of the registers on a modern x86 chip...
RAX
8-bits 8-bits AX
EAX
Name
64-Bit
32-Bit
16-Bit
8-Bit (High)
8-Bit (Low)
Accumulator
RAX
EAX
AX
AH
AL
Base
RBX
EBX
BX
BH
BL
Counter
RCX
ECX
CX
CH
CL
Data
RDX
EDX
DX
DH
DL
Not Examinable in 2019
Let¡¯s make a program!
.386 ; choose 32 bit mode
.model flat, stdcall ; execution model (don't worry about it for now)
ExitProcess PROTO, dwExitCode:DWORD ; declares this special external procedure and the type of its parameter
.code
main PROC
mov eax, 5
add eax, 6
invoke ExitProcess, eax
main ENDP
END main
; opens the code section
; here's where our "main" procedure begins
; move 5 into eax register
; add 6 to the value in the eax register
; exit returning eax as the result code
result
Not Examinable in 2019
Basic instructions: arithmetic
[label:] mnemonic [operands] [; comment]
Operands can be memory locations, registers or numeric literals
Mnemonic
Operands
Description
mov
dest, src
Move (copy) contents of src into dest
add
y, x
Add contents of x to y (result in y)
sub
y, x
Subtract x from y (result in y)
mul
x
Multiply eax by x (result in eax)
div
x
Divide eax by x, result in eax, remainder in edx
xor
y, x
Bitwise exclusive or (Tip, to zero a register: xor eax, eax)
Not Examinable in 2019
Basic instructions: jumps
Mnemonic
Operands
Description
jmp
label
Jump unconditionally to label
loop
label
If ecx > 0 jump to label and decrement ecx
cmp
x, y
Compare x and y and set the flags register accordingly
je
label
Jump to label if result of previous cmp operation was equal
j[ne|l|le|g|…]
label
Jump to label if ¡ü not equal, <, <=, >, etc…
Not Examinable in 2019
Basic instructions: stack operations
Code Address Stored values push 3 esp 00001000 00000003
Mnemonic
Operands
Description
push
x
Push x onto the top of the stack, decrement esp
pop
x
Take top value off stack, put into x and increment esp
Not Examinable in 2019
Basic instructions: stack operations
Code Address
mov eax,5 esp 00000FFC
Stored values
00000005
00000003
push eax
00001000
Mnemonic
Operands
Description
push
x
Push x onto the top of the stack, decrement esp
pop
x
Take top value off stack, put into x and increment esp
Not Examinable in 2019
Basic instructions: stack operations
Code Address
mov var1,1 esp 00000FF8
Stored values
00000001
00000005
00000003
push var1
00000FFC
00001000
Mnemonic
Operands
Description
push
x
Push x onto the top of the stack, decrement esp
pop
x
Take top value off stack, put into x and increment esp
Not Examinable in 2019
Basic instructions: stack operations
Code Address
pop var2 esp 00000FFC 00001000
Stored values Result
00000005 eax = 1 00000003
Mnemonic
Operands
Description
push
x
Push x onto the top of the stack, decrement esp
pop
x
Take top value off stack, put into x and increment esp
Not Examinable in 2019
Basic instructions: stack operations
Code Address Stored values Result pop eax esp 00001000 00000003 var2 = 5
Mnemonic
Operands
Description
push
x
Push x onto the top of the stack, decrement esp
pop
x
Take top value off stack, put into x and increment esp
Not Examinable in 2019
Basic instructions: procedures
.386
.model flat, stdcall
ExitProcess PROTO, dwExitCode:DWORD
.data
varA DWORD 1
varB DWORD 2
varC DWORD 3
.code
main PROC
mov ebx, varA
mov ecx, varB
mov eax, varC
call sum3
invoke ExitProcess, eax
main ENDP
sum3 PROC
add eax, ebx
add eax, ecx
ret sum3 ENDP
; call the procedure
; result is 1+2+3=6
END main
; need to end procedures (other than main) in ret
JavaScript
JavaScript (aka EcmaScript), is an incredibly ubiquitous language that has supported ¡°functions as values¡± since its inception.
As a result, server and client side JavaScript in the wild makes heavy use of
Functional Programming (FP) patterns.
You will see sophisticated FP influence in many JS libraries (JQuery, React, D3, RxJS, Mocha and many more).
FP makes these libraries flexible and robust.
JavaScript 101: defining variables and functions
const z = 1; // constant (immutable variable) at global scope
/**
* define a function called “myFunction” with two parameters, x and y
* which does some silly math, prints the value and returns the result
*/
function myFunction(x, y) {
let t = x + y; // t is mutable
t += z; // += adds the result of the expression on the right to the value of t
const result = t // semi colons are not essential (but can help to catch errors)
console.log(“hello world”) // prints to the console
return result; // returns the result to the caller
}
JavaScript 101: if statements
/**
* get the greater of x and y
*/
function maxVal(x, y) {
if (x >= y) {
return x;
} else {
return y;
} }
JavaScript 101: if statements
/**
* get the greater of x and y
*/
function maxVal(x, y) {
if (x >= y) return x;
return y; }
JavaScript 101: if statements
conditional expression syntax:
/**
* get the greater of x and y
*/
function maxVal(x, y) {
return x >= y ? x : y;
}
JavaScript 101: Loops
/**
* sum the numbers up to and including n
*/
function sumTo(n) {
} }
let sum = 0;
while (n) {
// because Boolean(0) === false
// operator fun! Cheatsheet coming…
sum += n–;
return sum;
JavaScript 101: Loops
/**
* sum the numbers up to and including n
*/
function sumTo(n) {
let sum = 0;
for (let i = 1; i <= n; i++) {
sum += i; }
return sum; }
JavaScript 101: Basic Operator Cheat Sheet
Binary Operators:
Unary Operators:
i++ // post-increment
++i // pre-increment
i-- // post-decrement
--i // pre-decrement
!x // not x
In-place math operators:
x +=
// add result of expr to x
// also -=, *=, /=, |=, &=.
x % y
x == y
x != y
x === y
x !== y
a && b a || b
a & b a | b
// modulo
// loose* equality
// loose* inequality
// strict* equality
// strict* inequality
// logical and
// logical or
// bitwise and
// bitwise or
Ternary Conditional Operator:
* Loose (in)equality means type conversion may occur
Use strict (in)equality if type is expected to be same
Live coding exercise 1:
To be announced…
You will work with your table group to complete this task. You might like to use a shared editor like codeshare.io Remember to run the tests before you submit your answer
JavaScript 101
Recursive Loops:
/**
* sum the numbers up to n
*/
function sumTo(n) {
if (n === 0) return 0; // base case
return n + sumTo(n-1); // inductive step
}
We consider this recursive loop a more ¡°declarative¡± coding style than the imperative loops.
It is closer to the inductive definition of sum than a series of steps for how to compute it.
– No mutable variables used
– Each expression in this code is
¡°pure¡±: it has no effects outside the
expression.
– Therefore: this code has the property
of referential transparency.
– The code succinctly states the loop
invariant.
A rather serious caveat:
Too many levels of recursion will cause a stack overflow.
JavaScript 101
Recursive Loops:
/**
* sum the numbers up to n
*/
function sumTo(n) {
return n ? n + sumTo(n-1) : 0;
}
We consider this recursive loop a more ¡°declarative¡± coding style than the imperative loops.
It is closer to the inductive definition of sum than a series of steps for how to compute it.
– No mutable variables used
– Each expression in this code is
¡°pure¡±: it has no effects outside the
expression.
– Therefore: this code has the property
of referential transparency.
– The code succinctly states the loop
invariant.
A rather serious caveat:
Too many levels of recursion will cause a stack overflow.
Live coding exercise 2:
To be announced…
JavaScript 101: First higher-order function
function square(x) {
return x * x;
}
function sumTo(f, n) {
return n ? f(n) + sumTo(f, n-1) : 0;
}
sumTo(square, 10) > 385
A higher-order function is one that: – takes a function as argument; – or returns a function.
Conclusion
Assembly language offers minimal abstraction over the underlying computer architecture, it offers:
– the ability to name operations and memory locations symbolically;
– the ability to define procedures (more recently);
– conveniences for dealing with arrays and macros (not examined here)
C is adds more understandable syntax,
but is still close to the machine execution model.
Languages we examine in future lectures will depart further and further from the underlying (von Neumann) computer architecture.
Conclusion (cont…)
JavaScript is basically an imperative language with C or Java-like syntax, except that it is:
– Interpreted
– Functions are objects which can be assigned to variables
In coming weeks we will incorporate more ¡°functional¡± abstractions into our JavaScript coding, before moving onto a language which significantly departs from the imperative model.
Imperative programming involves telling the computer how to compute step-by-step Declarative programming describes what you want to do, not how you want to do it