Функциональное программирование

       

Функции. Базовые функции


ЛЕКЦИЯ 2.Функции. Базовые функции.

Содержание



Понятие функции.

В математике функция отображает одно множество в другое. Записывается: Y = F (x)

Для х из множества определения (Domain) ставится в соответствие Y из множества значений (range) функции F.

   

Можно записать:

  • У функции может быть любое количество аргументов,

    в том числе их может не быть совсем.

  • Функция без аргументов имеет постоянное значение.

  •      

    Примеры функций:

    abs( -3 ) --> 3 абсолютная величина.

    + ( 2 , 3 ) --> 5 сложение

    union ( ( a , b ), ( c , b ) ) --> ( a , b , c ) объединение множеств.

    количество_букв ( слово ) --> 5

    Типы аргументов и функций.

    Функция в общем случае задает отображение из нескольких множеств в множество значений.

         

    Можно записать :

    Это функция двух аргументов: первый х принадлежит А, второй у принадлежит В, значение z принадлежит С. В этом случае говорят, что аргументы и значение имеют разные типы.

    Пример:

    1.2 Префиксная нотация.

    В математике принята префиксная нотация, в которой имя функции стоит перед аргументами заключенными в скобках. В Лиспе для записи арифметических выражений и функций используется единая префиксная форма записи, в которой имя функции или действия стоит перед аргументами и записывается внутри скобок.

    f ( x )

    g ( x , y )

    h ( x , g ( y , z ) )

    ( f x )

    ( g x y )

    ( h x ( g y z ) )

    ( + x y )

    ( - x y )

    ( * x ( + x z ) )

    в арифметических выражениях используется инфиксная запись :

    x + y

    x - y

    x * ( x + z )

     

    Достоинства :

  • упрощается синтаксческий анализ выражений, так как по первому

    символу текущего выражения система уже знает, с какой структурой

    имеет дело.

  • появляется возможность записывать функции в виде списков, т.е. данные (списки) и программа (списки) представляются единым образом.
  • Диалог с интерпретатором ЛИСПА.

    Транслятор Лиспа работает как правило в режиме интерпретатора.


    Read-eval-print цикл

    loop { read evaluate print)



    В Лиспе сразу читается , затем вычисляется (evaluate) значение функции и выдается значение.



    Пример :







    * ( + 2 3 )

    5


     


     


     


    Иерархия вызовов.

    В вводимую функцию могут входить функциональные подвыражения :





    * (* ( + 1 2 ) ( + 3 4 ))

    21




     


     


    Блокировка QUOTE.

    В некоторых случаях не требуется вычисления значений выражений, а требуются само

    выражение. Если прямо ввести * ( + 2 3 ) , то 5 получится как значение. Но можно понимать ( + 2 3 ) не как функцию, а как список. S-выражения, которые не надо вычислять,

    помечают для интерпретатора апострофом " ' " (quote).







    QUOTE - специальная функция с одним аргументом, которая возвращает в качестве значения этот аргумент.


     


     


     




    * ' ( + 2 3 )

    ( + 2 3 )



    Или



    * ' y

    y


     


     


     




    * ( quote ( + 2 3 ) )

    ( + 2 3 )

    * ( quote y )

    y


    Вместо апострофа можно использовать функцию QUOTE.





    * ' ( a b ' ( c d ) )

    (a b ( quote c d ) )


    Апостроф автоматически преобразуется в QUOTE.



     


     




    * ( quote ' y )

    ( QUOTE Y )

    * '' y

    ( QUOTE Y )

    * ( QUOTE QUOTE )

    QUOTE


     


     


     
    Перед константами не надо ставить апостроф, так как число и его значение совпадают.





    * ' 3.17

    3.17

    * ( + ' 2 3 )

    5

    * t

    T

    * ' t

    T

    * ' nil

    NIL


     


     


     


    /FONT>.4 Функция EVAL.





  • Функция EVAL обеспечивает дополнительный вызов интерпретатора Лиспа.


  • При этом вызов может производится внутри вычисляемого S-выражения.


  • Функция EVAL позволяет снять блокировку QUOTE.





  •  


     




    * ( quote ( + 1 2 ) )

    ( + 1 2 )

    * ( eval ( quote ( + 1 2 ) ) )

    3


    quote и eval действуют во взаимно противоположенных

    направлениях и аннулируют эффект друг друга.

    Примеры:







    * ( setq x ' ( a b c ) )

    ( a b c )

    * ' x

    x


    * x

    ( a b c )

    * ( eval ' x )

    ( a b c )




    EVAL - это универсальная функция Лиспа, которая может вычислить любое правильно составленное s-выражение.


     


     


     
    <



    /p>



    Использование символов в качестве переменных.



    Изначально символы в Лиспе не имеют значения. Значения имеют только константы.

    * t

    T

    * 1.6

    1.6

    Если попытаться вычислить символ, то система выдает ошибку.



    Значения символов хранятся в ячейках, закрепленных за каждым символом. Если в эту ячейку положить значение, то символ будет связан (bind) сo значением. В процедурных языках говорят "будет присвоено значение".
         
    Для Лиспа есть отличие:

  • Не оговаривается, что может хранится в ячейке: целое, атом, список, массив и т.д. В ячейке может хранится что угодно.


  • С символом может быть связана не только ячейка со значением, а многие другие ячейки, число которых не ограничено.


  • Для связывания символов используется три функции:













    Функция SET.

    Функция SET cвязывает символ со значением, предварительно вычисляя значения аргументов.
       
    В качестве значения функция SET возвращает значение второго аргумента. Если перед первым аргументом нет апострофа,

    то значение будет присвоено значению этого аргумента.
    * ( set 'd ' ( x y z ) )

    ( x y z )
    * ( set a ' e )

    e
       
    * ( set ' a ' b )

    b
    * a

    b

    * b

    e


    На значение символа можно сослаться записав его без апострофа.





    Функция SETQ.



    Она аналогична
    , но не вычисляет значение первого аргумента. Буква q на блокировку.



    * ( setq m ' k )

    k
    * m

    k
       


    Обобщенная функция SETF.

    Действует аналогично , но может использоваться для присвоения символу не только значения.



    Базовые функции.

    В Лиспе для обработки списков, т.е. для разбора, анализа и построения списков

    существуют базовые функции. Они образуют систему аксиом языка, к которым

    сводятся символьные вычисления. В этом смысле их можно сравнить с основными арифметическими операциями. Простота базовых функций и их малое число -

    одно из достоинств Лиспа.

    Базовые функции:



    ATOM EQ



  • Функции CAR и CDR извлекают информацию из списка,

    или обеспечивают доступ к элементам списка.


  • CONS объединяет элементы в список.


  • ATOM и EQ проверяют аргументы.

  •    
    <



    /p>



    Функция CAR.

  • Первый элемент списка - голова.


  • Список без головы - хвост.

  •      
    Функция CAR возвращает в качестве значения первый элемент списка, т.е. голову.
         
    CAR < список >


    * ( car '(( head ) tail )) -> ( head )





    * ( car ( a b ))

    ошибка - имя несуществующей функции.
    car применяется только для списков, т.е. если есть голова списка.
     
    * ( car nil )

    nil

    * ( car ' nil )

    nil
    * ( car ' ( nil a ) )

    nil
       


    Функция CDR.



    * (cdr ' ( a ) )

    nil

    * ( cdr nil )

    nil
    Так как список из одного элемента ,его хвост - пустой список.
    Для

    атомов



    * ( cdr ' kat ) ошибка, т.к. не список.

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

    ( ( c d ) )



    Имена функций и возникли по историческим причинам. Автор Лиспа реализовывал свою первую систему на машине IBM 605. Для хранения адреса головы списка

    использовался регистр CAR (content of address registr) Для хранения адреса хвоста списка использовался регистр CDR (contеnt of decrement registr)



    В MCL можно наряду с CAR и CDR использовать имена FIRST REST.

    * ( FIRST ' ( a b c ) )

    a
         
    * ( FIRST ( REST ' ( 1 2 3 4 ) )

    2

    * ( FERST ' ( REST ' ( 1 2 3 4 ) ) )

    REST
         
    Рассмотрим ( сar ( cdr ' ( ( a b ) c d ) ) )



    Первым выполняется cdr ,а затем car,

    т.е. в Лиспе первым выполняются внутренние функции, а затем внешние.

    Исполнение идет "изнутри наружу".
         


    Функция CONS.

    Функция CONS строит новый список из своих аргументов.

    cons: s-выражение + список = список

       
    CONS < s-выражение > <список >




    Примеры:



    * ( cons ' a ' ( b c ) )

    ( a b c )
    * ( cons ' ( a b ) ' ( c d ) )

    ( ( a b) c d )
       
    Первый аргумент становится головой второго аргумента, который обязательно является списком.

    * ( cons ' ( a b ) ' ( ( a b ) ) )

    ( ( a b ) ( a b ) )

    * (cons ( + 1 2 ) ' ( + 3 4 ) )

    ( 3 + 3 4 )
    * (cons ' ( + 1 2 ) ( + 3 4 ) )

    error

    * ( cons ' ( + 1 2 ) ' ( + 3 4 ) )

    ( ( + 1 2 ) + 3 4 )
       
    <



    /p>

    Примеры манипуляции с пустым списком:



    * ( cons ' ( a b c ) nil )

    ( ( a b c ) )

    * ( cons nil ' ( a b c ) )

    ( nil a b c )


    * ( cons nil nil )

    ( nil )




    * ( cons ' a nil )

    ( a )


    Очень полезно, т.к. позволяет превращать элемент в список.



     


     


    Связь между CAR, CDR и CONS.

    Таким образом функции по принципу их использования делятся на группы:

  • Назначение


  • запись


  • результат












  • * ( cons ( car '( голова хвост ))

    ( сdr '( голова хвост )))

    ( голова хвост)



    Селекторы и являются

    обратными для конструктора .

    Список, разбитый с помощью функции

    CAR и CDR

    на голову и хвост,

    можно восстановить функцией CONS.




    Комбинации функций CAR и CDR.

    Комбинируя функции и можно выделить произвольный элемент списка :





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

    ( a b c )

    ( b c )

    ( c )



    Можно записать проще :

    ( CDDAR ' ( ( a b c ) d ) )



    Т.е. записывается (C...R список)

    А - CAR D - CDR




     
    В MCL можно использовать только три буквы, в других реализациях больше.







    N - элемент.





    Функция NTH извлекает n-й элемент из списка.


     


     


     
    Форма записи:





    NTH < n > <список >




    Пример :



    Извлекаем седьмой элемент :



    *( NTH 7 '( 1 2 3 4 5 6 7 8 9 10 ) )

    7







    6.7 Функция LIST.





    Функция LIST создает список из s- выражений (списков или атомов).




     


     


    Форма записи:



    Число аргументов может быть любое.



    Примеры:







    * ( list 1 2 )

    ( 1 2 )

    * ( list ' a ' b ( + 1 2 ) )

    ( a b 3 )

    * ( list ' a ' ( b c ) ' d )

    ( a ( b c ) d )


    * ( list nil )

    ( nil )

    * ( list ' a )

    ( a )

    * ( list ' a nil )

    ( a nil )


     


     


    Функция LENGTH.





    Функция LENGTH возвращает в качестве значения длину списка. т.е. число элементов на верхнем уровне


     


     


     




    Примеры:





    2.7 Арифметические функции.

  • Арифметические функции могут быть использованы с целыми или действительными аргументами.


  • Число аргументов для большинства арифметических функций может быть разным.


  • (+ x1 x2 ... xn) возвращает x1 + x2 + x3 + ... + xn.


  • (- x1 x2 ... xn) возвращает x1 - x2 - x3 - ... - xn.


  • (* y1 y2 ... yn) возвращает y1 x y2 * y3 * ... * yn.


  • (/ x1 x2 ... xn) возвращает x1/x2/... /xn.


  • Специальные функции для прибавления и вычитания единицы: (1+ x) и (1- x).







  • Содержание раздела