week1 Flashcards
programming language
describing computer programs
implementable
unambiguous
expressing algorithms to ppl
halting problem
cannot be computed
apl
oriented toward matrix operations
turing complete
it is possible to write, in that language, a program that can compute anything that a Turing machine could compute.
turing machine
mathematical model of a computing engine
abstract mathematical model of computation
state machine
set of states and notion of current state
church’s thesis
any computable function can be implemented by a turing machine
universal turing machine
emulate any other tm
given a TM m and an input p, a UTM can emulate the behavior of m on p
3 requirements to be tm
variable (notion of state)
conditional (show all features can be implemented)
jump (way to transition back to prev state)
some examples of “power” of a language
concise readability resusability versatility strong typing (for deub) protability
high level language
- strong abstraction from the details of the computer.
- few, if any, language elements that translate directly into a machine’s native opcodes
- hll can either be interpreted, compiled, or translated to get to lll or ml
low level language
reflects the underlying hardware: storage, test, jump, arith
imperative pl
- state based on storage
- programs are sequences of statements that modify state and other statements determine flow of control
- describes process to get final answer “how its being computed”
oo pl
- lang w sophisticated type systems supporting inheritance
- typically also imperitive (c++, java, obj c)
- oo features can be other categories of pl
declarative pl
- programs are descriptions of what is to be computed but not how
- functional languages, logic lang
- expresses the logic of a computation without describing its control flow
functional languages
- variables are not modifiable, represent single value
- programs consist of functions that can be recursive (math)
- no loops, can’t modify existing variables
- declarative
logic languages
- declarative
- based on 1st order logic (relations)
- i.e. prolog
scripting lang
- a domain-specific language for a particular environment
- dynamic high-level general-purpose language,
syntax
- rules governing the use of words and sentences in the language
- using grammars
semantics
- define the meaning of the valid syntactic constructs in the language
static semantics vs dynamic semantics
static - governs the use of types
dynamic - indicates what a construct does
assembler
- translate mnemonics and ml language
- machine independent
compiler
- translates HLL to assembly or ml
- better for maintenence
declarative vs imperative
declarative - WHAT a computer should do
imperative - HOW a computer should do it
lambda calc
formal computational model
- a program = function from inputs to outputs defined in terms of simper functions through refinement
dataflow
flow fo info among primitive nodes
von neuman
modification of variables and statements/assignments that influence further computation
compilation:
source program => ? => ?
source program => compiler => target
input => target => output
i.e. source program is compiled into target then input is fed into that target to receive corresponding output
interpretation:
source program =>
source program => interpreter
input => interpreter
interpreter => output
i.e. source program and input goes to interpreter, then to output
compiler
- translate HL source into target program
- better performance
- decision made at compile time (variable location) can be saved
interpreter
- stags during execution
- implements vm whose “ML” is the HLPL
- greater flexibility and better diagnostic (error msg)
- ex = lisp and prolog
mixed model:
source program =>
source program => translator => intermed prog => virtual m
input => virtual m
virtual m => output
i.e. source program is translated to intermediate program; both input and intermediate program is fed into virtual machine for output.
intermediate form
used preprocessor to create tokens of keywords to mirror structure of source
library routines & linking :
ex fortran ->
ex2 source program:
fortran -> compiler -> incomplete ML
incomplete ML & library routines -> linker -> ml program
i.e. use library of subroutines (“extensions” to hardware instruction set
source prog -> compiler -> assembly -> assembler -> ML
preprocessor
define and ex:
source ->
allows for conditional compilation to allow several versions of program to be built from same source
source -> preprocessor -> modified source program -> compiler -> assembly
ex of preprocessor and intermediate lang in c
source ->
source -> preprocesor -> modified source -> c++ compiler -> c code -> c compiler -> assembly
phases of compiler
1) lexer : text- > tokens
2) parser : tokens -> parser tree
3) semantic analysis
4) int code generator
5) optimization
6) target code
