Основы функционального программирования

Предикаты и истинность в Лиспе


Хотя формальное правило записи программ вычислений в виде S-выражения предписывает, что константа Т — это (QUOTE T), было оговорено, что в системе всегда пишется Т. Кроме того, Nil оказался удобнее, чем атом F, встречавшийся в начальных предложениях по Лиспу аналог значения FALSE. Программист может либо принять это правило на веру, либо изучить следующие уточнения.

В Лисп есть два атомных символа, которые представляют истину и ложь, соответственно. Эти два атома — T и NIL. Данные символы — действительные значения всех предикатов в системе. Главная причина в удобстве кодирования. Во многих случаях достаточно отличать произвольное значение от пустого списка. Если атомы T и F имеют значение T и NIL, соответственно, то символы T и F в качестве константных предикатов могут работать, потому что:

(eval-a T '((Nil . Nil)(T . T) (F . NIL))) ; = T (eval-a NIL'((Nil . Nil)(T . T) (F . NIL))) ; = NIL (eval-a F '((Nil . Nil)(T . T) (F . NIL))) ; = NIL

Формы (QUOTE T) и (QUOTE NIL) будут также работать, потому что:

(eval (QUOTE T) ) ; = T (eval (QUOTE NIL) ) ; = NIL

Но

(eval (QUOTE F)NIL) ; = F

Это неправильно, отлично от NIL, и поэтому (QUOTE F) не будет работать как представление ложного значения в системе.

Заметим, что

(eval T ) ; = T (eval NIL ) ; = NIL

будет работать в силу причин, которые объясняются в лекции 6.

Формального различия между функцией и предикатом в Лиспе не существует. Предикат может быть определен как функция со значениями либо T либо NIL. Это верно для всех предикатов системы. Можно использовать форму, не являющуюся предикатом там, где требуется предикат: предикатная позиция условного выражения или аргумент логической операции. Семантически любое S-выражение, отличного от NIL, будет рассматриваться в таком случае как истинное. Первое следствие из этого — предикат Null и логическое отрицание Not идентичны. Второе — то, что (QUOTE T) или (QUOTE Х) практически эквивалентны Т как константные предикаты.

Предикат EQ ведет себя следующим образом:

  1. Если его аргументы различны, значением EQ является NIL.
  2. Если оба его аргументы являются одним и тем же атомом, то значение — Т.
  3. Если значения одинаковы, но не атомы, то его значение T или NIL в зависимости от того, идентично ли представление аргументов в памяти.

  4. Значение EQ всегда T или NIL. Оно никогда не бывает не определено, даже если аргументы неправильные.

Универсальная функция — это джин, выпущенный из бутылки, т.к. потенциал такой функции ограничен лишь способностями нашего воображения. Пока рассмотрены лишь простейшие, самые очевидные следствия из возможности явно применять и уточнять механизмы символьного представления и определения функций, такие как использование накапливающих параметров, связывание обозначений по схеме знак-смысл в ассоциативном списке как имен переменных со значениями, так и названий функций с определениями, а также применение вспомогательных функций для достижения прозрачности определений. Эти возможности имеют место в любом языке высокого уровня. Но попутно выполнено достаточно строгое построение совершенно формальной математической системы, называемой "Элементарный ЛИСП". Составляющие этой формальной системы следующие:

  1. Множество символов, называемых S-выражениями.
  2. Система функциональных обозначений для основных понятий, необходимых при программировании обработки S-выражений.
  3. Формальное представление функциональных обозначений в виде S-выражений.
  4. Универсальная функция (записанная в виде S-выражения), интерпретирующая обращение произвольной функции, записанной как S-выражение, к ее аргументам.
  5. Система базовых функций, обеспечивающих техническую поддержку обработки S-выражений, и специальных функций, обеспечивающих управление вычислениями.

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


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