class: center, middle ### COMP26020 Programming Languages and Paradigms Part 1: C Programming *** # The Main Programming Paradigms ??? - Hello everyone. - In this video we will learn about the main programming paradigms, example of languages implementing them, and what are the kind of software engineering problems they are good at solving. --- # Main Programming Paradigms and Sub-Paradigms - **Imperative** - **Structured** (or procedural) - **Object Oriented** - **Concurrent** - **Declarative**: - **Functional** - **Concurrent** Note that there are many other paradigms! ??? - These are some of the main programming paradigms. - They generally belong to one of the two high level paradigms, imperative or declarative. - Note that I just picked the main ones but there are much more. --- # **Imperative** Programming Paradigm - Programmer describes **sequences of statements** manipulating the program state - I.e. describes *how to obtain the computation results* - Basically a cooking recipe .center[] ??? - As we saw in the JavaScript example the imperative paradigm requires the programmer to describe the computation step by step, as a sequence of statements, a bit like a cooking recipe. --- # **Imperative** Programming Paradigm Example: Intel x86-64 assembly ```asm .global _start .text quit: # exit(0) mov $60, %rax # system call 60 is exit xor %rdi, %rdi # we want return code 0 syscall # invoke operating system to exit _start: # write(1, message, 14) mov $1, %rax # system call 1 is write mov $1, %rdi # file handle 1 is stdout mov $message, %rsi # address of string to output mov $14, %rdx # number of bytes syscall # invoke operating system to do the write jmp quit # jump to the quit label above message: .ascii "Hello, world!\n" ``` .codelink[<a href="src/imperative-asm.S" download>`02-main-programming-paradigms/imperative-asm.S`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a>] ??? - Here is an example in x86-64 assembly language. - Note that for all the code snippets I give in these slides the two links at the bottom will lead you to a fully working program as well as instructions on how to run it. - I won't go into the details but in this program instructions are executed one after the other to print a message on the console. - We can assemble it an run it as follows. - An we get our message. --- class: center, middle <div style="text-align:center"><img src="include/spaghetti.svg" width=400 /></div> ??? - Assembly is purely imperative is very low level, so it has some nice benefits such as very good performance and low memory footprint. - It is also the only way to realise some low level operations that are needed when you write things like an OS or a virtual machine monitor. - Now the problem with assembly is that it's not structured. - In terms of control flow there is no clear notion of functions, loops, and so on. - You get what is called spaghetti code. - So even a medium sized code becomes very hard to understand and reason about. --- class: middle <div style="text-align:center"><img src="include/spaghetti2.png" width=900 /></div> ??? - Here is a quote from a question on stack overflow. - Someone has to take over an assembly program written a long time ago by someone else. - There is no documentation. - He says "The program--written as a single file--is a maze of CALL and LJMP statements (about 1200 total), with subroutines having multiple entry and/or exit points, if they can be identified as subroutines at all." - There is no good solution to that problem. -- <div style="text-align:center"><img src="include/spaghetti3.png" width=800 /></div> ??? - Here is one of the answers. - Basically it says "you are screwed" -- Other examples of unstructured imperative languages: early versions of FORTRAN, COBOL, BASIC ??? - Other examples of purely imperative languages are early versions of FORTRAN, COBOL, basic --- # **Imperative Structured** Programming Paradigm - The programmer uses advanced **control flow operations** - Loops, conditionals, procedures - Compared to pure imperative, easier to describe/reason about complex/large programs <div style="text-align:center"><img src="include/control-flow.png" width=700 /></div> ??? - So to be able to write bigger programs we need to use structure imperative programming. - It includes control flow operations and the notion of procedures or functions. - It makes it much easier to reason about large programs. --- # **Imperative Structured** Programming Paradigm Example: C ```c /* Check if a number is prime */ int is_prime_number(int number) { if(number < 2) return 0; for(int j=2; j<number; j++) if(number % j == 0) return 0; return 1; } int main(void) { /* Check which of the first 10 natural integers are prime */ int i; int total_iterations = 10; for(i=0; i<total_iterations; i++) if(is_prime_number(i)) printf("%d is a prime number\n", i); else printf("%d is not a prime number\n", i); return 0; } ``` .codelink[<a href="src/imperative-structured.c" download>`02-main-programming-paradigms/imperative-structured.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/5ODXUi734KOeS" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ??? - Here is an example in C. - Once again the instructions within a function are executed one after the other. - But we can see some control flow operations: loops, conditionals, and function calls. - If we compile it and run it, it prints the list of the first 10 integers and which ones are prime or not --- # **Imperative Structured** Programming Paradigm <div style="text-align:center"><img src="include/structured.png" width=800 /></div> ??? - Structured imperative programming originally appeared in languages such as ALGOL, Pascal, ADA, etc. - Today most programming languages are structured for obvious reasons, compared to unstructured programming: - their modularity makes it easier to write code for medium/large programs. - There is Less complexity and the code is easier to understand. - It also eases testing and debugging - Modern low-level imperative structural languages without too much additional layers include C and FORTRAN. - We will see that they are very efficient for HPC and systems software development. - We we also see that they have big memory safety issues. --- # **Imperative Object-Oriented** Programming Paradigm - **Encapsulation** of code and the associated data into objects .leftcol[ Non-OO (procedural): ```c operation(data) ```] .rightcol[ OO: ```cpp data.operation() ```] .center[] ??? - A very popular programming paradigm is the object oriented one. - The programmer links together the data and the code manipulating it into objects. - While in non object oriented languages you call a function out of nowhere passing data as parameters. - With object oriented this function can be called upon a given data, for example here with the dot operator. - Object oriented also defines concepts such as inheritance and polymorphism that facilitates code reuse and organization. - For example here we have two types of objects, square and circle, reusing part of the code from another type of object, shape. --- # **Imperative Object-Oriented** Programming ```cs // Example in C# abstract class Shape { public abstract void printMe(); /* ... */ } class Square : Shape { override void printMe() {Console.WriteLine ("Square id: {0}, side: {1}", _id, _side);} /* ... */ } class Cicle : Shape { override void printMe() {Console.WriteLine ("Circle id: {0}, radius: {1}", _id, _radius);} } public class MainClass { public static void Main(string[] args) { Square mySquare = new Square(42, 10); Circle myCircle = new Circle(242, 12); mySquare.printMe(); myCircle.printMe(); } } ``` .codelink[<a href="src/imperative-oo.cs" download>`02-main-programming-paradigms/imperative-oo.cs`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/693b7s8p6i87q" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ??? - Here is a program implementing these object types, that are actually named classes: shape, square and circle. - We create two objects and call the printme function on them. - It is written in C sharp. - You can use the links below to try it out. --- # **Imperative Object-Oriented** Programming ```c++ // Example in C++ class Shape { public: virtual void printMe(void) = 0; /* ... */ }; class Square : Shape { public: void printMe(void) { cout << "Square id: " << _id << ", side: " << _side << endl; } /* ... */ }; class Circle : Shape { public: void printMe(void) { cout << "Circle id: " << _id << ", radius: " << _radius << endl; } /* ... */ }; int main(void) { Square mySquare = Square(42, 10); Circle myCircle = Circle(242, 12); mySquare.printMe(); myCircle.printMe(); } ``` .codelink[<a href="src/imperative-oo.cpp" download>`02-main-programming-paradigms/imperative-oo.cpp`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/15xo4S0DPVpUh" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ??? - An here's the version in C++. - As you can see it looks very similar. - This illustrates well the fact that paradigms defines a programming style. --- # **Imperative Object-Oriented** Programming Paradigm <div style="text-align:center"><img src="include/object.png" width=600 /></div> - Well suited to represent problems with a lot of state/operations - GUI, simulators, video games, business management software, and many other use cases - Ease reasoning about / organising large codebases - Can sometimes be overkill for small programs ??? - A few examples of object oriented languages are C++, C sharp, or java. - There are many others. - Object oriented languages are good to represent problems with a lot of state and operations, for example when we have to process a lot of data that can be described as attributes. - For example simulators, video games, and so on. - This paradigm also helps in organising and understanding large code bases but for small programs it can sometimes be overkill --- # **Imperative Concurrent** Programming Paradigm - The programmer uses execution threads/processes to describe interleaving and/or parallel computation flows Example in C with POSIX threads: ```c static void *thread_function(void *argument) { int id = *(int *)argument; for(int i=0; i<10; i++) printf("Thread %d running on core %d\n", id, sched_getcpu()); } int main(void) { pthread_t threads[NUMBER_OF_THREADS]; int thread_ids[NUMBER_OF_THREADS]; for(int i=0; i<NUMBER_OF_THREADS; i++) { thread_ids[i] = i; pthread_create(&threads[i], NULL, &thread_function, &thread_ids[i]); } /* ... */ ``` .codelink[<a href="src/pthread.c" download>`02-main-programming-paradigms/pthread.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a>] ??? - Another imperative paradigm is the concurrent one. - With this paradigm the programmer uses various features provided by the language to describe parallel and interleaving operations. - Here we have an example with a C library named the POSIX threads. - The important part is within the for loop where we create a certain number of threads. - These threads are parallel execution flows and each will execute the function named thread function. --- # **Imperative Concurrent** Programming Paradigm Execution example with 4 threads and 2 parallel processing units (cores): <div style="text-align:center"><img src="include/concurrency.svg" width=600 /></div> - Many imperative languages provide ways to exploit concurrency: - Shared-memory threads/processes in C/C++, Java, Python, etc. - Message passing (for example MPI) in C/C++/FORTRAN - Semi-automatic loop paralelization with libraries such as OpenMP - GPU programming with CUDA - ... - Use cases: HPC, distributed computing, graphic processing, etc. ??? - Here is an execution example of 4 threads on a CPU with 2 cores. - Core 1 starts with thread 1, that gets kicked off the CPU by thread2 after some time, comes back later, and so on. - Something similar happens on core 2 with thread 3 and thread 4. - A concurrent programming language describes in particular how the execution flows can communicate, can they share data structures, and if yes what is the consistency of that sharing. - There are many methods for concurrent programming in imperative languages. - They include shared memory threads and processes, message passing and automatic parallelization libraries, GPU programming languages, and so on. - Important use cases for concurrent programming are of course high performance and distributed computing, graphic processing, etc. --- # **Declarative** Programming Paradigm .center[The programmer describes the **meaning/result of computations**] ```html <html> <!-- ... --!> <body> <h1> Hello, world! </h1> <p> Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vestibulum sed leo sit amet urna accumsan aliquam. Fusce et aliquet nibh. </p> </body> </html> ``` See the result [here](src/listing7.html). These slides are also created with a combination of 2 declarative languages: HTML and Markdown -- try typing ctrl+U :) ??? - Now let's switch to declarative paradigms. - Contrary to imperative programming where the programmer describes a sequence of instructions, in other words the way to obtain a certain result, with declarative programming the programmer describes how the result should look like. - A good example of a pure declarative language is HTML. - Here I am constructing a web page, declaring elements such as headings and paragraphs with tags. - We can see the result page here. - Fun fact: these slides are also realised with declarative languages. - Load them in your browser and type control plus u to see the sources. --- # **Declarative** Programming Paradigm - High level of abstraction - Code can easily become convoluted - Languages: HTML, SQL, XML, CSS, Latex (non-Turing complete) - Usage: document rendering, structured data storage and manipulation ??? - Declarative programming is at a much higher level of abstraction compared to imperative programming that is closer to the machine model - One can describe complex programs with few lines of code and the low level implementation details are abstracted - A downside is that the code can easily become convoluted and hard to understand in large programs - Some examples of pure declarative languages include: HTML, SQL, XML, CSS, Latex. - Note that these are not Turing complete. - Pure declarative programming is useful for document rendering, structured data storage and manipulation --- # **Declarative Functional** Programming Paradigm - Calling and composing functions to describes the program Example in Haskell: ```haskell add_10 x = x + 10 twice f = f . f main = do print $ twice (add_10) 7 ``` .codelink[<a href="src/functional.hs" download>`02-main-programming-paradigms/functional.hs`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a>] ??? - A very important declarative subparadigm is functional programming. - With this paradigm, the programmer calls and composes functions to describe the program. - Here is an example in Haskell. - We define a function add_10 that takes one parameter and adds ten to it. - We also define another function that takes a function as parameter and applies it twice. - The last line will print 27 as it first adds 10 to 7 and passes the result as parameter to a second invocation of add 10. --- # **Declarative Functional** Programming Paradigm ```ml (* Example in OCaml *) let width, height = 800, 600 let pi = 4. *. atan 1.;; let endpoint x y angle length = x +. length *. cos angle, y +. length *. sin angle;; let drawLine x y angle length width = let x_end, y_end = endpoint x y angle length in set_line_width (truncate width); moveto (truncate x) (truncate y); lineto (truncate x_end) (truncate y_end);; let rec drawRec x y angle length width = if length > 0. then let endx, endy = endpoint x y angle length in drawLine x y angle length width; drawRec endx endy (angle +. pi *. 0.133) (length -. 4.) (width *. 0.75); drawRec endx endy (angle +. pi *. -0.166) (length -. 4.) (width *. 0.75);; moveto 400 200;; drawRec 400. 200. (pi *. 0.5) 50.0 4.;; ``` .codelink[<a href="src/functional.ml" download>`02-main-programming-paradigms/functional.ml`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a>] .small[Source: https://github.com/DaQuirm/ocaml-fractals] ??? - Here is another nice example written in objective caml. - It uses recursion to create a potentially never ending pattern, a fractal. - Here is how it looks like. - We compile and run like that. - It turns out that we need very few lines of code to describe this with a functional language. --- # **Declarative Functional** Programming Paradigm - First-class/higher-order functions - Loops implemented with **recursion** - **Pure functions have no side-effects** - Languages: Haskell, Scala, F#, etc. ??? - With functional programming we have first-class/higher-order functions can be bound to identifier and passed as parameters or returned. - Loops are implemented with recursion, which is well suited for some optimisations, as well as operations such as tree traversal problems, used for example when parsing. - Pure functions have no side-effects on global state. - It is easier to understand and reason about what they do, it is also easier to proof, test and debug, because having less state means less chances for mistakes. - Some example of functional languages are Haskell, Scala, F#, etc. --- # **Declarative Concurrent** Programming Paradigm ```erlang % Example in Erlang using the actor model server() -> receive {From, {convert, TempC}} -> From ! {converted, 32 + TempC *9/5}, server(); {stop} -> io:format("Stopping~n"); Other -> io:format("Unknown: ~p~n", [Other]), server() end. client(ClientID, ServerPID) -> TempC = rand:uniform(40), ServerPID ! {self(), {convert, TempC}}, receive {converted, TempF} -> io:fwrite("~p: ~p deg. C is ~p deg. F~n.", [ClientID, TempC, TempF]), timer:sleep(100), client(ServerPID); {stop} -> io:format("Stopping~n"); Other -> io:format("Unknown: ~p~n", [Other]) end. start() -> Pid1 = spawn(temperature, server, []), spawn(temperature, client, [0, Pid1]), spawn(temperature, client, [1, Pid1]), ``` .codelink[<a href="src/declarative-concurrent.erl" download>`02-main-programming-paradigms/declarative-concurrent.erl`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a>] ??? - Some declarative languages also provide ways to describe concurrent operations. - Here is an example in Erlang, using what is called the actor model. - We declare two concurrent execution flows, a server offering to convert temperature values between Celsius and Fahrenheit degrees, and a client sending conversion requests. --- # **Declarative Concurrent** Programming Paradigm <div style="text-align:center"><img src="include/actors.svg" width=600 /></div> - Less need for synchronisation - Use cases: distributed applications, web services, etc. ??? - We can easily spawn multiple clients and obtain something like that. - One of the advantages of this model is a reduction in synchronisation operations, for example there is no lock. - Declarative concurrent languages are useful when designing distributed applications, web services, and so on. --- # There are Many Other Programming Paradigms - **Logic**, **Dataflow**, **Metaprogramming/Reflexive**, Constraint, Aspect-oriented, Quantum, etc. https://en.wikipedia.org/wiki/Template:Programming_paradigms ??? - There are many other programming paradigms, some of them listed here. - Don't hesitate to check out the Wikipedia page that contains a lot more information. --- # Multi-Paradigm Languages - Haskell: purely functional and does not allow OO style - OCaml: mainly functional, allows OO and imperative constructs - C, C++: imperative but allow some functional idioms: ```c int fact(int x) { if(x == 0) return 1; return x * fact(x-1); } ``` - So many languages are **multi-paradigm** ??? - A Language X is said to support paradigm Y if the language offers to possibility to program in the style defined by the paradigm - For example Haskell is purely functional and does not allow OO style - OCaml is mainly functional but allow OO and imperative constructs - C, C++ and many others are imperative but allow some functional idioms. - For example this is a recursive factorial implementation using C. --- # It all Boils down to Machine Code <div style="text-align:center"><img src="include/compilation.svg" width=700 /></div> ??? - A last thing to remember is that independently of the programming language used to build a program, the only language that the CPU understands is machine code, which is a binary representation of assembly. - So in the end all programming language compile or translate to machine code. --- # Summary <div style="text-align:center"><img src="include/overview1.svg" width=700 /></div> ??? - Here is a summary of the main paradigms we have seen. - We have the two principal categories, declarative on the left and imperative on the right. - On the declarative side, a major subparadigm is functional programming, defined by several features including first class and higher order functions. - Regarding imperative paradigms, we have procedural or structured programming enabled by control flow structures such as loops and functions or procedures. - Adding to this the notion of object we get the object-oriented paradigm. - And adding the notion of concurrent execution flows we get the imperative concurrent paradigm. --- # Course Overview <div style="text-align:center"><img src="include/overview2.svg" width=700 /></div> ??? - Now let's see how the different parts of COMP26020 map to these paradigms. - We will start with imperative procedural programming in C - After that, we will study compilation, the process of transforming language source code (for example C code) into the machine code that is eventually executed on the CPU. - Then we will cover object-oriented programming, looking at the C++ language. - Next we will see functional programming, with Haskell. - And finally, we will see concurrent programming with a language named solidity. --- # Feedback Form .center[https://bit.ly/3lJIvWq] <div style="text-align:center"><img src="include/qr-code.png" height=150 /></div> ??? - And that's it, feel free to leave some feedback if you have any - In the next video, we will start to learn about C.