Mimir:Draft6 Chapter4

From Openitware
Jump to: navigation, search

Back to Main Textbook Index


"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

Contents

Chapter 4: Functional Programming

In this chapter, you will learn:

  • What is a functional programming language?
    • How are they based in mathematics?
  • What are the main functional programming concepts?
  • What are the highlights of the LISP programming language?
    • How has LISP been used in Artificial Intelligence research?
    • What are atoms and lists in LISP?


Introduction

Functional programming is one of several programming language paradigms introduced in this text and in this chapter we go in more specific detail. Functional Programming is a paradigm, or pattern, that is similar to the evaluation of mathematical functions written in a mathematical notation. Functional programs do not use state changes of variables during execution. Many other paradigms can be considered as extensions of imperative programming such as procedural, object oriented and even graphical languages. Functional programming is unique, it is not a series of statements that form a program but a set of functions that turn into a series of evaluations that create the program.

Functional languages evolved from studies of formalizing notation of computation before modern computers had even been developed. The root of this work is by Alonzo Church and is known as lambda calculus. The calculus involved is the formal notation of how functions behave. [1] The use of functional languages is more accepted in academic institutions than in general programming use and is an example of an alternate to the more common program paradigms. Functional languages do provide a method to quickly prototype problems. For many years the functional language LISP was used in the study of AI.

The first actual imperative (FORTRAN) and functional (LISP) languages to run on actual computers were both implemented in the 1950's. 3 As functional languages like LISP progressed some of the features similar to imperative programming have evolved into the language. This can be considered a split between functional and imperative languages. Imperative has been the mainstream choice of programming. Procedural and Object Oriented languages would develop from the imperative paradigm.

What are functions?

A function is a mathematical idealization of how a variable quantity is dependent upon another quantity. It is a machine, or black box, that for any given input has a corresponding output.

In history, the concept of the function was elaborated with infinitesimal calculus at the end of 17th century, and, until the 19th century, the functions had a high degree of regularity. The concept of a function was formalized at the end of the 19th century with set theory, and this has grown the domains of the application of the concept of a function1.

Advantages of functional programming

Pure functions are easier to reason about because they can't do certain things, such as hidden inputs or modify hidden state. Functional programs are written at a higher level, and are therefore easier to comprehend. Testing is easier, and pure functions allow property-based testing. Debugging is also easier. Because pure functions depend only on their input parameters to produce their output, debugging applications written with pure functions is easier. Of course it’s possible to still make a mistake when you write a pure function, but once you have a stack trace or debug output, all you have to do is follow the values to see what went wrong. Overall, the loose coupling supports the goal readability and maintainability of the code. 5

A functional design assures that each modular part of a device has only one responsibility and performs that responsibility with the minimum of side effects on other parts. Since there are are fewer moving parts, such as no mutable variables and hidden state, the overall application is less complex. The biggest benefit of Functional programming is simplicity, because code can be more concise. A functional program doesn't create an iterator variable to be the center of a loop, so this and other kinds of overhead are eliminated from your code. Another major benefit is concurrency, which is easier to do with functional programming because the compiler is taking care of most of the operations which used to require manually setting up state variables (like the iterator in a loop).

Some performance benefits can be seen in the context of a single-processor as well, depending on the way the program is written, because most functional languages and extensions support lazy evaluation. Functional programming is being used as a safe way to program and a method to teach problem solving, algebra and geometric concepts. Combinatory logic and lambda calculus were both originally developed to achieve a clearer approach to the foundations of mathematics. Functional programming is modular in the dimension of functionality, whereas Object-Oriented Programming is modular in the dimension of different components.

Disadvantages of functional programming

Functional programs do not have assignment statements, that is, the value of a variable in a functional program never changes once defined. This can be a disadvantage, especially if we would like to change the variable value and would not be able to handle arrays very well like in imperative programming. Functional programming languages are typically less efficient in their use of CPU and memory than imperative languages such as C and Pascal. This is due to the fact that some mutable data structures like arrays have a very straightforward implementation using present hardware (a highly evolved Turing machine).

Writing pure functions is easy, but combining them into a complete application is where things can get hard. While recursion is a great concept to understand in order to be a better programmer, it often does not feel natural for many programmers. The advanced math terminology is also hard concept to understand for anyone. Another disadvantage is that because you can’t mutate existing data, you instead use a pattern that we can call, “Update as you copy.” In functional programming, you don’t mutate existing objects. Instead, what you do is (a) you copy an existing object to a new object, and then as a copy of the data is flowing from the old object to the new object, you (b) update any fields you want to change by providing new values for those fields. 6 In contrast, OOP is much easier to code because we can use subclasses and nested objects are easier to handle, as well.

Types

There are two main types of functions - ones that are pre-defined by the language, and ones that are defined by the user of the language.

Pre-Defined Functions

Predefined functions are functions that are already defined by the programming languages, such as modulus and power of. These functions can be accessed without programming any additional code to define the functions. Pre-defined functions go anywhere the language does, because they are built-in.

User-Defined Functions

User-defined functions are functions that are defined by the user. These can be highly customized, such as return the Fibonacci sequence up to a certain number, or return the Factorial of a certain number - which would just be all of the numbers up to that number multiplied against each other. User-defined functions are private, and only the creator(s) and anyone that the creator(s) share them with can have the functions.

General Concepts

Call By Value

Call by value, which is also referred to as "pass by value", is the most common evaluation strategy that is used in programming languages, in which the argument expression is evaluated, and the resulting value is bound to the corresponding variable in the function by copying the value into a new memory region.

Call by reference

Call by reference, also referred to as "pass by reference", is an evaluation strategy where a function receives an implicit reference to a variable used as an argument instead of a copy of the variable's value. This means that the function can modify the variable used as an argument. Call by reference can be used to provide communication between the called function and a calling function. A call-by-reference language makes it difficult to track the effects of a function call, and can introduce bugs into the program. 4

Function Overloading

Function overloading, or "method overloading", is the ability to create multiple methods of the same name with different implementations. Calls to an overloaded function will run a specific implementation of that function appropriate to the context of the call, allowing one function call to perform different tasks depending on context. An example of this would be a function called concatenate() that takes in either two strings, or two numbers, or a combination of strings and numbers.

Function Overriding

A feature that allows a function to override a specific implementation of a function that already exists.

I.e.

 (DEFUN ABS (NUM)
    (COND
        ((< NUM 0) (* NUM (- 1)))
        (T NUM)
    )
 )

Chapter 4 - Function Overriding.png

Pure functions

Pure functions, or expressions, have no side effects - which means that they don't store any values in memory, or process any input/output streams. If the result of a pure function isn't used, it can be removed without affecting other expressions.

If a pure function is processed with a set of arguments that cause no side-effects, the result is constant with respect to that argument list, which is sometimes referred to as "referential transparency". If the same pure function is called again with the same set of arguments, it returns the same result, which can enable caching optimizations.

If there is no dependency between the data of two different pure expressions, they are considered to be thread-safe.

If the programming language being used doesn't allow side-effects, or in other words if it is a purely functional programming language, then any evaluation strategy can be used. This allows the compiler the freedom to evaluate expressions in the program using deforestation, or other methods of re-ordering.

First Class Functions

Functional languages have functions that are known as first class functions. The concept of a first class function is that for the same input to the function, it will return the same result every time it is called. In imperative programs and its derivatives, this is not always the case since stored data that could be used when a function is called may have changed. That is because imperative data is global, while functional programming data is not.

Recursion

Recursion is possible in functional languages and this is often the method used for iteration. Early functional languages did not include the typical iteration and looping statements seen in many of the imperative program languages at the time. The example below can be seen using LISP to calculate a factorial given an input value.

( defun fact (n)
  ( cond 
    ( (equal n 0) 1 )
    (T ( * n (fact (- n 1)) ) ) 
  ) 
)

Mathematical Programming Language

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 it is part of. 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 + g(y)
where g(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

A composite function can also be created.

f(x) = x * 3
g(x) = x - 1
g(f(x)) = ( f(x) - 1 )
If x is 2 the composite function in LISP would be:  
>( - ( * 2 3 ) 1 )
>5

In LISP functions that are defined may use a single input or multiple inputs and can be represented as a function with multiple inputs.

f(x,y) = (x * x) + y
In LISP if the following function is defined: (defun func(x y) (+ (* x x) y))
>(func 2 1)
>5


Difference From Imperative Languages

One major advantage of the simplest concepts 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. An analogy is that an imperative program will operate like reading down a list of statements (like a recipe) where as a functional program will become an algebraic formula representing the program. The imperative flow will operate on and change data and the functional program will only use data as input and then return a result calculated from that data.

A Partial Functional Language List

Some common functional languages are:

  • LISP: First functional language. Started as purely functional language, but soon acquired some important imperative features that increased its execution efficiency.
  • ML: A strongly typed functional language with more conventional syntax than LISP.
  • HASKELL: Haskell is partially based on ML but is a purely functional language.
  • APL: An early functional language developed in 1960. One unique feature is the symbols used in the language.
  • R: An an open source programming language for statistics. It is considered a functional language and is a common language in use today for data analysis.


A Specific Example: LISP Programming

LISP is an acronym for "LISt Processing language" - so named because the list is one of the primary data structures in the language. Symbolic AI regards symbolic lists as being a key part of the way intelligent beings and systems actually store and manipulate information.

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). [2] LISP was intended as a mathematical formalism for reasoning about the use of recursion equations as a model for computation. Of the computer languages that are 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 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.

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

The description "Polish Notation" refers to the nationality of logician Jan Łukasiewicz, who invented the Polish notation in 1924. HP calculators for a while used "Reverse Polish Notation" which is the arguments followed by the function name. For example:

2 2 +   -> returns 4, and is entered without the parenthesis.

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)

The following table shows all the arithmetic operators supported by LISP. Assume variable A holds 10 and variable B holds 20 then: Examples

Operator Description Example
+ Adds two operands (+ A B) will give 30
_ Subtracts second operand from the first (- A B) will give -10
* Multiplies both operands (* A B) will give 200
/ Divides numerator by de-numerator (/ B A) will give 2
mod,rem Modulus Operator and remainder of after an integer division (mod B A )will give 0
incf Increments operator increases integer value by the second argument specified (incf A 3) will give 13
decf Decrements operator decreases integer value by the second argument specified (decf A 4) will give 9


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

Functional Programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It uses a declarative programming paradigm, which means programming is done with expressions or declarations instead of statements. In functional code, the output value of a function depends only on the arguments that are passed to the function, so calling a function f(x) twice with the same value for an argument x produces the same result f(x) each time; this is in contrast to procedures depending on a local or global state, which may produce different results at different times when called with the same arguments but a different program state. 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 benefits for the usage of functional programming.3

Functional languages has its roots from lambda calculus, a formal system in mathematical logic developed in the 1930s to investigate computability, function application, and recursion. The use of functional languages is more accepted in academic institutions rather than in commercial development. Functional languages do provide a method to quickly prototype problems. LISP is the one of the original programming languages which is considered functional developed in 1950s. For many years, the functional language LISP was used in the study of Artificial Intelligence (AI). Functional programming has been the go-to for students in order to become a better programmer and to understand the concept of recursion. The main idea of recursion is to replace iteration in imperative programming which make coding easier and maintenance simpler to do. As original functional languages like LISP have evolved, some of the features similar to imperative programming have been integrated into the language making it more versatile.

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

Theoretical Questions

1. What are functions?

2. What are the two main types of functions?

3. Define NULL.

4. What is symbolic expression?

5. What is defun used for?

Practical Questions

1. Write a function that calculates sum of elements in array.

2. Write a function that reverses the array.

3. Write a function to check if the string is palindrome.


References

  1. https://en.wikipedia.org/wiki/Function_(mathematics)
  2. http://www.dbnet.ece.ntua.gr/~adamo/languages/books/p359-hudak.pdf
  3. https://en.wikipedia.org/wiki/Functional_programming
  4. https://en.wikipedia.org/wiki/Evaluation_strategy
  5. https://alvinalexander.com/scala/fp-book/benefits-of-functional-programming
  6. https://alvinalexander.com/scala/fp-book/disadvantages-of-functional-programming


Top of Page - Prev Chapter - Next Chapter