Что такое паскаль в программировании

Computer Science Logo Style volume 3: Beyond Programming 2/e Copyright (C) 1997 MIT

фото на обложке

Файл программы для этой главы: pascal Эта и следующая главы посвящены двум взаимосвязанным вещам: почему разные языки программирования отличаются друг от друга и как реализуется язык программирования. Чтобы сделать обсуждение конкретным. Я выбрал в качестве примера конкретный язык: Pascal. Этот выбор кажется уместным отчасти потому. Что Pascal сильно отличается от Logo. А отчасти потому. Что он широко используется в качестве средства обучения вводной информатике. Той же самой задаче. Которую я пытаюсь решить в этой книге с помощью Logo.

*

*Недавней тенденцией в образовании в области компьютерных наук стал переход от языка Pascal к языку C или C++. Я не следовал этой тенденции в этой книге. Потому что. С моей точки зрения. Язык Си не освещает никаких новых проблем. Он имеет более сложный синтаксис и упускает одну интересную особенность Паскаля: вложенные определения процедур (блочная структура). C++ действительно вводит проблему объектно-ориентированного программирования. Но, я думаю. Не таким образом. Чтобы прояснить эти проблемы; если вы хотите понять ООП. Вам лучше изучить объектно-ориентированное программирование.

Для целей этой книги я написал программу которая переводит небольшое подмножество Паскаля в имитируемый машинный язык. Вы можете получить настоящий компилятор Pascal для своего компьютера. Который принимает полный язык, и это то. Что вы должны сделать. Если хотите научиться программировать на Pascal. У меня было две причины написать этот компилятор подмножества. Одна из них заключается в том. Что некоторые читатели могут не иметь доступа к компилятору Pascal, а мой. Несмотря на его ограничения. Позволит вам изучить те части языка. О которых я буду говорить.

Во-вторых, следующая глава посвящена тому. Как работает компилятор. И этот компилятор доступен для изучения. Потому что он написано в логотипе.

Когда вы сравниваете два языка программирования. Очевидный вопрос: Пожалуйста, не используйте мой частичный компилятор Pascal в качестве основы для ответа на этот вопрос; это было бы несправедливо. Вы уже знаете мое мнение. Но моя цель в этой главе не в том. Чтобы убедить вас в этом. Вместо этого я хочу. Чтобы вы поняли, почему каждый язык разработан таким. Какой он есть. Для каждого из языковых различий. Которые мы рассмотрим. Есть веские причины для любого выбора; причины. Которые влияют на языкового дизайнера. Будут зависеть от общих целей. Которые он или она имеет для этого языка.

Парадигмы программирования

Возможно, самым важным аспектом разработки языка программирования является парадигма программирования. Которую он поощряет. Парадигма (она произносится как Это аспект стиля программирования. Но когда люди говорят Возможно. Поможет пример различных парадигм.

Вот как факториальная функция обычно вычисляется в Logo. Используя рекурсивную операцию:

to fact :n if :n=0 [вывод 1] выход :n * факт :n-1 конец 

Цель состоит в том. Чтобы умножить несколько чисел вместе. Целые числа от 1 до

:n. Мы делаем это. Выполняя одно умножение в каждом рекурсивном вызове. Эта процедура написана в парадигме функционального программирования. Основным инструментом построения сложности является композиция функций. В этом примере результат рекурсивного factвызова составляется с помощью функции примитива *(умножения).

Теперь рассмотрим этот альтернативный подход:

to fact.seq :n localmake выход : конец продукта 

Это пример парадигмы последовательного программирования. Названной так потому

for, что инструкция выполняет последовательность шагов:

    Умножьте накопленный продукт на 1.
    Умножьте произведение на 2.
    Умножьте его на 3.

.. и так далее. Вместо композиции функций у нас есть частичный результат. Хранящийся в коробке. Переменная product. На каждом шаге старое значение заменяется обновленным.

Хотя fact.seqего можно написать логотипом. Это не самый естественный стиль логотипа. Большинство версий Logo даже не предоставляют forв качестве примитивной команды. Хотя (как мы видели в томе 2) она может быть написана в Logo.* Как мы уже видели. Logo поощряет парадигму функционального программирования. В которой сложные вычисления достигаются с помощью композиции функций и рекурсии.

Logo поощряет функциональное программирование отчасти благодаря акценту на рекурсии. А не на итеративных структурах управления. А отчасти потому. Что списки используются в качестве основного механизма агрегации данных. Как мы видели в главе 3, списки поощряют создание агрегата по одному члену за раз (как это делают рекурсивные функции) и препятствуют мутации (что имеет решающее значение для последовательного подхода).

*Даже в логотипе Беркли forэто библиотечная процедура. А не настоящий примитив.

У Паскаля все наоборот. Можно написать рекурсивную факторную функцию на Паскале:

факт функции(n:integer): целое число; начать , если n=0, то факт := 1 другой факт := n * факт(n-1) конец; 

но привычный программист Pascal с гораздо большей вероятностью напишет эту функцию в последовательном стиле:

факт функции(n:integer): целое число; var product. I: целое число; начать продукт := 1; для i := от 1 до n сделать продукт := продукт * i; факт := конец продукта; 

(Не волнуйтесь, я знаю. Что детали нотации для вас загадка. Но вы все равно должны быть в состоянии увидеть связь между каждой версией Pascal и соответствующей версией Логотипа.

Единственный важный момент в нотации прямо сейчас-это :=оператор присваивания Pascal. Как makeв Logo. Подробнее о синтаксисе языка Паскаль мы поговорим позже.)

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

математический дисплей

использование этих процедур:

to simplex :buttons output 2 * f :buttons end to f :n if equalp :n 0 [выход 1] выходной каскад :n [? + ((choose :n (#-1)) * f (#-1))] 0 end 

Здесь математическое определение f в терминах самого себя отражается в рекурсивной природе операции f. В главе 3 мы повысили эффективность процедуры. Запомнив меньшие значения f, чтобы избежать их повторного вычисления; аналогично. Вместо chooseтого чтобы каждый раз вычислять функцию отдельно. Мы использовали старые значения для вычисления новых:

to simplex :buttons output 2 * first (каскад :кнопки [fput (sumprods butfirst ?2 ?1) ?1] [1] [fput 1 nextrow ?2] [1 1]) конец to sumprods :a :b output reduce конец to nextrow :combs if emptyp butfirst :combs [output :combs] выход fput (sum first :combs first butfirst :combs) ~ 

nextrow butfirst :combs end

Рекурсивная природа f менее очевидна во второй реализации. Но общая техника по-прежнему заключается в композиции функций. (Напомним. Что задача cascadeсостоит в том. Чтобы вызывать функцию повторно. В шаблоне f(f(f(··· f(x))). В этом случае cascadeпроисходит параллельное вычисление двух функций; одна представляет собой список значений симплексной функции f, а другая-ряд треугольника Паскаля.) Наличие функций более высокого порядка (в этой программе я использовал cascade, map, иreduce) — это еще один способ. Которым Logo поощряет функциональную парадигму.

В последовательном стиле композиция функций заменяется последовательностью шагов. В которых значения хранятся в ящиках (элементах массивов) и многократно заменяются различными значениями:

to simplex.seq :buttons localmake localmake местный [левый правый] setitem класса 0 С :F 1 setitem класса 0 :расчески 1 Для [я 1 :кнопки] [ setitem класса :я :ф 0 сделайте setitem :i :гребни 1 ] выход 2 * элемент :кнопки :f end 

Может потребоваться некоторое усилие. Чтобы убедить себя. Что эта процедура действительно вычисляет те же результаты. Что и другие версии! В рамках процедуры массив fсодержит значения f(0), f(1), … так как они вычисляются по одному; массив

combsсодержит одну строку ( одновременно) треугольника Паскаля.

Сначала процедура помещает f(0) в нулевую позицию fмассива и первую строку треугольника Паскаля (содержащую только один 1) в combsмассиве. Затем идет forцикл. Который вычисляет f(1), затем f(2) и так далее. Пока не будет достигнуто желаемое значение. Внутренний forцикл выполняет ту же функцию, sumprodsчто и функция в предыдущей версии simplex: он вычисляет сумму нескольких членов не по составу функций. А путем добавления каждого члена в сумму отдельно.

Инструкция

setitem :i :f (item :i :f) + (item :j :f)*(item :j :combs) 

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

Последовательное симплексное вычисление выглядит странно в Logo. Но оно гораздо более естественно в Pascal:

функция simplex(кнопки:integer): integer; var left, right. Iinteger; f. Combs: array [0..30] of integer; начать f[0] := 1; combs[0] := 1; for i := 1 to buttons do begin f[i] := 0; справа := 0; для j := 0 до i-1 действительно начинайте слева := справа; справа := гребни[j]; гребни[j] := левый+правый; f[i] := f[i] + (f[j] * combs[j]) 

конец; гребни[i] := 1 конец; симплекс := 2 * f[кнопки] конец;

Паскаль хорошо подходит для этого стиля программирования по нескольким причинам. Один из них заключается в том. Что f[i]нотация для элемента массива является более компактной и более читаемой. Чем использование Логосом вызовов процедур (вызов itemдля изучения элемента массива и setitemизменения его значения). Другой, уже упоминавшийся, — это то. Что forвстроено в Паскаль. Возможно, наиболее важной является блочная структура Паскаля: ключевые beginслова и endмогут быть использованы для группировки того. Что в противном случае было бы отдельными инструкциями. В одну большую инструкцию.

В Logo инструкции. Которые повторяются в forцикле. Должны быть частью списка. Одним из входов в for процедура; в принципе. Вся for вызов-это одна строка инструкций по логотипу.

И Логос, и Паскаль представляют собой компромисс между функциональной парадигмой и последовательной парадигмой. (В логосе графические программы черепах чаще всего выполняются последовательно. Тогда как манипуляции со словами и предложениями обычно выполняются функционально.) Но Logo-это гораздо более функциональный язык. Чем Pascal. Отчасти потому. Что он поддерживает обработку списков (вы можете создавать списки в Pascal. Но это болезненно). И даже более важно. Потому что в Logo легко изобретать функции более высокого порядка. Такие как mapи cascade. Программисты Pascal не могут легко придумать свои собственные структуры управления. Потому что нет ничего подобного runили applyв Pascal. И встроенные структуры управления являются последовательными. (Кроме того for, Pascal имеет эквиваленты команд whileand do.untilв библиотеке логотипов Berkeley.) В качестве другого примера ifelseпримитив Logo может использоваться либо как команда. Либо как операция. Но эквивалент Pascal работает только как команда.

Не все языки программирования идут на компромисс между парадигмами. В наши дни редко можно встретить чисто последовательный язык. Но раньше он был обычным; как оригинальный язык Фортран. Так и ранние микрокомпьютерные версии BASIC не обладали способностью обрабатывать рекурсивные процедуры. Чисто функциональные языки не находят широкого применения в промышленности. Но представляют интерес для многих исследователей информатики; наиболее известный пример-ML. В чисто функциональном языке нет оператора присваивания (как makeв Logo) и мутаторов (как setitemв or .setfirst).

Существуют и другие парадигмы программирования. Помимо последовательной и функциональной. Хотя они являются самыми старыми. Последовательная парадигма возникла прежде всего потому. Что сама цифровая компьютерная техника работает последовательно; Фортран, который был первым языком программирования более высокого уровня. Первоначально рассматривался как просто аббревиатура для аппаратных последовательностей команд компьютера.* Функциональная парадигма была введена с Lisp. Вторым по возрасту языком программирования. Все еще используемым. Хотя Lisp не является чистым функциональным языком (он имеет назначение и мутацию). Его дизайн твердо основан на идее функций как способа выражения вычисления.

Сегодня мы думаем о языках программирования прежде всего как о способах выражения проблем. А не как о способах моделирования работы компьютерного оборудования. Этот сдвиг в отношении позволил развить непоследовательные парадигмы. Мы разрабатываем языки. Которые лучше соответствуют задачам. Которые хотим решить. А не используемому оборудованию.

Еще одна парадигма. Которая сегодня очень популярна,-это объектно-ориентированное программирование. В этой парадигме мы представляем себе. Что вместо одного компьютера. Выполняющего одну программу. Вычислительный мир включает в себя множество независимых Каждый объект включает в себя методы, которые похожи на локальные процедуры, и переменные, такие же. Как переменные. Которые мы использовали все время. За исключением того. Что каждый из них принадлежит определенному объекту. Если один объект хочет узнать значение переменной другого объекта. Первый объект должен отправить сообщение ко второму. Сообщение-это запрос на выполнение метода. Поэтому сообщения. Которые принимает каждый объект. Зависят от методов. Которые он знает.

У логотипа уже много лет есть своего рода проблеск объектной парадигмы. Потому что многие диалекты Логотипа включают в себя несколько черепах. Чтобы переместить черепаху. Вы посылаете ей сообщение. Используя нотацию что-то вроде

спросите 7 [вперед 100] 

чтобы отправить сообщение черепахе № 7. Но эта нотация. Хотя она и передает некоторую изюминку объектно-ориентированного программирования. На самом деле не представляет парадигму. В реальной объектной системе конкретные черепахи могли бы иметь свои собственные. Специализированные forwardметоды. Черепаха 7, например. Может быть специальной Один диалект логотипа. Называемый логотипом объекта. Обеспечивает подлинную возможность объекта.

Объектно-ориентированное программирование естественно вписывается в задачи. В которых компьютер моделирует или моделирует множество реальных объектов; фактически. Эта парадигма была изобретена для моделирования программы. Используемые для того. Чтобы попытаться ответить на такие вопросы. Как Объектами в программе моделирования являются люди. Автомобили. Автобусы и полосы движения. Другим примером проблемы. Которая поддается объектной парадигме. Является оконная система, например. В Mac OS или Microsoft Windows. Каждое окно-это объект; когда окно отображается таким образом. Чтобы скрыть часть другого окна. Новое окно должно отправить сообщение пользователю. скрытый. Говорящий ему не отображать скрытую область.

Некоторые люди утверждают. Что объектно-ориентированное программирование должно использоваться для каждой проблемы программирования не потому. Что всегда уместна метафора независимого объекта, а потому. Что использование объектов помогает скрывать информацию; если каждая переменная принадлежит определенному объекту. Программа с меньшей вероятностью будет иметь ошибку. При которой одна часть программы испортит структуру данных. Используемую в другой части. Это может быть особенно важно. Говорят они. В большой задаче программирования. В которой несколько программистов работают над разными частями программы. Когда процедуры разных программистов объединяются. Могут возникнуть конфликты. Но объектная парадигма помогает изолировать работу каждого программиста от других. Хотя этот аргумент имеет некоторые достоинства. Я с осторожностью отношусь к любому утверждению. Что он конкретная парадигма лучше всего подходит для всех проблем. Я думаю. Что программисты должны быть знакомы со всеми основными парадигмами и иметь возможность выбрать одну из них в соответствии с потребностями каждой задачи.

Другая важная парадигма программирования называется логическим программированием или декларативным программированием. В этом подходе программист вообще не предоставляет алгоритм. А вместо этого перечисляет известные факты о проблеме и ставит вопросы. Это зависит от языковой реализации. Чтобы найти все возможные решения вопроса. Мы видели очень упрощенную версию этой парадигмы при обсуждении логических задач в главе 2. Логическое программирование особенно хорошо подходит для баз данных проблемы. В которых мы задаем такие вопросы. Как Но. Как и все упомянутые мной парадигмы. Логическое программирование универсально; любая задача. Которую может решить компьютер. Может быть выражена в виде логической программы. Логическое программирование довольно популярно в Японии и Европе. Но не так сильно в Соединенных Штатах, возможно. Просто потому. Что оно не было изобретено здесь.

Интерактивные и неинтерактивные языки

Вы используете логотип. Взаимодействуя с языковым процессором. Вы выдаете инструкцию. Логотип делает то. Что вы ему сказали. И, возможно. Печатает результат. А затем вы выдаете другую инструкцию. Вы можете сохранить последовательность инструкций. Определив процедуру. И в этом случае эта процедура может быть вызвана в последующих инструкциях. Но вам не нужно определять процедуры; маленькие дети обычно начинают использовать логотип. Выдавая примитивные команды движения черепахи по одной за раз. Определяющие процедуры можно рассматривать как расширение репертуара вещей. Которые Логос знает. Как сделать для будущего взаимодействия.

Напротив, вы пишете программу на языке Паскаль как целостную сущность, Часто. Когда вы вводите свою программу в компьютер. Вы вообще не имеете дела с процессором Pascal; вы используете другую программу. Текстовый редактор. Чтобы позволить вам ввести свою программу Pascal в компьютер. Тогда вы запускаете сам Паскаль. (Большинство микрокомпьютерных версий Pascal включают простой текстовый редактор для ввода программы. Так же как Logo включает редактор процедур.) Обычно вы храните свою программу Pascal в виде файла на диске и даете имя файла в качестве входных данных процессору языка Pascal.

Имейте в виду. Что это процесс написания и ввода программы. Которая не является интерактивной в Pascal. Вполне возможно написать программу на языке Паскаль. Которая взаимодействует с пользователем сразу после запуска. Чередуя readwriteоператоры and. (Однако пользовательский ввод-это одна из вещей. Которые я оставил в своем подмножестве Pascal. Как вы вскоре увидите.)

Если вы хотите написать свои собственные программы Pascal для использования с моим компилятором. Вам понадобится способ создания дискового файла. Содержащего вашу новую программу. Используя либо редактор процедур Logo. Либо какую-либо отдельную программу редактирования. Примеры программ Pascal в этой главе включены вместе с программными файлами логотипа. Сопровождающими эту книгу.

Наш первый пример полной программы на Паскале-это версия головоломки Я описал эту проблему в первом томе этой серии. Решение Логотипа состоит из двух процедур:

to hanoi :number :from :to :other if equalp :number 0 [stop] ханой :номер-1 :от :другое :до movedisk :номер :от :до ханоя :номер-1 :другое :до :от конца to movedisk :number :from :to print (предложение [Переместить диск] :number 

Для использования этих процедур вы выдаете инструкцию, такую как

? ханой 5  Перемещение диска 1 из a в b Перемещение диска 2 из a в c Перемещение диска 1 из b в c Перемещение диска 3 из a в b Переместите диск 1 из а в с ... и так далее. 

Вот соответствующая программа на языке Паскаль. Эта программа есть в файле tower. (Как вы можете видеть. Программы на языке Паскаль начинаются с имени программы; во всех примерах в этой главе имя файла совпадает с именем программы. Хотя это не является обязательным требованием языка Паскаль.) Не берите в голову детали программы на данный момент; прямо сейчас главное-убедиться. Что вы знаете. Как заставить компилятор Pascal перевести ее в Логотип.

программная башня; процедура ханой(число:целое число;from,on. Other:char); {Рекурсивная процедура. Которая решает подзадачу исходной задачи. Перемещая некоторое количество дисков. Не обязательно 5. процедура movedisk(number:integer;from,on: char); {Эта процедура перемещает один диск. Он предполагает. Что перемещение является законным. То есть диск находится в верхней части своего стека и целевого стека уже не имеет дисков меньшего размера. movedisk(number,from,onto); ханой(номер-1,другой,на,из) 

Как только у вас есть программа Pascal в файле на диске. Вы компилируете ее с помощью compileкоманды с именем файла в качестве входных данных:

? скомпилировать  

Компилятор печатает программу по мере ее компиляции. Отчасти для того. Чтобы вы не заснули во время работы. Но также и для того. Чтобы, если компилятор обнаружит ошибку в программе. Вы увидели. Где она была обнаружена.

Когда компилятор закончит обработку исходного файла (файла. Содержащего программу Pascal). Он остановится. И вы увидите приглашение с логотипом. На этом этапе программа была переведена на имитированный машинный язык. Чтобы запустить программу, скажем

? подрезать  Перемещение диска 1 из a в b Перемещение диска 2 из a в c Перемещение диска 1 из b в c Перемещение диска 3 из a в b Переместите диск 1 из а в с ... и так далее. 

Входными данными для команды prun(Pascal run) является имя программы -слово. Которое следует после programв начале исходного файла.

Разница между интерактивным и неинтерактивным языком заключается не только в произвольном выборе стиля Этот выбор отражает более глубокое различие между двумя различными способами мышления о том. Что такое компьютерная программа. В Логосе на самом деле нет такой вещи. Как Вы можете думать об одной конкретной процедуре как о процедуре верхнего уровня. Но Логос этого не знает; вы можете вызвать любую процедуру напрямую. Используя интерактивную инструкцию. Называющую эту процедуру. Логотип имеет идею рабочего пространства, набор процедур. Хранящихся вместе в файле. Поскольку они связаны. Но рабочее пространство не обязательно должно быть иерархически структурированной иерархией с одной процедурой верхнего уровня. А другие-как подпроцедуры. Это может быть набор полезных процедур без зонтика верхнего уровня. Как библиотека логотипов Беркли. Это может быть группа проектов. Концептуально связанных. Но с несколькими независимыми процедурами верхнего уровня. Такими как два примера запоминания. Два алгоритма сортировки. База данных дерева и другие проекты в algsрабочей области главы 3.

Напротив, программа на языке Паскаль считается единым целым. Оно всегда начинается со слова programи заканчивается точкой. По аналогии с английским предложением. (Подпроцедуры и отдельные операторы в программе разделяются точкой с запятой. Поскольку они аналогичны английским предложениям.*) Нет никакого смысла давать компилятору Pascal исходный файл. Содержащий только процедуры без основной программы.

Я говорю Однако во всех их языках есть точки и точки с запятой.

Почему дизайнеры Logo выбрали интерактивный подход к разработке программ. В то время как дизайнеры Pascal выбрали парадигму целостной программы? Как и все стоящие вопросы. Этот имеет более чем один ответ. И, как и многие вопросы в языковом дизайне. Этот имеет два широких вида ответов: ответы. Основанные на стратегии реализации языка, и те. Которые основаны на базовых целях программирования.

Самый очевидный ответ заключается в том. Что Pascal-это компилируемый язык. А Logo-интерпретируемый. То есть большинство процессоров языка Паскаль-это компиляторы: программы. Которые переводят программу с одного языка на другой. Как переводят книгу с английского на китайский. Большинство компиляторов переводят с исходного языка. Такого как Pascal. На родной машинный язык любого компьютера. Который вы используете. (Мой компилятор Pascal переводится на имитируемый машинный язык. Который на самом деле обрабатывается процедурами логотипа.) В отличие от этого. Большинство версий логотипа являются интерпретаторами: программы. Которые непосредственно выполняют инструкции в исходной программе. Не переводя ее на другой (*

*Это еще один случай. Когда одно и то же слово имеет два несвязанных технических значения. Использование

Чтобы понять. Почему интерпретаторы обычно используют интерактивные языки. В то время как компиляторы обычно подразумевают разработку программ в Если вы думаете. Что компьютер полон маленьких людей. Которые знают. Как выполнять различные процедуры. Которые вы написали, тот. Кто действительно отвечает,-это не тот. Кто выполняет вашу процедуру верхнего уровня. А скорее тот. Кто представляет сам интерпретатор логотипа. Если процедура специалистов похожа на цирк исполнители. Интерпретатор логотипа — это директор манежа. Метафора цирка на самом деле довольно хороша. Потому что. С одной стороны. Каждый исполнитель-это автономная личность. Но в то же время исполнители должны сотрудничать. Чтобы устроить шоу. Уместность метафоры в данном обсуждении заключается в том. Что в компилированном языке нет Компилятор более близок к птице. Которая высиживает яйцо (ваша программа). А затем выталкивает новую птицу из гнезда. Чтобы позаботиться о себе. В компилируемом языке не предусмотрен интерактивный интерфейс. К которому вы могли бы получить доступ. дайте команды. Которые управляют работой вашей программы. Если только ваша программа сама не включает такой интерфейс.

Говоря то же самое по-другому. Интерпретатор Логотипа является частью среды. В которой работает любая программа логотипа. (Вот почему Логотип может обеспечить такое средство. Как run команда. Позволяющая вашей программе создавать новые инструкции логотипа по мере ее продвижения.) Но компилятор Pascal делает свою работу. Переводя вашу программу в другую форму. А затем исчезает. Любые механизмы. Доступные для управления вашей программой. Должны быть встроены в программу. Например, моя паскаль-версия программы В версии логотипа эта инструкция не считается частью программы; вместо этого вы управляете логотипом в интерактивном режиме для вызова hanoiпроцедуры.

Различие между компилируемыми и интерпретируемыми языками не столь абсолютное. Как это было когда-то. Существуют версии Logo. В которых каждая процедура компилируется так. Как вы ее определяете. Но все еще можно давать инструкции в интерактивном режиме. (Некоторые такие версии включают в себя как компилятор. Так и интерпретатор; в других промежуточный язык называется P-код называется промежуточным языком. Потому что уровень детализации в программе P-кода находится между уровнем языка. Который вы хотите использовать. И уровнем базового машинного языка. Его примитивы просты и быстры. А не сложные структуры управления. Такие как ifили for. Преимущество процессора языка Pascal. Основанного на P-коде. Заключается в том. Что компилятор переносим—он может работать на любом компьютере. Все, что нужно. Чтобы начать использовать Pascal на новом компьютере,-это интерпретатор P-кода. Который является относительно простым проектом программирования.

До сих пор я объяснял решение языкового дизайна (интерактивная или неинтерактивная разработка) с точки зрения ограничения реализации (интерпретируемого или компилируемого). Но можно выйти за рамки этого объяснения. Чтобы спросить, почему кто-то решил создать компилятор. А не интерпретатор или наоборот.

Основное преимущество компилятора заключается в том. Что готовая объектная программа работает быстро. Так как она непосредственно выполняется на родном языке хост-компьютера. (Переводчик тоже в конечном счете выполняет программу на родном языке компьютера. Но интерпретатор должен решить. Какие инструкции на родном языке выполнять для данной инструкции на исходном языке каждый раз. Когда эта инструкция оценивается. В скомпилированном языке этот процесс перевода происходит только один раз. Создавая объектную программу. Которая не требует дальнейшего перевода во время работы.) Компромисс заключается в том. Что сам процесс компиляции является медленным. Если вы пишете программу. Которая будет использоваться каждый день навсегда. Скомпилированный язык имеет преимущество. Потому что процесс разработки происходит только один раз. А затем программу не нужно перекомпилировать. С другой стороны. При разработке программы компилируемый язык может оказаться в невыгодном положении. Поскольку любое небольшое изменение в одной инструкции требует перекомпиляции всей программы. (Для некоторых языков существуют инкрементные компиляторы. Которые могут отслеживать. Какую часть программы вы изменили. И только перекомпилировать эту часть.)

Таким образом. Скомпилированный язык. Такой как Pascal (или Fortran или C). Имеет смысл в бизнес-среде. Где программа написана для практического использования. Обычно используя хорошо понятные алгоритмы. Чтобы процесс разработки был простым. Интерпретируемый язык. Такой как Logo (или Lisp или BASIC). Имеет больше смысла в исследовательском объекте. Где изучаются новые алгоритмы и процесс разработки может быть довольно длительным. Но программа никогда не может использоваться в рутинном производстве. (На самом деле никто не использует BASIC в исследовательских целях из-за других слабостей. Но его интерактивная природа-это плюс.) Другая среда. В которой взаимодействие важно. — это образование; студент-компьютерщик пишет программы. Которые, возможно, никогда не будут запущены. Кроме как для тестирования. Программа представляет интерес только до тех пор. Пока она еще не работает. Для таких программ преимущество скорости скомпилированной программы не имеет значения.

Есть также причины. Которые не имеют ничего общего с проблемами реализации. Ранее я говорил о двух противоположных взглядах на компьютерную науку. Которые я назвал взглядом на разработку программного обеспечения и взглядом на искусственный интеллект. В первом случае процесс разработки программы начинается с четкого. Четко определенного представления о том. Что должна делать программа. Эта идея записана в виде спецификации программы это составляет основу для фактического программирования. Начиная с этой начальной точки. Программа разрабатывается сверху вниз; сначала основная программа пишется в терминах подпроцедур. Которые запланированы. Но еще не написаны; затем пишутся процедуры более низкого уровня. Чтобы заполнить детали. Никакая процедура не будет написана до тех пор. Пока не станет ясно. Как она вписывается в общую программу. Поскольку разработчики Паскаля принадлежат к лагерю программной инженерии. Неудивительно. Что программа на Паскале имеет форму единого целого. В котором каждая процедура должна находиться внутри более крупная. Чем набор более автономных процедур. Напротив, логотип-это продукт лагеря искусственного интеллекта. Для которого разработка программ-это более сложный процесс. Включающий как восходящий. Так и нисходящий дизайн. Исследователи ИИ признают. Что они могут начать проект. Имея лишь смутное представление о том. Что будет делать готовая программа или как она будет организована. Поэтому уместно начать с написания фрагментов программы. Которые имеют дело с любыми подзадачами. Которые вы выполняете поймите. А затем посмотрите. Как эти части могут сочетаться друг с другом. Чтобы завершить общий проект. Разработка-это не прямая линия от абстрактной спецификации к конкретным подпроцедурам; это зигзагообразный путь. По которому программист получает идею. Пробует ее. А затем использует полученные результаты как основу для дальнейших размышлений об идеях.

Традиционно интерпретатор был основным инструментом для облегчения разработки интерактивных программ. Недавно, правда, разработчики привезли более интерактивным аромат для компилируемых языков, придумав идею интегрированной среды разработки (ИСР), в котором компилятор одну часть пакета, который также включает в себя языковой Редактор (тот, который знает о синтаксисе языка и автоматически обеспечивает, например, ключевого слова do , которое должно следовать for в Паскале), онлайн документации, и отладчик, это программа. Которая позволяет вам следить за выполнением вашей программы по одному шагу за разом. Как stepкоманда в Berkeley Logo. Идея состоит в том. Чтобы иметь свой торт и есть его тоже: вы используете инструменты IDE во время разработки программы. Но как только ваша программа отлажена. Вы остаетесь с быстрой скомпилированной версией. Которая может быть запущена без IDE.

Блочная структура

До сих пор мы рассматривали. Как каждый язык думает о программе в целом. Перейдем теперь к расстановке фигур в рамках программы или процедуры.

Процедура логотипа начинается со строки заголовка, за которой следуют инструкции в теле процедуры, а затем endстрока. Цель строки заголовка — дать имена самой процедуре и ее входам.

Структура программы на Паскале в чем-то схожа. Но с некоторыми сложностями. Программа начинается со строки заголовка, очень похожей на строку заголовка в логотипе. Слово towerв строке заголовка нашего образца программы-это название программы. Пропуская на данный момент среднюю часть программы. Часть между beginи endв последних нескольких строках является частью заявления программы. Так же как и в Логотипе. Слово endв программе Pascal не совсем аналогично endстроке в процедуре Логотипа; это своего рода закрывающая скобка. Соответствующая beginпредшествующей. Период сразу после финала end это то. Что соответствует линии логотипаend.

То, что делает структуру Паскаля отличной от Логоса. — это часть. Которую я пропустил. Декларация процедур. В логосе каждая процедура является отдельной сущностью. В Pascal объявление процедурыhanoi, например . Является частью программы tower. Эта конкретная программа не использует глобальных переменных. Но если бы это было так. Эти переменные также должны были бы быть объявлены в программе. Если программа использовала глобальные переменные a, b, i, и jтогда это могло бы начаться

программная башня; var a,b:реальный; i,j:целое число; процедура ханой(number:integer;from,onto,other:char); 

Таким образом. Программа на языке Паскаль состоит из

1.     строка заголовка
2.     часть объявления (переменные и процедуры)
3.     часть заявления
4.     заключительная пунктуация (точка)

Но обратите внимание . Что процедура hanoi, объявленная внутри tower, имеет ту же структуру. Что и вся программа. Он начинается со строки заголовка; его часть объявления включает в себя объявление процедуры movedisk; он имеет часть утверждения между beginи end; его окончательная пунктуация является точкой с запятой вместо точки.

Что означает объявление одной процедуры внутри другой? Вы уже знаете. Что означает локальная переменная; если переменная vпринадлежит процедуреp, то эта переменная существует только во время выполнения процедуры; в другой точке программы может быть другая переменная с тем же именем. В Паскале то же самое верно для локальных процедур. В нашем примере программы процедура movediskсуществует только во время hanoiвыполнения процедуры. Было бы ошибкой пытаться вызвать movediskего непосредственно из основной программы.

Строка заголовка процедуры может содержать имена ее входов. Точно так же как строка заголовка процедуры Логотипа содержит имена ее входов. Полезная часть терминологии состоит в том. Что имена переменных в заголовке процедуры называются формальными параметрами, чтобы отличать их от выражений. Которые предоставляют определенные входные значения при фактическом вызове процедуры; последние называются фактическими аргументами. Слова *

*Я немного ввожу вас в заблуждение. Называя его Как и любая часть программы на языке Паскаль. Заголовок может занимать более одной строки или находиться в одной строке с другими объектами. Конец заголовка помечается точкой с запятой. В Паскале разрыв строки подобен промежутку между словами. Однако существуют соглашения для правильного форматирования программы Pascal. Несмотря на то. Что компилятор Pascal не заботится о интервалах и разрывах строк. Люди всегда делают это так. Как я показал вам здесь. С отступами между подчиненными частями программы и каждым оператором в отдельной строке.

Последовательность заголовков. Объявлений. Операторов и знаков препинания называется блоком. Pascal называется блочным структурированным языком из-за того. Что блоки могут включать в себя более мелкие блоки. Другим аспектом блочной структуры является использование Паскалем составных операторов. Последовательность формы

begin statement ; statement ; statement end 

называется составным оператором. Пример из towerпрограммы

начать ханой(номер-1,от,другой,на); movedisk(number,from,onto); ханой(номер-1,другой,на,из) конец 

(Обратите внимание. Что точки с запятой уходят между операторами внутри этой последовательности; ни один из них не нужен после последнего оператора группы. Это синтаксическое правило основано на аналогии между Высказывания на Паскале и английские предложения. О которых я упоминал ранее.) Например. Паскаль включает условное утверждение. Форма которого

если условие то оператор 

Часть простым оператором. Как вызов процедуры. Или это может быть составной оператор. Разделенный beginи end. Поскольку общий термин

Типы операторов

В Логосе мы не говорим о различных типах утверждений. Таких как сложные. Простые и т. Д. Каждая инструкция логотипа (ну, все. Кромеto) — это вызов процедуры. IfНапример, это процедура. Первым входом которой является trueorfalse, а вторым входом-список. Содержащий инструкции. Которые должны быть выполнены. Если первый вход есть true. В языке Паскаль существует несколько различных типов операторов. Каждый из которых имеет свой собственный синтаксис.

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

while condition do оператор; повторяйте операторы до тех пор. Пока условие в то время как x); writeln(x) конец; повторное увеличение(x); 

Они похожи на whiledo.untilинструменты и в логотипе Berkeley. Whileнапример if, требуется один оператор (который может быть составным оператором между beginи end) после do. Однако слова repeatи untilнеявно разграничивают составные операторы. Поэтому вы можете поместить между ними более одного оператора без использования beginи end. Другой пример for, который вы увидите в использовании через мгновение. Продолжая аналогию с английской грамматикой. Составное высказывание подобно сложному предложению с несколькими независимыми (или координированными) предложениями; структурированное высказывание подобно сложному предложению с зависимым (или подчиненным) предложением. (Если вы всегда ненавидели грамматику. Вы можете просто проигнорировать эту аналогию.)

В принципе, существует только два вида простых операторов: вызов процедуры. Который вы уже видели. И оператор присваивания. Используемый для присвоения переменной нового значения. Эта последняя является паскалевской версией makein Logo; она принимает форму

переменная := выражение наклон := ychange/xchange 

Как я уже упоминал. Переменная должна быть объявлена либо в заголовке процедуры. Либо в varобъявлении. (Присвоение представлено двухсимвольным символом:=, потому =что само по себе означает equalpскорее чем make.)

Я говорю, что есть Например. Печать на экране компьютера выполняется с помощью того. Что выглядит как вызов write(аналогично typeв логотипе) или writeln(print). Но это не обычные процедуры. Они не только принимают переменное число аргументов. Но и могут принимать особую форму. Обычно не допускаемую. В movediskпроцедуре в towerпрограмме одним из аргументов writelnявляется

количество:1 

Буква :1Форматирование Pascal print предназначено для того. Чтобы подчеркнуть печать чисел в столбцах. Поэтому по умолчанию каждое число печатается с довольно большим количеством символов. С пробелами слева. Если число не содержит достаточного количества цифр. Точное число символов зависит от типа числа и диалекта языка Паскаль. Но 10-это типичное число для целых чисел. Так

writeln(1,2,3,4); writeln(1000,2000,3000,4000); 

даст результат выглядящий примерно так:

 1 2 3 4 1000 2000 3000 4000 

movediskЯ должен был сказать:1

Каковы плюсы и минусы использования различных синтаксических правил для различных типов операторов? Одна из причин подхода Паскаля заключается в том. Что различия в значении могут быть неявными в определениях различных типов операторов вместо того. Чтобы быть явными в программе. Не волнуйтесь. От вас не ожидают. Что вы поймете. Что означало это предложение. Но вы поймете. Как только увидите пример. В логотипе мы говорим

если :x] в то время как [:x] 

Почему выражение предиката :x в цитируемом списке находится в случаеwhile, но не для if? If хочет, чтобы выражение было вычислено один раз, прежде if чем оно будет вызвано. Фактическим входным сигналом to ifявляется не это выражение. А значение выражения either trueor false. WhileС другой стороны. Он хочет многократно оценить это выражение. Если Logo заранее оценит это выражение и whileвведет значение trueor false, то он не сможет узнать. Когда прекратить повторение.

Тот факт. Что ifтребуется. Чтобы условие оценивалось один раз, но whileхочет оценить его повторно. Не имеет ничего общего с синтаксисом Logo; то же самое верно и в Pascal. Но в Паскале вы говорите

если x); в то время как x); 

В Логотипе тот факт. Что ifусловие whileВ Паскале это просто часть семантических определений операторов if andwhile. (Синтаксис-это форма. В которой что-то представлено; семантика-это значение этого чего-то.)

Еще один пример: начинающие студенты Logo часто испытывают трудности с пониманием того. Почему вы говорите

make 

присвоить значение одной переменной другой переменной. Почему первое заключено в кавычки. А второе-в точки? Конечно, вы понимаете. Что это происходит потому. Что первый входmake-это имя переменной. Которую вы хотите установить. А второй-значение, которое вы хотите ей дать. Но в Паскале это различие подразумевается в семантическом определении оператора присваивания; вы просто говорите

новое := старое 

Поскольку у начинающих студентов с логотипом возникают проблемы с кавычками и точками make, вы можете подумать. Что подход Паскаля лучше. Но у начинающих студентов Паскаля есть своя проблема; они. Как правило. Бросаются такими утверждениями, как

x := x+1 

Это выглядит не так плохо. Как БАЗОВАЯ или фортранская версия. В которой символ для присвоения является просто знаком равенства. Но все равно легко запутаться. Потому что символ xВ версии логотипа

сделать 

явная разница во внешнем виде между "xними и :xработает в нашу пользу.

Каким образом вам легче узнать что-то: вы хотите начать с простого, возможно. Отчасти неточного понимания и узнать о сложных особых случаях позже или предпочитаете. Чтобы вам с самого начала сказали всю правду? Я поставил вопрос так. Что, боюсь. Это показывает мои собственные предпочтения. Но есть много людей с противоположной точкой зрения.

Вопрос о том. Следует ли делать семантику некоторого действия неявной в синтаксисе языка. Является самой глубокой причиной различия между синтаксисом одной инструкции Logo и набором типов операторов Pascal. Но есть и другие следствия. Одно из достоинств составного оператора Паскаля состоит в том. Что он обеспечивает короткие. Управляемые строки команд. Вы видели процедуры логотипа в этих книгах. В которых одна if содержит несколько инструкций. Это особенно болезненная проблема в версиях логотипа. Которые не допускают линий продолжения.

С другой стороны. Синтаксическая однородность логотипа способствует его расширяемости. В приведенном выше примере ifявляется примитивом Logo. В то whileвремя как является библиотечной процедурой. Написанной в Logo. Но разница не очевидна; оба используются синтаксически сходными способами. Вы не можете писать структуры управления. Как whileв Pascal. Потому что нет ничего аналогичного runтому. Чтобы позволить списку инструкций быть входными данными для процедуры. Но даже если бы вы могли. Он должен был бы иметь форму

while(условие,оператор) 

потому что так выглядит вызов процедуры. Но это не то. Как выглядит встроенная структура управления Pascal.

Перетасовка колоды С помощью Массивов

Пришло время для еще одного примера программы на Паскале. Программа cardsпредставляет собой паскаль-версию задачи перетасовки колоды карт. Которую мы обсуждали в главе 3. Она включает в себя локальные переменные. Операторы присваивания и forструктурированные операторы. Это также приведет нас к некоторым дополнительным проблемам языкового дизайна.

программные карты; var ранги:массив [0..51] целых чисел; костюмы:массив [0..51] символов; i:целое число; процедура showdeck; пишите(ранги[i]:3,масти[i]); конец; writeln; процедурная палуба; var i,j:целое число; suitnames:упакованный массив [0..3] символов; ранги[13*j+i] := i+1; костюмы[13*j+i] := suitnames[j] конец; writeln('Начальная колода:'); процедура shuffle; var rank,i,j:целое число; костюм:шар; ранги[j] := ранг; костюмы[i] := костюмы[j]; костюмы[j] := конец костюма; writeln(палуба; конец перетасовки. 

Опытные программисты Pascal заметят. Что эта программа написана не в самом элегантном стиле Pascal. Это частично из-за проблем в Pascal. О которых я не хочу говорить (записи). И частично из-за проблем. О которых я хочу поговорить в следующем разделе (область).

Вот что происходит при запуске программы:

обрезка  Начальная колода: 1Ч 2Ч 3Ч 4Ч 5Ч 6Ч 7Ч 8Ч 9Ч 10Ч 11Ч 12Ч 13Ч 1С 2С 3С 4С 5С 6С 7С 8С 9С 10С 11С 12С 13С 1D 2D 3D 4D 5D 6D 7D 8D 9D 10D 11D 12D 13D 1C 2C 3C 4C 5C 6C 7C 8C 9C 10C 11C 12C 13C Перетасованная колода: 2D 11D 6S 9D 6C 10H 8D 11C 3D 4C 5H 4S 1D 5C 5D 6D 9S 4D 8C 13S 13D 10C 9H 10D 5S 12D 13Ч 9С 3С 1С 10С 4Ч 12С 11С 12Ч 11Ч 2Ч 3Ч 1Ч 13C 8H 7C 2C 1C 7S 6H 2S 7D 8S 12C 3S 7H 

Паскаль чемfor-то напоминает логотип Беркли for по своей семантике. Хотя, конечно. Синтаксис совсем другой. Значение шага должно быть либо 1 (обозначается ключевым toсловом). Либо -1 (downto). Кстати, если вам интересно. Почему я изменил одно из имен переменных в программе Tower of Hanoi с toверсии логотипа ontoна версию Pascal. То это потомуto , что это зарезервированное слово в Pascal и не может быть использовано в качестве имени чего-либо.

Стандарт Pascal не включает в себя randomфункцию. Большинство практических версий Pascal действительно предоставляют какой-то генератор случайных чисел; поскольку стандарта не существует. Я решил реализовать тот тип. Который наиболее полезен для интересующего меня вида программирования. А именно логотипrandom, который принимает целочисленный аргумент и возвращает целое число от нуля до единицы меньше аргумента.

Лексический объем

Программа cardsимеет три процедуры: showdeck, deck, и shuffle. Каждый из них объявляется непосредственно в программе верхнего уровня. Однако showdeckон не вызывается непосредственно на верхнем уровне; он используется двумя другими процедурами. (Это один из сомнительных битов стиля программирования. Который я ввел ради следующего обсуждения; обычно я думаю. Что поместил бы операторы. Которые вызываютshowdeck, в основной программный блок.)

Если вы внимательно прочтете программу. Вы увидите. Что она showdeckиспользует переменнуюi, но не объявляет ее.* (Когда переменная используется. Но не объявляется в определенной процедуре. Это использование переменной называется свободной ссылкой. Использование переменной, объявленной в том же блоке. Называется связанной ссылкой.) В программе есть три переменные с именамиi: одна во внешнем блоке. Одна внутри deckи одна внутри shuffle. Когда, например. Основная программа вызывает deckи deckвызывает вызовы showdeck, какую переменную iона showdeckиспользует?

*На самом деле язык Pascal требует. Чтобы переменная. Используемая в forоператоре, была объявлена в той же процедуре. В которой forпоявляется; программа cardsне является законным Pascal по этой причине. Какова цель этого ограничения? Предположим. Что эта процедура была вызвана из другого forцикла в другой процедуре и обе используют одну и ту же переменную; тогда обе процедуры будут пытаться присвоить этой переменной конфликтующие значения. Логотип Berkeley forавтоматически делает свою переменную локальной для for сама процедура. По той же причине. Но мой компилятор Pascal позволяет нам безнаказанно нарушать это правило. И я сделал это намеренно. Чтобы подчеркнуть свою точку зрения.

В логосе ответом будет то . Что showdeckиспользует iпринадлежность кdeck, процедуру. Которая его вызвала. Это связано с тем. Что Logo следует правилам динамической области: свободная ссылка на переменную направляется на переменные процедуры. Которая вызвала текущую, затем. При необходимости. На переменные процедуры. Которая вызвала эту. И так далее до глобальных переменных. (Динамическая область более полно обсуждается в первом томе этой серии.)

В Pascal showdeckиспользуется iпринадлежность к основной программе. Это происходит потому. Что свободная ссылка на переменную направляется на блок. В котором была объявлена текущая процедура, затем на блок. Окружающий этот блок. И так далее до самого внешнего программного блока. Это правило называется лексической областью. Набор блоков. Окружающих данный блок. От меньшего к большему. Является его лексической средой. Лексическая среда showdeckis

Лексическая среда movediskв towerпрограмме

Набор вызовов процедур. Ведущих к данной процедуре. Является ее динамическим окружением. Динамическая среда процедуры не всегда одинакова; например. Динамическая среда showdeckis иногда

а иногда

Слово lexicon, что означает Он используется в контексте информатики. Потому что лексический контекст процедуры имеет отношение к тому. Где она определена. Точно так же. Как слова определены в словаре. Слово оно используется потому. Что динамический контекст процедуры постоянно меняется по мере выполнения программы.

Каковы причины выбора лексической или динамической сферы? Это еще один выбор. Который был первоначально сделан из соображений реализации. Оказывается. Интерпретатору легко использовать динамическую область. Но компилятору гораздо проще использовать лексическую область. Это связано с тем. Что интерпретатор принимает решение о том. Какую переменную использовать во время работы программы. И динамическая среда известна. Но компилятор должен перевести программу до это бег. Во время Первоначально интерпретируемые языки. Такие как Logo. Lisp и APL. Использовали динамическую область действия. В то время как компилируемые языки. Такие как Fortran и Pascal. Использовали лексическую область. (Был даже период времени. Когда системы Lisp предлагали как интерпретатор. Так и компилятор. И поведение одной и той же программы было различным в зависимости от того. Компилировали ли вы ее или интерпретировали из-за разных правил области действия.)

Более поздние диалекты лиспа. Такие как Common Lisp и Scheme. Были разработаны для использования лексической области даже при интерпретации. Их разработчики считают. Что лексическая область действия лучше по причинам. Которые не зависят от техники реализации. Одна из причин заключается в том. Что динамическая область допускает ошибки программирования. Которые не возникают при использовании лексической области. В Логосе предположим. Что вы пишете процедуру. Которая делает свободную ссылку на некоторую переменную v Допустим. Вы намеревались использовать глобальную переменную с таким именем. Но вы забыли. Что ваша процедура иногда вызывается другой процедурой. Которую вы написали две недели назад и которая случайно имеет имя ввода v. Бывает очень трудно понять. Почему ваша процедура внезапно получает неправильную переменную. С лексической областью действия гораздо проще отслеживать контекст. В котором определяется ваша процедура. Чтобы убедитьсяv, что в лексической среде нет локальных переменных.

Можно поспорить и в пользу динамического объема. Один из аргументов заключается в том. Что в лексически ограниченном языке определенные виды инструментальных процедур вообще не могут быть записаны: такие. Как whileили forкоторые принимают список инструкций в качестве входных данных, и runсписок повторно. Предположим. Вы пишете процедуру в Logo. Которая содержит такую инструкцию, как

в то время как [:градусы] 

Какую переменную degreesвы хотите использовать в этой инструкции? Предположительно. Вы имеете в виду ту же переменнуюdegrees, которая используется другими инструкциями в той же процедуре. Но если бы Logo использовал лексическую область действия, то whileне имел бы доступа к локальным переменным вашей процедуры. (Можно создать другие функции в лексически ограниченном языке. Чтобы обойти это ограничение. Но необходимые методы более сложны. Чем простой способ написания whileлоготипа.)

Другой аргумент в пользу динамической области. Имеющий особое отношение к Logo. Заключается в том. Что динамическая область лучше соответствует ожиданиям неискушенного программиста. Который вообще не думал о области. Одна из целей дизайна логотипа-быть легким для таких новичков. До сих пор мы говорили о сфере действия в терминах конфликтов имен: что происходит. Если две переменные имеют одно и то же имя. Но предположим. Что вы пишете программу с кучей процедур. С кучей различных процедур. имена переменных. Используемые в качестве входных данных. Это очень упрощает жизнь. Если все эти переменные доступны в любое время. Когда вы хотите. Поэтому вам не нужно так подробно думать о том. Как передать определенную часть информации вниз по цепочке вызова процедуры к подпроцедуре. Если некоторые переменные доступны для подпроцедур. А другие-нет. Это еще одна загадка. Которая усложняет программирование. В частности. Динамическая область действия может упростить отладку программы с логотипом. Если вы организуете свою программу так. Чтобы pause в тот момент. Когда происходит ошибка. Вы можете ввести инструкции логотипа со всеми локальными переменными всех ожидающих вызовов процедур. Чтобы помочь вам выяснить причину ошибки. Отладчики для лексически ограниченных языков требуют более сложного механизма отладки. В котором программист должен явно переключать фокус с одной процедуры на другую.

В ситуациях. Которые мы видели. Лексическая область всегда действует как ограничение на доступность переменных для подпроцедур. То есть лексическая среда процедуры всегда является подмножеством ее динамической среды. (Предположим. Что процедура aвключает в себя определение процедуры b, которое. В свою очередь. Включает в себя определение c. Так что лексическая среда cесть {c,b,a}. Вы можете себе представить. Что cдинамическая среда может быть{c,a}, если процедура aвызывается cнапрямую. Но на самом деле это незаконно. Точно так же. Как aне может использовать bлокальные переменные. Он не может использовать bместные процедуры тоже. Причина, по которой динамическая среда может вообще отличаться от лексической. Заключается в том. Что две процедуры могут быть частью одного и того же блока. Как showdeckи deckв cardsпрограмме. в качестве его вывода-не просто название процедуры или текст процедуры. Как мы могли бы сделать в логотипе. Но сама процедура. Лексическая среда и все. Когда такая процедура позже вызывается из какой-либо другой части программы. Лексическая среда процедуры может не быть подмножеством ее динамической среды. И поэтому лексическая область предоставляет ей доступ к переменным. Которые она не может использовать в соответствии с правилами динамической области. Это мощный аргумент в пользу лексической области для Lisp. Но он не применим к Pascal.

Одно специальное правило области действия в Pascal применимо к процедурам. Объявленным в том же блоке: процедура. Объявленная позже. Может вызывать процедуру. Объявленную ранее. Но не наоборот. В cardsпрограмме deckможно позвонить showdeck, но showdeckнельзя позвонить deck Нет никакой глубокой причины для этого ограничения; это полностью в интересах компилятора. Одна из целей разработки Pascal состояла в том. Чтобы было легко написать компилятор. Который проходит через исходную программу один раз. От начала до конца. Без необходимости создавать резервную копию и читать часть программы дважды. В частности. Когда компилятор видит вызов процедуры. Он должен уже знать. Какие входные данные требуются этой процедуре; следовательно. Он должен уже прочитать заголовок подпроцедуры. Обычно вы можете обойти это ограничение путем перестановки процедуры в вашей программе. Но в тех случаях. Когда это не работает. Pascal предоставляет клудж. Который позволяет поместить заголовок в одно место исходного файла и отложить остальную часть процедуры на потом.

Типизированные переменные

Логотип Berkeley имеет три типа данных: word. List и array. (Числа-это всего лишь слова. Состоящие из цифр.) Но переменная в Логосе не имеет типа. Связанного с ней; любая данность может быть значением любой переменной.

В языке Паскаль существует множество типов. И каждая переменная принадлежит только одному из них. В примерах программ до сих пор мы использовали пять типов: char, integer, array of char, array of integer и packed array of char.

Выбор типов данных-это та область. В которой моему компилятору Pascal больше всего не хватает; я реализовал только несколько возможных типов. Я подробно опишу те из них. Которые доступны в моем компиляторе. И дам подсказки о других.

Фундаментальные типы. Из которых строятся все остальные. — это скалярные типы. Представляющие одно значение. В отличие от агрегата. Такого как массив или список. У Паскаля их четыре:

integer    положительное или отрицательное целое число (например, 23)
real    число, включающее десятичную дробную часть (например, -5.0)
char    один символ (например, 'Q')
Boolean     true или false

Паскаль также имеет несколько видов агрегатных типов. Единственное. Что я реализовал. — это массив. Представляющий собой фиксированное количество однородных элементов. Под Полный Паскаль позволяет членам быть любого типа. Включая агрегатный тип. При условии. Что все они одинаковы. Так что вы можете сказать

var a : массив [1..10] массива [1..4] целого числа; 

чтобы получить массив массивов. Но в моем подмножестве Pascal члены массива должны быть скалярами. Это ограничение не слишком сильно. Потому что массивы Pascal могут иметь несколько индексов; вместо вышеперечисленного вы можете использовать эквивалент

var a : массив [1..10, 1..4] целых чисел; 

Это объявление создает двумерный массив. Члены которого имеют имена типа a[3,2].

Обозначение 1..10называется диапазоном; оно указывает на экстент массива. Массивы логотипов Berkeley обычно начинаются с индекса один. Поэтому инструкция по логотипу, например

сделайте 

эквивалентно объявлению Паскаля

var ten:массив [1..10] чего-то 

за исключением того. Что массив логотипов не обязательно должен иметь однородные элементы.* (Кроме того. Тонкое различие заключается в том. Что массив логотипов является независимым датумом. Который может быть значением переменной точно так же. Как число может быть значением переменной. Массив Pascal-это переменная; вы можете изменить содержимое отдельных элементов массива. Но бессмысленно говорить об изменении значения этой переменной. Чтобы быть чем-то иным. Чем этот массив.)

*arrayПримитив логотипа Berkeley может принимать дополнительный второй вход для указания другого начального индекса.

В Паскале диапазон индексов не обязательно должен быть числами; вы можете использовать любой скалярный тип. Кроме реального:

частота var : массив ['a'..'z'] целого числа; 

может использоваться в программе. Которая подсчитывает частоту использования букв. Например в криптографической программе. Члены этого массива будут использоваться. Обращаясь к таким вещам. Как frequency['w']. (В документации Pascal есть слово. Обозначающее Это называется порядковый тип.)

Упакованный массив-это массив. Представленный в компьютере таким образом. Что он занимает как можно меньше памяти. Обычные массивы хранятся таким образом. Чтобы можно было как можно быстрее исследовать или изменять отдельный элемент. Это различие может быть или не быть важным для данного типа на данном компьютере. Например, большинство современных домашних компьютеров имеют память. Организованную в байтах это как раз подходящий размер для одного персонажа. На таком компьютере массив символов и упакованный массив символов, вероятно. Будут представлены одинаково. Но один из моих любимых больших компьютеров, Digital Equipment Corporation PDP-10, имел свою память. Организованную в слова по 36 бит. Достаточно для пяти 7-битных символов с одним оставшимся битом. Упакованный массив символов на PDP-10 был бы представлен пятью символами на слово; обычный массив символов мог бы хранить только один символ на слово. Тратя некоторое пространство. Чтобы упростить задачу поиска n-го символа массива.

Мой компилятор. Который должен быть простым. А не эффективным. Игнорирует packedобъявление. Причина, по которой я использовал его в cardsпрограмме. Заключается в том. Чтобы проиллюстрировать правило Паскаля: утверждение

имена костюмов := 'HSDC' 

присваивает постоянную строку переменной массива suitnames, и такие назначения разрешены только для упакованных массивов char. Кроме того, размер массива должен быть равен длине строки. Если suitnamesбы был массив длиной 10, например. Мне пришлось бы сказать

имена костюмов := 'HSDC ' 

заполнение неиспользуемой части массива явно пробелами.

В операторе присваивания тип переменной слева должен совпадать с типом выражения справа. Назначение может копировать один массив в другой. Если оно включает две переменные одного и того же типа:

var a,b:массив [3..17] вещественных; a := b 

но за исключением случая упакованных массивов char. Упомянутых выше. Нет способа представить постоянный массив в программе Pascal. Если вы хотите массив всех простых чисел меньше 10, вы должны инициализировать его по одному члену за раз:

var primes : массив [1..4] целых чисел; простые числа[1] := 2; простые числа[2] := 3; простые числа[3] := 5; простые числа[4] := 7 

При скалярных присваиваниях допускается небольшое ослабление правил . Поскольку вещественной переменной можно присвоить целое значение. Это значение преобразуется в действительное число (например, 17в 17.0). Обратное не допускается. Но есть две встроенные функции trunc(для roundкоторые можно использовать для преобразования действительного значения в целое. Trunc отсекает дробную часть. Так trunc(4.99)и есть 4. Round округляется до ближайшего целого числа.

Pascal предоставляет обычные инфиксные арифметические операции +, -, *, и /, следуя обычным правилам приоритета. Так же как и в Logo. Результат любого из них является целочисленным. Если оба операнда целочисленны. В противном случае реальны. За исключением того. Что результат /(деления) всегда реален. Существуют целочисленные операции деления div(целочисленное частное) и mod(целочисленный остаток); оба операнда к ним также должны быть целыми числами. Операторы =отношения (как equalpв Logo), (меньше), >(больше), (меньше или равно), >=(больше или равно) и (не равно) возьмите два вещественных или целочисленных операнда и получите логический результат. Есть также логические операторы and, or, и not, как и логические. За исключением того. Что они используют синтаксис infix:

(x 

Дополнительные типы в стандартном Pascal

Стандартный Pascal. Но не моя версия. Включает в себя другие типы агрегатов. Кроме массива. Одним из таких типов является запись; запись-это неоднородный агрегат. Но Например. Можно объявить запись. Содержащую три целых числа и массив из 10 символов. В cardsпрограмме вместо двух отдельных массивов для рангов и костюмов я мог бы сказать

var carddeck: массив [0..51] ранга записи:целое число; костюм:char end; 

Тогда для обозначения ранга карты номер 4 я бы сказал

carddeck[4].ранг 

и это будет целое число. Указатель-это переменная. Значение которой является адресом памяти записи; переменные указателя могут использоваться для реализации динамических структур данных. Таких как списки логотипов. Путем явного построения коллекций полей и стрелок. Показанных на некоторых рисунках в главе 3. Но в Pascal трудно построить что-либо похожее на списки логотипов. Даже используя указатели. Потому что то. Что находится в каждом поле. Должно принадлежать какому-то определенному типу.

Реальный Паскаль также включает в себя пользовательские типы. Существует typeдекларация которая идет перед varдекларацией в блоке:

тип string = упакованный массив [1..10] char; 

Затем объявления переменных можно использовать stringв качестве типа объявляемой переменной. Фактически, стандартный язык Pascal требует использования именованных типов в определенных ситуациях. Например, в заголовке процедуры формальным параметрам должен быть задан именованный тип (либо встроенный скалярный тип likeinteger, либо определенный тип like string); поскольку я еще не реализовал typeсвой компилятор. Он позволяет

процедура paul(слова:упакованный массив [1..10] char); 

хотя стандартный Pascal не допускает такого заголовка.

Вы также можете определить типы поддиапазонов:

тип dieface = 1..6; 

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

тип Битл = (Джон, Пол. Джордж, Ринго); 

Этот тип используется для переменной. Представляющей одну из небольшого числа возможных вещей. На самом деле это тоже своего рода целое число; слово Johnпредставляет 0, Paulравно 1 и так далее. На самом деле. Только во время компиляции программы Паскаль запоминает имена возможных значений; вы не можете прочитать или распечатать эти переменные во время выполнения программы.

Критика типизированных переменных

Зачем кому — то понадобилось использовать поддиапазон или другой ограниченный тип? Если программа работает с переменной типа dieface, то она будет работать точно так же. Как если бы переменная была типа integer. Единственная разница заключается в том. Что использование поддиапазонного типа происходит медленнее. Поскольку программа должна проверять (во время выполнения). Чтобы убедиться. Что любое значение. Которое вы пытаетесь присвоить этой переменной. Находится в одобренном диапазоне.

По мнению энтузиастов Паскаля. Достоинство ограниченных типов. Как и прежде всего типизированных переменных. Состоит в том. Что их использование помогает отлавливать программные ошибки. Например, в cardsпрограмме процедура shuffleимеет переменные iиj, которые используются для индексации массивов ranksи suits. Откуда мы знаем. Что в программе нет ошибки. Чтобы одной из этих переменных было присвоено значение. Которое не является допустимым индексом для этих массивов? Такая ошибка будет поймана. Когда мы используем индексная переменная пытается ссылаться на элемент массива. Который не существует. Но проще отлаживать программу. Если мы получаем сообщение об ошибке в тот момент. Когда переменной присваивается неверное значение. Так что я должен был заявить

var i,j : 0..51; 

вместо того. Чтобы использовать integer. (Конечно. Одна из причин. По которой я не использовал тип поддиапазона. Заключается в том. Что я не реализовал их в своем компиляторе!)

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

*Я знаю. Что сказал. Что не собираюсь пытаться убедить вас. Какой язык лучше. Но в этом конкретном вопросе я действительно думаю. Что у людей Паскаля нет ноги. На которую можно опереться.

i := 0; в то время как я]); i := i+1 конец 

В этом нет ничего плохого. Он выведет значение каждого члена двух массивов. Начиная с индекса 0 и продолжая через 51. Однако в конце whileинструкции переменная iимеет значение 52. Это не ошибка; программа не пытается ссылаться на элемент 52 массивов. Но если мы объявим i тип поддиапазона так. Как мы Этот конкретный пример можно было бы переписать . Используя forвместо while чтобы избежать этой проблемы. Но оказывается. Что существует множество алгоритмов. Которые прыгают в массиве. В котором индексная переменная иногда принимает значение прямо за пределами массива. Некоторые алгоритмы сортировки. Например, таковы.

Типизированные переменные работают против надежности программы. (Надежная программа-это та. Которая сохраняет спокойствие перед лицом плохих данных или другой ошибки пользователя. А не умирает внезапно.) Например. Предположим. Что мы хотим найти сумму множества чисел. Какой-то человек собирается ввести эти цифры в компьютер. По одной за раз. Мы не знаем заранее. Сколько их. Поэтому мы позволяем человеку печататьdone, когда закончим. Поскольку машинист-это всего лишь человек. А не компьютер. Мы хотим убедиться. Что программа не взорвется. Если он случайно наберет что-то другое. Кроме номера или номера. done. Вот один из способов сделать это в логотипе:

чтобы добавить номера печати [Введите номера. По одному в строке.] print [Введите слово печать se [Сумма равна] addnumbers1 0 конец чтобы добавить numbers1 :sum localmake вывод addnumbers1 :sum+:next end to readnumber localmake if equalp :input [done] [output []] if numberp first :input [output first :input] печать [Пожалуйста. Введите только номера.] выходной номер окончания 

Если пользователь делает опечатку. Программа говорит об этом. Игнорирует плохой ввод и продолжает работать. Теперь, как мы напишем это на Паскале? В какой тип переменной мы должны читать каждое число с клавиатуры? Если мы выберем integer, то любая запись не-числа побудит Паскаля напечатать сообщение об ошибке и завершить программу. Вместо этого мы можем читать ввод с клавиатуры по array of charодному символу за раз. Тогда все, что вводит пользователь, нормально. Но мы не можем сделать арифметику с результатом-мы не можем добавить его в накопленную сумму. Мы можем прочитать его как chars, а затем напишите процедуру. Которая знает. Как посмотреть на строку цифр и вычислить число. Которое эти цифры представляют. Но это не то. Что мы должны делать сами на языке программирования высокого уровня.

Почему программист должен заранее решить. Являются ли числа. Которыми будет манипулировать программа. Целыми числами? В Logo я могу написать общую числовую процедуру. Подобную этой:

в квадрат :x выход :x * :x конец 

но в Pascal мне нужно по одному для каждого вида числа:

функция RealSquare(x:real): real; начать RealSquare := x * x конец; функция IntSquare (x:integer): integer; начать IntSquare := x * x конец; 

Зачем выбирать различие между целыми и нецелыми значениями? Почему не положительные и отрицательные значения. Или нечетные и четные значения? Исторический ответ заключается в том. Что компьютерное оборудование использует два различных представления для целых и вещественных чисел. Но что с того? Это не означает. Что различие имеет отношение к конкретной программе. Которую я пишу.

Язык ML, который я упоминал ранее как пример чисто функционального языка. Пытается предоставить лучшее из обоих миров в этом вопросе. Это требует. Чтобы переменные имели типы. Как в Паскале. Чтобы помочь поймать ошибки программирования. Но две особенности делают систему типов ML более удобной. Чем систему типов Pascal. Одним из них является предоставление типов союзов. Можно сказать . Что конкретная переменная должна содержатьdone, например. Число или слово. (У Паскаля есть нечто подобное. Называемое вариантами, но они менее гибкие.) Во-вторых. Компилятор ML использует вывод типов, метод. С помощью которого компилятор часто может определить подходящий тип переменной без явного объявления.

Процедуры и функции

В Logo проводится различие между теми процедурами. Которые выводят значение (операции), и теми. Которые этого не делают (команды). Pascal имеет те же категории. Но они называются функциями и процедурами соответственно.

Функция-это такой же блок. Как и блок процедуры. За исключением незначительных изменений. Необходимых для учета того факта. Что функция производит значение. Прежде всего. Заголовок функции должен сказать. Каким будет тип результата:

функция whatever (аргументы) : integer; 

Тип функции должен быть скалярным. А не агрегатным. Это ограничение входит в стандарт только для того. Чтобы облегчить жизнь компилятору. И некоторые версии Pascal допускают функции с массивом (или с записью и т. Д.).

Другое отличие состоит в том. Что в операторной части функционального блока мы должны сообщить Паскалю. Каким будет его значение. То есть нам нужно что-то эквивалентное outputin Logo. Условность Паскаля состоит в том. Что где-то в блоке должен быть выполнен оператор присваивания. Который имеет имя функции в качестве своей левой части. То есть имя функции используется в операторе присваивания. Как если бы это было имя переменной. (Однако имя не должно быть объявлено как переменная.) Это обозначение может немного сбить с толку. Потому что если одно и то же имя появляется справа на стороне оператора присваивания он сигнализирует о рекурсивном вызове функции. Возможно, пример прояснит это.

Программа multiпредставляет собой паскаль-версию запомнившейся полиномиальной функции из главы 3. В версии логотипа t(n,k) был записан с использованием имени свойства k в списке свойств с именем n. В версии Pascal. Поскольку у нас есть многомерные массивы. Легко использовать двумерный массив и хранить t(n,k) внутри memo[n,k].

программа мульти; var memo: массив [0..4, 0..7] целых чисел; i,j: integer; функция t(n,k:integer) : целое число; функция realt(n,k:integer) : целое число; если k = 0, то realt := 1 else if n = 0 then realt := 0 else realt := t(n,k-1)+t(n-1,k) 
writeln(t(4,7)); конец. 

Операторы присваивания, такие как

realt := 0 

являются те. Которые управляют значениями. Возвращаемыми функциями. Эти операторы присваивания не совсем такие. Как outputв Logo. Потому что они не вызывают немедленного возврата функции. Они действуют так же. Как обычные присваивания. Как если бы на самом деле существовала переменная с именем realtor t; когда часть оператора функции завершена. Любое значение. Которое было недавно присвоено имени функции. Используется в качестве возвращаемого значения. (На самом деле функции в программе multi они написаны так. Что выполняется только одно такое задание. И после этого задания больше нет операторов. Которые нужно выполнить. Это довольно распространенный стиль программирования; очень редко можно изменить присвоение имени функции после того. Как оно было сделано.)

Помимо произвольных синтаксических деталей. Дизайн Pascal в отношении процедур и функций аналогичен дизайну Logo. Поэтому я не могу спросить. Почему эти два языка сделали разный выбор. Возможно, это и к лучшему. Поскольку у вас не должно сложиться впечатление. Что Паскаль-полная противоположность Логосу во всех отношениях. Вместо этого мы могли бы сравнить эти два языка с Lisp. В котором есть только операции. Или с большинством версий BASIC. В которых есть только команды. Но у меня нет места. Чтобы рассказать вам об этих языках достаточно. Чтобы сделать такое сравнение осмысленным.

Вызов по значению и вызов по ссылке

Рассмотрим эту процедуру логотипа:

приращение :var make :var (thing :var)+1 конец ? сделать  ? инкремент  ? print :баз 24 

Входные данныеincrement-это имя переменной . Которую вы хотите увеличить. Аналогичная техника используется, например, в pushpopпроцедурах библиотеки and. Которые принимают имя переменной стека в качестве входных данных. Причина, по которой этот метод необходим. Заключается в том. Что мы хотим . Чтобы процедура могла изменять переменную-присваивать ей новое значение.

Та же техника не будет работать в Pascal. Во-первых, ассоциация имени с переменной существует только во время компиляции. После запуска скомпилированной программы переменные не имеют имен. Только адреса в памяти компьютера. Кроме того, incrementон использует преимущества динамической области видимости. Поскольку переменная. Которую он хочет изменить. Является не его собственной. А скорее переменной. Доступной вызывающей процедуре.

Вот как вы это делаете на Паскале:

инкремент процедуры(var v:integer); начать v := v+1; конец; 

Что здесь нового. Так это зарезервированное слово varв списке аргументов. Это слово указывает vна то. Что это переменный параметр; обычные параметры называются параметрами значения. Increment :

программа whatzit; var gub:целое число; начать ... губ := 5; инкремент(gub); ... конец. 

Предположимincrement, было написано без слова varв заголовке. В том случае. Когда оператор increment(gub)был выполнен вот что произойдет. Во-первых, фактический аргумент кincrement (а именно gub) будет оцениваться. Значение будет 5, так как это значение переменной gub. Затем это значение будет присвоено локальной переменной vin increment. Затем incrementбудет запущена командная часть. Оператор присваивания там изменит значение vот 5 до 6. Тогда incrementбудет закончено. И его локальная переменная vисчезнет. Все это не будет иметь никакого влияния на переменную gub. Это обычная интерпретация v вызывается вызовом по значению, потому что то. Что ассоциируется с именемv, является значением фактического аргумента, 5 в этом примере. Независимо от того. Как этот 5 был получен. Например, инструкция в основной программе могла бы быть

инкремент(2+3); 

и это не имело бы никакого значения.

Создание vпараметра переменной вместо параметра значения существенно изменяет работу программы. При incrementвызове фактическим аргументом должно быть имя переменной. А не произвольное выражение. Паскаль не находит значение фактического аргумента и не передает incrementего ; вместо этого формальный параметр vстановится другим именем для той же переменной, названной в фактическом аргументе. В этом примере vстановится другим именем для gub. Итак, оператор присваивания

v := v+1 

на самом деле речь идет вовсе не о локальной переменнойv; это совсем другой способ сказать

gub := gub+1 

и поэтому он действительно влияет на переменную в вызывающем блоке. Такое использование переменных параметров называется вызовом по ссылке, поскольку формальный параметр (v) ссылается на другую переменную.

Один из способов думать о вызове по ссылке заключается в том. Что он обеспечивает, по сути. Своего рода ограниченную динамическую область. Это способ для суперпроцедуры разрешить подпроцедуре доступ к одной выбранной переменной из лексической среды суперпроцедуры. Поскольку это разрешение дается подпроцедуре явно. Вызов по ссылке не приводит к возможным ошибкам именования. Которые противоречат динамической области видимости в целом. Кроме того, динамическая область видимости. Используемая в Logo. Имеет ту проблему. Что вы должны быть осторожны. Чтобы не допустить. Чтобы формальное имя параметра совпадало с именем переменная. Которую вы хотите использовать из среды суперпро-цедуры. Например, в версии логотипа increment, что делать. Если вы хотите использовать incrementдля увеличения имени переменной var? Если вы попытаетесь сказать

инкремент 

это не сработает. Потому incrementчто в конечном итоге будет пытаться увеличить свой собственный формальный параметр. (Вот почему входные данные некоторых процедур библиотеки логотипов Berkeley имеют такие длинные и непонятные названия.) Но у Паскаля incrementне возникло бы никаких проблем с переменной. Названной vв вызывающей процедуре.

С другой стороны. Вызов по ссылке-это немного загадочно. Если вы поняли все вышесказанное и точно знаете. Когда следует указывать varв формальном списке параметров. А когда нет. То у вас это получается лучше. Чем у большинства начинающих студентов Паскаля. В Logo существует только одно правило передачи входных данных процедурам; чтобы сделать что-то подобное incrementработе, вы явно передаете имя переменной в качестве входных данных.

Вызов по ссылке обычно используется. Когда подпроцедуре необходимо изменить значение переменной в суперпроцедуре. Но есть и другая ситуация. В которой некоторые люди используют его. Предположим. Вы хотите написать процедуру. Которая принимает большой массив в качестве аргумента. Если вы сделаете массив параметром value. Pascal выделит пространство для массива в подпроцедуре и скопирует каждый элемент массива из переменной суперпроцедуры в переменную подпроцедуры в качестве первого шага при вызове подпроцедуры. Это трудоемкое копирование массива может быть избегается путем объявления массива в качестве параметра переменной. Тем самым предоставляя подпроцедуре прямой доступ к массиву суперпроцедуры. Однако энтузиасты Pascal считают такое использование вызова по ссылке мошенничеством. Поскольку оно создает возможность того. Что подпроцедура может случайно изменить что-то в массиве суперпро-цедуры. С этой точки зрения вызов по значению безопаснее.

Параметры в логотипе: Вызов по привязке

Использует ли Logo вызов по значению или вызов по ссылке для передачи аргументов процедурам? Официальный ответ учебника — Переменная Logo отличается от переменной Pascal тонким образом. Если вы сможете понять эту разницу между двумя языками. Вы узнаете что-то очень ценное.

В логосе мир полон данных (слов. Списков и массивов). Эти данные могут быть связаны или не связаны с переменными. Например, когда вы вводите такую инструкцию, как

print butlast butfirst [Да. Это, очевидно. Список.] 

задействованы три разных списка: тот. Который вы ввели явно в инструкции. И два меньших списка. Ни один из этих трех списков не является значением какой-либо переменной. Переменная-это ассоциация (называемая привязкой) между именем и данным. Если вы введете инструкцию

make 

мы говорим. Что имя langs привязано к указанному списку. Если вы тогда это сделаете

make 

мы говорим. Что имя mylangsсвязано с тем же самым данным, langsчто и . Мы имеем дело с одним списком. В котором есть два имени.

рисунок: привязки

В Паскале переменная не является привязкой в этом смысле. Переменная Паскаля — это содержащаяся в ней данность. Если у вас есть две переменные массива

var this,that: array [1..10] of integer; 

и вы выполняете такое задание как

это := то; 

тогда есть два отдельных массива. Которые имеют одинаковые значения. Хранящиеся в них. То же самое верно. Хотя и менее очевидно. О скалярах. Если целочисленные переменные iи jоба имеют значение 10, то есть два разных целых числа. Которые случайно имеют одно и то же значение. Это не так. Как математик использует слово Но для программиста Pascal целое число-это не что-то вроде 10; целое число-это коробка. И в коробке может быть что-то вроде 10.

В Logo присвоение переменной (то есть вызов make) изменяет привязку данного имени переменной таким образом. Что это имя теперь ассоциируется с другим датумом. В Pascal присвоение переменной изменяет значение datum, которое неизменно связано с именованной переменной.

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

Но обычно мы не рассматриваем значение переменной Логотипа как указатель; мы думаем. Что значение переменной-это слово. Список или массив. С этой точки зрения передача параметров в Logo в некоторых отношениях действует как вызов по ссылке. А в других-как вызов по значению. Например, вызов по значению создает копию передаваемого значения. Логотип не копирует фактическую данность. Так что в этом отношении он похож на вызов по ссылке. С другой стороны. Присвоение нового значения формальному параметру Логотипа не изменяется значение любых переменных в вызывающей процедуре; таким образом. Logo работает как вызов по значению. С другой стороны. Если датум. К которому привязан формальный параметр. Является изменяемой структурой данных. Такой как массив. Подпроцессор Logo может изменить значение переменной в вызывающей процедуре. Не назначая новое значение имени формального параметра (изменение привязки). А вызывая setitemобщий датум (изменение самого связанного датума).

Следующая диаграмма представляет собой графическое представление идей. Изложенных в последнем абзаце. Эти три столбца представляют вызов Pascal по значению. Вызов Pascal по ссылке и Логотип. В каждом случае основная программа имеет два массива с именами actualи other; затем она вызывает процедуруproc, использующую actualв качестве фактического аргумента значение procформального параметра formal. Вот эти программы:

Вызов Паскаля по значению    Вызов Паскаля по ссылке
 
программа pgm; type pair = array [0..1] целого числа; var actual,other: pair; процедура proc(формальная:pair); начать тело конец begin actual[0] := 3; actual[1] := 4; other[0] := 5; other[1] := 6; proc(фактический) конец. 
программа pgm; тип pair = array [0..1] целого числа; var actual,other: pair; процедура proc(var): pair); начать тело конец begin actual[0] := 3; actual[1] := 4; other[0] := 5; other[1] := 6; proc(фактический) конец. 
Логотип
 
к процессу :формальный  конец тела 

рисунок: каллби

Первая строка рисунка показывает ситуацию. Когда proc вводится. До выполнения его тела. Вторая строка показывает . Что происходит. Если procсодержит назначение othertoformal, т. Е.,

формальное := другое 

либо в версии Pascal, либо

сделать 

в версии логотипа. Третья строка показывает. Что происходит. Если вместо procэтого содержит назначение только одного элемента массива, т. Е.,

формальное[1] := другое[1] 

либо в версии Pascal, либо

setitem 1 :формальный (пункт 1 :прочие) 

в версии логотипа. Ваша цель состоит в том. Чтобы увидеть. Что происходит actualв каждом случае. Когда procон закончен.

Наш последний пример программы Pascal, показывающий использование вызова по ссылке, представляет собой версию сортировки разделов из главы 3, которая использует метод обмена двумя членами массива. Когда это уместно. Чтобы разделить массив на два раздела Эта программа адаптирована из версии Джона Бентли в программировании жемчуга (Addison-Wesley, 1986). Он гораздо ближе по стилю к реальному quicksort. Чем моя версия на основе списка.

В программе сортировки разделов главы 3 мне пришлось приложить много усилий. Чтобы предотвратить ситуацию. В которой каждый член сортируемого списка оказался на одной стороне значения раздела. Решение быстрой сортировки начинается с выбора некоторого элемента массива в качестве значения разбиения и исключения этого элемента из процесса разбиения. В результате наихудший возможный случай состоит в том. Что n элементов массива разделены на элемент секционирования. Раздел размера n-1 и раздел размера ноль. Если нам не повезет каждый раз попадать в это дело. То у нас будет O(n2) время выполнения. Но не бесконечный цикл.

Как мы выбираем член секционирования? Оказывается. На удивление удачно выбрать одну из них наугад; иногда вы получаете очень плохой выбор. Но обычно нет. Но в этой программе я использую популярный метод. Который имеет тенденцию работать немного лучше (то есть. Дать более взвешенную раздела размеров): программа находит первый элемент в несортированном массиве последний элемент. И одна ровно посередине. И выбирает средний из этих трех значений-то. Что ни крупный. Ни самый маленький.

После того. Как элемент секционирования был выбран. Цель состоит в том. Чтобы переставить элементы массива в порядке. Подобном этому:

рисунок: раздел

Если другие члены массива имеют то же значение. Что и тот. Который мы выбрали в качестве элемента секционирования. То на самом деле не имеет значения. В какой секции они окажутся. Важно то. Что перед выполнением секционирования мы не знаем. Где в массиве будет находиться член секционирования. Так как же мы можем удержаться от столкновения с ним при перестановке других членов? Решение состоит в том. Что секционирующий элемент временно удерживается в крайнем левом возможном положении; остальные элементы секционируются. А затем секционирующий элемент возвращается обратно в свое правильное положение.

Разбиение работает с использованием двух индексных переменных iи j, которые начинаются с самого левого и самого правого концов той части массива. Которую мы сортируем. (Помните. Что этот алгоритм использует рекурсивные вызовы для сортировки каждого раздела. Так что это могут быть не все 100 членов полного массива.) Мы iдвигаемся то вправо, то jвлево. Пока не обнаруживаем двух членов. Не стоящих на своих местах. То есть мы ищем ситуацию. В которой data[i]больше член разбиения и data[j]меньше член разбиения. Затем мы меняем местами эти два элемента массива и продолжаем до тех пор. Пока iи j встретимся посередине. Процедура exchимеет два переменных параметра и обменивается их значениями.

Программа psortиллюстрирует довольно распространенный. Но не очевидный метод: массив dataсодержит 100 i, достигающей конца массива. Значение data[100]гарантированно будет больше. Чем все числа. Которые на самом деле сортируются. Наличие этого дополнительного элемента в массиве позволяет избежать необходимости дополнительного сравнения формы

и тем самым помогает сделать программу немного быстрее.

программа psort; данные var: массив [0..100] целых чисел; i: целое число; процедура showdata; var i: целое число; для i := от 0 до 99 do begin if i mod 20 = 0 then writeln; запись(данные[i]:3) конец; writeln; функция медиана(нижняя,верхняя:целое число):целое число; var mid: целое число; begin mid := (lower+upper) div 2; if (data[lower] 

(вернуться к Оглавлению)

СЛЕДУЮЩАЯ тема ЗАДНЕЙ главы

Brian Harvey, bh@cs.berkeley.edu