ЯЗЫКИ СПИСКОВЫЕ
— специализированные алгоритмические языки, предназначенные для описания процессов обработки информации, представленной в виде списков объектов с различными свойствами. В памяти электронных цифровых машин такие списки образуются либо путем расположения членов списка в ячейках памяти с последовательно возрастающими адресами, либо путем указания для каждого члена списка адреса следующего за ним члена списка. К числу осн. Я. с. относятся IPL-V, ЛИСП-1.
Кроме того, во многих универсальных алгоритмических языках имеются спец. средства для описания операций над списками (ПЛ-1, АЛГЭМ, язык ассоциативного программирования, адресный язык и др.). В ряде современных машин имеются спец. устройства для выполнения элементарных списковых операций.
Осн. средствами Я. с. являются: использование адресов связи для построения списков различных видов, объединяющих объекты с общими признаками; использование списковых структур, представляющих собой многоуровневые списки, т. е. списки с ответвляющимися от них подсписками для представления иерархических систем организации данных; использование т. н. продвигаемых списков (стэков или магазинов) для временного запоминания данных в определенном порядке и восстановления их в обратном порядке; организация свободной памяти в виде цепного списка ячеек, обеспечивающая гибкость и полноту использования всего объема памяти и исключающая необходимость в ее детальном предварительном распределении.
Обычно при обработке данных о некоторой совокупности объектов эти объекты распределяются между различными списками, причем один и тот же объект может находиться одновременно в нескольких списках. Для того, чтобы многократно не повторять во всех списках всю информацию об этом объекте, ее записывают в отд. области памяти (обычно на лентах магнитных) в виде т. н. записей. Каждому объекту соответствует отд. запись со своим адресом. В списках объекты указываются их машинными наименованиями, которыми являются обычно начальные адреса участков памяти, в которых хранятся их записи. Списки объектов строятся из списковых слов. В простейшем случае списковое слово состоит из двух частей: в одной части хранится машинный адрес записи объекта, являющегося членом данного списка, в другой — адрес связи, указывающий положение следующего члена списка.
Для Я. с. характерной чертой является цепная организация свободных ячеек (СЯ) списковой области памяти. Обычно свободные ячейки завязаны в т. н. список свободных ячеек. Одна ячейка в памяти постоянно
закрепляется в качестве фиксатора (указателя) свободных ячеек. В первой половине фиксатора СЯ хранится число имеющихся в наличии Я, а во второй — адрес связи, показывающий положение первой ячейки из списка СЯ. В 1-й ячейке имеется адрес связи, указывающий 2-ю ячейку, во 2-й — 3-ю и т. д. В последней ячейке списка СЯ (как и в последней ячейке любого цепного списка) вместо адреса связи стоит условный код (КС), показывающий конец списка. Список СЯ служит резервом, из которого берутся ячейки для построения списков и в который возвращаются ячейки, освободившиеся из списков.
Для каждого цепного списка объектов выделяется одна ячейка, которая играет роль фиксатора этого списка. Адрес ячейки (или идентификатор списка при автоматическом программировании) известен программисту и указывается во всех командах, содержащих обращения к этому списку. Фиксаторы списков могут строиться различными способами. Напр., фиксатор списка, как и указатель СЯ, может содержать две части: 1-ю, указывающую число членов в данном списке, и 2-ю, указывающую адрес первого члена списка. В отличие от списка СЯ, в котором первые части ячеек, содержащих списковые слова, не используются, в списках объектов первые части этих ячеек содержат машинные наименования (адреса записей) объектов, являющихся членами данных списков. Вторая часть каждой ячейки содержит адрес связи, указывающий положение следующего члена списка. Ячейки с членами цепных списков могут размещаться в памяти в произвольном порядке; связи их между собой обеспечиваются адресами связи. При этом не требуется заранее выделять под каждый список определенное число ячеек. Эти ячейки берутся из общего резерва СЯ по мере надобности. Т. о. обеспечивается гибкость использования памяти.
Другим важным достоинством цепного способа организации списков является удобство включения новых и исключения ненужных членов списков. Как включение членов, так и исключение их может производиться из любого места списка без перемещения остальных членов. Включение нового члена в цепной список обычно связано с появлением нового объекта, для которого составляется запись и заносится в одну из свободных зон области памяти, отведенной под записи. Адрес этой записи становится машинным наименованием нового объекта. Затем по значениям признаков объекта определяется, к каким спискам он должен быть отнесен, и производится последовательное включение данного объекта в соответствующие списки.
Для включения нового члена в любой список (и в любое место списка) сначала должна быть взята свободная ячейка из их резерва. В левую половину этой ячейки записывается машинное наименование (адрес записи) нового объекта. Затем процес включения может идти двумя путями. Если новый объект включается в начало списка, то на место адреса связи в новую ячейку записывается значение адреса связи, взятое из фиксатора данного списка, а в фиксатор на место адреса связи записывается адрес новой ячейки. Если новый член включается в середину списка, то сначала находится предшествующий член списка, после которого требуется включить новый член, а затем производится замена адресов связи: в предшествующем члене ставится адрес связи, указывающий новый член, а в новом члене ставится адрес связи, взятый из предшествующего члена. В обоих случаях производится увеличение числа членов в фиксаторе данного списка на единицу.
Процесс исключения членов из цепных списков осуществляется также путем замены адресов связи. Находится член, предшествующий исключаемому (для 1-го члена это будет фиксатор списка), и в предшествующем члене адрес связи заменяется на адрес связи, взятый из исключаемого члена. Одновременно производится уменьшение числа членов в фиксаторе данного списка на единицу. Модификациями цепных списков являются т. н. гнездовые списки и узловые списки.
Я. с. имеют некоторые особенности. Так, язык ЛИСП основан на использовании списков и служит для описания вычислительных процессов с помощью ряда элементарных рекурсивных функций. Язык IPL-V имеет в своем составе ряд спец. операторов, реализующих элементарные процессы просмотра списков, включения и исключения членов списков, образования и стирания списков и подсписков и т. д. Особенностью языка SLIP является двойная цепная адресация списковых членов. При этом каждый член списка содержит не только адрес следующего, но и адрес предыдущего члена списка. Это позволяет осуществлять движение по спискам в двух направлениях (вперед и назад) и обеспечивать контроль адресных переходов. Недостатком этого приема является увеличение расхода памяти и усложнение операций с адресами связи при включении и исключении членов списков.
Язык ассоциативного программирования построен на базе языка АЛГОЛ и обеспечивает возможность описывать алгоритмы (программы) обработки списков, имеющих различные структуры списковых членов. Язык 
использует те же осн. принципы обработки списков, но отличается наличием ряда сложных операторов (процедур). В адресном языке программирования, который также может быть частично отнесен к Я. с., с помощью штрих-операции можно осуществлять переходы по адресам связи в цепных списках и производить поиск данных, включение и исключение членов в цепных списках.
Применение Я. с. и приемов ассоциативного программирования обеспечивает удобное, наглядное и компактное представление сложных алгоритмов решения информационно-логических задач (планирование производства и материально-технич. снабжения, поиск науч.-технич. информации, поиск справочных данных, учет кадров, построение самообучающихся
и эвристических программ для оценки обстановки и выбора решений).
Лит.: Ющенко Е. Л. Адресное программирование. К., 1963 [библиогр. с. 285—286]; Ефимова М. Н. Алгоритмические языки. М., 1965 [библиогр. с. 86]; Китов А. И. Программирование информационно-логических задач. М., 1967 [библиогр. с. 327]. А. И. Китов.
