АТС (язык программирования)

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) В статье чрезмерно много ссылок на первоисточники . Please improve this article by adding secondary or tertiary sources. Find sources: "ATS" programming language – news · newspapers · books · scholar · JSTOR (March 2018) (Learn how and when to remove this message) This article is written like a manual or guide. Please help rewrite this article and remove advice or instruction. (February 2020) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (September 2020) (Learn how and when to remove this message) (Learn how and when to remove this message)

АТС

Парадигмы	мультипарадигмальный : функциональный , императивный , объектно-ориентированный , параллельный , модульный
Семья	ML : Caml : OCaml : Зависимый ML
Разработано	Хунвэй Си
Разработчик	Бостонский университет
Впервые появился	2006 ; 18 лет назад (2006)
Стабильный релиз	ATS2-0.4.2 [1] / 14 ноября 2020 г. ; 3 года назад (2020-11-14)
Дисциплина набора текста	статический , зависимый
Лицензия	GPLv3
Расширения имени файла	.sats, .dats, .hats
Веб-сайт	www.ats-lang.org
Под влиянием
Зависимый ML , ML , OCaml , C++

В вычислительной технике ATS ( Applied Type System ) — это многопарадигмальный , универсальный , высокоуровневый , функциональный язык программирования . Это диалект языка программирования ML , разработанный Хунвэем Си для унификации компьютерного программирования с формальной спецификацией . ATS поддерживает объединение доказательства теорем с практическим программированием посредством использования расширенных систем типов . ^[2] Предыдущая версия The Computer Language Benchmarks Game продемонстрировала, что производительность ATS сопоставима с производительностью языков C и C++ . ^[3] Используя доказательство теорем и строгую проверку типов, компилятор может обнаружить и доказать, что его реализованные функции не подвержены ошибкам, таким как деление на ноль , утечки памяти , переполнение буфера и другие формы повреждения памяти , путем проверки арифметики указателей и подсчета ссылок перед компиляцией программы. Кроме того, используя интегрированную систему доказательства теорем ATS (ATS/LF), программист может использовать статические конструкции, которые переплетаются с оперативным кодом, чтобы доказать, что функция соответствует своей спецификации.

ATS состоит из статического компонента и динамического компонента. Статический компонент используется для обработки типов, тогда как динамический компонент используется для программ. Хотя ATS в основном опирается на функциональный язык вызова по значению в своей основе, он обладает способностью приспосабливаться к различным парадигмам программирования , таким как функциональная , императивная , объектно-ориентированная , параллельная и модульная .

По словам автора, ATS был вдохновлен конструктивной теорией типов Мартина-Лёфа , которая изначально была разработана с целью создания фундамента для математики. Си разработал ATS «в попытке объединить спецификацию и реализацию в единый язык программирования». ^[4]

ATS в основном происходит от языков ML и OCaml . Более ранний язык, Dependent ML , того же автора был включен в ATS.

Первая реализация, ATS/Proto (ATS0), была написана на OCaml и выпущена в 2006 году. Это была предварительная первая редакция ATS, которая больше не поддерживается. Год спустя была выпущена ATS/Geizella, первая реализация ATS1. Эта версия также была написана на OCaml и больше не используется активно. ^[5]

Вторая версия ATS1, ATS/Anairiats, выпущенная в 2008 году, стала важной вехой в развитии языка, поскольку язык мог самозагружаться . Эта версия была написана почти полностью на ATS1. Текущая версия, ATS/Postiats (ATS2), была выпущена в 2013 году. Как и ее предшественница, эта версия также почти полностью написана на ATS1. Последняя выпущенная версия — ATS2-0.4.2. ^[5]

По состоянию на 2024 год ^[update]ATS в основном используется для исследований; менее 200 репозиториев GitHub содержат код, написанный на ATS. Это намного меньше, чем у других функциональных языков, таких как OCaml и Standard ML, которые имеют более 16 000 и 3 000 репозиториев соответственно. Это, вероятно, связано с крутым обучением, связанным с ATS, которое присутствует из-за использования языком зависимой проверки типов и разрешения экземпляров шаблонов. Эти функции обычно требуют использования явных квантификаторов , которые требуют дальнейшего обучения. ^[6]

С 2024 года ^[update]ATS/Xanadu (ATS3) активно разрабатывается в ATS2 с надеждой на сокращение необходимого обучения за счет двух основных улучшений:

• Добавление дополнительного слоя в ATS2 для поддержки алгебраической проверки типов в стиле ML
• Метапрограммирование на основе типов, использующее только алгебраические типы ^[6]

С этими улучшениями Си надеется, что ATS станет гораздо более доступным и простым в изучении. Основная цель ATS3 — превратить ATS из языка, используемого в основном для исследований, в язык, достаточно сильный для крупномасштабной промышленной разработки программного обеспечения. ^[5]

Основное внимание ATS уделяется поддержке формальной проверки посредством автоматизированного доказательства теорем в сочетании с практическим программированием. ^[2] Доказательство теорем может доказать, например, что реализованная функция не приводит к утечкам памяти. Оно также может предотвратить другие ошибки, которые в противном случае могли бы быть обнаружены только во время тестирования. Оно включает в себя систему, похожую на системы помощников по доказательству , которые обычно нацелены только на проверку математических доказательств — за исключением того, что ATS использует эту возможность для доказательства того, что реализации его функций работают правильно и выдают ожидаемый результат.

В качестве простого примера, в функции, использующей деление, программист может доказать, что делитель никогда не будет равен нулю, предотвращая ошибку деления на ноль . Допустим, делитель 'X' был вычислен как 5 раз больше длины списка 'A'. Можно доказать, что в случае непустого списка 'X' не равен нулю, поскольку 'X' является произведением двух ненулевых чисел (5 и длины 'A'). Более практичным примером было бы доказательство с помощью подсчета ссылок того, что счетчик сохранения в выделенном блоке памяти подсчитывается правильно для каждого указателя. Тогда можно знать и буквально доказать, что объект не будет освобожден преждевременно, и что утечек памяти не произойдет.

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

В ATS доказательства отделены от реализации, поэтому при желании можно реализовать функцию, не доказывая ее.

По мнению автора, эффективность ATS ^[7] во многом обусловлена ​​способом представления данных в языке и оптимизацией хвостовых вызовов (которые, как правило, важны для эффективности функциональных языков). Данные могут храниться в плоском или неупакованном представлении, а не в упакованном.

datapropвыражает предикаты как алгебраические типы .

Предикаты в псевдокоде несколько похожи на источник ATS (допустимый источник ATS см. ниже):

ФАКТ(n, r) тогда и только тогда, когда факт(n) = r MUL(n, m, prod) тогда и только тогда, когда n * m = prod  ФАКТ(n, r) = ФАКТ(0, 1) | FACT(n, r) тогда и только тогда, когда FACT(n-1, r1) и MUL(n, r1, r) // для n > 0  // выражает факт(n) = r тогда и только тогда r = n * r1 и r1 = факт(n-1)

В коде ATS:

 dataprop FACT ( int , int ) = | FACTbas ( 0 , 1 ) // базовый случай: FACT(0, 1) | { n : int | n > 0 } { r , r1 : int } // индуктивный случай FACTind ( n , r ) of ( FACT ( n -1 , r1 ), MUL ( n , r1 , r ))                            

где ФАКТ (int, int) — тип доказательства

Нехвостовой рекурсивный факториал с утверждением или « теоремой », доказывающимся посредством конструкции dataprop .

Оценка fact1(n-1)возвращает пару (proof_n_minus_1 | result_of_n_minus_1), которая используется при вычислении fact1(n). Доказательства выражают предикаты предложения.

 [ ФАКТ  ( n ,  r )]  подразумевает  [ факт  ( n )  =  r ]  [ МУЛ  ( n ,  m ,  prod )]  подразумевает  [ n  *  m  =  prod ] FACT  ( 0 ,  1 )  FACT  ( n ,  r )  тогда и только тогда  FACT  ( n - 1 ,  r1 )  и  MUL  ( n ,  r1 ,  r )  для всех  n  >  0

Чтобы запомнить:

{...} универсальная квантификация[...] экзистенциальная квантификация(... | ...) (доказательство | ценность)@(...) плоский кортеж или кортеж параметров вариативной функции.<...>. метрика завершения [8]

# включить  "share/atspre_staload.hats"dataprop  FACT  ( int ,  int )  =  |  FACTbas  ( 0 ,  1 )  of  ()  //  базовый  случай  |  { n : nat }{ r : int }  //  индуктивный  случай  FACTind  ( n + 1 ,  ( n + 1 )* r )  of  ( FACT  ( n ,  r ))(* обратите внимание, что int(x) , также int x, является однозначным типом значения int x.Сигнатура функции ниже гласит: forall n:nat, exist r:int where fact( num: int(n)) returns (FACT (n, r) | int(r)) *)забавный  факт { n : nat }  .< n >.  ( n :  int  ( n ))  :  [ r : int ]  ( FACT  ( n ,  r )  |  int ( r ))  = (  ifcase  |  n  >  0  =>  (( FACTind ( pf1 )  |  n  *  r1 ))  где  {  val  ( pf1  |  r1 )  =  fact  ( n - 1 )  }  |  _ (*else*)  =>  ( FACTbas ()  |  1 ) )

реализовать  main0  ( argc ,  argv )  = {  val  ()  =  if  ( argc  !=  2 )  then  prerrln !  ( "Использование: " ,  argv [ 0 ],  " <integer>" ) val  ()  =  assert  ( argc  >=  2 )  val  n0  =  g0string2int  ( argv [ 1 ])  val  n0  =  g1ofg0  ( n0 )  val  ()  =  assert  ( n0  >=  0 )  val  (_ (*pf*)  |  res )  =  fact  ( n0 ) val  ( (*void*) )  =  println !  ( "fact(" ,  n0 ,  ") = " ,  res ) }

Все это можно добавить в один файл и скомпилировать следующим образом. Компиляция должна работать с различными компиляторами C back-end, например, GNU Compiler Collection (gcc). Сборка мусора не используется, если явно не указано иное с помощью -D_ATS_GCATS) ^[9]

$ patscc  fact1.dats  -o  факт1 $ ./fact1 4 

компилируется и дает ожидаемый результат

• бул (истина, ложь)
• int (литералы: 255, 0377, 0xFF), унарный минус как ~ (как в ML )
• двойной
• символ 'a'
• строка "abc"

• префикс @ или none означает прямое, плоское или неупакованное распределение

   val x : @ ( int , char ) = @ ( 15 , 'c' ) // x.0 = 15 ; x.1 = 'c' val @ ( a , b ) = x // сопоставление с образцом, a = 15, b = 'c' val x = @ { first = 15 , second = 'c' } // x.first = 15 val @ { first = a , second = b } = x // a = 15, b = 'c' val @ { second = b , ...} = x // с пропуском, b = 'c'                                

• префикс ' означает косвенное или блочное распределение

   val x : ' ( int , char ) = ' ( 15 , ' c' ) // x.0 = 15 ; x.1 = ' c' val ' ( a , b ) = x // a = 15, b = ' c' val x = ' { first = 15 , second = ' c' } // x.first = 15 val ' { first = a , second = b } = x // a = 15, b = ' c' val ' { second = b , ...} = x // b = ' c'                                

• особенный

  При |использовании разделителя некоторые функции возвращают обернутое значение результата с оценкой предикатов.

val (predicate_proofs | values) = myfunct params

{...} универсальная квантификация[...] экзистенциальная квантификация(...) выражение в скобках или кортеж(... | ...) (доказательства | значения)

.<...>. метрика завершения@(...) плоский кортеж или кортеж параметров вариативной функции (см. пример printf )@[byte][BUFLEN] тип массива значений BUFLEN типа byte [10]@[byte][BUFLEN]() экземпляр массиваМассив @[byte][BUFLEN](0) инициализирован значением 0

сортировать:домен

 sortdef nat = { a : int | a >= 0 } // из прелюдии: ∀ ''a'' ∈ int ...           typedef String = [ a : nat ] string ( a ) // [..]: ∃ ''a'' ∈ nat ...     

тип (как сортировать)

общая сортировка для элементов с длиной слова указателя, для использования в полиморфных функциях с параметризацией типа. Также "boxed types" ^[11]

 // {..}: ∀ a,b ∈ тип ... забава { a , b : тип } swap_type_type ( xy : @ ( a , b )): @ ( b , a ) = ( xy .1 , xy .0 )           

тип

Линейная версия предыдущего типа с абстрактной длиной. Также неупакованные типы. ^[11]

тип представления

доменный класс, подобный типу с представлением (ассоциация с памятью)

viewt@ype

Линейная версия viewtype с абстрактной длиной. Она надмножествует viewtype

вид

Отношение типа и расположения в памяти. Инфикс @ является его наиболее распространенным конструктором

T @ Lутверждает, что в точке L существует представление типа T

 fun  { a : t @ ype }  ptr_get0  { l : addr }  ( pf :  a  @  l  |  p :  ptr  l ):  @( a  @  l  |  a )  fun  { a : t @ ype }  ptr_set0  { l : addr }  ( pf :  a ?  @  l  |  p :  ptr  l ,  x :  a ):  @( a  @  l  |  void )

тип ptr_get0 (T)— ∀ l : addr . ( T @ l | ptr( l ) ) -> ( T @ l | T) // see manual, section 7.1. Safe Memory Access through Pointers^[12]

 viewdef  array_v  ( a : viewt @ ype ,  n : int ,  l :  addr )  =  @[ a ][ n ]  @  l

Т?

возможно неинициализированный тип

как в случае+ , val+ , type+ , viewtype+ , ...

• с суффиксом '+' компилятор выдает ошибку в случае неисчерпывающих альтернатив
• без суффикса компилятор выдает предупреждение
• с суффиксом «-» избегает контроля полноты

staload "foo.sats" // foo.sats загружается и затем открывается в текущем пространстве имен staload F = "foo.sats" // для использования идентификаторов, квалифицированных как $F.bar dynload "foo.dats" // загружается динамически во время выполнения

Представления данных часто объявляются кодирующими рекурсивно определенные отношения на линейных ресурсах. ^[13]

 dataview  array_v  ( a :  viewt @ ype +,  int ,  addr )  =  |  { l :  addr }  array_v_none  ( a ,  0 ,  l )  |  { n :  nat }  { l :  addr }  array_v_some  ( a ,  n + 1 ,  l )  of  ( a  @  l ,  array_v  ( a ,  n ,  l + sizeofa  ) )

Типы данных ^[14]

тип данных рабочий день = Пн | Вт | Ср | Чт | Пт

списки

тип данных list0 (a:t@ype) = list0_cons (a) из (a, list0 a) | list0_nil (a)

Тип представления данных похож на тип данных, но он линейный. С типом представления данных программисту разрешено явно освобождать (или отменять) безопасным способом память, используемую для хранения конструкторов, связанных с типом представления данных. ^[15]

локальные переменные

var res: int с pf_res = 1 // вводит pf_res как псевдоним представления @ (res)

при выделении стекового массива:

 #define BUFLEN 10 var ! p_buf с pf_buf = @ [ байт ][ BUFLEN ]( 0 ) // pf_buf = @[байт][BUFLEN](0) @ p_buf       

^[16]

См. объявления val и var ^[17]

В Wikibooks есть книга по теме: ATS: Программирование с доказательством теорем

• Официальный сайт
• Язык программирования ATS Архивировано 2014-12-05 в Wayback Machine Документация для ATS2
• Язык программирования ATS Старая документация для ATS1
• Черновик руководства (устарел). Некоторые примеры относятся к функциям или процедурам, отсутствующим в выпуске (Anairiats-0.1.6) (например: перегрузка печати для strbuf и использование ее примеров массивов приводит к ошибкам типа «использование подписки на массив не поддерживается»).
• ATS для программистов машинного обучения
• Примеры обучения и краткие примеры использования ATS