Precious words are like falling glass... We must act quickly to catch them before they shatter into an oblivion.... My friend asked some questions about basic principles of programing paradigms that are contemporary to today's Computer Science world....
1. What makes a language functional, logic programming or procedural ?
A procedural or imperative language focuses on telling the computer
what to do, step by step. These are descended from Turing machines
and assembly language. You knew a lot about them before this course.
A logic programming language focuses on computation as constructive
proofs, i.e., proving a term that says that two employees or three
numbers are in a particular relationship. Typically unification and
backtracking are used to help efficiently construct the proofs, but
there are other possible strategies. These languages are descended
from Prolog, and you have been learning about them.
A functional language focuses on computation as the evaluation of
mathematical functions. These are descended from the lambda calculus
and Lisp. I'll say a little more below in answer to your questions.
In a purely functional language, a program simply defines a bunch of
functions, in the mathematical sense of "function." The return value
of a function depends only on its arguments; the function has no side
effects and is not sensitive to side effects, so it returns the same
value every time it's called.
Of course, you can program in this functional style in other
languages, too. But programming in a actual functional language
forces you to learn this style. :-) More important, compilers for a
functional language can take advantage of the guaranteed lack of side
effects to introduce optimizations -- including memoization and lazy
evaluation.
In a really pure functional language, the only thing that happens
within a function is to call other functions -- e.g., you would define
f(x,y) as g(h(x),f(x,minus(y,1))). This is just putting f,g,h, and
minus together by wiring the outputs of some functions into the inputs
of others. Note that minus is presumably a built-in function. So are
conditionals: if(condition, then-value, else-value).
Similarly, in a really pure logic language, the only thing that a
query can do is to combine other queries by unifying their arguments,
which is similar to the way that a function call in a functional
language combines other function calls by wiring their inputs and
outputs together. A query may also have nondeterminism, e.g., there
may be a choice of several ways to answer it (e.g., several clauses
with the same head). This is why constructing a proof may involve
backtracking.
So in both pure functional and pure logic programming languages, there
is no mechanism for modifying values. This rules out side effects,
but it actualy rules out more than that, because there's not even a
way to modify values privately within the definition of a function.
Objects can't be modified once they're created. Indeed, there is no
way even to change the value of a variable! (You can introduce a
LOCAL variable as a temporary name for something, but once you've
introduced it, its value will never change (except perhaps for being
specialized through unification), and it goes away once you leave the
scope where the variable was introduced.)
As an example, you can't write loops since you can't change the loop
variable. You use recursion instead. This introduces new local
variables on every recursive call rather than changing the value of
your loop variable. The compiler may secretly turn the recursive
calls back into loops where it can, of course.
As another example, you can't write a destructive function to append
two lists A and B, i.e., changing the last pointer of A to point to
the start of B, because this would be a side effect. You have to
write a function that leaves A and B intact and returns a new list C,
which is basically the list that you would get if you made a copy of A
and changed the last pointer of the copy to point to the start of B.
(There is no need to copy B.)
As another example, you can't easily memoize the result of a function,
because it would be a side effect to store the result in an global
array that would be accessible to future calls of that function. To
avoid handling this as a side effect, you would have to pass the array
as an argument to the function, and the function would return a
modified array that you could pass to the next call of the function.
Some functional or logic languages do have memoization built in,
however -- the lack of side effects means that the memo will remain
valid.
Many functional and logic languages are not pure, though -- they are
extended with some ability to have side effects. In Prolog, there are
"assert" and "retract" predicates which actually modify the program as
it's running (e.g., adding new facts to the database) if you query
them. The original functional language Lisp allows modification fo
both local and global variables. Several recently developed
functional languages like OCaml and Haskell have more principled or
careful ways to let side effects into the language in restricted
circumstances.
Is it ability to use functions as arguments to other functions ?
No, but this is indeed a feature commonly found in functional
languages. That is because the feature is useful, and because those
languages are mainly descended from the lambda calculus, in which
functions are the only objects in the language.
A language "has first-class functions" if functions can be treated
like any other object, e.g.,
* as the argument to another function
* as the return value of another function
* as the value of a variable
* as fair game for type checking (i.e., if there is a strong type
system, then it must distinguish different types of functions, e.g.,
by their input and output types)
A "higher-order function" is a particular function that has other
functions as arguments or return values. A language that has
first-class functions obviously allows higher-order functions.
If it is then what is python ?
Python is a procedural, object-oriented language that has first-class
functions, recursion, and other things that make it easy to program in
a functional style if you choose not to use any side effects.
2. How important is the concept of immutability to any functional
programming language ?
Immutability means that objects can be created but not subsequently
modified. In pure functional languages, everything is immutable, as
noted above.
3. How is functional programming different from logic programming ?
Logic programming usually has nondeterminism (backtracking) and
unification as built-in features. Few functional programming
languages have this.
Logic programming doesn't have return values; it describes relations
like times(A,B,C) (which is either provable or not) rather than
functions like times(A,B).
Logic programming generally does *not* have higher-order functions,
since it doesn't have functions. But there are logic programming
languages that do, like lambda-Prolog.
