程序代写代做代考 flex Haskell C js javascript x86 Lambda Calculus interpreter computer architecture compiler jquery assembly Java clock FIT2102

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