Язык программирования Форт

       

Язык программирования Форт

Форт (FORTH) -- это мощный язык программирования, который обеспечивает высокую производительность ЭВМ. Предлагаемая книга является одновременно учебником и справочником, позволяющим овладеть языком Форт независимо от того, начинающий вы программист или опытный. Вы можете пользоваться этой книгой как учебником для классных или индивидуальных занятий, при этом не предполагается знание основ ЭВМ или программирования. Книга содержит полное описание языка, начинающееся с упрощенного изложения принципов работы компьютеров. Постепенно осуществляется переход к более сложным понятиям, не описанным в других книгах. Вы сами можете выбрать материал и скорость изучения с учетом своего уровня подготовки. В книге приводится множество примеров, показывающих стиль программирования на языке Форт, включая полный текст программы редактора, большое количество упражнений для приобретения опыта, уверенности и, что более важно, полезных технических навыков. В даны ответы к упражнениям. Излагаются обе версии языка Форт в соответствии со стандартами 1979 и 1983 гг. Кроме того, изложены вопросы, не освещаемые в стандартах, в том числе организация файлов данных, обработка алфавитно-цифровых текстов, арифметика с плавающей запятой, а также различные инструментальные программные средства, что поможет вам расширить сферу применения языка Форт для ваших нужд. Даны примеры функций усовершенствованной реализации языка MMSFORTH.

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

Операторы сравнения и ветвления
Предположим, что вам нужно проверить, не приводят ли к ошибке слова, которые вы ввели в конце какого-либо определения через двоеточие. Тогда можно сделать, чтобы эти слова игнорировались бы с помощью слова EXIT (разумеется, то же можно сделать, помещая эти слова в круглые скобки). Можно также применить QUIT, чтобы прервать исполнение программы каком-то месте и посмотреть содержимое стека или переменных.

Память Форта. Словари и контекстные словари
Память может адресоваться через обычные коды и, хотя карта памяти организована так же, как было описано, программа может работать со всей доступной памятью. Может быть, наиболее сложное использование памяти большей емкости реализовано в HS/FORTH, где применены различные сегменты для различных частей описаний слов, для различных контекстных словарей и для стеков, буферов и т.д.

Ответы к упражнениям

Способ мышления-Форт

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

Введение
Уже несколько лет я использую для программирования язык Форт. С первой же встречи с ним я был очарован и покорен его простотой, элегантностью и логичностью. И Форт пока ни разу не давал мне повода для разочарований. К сожалению, в нашей стране Форт знают и используют лишь считанные энтузиасты, чему в большой мере способствует отсутствие сколько-нибудь доступной литературы и программного обеспечения.

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

Анализ
Как мы видели, Форт интегрирует аспекты проектирования с вопросами реализации и поддержки. В результате этого упоминание о "типичном цикле разработки" звучит примерно так же, как и упоминание о "типичном шуме". Однако любой подход лучше, чем отсутствие подхода и, разумеется, некоторые из подходов разработаны лучше других.

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

Детализированная разработка решение задачи
Когда Вы приняли решение по составу компонентов в задаче, Вашим следующим шагом является разработка этих компонентов. В этой главе мы применим технику решения задач для детализированной проработки проблемы на Форте. Это - время чистого творчества, та часть, которую большинство из нас находят наиболее занятной. Есть особое моральное удовлетворение в том, чтобы выйти на ринг с нетривиальной проблемой и уйти оттуда победителем.

Разработка: элементы Форт-стиля
Плохо написанная на Форте программа обычно выглядит как "код, пропущенный через пресс для мусора". Форт в действительности дает много свободы в выборе способа написания программ. Такая свобода обеспечивает все возможности для создания черезвычайно удобочитаемого и легко управляемого кода, что достигается сознательным применением элементов хорошего Форт-стиля.

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

Работа с данными: стеки и состояния
Форт оперирует с данными одним из двух способов: либо на стеке, либо в структурах данных. Когда какой из подходов применять и как управлять и стеком, и структурами данных - вот тематика этой главы. Для Форт-слов простейший способ прередачи аргументов друг другу - это через стек. Процесс "прост", поскольку вся работа по заталкиванию и извлечению чисел со стека подразумевается сама собою разумеющейся.

Минимизация структур управления
Структуры управления в Форте играют меньшую роль, нежели в других языках. Форт-программисты стараются описывать очень сложные приложения в терминах коротких слов и без особого акцента на конструкции IF THEN. Имеется несколько приемов для минимизации структур управления. Они включают в себя:* вычисления или подсчет * упрятывание условных операторов при рефакторизации * использование структурированных выходов * перепроектирование.

Обзор Форта (для новичков)
На Форте (FORTH) говорят словами (и числами), которые отделяются друг от друга пробелами: ЛАДОНЬ ОТКРЫТЬ РУКА ОПУСТИТЬ ЛАДОНЬ ЗАКРЫТЬ РУКА ПОДНЯТЬ Подобные команды могут быть набраны прямо с клавиатуры или вначале набраны редактором на устройствах массовой памяти (в файлах на диске), а потом загружены ("LOAD"). Все слова, уже имеющиеся в системе или определенные пользователем, существуют в "словаре", связном списке. "Определяющие слова" используются для добавления новых имен в словарь.

Язык Форт и его реализации

Язык программирования Форт (англ. forth - вперед и одновременно сокращение от fourth - четвертый), которому посвящена эта книга, появился в начале 1970-х гг. в США. Его изобретатель Чарльз Мур первоначально применил его для разработки программного обеспечения микроЭВМ, управляющей работой радиотелескопа. Преимущества работы с языком Форт вместо применявшегося ранее Ассемблера были настолько велики, что вскоре он стал использоваться и на других специализированных ЭВМ.
Быстрый рост популярности языка Форт начался с середины 1970-х гг., когда появились персональные ЭВМ. Оказалось, что этот язык позволяет обходиться сравнительно небольшим набором возможностей первых персональных ЭВМ, превращая их в удобный и эффективный инструмент для самой разной работы. К середине 1980-х гг. Форт выдвинулся на третье место после языков Бейсик и Паскаль в качестве средства программирования для персональных ЭВМ, и рост его применения продолжается. Широкое распространение получили коммерческие программные продукты, написанные на Форте: системы обработки текстов, пакеты машинной графики, трансляторы, видеоигры. Стихийно быстрое распространение Форта и его практический успех обусловили необходимость стандартизации языка. В 1983 г. был опубликован стандарт «Форт-83», в соответствии с которым ведется изложение материала в этой книге.

Предисловие
Этот язык, получивший широкое распространение за рубежом (особенно как средство программирования для персональных ЭВМ), стал привлекать внимание и советских программистов благодаря особенностям своей методологии. Язык Форт сочетает в себе достоинства интерпретирующих и компилирующих систем и ориентирован на диалоговый режим работы. В книге приведено большое количество примеров.

Основные понятия
Язык Форт больше всего похож на язык ассемблера. Его синтаксис также максимально прост. Запись каждой конструкции (команды) состоит из одного слова мнемонического обозначения, в качестве которото может выступать последовательность любых литер, не содержащая пробела. Простота синтаксиса является следствием того, что в качестве вычислительной модели используется стековая машина.

Шитый код и его разновидности
Логически можно выделить два подхода к реализации языков программирования трансляцию и интерпретацию. Транслятор преобразует входной текст программы в машинный код данной ЭВМ; впоследствии этот код, объединяясь с другими машиниыми модулями, образует рабочую программу, которую можно загрузить в оперативную память и исполнить. Интерпретатор непосредственно исполняет программу на языке высокого уровня, рассматривая входной текст как последовательность кодов операций, управляющих его работой.

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

Модель форт-системы
Приводимый ниже текст представляет собой ядро системы ФОРТ-ЕС (см. ), из которого исключены запускающая часть и реализации слов нижнего уровня для обмена с терминалом и внешней памятью. Общий объем ядра 8Кбайт (свыше 200 слов). Текст состоит из двух частей списка слов с их краткими спецификациями и экранов с определениями на встроенном языке ассемблера и на языке Форт.

Распространенные форт-системы
Форт-СМ. Система разработана в Ленинграде С.Б.Кацевым (ЛГУ) и И.А.Шендриковым (ЛИТМО) на основе стандарта Форт-83. Используется с 1985г. на ЭВМ СМ-3, СМ-4, ДВК, Электроника-60, БК0010. Словарь включает около 350 слов, его общий объем 10,5К. В зависимости от генерации может работать под операционными системами ОСРВ, РАФОС или без операционной системы с перфоленточной загрузки.

Список литературы

Введение в теорию программирования. Функциональный подход

Важнейшими математическими формализациями, рассматриваемыми в данном курсе, являются ламбда-исчисление и комбинаторная логика.
Еще в 1924 г. М. Шейнфинкель (Moses Schonfinkel) разработал простую (simple) теорию функций, которая фактически являлась исчислением объектов-функций и предвосхитила появление ламбда-исчисления – математической формализации, поддерживающей языки функционального программирования (т.е. программирования в терминах функций).
Затем в 1934 г. А. Черч (Alonso Church) предложил собственно исчисление ламбда-конверсий (или ламбда-исчисление) и применил его для исследования теории множеств. Вклад ученого был фундаментальным, так что теория до сих пор называется ламбда-исчислением и часто именуется в литературе ламбда-исчислением Черча.
Позднее, в 1940 г., Х. Карри (Haskell Curry) создал теорию функций без переменных (иначе называемых комбинаторами), известную в настоящее время как комбинаторная логика. Эта теория является развитием ламбда-исчисления и представляет собой формальный язык, подобный языку функционального программирования.

Вступительная лекция
В 60-х годах Дж. Бэкусом (John Backus) были созданы основы формализации синтаксиса языков программирования посредством специального математического языка. Позднее П. Науром (Peter Naur) этот язык (а с точки зрения целевого языка программирования — метаязык) был доработан, в результате чего возникла математическая нотация, известная и сегодня под названием "форм Бэкуса-Наура", или, сокращенно, БНФ.

Классификация языков программирования
Первые языки программирования возникли относительно недавно. Различные исследователи указывают в качестве времени их создания 20-е, 30-е и даже 40-е годы XX столетия. Нашей задачей является не установление самого раннего языка, а поиск закономерностей в их развитии.

Концепция и возможности подхода .NET
Попытаемся найти ответ на вопрос: что такое .NET? Несмотря на популярность термина, однозначно ответить непросто, прежде всего по той причине, что ответ представляется многоаспектным.

Функциональный подход к программированию
Время появления теоретических работ, обосновывающих функциональный подход, относится к 20-м – 30-м годам XX столетия. Как мы убедимся впоследствии, теория часто значительно опережает практику программирования, и важнейшие работы, которые сформировали математическую основу подхода, были написаны задолго до появления компьютеров и языков программирования, которые потенциально могли бы реализовать эту теорию.

Ламбда-исчисление как формализация языка функционального программирования
Пожалуй, наиболее продуктивной формализацией понятия "функция" стала математическая теория, известная сегодня под названием ламбда-исчисления. Более точно это исчисление следует называть исчислением ламбда-конверсий.

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

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

Теория типов и комбинаторная логика
В математике принято называть типами (или, иначе, сортами) относительно устойчивые и независимые совокупности элементов, которые можно выделить во всем рассматриваемом множестве (предметной области). Заметим, что разделение элементов предметной области на типы или сорта во многом является условным и носит субъективный характер, т.к. зависит от эксперта в этой области.

Задание
Сформулируйте формальную постановку задачи, запишите правила вывода и реализуйте программу на SML в соответствии с вариантом исполнения.

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

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

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

Рекурсивные функции и множества
Построим модель рекурсивных вычислений посредством формальной логики. Под рекурсивным определением объекта (как в абстрактном теоретическом смысле, так и в аспекте практического программирования) будем понимать такое определение, которое содержит внутри себя ссылку на определяемый объект.

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

Абстрактные машины и категориальная комбинаторная логика
Абстрактной машиной (abstract machine) в рамках данного курса будем называть математическую формализацию, которая моделирует правила выполнения программы (или, иначе, алгоритмы) для реальной вычислительной машины (компьютера).

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

Оптимизация вычислений и абстрактные машины
Проиллюстрируем особенности реализации наиболее существенных стратегий вычислений на примере КАМ. Как было показано в ходе предыдущей лекции, такая формализация вычислительной машины как категориальная абстрактная машина позволяет вполне удовлетворительно реализовать модель транслятора языка функционального программирования.

Теоретические сведения
Состояния КАМ принадлежат пространству декартово замкнутых категорий (д.з.к.), важными свойствами которых являются тождественное преобразование, а также операции композиции, образования упорядоченной пары, взятия проекций, каррирования и аппликации.