Mimir:Draft3 Chapter4

From Openitware
Jump to: navigation, search

Back to Table of Contents


Chapter 4: Functional Programming

"Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot." - Eric Raymond

In this chapter you will learn:

  1. Functional Programming Basics
  2. LISP Programming Language

Introduction

In computer science, functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Functional programming emphasizes functions that produce results that depend only on their inputs and not on the program state—i.e. pure mathematical functions. It is a declarative programming paradigm, which means programming is done with expressions. In functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function f twice with the same value for an argument x will produce the same result f(x) both times. Eliminating side effects, i.e. changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.

What is a functional language?

The functional programming paradigm is based on mathematical functions. The objective of the design of a functional programming language is that it allows the program to heavily rely on mathematical functions. Contrary to imperative languages, a purely functional programming language does not use variables or assignments. This frees the programmer any concerns about memory allocation, or state of the program. One main difference due to the non-existence of variables is that iterative constructs are not possible since they are controlled by variables. Thus, repetition (i.e. loops) must be obtained through recursion rather than iteration. This also makes testing easier since each function can be tested without any concerns for its context.

LISP2.JPG

There are various functional Programming languages like LISP, ML,Erlang,Haskell.

  • LISP: Began as purely functional language but soon acquired some important imperative features that increased its execution efficiency.
  • ML: ML is strongly typed functional language with more conventional syntax than LISP.
  • HASKELL: Haskell is partially based on ML but is a purely functional language.

Though there are many functional languages, the language we will focus on is "LISP",oldest and most widely used language.

Lisp

Lisp was invented by Artificial Intelligence (AI) pioneer John Mc Carthy in the late 1950s. McCarthy published its design in a paper in Communications of the ACM in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" (interesting that "Part II" was never published). LISP was intended as a mathematical formalism for reasoning about the use of recursion equations as a model for computation. Of computer languages still in widespread use today, only Fortran is older.

The Lisp family of languages has evolved with the field of computer science, both by putting the best ideas from the field into practical use, and by contributing many such ideas. The association of Lisp with research, however, has not always been beneficial. Lisp has always been among the main tools of AI since the beginning. When the commercial AI market failed to deliver on its promises, Lisp was blamed as a scapegoat. In the late 1980s, many companies abandoned Lisp in favor of other languages, starting the so called "AI winter". Although Lisp survived the crisis, some of the resulting prejudice and lack of information is still present in the computing field.

With growing popularity of LISP, many dialects were developed and were being used by LISP users by 1980's. The LISP community started a consolidation effort to design the Common Lisp dialect, which became the standard and commercial version of LISP.


Mathematical Programming Language

Describes how a Functional Language is derived from mathematical functions.

What is a mathematical function?

f(x) = x + 1;

g(x) = (x + 32) * 5 / 9

  • Lambda expression

LISP, the first Functional Language

The oldest and most widely used functional language is Lisp.The functional programming paradigm, which is based on mathematical functions, is the design basis for one of the most important non-imperative styles of languages.This style of programming is supported by functional, or applicative, programming languages.Lisp began as a purely functional language, but it soon acquired some important imperative features that increased its execution efficiency.COMMON Lisp is an amalgam of several early 1980’s dialects of Lisp

LISP data types and objects

LISP has two categories of data objects:

  • Atoms
 Indivisible things like 27,3.14 and + which have obvious meaning, as well as things like FOO,B27 are called atoms.
 Atoms like 27 and 3.14 are called numeric atoms and atoms like FOO B27 are called symbolic atoms.
  • Lists
 A list consist of a left parenthesis ,followed by zero or more atoms or lists, followed by a right parenthesis.

LISP Interpreter and the Polish notation

(function_name argument1 argument2 ... argumentn)

(+ 2 2) -> returns 4

(+ 2 4 6 8 10) -> returns 30

Common Functions

Assignment: set (remind readers to quote arguments with ' to prevent evaluation)

The set function takes two arguments and sets the symbol of the second to the symbol of the first argument. The second argument could be a list of Atoms and the whole list will be set to the symbol of the first argument. This is much like setting and initializing variables in other programming languages (int c = 2;). Both arguments need to be single quoted so that the first argument is not evaluated as a function. The setq function can be used and the single quote for the first argument can be dropped because the q on the end of set signifies quote.

Examples:
(set ‘k ‘(a b c d e))
(setq k ‘(a b c d e))
(print k) returns (a b c d e)

Math functions: +, -, *, /

The grammatical structure that is used to perform mathematical computations in Lisp is a bit different then in a normal mathematics problem. In a mathematical problem we say “2 plus 4”. In Lisp we call the math operation first then the two arguments, so the problem is stated “Add(+) 2 and 4, Subtract(-) 2 from 4, Multiply(*) 2 and 4, or Divide(/) 2 by 4”.

Example:
 Mathematically: 2 + 4 = 6, 2 - 4 = 2, 2 * 4 = 8, 2 / 4 = ½ 
 Lisp: (+ 2 4) returns (6)
       (- 2 4) returns (2)
       (* 2 4) returns (8)
       (/ 2 4) returns (½)

After the first operation argument there can be one or many arguments that will be evaluated from left to right. When adding or multiplying the order of the second through last arguments doesn’t matter, but be aware that, just like in mathematics, with subtraction and division the order the arguments are arranged in matters.

Examples:
(+ 1 2 3 4 5) returns (15)
(- 1 2 3 4 5) returns (-13)
  whereas
(- 5 4 3 2 1) returns (-5)

List functions: list, cons, append, car, cdr

  • Cons : Cons takes an expression and a list and returns a new list whose first element is the expression and whose remaining elements are those of the old list:
  • Append : Combines the elements of all lists supplied as arguments.
  • List : List does not run things together like APPEND does.Instead,it makes a list out of its arguments. Each argument becomes an element of the new list.

Defining functions: defun

The defun function is used for programming defined functions.

(defun <function name> (<arg1> . . . <argn>)
	( <function body> )
)

Conditional functions: cond, null

Conditional Functions -

  • Cond - This function is like the IF statement in other languages and can take the form of an if-else-if statement. When Cond is called the first conditional statement will be evaluated and if true then the next part will be evaluated and so on to the last Atom which then becomes the returned value. If the first conditional statement is false the second conditional statement will be evaluated and so on until a conditional statement tests true. In the last conditional statement a T can be used to force TRUE condition and have a value returned.
  • Null - This is used to evaluate an Atom to see if it have a value and returns either T (True) or NIL (False). Used many time as the first statement in a cond function to see if the Atom is not NIL and can be run through the conditional statements. (NULL X) is TRUE if X is NIL.
(cond 
       ( <conditional 1> <function call or return value 1> )
       ( <conditional 2> <function call or return value 2> )
       ( <conditional n> <function call or return value n> )
       ( T               <function call or return value for default case> )
)

Recursive functions: differentiate recursive from iterative

Recursion in Lisp - Is the ability of a function to call itself from within itself. This condition then repeats until the call to itself is NIL.

Example  palindrome2 () 
(defun palindrome2 ()
    (set 'k '(a b c d))
    (append k (cdr (myReverse k)))
)
(defun myReverse (k)
    (cond
        ((NULL k) k)
        (T (append (myReverse (cdr k)) (list (car k))))
    )
)
Example Fibonacci () 
(defun fib (n)
    (cond
        ((= n 0) 0); if 0 by definition it's 0
        ((= n 1) 1); if 1 by definition it's 1
        (T (+ (fib (- n 1)) (fib (- n 2))) ); if > 1 then add two previous values
    )
)

Summary

A quick summary of the chapter should go here

Key Terms

LISP: LISt Processing.

Atoms: In the original LISP there were two fundamental data types: atoms and lists. A list was a finite ordered sequence of elements, where each element is in itself either an atom or a list, and an atom was a number or a symbol. A symbol was essentially a unique named item, written as an alphanumeric string in source code, and used either as a variable name or as a data item in symbolic processing. For example, the list (FOO (BAR 1) 2) contains three elements: the symbol FOO, the list (BAR 1), and the number 2.

The essential difference between atoms and lists was that atoms were immutable and unique. Two atoms that appeared in different places in source code but were written in exactly the same way represented the same object,[citation needed] whereas each list was a separate object that could be altered independently of other lists and could be distinguished from other lists by comparison operators.

As more data types were introduced in later Lisp dialects, and programming styles evolved, the concept of an atom lost importance.

Car/cdr: In computer programming, car /ˈkɑr/ and cdr (/ˈkʌdər/ or /ˈkʊdər/) are primitive operations on cons cells (or "non-atomic S-expressions") introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.

Thus, the expression (car (cons x y)) evaluates to x, and (cdr (cons x y)) evaluates to y.


Cond - This function is like the IF statement in other languages and can take the form of an if-else-if statement. When Cond is called the first conditional statement will be evaluated and if true then the next part will be evaluated and so on to the last Atom which then becomes the returned value. If the first conditional statement is false the second conditional statement will be evaluated and so on until a conditional statement tests true. In the last conditional statement a T can be used to force TRUE condition and have a value returned.

Lists: A Lisp list is written with its elements separated by whitespace, and surrounded by parentheses. For example, (1 2 foo) is a list whose elements are three atoms: the values 1, 2, and foo. These values are implicitly typed: they are respectively two integers and a Lisp-specific data type called a "symbolic atom", and do not have to be declared as such.

The empty list () is also represented as the special atom nil. This is the only entity in Lisp which is both an atom and a list.

Expressions are written as lists, using prefix notation. The first element in the list is the name of a form, i.e., a function, operator, macro, or "special operator" (see below). The remainder of the list are the arguments. For example, the function list returns its arguments as a list, so the expression

(list '1 '2 'foo)

evaluates to the list (1 2 foo). The "quote" before the arguments in the preceding example is a "special operator" which prevents the quoted arguments from being evaluated (not strictly necessary for the numbers, since 1 evaluates to 1, etc.). Any unquoted expressions are recursively evaluated before the enclosing expression is evaluated. For example,

(list 1 2 (list 3 4))

evaluates to the list (1 2 (3 4)). Note that the third argument is a list; lists can be nested.

Recursion (Recursive Functions):

Null - This is used to evaluate an Atom to see if it have a value and returns either T (True) or NIL (False). Used many time as the first statement in a cond function to see if the Atom is not NIL and can be run through the conditional statements. (NULL X) is TRUE if X is NIL.

Symbolic expressions (S-expressions): In computing, s-expressions, sexprs or sexps (for "symbolic expression") are a notation for nested list (tree-structured) data, invented for and popularized by the programming language Lisp, which uses them for source code as well as data. In the usual parenthesized syntax of Lisp, an s-expression is classically defined[1] inductively as

   an atom, or
   an expression of the form (x . y) where x and y are s-expressions.

The second, recursive part of the definition represents an ordered pair so that s-exprs are effectively binary trees.

The definition of an atom varies per context; in the original definition by John McCarthy,[1] it was assumed that there existed "an infinite set of distinguishable atomic symbols" represented as "strings of capital Latin letters and digits with single embedded blanks" (i.e., character string and numeric literals). Most modern sexpr notations in addition use an abbreviated notation to represent lists in s-expressions, so that

   (x y z)

stands for

   (x . (y . (z . NIL)))

where NIL is the special end-of-list symbol (written '() in Scheme).

In the Lisp family of programming languages, s-expressions are used to represent both source code and data. Other uses of S-expressions are in Lisp-derived languages such as DSSSL, and as mark-up in communications protocols like IMAP and John McCarthy's CBCL. The details of the syntax and supported data types vary in the different languages, but the most common feature among these languages is the use of S-expressions and prefix notation.

Lambda expressions:

...other key terms:

Problem Sets

Basics 1. Evaluate the following expressions:

(+ 2 2)

(- 4 2)

(* 5 2)

(/ 10 5)

(/ 11 2)

(+ 1 2 3 4 5 6 7 8 9)

(* 1 2 3 4 5)

(* (+ 2 3) (/ 24 6))

(/ (* (- 212 32) 5) 9)

2. Evaluate the following forms:

(car '(a b c))

(cdr '(m n o p))

(car '((a b) (c d))

(cdr '((a b) (c d))

(car (cdr (car (cdr '((a b) (c d) (e f))))))

(car (car (cdr (cdr '((a b) (c d) (e f))))))

(car (cdr (car '(cdr ((a b) (c d) (e f))))))

(car (cdr '(car (cdr ((a b) (c d) (e f))))))

(car '(cdr (car (cdr ((a b) (c d) (e f))))))


3. Using only CAR and CDR, try to pick the atom PEAR our of the following lists:

(apple orange pear grape)

((apple orange) (pear grape))

(((apple) (orange) (pear) (grape)))

(apple (orange) ((pear)) (((grape))))

((((apple))) ((orange)) (pear) grape)

((((apple) orange) pear) grape)


4. Understanding APPEND and LIST

First let's define two lists, ab-list and cd-list as follows:

(setq ab-list '(a b) cd-list '(c d))

(append ab-list cd-list)

(list ab-list cd-list)

(append ab-list ab-list)

(list ab-list ab-list)

(append 'ab-list ab-list)

(list 'ab-list ab-list)

(list (car ab-list) cd-list)

(append (car ab-list) cd-list)


5. Defining your own function:

    (defun double (num)
       (* num 2))
    (defun half (num)
       (/ num 2))
    (defun Celcius (temp)
       (/ (* (- 212 32) 5) 9))

6. Conditionals. Evaluate these expressions:

  (setq bmi 25)
  (cond ((> bmi 30) 'obesity)
        ((> bmi 25) 'overweight)
        ((> bmi 20) 'normal-weight)
        (t 'underweight))
  (setq distance 40)
  (cond ((> distance 40) 'very-long-commute)
        ((> distance 30) 'long-commute)
        ((> distance 20) 'average)
        ((> distance 10) 'short-commute)
        (t 'no-commute))

7. Recursion

  (defun (factorial n) 
     (cond ((= n 0) 1)
           (t (* n (factorial (- n 1))))))

Top of Page - Prev Chapter - Next Chapter