Transcript A Big Test Result - Knowledge Systems Institute

Programming Languages
Functional Programming
Languages
This lesson describes the concept of a function and
how programs can be viewed as functions. We
then study a functional language – Lisp, and
discuss some of its fundamental properties.
Functions and Programming
• Functional programming has a number of distinct
advantages, which have traditionally made it
popular for artificial intelligence, mathematical
proof systems, and logic applications.
• These include the uniform view of programs as
functions, the treatment of functions as data, the
limitation of side effects, and the use of automatic
memory management.
• A functional programming language has as a
result great flexibility, conciseness of notation,
and simple semantics.
The Drawback
• The major drawback has traditionally been the
inefficiency of execution of functional languages.
• Because of their dynamic nature, such languages
historically were interpreted rather than compiled,
• with a resulting substantial loss in execution speed.
• Even when compilers became available, the
speedups obtained were inadequate.
• But the semantic simplicity and orthogonality of
design have made it a reasonable alternative for
teaching computer science.
Programs as Functions
• A program is a description of a specific computation
• If we ignore the details of the computation, and
focus on the result, then a program becomes
simply a "black box" for obtaining output from
input.
• From this point of view, a program is essentially
equivalent to a mathematical function:
• Definition: A function is a rule that associates to
each x from some set X of values a unique y from
another set Y of values: y = f(x)
Variables and Assignments
• We can think of programs, procedures, and
functions in a programming language as all being
represented by the mathematical concept of a
function.
• In mathematics there is no concept of memory
location, or values of variables, so that an
assignment statement such as x = x + 1 makes
no sense in functional programming.
• In this sense, in functional programming, there are
no variables, only constants, parameters, and
values.
Loops
• Most modern functional programming languages
retain some notion of variable and assignment,
and so are "impure”.
• Pure functional programming is Turing complete in
that any computation may be described using
functions alone.
• One consequence of the lack of variables and
assignment in functional programming is that there
also can be no loops.
• A loop must have a control variable that is assigned
as the loop executes, and this is not possible
Recursion
• How do we write repeated operations in functional
form? Recursion is the essential feature.
Example 2, Translation of first-order
predicate calculus
• Another consequence of the lack of variables and
assignment is that there is no notion of the
internal state of a function:
• The value of any function depends only on the
values of its parameters, and not on any previous
computations, including calls to the function itself.
• The property that a function’s value depends only
on the values of its parameters is called referential
transparency.
• The value of any function also cannot depend on
the order of evaluation of its parameters.
No State
• The lack of variables and the referential
transparency of functional programming make the
semantics of functional programs particularly
straightforward: there is no state.
• Indeed, the lack of local state in functional
programming makes it in a sense the opposite of
object-oriented programming, where computation
proceeds by changing the local state of objects.
Generality
• We express this generality of functions in
functional programming by saying that functions
are first-class values.
• Composition is itself a function that takes two
functions as parameters and produces another
function as its returned value. Such functions are
sometimes called higher-order functions.
Function Definitions in Lisp
• When the Lisp interpreter evaluates a list, it looks
to see whether the first symbol on the list has a
function definition attached to it;
• or, put another way, whether the symbol points to
a function definition.
• If it does, the computer carries out the instructions
in the definition.
• A symbol that has a function definition is called a
function.
Function Definitions in Lisp (2)
• Lisp function definition has up to five parts:
• (defun function-name (arguments...)
"optional-documentation..."
(interactive argument-passing-info);
optional body...
)