Difference between revisions of "Mimir:Draft4 Chapter4"

From Openitware
Jump to: navigation, search
(Common Functions)
(Old introduction, full of material copied from web)
Line 22: Line 22:
  
 
* Recursion here?
 
* Recursion here?
 
= Old introduction, full of material copied from web =
 
 
* Sentences below match with Wikipedia page, need to rewrite and remove
 
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.
 
 
LISP is the earliest representative of the functional programming language paradigm. Unlike procedural and object-oriented languages - whose theoretical model of computation is the Turing Machine, LISP's theoretical model of computation is the Lambda calculus developed by Alonzo Church. (It can be shown that the two models of computation are equivalent in power - that is, any algorithm that can be expressed in one model can also be expressed in the other).
 
 
This difference might be understood in terms of the following diagram:
 
 
[[File:fig1.png]]
 
 
 
* Above figure from http://www.math-cs.gordon.edu/courses/cs323/LISP/lisp.html without reference and the text below
 
 
In procedural languages, code operates on data; in object-oriented languages, objects encapsulate code and data and interact with one another; in functional languages data flows through functions but has no separate existence of its own. That is, in procedural languages data is passive; in OO languages it is active; in pure functional languages it is ephemeral.
 
 
However, most functional languages (including LISP) provide a mechanism for keeping certain data in existence even when it is not flowing through functions. In LISP, this takes the form of what Common Lisp calls "special variables" - essentially equivalent to what in other programming languages are called "global variables". That is to say, though LISP is a functional language, it is not a pure functional language (though it could be used as one by avoiding imperative constructs.)
 
 
<!--
 
<font color=red>BELOW IS LIST SPECIFIC AND HIGHLIGHT CAR/CDR AND NOT FUNCTIONAL? (SS)</font>
 
 
[[File: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 in Artificial Intelligence'''
 
 
Lisp WAS used in AI until the end of the 1980s. In the 80s, though, Common Lisp was oversold to the business world as the "AI language"; the backlash forced most AI programmers to C++ for a few years.
 
 
1.Lisp is an excellent prototyping tool. It was the best for a very long time. Lisp is still great at tackling a problem you don't know how to solve yet. That description characterises AI perfectly.
 
 
2.Lisp supports symbolic programming well. Old AI was also symbolic. It was also unique in this regard for a long time.
 
 
3.Lisp is very powerful. The code/data distinction is weaker so it feels more extensible than other languages because your functions and macros look like the built-in stuff.
 
  
 
= Description =
 
= Description =

Revision as of 04:43, 11 April 2017

Back to Main Textbook Index


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 Concepts
  2. LISP Programming Language

Introduction

  • DONE Reduce the amount of detail here and push into other sections
  • Do mention research that created the language
  • Add info on LISP and creation
  • Add info on "split" of imperative and functional (FORTRAN and LISP)
  • Add note of academic use
  • Add (if info found) about modern uses (AI, other(AutoCad))


Functional programming is one of several paradigms that has been defined in the different categorical classifications of programming languages. Common descriptions of functional programming include a language that is similar to the evaluation of functions similar to mathematical notation and not using changing the state of variables during execution. Many other paradigms are extensions to imperative programming such as procedural, object and even graphical languages. Functional is unique where it is not a series of statements that form a program and its functions but a series of evaluations that create the program. Functional languages were studied as a method of computing before actual computers were available and are the result of evaluating a problems in mathematical terms and the study of the methods to solve the problem. The first actual imperative (FORTRAN) and functional (LISP) languages to run on actual computers were both implemented in the 1950's. As functional languages like LISP progressed some the features similar to imperative programming have evolved into the language. [CONFIRM SS]

  • Recursion here?

Description

  • Describe the parts of a functional language - ref to Backus article
  • Add more sections here following the update format by team

Functional languages are generally very concise and bounded by parenthesis similar to an algebraic formula. Each set of parenthesis is a function that will return a value into the function is part of. For examples LISP will be used. Typically a simple formula in algebra [ or MATH?] would be f(x) = a + b would in LISP would be (+ a b). The function bounded by the parenthesis would return the result of a + b. At this point it should be noted the LISP format replaces infix notation with prefix notation. The function f(f(x)) [CHECK] could be represented by (+ (+ a b))[CHECK CHECK].


Mathematical Programming Language

The functional programming paradigm has roots in mathematical studies of computing and uses formatting similar to the formal descriptions of functions. An example using a simple algebraic formula x = a + b translated into functional language using LISP would result in (+ 2 3) where a, b are represented by 2, 3 and the return of x is 5. In this example and other examples LISP uses prefix notation versus traditional infix notation. The translation of the simple addition example into a more formal function and then to LISP.

x = a + b
f(x) = a + b
f(a + b)
(+ a b) where a,b are replaced by valid types
>(+ 2 3)
>5

An important concept to expand the capability of a functional language is the values in a function can be functions or even functions of functions. LISP also supports lists as input which will not be detailed here but can be seen in the programming section below. The use of a function as a value in another function is known as composite functions.

x = a + (b - c)
f(x) = a + f(y)
where f(y) = b - c
f(a + (b - c)) where a,b,c are replaced by valid types
>(+ 2 (- 3 4))
>1

To use a function on the return of the same function a function needs to be defined in the example using LISP. The function can then operate on a result it returns. In the example below 2 will be squared returning 4 to square(x) and then return 16.

f(f(x))
In LISP if the following function is defined: (defun square(x) (* x x))
>(square (square 2))
> 16

In functional programming the mathematical concept of recursion is a method of iteration in a function. A function will refer to itself [need simple example to demonstrate][need to show power symbol]

f(f(x))



  • Add Lambda calculus information or section
  • Add fucntion description with both f(x) and f(x, y, z, etc) on left side
  • Add info about early theory or study of computation before computers
  • Add in key figures (some redundancy)
  • Clean up above to a more defined example for concept of functional program

Difference From Imperative Languages

Note: Imperative have the statement and store flow, not evals and return of evals

One major advantage of the most basic concept of an imperative language over functional is the visible flow of the instructions in the code. Disregarding the states of variables and the program is the concept of a "recipe" which can be seen in the code to understand the solution of the problem. Functional programming especially in its purest form does not allow iteration and therefore results in the use of recursion. Defined functions cannot do multiple actions except with conditionals which can be limited. The programming technique of functional programming requires all functions or evaluations to return into another layer of evaluations. An imperative language can make a list in order of execution to be performed whereas functional programming requires layers of nesting by parenthesis to order evaluation.

  • [ADD THE ALGEBRA-RECIPE CONCEPT IS OK] Add simple description of "recipe" vs. algebraic
  • Add note of state and storage vs. () eval and return
  • Add any BNF differences

Functional Languages List

Note: Get more for these, find others

  • 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.
  • APL

LISP Programming

History

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.

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

An atom is a word or a number or the pair of parentheses "()" which we will call "NIL". So, by that description, all of the following are atoms:

hello
()
car
axe
0
stephen
12345

In fact, there are a few more things that we can use as atoms also. The rules for creating atoms are, to be exact, as follows.

  • An atom can be any number the computer understands. This is called a numeric atom. These are integers like: 145, -15, 0, etc., or floating point numbers [ones with fractional parts] like: 1.4, -56.3, etc.
  • A non-numeric atom can be any name made up of letters and/or numbers. There is no limit on the length of this. The only restriction is that the first character must be a letter, not a number. This is called an alphanumeric atom.
  • The form of NIL "()" can be an atom.
  • Alphanumeric atoms can have some funny characters in them [such as "*" and "+"] but special Lisp characters cannot be used in atom names. This should be clear by now. The characters "(", ")", and "'", would simply confuse Lisp if you tried to use them in atom names. In general, we avoid using anything other than the letters "A" through "Z" and the numbers "0" through "9" in atom names.
  • Indivisible things like 27, 3.14 and + which have obvious meaning, as well as things like Foo and B27 that are called atoms.
  • Atoms like 27 and 3.14 are called numeric atoms and atoms like Foo and 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.

When working with numbers, like 2 and 3, Lisp makes it easy to work with a group of several items, called a list. To specify a list of items you enclose the items in brackets. For example, the list of two-digit squares is:

(16 25 36 49 64 81)

A list containing no items is called the empty list. You can write it as:

()

but it is also called nil.

In fact we can ask the Lisp to evaluate a list:

(+ 2 3 4)

This was a list of four items: the symbol +, and the numbers 2, 3, and 4. When Lisp evaluates a list it treats the first item as the name of a procedure, and the remaining items as the arguments to the expression.

The output is ,

9

This illustrates one of the remarkable features of Lisp - Lisp programs and Lisp data are both expressed in the same way, as lists.

LISP Interpreter and the Polish notation

(function_name argument1 argument2 ... argument)

(+ 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

  • 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