Вычисление в Лиспе

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

1. Самоопределённые формы. Эти формы, подобно константам, являются объектами, представляющими лишь самих себя. Это такие формы, как числа и специальные константы true, false и nil, а также знаки и строки.
2. Символы, которые используются в качестве переменных.
3. Формы в виде списочной структуры, которыми являются:
   1. Вызовы функций и лямбда-вызовы.
   2. Специальные формы, в которые входят setq, ' и многие описанные в этой главе формы, предназначенные для управления вычислением и контекстом.
   3. Макровызовы (будут рассмотрены позже).

  В распространённых процедурных языках наряду с основными действиями есть специальные управляющие механизмы разветвления вычислений и организации циклов. В Паскале, например, используются структуры if then else, while do, case и другие.
  Управляющие структуры Лиспа (будем для них использовать термин предложение) выглядят внешне как вызовы функций. Предложения будут записываться в виде скобочных выражений, второй элемент которых действует как имя управляющей структуры, а остальные элементы - как "аргументы". Результатом вычисления, так же как у функции, является значение, т.е. управляющие структуры представляют собой формы. Однако предложения не являются вызовами функций, и разные предложения используют аргументы по-разному.
  Наиболее важные с точки зрения программирования синтаксические формы можно на основе их использования разделить на следующие группы:

Работа с контекстом:

- ' или блокировка вычисления;

- вызов функции и лямбда-вызов;

- предложение let.

Форма исполнения:

- пошаговая progn;

- параллельная parallel;

- независимая fork.

Разветвление вычислений:

- условные предложения cond, if.

Итерации:

- циклические предложения for, for*, while, do-while.

  Вычисление функции создаёт на время вычисления новые связи для формальных параметров функции. Новые связи внутри формы можно создать и с помощью предложения let. Эта структура выглядит так:

(nil let ((m₁ {value₁})|m₁ (m₂ {value₂})|m₂ …)
  form₁
  form₂ …)

  Предложение let вычисляется так, что сначала динамические переменные m₁, m₂, … из первого "аргумента" формы связываются (одновременно) с соответствующими значениями знач₁, знач₂, … Затем пошагово вычисляются значения форм форма₁, форма₂, … В качестве значения всей формы возвращается значение последней формы. Как и у функций, после окончания вычисления связи динамических переменных m₁, m₂, … ликвидируются и любые изменения их значений (setq) не будут видны извне. Например:

>(nil setq  a 2)
nil
>(nil let ((a 0))
  (nil  setq  a 1))
nil
>a
2

  Форма let является на самом деле синтаксическим видоизменением лямбда-вызова, в которой формальные и фактические параметры помещены совместно в начале формы:

(nil let ((m₁ {a₁}) (m₂ {a₂}) … (m_n {a_n}))
  form₁ form₂ …)
≡
(nil (lambda
  (m₁ m₂ … m_n)  ; формальный параметр
  form₁ form₂ …)  ; тело функции
  (nil progn {a₁}) (nil progn {a₂}) … (nil progn {a_n}))  ; фактический параметр

  Тело лямбда-выражения может состоять из нескольких форм, которые вычисляются пошагово, и значение последней формы возвращается в качестве значения лямбда-вызова.
  Значения переменным формы let присваиваются одновременно. Это означает, что значения всех переменных m_i вычисляются до того, как осуществляется связывание с формальными параметрами. Новые связи этих переменных ещё не действуют в момент вычисления начальных значений переменных, которые перечислены в форме позднее. Например:

>(nil let ((x 2)  (y  (3  * x)))
  (nil  list  x y)) ; при вычислении y у x нет связи
Error:eval: Symbol x have no value

  Предложения progn, parallel и fork позволяют работать с несколькими вычисляемыми формами:

(nil progn форма₁ форма₂ … форма_n)
(nil parallel форма₁ форма₂ … форма_n)
(nil fork форма₁ форма₂ … форма_n)

  У этих специальных форм переменное число аргументов. Предложение progn пошагово вычисляет эти аргументы и возвращает в качестве значения значение последнего аргумента. Предложение parallel параллельно вычисляет все эти аргументы и не возвращает ничего, то-есть nil. Предложение fork запускает на вычисление форму (nil progn форма₁ форма₂ … форма_n), не ожидает её результата и ничего не возвращает, то-есть nil. Эти формы не содержат механизм определения внутренних переменных:

>(nil progn (nil  setq  x 2)  (nil  setq  y (3  * x)))
nil
>x
2

   С помощью формы let нужно задавать область действия переменных. Данная форма позволяет использовать формы, вычисляемых пошагово, и в качестве результата возвращает значение последней формы. Это свойство называют неявным progn.

  Предложение cond является основным средством разветвления вычислений. Это синтаксическая форма, позволяющая управлять вычислениями на основе определяемых предикатами условий. Структура условного предложения такова:

(nil cond
  (p₁ a₁)
  (p₂ a₂)
  …
  (p_n a_n))

  Предикатами p_i и результирующими выражениями a_i могут быть произвольные формы. Значение предложения cond определяется следующим образом:

1. Выражения p_i, выполняющие роль предикатов, вычисляются пошагово слева направо (сверху вниз) до тех пор, пока не встретится выражение, значением которого не является ни nil ни false, т.е. логическим значением которого является истина.
2. Вычисляется выражение, соответствующее этому предикату, и полученное значение возвращается в качестве значения всего предложения cond.
3. Если истинного предиката нет, то значением cond будет nil.

>(nil defmethod тип  (l)
  (nil  cond
    ((nil = l)  'пусто)
    ((nil atom  l)  'атом)
    (true 'список)))
(lambda (l) (nil  cond  ((nil = l)  'пусто)  ((nil atom  l)  'атом)  (true 'список)))
>(nil тип  '(a b c))
список
>(nil тип  (nil  atom  '(а  т  о  м)))
атом

  В условном предложении может отсутствовать выражение a_i или на его месте часто может быть несколько форм:

(nil cond
  (p₁ a_1,1)
  …
  (p_i)  ; выражение отсутствует
  …
  (p_k a_k,1 a_k,2 … a_k,n)  ; несколько форм в качестве результата
  …)

  Если условию не ставится в соответствие выражение, то в качестве результата предложения cond при истинности предиката выдаётся само значение предиката. Если же условию соответствует несколько форм, то при его истинности формы вычисляются пошагово слева направо и результатом предложения cond будет значение последней формы (неявный progn).
  В качестве примера использования условного предложения определим логические действия логики высказываний and, or, not, => (импликация) и <=> (тождество):

>(('logic defclass) defvar  value)
logic
>('logic  defmethod set (x)
  ('valuef  set x))
(lambda (x) ('value set x))
>('logic  defmethod and (x)
  (nil  cond
    (value  x)
    (true false)))
(lambda (x) (nil  cond  (value  x)  (true false)))
>('x  set ('logic newobject))
logic(EnvironmentLayer((this .  .. logic(EnvironmentLayer((this .  ... ) (value . nil) ))) (value . nil) ))
>(x set true)
true
>(x and false)
false
>('logic  defmethod or  (x)
  (nil  cond
    (value  true)
    (true x)))
(lambda (x) (nil  cond  (value  true) (true x)))
>(x or  false)
true
>('logic  defmethod not ()
  (nil  not value))
(lambda nil (nil  not value))
>(x not)
false
>('logic  defmethod =>  (x)
  (nil  cond
    (value  x)
    (true true)))
(lambda (x) (nil  cond  (value  x)  (true true)))
>(x set false)
false
>(x =>  true)
true

  Импликацию можно определить и через другие операции:

('logic defmethod =>  (x)
  (this or  (x  not)))
('logic defmethod <=> (x)
  ((this  =>  x)  and (x  =>  this)))

  Предикаты and и or входят в состав встроенных функций Лиспа. Число их аргументов может быть произвольным.

>(nil and (nil  atom  nil)  (nil  = nil)  (nil  eq  nil nil))
true

  Предложения cond можно комбинировать таким же образом, как и вызовы функций. Например, предикат xor, который истинен при наличии единственного утвердительного аргумента, можно определить следующим образом:

>('logic  defmethod xor (x)
  (nil  cond
    (value
      (nil  cond
        (x  false)
        (true value)))
    (true x)))
(lambda (x) (nil  cond  (value  (nil  cond  (x  false)  (true value)))  (true x)))
>(x set true)
true
>(x xor false)
true
>(x set false)
false
>(x xor false)
false

  В этой функции на месте выражения первого условия вновь стоит предложение cond. На месте, определённом условию, также можно использовать ещё одно условное предложение, и в этом случае мы получим условное условие. Такие построения очень быстро приводят к трудным определениям.

  Предложение cond представляет собой наиболее общую условную структуру. Её критикуют за обилие скобок и за то, что структура этого предложения совершенно оторвана от естественного языка. Поэтому в Лисп-системах используются и другие, в различных отношениях более естественные, условные предложения. Но можно обойтись и с помощью лишь cond предложения.
  В простом случае можно воспользоваться вполне естественной и содержащей мало скобок формой if.

(nil if условие то-форма иначе-форма)
≡
(nil cond
  (условие то-форма)
  (true иначе-форма))

>(nil if  (nil  atom  true) 'атом 'список)
атом

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

(число for* переменная {участок для вычислений})

  Пошагово локальной переменной присваиваются числа от 0 до число-1. При каждом таком значении вычисляется тело цикла.
  Для примера с помощью предложения for* определим функцию, вычисляющую n-ую степень числа (n - целое, положительное):

>('number defmethod expt  (n)
  (nil  let ((результат  1))
    (n  for*  i
      (nil  setq  результат  (результат * this)))
    результат))
(lambda (n) (nil  let ((результат  1)) (n  for*  i (nil  setq  результат  (результат * this))) результат))
>(2 expt  3)
8

  Цикл for отличается от for* тем, что в нём всё тело вычисляется параллельно, и каждый процесс имеет свою собственную переменную. Применяется данный цикл при обслуживании элементов вектора (в случае, если вычисления независимы от их порядка). Данные циклы определены ещё для обслуживания элементов списка и строк.

  Следующий цикл while предназначен для пошагово выполняемых действий до получения удовлетворяющих результатов.

(nil while условие {участок для вычислений})

>(nil setq  x 10  s 0)
nil
>(nil while (x  > 0)
  (nil  setq  s (s  + x))
  (nil  setq  x (x  - 1)))
false
>s
55

  Цикл do-while отличается от while только порядком проверки и действий:

(nil do-while {участок для вычислений} условие)

  В "чистом" функциональном Лиспе нет ни циклических предложений (for, progn и другие), ни тем более операторов передачи управления. Для программирования повторяющихся вычислений в нём используются лишь условные предложения и определения рекурсивных, или вызывающих самих себя, функций.
  Например, рекурсивный вариант функции expt можно было бы определить так:

('number  defmethod expt  (n)
  (nil  if  (n  < 2)  this
    (this * (this expt  (n  - 1)))))

  Функция expt вызывает себя до тех пор, пока используемый как счётчик аргумент n не уменьшится до единицы, т.е. всего лишь n-1 раз. После этого в качестве результата вызова функции expt возвращается значение this. При каждой передаче значения на предыдущий уровень результат умножается на this. Так this окажется перемноженным на себя n раз.
  Рекурсивное определение функции expt короче, и лучше отражает суть функции, чем версии, основанные на for*.
  Рассмотрим ещё одну функцию, просто определяемую через рекурсию, - факториал (факториал - это произведение данного числа на все целые положительные числа, меньшие данного. Например, факториал от 5, обозначаемый как 5!, есть 1*2*3*4*5=120. Факториалом нуля считается 1):

>('number defmethod ! ()
  (nil  if  (this < 2)  1
    (this * ((this  - 1)  !))))
(lambda nil (nil  if  (this < 2)  1 (this * ((this  - 1)  !))))
>(5 !)
120

  Итеративные и рекурсивные программы теоретически одинаковы по своим вычислительным возможностям, иными словами, множества вычислимых с их помощью функций совпадают (так называемые частично рекурсивные функции). Так что любое вычисление в принципе, можно запрограммировать любым из этих способов. Однако свойства итеративных и рекурсивных вариантов программ могут существенно отличаться. В связи с этим часто приходится решать, какой из способов программирования больше подходит для данной задачи. От сделанного выбора зависит простота и естественность программирования, а также его эффективность с точки зрения времени исполнения и использования памяти.
  С помощью итеративного программирования, как правило, более длинного и трудного в осуществлении, результат может вычисляться значительно проще и быстрее. Это происходит по двум причинам, во-первых, потому, что вычислительные машины в общем ориентированы на пошаговые вычисления, и, во-вторых, потому, что трансляторы не всегда в состоянии преобразовать рекурсивное определение в итеративное и используют при вычислениях стек, несмотря на то что он не всегда нужен.
  Рекурсивное программирование в общем более короткое и содержательное. Особенно полезно использовать рекурсию в тех случаях, когда решаемая задача или обрабатываемые данные по сути своей рекурсивны. Например, математическое определение факториала рекурсивно и его реализация через рекурсивную функцию совершенно естественна:

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