74202

Functional programming languages and tools

Лекция

Информатика, кибернетика и программирование

Functional programming languages (FPL) were originally developed specifically to handle symbolic computation and list-processing applications. In FPLs the programmer is concerned only with functionality, not with memory-related variable storage and assignment sequences.

Английский

2014-12-29

55 KB

0 чел.

Lecture 6. Functional programming languages and tools

Functional programming languages (FPL) were originally developed specifically to handle symbolic computation and list-processing applications. In FPLs the programmer is concerned only with functionality, not with memory-related variable storage and assignment sequences.

FPL can be categorized into two types:

  •  pure functional languages, which support only the functional paradigm (Haskell), and
  •  impure functional languages that can also be used for writing imperative-style programs (LISP).

Applications.

Artificial intelligence is the main application domain for functional programming, covering topics such as:

  •  expert systems
  •  knowledge representation
  •  machine learning
  •  natural language processing
  •  modelling speech and vision

In terms of symbolic computation, functional programming languages have also proven useful in some editing environments (EMACS) and some mathematical software (particularly calculus).

Lisp and its derivatives are still the dominant functional languages. Other functional languages Scheme, Miranda, Sisal, Haskell, APL, ML.

Characteristics of functional programming languages are:

  •  Functional programming languages are modeled on the concept of mathematical functions, and use only conditional expressions and recursion to effect computation.
  •  In the purest form they use neither variables nor assignment statements, although this is relaxed somewhat in most applied functional languages.
  •  The concept of side effects is also alien to purely functional programming: a function is given values and returns a value, there are no variables to manipulate and hence no possibility for side effects.
  •  Programs are constructed by composing function applications - the values produced by one or more functions become the parameters to another.
  •  For reasons of efficiency (because the underlying machine is, in fact, imperative) most functional languages provide some imperative-style capabilities, including variables with assignment, sequences of statements, and imperative style loop structures.
  •  Note that the functional paradigm can also be used with some imperative languages - e.g. C has both a conditional expression and support for recursion - so the factorial function code be coded in functional style in C (or C++ or Java) as follows: int fact(int x){ return (x == 0) ? 1 : x * fact(x - 1); }
  •  Three primary components:

ƒA set of data object: A single, high-level data structure like a list

ƒA set of built-in functions for object manipulation: Building, deconstructing, and accessing lists

ƒA set of functional forms for building new functions: Composition, reduction, etc.

Lambda calculus (LC). Lambda calculus is a method of modeling the computational aspects of functions. It helps us understand the elements and semantics of functional programming languages independent of syntax.

LC expressions are of three forms:

  •  e1: A single identifier (such as x, or 3)
  •  e2: A function definition of the form (λx.e):The expression e, with x being a bound variable

 e is the body of the function, x is a parameter

 e may be any of the three types of expressions

 square(x) would be written as (λx.x*x)

  •  e3: A function application of the form e1 e2, meaning e1 applied e2; square applied to 2 would be ((λx.x*x) 2)

Free and Bound Variables. A variable appearing in a function F is said to be free if it is not bound in F. Bound variables are like formal parameters, and act like local variables. Free variables are like non-local variables that will be bound at an outer level. In the function λx.xk, x is bound and k is free.

Substitution: Applying a function. To apply a function, we rewrite the function, substituting all occurrences of the bound variable by the argument. We use substitution to replace all occurrences of an identifier with an expression: [e/x]y means “substitute e for all occurrences of x in expression y”.

Semantic of Functional Computations. We define the result of a function application in terms of the following:

ƒRewriting the definition

ƒReplacing bound variables with the corresponding arguments

Rewrite rules:

1) r1: Renaming

λxi.e λxj.[xj/xi]e, where xj is not free in e

We can replace all occurrences of the name of a bound variable with another name without changing the meaning.

2) r2: Application

(λx.e1)e2 [e2/x]e1

Replace the bound variable with the argument to the application.

3) r3: Redundant function elimination

λx.(e x) e, if x is not free in e

An expression that can no longer be reduced is said to be in normal form:

(λx.( λy.x + y) 5)(( λy.y * y) 6) =

(λx.x + 5)(( λy.y * y) 6) =

(λx.x + 5)(6 * 6) =

((6 * 6) + 5)

Functions in FPLs.

In a functional language, the basic unit of computation is the FUNCTION. The function definitions typically include a name for the function, its associated parameter list, and the expressions used to carry out the computation. A function computes a single value based on 0 or more parameters. Though the parameters of a function look like variables in an imperative language, they are different in that they are not subject to having their value changed by assignment - i.e. they retain their initial value throughout the computation of the function. Pure functional languages don’t need an assignment statement.

Function construction: given one or more functions as parameters, as well as a list of other parameters, construction essentially calls each function and passes it the list of "other" parameters.

Function composition: applying one function to the result of another. E.g. square_root(absolute_value(-3)).

Apply-to-all functions: takes a single function as a parameter along with list of operand values. It then applies the function to each parameter, and returns a list containing the results of each call.

Example 1. Suppose applyall carried this out with the function square and the data list (1 2 3). The result would be a list with the values from square(1), square(2), and square(3), i.e. (1 4 9).

Example 2. A LISP factorial function, illustrating use of conditional expressions and recursion for iteration

(DEFUN FACT (X)

(IF (= X 0)

1

( * X (FACT (- 1 X)) )

)

)

Imperative programming languages vs. functional programming languages.

Note that in imperative programming we concern ourselves with both the computation sequence and maintaining the program state (i.e. the collection of current data values). Unlike IPLs, purely functional languages (no variables and hence no assignments) have no equivalent concept of state: the programmer focuses strictly on defining the desired functionality. Iteration is not accomplished by loop statements, but rather by conditional recursion. Functional programmers are concerned only with functionality. This comes at a direct cost in terms of efficiency, since the code is still translated into something running on Von Neuman architecture.

LISP. In 1958, John McCarthy of MIT created the LISt Processing (or LISP) language. It was designed for Artificial Intelligence (AI) research. Because it was designed for such a highly specialized field, its syntax has rarely been seen before or since. The most obvious difference between this language and other languages is that the basic and only type of data is the list, denoted by a sequence of items enclosed by parentheses. LISP programs themselves are written as a set of lists, so that LISP has the unique ability to modify itself, and hence grow on its own. LISP remains in use today because it’s highly specialized and abstract nature.

6.1 LISP major dialects

The two major dialects of Lisp used for general-purpose programming today are Common Lisp and Scheme. These languages represent significantly different design choices.

Common Lisp is a successor to MacLisp. The primary influences were Lisp Machine Lisp, MacLisp, NIL, S-1 Lisp, Spice Lisp, and Scheme. It has many of the features of Lisp Machine Lisp (a large Lisp dialect used to program Lisp Machines), but was designed to be efficiently implementable on any personal computer or workstation. Common Lisp has a large language standard including many built-in data types, functions, macros and other language elements, as well as an object system (Common Lisp Object System or shorter CLOS). Common Lisp also borrowed certain features from Scheme such as lexical scoping and lexical closures.

Scheme (designed earlier) is a more minimalist design, with a much smaller set of standard features but with certain implementation features (such as tail-call optimization and full continuations) not necessarily found in Common Lisp. Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have exceptionally clear and simple semantics and few different ways to form expressions. A wide variety of programming paradigms, including imperative, functional, and message passing styles, find convenient expression in Scheme. Scheme continues to evolve with a series of standards (Revisedn Report on the Algorithmic Language Scheme) and a series of Scheme Requests for Implementation.

Clojure is a recent dialect of Lisp that principally targets the Java Virtual Machine, as well as the CLR, the Python VM, the Ruby VM YARV, and compiling to JavaScript. It is designed to be a pragmatic general-purpose language. Clojure draws considerable influences from Haskell and places a very strong emphasis on immutability. Clojure is a compiled language, as it compiles directly to JVM bytecode, yet remains completely dynamic. Every feature supported by Clojure is supported at runtime. Clojure provides access to Java frameworks and libraries, with optional type hints and type inference, so that calls to Java can avoid reflection and enable fast primitive operations.

In addition, Lisp dialects are used as scripting languages in a number of applications, with the most well-known being Emacs Lisp in the Emacs editor, AutoLisp and later Visual Lisp in AutoCAD, Nyquist in Audacity, Scheme in LilyPond. The potential small size of a useful Scheme interpreter makes it particularly popular for embedded scripting. Examples include SIOD and TinyScheme, both of which have been successfully embedded in the GIMP image processor under the generic name “Script-fu”. LIBREP, a Lisp interpreter by John Harper originally based on the Emacs Lisp language, has been embedded in the Sawfish window manager.

6.2 What made Lisp different1

Lisp was the first language where the structure of program code is represented faithfully and directly in a standard data structure. As a result, Lisp functions can be manipulated, altered or even created within a Lisp program without low-level manipulations. This is generally considered one of the primary advantages of the language with regard to its expressive power, and makes the language suitable for syntactic macros and metacircular evaluation.

Lisp deeply influenced Alan Kay, the leader of the research on Smalltalk, and then in turn Lisp was influenced by Smalltalk, by adopting object-oriented programming features (classes, instances, etc.) in the late 1970s. The Flavours object system (later CLOS) introduced multiple inheritance.

Largely because of its resource requirements with respect to early computing hardware (including early microprocessors), Lisp did not become as popular outside of the AI community as Fortran and the ALGOL-descended C language. Because of its suitability to complex and dynamic applications, Lisp is currently enjoying some resurgence of popular interest.

Lisp embodied nine new ideas:

1) Conditionals. A conditional is an if-then-else construct. We take these for granted now. They were invented by McCarthy in the course of developing Lisp. (Fortran at that time only had a conditional goto, closely based on the branch instruction in the underlying hardware.) McCarthy proposed conditional inclusion in ALGOL, but it was not made part of the Algol 58 specification. Algol 60 took up if-then-else and popularized it. For Lisp, McCarthy used the more general cond-structure.

2) A function type. In Lisp, functions are first class objects – they are a data type just like integers, strings, etc, and have a literal representation, can be stored in variables, can be passed as arguments, and so on.

3) Recursion. Recursion existed as a mathematical concept before Lisp of course, but Lisp was the first programming language to support it.

4) A new concept of variables. In Lisp, all variables are effectively pointers. Values are what have types, not variables, and assigning or binding variables means copying pointers, not what they point to.

5) Garbage-collection. Lisp introduced the concept of automatic garbage collection, in which the system walks the heap looking for unused memory. Progress in modern sophisticated garbage collection algorithms such as generational garbage collection was stimulated by its use in Lisp.

6) Programs composed of expressions. Lisp programs are trees of expressions, each of which returns a value. (In some Lisps expressions can return multiple values.) This is in contrast to Fortran and most succeeding languages, which distinguish between expressions and statements.

It was natural to have this distinction in Fortran because (not surprisingly in a language where the input format was punched cards) the language was line-oriented. You could not nest statements. And so while you needed expressions for math to work, there was no point in making anything else return a value, because there could not be anything waiting for it.

This limitation went away with the arrival of block-structured languages, but by then it was too late. The distinction between expressions and statements was entrenched. It spread from Fortran into Algol and thence to both their descendants.

When a language is made entirely of expressions, you can compose expressions however you want. You can say either (using Arc syntax)

(if foo (= x 1) (= x 2))

or

(= x (if foo 1 2))

7) A symbol type. Symbols differ from strings in that you can test equality by comparing a pointer.

8) A notation for code using trees of symbols.

9) The whole language always available. There is no real distinction between read-time, compile-time, and runtime. You can compile or run code while reading, read or run code while compiling, and read or compile code at runtime.

Running code at real-time lets users reprogram Lisp’s syntax; running code at compile-time is the basis of macros; compiling at runtime is the basis of Lisp's use as an extension language in programs like Emacs; and reading at runtime enables programs to communicate using s-expressions, an idea recently reinvented as XML.

6.3 Basic LISP Programming2

LISP Expressions.

When you start up the Common LISP environment, you should see a prompt, which means that LISP is waiting for you to enter a LISP expression. In the environment it looks like the following:

USER(1):

The Common LISP environment follows the algorithm below when interacting with users:

loop

   read in an expression from the console;

   evaluate the expression;

   print the result of evaluation to the console;

end loop.

Common LISP reads in an expression, evaluates it, and then prints out the result. For example, if you want to compute the value of (2 * cos(0) * (4 + 6)), you type in:

USER(1): (* 2 (cos 0) (+ 4 6))

Common LISP replies:

20.0

before prompting you to enter the next expression. Several things are worth noting:

LISP expressions are composed of forms. The most common LISP form is function application. LISP represents a function call f(x) as (f x). For example, cos(0) is written as (cos 0). LISP expressions are case-insensitive. It makes no difference whether we type (cos 0) or (COS 0).

Similarly, “+” is the name of the addition function that returns the sum of its arguments. Some functions, like “+” and “*”, could take an arbitrary number of arguments. In our example, “*” took three arguments. It could as well take 2 arguments, as in “(* 2 3)”, or 4 arguments, as in “(* 2 3 4 5)”.

In general, a function application form looks like

(function argument1 argument2 ... argumentn).

As in many programming languages (e.g. C/C++), LISP evaluates function calls in applicative order, which means that all the argument forms are evaluated before the function is invoked. That is to say, the argument forms (cos 0) and (+ 4 6) are respectively evaluated to the values 1 and 10 before they are passed as arguments to the * function. Some other forms, like the conditionals we will see later, are not evaluated in applicative order.

Numeric values like 4 and 6 are called self-evaluating forms: they evaluate to themselves. To evaluate (+ 4 6) in applicative order, the forms 4 and 6 are respectively evaluated to the values 4 and 6 before they are passed as arguments to the + function.

Complex arithmetic expressions can be constructed from built-in functions like the following:

Numeric Functions Meaning

(+ x1 x2 ... xn)  The sum of x1, x2, ..., xn

(* x1 x2 ... xn)  The product of x1, x2, ..., xn

(- x y)    Subtract y from x

(/ x y)    Divide x by y

(rem x y)   The remainder of dividing x by y

(abs x)   The absolute value of x

(max x1 x2 ... xn)  The maximum of x1, x2, ..., xn

(min x1 x2 ... xn)  The minimum of x1, x2, ..., xn

Defining Functions.

Evaluating expressions is not very interesting. We would like to build expression abstractions that could be reused in the future. For example, we could type in the following:

USER(2): (defun double (x) (* x 2))

DOUBLE

In the above, we define a function named double, which returns two times the value of its input argument x. We can then test-drive the function as below:

USER(3): (double 3)

6

USER(4): (double 7)

14

Lists.

Numeric values are not the only type of data LISP supports. LISP is designed for symbolic computing. The fundamental LISP data structure for supporting symbolic manipulation are lists.

Lists are containers that supports sequential traversal. List is also a recursive data structure: its definition is recursive. As such, most of its traversal algorithms are recursive functions. In order to better understand a recursive abstract data type and prepare oneself to develop recursive operations on the data type, one should present the data type in terms of its constructors, se lecturers and recognizers.

Constructors are forms that create new instances of a data type (possibly out of some simpler components). A list is obtained by evaluating one of the following constructors:

 nil: Evaluating nil creates an empty list;

 (cons x L): Given a LISP object x and a list L, evaluating (cons x L) creates a list containing x followed by the elements in L.

Notice that the above definition is inherently recursive. For example, to construct a list containing 1 followed by 2, we could type in the expression:

USER(21): (cons 1 (cons 2 nil))

(1 2)

LISP replies by printing (1 2), which is a more readable representation of a list containing 1 followed by 2. To understand why the above works, notice that nil is a list (an empty one), and thus (cons 2 nil) is also a list (a list containing 1 followed by nothing). Applying the second constructor again, we see that (cons 1 (cons 2 nil)) is also a list (a list containing 1 followed by 2 followed by nothing).

Typing cons expressions could be tedious. If we already know all the elements in a list, we could enter our list as list literals. For example, to enter a list containing all prime numbers less than 20, we could type in the following expression:

USER(22): (quote (2 3 5 7 11 13 17 19))

(2 3 5 7 11 13 17 19)

Notice that we have quoted the list using the quote special form. This is necessary because, without the quote, LISP would interpret the expression (2 3 5 7 11 13 17 19) as a function call to a function with name “2” and arguments 3, 5, ..., 19 The quote is just a syntactic device that instructs LISP not to evaluate the a form in applicative order, but rather treat it as a literal. Since quoting is used frequently in LISP programs, there is a shorthand for quote:

USER(23): '(2 3 5 7 11 13 17 19)

(2 3 5 7 11 13 17 19)

The quote symbol ‘ is nothing but a syntactic shorthand for (quote ...).

The second ingredient of an abstract data type are its se lecturers. Given a composite object constructed out of several components, a se lecturer form returns one of its components. Specifically, suppose a list L1 is constructed by evaluating (cons x L2), where x is a LISP object and L2 is a list. Then, the se lecturer forms (first L1) and (rest L1) evaluate to x and L2 respectively, as the following examples illustrate:

USER(24): (first '(2 4 8))

2

USER(25): (rest '(2 4 8))

(4 8)

USER(26): (first (rest '(2 4 8)))

4

USER(27): (rest (rest '(2 4 8)))

(8)

USER(28): (rest (rest (rest '(8))))

NIL

Finally, we look at recognizers, expressions that test how an object is constructed. Corresponding to each constructor of a data type is a recognizer. In the case of list, they are null for nil and consp for cons. Given a list L, (null L) returns t iff L is nil, and (consp L) returns t iff L is constructed from cons.

USER(29): (null nil)

T

USER(30): (null '(1 2 3))

NIL

USER(31): (consp nil)

NIL

USER(32): (consp '(1 2 3))

T

Notice that, since lists have only two constructors, the recognizers are complementary. Therefore, we usually need only one of them. In our following discussion, we use only null.

Structural Recursion with Lists.

Understanding how the constructors, se lecturers and recognizers of lists work helps us to develop recursive functions that traverse a list. Let’s begin with an example. The LISP built-in function list-length counts the number of elements in a list. For example,

USER(33): (list-length '(2 3 5 7 11 13 17 19))

8

Let’s try to see how such a function can be implemented recursively. A given list L is created by either one of the two constructors, namely nil or a cons:

Case 1: L is nil. The length of an empty list is zero.

Case 2: L is constructed by cons. Then L is composed of two parts, namely, (first L) and (rest L). In such case, the length of L can be obtained inductively by adding 1 to the length of (rest L).

Formally, we could implement our own version of list-length as follows:

(defun recursive-list-length (L)

 "A recursive implementation of list-length."

 (if (null L)

     0

   (1+ (recursive-list-length (rest L)))))

Here, we use the recognizer null to differentiate how L is constructed. In case L is nil, we return 0 as its length. Otherwise, L is a cons, and we return 1 plus the length of (rest L). Recall that (1+ n) is simply a shorthand for (+ n 1).

Symbols.

The lists we have seen so far are lists of numbers. Another data type of LISP is symbols. A symbol is simply a sequence of characters:

USER(45): 'a           ; LISP is case-insensitive.

A

USER(46): 'A           ; 'a and 'A evaluate to the same symbol.

A

USER(47): 'apple2      ; Both alphanumeric characters ...

APPLE2

USER(48): 'an-apple    ; ... and symbolic characters are allowed.

AN-APPLE

USER(49): t            ; Our familiar t is also a symbol.

T

USER(50): 't           ; In addition, quoting is redundant for t.

T

USER(51): nil          ; Our familiar nil is also a symbol.

NIL

USER(52): 'nil         ; Again, it is self-evaluating.

NIL

Using Lists as Sets

Formally, lists are ordered sequences. They differ with sets in two ways: (1) sets are unordered, but lists are. (a b c) and (2) (c b a) are two different lists.

An element either belong to a set or it does not. There is no notion of multiple occurrences. Yet, a list may contain multiple occurrences of the same element. (a b b c) and (a b c) are two different lists.

1 http://www.paulgraham.com/diff.html

2 http://www.cs.sfu.ca/CourseCentral/310/pwfong/Lisp/1/tutorial1.html


 

А также другие работы, которые могут Вас заинтересовать

1255. Проектирование двухэтажного жилого здания 164 KB
  Объемные строительные системы, имеющие надземную и (или) подземную части, включающие в себя помещения, сети инженерно-технического обеспечения и системы инженерно-технического обеспечения. Здание в плане имеет неправильную форму . Здание двухэтажное с высотой этажа3,3м. Размеры здания в осях 14,3х13,5м. Отметка подошвы фундамента -1,85 м. Грунтовые воды отсутствуют.
1256. Создание предприятия ИП Британ 73.5 KB
  Наименование предприятия, его специализация форма собственности и адрес. Схема действующего гаражно-технологического процесса, его описание. Описание методов организации технологических процессов ТО и ремонта ПС. Ведомость оборудования и оснастки на предприятии по форме.
1257. Соціально-психологічне дослідження ревнощів чоловiкiв 115.5 KB
  Науково-теоретичні підходи до розуміння та дослідження почуття ревнощів чоловіків. Літературно-філософські підході до розуміння природи ревнощів. Методика емпірико-практичного дослідження почуття ревнощів у чоловіків. Емпірико-практичне дослідження особливостей почуття ревнощів у чоловіків. Експериментальне дослідження співвідношення ревнощів з іншими почуттями та емоціями.
1258. Технология изготовления детали подъемника (вала редуктора) 91.5 KB
  Тихоходный вал редуктора, массой 11 кг., является телом вращения. Вал считается жёстким, поскольку отношение длины к максимальному диаметру меньше 15. Выбор заготовки и метод её изготовления. Определение групп допусков на исходные размеры заготовки.
1259. Разработка технических требований к сборочной единице 349.5 KB
  Техническое описание сборочной единицы. Выбор степени точности зубчатой передачи и класса точности подшипников. Выбор посадок шлицевых соединений и резьбовых соединений. Выбор исполнительных размеров калибров и их расчет. Выбор параметров точности зубчатого колеса.
1260. Анализ рынка. Абсолютная доля рынка по сегментам 375 KB
  Абсолютная доля рынка по сегментам. Уровень овладения рынком или горизонтальное проникновение. Уровень приверженности марке. Модель формирования позиции отдельного потребителя по отношению к продукту. Средняя важность атрибута.
1261. Економічне обґрунтування діяльності підприємства 497 KB
  Дані методичні вказівки покликані допомогти студентам напряму Архітектура, Реставрація творів мистецтва і Дизайн (рівень бакалавра) в написанні, а головне у виконанні тих певних обчислень, які необхідні для визначення вартості підприємницького проекту та обґрунтуванні виробничої програми.
1262. Всесторонняя характеристика рынка ценных бумаг РФ 460.5 KB
  Понятие рынка ценных бумаг, его место в системе рынков. Функции РЦБ и особенности ценообразования на рынке ценных бумаг. Участники и виды профессиональной деятельности на рынке ЦБ. Особенности первичного и вторичного рынка ценных бумаг. Проблемы регулирования Российского рынка ценных бумаг в России.
1263. Учет основных средств Ейского филиала ФГУП Росморпорт 398.5 KB
  Теоретические аспекты бухгалтерского учета основных средств. Оценка и переоценка основных средств. нализ основных финансовых показателей деятельности ФГУП Росморпорт. Документарное оформление и аналитический учет основных средств. Порядок проведения и учет результатов инвентаризации основных средств.