week1

Question 1

programming language

Answer 1

describing computer programs
implementable
unambiguous
expressing algorithms to ppl

Question 2

halting problem

Answer 2

cannot be computed

Question 3

apl

Answer 3

oriented toward matrix operations

Question 4

turing complete

Answer 4

it is possible to write, in that language, a program that can compute anything that a Turing machine could compute.

Question 5

turing machine

Answer 5

mathematical model of a computing engine

abstract mathematical model of computation

Question 6

state machine

Answer 6

set of states and notion of current state

Question 7

church’s thesis

Answer 7

any computable function can be implemented by a turing machine

Question 8

universal turing machine

Answer 8

emulate any other tm

given a TM m and an input p, a UTM can emulate the behavior of m on p

Question 9

3 requirements to be tm

Answer 9

variable (notion of state)
conditional (show all features can be implemented)
jump (way to transition back to prev state)

Question 10

some examples of “power” of a language

Answer 10

concise
readability
resusability
versatility
strong typing (for deub)
protability

Question 11

high level language

Answer 11

• 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

Question 12

low level language

Answer 12

reflects the underlying hardware: storage, test, jump, arith

Question 13

imperative pl

Answer 13

• 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”

Question 14

oo pl

Answer 14

• lang w sophisticated type systems supporting inheritance
• typically also imperitive (c++, java, obj c)
• oo features can be other categories of pl

Question 15

declarative pl

Answer 15

• 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

Question 16

functional languages

Answer 16

• variables are not modifiable, represent single value
• programs consist of functions that can be recursive (math)
• no loops, can’t modify existing variables
• declarative

Question 17

logic languages

Answer 17

• declarative
• based on 1st order logic (relations)
• i.e. prolog

Question 18

scripting lang

Answer 18

• a domain-specific language for a particular environment

- dynamic high-level general-purpose language,

Question 19

syntax

Answer 19

• rules governing the use of words and sentences in the language
• using grammars

Question 20

semantics

Answer 20

• define the meaning of the valid syntactic constructs in the language

Question 21

static semantics vs dynamic semantics

Answer 21

static - governs the use of types

dynamic - indicates what a construct does

Question 22

assembler

Answer 22

• translate mnemonics and ml language

- machine independent

Question 23

compiler

Answer 23

• translates HLL to assembly or ml

- better for maintenence

Question 24

declarative vs imperative

Answer 24

declarative - WHAT a computer should do

imperative - HOW a computer should do it

Question 25

lambda calc

Answer 25

formal computational model

- a program = function from inputs to outputs defined in terms of simper functions through refinement

Question 26

dataflow

Answer 26

flow fo info among primitive nodes

Question 27

von neuman

Answer 27

modification of variables and statements/assignments that influence further computation

Question 28

compilation:

source program => ? => ?

Answer 28

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

Question 29

interpretation:

source program =>

Answer 29

source program => interpreter
input => interpreter
interpreter => output

i.e. source program and input goes to interpreter, then to output

Question 30

compiler

Answer 30

• translate HL source into target program
• better performance
• decision made at compile time (variable location) can be saved

Question 31

interpreter

Answer 31

• stags during execution
• implements vm whose “ML” is the HLPL
• greater flexibility and better diagnostic (error msg)
• ex = lisp and prolog

Question 32

mixed model:

source program =>

Answer 32

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.

Question 33

intermediate form

Answer 33

used preprocessor to create tokens of keywords to mirror structure of source

Question 34

library routines & linking :
ex fortran ->
ex2 source program:

Answer 34

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

Question 35

preprocessor
define and ex:
source ->

Answer 35

allows for conditional compilation to allow several versions of program to be built from same source

source -> preprocessor -> modified source program -> compiler -> assembly

Question 36

ex of preprocessor and intermediate lang in c

source ->

Answer 36

source -> preprocesor -> modified source -> c++ compiler -> c code -> c compiler -> assembly

Question 37

phases of compiler

Answer 37

1) lexer : text- > tokens
2) parser : tokens -> parser tree
3) semantic analysis
4) int code generator
5) optimization
6) target code