✖


Jump to content

S-алгол

Add links
S-алгол
Парадигмы Мультипарадигмальность : процедурная , императивная , структурированная.
Семья АЛГОЛ
Разработано Рон Моррисон , Тони Дэви
Разработчик Университет Сент-Эндрюс
Впервые появился 1979 год ; 45 лет назад ( 1979 )
Язык реализации S-алгол
Платформа PDP-11 /40, IBM System/360 , VAX , Zilog Z80 , Macintosh , Sun-3
ТЫ Юникс , БОС/360 , ВМС , КП/М
Под влиянием
АЛГОЛ 60
Под влиянием
PS-алгол , Napier88

S-алгол (Сент-Эндрюс Алгол) [1] : vii — это языка программирования производный от АЛГОЛ 60, разработанный в Университете Сент-Эндрюс в 1979 году Роном Моррисоном и Тони Дэви. Этот язык представляет собой модификацию АЛГОЛА и содержит ортогональные типы данных , которые Моррисон создал для своей докторской диссертации. Моррисон впоследствии стал профессором университета и заведующим кафедрой информатики . Язык S-algol использовался для преподавания в университете на уровне бакалавриата до 1999 года. Этот язык также преподавался в течение нескольких лет в 1980-х годах в местной школе в Сент-Эндрюсе, Мадрасском колледже . Текст по информатике «Рекурсивная компиляция спуска» [2] описывает рекурсивного спуска компилятор для S-алгола, реализованный в S-алголе.

ПС-алгол представляет собой стойкое производное S-алгола. Он был разработан примерно в 1981 году в Эдинбургском и Сент-Эндрюсском университетах. Он поддерживает возможности базы данных , обеспечивая долговечность данных в виде постоянной кучи , которая сохраняется после завершения программ PS-algol.

История и реализации [ править ]

Докторская диссертация Рона Моррисона 1979 года «О разработке Алгола » описывает разработку и реализацию языка S-алгол. [3] В техническом отчете, определяющем язык, «Справочное руководство по S-алголу» (1979, 1988), выражается благодарность нескольким людям за помощь, в том числе Дэвиду Тернеру за обсуждения дизайна языка примерно в 1975 году. [4] : 5  В учебнике по информатике 1981 года «Рекурсивная компиляция спуска» описывается реализация компилятора и процесс начальной загрузки. [2] а в книге 1982 года « Введение в программирование с помощью S-algol» этот язык используется для обучения компьютерному программированию. [1]

Первая реализация S-algol была на компьютере PDP-11 /40 под управлением операционной системы Unix . [1] : vii Из-за небольшого в 64 килобайта, адресного пространства доступного на PDP-11, была выбрана реализация интерпретируемого байт-кода . [3] : 37–38  Однопроходный написанный на S-algol , , компилятор рекурсивного спуска преобразовал исходный код S-algol в S-код, байт-код для абстрактной машины на основе стека, адаптированной для S-algol. Затем S-код был выполнен интерпретатором . Реализация S-algol имела много общего с работой над более ранними компиляторами Pascal . Техника использования компилятора с рекурсивным спуском для создания кода для абстрактной машины была хорошо известна, а компилятор Pascal P. знаменитым примером начала 1970-х годов был [2] : 137  Компилятор S-algol был написан с использованием уточнения . поэтапного процесса [2] : 71  описан Урсом Амманом для разработки компилятора Паскаля [5] и поддержан изобретателем Паскаля Никлаусом Виртом . [6]

Отражая организацию памяти PDP-11 в виде 32 КБ 16-битных слов , кодировка инструкций S-кода была разработана таким образом, чтобы каждый байт-код состоял из одного слова. [3] : 38  Первоначальная загрузка выполнялась путем написания компилятора S-algol на Algol W на IBM/360 , который создавал S-код, и использования его для компиляции компилятора, написанного на S-algol, в S-код. Полученный файл S-кода был скопирован на PDP-11 и выполнен на интерпретаторе S-кода, написанном для PDP-11, что сделало его самостоятельным хостингом . Автономный компилятор S-algol выполнил примерно 7,7 миллиона инструкций S-кода для компиляции, создав выходной файл, содержащий около десяти тысяч инструкций S-кода (16-битных слов). [3] : 45 

Интерпретатор S-кода был написан для компьютера VAX под управлением VMS , что сделало VAX первым портом S-algol . S-algol также был портирован на микропроцессор Zilog Z80 под управлением CP/M , включая средства растровой графики , которые были добавлены в язык. В 1983 году S-алгол был использован в качестве основы для системы PS-алгол, используемой для исследований стойкости . Интерпретатор S-кода PS-algol был реализован на языке C , а язык S-кода был расширен за счет включения растровой графики. Реализация PS-algol послужила основой для портирования S-algol на рабочие станции Macintosh и Sun с компилятором, переписанным на C и ориентированным на расширенный S-код. [4] : 5 

S-алгол послужил основой для исследования PS-алгола в 1983 году, а несколько лет спустя PS-алгол стал отправной точкой для языка и реализации Napier88 . В то время как все компиляторы S-algol создавали S-код для интерпретации, более поздняя реализация Napier88 экспериментировала с генерацией кода на C и компиляцией его с помощью компилятора gcc, чтобы обеспечить реализацию собственного кода . [7]

Обзор языка [ править ]

Программа на S-algol представляет собой последовательность объявлений и предложений. Объявленные элементы языка включают константы, переменные, процедуры и структуры. В объявлениях констант и переменных должно быть указано начальное значение. Компилятор выводит тип данных объявленной константы или переменной из типа начального значения, поэтому тип не указывается явно. Типы данных включают целочисленные, вещественные, логические, строковые, указатель (на структуру) и файл, а также векторы (массивы) этих типов. В объявлениях процедур указываются типы данных их аргументов и возвращаемое значение (кроме случаев void). Структуры также определяют типы данных своих полей. Предложения включают в себя выражения и управляющие структуры (if, case, for, while и повторение while). Структуры управления if и case могут иметь значения и могут свободно использоваться в выражениях, если соблюдаются правила совместимости типов. [4] [1] 

! Comments are introduced by an exclamation point and continue until end of line.

! The let keyword introduces declarations of constants and variables
! Identifiers start with an alphabetic character followed by alphanumeric characters or the full stop (.)
! An initial value must be given, and this determines the data type of declaration

let width := 10                   ! := sets the value of a variable, this is an int
let animal := "dog"               ! type string

let x := -7 ; let y := x + x      ! ; separates clauses, needed only if there are two or more clauses on a line

let n.a = 6.022e+23               ! = is used to set the value of a constant, this is a cfloat (constant float)

! if and case can have values and be used in expressions
let no.of.lives := if animal = "cat" then 9 else 1

! Sieve of Eratosthenes
write "Find primes up to n = ?"
let n = readi                     ! constant values can be set during the program run
let p = vector 2::n of true       ! vector of bool with bounds 2 to n
for i = 2 to truncate(sqrt(n)) do ! for indexes are constants so they use = rather than :=
    if p(i) do                    ! vector dereference uses parens like a procedure call
        for j = 2 * i to n by i do
            p(j) := false
for i = 2 to n do
    if p(i) do write i, "'n"      ! 'n in a literal string is a newline

! structure (record) type for a binary tree of cstrings
! the pntr data type can point to a structure of any type, type checking is done at runtime
structure tree.node(cstring name ; pntr left, right)

! inserts a new string into the binary tree head
procedure insert.tree(cpntr head ; cstring new -> pntr)
! the case clause ends with a mandatory default option, use default : {} if it is not needed
case true of
    head = nil       : tree.node(new, nil, nil)
    new < head(name) : { head(left) := insert.tree(head(left), new) ; head }
    new > head(name) : { head(right) := insert.tree(head(right), new) ; head }
    default          : head

procedure print.tree(cpntr head)
if head ~= nil do                 ! ~= is the not equals operator
begin
    print.tree(head(left))
    write head(name), "'n"
    print.tree(head(right))
end

let fruit := nil
fruit := insert.tree(fruit, "banana")
fruit := insert.tree(fruit, "kiwi")
fruit := insert.tree(fruit, "apple")
fruit := insert.tree(fruit, "peach")
print.tree(fruit)                 ! print in sorted order

! The end of the S-algol program is indicated by ?
?

Семантические принципы [ править ]

Как следует из названия, S-algol является членом семейства ALGOL языков программирования . Моррисон выделяет пять черт семейства АЛГОЛ: [3] : 5 

  1. Правила области и структура блоков . Имена могут быть введены для определения локальных величин, которые не определены вне локальной среды , но разные среды могут однозначно использовать одно и то же имя для представления разных объектов. [3] : 5 
  2. Средство абстракции — предоставление мощного средства абстракции для сокращения и уточнения программ. В семействе ALGOL это обеспечивается процедурами с параметрами . [3] : 5 
  3. Проверка типов во время компиляции . Типы можно проверить путем статического анализа программы. [3] : 5 
  4. Бесконечное хранилище . Программист не несет ответственности за распределение памяти и может создавать столько объектов данных, сколько необходимо. [3] : 5 
  5. Выборочное обновление магазина . Программа может выборочно изменять магазин. В семействе АЛГОЛ это осуществляется с помощью оператора присваивания . [3] : 6 

S-algol был разработан, чтобы отличаться от предыдущих членов семейства ALGOL, поскольку он разработан в соответствии с семантическими принципами, обеспечивающими мощность за счет простоты и простоту за счет большей общности. (См. «Ортогонал» .) Моррисон описывает три семантических принципа, которыми руководствовалась конструкция S-алгола:

  1. Принцип соответствия . Правила, регулирующие имена, должны быть единообразными и применяться повсеместно. В основном это касается соответствия объявлений параметрам процедуры, включая рассмотрение всех режимов передачи параметров. Этот принцип был исследован Р.Д. Теннентом совместно с Паскалем. [8] и уходит корнями в работу Питера Ландина. [9] и Кристофер Стрейчи . [3] : 9–10  [10]
  2. Принцип абстракции . Должна быть возможность абстрагироваться от всех значимых семантических категорий в языке. Примеры включают функцию, которая является абстракцией над выражениями , и процедуру, которая является абстракцией над операторами . Теннент и Моррисон отмечают, что применить этот принцип сложно, поскольку трудно определить семантически значимые конструкции, которые следует абстрагировать. [3] : 10 
  3. Принцип полноты типов данных . Все типы данных должны иметь одинаковые права в языке и должны быть разрешены в общих операциях, таких как присвоение или передача в качестве параметра. [3] : 10  (См. первоклассный гражданин .)

Моррисон также выделяет еще одно основное соображение при проектировании:

  1. Концептуальное хранилище . Ключевые проектные решения, касающиеся хранилища ( управления памятью ), включают в себя то, как используется хранилище, его связь с типами данных, реализацию указателей и защиту ( постоянные местоположения, которые не могут быть обновлены). [3] : 10–11 

Дизайн [ править ]

Диссертация Моррисона объясняет, как принципы проектирования были применены в S-алголе.

Типы данных [ править ]

Базовыми или примитивными типами данных в S-алголе являются целочисленные, действительные, логические, файловые и строковые. (Позднее были добавлены типы пикселей и изображений для поддержки растровой графики .) Целое , вещественное и логическое значения — это типы, общие для большинства языков программирования. Тип файла представляет собой ввода-вывода (I/O) поток , который позволяет записывать или читать объекты данных. Строковый тип во многих языках того времени считался составным типом , но включение его в качестве собственного типа упрощает использование основных операций конкатенации, выбора подстроки, длины и сравнения (равно, меньше и т. д.). Это гораздо приятнее, чем массивы символов, используемые в Паскале. [3] : 12 

Векторы снабжены компонентами любого типа. Для любого типа данных T, *T — это тип вектора с компонентами типа T. Границы вектора не являются частью его типа, а определяются динамически, а многомерные массивы реализуются как векторы векторов . [3] : 12 

Тип данных структуры содержит любое фиксированное количество полей, каждое из которых имеет фиксированный тип. Класс структуры не является частью типа, но может определяться динамически. [3] : 12 

Замыкание базовых типов векторов и структур обеспечивает бесконечное количество типов данных. Определение языка позволяет использовать любой тип везде, где он приемлем. Это не относится к инфиксным операторам , поскольку они являются синтаксическим сахаром для общих функций и не являются частью семантической модели. [3] : 12–13 

Магазин [ править ]

Векторы и структуры имеют полные права и могут назначаться при передаче в качестве параметров, но копирование при назначении и при передаче может быть неэффективно для больших объектов. Векторы и структуры рассматриваются как указатели на объекты, а указатели назначаются и передаются как параметры. Указатели как общие объекты, как в АЛГОЛе 68 и C, отвергаются для S-алгола из-за опасений CAR Hoare по поводу нулевого указателя. [11] и проблемы с висящими указателями . [3] : 13 

S-algol предоставляет истинные константные значения , объекты, значение которых не может быть обновлено. Эта идея принадлежит Стрейчи, но константы во многих языках, таких как Паскаль, являются константами манифеста, обрабатываемыми во время компиляции и не реализуемыми как защищенные места. Также должна быть возможность объявить константу любого типа данных, а не только скалярных типов. [3] : 13 

Структуры управления [ править ]

S-algol — это язык, ориентированный на выражения, а операторы — это выражения типа void . Как следствие, некоторые управляющие структуры представляют собой выражения, возвращающие значения .

Существует несколько условных конструкций . Двуальтернативная версия условного оператора: if <condition> then <clause> else <clause>, где предложения могут быть утверждениями или выражениями. Если это выражения, они должны иметь один и тот же тип. Однорукий условный if <condition> do <statement> имеет тип void. [3] : 13  Использование do вместо else в условном операторе позволяет избежать висящей синтаксической двусмысленности else . [2] : 20 

The case В предложении есть селектор любого типа, который сопоставляется с помощью проверки равенства с выражениями того же типа, чтобы найти выбранное предложение. Предложение case может быть оператором или выражением, поэтому все предложения результата должны быть операторами (типа void) или выражениями одного и того же типа. Матчи проверяются по порядку, поэтому это напоминает защищенные команды Эдсгера Дейкстры без недетерминизма . [3] : 14 

Операторы цикла в основном обычные. for цикл аналогичен циклу Хоара. [12] Идентификатор элемента управления является постоянным и не может быть изменен внутри цикла. Также традиционными являются while <condition> do <statement> и repeat <statement> while <condition> петли. repeat <statement> while <condition> do <statement> конструкция обеспечивает ранний выход или «полтора» [13] петля. [3] : 14 

Абстракции [ править ]

S-алгол абстрагирует выражения как функции, а операторы (пустые выражения) — как процедуры. Модули могли бы обеспечить абстракцию объявлений, но S-algol не включает модули из-за трудностей, которые они создают при использовании блочной структуры. Последняя синтаксическая категория — секвенсор или управляющая структура. Теннент использовал термин «продолжение» для абстракции секвенсоров. Это были обобщения goto и Break . Самая известная абстракция в этой категории — call-with-current-continuation , но она станет понятна лишь несколько лет спустя. S-algol не поддерживает переходы и разрывы, а также абстракцию над секвенсорами. [3] : 14 

Объявления и параметры [ править ]

Каждому объекту данных в S-алголе должно быть присвоено значение при его объявлении. Это соответствует вызову по передаче параметра по значению и исключает возможность использования неинициализированного значения. Фактически вызов по значению — единственный метод передачи параметров в S-алголе. Ссылочные и результирующие параметры отклоняются, что согласуется с запретом S-алгола на передачу l-значений . Структуры и векторы передаются как указатели на объекты, но это по-прежнему является вызовом по значению, поскольку поведение такое же, как и у значения, используемого в правой части присваивания. [3] : 15 

Каждое объявление имеет параметрический эквивалент. Необходимо указать все типы параметров процедуры. Для любой процедуры, передаваемой в качестве параметра, указан ее полный тип (в отличие от Паскаля), и то же самое справедливо и для структурного класса. [3] : 15 

Модель ввода-вывода [ править ]

S-алгол обеспечивает file тип данных для потоков ввода-вывода и несколько вариантов read и write определены для работы с базовыми типами. Ожидается, что отдельные реализации будут расширять эти простые возможности по мере необходимости. [3] : 15 

Конкретный синтаксис [ править ]

Языки АЛГОЛ критиковали за многословие. S-algol пытается улучшить эту ситуацию, предоставляя менее строгий синтаксис. [1] : 159  Это демонстрируется в основном в синтаксисе объявлений. Поскольку объявления переменных всегда должны включать начальное значение, тип не нужно указывать явно. [3] : 17 

Хотя можно было бы определить параметры процедуры и типы возвращаемых значений, исследовав, где вызывается процедура, S-algol требует указания типов параметров и возвращаемых значений. Это практическое решение, поскольку должно быть возможно понять процедуру, не изучая ее вызовы. [3] : 17 

Большинство АЛГОЛов требуют, чтобы все объявления предшествовали инструкциям в блоке. В S-алголе объявления могут быть смешаны с операторами, поскольку все должно быть объявлено до того, как оно будет использовано, и не существует перехода, который позволил бы пропустить объявление. [3] : 17 

См. также [ править ]

Ссылки [ править ]

  1. ^ Jump up to: Перейти обратно: а б с д и Коул, Эй Джей; Моррисон, Р. (1982), Введение в программирование с использованием S-алгола , Cambridge University Press, ISBN  978-0-521-25001-6
  2. ^ Jump up to: Перейти обратно: а б с д и Дэви, Энтони Дж.Т.; Рональд Моррисон (1981), Брайан Мик (редактор), Компиляция рекурсивного спуска , серия Эллиса Хорвуда о компьютерах и их приложениях, Чичестер, Западный Суссекс: Эллис Хорвуд, ISBN  978-0-470-27270-1
  3. ^ Jump up to: Перейти обратно: а б с д и ж г час я дж к л м н тот п д р с т в v В х и С аа аб и объявление Моррисон, Р. (1979). О разработке Алгола (доктор философии). Университет Сент-Эндрюс . стр. 1–70.
  4. ^ Jump up to: Перейти обратно: а б с Моррисон, Рон (1988) [1979], Справочное руководство по языку S-algol (PDF) (технический отчет CS/79/1), Файф: Университет Сент-Эндрюса, стр. 1–53, заархивировано из оригинала (PDF) 12 мая 2014 г.
  5. ^ Амман, Урс (1972), «Разработка компилятора», Proc. Межд. Симпозиум по вычислительной технике , Северная Голландия, стр. 93–99.
  6. ^ Вирт, Никлаус (апрель 1971 г.), «Разработка программы путем поэтапного усовершенствования», Communications of ACM , 14 (4): 221–227, doi : 10.1145/362575.362577 , hdl : 20.500.11850/80846 , S2CID   13214445
  7. ^ Бушелл, С.Дж.; Дирл, А; Браун, Алабама; Воан, Ф.А. (1994), «Использование C в качестве целевого языка компилятора для генерации собственного кода в постоянных системах» (pdf) , в Аткинсоне, член парламента; Майер, Д; Бензакен, В. (ред.), Proc. 6-й международный семинар по системам постоянных объектов (POS6), Тараскон, Франция , Семинары по вычислительной технике, Springer-Verlag, стр. 164–183.
  8. ^ Теннент, Р.Д. (1977), «Методы языкового проектирования, основанные на семантических принципах», Acta Informatica , 8 (2): 97–112, doi : 10.1007/bf00289243 , S2CID   31491993
  9. ^ Ландин, П.Дж. (март 1966 г.), «Следующие 700 языков программирования», Communications of ACM , 9 (3): 157–164, doi : 10.1145/365230.365257 , S2CID   13409665
  10. ^ Стрейчи, К. (1966), «На пути к формальной семантике», Языки формального описания языков , Северная Голландия, стр. 198–220.
  11. ^ Хоар, CAR (1975), «Рекурсивные структуры данных» , International Journal of Computer and System Sciences , 4 (2): 105–132, doi : 10.1007/bf00976239 , S2CID   24022888 , заархивировано из оригинала 26 сентября 2017 г.
  12. ^ Хоар, CAR (1972), «Примечание к заявлению for», BIT , 12 (3): 334–341, doi : 10.1007/bf01932305 , S2CID   61902610
  13. ^ Эдсгер Дейкстра (1973). Личное общение с Дональдом Кнутом , цитируемое в Кнут, Д. (1974), «Структурное программирование с переходом к операторам» (PDF) , Computing Surveys , 6 (4): 261–301, CiteSeerX   10.1.1.103.6084 , doi : 10.1145/356635.356640 , S2CID   207630080 , заархивировано из оригинал (PDF) от 23 октября 2013 г.

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=S-algol&oldid=1170458303"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: b5191d3f6b8bac0c43a0fbdc004d112c__1692063780
URL1:https://arc.ask3.ru/arc/aa/b5/2c/b5191d3f6b8bac0c43a0fbdc004d112c.html
Заголовок, (Title) документа по адресу, URL1:
S-algol - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)