LINUX.ORG.RU

статьи по системам типов?

 , ,


0

7

Хочу какой-нить ликбез написанный простыми словами про существующие системы типов. А то я вот мучаюсь что выбрать для своего яп (википедию читал).

Пока решил идти от простого: три базовых иммутабельных типа (str, int, double), массив однородных данных и ADT. Я не уверен что мне хочется сделать всё это совершенно иммутабельным, но хочу чтобы передача параметров функции была по значению. Т.е. чтобы in-place модификация вложенных структур данных работала, но при этом это никак не влияло на другие функции которые тоже работают с этими данными. Это позволит избежать горождения огорода с хаскелевыми линзами. Есть ли у такого подхода научное название? И как бы это в коде реализовать?

Пока на ум приходит версионность данных. Типа, мы делаем x= 0; x++ и у нас x уже равен 1, но это не тот x что был изначально. (по-моему, меня на это натолкнули статьи про llvm и SSA).

PS вопросов у меня много, я лучше разобью на несколько постов.

PPS всем добра :)

★★★★★
Ответ на: комментарий от true_admin

лишь бы до редхета не добиралось:)

pylin ★★★★★
()
Ответ на: комментарий от true_admin

По сабжу, вроде классикой считают этот учебник: Типы в языках программирования Б. Пирса, если в русском переводе.

pylin ★★★★★
()
Ответ на: комментарий от pylin

Плюсую данную книжку. Еще можно посмотреть мануал для какого-нибудь ЯП с годной системой типов. Standard ML или ATS (если хочется узнать что-то о зависимых типах и линейности).

buddhist ★★★★★
()

чтобы in-place модификация вложенных структур данных работала, но при этом это никак не влияло на другие функции которые тоже работают с этими данными

Не совсем понял, что ты хочешь

buddhist ★★★★★
()

Хочу какой-нить ликбез написанный простыми словами про существующие системы типов

Простыми словами - нет, но Википедия послужит хорошей точкой входа. Еще классика от Карделли: http://lucacardelli.name/Papers/OnUnderstanding.pdf

Пока на ум приходит версионность данных

Все в машину...

tailgunner ★★★★★
()
Ответ на: комментарий от buddhist

Именно так и делаю :). Конкретно, мануал по ocaml и сейчас читаю про hope.

На счёт зависимых типов. Читал статью по agda. Но т.к. материала слишком много то я для себя решил что зависимые типы это когда ты, например, принципиально не можешь выйти за пределы границы массива т.к. ЯП заставит тебя сделать constrains на значения переменной которая используется для индексирования. На сколько примитивно моё видение зависимых типов?

true_admin ★★★★★
() автор топика
Ответ на: комментарий от buddhist

Не совсем понял, что ты хочешь

CoW он хочет

mashina ★★★★★
()

str, int, double

int и double давно пора объединить, если у тебя язык высокого уровня

чтобы in-place модификация вложенных структур данных работала
но при этом это никак не влияло на другие функции которые тоже работают с этими данными

зависит от этих функций.

Пока на ум приходит версионность данных

лучше сделай ис(з?)коробочную transactional memory как базовый элемент языка

MyTrooName ★★★★★
()
Последнее исправление: MyTrooName (всего исправлений: 1)
Ответ на: комментарий от buddhist

Допустим, у нас есть массив [1,2,3]. Мы его передаём в другой поток исполнения который работает паралельно. Теперь я меняю некоторый элемент массива. Я не хочу чтобы другой поток увидел эти изменения. Пусть он работает со своей локальной «копией».

true_admin ★★★★★
() автор топика
Ответ на: комментарий от true_admin

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

buddhist ★★★★★
()
Ответ на: комментарий от true_admin

Да, уже понял. Ну тогда либо линзы, либо простое навязывание иммутабельного стиля, как это любят в схемке, к примеру.

С copy-on-write может вылезти куча самых разных проблем, но попробовать можно

buddhist ★★★★★
()
Последнее исправление: buddhist (всего исправлений: 1)
Ответ на: комментарий от MyTrooName

int и double давно пора объединить

Ой, не, не надо :) В int можно, например, играться отдельными битиками, делать сдвиги и использовать как индекс массива. Индексировать по double... Потом, на больших значениях double становится неточным даже для целых чисел. Попробуй перевести 99999999999999999 в double и обратно.

transactional memory как базовый элемент языка

Моя давняя мечта, но у меня даже проца нет который это поддерживает.

true_admin ★★★★★
() автор топика
Ответ на: комментарий от MyTrooName

int и double давно пора объединить, если у тебя язык высокого уровня

расскажи как взять 1.0001(1) элемент из массива. И как это будет связанно с «уровнем» яп.

mashina ★★★★★
()
Ответ на: комментарий от true_admin

А что так? :(

SSA - это внутреннее представление кода. Предлагать писать это человеку - кхм... неразумно.

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

tailgunner ★★★★★
()
Ответ на: комментарий от buddhist

С copy-on-write может вылезти куча самых разных проблем, но попробовать можно

Понял, лучше отложу на отдалённое будущее.

Спасибо за помощь.

true_admin ★★★★★
() автор топика
Ответ на: комментарий от true_admin

есть софтварные эмуляции, в том же хаскеле.

возьми какое-нить STM API и пиши на базе него

MyTrooName ★★★★★
()
Ответ на: комментарий от true_admin

Моя давняя мечта, но у меня даже проца нет который это поддерживает

Это же просто абстракция, которая может быть реализована и на обычной памяти.

К слову об интересных манипуляциях с памятью, советую посмотреть на region inference в MLKit.

buddhist ★★★★★
()
Ответ на: комментарий от true_admin

В int можно, например, играться отдельными битиками

не очень-то высокоуровневое действие. в ЯВУ ненужно

Индексировать по double

индексируй. в чем проблема?

на больших значениях double

для этих целей все равно должен быть BigInteger и BigDecimal

MyTrooName ★★★★★
()
Ответ на: комментарий от tailgunner

SSA - это внутреннее представление кода.

Всё верно, человек не должен над этим вообще думать.

ты хочешь линейные типы или еще какую-то экзотику, но зачем?

Чтобы сделать ЯП лучше :). Возможно, я плохо объяснил зачем это нужно. Это нужно для бОльшей потокобезопасности (статьи по системам типов? (комментарий))

зачем тебе вообще свой язык...

На то две причины:

1) помогает отвлечься на выходных от работы и переключиться на что-то другое.

2) Проснулся азарт. Хочу довести дело до конца.

ЗЫ вилдродень таки зарелизил свою игру или нет? Или зарелизил, а вышла какашка?

true_admin ★★★★★
() автор топика
Ответ на: комментарий от MyTrooName

для этих целей все равно должен быть BigInteger и BigDecimal

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

true_admin ★★★★★
() автор топика
Ответ на: комментарий от true_admin

тогда и double замени на decimal и сделай резиновым, с заданной точностью

а еще лучше на float с заданным числом значимых цифр и основанием системы счисления, чтобы избежать ошибок округления :) мантисса будет массивом цифр, показатель - твой резиновый int. а в частных случаях можно использовать и машинные типы (2-ичная сс, 23 или 52 цифры) до первого overflow показателя.

MyTrooName ★★★★★
()
Последнее исправление: MyTrooName (всего исправлений: 3)
Ответ на: комментарий от true_admin

Возможно, я плохо объяснил зачем это нужно. Это нужно для бОльшей потокобезопасности (статьи по системам типов? (комментарий))

Единственная приличная потокобезопасность - это CSP. Если Хоар (другой Хоар) прав, для этого хватит линейных типов.

Проснулся азарт. Хочу довести дело до конца.

«От ненужных побед остается усталость» (ц)

И спроектировать юзабельный ЯП очень трудно.

ЗЫ вилдродень таки зарелизил свою игру или нет?

Он ее не сделал.

tailgunner ★★★★★
()
Последнее исправление: tailgunner (всего исправлений: 1)
Ответ на: комментарий от true_admin

Индексировать по double

насчет индексации я таки погорячился, для Haskel-подобного языка целочисленные типы однозначно лучше оставить. но тогда не нужно останавливаться на int, а сделать еще и uint. возможно

MyTrooName ★★★★★
()
Последнее исправление: MyTrooName (всего исправлений: 1)

Читай про систему типов Rust. Там можно мутировать при желании данные, но мутирующая ссылка может быть только одна. Соответственно проблем с разделяемым состоянием нет.

dizza ★★★★★
()
Ответ на: комментарий от buddhist

Это же просто абстракция, которая может быть реализована и на обычной памяти.

Кишка у меня тонка :). Я пару лет назад интересовался этим вопросом, мне результаты не понравились. PyPy пытается такое сделать, по состоянию на год назад получилось не очень.

Я не помню что я тогда накопал, но для себя решил что время STM придёт только когда это будет в железе, на уровне кода это слишком сложно. К сожалению, если не путаю, последнее поколение интеловых процов идёт с отключённым STM из-за бага. Собстно, вот: http://techreport.com/news/26911/errata-prompts-intel-to-disable-tsx-in-haswe...

region inference

Ееее, очень хочу поближе присмотреться к этой фишке. Если не ошибаюсь, это есть в rust.

true_admin ★★★★★
() автор топика

Пока на ум приходит версионность данных. Типа, мы делаем x= 0; x++ и у нас x уже равен 1, но это не тот x что был изначально

Если я правильно понял, то в Clojure есть коллекции с подобными свойствами: http://clojure.org/data_structures#Data Structures-Collections. И более общая ифа в вики: http://en.wikipedia.org/wiki/Persistent_data_structure .

hatefu1_dead
()

Меня как-то давно показались интересными замечания Дейта о типах в «Введении в СУБД». Он там писал что в СУБД для некоторых типов очень желательно держать и физическую размерность, множества это важный тип и т.п. Непонятно насколько это пригодилось бы в ЯП общего назначения, но вот с принудительными проверками размерностей и единиц измерения наверное можно было бы избежать некоторых факапов

версионность данных

Это что-то типа MVCC в тех же СУБД?

Deleted
()
Ответ на: комментарий от Deleted

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

Я согласен и это сейчас решается с двух сторон.

1) ADT. Это канонический путь.

2) Планирую разрешить свои постфиксы к данным. Конкретный синтаксис пока не придумал. Можно как-то так:

# введёт тип данны время. Это часы или минуты
data Time = Hours Int | Minutes Int

# укажем что, скажем, 1h это (Hours 1)
::postfix h -> Hours
::postfix m -> Minutes

# зададим функцию для сложения
(+) left:Time, right:Time ->
    ...

# вот теперь их можно складывать
time = 1h + 2m

В общем, это пока не проработано потому что я не умею в функторы.

true_admin ★★★★★
() автор топика
Ответ на: комментарий от Deleted

Это что-то типа MVCC в тех же СУБД?

Про версионность это я наобум выпалил. Нужен был CoW и я предположил что его можно достичь через версионность (как именно — хз). Я думаю тут я фигню сморозил.

true_admin ★★★★★
() автор топика
Ответ на: комментарий от pylin

Как теоретическая задача «для себя» — неплохой способ размять голову. Лишь бы в продакшен оно не выпускалось!

comp00 ★★★★
()
Ответ на: комментарий от true_admin

печатать неудобно очень) оба знака одним и тем же пальцем набираю

MyTrooName ★★★★★
()

совершенно иммутабельным

модификация

Э-э-э... чего?

То есть, я, в принципе, могу понять это как «функция может менять свои параметры, но не может менять более ничего, и изменение ею своих параметров ни на что более не влияет», но смысл подобного от меня ускользает.

Miguel ★★★★★
()

Пока решил идти от простого: три базовых иммутабельных типа (str, int, double), массив однородных данных и ADT.

три базовых иммутабельных типа

Тогда делай уж 2: «А когда на кухне дежурит Гитлер, Сталин ест серпом и молотом.»(ц)

Napilnik ★★★★★
()
Ответ на: комментарий от MyTrooName

int и double давно пора объединить, если у тебя язык высокого уровня

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

Размер типа int не определяется стандартом, а зависит от компьютера и компилятора. Для 16-разрядного процессора под величины этого типа отводится 2 байта, для 32-разрядного – 4 байта.
Для точного определения количества байт следует написать тестовую программу и включить в нее операцию:

s=sizeof(int);
Napilnik ★★★★★
()

Классика: Пирс TAPL/ATTAPL + любая книжка по SML.

Ну и более навороченные статьи тут.

Алсо годная библиотечка.

ymn ★★★★★
()
Ответ на: комментарий от true_admin

приведи ещё один

функция, гарантированно принимающая (возвращающая) сортированный массив. taint check. функция, гарантированно вызываемая в синхронизированном контексте. генератор, возвращающий n значений без коллизий

с проверкой гарантий во время компиляции

jtootf ★★★★★
()
Ответ на: комментарий от true_admin

чем бы дитя не тешилось...

"...лишь бы замуШЪ не хотело..."

Да чо, изобретай. Я, вот, тоже изобретаю «в стол» разные виды велосипедов =)

Deleted
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.