final Flashcards
functional languages vs imperative languages
imperative:
- based directly on the von Neumann
architecture:
- Efficiency is the primary concern, rather than the suitability of the language for software development
functional:
- based on mathematical functions:
- A solid theoretical basis that is also closer to the user, but relatively unconcerned with the architecture of the machines on which programs will run
mathematical function
a mapping of members of one set, called the domain set, to another set, called the range set
Lambda expressions
*Lambda expressions describe nameless functions
*Lambda expressions are applied to parameter(s) by placing the parameter(s)
after the expression,
Function Composition
A functional form that takes two functions as parameters and yields a function
whose value is the first actual parameter function applied to the application of
the second:
Form: h =f∘g
which means: h(x) =f(g(x)
objective of the design of an FPL
mimic mathematical functions to the
greatest extent possible
basic process of computation in FPL vs imperative languages
§ imperative language: operations are done and the results are stored in variables for later use
§Management of variables is a constant concern and source of complexity for
imperative programming
* FPL: variables are not necessary, as is the case in mathematics, the evaluation of a function always produces the same result given the same parameters (referential transparency)
Tail recursive function in Scheme
- A function is tail recursive if its recursive call is the last operation in
the function - A tail recursive function can be automatically converted by a compiler to use iteration, making it faster
- Scheme language definition requires that Scheme language systems convert all tail recursive functions to use iteration
common lisp features
§records
§arrays
§complex numbers
§character strings
§powerful I/O capabilities
§packages with access control
§iterative control statements
Symbol Data Type
*Similar to that of Ruby
*The reserved words are symbols that evaluate to themselves
*Symbols are either bound or unbound:
§Parameter symbols are bound while the function is being evaluated
§Symbols that are the names of imperative style variables that have been assigned
values are bound
§All other symbols are unbound
ML
- static-scoped
- syntax that is closer to Pascal than to
Lisp - type declarations + type inferencing
- strongly typed and has no type coercions
- Does not have imperative-style variables
- identifiers are untyped
- exception handling and a module facility for implementing abstract data types
- lists and list operations
how is Haskell similar and different from ML?
*Similar to ML (syntax, static scoped, strongly typed, type inferencing, pattern
matching)
*Different from ML (and most other functional languages) in that it is purely
functional (e.g., no variables, no assignment statements, and no side effects of
any kind)
F#
- imperative features and supports
OOP - tuples, lists, discriminated unions, records, and both mutable and immutable arrays
Trends in imperative languages
Support for functional programming is increasingly creeping into imperative languages
Comparing Functional and Imperative Languages
*Imperative Languages:
§Efficient execution
§Complex semantics
§Complex syntax
§Concurrency is programmer designed
*Functional Languages:
§Simple semantics
§Simple syntax
§Less efficient execution
§Programs can automatically be made concurrent
abstraction
view or representation of an entity that includes only the most significant attributes
* fundamental in programming (and computer science)
*Nearly all programming languages support process abstraction with subprograms
*Nearly all programming languages designed since 1980 support data
abstraction
abstract data type (ADT)
a user-defined data type that satisfies the
following two conditions
1. the only operations possible are those provided in the type’s definition
2. declarations and the protocols of the operations on objects of the type are contained in a single syntactic unit
Advantages of Data Abstraction
*Advantages the first condition:
§Reliability: by hiding the data representations, user code cannot directly access objects of the type or depend on the representation, allowing the representation to
be changed without affecting user code
§Reduces the range of code and variables of which the programmer must be aware
§Name conflicts are less likely
*Advantages of the second condition:
§Provides a method of program organization
§Aids modifiability (everything associated with a data structure is together)
§Separate compilation
Language Requirements for ADTs
*A syntactic unit in which to encapsulate the type definition
*A method of making type names and subprogram headers visible to clients,
while hiding actual definitions
*Some primitive operations must be built into the language processor
Parameterized ADTs
Parameterized ADTs allow designing an ADT that can store any type elements:
only an issue for static typed languages
Encapsulation Constructs
a grouping of subprograms that are logically related into a unit that can be separately compiled (compilation units)
Nested Subprograms
*Organizing programs by nesting subprogram definitions inside the logically
larger subprograms that use them
*Nested subprograms are supported in Python, JavaScript, and Ruby
Object-Oriented Programming (OOP) Languages
*Some support procedural and data-oriented programming (e.g., C++)
*Some support functional program (e.g., CLOS)
*Newer languages do not support other paradigms but use their imperative
structures (e.g., Java and C#)
*Some are pure OOP language (e.g., Smalltalk & Ruby)
*Some functional languages support OOP, but they are not discussed in this chapter
Three major OOP language features:
§Abstract data types (Chapter 11)
§(Class) Inheritance:
o Inheritance is the central theme in OOP and languages that support it
§Polymorphism
Design Issues for OOP Languages
*The Exclusivity of Objects
*Are Subclasses Subtypes?
*Single and Multiple Inheritance
*Object Allocation and Deallocation
*Dynamic and Static Binding
*Nested Classes
*Initialization of Objects
Single and Multiple Inheritance
*Multiple inheritance allows a new class to inherit from two or more classes
*Disadvantages of multiple inheritance:
§Language and implementation complexity (in part due to name collisions)
§Potential inefficiency: dynamic binding costs more with multiple inheritance (but not
much)
*Advantage:
§Sometimes it is quite convenient and valuable
Allocation and DeAllocation of Objects
§If they behave line the ADTs, they can be allocated from anywhere:
o Allocated from the run-time stack
o Explicitly create on the heap (via new)
§If they are all heap-dynamic, references can be uniform thru a pointer or reference
variable:
o Simplifies assignment: dereferencing can be implicit
§If objects are stack dynamic, there is a problem with regard to subtypes: object
slicing
Two interesting and challenging parts of implementing OO constructs:
§Storage structures for instance variables
§Dynamic binding of messages to methods
Instance Data Storage
*Class instance records (CIRs) store the state of an object:
§Static (built at compile time)
*If a class has a parent, the subclass instance variables are added to the parent
CIR
*Because CIR is static, access to all instance variables is done as it is in records:
§Efficient
Dynamic Binding of Methods Calls
Methods in a class that are statically bound need not be involved in the CIR;
methods that will be dynamically bound must have entries in the CIR:
§Calls to dynamically bound methods can be connected to the corresponding code
thru a pointer in the CIR
§The storage structure is sometimes called virtual method tables (vtable)
§Method calls can be represented as offsets from the beginning of the vtable
Reflection
A programming language that supports reflection allows its programs to have runtime access to their types and structure and to be able to dynamically modify their behavior
metadata
The types and structure of a program
introspection
The process of a program examining its metadata
intercession
Interceding in the execution of a program
Uses of reflection for software tools:
§Class browsers need to enumerate the classes of a program
§Visual IDEs use type information to assist the developer in building type correct code
§Debuggers need to examine private fields and methods of classes
§Test systems need to know all of the methods of a class
Concurrency can occur at four levels:
§Machine instruction level
§High-level language statement level
§Unit level
§Program level
Categories of Concurrency:
§Physical concurrency: Multiple independent processors ( multiple threads of control)
§Logical concurrency: The appearance of physical concurrency is presented by time-
sharing one processor (software can be designed as if there were multiple threads of
control)
Coroutines
have a single thread of control
thread of control in a program
the sequence of program points reached as control flows through the program
task or process or thread
a program unit that can be in concurrent execution
with other program units
Tasks differ from ordinary subprograms in that:
§A task may be implicitly started
§When a program unit starts the execution of a task, it is not necessarily suspended
§When a task’s execution is completed, control may not return to the caller
Tasks dont usually work together
FALSE
Two General Categories of Tasks
*Heavyweight tasks execute in their own address space
*Lightweight tasks all run in the same address space, more efficient
*A task is disjoint if it does not communicate with or affect the execution of any
other task in the program in any way
Task Synchronization
A mechanism that controls the order in which tasks execute
Two kinds of synchronization:
§Cooperation synchronization
§Competition synchronization
Task communication is necessary for synchronization, provided by:
§Shared nonlocal variables
§Parameters
§Message passing
Task Execution States
*New: created but not yet started
*Ready: ready to run but not currently running (no available processor)
*Running
*Blocked: has been running, but cannot now continue (usually waiting for some
event to occur)
*Dead: no longer active in any sense
Design Issues for Concurrency
*Competition and cooperation synchronization: the most important issue
*Controlling task scheduling
*How can an application influence task scheduling
*How and when tasks start and end execution
*How and when are tasks created
Semaphores
*A semaphore is a data structure consisting of a counter and a queue for storing
task descriptors:
§A task descriptor is a data structure that stores all of the relevant information about
the execution state of the task
*Semaphores can be used to implement guards on the code that accesses
shared data structures
*Semaphores have only two operations, wait and release (originally called Pand
Vby Dijkstra)
*Semaphores can be used to provide both competition and cooperation
synchronization
Monitors
*The idea: encapsulate the shared data and its operations to restrict access
*A monitor is an abstract data type for shared data
Message Passing
*Message passing is a general model for concurrency:
§It can model both semaphores and monitors
§It is not just for competition synchronization
*Central idea: task communication is like seeing a doctor, most of the time the
doctor waits for you or you wait for the doctor, but when you are both ready, you
get together, or rendezvous
Ada Evaluation
*Message passing model of concurrency is powerful and general
*Protected objects are a better way to provide synchronized shared data
*In the absence of distributed processors, the choice between monitors and tasks
with message passing is somewhat a matter of taste
*For distributed systems, message passing is a better model for concurrency
Java’s Thread Evaluation
*Java’s support for concurrency is relatively simple but effective
*Not as powerful as Ada’s tasks
C#’s Concurrency Evaluation
*An advance over Java threads, e.g., any method can run its own thread
*Thread termination is cleaner than in Java
*Synchronization is more sophisticated
Statement-Level Concurrency
*Objective: Provide a mechanism that the programmer can use to inform compiler of ways it can map the program onto multiprocessor architecture
*Minimize communication among processors and the memories of the other processors
High-Performance Fortran (HPF)
*A collection of extensions that allow the programmer to provide information to
the compiler to help it optimize code for multiprocessor computers
*Specify the number of processors, the distribution of data over the memories of
those processors, and the alignment of data
exception
any unusual event, either erroneous or not, detectable by either
hardware or software, that may require special processing
exception handling
The special processing that may be required after detection of an exception
exception handler
exception handling code unit
exceptions: Design Issues
*How and where are exception handlers specified and what is their scope?
*How is an exception occurrence bound to an exception handler?
*Can information about the exception be passed to the handler?
*Where does execution continue, if at all, after an exception handler completes
its execution? (continuation vs. resumption)
*Is some form of finalization provided?
*How are user-defined exceptions specified?
*Should there be default exception handlers for programs that do not provide
their own?
*Can predefined exceptions be explicitly raised?
*Are hardware-detectable errors treated as exceptions that can be handled?
*Are there any predefined exceptions?
*How can exceptions be disabled, if at all?
Exceptions: C++ Evaluation
*There are no predefined exceptions
*It is odd that exceptions are not named and that hardware- and system
software-detectable exceptions cannot be handled
*Binding exceptions to handlers through the type of the parameter certainly does
not promote readability
Exceptions: Java Evaluation
*The types of exceptions makes more sense than in the case of C++
*The throws clause is better than that of C++ (The throw clause in C++ says little to the programmer)
*The finally clause is often useful
*The Java interpreter throws a variety of exceptions that can be handled by user programs
Python Exception Handling
*Exceptions are objects: the base class is BaseException
*All predefined and user-defined exceptions are derived from Exception
*Predefined subclasses of Exception are:
§ArithmeticError: subclasses are OverflowError, ZeroDivisionError, and
FloatingPointError
§LookupError: subclasses are IndexError and KeyError
Ruby Exception Handling
*Exceptions are objects
*There are many predefined exceptions
*All exceptions that are user handled are either StandardError class or a
subclass of it
*StandardError is derived from Exception, which has two methods,
message and backtrace
*Exceptions can be raised with raise, which often has the form
Event Handling
*An event is a notification that something specific has occurred, such as a mouse click on a graphical button
*The event handler is a segment of code that is executed in response to an event
The Java Event Model
*User interactions with GUI components create events that can be caught by
event handlers, called event listeners
*An event generator tells a listener of an event by sending a message
*An interface is used to make event-handling methods conform to a standard
protocol
*A class that implements a listener must implement an interface for the listener
C# Event Handling
*Event handling in C# (and the other .NET languages) is similar to that in Java
*.NET has two approaches, Windows Forms and Windows Presentation
Foundation: we cover only the former (which is the original approach)
*An application subclasses the Form predefined class (defined in
System.Windows.Forms)
*There is no need to create a frame or panel in which to place the GUI
components
*Label objects are used to place text in the window
*Radio buttons are objects of the RadioButton class
Symbolic Logic
Logic which can be used for the basic needs of formal logic:
§Express propositions
§Express relationships between propositions
§Describe how new propositions can be inferred from other propositions
predicate
calculus
Particular form of symbolic logic used for logic programming
Propositions can be stated in two forms:
§Fact: proposition is assumed to be true
§Query: truth of proposition is to be determined
Compound proposition:
§Have two or more atomic propositions
§Propositions are connected by operators
Clausal Form
*Too many ways to state the same thing
*Use a standard form for propositions
*Clausal form
B1 ÈB2 È… ÈBn ÌA1 ÇA2 Ç… ÇAm
Unification
finding values for variables in propositions that allows matching
process to succeed
Instantiation
assigning temporary values to variables to allow unification to
succeed
After instantiating a variable with a value, if matching fails, may need to backtrack and instantiate with a different value
Hypotheses
a set of pertinent propositions
Goal
negation of theorem stated as a proposition
Theorem
proved by finding an inconsistency
Declarative semantics
§There is a simple way to determine the meaning of each statement
§Simpler than the semantics of imperative languages
Programming is nonprocedural:
Programs do not state now a result is to be computed, but rather the form of the result
When goal has more than one subgoal, can use either:
§Depth-first search: find a complete proof for the first subgoal before working on
others
§Breadth-first search: work on all subgoals in parallel
Trace
Built-in structure that displays instantiations at each step
Tracing model of execution, four events:
§Call: beginning of attempt to satisfy goal
§Exit: when a goal has been satisfied
§Redo: when backtrack occurs
§Fail: when goal fails
Language Evaluation Criteria
*Readability: the ease with which programs can be read and understood
*Writability: the ease with which a language can be used to create programs
*Reliability: conformance to specifications (i.e., performs to its specifications)
*Cost: the ultimate total cost
The von Neumann Architecture
Fetch-execute-cycle (on a von Neumann architecture computer)
initialize the program counter
repeat forever
fetch the instruction pointed by the counter
increment the counter
decode the instruction
execute the instruction
end repeat
Language Categories
*Imperative
§Central features are variables, assignment statements, and iteration
§Include languages that support object-oriented programming
§Include scripting languages
§Include the visual languages
§Examples: C, Java, Perl, JavaScript, Visual BASIC .NET, C++
*Functional
§Main means of making computations is by applying functions to given parameters
§Examples: LISP, Scheme, ML, F#
*Logic
§Rule-based (rules are specified in no particular order)
§Example: Prolog
*Markup/programming hybrid
§Markup languages extended to support some programming
§Examples: JSTL, XSLT
Implementation Methods
*Compilation
§Programs are translated into machine language; includes JIT systems
§Use: Large commercial applications
*Pure Interpretation
§Programs are interpreted by another program known as an interpreter
§Use: Small programs or when efficiency is not an issue
*Hybrid Implementation Systems
§A compromise between compilers and pure interpreters
§Use: Small and medium systems when efficiency is not the first concern
Language Groups
*Imperative:
§von Neumann (Fortran, Pascal, Basic, C)
§Object-oriented (Smalltalk, Eiffel, C++?)
§Scripting languages (Perl, Python, JavaScript, PHP)
*Declarative:
§Functional (Scheme, ML, pure LISP, FP)
§Logic, constraint-based (Prolog, VisiCalc, RPG)
*Imperative languages, particularly the von Neumann languages, predominate:
§They will occupy the bulk of our attention
Syntax
the form or structure of the expressions, statements, and program units
Semantics
the meaning of the expressions, statements, and program units
Users of a language definition
§Other language designers
§Implementers
§Programmers (the users of the language)
Context-Free Grammars
§Developed by Noam Chomsky in the mid-1950s
§Language generators, meant to describe the syntax of natural languages
§Define a class of languages called context-free languages
Backus-Naur Form
§Invented by John Backus to describe the syntax of Algol 58
§BNF is equivalent to context-free grammars
sentential form
Every string of symbols in a derivation
sentence
a sentential form that has only terminal symbols
leftmost derivation
leftmost nonterminal in each sentential
form is the one that is expanded
Parse Tree
A hierarchical representation of a derivation
Attribute Grammars
have additions to CFGs to carry some semantic info on parse tree nodes
Primary value of AGs:
§Static semantics specification
§Compiler design (static semantics checking)
Dynamic Semantics
There is no single widely acceptable notation or formalism for describing semantics
Several needs for a methodology and notation for semantics:
§Programmers need to know what statements mean
§Compiler writers must know exactly what language constructs do
§Correctness proofs would be possible
§Compiler generators would be possible
§Designers could detect ambiguities and inconsistencies
Syntax Analysis
The syntax analysis portion of a language processor nearly always consists of
two parts:
§A low-level part called a lexical analyzer(mathematically, a finite automaton based
on a regular grammar)
§A high-level part called a syntax analyzer, or parser (mathematically, a push-down
automaton based on a context-free grammar, or BNF)
Regular Expressions
A regular expression is one of the following:
§A character
§The empty string, denoted by ε
§Two regular expressions concatenated
§Two regular expressions separated by | (i.e., or)
§A regular expression followed by the Kleene star * (concatenation of zero or more
strings).
Goals of the parser, given an input program:
§Find all syntax errors; for each, produce an appropriate diagnostic message and
recover quickly
§Produce the parse tree, or at least a trace of the parse tree, for the program
Two categories of parsers:
§Top down:
o Produce the parse tree, beginning at the root
o Order is that of a leftmost derivation
o Traces or builds the parse tree in preorder
§Bottom up:
o Produce the parse tree, beginning at the leaves
o Order is that of the reverse of a rightmost derivation
Imperative languages are abstractions of von Neumann architecture:
§Memory
§Processor
Variables are characterized by attributes:
To design a type, must consider scope, lifetime, type checking, initialization, and
type compatibility
variable
an abstraction of a memory cell
Variables can be characterized as a sextuple of attributes:
§Name
§Address
§Value
§Type
§Lifetime
§Scope
Type
determines the range of values of variables and the set of operations that
are defined for values of that type; in the case of floating point, type also
determines the precision
Value
the contents of the location with which the variable is associated:
l-value
l-value of a variable is its address
r-value
r-value of a variable is its value
Abstract memory cell
the physical cell or collection of cells associated with a
variable
static binding
A binding is static if it first occurs before run time and remains unchanged
throughout program execution
dynamic binding
A binding is dynamic if it first occurs during execution or can change during
execution of the program
scope of a variable
scope of a variable is the range of statements over which it is visible
local variables of a program unit
local variables of a program unit are those that are declared in that unit
nonlocal variables of a program unit
nonlocal variables of a program unit are those that are visible in the unit but
not declared there
Global variables
a special category of nonlocal variables
scope rules of a language determine…
how references to names are
associated with variables
static scope search process
search declarations, first locally, then in increasingly larger
enclosing scopes, until one is found for the given name
static ancestors
Enclosing static scopes (to a specific scope) are called its static ancestors
static parent
the
nearest static ancestor is called a static parent
static scope bindings depend on
bindings are defined by the physical
(lexical) structure of the program
dynamic scope bindings depend on
depend on the current state of program
execution:
data type
defines a collection of data objects and a set of predefined
operations on those objects
descriptor
the collection of the attributes of a variable
object
represents an instance of a user-defined (abstract data) type
One design issue for all data types
What operations are defined and how are
they specified?
Almost all programming languages provide
provide a set of primitive data types
Primitive data types
Those not defined in terms of other data types
examples of primitive data types
§Integer
§Floating Point
§Complex
§Decimal
§Boolean
§Character
Access function
maps subscript expressions to an address in the array
Access function for single-dimensioned arrays:
address(list[k]) =
address (list[lower_bound]) + ((k-lower_bound) * element_size)
pointers
*A pointer type variable has a range of values that consists of memory addresses
and a special value, nil
*Provide the power of indirect addressing
*Provide a way to manage dynamic memory
*A pointer can be used to access a location in the area where storage is
dynamically created (usually called a heap)
Expressions
are the fundamental means of specifying computations in a
programming language
Essence of imperative languages is dominant role of
assignment statements
operator precedence rules for expression evaluation
define the order in
which “adjacent” operators of different precedence levels are evaluated
Typical precedence levels:
§parentheses
§unary operators
§** (if the language supports it)
§*, /
§+, -
Typical associativity rules
§Left to right, except **, which is right to left
§Sometimes unary operators associate right to left (e.g., in FORTRAN)
operator associativity rules for expression evaluation
define the order in
which adjacent operators with the same precedence level are evaluated
Precedence and associativity rules can be overridden with
parentheses
Operand evaluation order:
§Variables: fetch the value from memory
§Constants: sometimes a fetch from memory; sometimes the constant is in the
machine language instruction
§Parenthesized expressions: evaluate all operands and operators first
§The most interesting case is when an operand is a function call
Subtle but important differences in the semantics of assignment in different
imperative languages
Context based: a variable may refer to the value of the variable (r-value) or its
location (l-value) – a named container for a value
Value model of variables
an expression is either an l-value or an r-value, based
on the context in which it appears:
Reference model of variables
a variable is a named reference for a value –
every variable is an l-value:
control structure
a control statement and the statements whose execution it
controls
Design question:
§Should a control structure have multiple entries?
selection statement
provides the means of choosing between two or more
paths of execution
2 categories of selection statements
§Two-way selectors
§Multiple-way selectors
General design issues for iteration control statements:
§How is iteration controlled?
§Where is the control mechanism in the loop?
Iterative Statements
The repeated execution of a statement or compound statement is accomplished
either by iteration or recursion
purpose of guarded commands
to support a new programming methodology that supported verification
(correctness) during development
Basic Idea: if the order of evaluation is not important, the program should not
specify one
subprogram linkage
The subprogram call and return operations of a language
General semantics of calls to a subprogram:
§Parameter passing methods
§Stack-dynamic allocation of local variables
§Save the execution status of calling program
§Transfer of control and arrange for the return
§If subprogram nesting is supported, access to nonlocal variables must be arranged
Activation Record
*The activation record format is static, but its size may be dynamic
*The dynamic link points to the top of an instance of the activation record of the
caller
*An activation record instance is dynamically created when a subprogram is
called
*Activation record instances reside on the run-time stack
*The Environment Pointer (EP) must be maintained by the run-time system. It
always points at the base of the activation record instance of the currently
executing program unit
static chain
a chain of static links that connects certain activation record
instances
dynamic scoping deep access
non-local references are found by searching the activation record
instances on the dynamic chain:
§Length of the chain cannot be statically determined
§Every activation record instance must have variable names
static scoping shallow access
put locals in a central place:
§One stack for each variable name
§Central table with an entry for each variable name
