Забыли?

?

# CS 345 - Programming Languages

код для вставкиСкачать
```CS 345
Vitaly Shmatikov
slide 1
пЃµMitchell, Chapter 2.1
slide 2
What Is a Programming Language?
пЃµFormal notation for specifying computations,
independent of a specific machine
вЂў Example: a factorial function takes a single nonnegative 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?
slide 3
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 вЂ¦
slide 4
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?
slide 5
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
slide 6
Halting Problem
Ettore Bugatti: "I make my
cars to go, not to stop"
slide 7
Halting Function
пЃµDecide whether program halts on input
вЂў Given program P and input x to P,
Halt(P,x) =
yes if P(x) halts
no otherwise
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
Fact: There is no program for Halt
slide 8
Unsolvability of the Halting Problem
пЃµSuppose P solves variant of halting problem
yes if Q(Q) halts
вЂў On input Q, assume P(Q) =
no otherwise
пЃµBuild program D
вЂў D(Q) =
run forever
halt
if Q(Q) halts
if Q(Q) runs forever
пЃµIf D(D) halts, then D(D) runs forever
пЃµIf D(D) runs forever, then D(D) halts
slide 9
пЃµSome functions are computable, some are not
вЂў Example: halting problem
пЃµProgramming language implementation
an undefined basic operation (e.g., division by zero)
slide 10
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
slide 11
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);
вЂў fact :: Integer->Integer
вЂў fact 0 = 1
вЂў fact n = n*fact(n-1)
slide 12
пЃµImperative / Procedural
пЃµFunctional / Applicative
пЃµObject-Oriented
пЃµConcurrent
пЃµLogic
пЃµScripting
пЃµIn reality, very few languages are вЂњpureвЂќ
вЂў Most combine features of different paradigms
slide 13
пЃµ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
slide 14
пЃµ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)
slide 15
пЃµ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
slide 16
Concurrent and Scripting Languages
пЃµConcurrent programming cuts across imperative,
пЃµ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
slide 17
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
slide 18
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.
slide 19
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
пЃµLexical scope
slide 20
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
slide 21
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
slide 22
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
slide 23
Language Translation
пЃµNative-code compiler: produces machine code
вЂў Compiled languages: Fortran, C, C++, SML вЂ¦
пЃµInterpreter: translates into internal form and
вЂў 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
slide 24
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
source code
C
compiler
x86 ASM
x86
assembler
Pentium op codes
slide 25
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) вЂ¦
slide 26
Compilation Process
Syntax and static
type errors
Lexical
analyzer
tokens
raw source
code text
Preprocessor
Source code with
preprocessor directives
Syntax
analyzer +
type checker
ASTs
Intermediate
code gen
IC
Optimizer
ICopt
Final code
gen
ASM
Assembler
Machine code
slide 27
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
slide 28
Language Interpretation
вЂў 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
input
expression
REPL
interpreter
result
Interpreter
runtime
slide 29
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?
source
program
Bytecode
compiler
bytecodes
Bytecode
interpreter
Virtual machine
runtime
result
slide 30
Binding
пЃµBinding = association between an object and a
property of that object
вЂў Example: a variable and its type
вЂў Example: a variable and its value
пЃµA language element is bound to a property at
the time that property is defined for it
вЂў Early binding takes place at compile-time
вЂў Late binding takes place at run-time
slide 31
```
###### Документ
Категория
Презентации
Просмотров
30
Размер файла
517 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа