PART2 (Печатные лекции), страница 2

В качестве второго аргумента этой функции должно быть задано имя переменной, в качестве первого – произвольная форма. Функция вычисляет эту форму и строит новый список, первый элемент которого – вычисленное значение, а хвост – список, являющийся значением переменной v. Результирующий список присваивается в качестве нового значения переменной v (он также является значением самой функции push).

(return e)

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

(go e)

Это функция перехода по метке. В качестве аргумента функции go должен быть задан идентификатор – одна из меток ближайшей объемлющей блочной функции. Функция go полностью завершает вычисление той формы этой блочной функции, в которую она входит (на любом уровне), и осуществляет переход для вычисления формы, следующей за этой меткой.

Язык программирования Плэнер

В языке Плэнер программа и обрабатываемые ею данные записываются в виде выражений, к которым относятся: атомы (идентификаторы и числа), обращения к переменным, состоящие из префикса и имени переменной (например, .X) и списки, т.е. последовательности выражений заключенные в круглые, квадратные или угловые скобки (например, [elem 1 (a b c)]).

Некоторые выражения можно вычислять, получая в результате значения (ими являются выражения); такие выражения называются формами. К ним относятся: атомы (значение атома - сам атом), обращения к переменным с префиксом "." (значением является текущее значение переменной), списки в круглых скобках (значением является список из значений элементов исходного списка) и обращения к функциям, имеющие вид [f a₁ a₂ … a_n], где f - имя функции, а a_i - ее аргументы.

Программа на Плэнере представляет собой последовательность форм, ее выполнение заключается в вычислении этих форм.

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

Определение новых функций

Для определения новой функции следует обратиться к встроенной функции define:

[define f dexp]

Вычисление функции define в качестве побочного эффекта приводит к появлению в программе новой функции с именем f и т.н. определяющим выражением dexp, которое должно иметь вид

(lambda (v₁ v₂ … v_n) e) (n≥0)

где v_i - формальные параметры новой функции, а e - форма, зависящая от v_i.

При последующем обращении к этой новой функции

[f a₁ a₂ … a_n]

сначала вычисляются аргументы (фактические параметры) a_i, затем вводятся локальные переменные v_i, которым присваиваются значения соответствующих аргументов a_i, и далее вычисляется форма e при этих значениях переменных v_i, после чего эти переменные уничтожаются. Значение данной формы становится значением функции f при аргументах a_i.

Операции над списками

[elem n e]

Значением аргумента n должно быть ненулевое целое число (обозначим его N), а значением второго аргумента - список (L) с любыми скобками. Значением функции является N-й от начала элемент списка L, если N>0, или |N|-й от конца элемент этого списка, если N<0. В случае, когда в качестве n явно указано число, имя функции в обращении можно опустить; например, [1 .X] - это сокращение от [elem 1 .X], т.е. выделяется первый от начала элемент списка, являющего значением переменной X.

Если требуется вычислить список в круглых скобках

(e₁ e₂ … e_n) (n≥0)

т.е. если он рассматривается как форма, то все его элементы должны быть формами. Значением такого списка является список (с круглыми скобками) из значений его элементов. Например, если переменная X имеет значение (a b), то значением списка (.X c [-1 .X]) является список ((a b) c b).

В таких списках можно использовать т.н. сегментные формы, к которым относятся сегментные обращения к переменным (с префиксом "!.", например: !.X) и сегментные обращения к функциям (в угловых скобках, например: <elem 5 .X>). Сегментная форма вычисляется как обычная (простая) форма, но затем у ее значения, если это список, отбрасываются внешние скобки, и полученная таким образом последовательность элементов поставляется вместо сегментной формы. Например, если переменная X имеет значение (a (b c)), тогда:

значение (5 .X ()) равно (5 (a (b c)) ())

значение (5 !.X ()) равно (5 a (b c) ())

значение (!.X !.X) равно (a (b c) a (b c))

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

[+ n₁ n₂ … n_k] (k≥2)

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

[- n₁ n₂]

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

[max n₁ n₂ … n_k] (k≥2)

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

[min n₁ n₂ … n_k] (k≥2)

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

Предикаты

Предикатом называется форма, значение которой рассматривается как логическое значение «истина» или «ложь». При этом в Плэнере «ложью» считается пустой список (), а «истиной» – любое другое выражение (чаще всего в роли «истины» выступает атом T).

[num e]

Эта функция-предикат проверяет, является ли числом значение ее аргумента. Если да, то значение функции равно T («истина»), иначе – () («ложь»).

[empty e]

Функция проверяет, является ли значение ее аргумента пустым списком (с любыми скобками). Если да, то значение функции равно T, иначе – ().

[eq e₁ e₂]

Функция сравнивает значения своих аргументов. Если они равны, то значение функции равно T, иначе – ().

[neq e₁ e₂]

Аналог, но значения аргументов сравниваются на «не равно».

[gt n₁ n₂]

Значениями аргументов должны быть числа. Если первое из них больше второго, то значение функции равно T, иначе – ().

[ge n₁ n₂]

Аналог, но числа сравниваются на «больше или равно».

[lt n₁ n₂]

Аналог, но числа сравниваются на «меньше».

[hasval v]

Значением аргумента должно быть имя переменной, существующей в данный момент. Функция проверяет, имеет ли сейчас эта переменная какое-либо значение или нет. Если имеет, то функция возвращает результат T, а иначе - результат ().

Логические функции

Так называются функции, реализующие логические операции.

[not e]

Это «отрицание»: если значение аргумента равно () («ложь»), то функция выдает результат T («истина»), а при любом другом значении аргумента выдает результат ().

[and e₁ e₂ … e_k] (k≥2)

Это «конъюнкция». Функция по очереди вычисляет свои аргументы. Если значение очередного из них равно () («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением (), а иначе переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу.

[or e₁ e₂ … e_k] (k≥1)

Это «дизъюнкция». Функция по очереди вычисляет свои аргументы. Если значение очередного из них не равно () («ложь»), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением этого аргумента, в противном случае она переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу.

[cond (p₁ e_1,1 e_1,2 … e_1,k1) … (p_n e_n,1 e_n,2 … e_n,kn)] (n≥1, k_i≥1)

Это «условное выражение». Функция последовательно вычисляет первые элементы своих аргументов – предикаты p_i. Если все они имеют значение () («ложь»), тогда функция заканчивает свою работу с этим же значением. Но если нашелся предикат p_i, значение которого отлично от (), т.е. имеет значение «истина», тогда функция уже не будет рассматривать остальные предикаты, а последовательно вычислит формы e_i,j из этого i-го аргумента и со значением последнего из них закончит свою работу. Замечание: значения предыдущих форм из этого аргумента нигде не запоминаются, поэтому в качестве этих форм имеет смысл использовать только такие, которые имеют побочный эффект, например, меняют значения переменных.

Блочная и связанные с ней функции

[prog (v₁ v₂ … v_n) e₁ e₂ … e_k] (n≥0, k≥1)

Эту функцию называют «блочной», поскольку ее вычисление напоминает выполнение блоков в других языках программирования. Вычисление функции начинается с того, что вводятся локальные переменные, перечисленные в ее первом аргументе, и им присваиваются начальные значения: v_i – это либо идентификатор (имя) и тогда вводится локальная переменная с этим именем и без начального значения, либо пара (id val) и тогда вводится локальная переменная с именем id и начальным значением val (выражение val при этом не вычисляется). После этого функция последовательно вычисляет остальные свои аргументы – формы e_i, которые принято называть операторами. Вычислив последний из них, функция с его значением заканчивает работу, уничтожив при этом свои локальные переменные.

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

[set v e]

Это аналог оператора присваивания. Сначала вычисляются оба аргумента, причем значением аргумента v должно быть имя переменной, существующей в данный момент. Функция присваивает этой переменной новое значение – значение аргумента e. Это же значение является значением функции set, но оно, как правило, не используется.

[fin v₁ v₂]

Значением обоих аргументов должны быть имена переменных (обозначим их V1 и V2), существующих в данный момент, причем переменная V2 должна иметь значение и им должен быть список. Если этот список пуст, то функция ничего не делает и выдает значение (). Иначе функция «расщепляет» список на две части – на его первый элемент, который присваивается переменной V1, и на его «хвост» (без первого элемента), который становится новым значением переменной V2; в данном случае функция выдает результат T.

[return e]

Это оператор досрочного выхода из блока. Функция return может использоваться только внутри функции prog, поскольку она завершает вычисление ближайшей объемлющей блочной функции, объявляя ее значением значение аргумента e.

[go e]

Это оператор перехода. Отметим, что если в качестве оператора функции prog указан идентификатор, то он трактуется как метка. Значением аргумента функции go должен быть идентификатор – одна из меток ближайшей объемлющей блочной функции. Функция go полностью завершает выполнения того оператора этой блочной функции, в который она входит (на любом уровне), и передает управление на оператор, следующий за этой меткой.

Функции для режима возвратов

В язык Плэнер встроен т.н. режим возвратов, который упрощает реализацию различных поисковых алгоритмов, использующих перебор вариантов. Суть этого режима в следующем. В любом месте программы может быть установлена т.н. развилка, от которой возможно несколько вариантов продолжения работы программы. Выбирается один из вариантов, и программа продолжает свою работу. Если затем окажется, что этот вариант неуспешен, тогда вырабатывается т.н. неуспех, по которому программа автоматически «откатывается» к последней (по времени) развилке, отменяя при этом все изменения (в значениях переменных и т.п.), произведенные на неуспешном пути, и в этой развилке выбирается следующий вариант, после чего программа снова «идет вперед». Если в развилке уже не оказалось нерассмотренных альтернатив, то неуспех возвращает программу к предыдущей развилке.

В каких местах программы ставить развилки и с какими альтернативами, считать ли выбранный путь вычисления неуспешным и когда вырабатывать неуспех – за все это отвечает автор программы. Встроенный же режим возвратов обеспечивает запоминание мест развилок и то, какие альтернативы в них еще не рассматривались, обеспечивает возврат программы по неуспеху к последней развилке и отмену ранее произведенных изменений в значениях переменных.

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