CSE 3302 Exam 2

When Functional Programmers talk of Purity, they are referring what?

Pure Functions

Definition of Pure Functions

/*

Some of its examples in JavaScript:

var z = 10;

function add(x, y) {return x + y;}

*/

Simple functions which only operate on their input parameters.

List different styles of programming

/*

Different languages have evolved to support each style of programming

Each type of language rests on a distinct model of computation, which is different from the von Neumann model

*/

Functional programming, Logic programming, Object-oriented programming

Functional programming languages

1. Provides what

2. Treats functions as what

3. Provides prevention of what

4. Generally have what

/*

Useful for rapid prototyping, artificial intelligence, mathematical proof systems, and logic applications

*/

1. a uniform view of programs as functions

2. data,

3. side effects

4. simpler semantics and a simpler model of computation

Definition a side effect

/*

For example, a function which reads or writes from a variable outside its own arguments, a database, a file, or the console can be described as having side effects.

*/

when a function relies on, or modifies, something outside its parameters to do something.

Until recently, most functional languages suffered from what?

/ Most were originally interpreted instead of compiled /

inefficient execution

Today, functional languages are very attractive for general programming because

1. They lend themselves very well to what?

2. May be more efficient than what?

3. Have what?

1. parallel execution

2. imperative languages on multicore hardware architectures

3. mature application libraries

Despite these advantages, functional languages have not become mainstream languages for several reasons:

1. Programmers learn what first?

2. OO languages provide what?

1. imperative or object-oriented languages first

2. a strong organizing principle for structuring code that mirrors the everyday experience of real objects

Functional methods (such as WHAT) have become part of many programming languages

recursion, functional abstraction, and higher-order functions

1. Definition of a program

2. If we ignore the "how" and focus on the result, or the "what" of the computation, the program becomes a virtual black box that transforms input into output. A program is thus essentially equivalent to what

1. a description of specific computation

2. a mathematical function

Definition of a function

/*

In mathematical terminology, the function can be written as y=f(x) or f:X->Y

*/

a rule that associates to each x from set of X of values a unique y from a set Y of values

1. what is domain of f

2. what is range of f

1. The set X

2. The set Y

1. what is an independent variable

/*

In math, there is not always a clear distinction between a parameter and a variable- The term independent variable is often used for parameters

*/

2. what is a dependent variable

3. what is a partial function

1. the x in f(x), representing any value from the set X

2. the y from the set Y, defined by y=f(x)

3. occurs when f is not defined for all x in X

Definition of Total function

a function that is defined for all x in the set X

Definition of Functional definition

describes how a value is to be computed using formal parameters

Definition of Functional application

a call to a defined function using actual parameters, or the values that the formal parameters assume for a particular computation

A major difference between imperative programming and functional programming is the concept of a variable:

1. In math, variables always stand for what

2. In imperative programming languages, variables refer to what

3. Assignment statements allow memory locations to be what

In math, there are no concepts of memory location and assignment

1. actual values

2. memory locations that store values

3. reset with new values

1. Functional programming takes what to the concept of a variable

– Variables are bound to values, not memory locations

– A variable’s value cannot change, which eliminates assignment as an available operation

2. Most functional programming languages retain what

– It is possible to create a pure functional program that takes a strictly mathematical approach to variables

3. Lack of assignment makes loops impossible

– A loop requires a control variable whose value changes as the loop executes

– what is used instead of loops

4. There is no notion of what

– Its value depends only on the values of its arguments (and possibly nonlocal variables)

A function’s value cannot depend on the order of evaluation of its arguments

– An advantage for concurrent applications

1. a mathematical approach

2. some notion of assignment

3. recursion

4. the internal state of a function

1. Definition of Referential transparency

Examples:

– gcd function is referentially transparent

– rand function is not because it depends on the state of the machine and previous calls to itself

2. A referentially transparent function with no parameters must always return what. Thus it is no different than a constant

1. the property whereby a function's value depends only on the values of its variables (and nonlocal variables)

2. the same value

1. Definition of Value semantics

2. Lack of what in functional programming makes it opposite of OO programming, wherein computation proceeds by changing the local state of objects

In functional programming, functions must be general language objects, viewed as values themselves

1. semantics in which names are associated only to values, not memory locations

2. local state

1. In functional programming, functions are what

2. Functions can be what

3. Functions can be what to other functions

1. first-class data values

2. computed by other functions

3. parameters

1. Definition of Composition

2. A function takes two functions as parameters and produces what as its returned value

In math, the composition operator o is defined: If f:X->Y and g:Y->Z, then g o f:X->Z is given by (g o f)(x) = g(f(x))

1. essential operation on functions

2. another function

True / False:

1. All procedures are functions that distinguish incoming values (parameters) from outgoing values (results)

2. In pure functional programming, there are no assignments

3. In pure functional programming, there are no loops

4. Value of a function depends only on its parameters, not on order of evaluation or execution path

5. Functions are first-class data values

1. True

2. True

3. True

4. True

5. True

1. Lisp (LISt Processing): first language that what

Features included:

2. Uniform representation of programs and data using a single general structure: what

– Definition of the language using an interpreter written in the same language (metacircular interpreter)

– Automatic memory management by the runtime system

1. contained many of the features of modern functional languages

2. the list

• All programs and data in Scheme are considered expressions. Two types of expressions:

1. what: like literal constants and identifiers of an imperative language

2. what: a sequence of zero or more expressions separated by spaces and surrounded by parentheses

3. Syntax is expressed in what

Syntax of Scheme:

expression -> atom | ‘(‘ {expression} ’)’

atom -> number | string | symbol | character | boolean

1. Atoms

2. Parenthesized expression

3. extended Backus-Naur form notation

Some more info

1. if form: like an what construct

2. cond form: like an what construct; cond stands for conditional expression

3. Special form let Definition

– Example: (let ((a 2) (b 3)) (+ 1 b))• First expression in a let is a binding list

4. lambda special form Definition

Example: (lambda (radius) (* 3.14 (* radius radius)))

5. letrec special form Definition

Example: (letrec ((factorial (lambda (n) (if (= n 0) 1 (* n (factorial (- n 1))))))) (factorial 10)

6. define special form Definition

7. delay special form: Definition

8. force special form: Definition

1. if-else

2. if-elseif

3. binds a variable to a value within an expression

4. creates a function with the specified formal parameters and a body of code to be evaluated when the function is applied

5. works like a let but allows arbitrary recursive references within the binding list

6. creates a global binding of a variable visible in the top-level environment

7. delays evaluation of its arguments and returns an object like a lambda "shell" or promise to evaluate its arguments

8. causes its parameter, a delayed object, to be evaluated

Scheme’s semantics include what

– Only values, not variables, have data types

– Types of values are not checked until necessary at runtime

dynamic or latent type checking

Definition of Tail recursive

when the recursive steps are the last steps in any function

1. Basic data structure in Scheme is what

2. Scheme also supports structured types for what

List functions:

3. ???: accesses the head of the list

4. ???: returns the tail of the list (minus the head)

5. ???: adds a new head to an existing list

6. ???: returns true if the list is empty or false otherwise

Example: a list representation of a binary search tree

("horse" ("cow" () ("dog" () ())) ("zebra" ("yak" () ()) () ))

1. the list

2. vectors (one-dimensional arrays) and strings

3. car

4. cdr

5. cons

6. null?

Definition of Higher-order functions

• Example: function with a function parameter that returns a function value

(define make-double (lambda (f) (lambda (x) (f x x)))

• Can now create functions using this:

(define square (make-double *))(define double (make-double +))

functions that take other functions as parameters and functions that return functions as values

Definition of Garbage collection

automatic memory management technique to return memory used by functions

Definition of Static scope (or lexical scope)

– For static scoping, the meaning or value of a variable can be determined by reading the source code

– For dynamic scoping, the meaning depends on the runtime context

the area of a program in which a variable declaration is visible

Free variable

a variable referenced within a function that is not also a formal parameter to that function and is not bound within a nested function

Bound variable

a variable within a function that is also a formal parameter to that function

Metalinguistic power

the capacity to build, manipulate, and transform lists of symbols that are then evaluated as programs

Currying

a process in which a function of multiple parameters is viewed as a higher-order function of a single parameter that returns a function of the remaining parameters

A language is said to be fully curried if what

function definitions are automatically treated as curried and all multiparameter built-in functions are curried

In a language with an applicative order evaluation rule, all parameters to user-defined functions are what

evaluated at the time of a call

Nonstrict Definition

a property of a function in which delayed evaluation leads to a well-defined result, even though subexpressions or parameters may be undefined

1. what allows overloading of functions

• Type class:

– A set of types that all define certain functions

– Specifies the names and types (called signatures) of the functions that every type belonging to it must define

2. Instance definition Definition

3. Many type classes themselves are defined to be part of other type classes, called what

1. Haskell

2. contains the actual working definitions for each of the required functions

3. type class inheritance

1. Lambda calculus invented by who and when

2. Lambda abstraction Definition

1. invented by Alonzo Church in the 1930s

2. the essential construct of lambda calculus

1. Object-oriented programming languages began when with what language?

2. – Goals were to incorporate the notion of what, with properties that control its ability to react to events in predefined ways

– Factor in the development of abstract data type mechanisms

– Crucial to the development of the object paradigm itself

3. By what time, interest in object-oriented programming exploded

1. in the 1960s with Simula

2. an object

3. the mid 1980s

Object-oriented programming languages satisfy three important needs in software design:

1. Need to reuse what as much as possible

2. Need to modify what

3. Need to maintain what

1. software components

2. program behavior with minimal changes to existing code

3. the independence of different components

Four basic ways a software component can be modified for reuse:

1. ???

– Example: adding new methods to a queue to allow elements to be removed from the rear and added to the front, to create a double-ended queue or deque

2. ???

– Example: if a square is obtained from a rectangle, area or perimeter functions may be redefined to account for the reduced data needed

3. ???

– Example: can combine a circle and rectangle into an abstract object called a figure, to contain the common features of both, such as position and movement

4. ???

– Examples: overloading and parameterized types

1. Extension of the data or operations

2. Redefinition of one or more of the operations

3. Abstraction

4. Polymorphism

Definition of Application framework

– Examples: Microsoft Foundation Classes in C++ and Swing windowing toolkit in Java

a collection of related software resources (usually in object-oriented form) for developer use

1. Object-oriented languages have another goal, which is what

And Mechanism for that:

2. ???

3. ???

1. restricting access to internal details of software components

2. Encapsulation mechanisms

3. Information-hiding mechanisms

Smalltalk

1. originated from what

2. when

3. was influenced by what language

4. ANSI standard was achieved when

5. has the most consistent approach to what

– Everything is an object, including constants and the classes themselves

1. Dynabook Project at Xerox Corp.'s Palo Alto Research Center

2. in the early 1970s

3. Simula and Lisp

4. in 1998

5. object-oriented paradigm

1. Every object in Smalltalk has what

2. ???: a request for service

3. ???: object that receives a message

4. ???: how Smalltalk performs a service

5. ???: originator of the message

6. ???: messages that result in a change of state in the receiver object

7. ???: process of sending and receiving messages

8. ???: the set of messages that an object recognizes

9. ???: the message name

10. ???: object receiving the message is written first, followed by the message name and any arguments

11. ???: are enclosed in double quotation marks

12. ???: causes Smalltalk to evaluate the code you have entered

13. ???: returns the number of elements in a set

14. ???: a message sent to a class

15. ???: a message sent to an instance of a class

16. ???: one with no arguments

17. ???: messages that expect arguments; name ends in a colon

18. ???: allow you to write arithmetic and comparison expressions with infix notation

(Binary messages, Keyword messages, Instance message, size message, Unary message, Class message, Message passing, Interface, Selector, Syntax, Comments, Show it option, Mutators, Sender, Method, properties and behaviors, Receiver, Message)

1. properties and behaviors

2. Message

3. Receiver

4. Method

5. Sender

6. Mutators

7. Message passing

8. Interface

9. Selector

10. Syntax

11. Comments

12. Show it option

13. size message

14. Class message

15. Instance message

16. Unary message

17. Keyword messages

18. Binary messages

1. Temporary variables are declared between what and are not capitalized

2. Statements are separated by what

3. Smalltalk variables have no assigned what

– Any variable can name any thing

4. Assignment operator is ??? ( := / = / =:)

- Same as Pascal and Ada

1. vertical bars

2. periods

3. data type

4. :=

Smalltalk’s variables use what ( reference semantics / value semantics )

– A variable refers to an object; it does not contain an object

- to:do creates a loop

Block of code is enclosed in brackets [ ]

– Block is similar to a lambda form in Scheme

– Can contain arguments as block variables

reference semantics

Definition of Inheritance

supports the reuse of structure and behavior

Definition of Polymorphism

the use of the same names for messages requesting similar services from different classes

Concrete classes Definition

– Examples: Time and Date

classes whose objects are normally created and manipulated by programs

Abstract classes Definition

– Examples: Magnitude and Number

serve as repositories of common properties and behaviors for classes below them in the hierarchy

Java

1. Originally intended as what

2. Provides what

3. Support for what

- Is purely object-oriented

1. a programming language for systems embedded in appliances

2. conventional syntax and a large set of libraries

3. compile-time type checking

1. ???: a static method

2. ???: allow programs to view but not modify the internal state of a class

3. ???: like methods, they specify initial values for instance variables and perform other initialization actions

– 4. ???: has no parameters

– 5. ???: when one constructor calls another

6. Java uses what ( reference semantics / value semantics )

( Class method, Accessor methods, Constructors, Default constructor, Constructor chaining )

1. Class method

2. Accessor methods

3. Constructors

4. Default constructor

5. Constructor chaining

6. reference semantics

1. ??? is the equality operator for primitive types, and also means object identity for reference types

2. Methods are invoked after instantiation using what

- Can nest operations

3. ??? is not allowed in java like c++

4. Java does not allow multimethods, in which more than one object can be the target of a method call

(dot notation, ==, multimethods, operator overloading)

1. ==

2. dot notation

3. operator overloading

4. multimethods

Framework: Definition

• java.util package: contains the Java collection framework

a collection of related classes

Interface Definition

– Serves as the glue that connects components in systems

– Contains only type name and a set of public method headers; implementer must include the code to perform the operations

a set of operations on objects of a given type

1. and E in the interface and method headers are what

2. ??? exploit parametric polymorphism

3. ??? a class defined within another class

– No classes outside of the containing class need to use it

4. ??? the collection object on which the iterator object is operating

(Backing store, type parameters, Private inner class, Generic collections)

1. type parameters

2. Generic collections

3. Private inner class

4. Backing store

Static binding Definition

– Actual code is not generated by the compiler unless the method is declared as final or static

process of determining at compile time which implementation of a method to use by determining the object's actual class

C++ was originally developed by who at AT&T Bell Labs

• Now includes multiple inheritance, templates, operator overloading, and exceptions

Bjarne Stroustrup

1. ???: instance variables

2. ???: methods

3. ???: subclasses

4. ???: superclasses

Three levels of protection for class members:

5. ??? members are accessible to client code and derived classes

6. ??? members are inaccessible to client code but are accessible to derived classes

7. ??? members are inaccessible to client and to derived classes

(Public, Private, Protected, Member functions, Derived classes, Base classes, Data members)

1. Data members

2. Member functions

3. Derived classes

4. Base classes

5. Public

6. Protected

7. Private

1. ???: initialize objects

2. ???: called when an object is deallocated

- Name is preceded the tilde symbol (~)

- Required because there is no built-in garbage collection in C++

Member functions can be implemented outside the declaration by using the scope resolution operator :: after a class name

1. Constructors

2. Destructors

Four basic kinds of polymorphism:

1. ???: type parameters remain unspecified in declarations

2. ???: different function or method declarations share the same name but have different types of parameters in each

3. ???: all operations of one type can be applied to another type

4. ???: a kind of subtype polymorphism

(Overloading (ad hoc polymorphism), Inheritance, Subtype polymorphism, Parametric polymorphism)

1. Parametric polymorphism

2. Overloading (ad hoc polymorphism)

3. Subtype polymorphism

4. Inheritance