Programming paradigms

Сентябрь 7, 2022

Главная
Алгебра
Programming paradigms

Содержание

2. slide Reading Assignment Mitchell, Chapter 2.1
3. slide What Is a Programming Language? Formal notation for specifying computations, independent of a specific machine
4. slide Partial and Total Functions Value of an expression may be undefined Undefined operation, e.g., division
5. slide Partial and Total: Definitions Total function f:A→B is a subset f ⊆ A×B with ∀
6. slide Computability Function f is computable if some program P computes it For any input x,
7. slide Halting Problem Ettore Bugatti: "I make my cars to go, not to stop"
8. slide Halting Function Decide whether program halts on input Given program P and input x to
9. slide Unsolvability of the Halting Problem Suppose P solves variant of halting problem On input Q,
10. slide Main Points About Computability Some functions are computable, some are not Example: halting problem Programming
11. slide Computation Rules The factorial function type declaration does not convey how the computation is to
12. slide Factorial Functions C, C++, Java: int fact (int n) { return (n == 0) ?
13. slide Principal Paradigms Imperative / Procedural Functional / Applicative Object-Oriented Concurrent Logic Scripting In reality, very
14. slide Where Do Paradigms Come From? Paradigms emerge as the result of social processes in which
15. slide Imperative Paradigm Imperative (procedural) programs consists of actions to effect state change, principally through assignment
16. slide Functional and Logic Paradigms Focuses on function evaluation; avoids updates, assignment, mutable state, side effects
17. slide Concurrent and Scripting Languages Concurrent programming cuts across imperative, object-oriented, and functional paradigms Scripting is
18. slide Unifying Concepts Unifying language concepts Types (both built-in and user-defined) Specify constraints on functions and
19. slide Design Choices C: Efficient imperative programming with static types C++: Object-oriented programming with static types
20. slide Abstraction and Modularization Re-use, sharing, extension of code are critically important in software engineering Big
21. slide Static vs. Dynamic Typing Static typing Common in compiled languages, considered “safer” Type of each
22. slide Billion-Dollar Mistake Failed launch of Ariane 5 rocket (1996) $500 million payload; $7 billion spent
23. slide Program Correctness Assert formal correctness statements about critical parts of a program and reason effectively
24. slide Native-code compiler: produces machine code Compiled languages: Fortran, C, C++, SML … Interpreter: translates into
25. slide Language Compilation Compiler: program that translates a source language into a target language Target language
26. slide Checks During Compilation Syntactically invalid constructs Invalid type conversions A value is used in the
27. slide Compilation Process Lexical analyzer raw source code text Syntax analyzer + type checker tokens ASTs
28. slide Phases of Compilation Preprocessing: conditional macro text substitution Lexical analysis: convert keywords, identifiers, constants into
29. slide Language Interpretation Read-eval-print loop Read in an expression, translate into internal form Evaluate internal form
30. slide Virtual machine runtime Bytecode Compilation Combine compilation with interpretation Idea: remove inefficiencies of read-eval-print loop
32. Скачать презентацию

Слайд 2

slide
Reading Assignment
Mitchell, Chapter 2.1

Слайд 3

slide
What Is a Programming Language?
Formal notation for specifying computations, independent

of a specific machine
Example: a factorial function takes a single non-negative integer argument and computes a positive integer result
Mathematically, written as fact: nat → nat
Set of imperative commands used to direct computer to do something useful
Print to an output device: printf(“hello world\n”);
What mathematical function is “computed” by printf?

Слайд 4

slide
Partial and Total Functions
Value of an expression may be undefined
Undefined

operation, e.g., division by zero
3/0 has no value
Implementation may halt with error condition
Nontermination
f(x) = if x=0 then 1 else f(x-2)
This is a partial function: not defined on all arguments
Cannot be detected by inspecting expression (why?)
These two cases are “mathematically” equivalent, but operationally different (why?)

Subtle: “undefined” is not the name of a function value …

Слайд 5

slide
Partial and Total: Definitions
Total function f:A→B is a subset f

⊆ A×B with
∀ x∈A, there is some y∈B with 〈x,y〉 ∈ f (total)
If 〈x,y〉 ∈ f and 〈x,z〉 ∈ f then y=z (single-valued)
Partial function f:A→B is a subset f ⊆ A×B with
If 〈x,y〉 ∈ f and 〈x,z〉 ∈ f then y=z (single-valued)
Programs define partial functions for two reasons
What are these reasons?

Слайд 6

slide
Computability
Function f is computable if some program P computes

it
For any input x, the computation P(x) halts with output f(x)
Partial recursive functions: partial functions (int to int) that are computable

Слайд 7

slide
Halting Problem
Ettore Bugatti: "I make my cars to go, not

to stop"

Слайд 8

slide
Halting Function
Decide whether program halts on input
Given program P and

input x to P,
Halt(P,x) =
Fact: There is no program for Halt

Clarifications
Assume program P requires one string input x
Write P(x) for output of P when run in input x
Program P is string input to Halt

Слайд 9

slide
Unsolvability of the Halting Problem
Suppose P solves variant of halting

problem
On input Q, assume P(Q) =
Build program D
D(Q) =
If D(D) halts, then D(D) runs forever
If D(D) runs forever, then D(D) halts
Contradiction! Thus P cannot exist.

Слайд 10

slide
Main Points About Computability
Some functions are computable, some are not
Example:

halting problem
Programming language implementation
Can report error if program result is undefined due to an undefined basic operation (e.g., division by zero)
Cannot report error if program will not terminate

Слайд 11

slide
Computation Rules
The factorial function type declaration does not convey how

the computation is to proceed
We also need a computation rule
fact (0) = 1
fact (n) = n * fact(n-1)
This notation is more computationally oriented and can almost be executed by a machine

Слайд 12

slide
Factorial Functions
C, C++, Java:
int fact (int n) { return (n

== 0) ? 1 : n * fact (n-1); }
Scheme:
(define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
ML:
fun fact n = if n=0 then 1 else n*fact(n-1);
Haskell:
fact :: Integer->Integer
fact 0 = 1
fact n = n*fact(n-1)

Слайд 13

slide
Principal Paradigms
Imperative / Procedural
Functional / Applicative
Object-Oriented
Concurrent
Logic
Scripting
In

reality, very few languages are “pure”
Most combine features of different paradigms

Слайд 14

slide
Where Do Paradigms Come From?
Paradigms emerge as the result of

social processes in which people develop ideas
and create principles and practices that embody
those ideas
Thomas Kuhn. “The Structure of Scientific Revolutions.”
Programming paradigms are the result of people’s ideas about how programs should be constructed
… and formal linguistic mechanisms for expressing them
… and software engineering principles and practices for using the resulting programming language to solve problems

Слайд 15

slide
Imperative Paradigm
Imperative (procedural) programs consists of actions to effect state

change, principally through assignment operations or side effects
Fortran, Algol, Cobol, PL/I, Pascal, Modula-2, Ada, C
Why does imperative programming dominate in practice?
OO programming is not always imperative, but most OO languages have been imperative
Simula, Smalltalk, C++, Modula-3, Java
Notable exception: CLOS (Common Lisp Object System)

Слайд 16

slide
Functional and Logic Paradigms
Focuses on function evaluation; avoids updates, assignment,

mutable state, side effects
Not all functional languages are “pure”
In practice, rely on non-pure functions for input/output and some permit assignment-like operators
E.g., (set! x 1) in Scheme
Logic programming is based on predicate logic
Targeted at theorem-proving languages, automated reasoning, database applications
Recent trend: declarative programming

Слайд 17

slide
Concurrent and Scripting Languages
Concurrent programming cuts across imperative, object-oriented, and

functional paradigms
Scripting is a very “high” level of programming
Rapid development; glue together different programs
Often dynamically typed, with only int, float, string, and array as the data types; no user-defined types
Weakly typed: a variable ‘x’ can be assigned a value of any type at any time during execution
Very popular in Web development
Especially scripting active Web pages

Слайд 18

slide
Unifying Concepts
Unifying language concepts
Types (both built-in and user-defined)
Specify constraints on

functions and data
Static vs. dynamic typing
Expressions (e.g., arithmetic, boolean, strings)
Functions/procedures
Commands
We will study how these are defined syntactically, used semantically, and implemented pragmatically

Слайд 19

slide
Design Choices
C: Efficient imperative programming with static types
C++: Object-oriented programming

with static types and ad hoc, subtype and parametric polymorphism
Java: Imperative, object-oriented, and concurrent programming with static types and garbage collection
Scheme: Lexically scoped, applicative-style recursive programming with dynamic types
Standard ML: Practical functional programming with strict (eager) evaluation and polymorphic type inference
Haskell: Pure functional programming with non-strict (lazy) evaluation.

Слайд 20

slide
Abstraction and Modularization
Re-use, sharing, extension of code are critically important

in software engineering
Big idea: detect errors at compile-time, not when program is executed
Type definitions and declarations
Define intent for both functions/procedures and data
Abstract data types (ADT)
Access to local data only via a well-defined interface
Lexical scope

Слайд 21

slide
Static vs. Dynamic Typing
Static typing
Common in compiled languages, considered “safer”
Type

of each variable determined at compile-time; constrains the set of values it can hold at run-time
Dynamic typing
Common in interpreted languages
Types are associated with a variable at run-time; may change dynamically to conform to the type of the value currently referenced by the variable
Type errors not detected until a piece of code is executed

Слайд 22

slide
Billion-Dollar Mistake
Failed launch of Ariane 5 rocket (1996)
$500 million payload;

$7 billion spent on development
Cause: software error in inertial reference system
Re-used Ariane 4 code, but flight path was different
64-bit floating point number related to horizontal velocity converted to 16-bit signed integer; the number was larger than 32,767; inertial guidance crashed

Слайд 23

slide
Program Correctness
Assert formal correctness statements about critical parts of a

program and reason effectively
A program is intended to carry out a specific computation, but a programmer can fail to adequately address all data value ranges, input conditions, system resource constraints, memory limitations, etc.
Language features and their interaction should be clearly specified and understandable
If you do not or can not clearly understand the semantics of the language, your ability to accurately predict the behavior of your program is limited

Слайд 24

slide
Native-code compiler: produces machine code
Compiled languages: Fortran, C, C++, SML

…
Interpreter: translates into internal form and immediately executes (read-eval-print loop)
Interpreted languages: Scheme, Haskell, Python …
Byte-code compiler: produces portable bytecode, which is executed on virtual machine (e.g., Java)
Hybrid approaches
Source-to-source translation (early C++ → C→compile)
Just-in-time Java compilers convert bytecode into native machine code when first executed

Language Translation

Слайд 25

slide
Language Compilation
Compiler: program that translates a source language into a

target language
Target language is often, but not always, the assembly language for a particular machine

C
compiler

C
source code

x86
assembler

x86 ASM

Pentium op codes

Слайд 26

slide
Checks During Compilation
Syntactically invalid constructs
Invalid type conversions
A value is used

in the “wrong” context, e.g., assigning a float to an int
Static determination of type information is also used to generate more efficient code
Know what kind of values will be stored in a given memory region during program execution
Some programmer logic errors
Can be subtle: if (a = b) … instead of if (a == b) …

Слайд 27

slide
Compilation Process
Lexical analyzer
raw source
code text
Syntax analyzer + type checker
tokens
ASTs
Intermediate
code gen
Optimizer
IC
ICopt
Final code gen
ASM
Assembler
Machine

code

Syntax and static
type errors

Preprocessor

Source code with
preprocessor directives

Слайд 28

slide
Phases of Compilation
Preprocessing: conditional macro text substitution
Lexical analysis: convert keywords,

identifiers, constants into a sequence of tokens
Syntactic analysis: check that token sequence is syntactically correct
Generate abstract syntax trees (AST), check types
Intermediate code generation: “walk” the ASTs and generate intermediate code
Apply optimizations to produce efficient code
Final code generation: produce machine code

Слайд 29

slide
Language Interpretation
Read-eval-print loop
Read in an expression, translate into internal form
Evaluate

internal form
This requires an abstract machine and a “run-time” component (usually a compiled program that runs on the native machine)
Print the result of evaluation
Loop back to read the next expression

REPL interpreter

input expression

Interpreter
runtime

result

Слайд 30

slide
Virtual machine
runtime
Bytecode Compilation
Combine compilation with interpretation
Idea: remove inefficiencies of read-eval-print

loop
Bytecodes are conceptually similar to real machine opcodes, but they represent compiled instructions to a virtual machine instead of a real machine
Source code statically compiled into a set of bytecodes
Bytecode interpreter implements the virtual machine
In what way are bytecodes “better” then real opcodes?

Bytecode compiler

source
program

bytecodes

Bytecode interpreter

result

Programming paradigms

Содержание

slide Reading AssignmentMitchell, Chapter 2.1

slide What Is a Programming Language?Formal notation for specifying computations, independent

slide Partial and Total FunctionsValue of an expression may be undefinedUndefined

slide Partial and Total: DefinitionsTotal function f:A→B is a subset f

slide Computability Function f is computable if some program P computes

slide Halting ProblemEttore Bugatti: "I make my cars to go, not

slide Halting FunctionDecide whether program halts on inputGiven program P and

slide Unsolvability of the Halting ProblemSuppose P solves variant of halting

slide Main Points About ComputabilitySome functions are computable, some are notExample:

slide Computation RulesThe factorial function type declaration does not convey how

slide Factorial FunctionsC, C++, Java: int fact (int n) { return (n

slide Principal ParadigmsImperative / Procedural Functional / Applicative Object-OrientedConcurrent LogicScripting In

slide Where Do Paradigms Come From?Paradigms emerge as the result of

slide Imperative ParadigmImperative (procedural) programs consists of actions to effect state

slide Functional and Logic ParadigmsFocuses on function evaluation; avoids updates, assignment,

slide Concurrent and Scripting LanguagesConcurrent programming cuts across imperative, object-oriented, and

slide Unifying ConceptsUnifying language conceptsTypes (both built-in and user-defined)Specify constraints on

slide Design ChoicesC: Efficient imperative programming with static typesC++: Object-oriented programming

slide Abstraction and ModularizationRe-use, sharing, extension of code are critically important

slide Static vs. Dynamic TypingStatic typingCommon in compiled languages, considered “safer”Type

slide Billion-Dollar MistakeFailed launch of Ariane 5 rocket (1996)$500 million payload;

slide Program CorrectnessAssert formal correctness statements about critical parts of a

slide Native-code compiler: produces machine codeCompiled languages: Fortran, C, C++, SML

slide Language CompilationCompiler: program that translates a source language into a

slide Checks During CompilationSyntactically invalid constructsInvalid type conversionsA value is used

slide Compilation ProcessLexical analyzerraw sourcecode textSyntax analyzer + type checkertokensASTsIntermediatecode genOptimizerICICoptFinal code genASMAssemblerMachine

slide Phases of CompilationPreprocessing: conditional macro text substitutionLexical analysis: convert keywords,

slide Language InterpretationRead-eval-print loopRead in an expression, translate into internal formEvaluate

slide Virtual machineruntimeBytecode CompilationCombine compilation with interpretationIdea: remove inefficiencies of read-eval-print

Похожие презентации