Тьюринг-полон ли данный язык

[arseniiv]

Circiter в сообщении #479814 писал(а):

Как его вычислять и тем более как эффективно генерировать соответствующие цепочки -- мне пока непонятно...

И мне (посленее, а в первом вроде разности последовательности были вида $2^n$ или подобного (а может, и $2^{2^n}$); а та тема даже не помню как называлась!).

Circiter в сообщении #479814 писал(а):

2arseniiv
А как вы собирались назвать свой язык? Вот я там выше файлик с воображаемым исходником от-фонаря назвал banach_tarski.s1, так может быть в качестве кодового рабочего названия пока S1 сгодится? :)

Сначала, до создания этой темы, хотел назвать madh (mad + math), а потом [S]. Так что расширение .s1 вполне соответствует!

-- Сб сен 03, 2011 00:48:18 --

Ай, совсем наоборот! Частичные суммы (начиная с $n = 1$) образуют последовательность $2^{2^{n - 1}}$! Это уж точно.

[Lukin]

arseniiv в сообщении #479829 писал(а):

а та тема даже не помню как называлась!).

Нашел в архиве Вашей переписки через поиск, ключ "множеств* ранаг*":

arseniiv в сообщении #345959 писал(а):

Вывел рекуррентную формулу для $d_n$:

$$d_{n + 1} = \left( {2^{d_n} - 1} \right)2^{\sum_{i = 0}^{n - 1} {d_i}}$$

Надеюсь, я всё учёл и она верна. Осталось найти нерекуррентную, если такая имеет достаточно простой вид...
-- Сб авг 21, 2010 18:26:37 --
Ага, вот что накопалось:
http://mathworld.wolfram.com/Rank.html
A038081

Почти

Circiter в сообщении #479814 писал(а):

$$N(n+1)=\big(2^{N(n)}-1\big)\cdot\prod_{i=0}^{n-1}2^{N(i)}.$$

Похоже, что это вполне соответствует формуле для $S_n$...

[Circiter]

2arseniiv

Цитата:

а потом [S]

Скобки в названии -- оригинально. Но. Во-первых, расширение .s традиционно занято linux-ассемблером, а расширение .[s] плохо дружит с командной строкой (и даже с bb-тегами на этом форуме :) ). Во-вторых, язык S уже существует, и не в виде поделки, а в виде продукта из Bell labs.; причем квадратные скобки у многих дизайнеров традиционно используются в логотипах именно вокруг названия фирмы/продукта. Так что надо что-нибудь другое наверное придумать (мое S1 тоже мало пригодно, ибо тот же S последних версий тоже назывался S3, а потом и S4; упоминаний S1 в интернете нет, но мало ли...).

(ну со скобками прямо в текстовом названии, ещё раз повторюсь, это смело).

2Lukin
Формулы идентичны. У дураков мысли сходятся. :) Кстати, как теперь выяснилось, проще искать количество множеств разных рангов, от нулевого до $n$. Оно просто равно $\uparrow^{n-1} 2$, где $\uparrow$ - операция возведения в степень. Может быть и генерировать их все вместе проще?

-- Сб сен 03, 2011 03:15:54 --

По той ссылке в OEIS лежит такой код для mathematica:

f[n_]:=2^n; p=0; lst={p}; Do[p=f[p]; AppendTo[lst, p], {n, 6}]; lst [From Vladimir Orlovsky (4vladimir(AT)gmail.com), Jul 03 2009]

Он генерирует последовательность, разности которой дают обсуждаемую N(i), а она, как оказалось, слишком страшная: $1,\ 1,\ 2,\ 12,\ 65520,\ 2^{65536}-65536,\ \ldots$ Ну её, подальше. :) Таким образом, добавление поддержки бесконечных множеств в S1 является насущной необходимостью, призванной оградить от возникновения вопросов вроде "сколько всего существует множеств данного ранга". :)

[Circiter]

2arseniiv
Так что, вы, как архитектор S1, думаете о развитии декларативности?

Вот например можно пофантазировать на тему вашей задачки о булеане:

powerset(set) {return [S where S subset set];}

test()
{
    myset=[1, 5..41];
    ps=powerset(myset);
    _assert([] in ps);
    _assert(myset in ps);
    _assert(sizeof ps > sizeof myset); // Due to Cantor's diagonal argument.
    _assert(sizeof ps == 2^ sizeof myset);
}

Вообще, роль вашего select'а может выполнять операция in, используемая в декларативной манере, т.е. вместо while(s){a=select(s); use(a);} можно писать что-то вроде use(a) where a in s; или же ввести полее привычный "квантор" forall специально для циклов... циклов, могущих обрабатывать даже бесконечные множества. В общем тут есть над чем подумать.

-- Сб сен 03, 2011 20:14:36 --

Попробую переделать setl-пример генерации простых чисел под C-образный синтаксис S1, заодно посмотрим, можно ли использовать генераторы:

gen_primes()
{
    primes=[];
    p=1;

    while(++p)
        if(!(t in primes) where !(t%p))
        {
            primes+=t;
            yield t;
        }
}

test()
{
    primes=[x where x=gen_primes()];
    print(primes[100..1000]);
}

-- Сб сен 03, 2011 20:17:46 --

Не, дикий велосипед какой-то... :)

[Circiter]

Ещё мыслишки. Как быть с результатом выполнения powerset(Z)? Вот это настоящая эзотерика. :) Я имею ввиду _assert(sizeof powerset(Z) == sizeof R).

Насчет вашей nextSet(...). Кажется, можно окончательно скрыть намеки на упорядоченность множеств если убрать из этой функции аргумент, а саму её переименовать в random(). :)

Пример печати множества:

highlight(set)
{
    print("[");
    while(set) // whilene?
    {
        item=random();
        if(item in set) // ifne(set*[item])?
        {
            highlight(item);
            set=set*![item]; // set-=[item]?
        }
    }
    print("]");
}

[arseniiv]

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

Я предлагаю всё-таки представлять бесконечные множества специальными объектами, показывающими, как они строятся из других конечных и «атомных» бесконечных. Ещё в таком случае, всё-таки, наверно лучше отойти от только одних множеств и ввести числа — целые, рациональные (при этом логично использовать библиотеку для чисел произвольной длины) и действительные с плавающей точкой (тут, думаю, усложнения только повредят — мы же не собираемя строить ещё одну «всемогущую» CAS), а также кортежи, а то представление их множествами не очень удобно.

Есть интересный вопрос: пусть мы имеем какое-нибудь множество, заданное в форме выражения. Как определить, конечно ли оно? Если мы начнём перечислять его элементы, мы можем не остановиться, и о бесконечности множества не узнаем. Хотя вопрос выглядит глупо. Если мы рассмотрим каждую из дозволенных в языке операций над множествами, мы увидим всё и так. Например, если в объединении участвует бесконечное множество, то результат бесконечен; если в пересечении участвует конечное, то результат конечен; и прочее.

Язык можно сделать поддерживающим уникод в названиях операций (но тут я не буду его использовать).

Хочу посмотреть, что может получиться. Допустим, реализован REPL, и мы пишем туда всякие выражения. Синтаксис в этом воображаемом примере не буду ограничивать, а то неудобно будет понимать.

>  R1 := { x : x in R && x >= 0 } // тут лучше бы сделать синтаксис чуть-чуть по-другому: должно быть обязательное указание множеств, из которых берутся все переменные в левой части такого конструктора, а анализировать выражение справа для их поиска не всегда приятно
>> R * { t0 : t0 >= 0 }
>  R2 := { -x : x in R1 }
>> R * { t0 : t0 <= 0 } // тут нужно очень много повычислять, по-моему
>  R1 + R2
>> R
>  R1 * R2
>> { 0 }
>  R1 ~ R2
>> R - { 0 }
>  { x * y : x in R1 && y in R2 }
>> R * { t0 : t0 <= 0 } // кстати, можно сделать перед печатью результата поиск в таблице идентификаторов и отобразить это как "R2"
>  { 0 .. 8 } in Z
>> true
>  { (x, y) : x in N && y in N && x + 1 = y }
>> <infinite set>
>  { (x, x + 1) : x in N }
>> <infinite set>
>  %1 = %2
>> true // не понимаю, как прийти к этому

Мне бы хотелось рассмотреть побольше примеров, чтобы понять, насколько далеко идти, чтобы не застрять с этим языком навеки. Конструкции какой степени чоевидности он должен вычислять, а какой уже нет.

Circiter, какое будет ваше отношение к этому сообщению? Если понравится, не придумаете ли что-нибудь своё в пример?

-- Вс сен 04, 2011 02:19:16 --

(Оффтоп)

Если не возражаете, приведу здесь тот синтаксис, который имел в виду под Tcl-видным (давайте назовём его «скучным» — он простой для анализа программой, но записывать в нём для человека сложные вещи не столь удобно) в EBNF.

Программа   =  Блок
Блок        =  [ { Выражение0 ";" } Выражение0 ]
Выражение0  =  Выражение
.           =  Операция { Выражение }
Выражение   =  "{" Блок "}"
.           =  "(" Операция { Выражение } ")"
.           =  // тут можно ещё ввести конструкторы списков и множеств, но это уже синтаксический сахар похуже блоков
.           =  Число | Строка | Идентификатор

Т. е., если аргументом выражения является другое выражение, а не атомное значение или блок, его надо поместить в скобки, но выражения, из которых состоит блок, в скобки помещать не нужно. Такое осложнение синтаксиса только из-за поддержки блоков нормального вида.

Точки в началах строк поставлены оттого, что парсер [code] почему-то с ними вытворяет невесть что: то ест, а то уменьшает количество неясным образом.

[Circiter]

2arseniiv

Цитата:

А чтобы не мучиться с синтаксисом

Не, ваша первоначальная идея очень хороша. Очень не хватает именно такого императивного языка с такими возможностями. А то всякие хаскели да лиспы кругом. :) Да, парсер будет сложнее; ну и что, прототип компилятора все-равно будет занимать не больше 500-2000 строчек кода, не страшно.

Насчет tcl все внимательно прочитал, но поддержать здесь тоже вас не могу. Да, tcl -- замечательный язык, но в своей области. Я его вообще не более чем языком пакетных сценариев считаю (чем он впрочем и является). И, как я понимаю, без особых ухищрений придется использовать префиксную запись в выражениях; зачем такие ограничения (кои в тоже время вполне естественны для командно-ориентированного языка вроде tcl'а и --- но уже для случая дуальной, постфиксной нотации --- стек-ориентированного вроде форта)?

Думаю, не стоит бояться придумывания нового необычного синтаксиса. Это же все-равно эксперимент, деньги-то не плотют. :)

Цитата:

Ещё в таком случае, всё-таки, наверно лучше отойти от только одних множеств и ввести числа — целые, рациональные (при этом логично использовать библиотеку для чисел произвольной длины)

Пока стоит попробовать все-таки все выражать через множества. Даже числа. Согласитесь, так красивше.

Цитата:

и действительные с плавающей точкой (тут, думаю, усложнения только повредят — мы же не собираемя строить ещё одну «всемогущую» CAS), а также кортежи, а то представление их множествами не очень удобно.

Действительные пока, имхо, там вообще ни к чему, а кортежи уж пусть будут пока множествами. Если нужна упорядоченность, просто положите каждый элемент множества в двуэлементное множество [номер, [элемент]]. А вот лексические кортежи пригодятся, я имею ввиду в первую очередь конструкцию множественного присваивания a, b = c, d, что эквивалентно a=c; b=d;. В довесок получается, что формальные параметры функции -- тоже лексический кортеж. Но тут надо все-таки подумать. То ли можно обойтись функцией tuple или pair, позволяющей упорядочивать множество, помещая данные в кортеж-список, то ли действительно стоит ввести нотацию с перечислением в круглых скобках + неплохо бы было все это как-то хитро скомпоновать с лексическими кортежами, C'шными вычислительными последовательностями --- я имею ввиду оператор ',' --- и массивами (чем массив не кортеж? что если кортежи индексировать также как и массивы, т.е. через a[i]?) ... То есть, хотелось бы достичь определенной синтаксической однородности...

Кортежи ещё можно заменить такой несколько экзотичной, чуть ли не ООП'шной конструкцией. Когда нам нужен кортеж с фиксированным числом элементов, да ещё и с удобным доступом по имени, т.е., фактически C'шная struct мы создаем функцию с пустым телом, e.g. func(param1, param2){}, вызываем её с определенными фактическими параметрами, e.g. func(5, []), а результат передаем туда, где ожидается кортеж. Например, a=func(5, []). Теперь мы можем обращаться к элементам кортежа таким способом: a.param1. А присваивания b=a.param1; c=a.param2; можно тогда кратко записать как b, c = a;.

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

Ниже я парочку примеров S1-кода попытался привести. Так вот там я использую обычную (...) нотацию для кортежей (подразумевается, что котрежи можно порождать конструкторами, аналогичными конструкторам множеств, правда на этом пути есть серьезные синтаксические проблемы). Возможно, стоит считать литералы кортежей именно синтаксическим сахаром, на самом деле создающим множество: (a, b, ...) $\to$ [[1, [a]], [2, [b]], ...]. Как вам?

Ещё фичи: Думаю не помешают именованные фактические параметры функций, что-то вроде f(param1=1, param2=2). Также неплохо бы было внедрить сопоставление с образцом (кстати, предлагаю ввести ещё и универсальный идентификатор _), хотя здесь, с учетом специфики разрабатываемого языка, не все так просто.

Цитата:

Есть интересный вопрос: пусть мы имеем какое-нибудь множество, заданное в форме выражения. Как определить, конечно ли оно?

Ну вот вы там сами и ответили прекрасно. Кроме того, мне вот понравился вот этот ваш подход:

Цитата:

Я предлагаю всё-таки представлять бесконечные множества специальными объектами, показывающими, как они строятся из других конечных и «атомных» бесконечных.

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

Мне интересней теор-множественные операции на бесконечными множествами. Например, нужно нам найти пересечение двух таких множеств. Они порождаются выражениями e1 и e2. Мы можем сконструировать новое множество, выражение-генератор которого будет выражением e1&&e2. А можно сконструировать новое множество с указанием (e.g., в виде флажков), что это множество является пересечением исходных. Кажется, последний подход позволил бы много чего понадергать из теории типизации (обычное C'шное int i; ровно и означает i in Z; :) ).

Ох не просто будет компилятору S1, он ведь должен будет догадаться, что именно имел ввиду программист. :)

Цитата:

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

Не надо! S1 это вам не 1C. :)

Цитата:

Мне бы хотелось рассмотреть побольше примеров, чтобы понять, насколько далеко идти, чтобы не застрять с этим языком навеки.

А ну да, можно попробовать настоящий test-driven development, с предварительным написанием тестов; сначала примеры кода, потом -- компилятор. Опять же повторюсь, денег не плотют -- торопиться некуда. :)

За парсер и сложность синтаксиса не переживайте -- это самая простая часть в таком языке. :) Главное -- придумать правила анализа кода, затем придумать низкоуровневое представление (ассемблер для VM), ну и заодно написать саму VM (со сборщиком мусора!). (Пока здесь, имхо, нативный код не нужен. Выигрыш будет ничтожным из-за гипертрофированной высокоуровневости языка.)

Цитата:

Если понравится, не придумаете ли что-нибудь своё в пример?

Сначала поясните, что вы имели ввиду, когда говорили "должно быть обязательное указание множеств, из которых берутся все переменные в левой части такого конструктора"? Т.е. вы хотели бы видеть что-то вроде R=[x in R : x>=0];?

Также замечу, что я принципиально против вот такого вот вида интерактивной repl-сессии. То есть работать над отладочным инструментарием и над слоем интроспекции может быть и стоит, но изначально требовать от среды таких вот выкрутасов с красивой печатью промежуточных результатов -- это пока слишком, имхо. Лучше предусмотреть в языке простой консольный ввод-вывод и печатать множества самостоятельно. Или проверять выполнение различных интересных условий через _assert(), см. выше.

Не понял также, что вы имели ввиду под "кстати, можно сделать перед печатью результата поиск в таблице идентификаторов и отобразить это как "R2"". Если не ошибаюсь, смысл { x * y : x in R1 && y in R2 } ну никак не совпадает ни с R2, ни с R * { t0 : t0 <= 0 } (а может вы хотели написать не x*y, а [x]*[y]?). Через ~ (тильда) вы видимо обозначили симметрическую разность, а вот что такое %1=%2 даже близко не догадываюсь. И почему вы поменяли квадратные скобки на фигурные? Мне вот квадратные на моей клавиатуре набирать проще, без шифта. :)

А так ваш код понятен. Могу только попробовать переписать его в более для меня понятный синтаксис:

    res= R1 = [x in R : x>=0];
    res+= R2 = [-x : x in R];
    res+= R1+R2;
    res+= R1*R2;
    res+= R1\R2;
    res+= [x*y : x in R1, y in R2];
    res+= [0, ... , 8] in Z;
    res+= [pair(x, y) : x in N, y in N, x+1=y];
    res+= [pair(x, x+1) : x in N];
    print(res);

Что должно вывестись в результате -- не представляю; как я говорил выше, для меня проще проверять ход дела assert'ами.

Вообще эти примеры хорошо изучены и проработаны в функциональных языках. Так что с list comprehension проблем быть не должно. Хотя, опять же, специфика S1 подразумевает, что такие конструкторы множеств должны обрабатываться иначе, с использованием даже не лени, а суперлени. :) То есть, если в типичном функциональном языке со списочными литералами, выражение [x | x in list1, x>5] есть сахар над r=[]; forall(x in list) if(x>5) r+=[x];, то в S1 мы должны таскать за собой конструктор множества пока не выяснится, что его действительно можно и нужно превратить в цепочку циклов и условий. Собственно, при интроспекции (если её вообще стоит делать, ибо лучше всего семантиу конструктора конкретного множества описывает либо весь жизненный цикл запущенной программы, либо сгенерированный байт-код; и то и другое не совсем то, что ожидается в качестве результата работы воображаемой функции печати introspect) можно печатать именно внутреннее представление множеств, выгребая оттуда куски использованных при их построении конструкторов (например, сообщение repl-интерпретатора <infinite set> должно быть дополнено указанием способа создания множества, с указанием выражения-функции, генерирующего печатаемое множество). Нужны эксперименты. В том числе нужно поиграться с разными вариантами написанных на самом S1 функций печати множеств.

Теперь попробую ещё немного пофантазировать, и привести ещё парочку примеров S1-программулек; я тоже не буду никак себя ограничивать в синтаксисе, так что фрагменты могут быть немного противоречивыми и несамосогласованными.

Переписанный генератор простых чисел:

sieve(set)
{
    s=set;
    p=select s;
    return [p]+sieve([x in s : x%p]);
}

primes() {return sieve([x in N : x>=2]);}

Использование сопоставления с образцом для написания игрушечного мета-eval'а для теор-множественных выражений самого языка (ну совсем несерьезный пример :) ):

eval(expr)
{
    switch(expr)
    {
        match a+b: return eval(a)+eval(b);
        match a*b: return eval(a)*eval(b);
        case []: return [];
        match [a]: return [eval(a)];
        match !a: return !eval(a);
        default: panic();
    }
}

test()
{
    myset=random();
    _assert(myset==eval(myset));
}

Преобразования частичного порядка в линейный:

domain(pairs) {return [x : (_, x) in pairs];}

linext(nodes, edges)
{
    // Reverse the arcs.
    arcs=[(x, y) : x,y in nodes, (y, x) in edges];
    visited=[];
    sources=nodes-domain(arcs); // Nodes with no incoming arcs.
    temp=nodes;
    while(temp) yield visit(select temp); // Start DFS.
    visit(node) // Local function.
    {
        if(node in visited) return [];
        visited+=[node];
        temp=[x in nodes : (node, x) in arcs]; // Forward neighborhood.
        while(temp) yield visit(select temp);
        yield node;
    }
}

Функция linext() может быть напрямую использована в задачах планирования работ (cf. сетевые графики), для определения последовательности компиляции взаимозависимых файлов проекта (make), для разрешения зависимостей при компоновке объектного кода, &c.

Детектор гамильтоновых путей (использует linext и воображаемую cycles; в коде могут быть ошибки):

hamilton(dag)
{
    if(cycles(dag)) return false; // Only DAGs are allowed.
    sorted=[];
    // Find linear extension of partial order "dag".
    while(s=linext(dag.nodes, dag.arcs)) sorted+=[s];
    return dag.arcs subset [(x, y) : x, y in sorted]; // Find a path.
}

Детекторы гамильтоновых путей относятся к $\mathrm{NP}$-hard задачам, но hamilton() имеет не более чем $\mathcal{O}(n^2)$, т.е. полиномиальную сложность... Да, дайте мне миллион. Шутка. :)

Суммирование бесконечного ряда (вот это уже излишество; к тому же непонятно, как это реализовывать, ну разве что через сивольные $\lim$'ы как в cas'ах):

    s=[sum([1/x : x in N])];
    s+=[sum([1/x^2 : x in N])];
    s+=[sum([(-1)^(x+1)/x : x in N])];
    _assert(s==[INF, pi^2/6, ln(2)]);

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

Здесь видимо необходимы пояснения (вольное изложение примера из работы J.Cai et al.). Дан граф, дано подмножество $w$ его вершин. Если мы начнем путешествия из каждого элемента $w$ и будем помечать все посещенные вершины, то, когда этот процесс закончится, мы получим множество всех помеченных вершин $s$. Очевидно, что вершины из $w$ в любом случае тоже будут помечены, т.е. $w\subseteq s$. Определим функцию $e=e(v)$, которая для вершины $v$ возвращает её окрестность, а именно множество вершин, в которые можно попасть из исходной ровно за один шаг. Пусть функцию $e$ можно применять к множеству поточечно; тогда мы можем обозначить "выколотую окрестность" множества $s$ как $e(s)$, а саму окрестность как $f(s)=s\cup e(s)$.

Идея в том, что искомое решение $s$ является неподвижной точкой $f(s)=s$. Но $f$ имеет и другие неподвижные точки, в том числе и тривиальные: пустое множество, стоки орграфа, все множество вершин. Поэтому к уравнению $f(s)=s$ надо добавить ограничения. Одно уже было описано, я имею ввиду $w\subseteq s$, ограничивающее решение снизу. Ограничение сверху дается через соображение о минимальности неподвижной точки (по включению).

Булеан вершин имеет структуру решетки. Введенная функция $f$ монотонна в смысле $a\subseteq b\Rightarrow f(a)\subseteq f(b)$. Это позволяет применить теорему Тарского-Кнастера (где-то на форуме я уже о ней подробно писал), которая во-первых, утверждает существование минимальной неподвижной точки и, во-вторых, будучи конструктивной теоремой, дает рецепт нахождения такого решения путем итераций $f^n(w)\to s,\ n\to\infty$.

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

В-принципе, мы можем искать неподвижную точку "вручную":

leastfixed(f, w)
{
    p=f(w);
    return p==w?p:leastfixed(f,p);
}

Но может быть стоит придумать для такого кода какой-нибудь подходящий синтаксический сахар (нет, Y-комбинатор пока оставим для экспериментов :) ).

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

Если это возможно, хотелось бы увидеть "живые" примеры парадоксов теории множеств. Но пока мозги/руки что-то не доходят, ленятся. :)

Насчет бесконечности. Из области формальных спецификаций ещё известен (т.е. лично мне-то он как раз-таки и неизвестен; и если есть какая-то информация -- буду рад услышать) язык rsl, в котором вроде бы есть поддержка мощности $\aleph_0$.

Вопрос: Семантика random()'а вроде-как соответствует операции in. Нельзя ли в таком случае как-то определить эту функцию на самом S1? Здесь есть проблемы. Во первых, рассматривается принадлежность универсуму, как же его обозначить, set42 (кстати, ещё одно хорошее название для языка!)? :) Во-вторых, операция принадлежности, вроде как очень часто тянет за собой неявный квантор всеобщности, так что такой random() может тривиально оказаться тождественной функцией. Здесь неплохо бы смотрелись обозначение универсума+select. Но все-таки, вдруг как-то можно обойтись одной лишь операцией in? Возможно, даже с небольшими изменениями в синтаксисе, лишь бы попробовать избавиться от "свышеданных" операторов/функций типа select/nextSet/random. Какой-нибудь сахарок бы придумать для навешивания ограничения, запрещающего множеству быть не singleton'ом. Подумайте над этим, пожалуйста. В-принципе, функция select() мне нравится, но хотелось бы иметь возможность определить её в терминах других конструкций S1. Намек-зацепка: сопоставление с образцом позволяет разбирать множества на составные части.

Вот не знаю, нужны ли в языке безымянные вызываемые функции, а если нужны то как их синтаксически оформлять, у нас же не используется pascal-like слово function при определении функции; но и до \x x^2 докатываться не хотелось бы. :)

Насчет forall'а. Нужен или не нужен? Конструкция forall(expr_over_x) body может быть сахаром над s=[expr_over_x]; while(s) {x=select s; body}.

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

Ещё есть беспокойство по поводу возможных конфликтов тернарного оператора ?: и бинарного : из конструкторов множеств.

P.S.: Боюсь, что этот поток сознания вообще нечитабелен... :) Если бы мысли были более конкретными, то можно было бы их оформить в виде TODO-списка, а так...
P.P.S.: Ещё один вариант названия для S1 -- infty (есть правда как минимум один кофликтующий по названию проект, но вроде-бы пока занять это название ещё можно; да и скобки квадратные все-таки подрисуем -- к логотипу). :) Вообще, надо выписать внушительнй список названий, проверить конфликты в поисковике, ну и выбрать наиболее подходящее. Вы знаете как бренд Java придумывался? Поинтересуйтесь.

[arseniiv]

Circiter в сообщении #480496 писал(а):

Думаю, не стоит бояться придумывания нового необычного синтаксиса. Это же все-равно эксперимент, деньги-то не плотют. :)

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

Спасибо, что написали много примеров! Почитаю. Завтра на день рождения сделаю себе подарок.

-- Вт сен 06, 2011 00:46:43 --

Circiter в сообщении #480496 писал(а):

Даже числа. Согласитесь, так красивше.

У меня просто маленький оптимизационно-по-времени бзик. Да, соглашусь. Люблю сходство формы.

Circiter в сообщении #480496 писал(а):

Действительные пока, имхо, там вообще ни к чему

Спасибо! Теперь не перед кем извиняться за отсутствие их будет.

Circiter в сообщении #480496 писал(а):

Если нужна упорядоченность, просто положите каждый элемент множества в двуэлементное множество [номер, [элемент]].

О, а я голову каноническими примерами забил, а ведь этот не менее наглядный, а быстродействие намного больше!

О лексических кортежах. Как вам вариант такой?: в скобках через запятую синтаксис для кортежа, тогда функция всегда принимает один аргумент (который может оказаться пустым кортежом; вообще я за нестрогую типизацию здесь и за такие маленькие вольности), притом можно выбрать или (1) вариант с перечислением параметров в заголовке — тогда им после вызова сопоставляются элементы кортежа, а тем, кому не досталось элемента, достаётся что-то типа null (т. к. пока у нас нет отхода от множеств, достаётся $\varnothing$), или (2) вариант, при котором нельзя в заголовке параметры указывать. В любом случае, кортеж со всеми параметрами будет виден в функции под каким-нибудь фиксированным именем или, например, под именем # (ворую из Mathematica, немного меняя смысл). Множественное присваивание немного отдельно от кортежей — шаблоны реализовывать здесь вредно, но ничто не мешает ему, конечно, быть. Операция , будет преобразована в ; — блоки возвращают значение последнего оператора, все операторы являются выражениями.

Щас почитаю дальше.

-- Вт сен 06, 2011 01:02:30 --

Circiter в сообщении #480496 писал(а):

и массивами

Да, да, я за их тождественность. Вообще не вижу разницы между ними здесь. Пусть уж массивы реализуются кортежами (или нет, и сделать две разные реализации? Честно говоря, даже не думал об отдельных массивах.) На кортежах будут ещё операции типа строковых, как считаете?

Кстати, о функциях tuple и pair. Вторую сведём к первой, а первую оставим, несмотря на предыдущее моё предложение — она мешать не будет, а будет даже помогать. С другой стороны, если сделать синтаксис для кортежей, она отпадает как сахар (или такой синтаксис отпадает, если сделать именно функцию).

Circiter в сообщении #480496 писал(а):

Кортежи ещё можно заменить такой несколько экзотичной, чуть ли не ООП'шной конструкцией. Когда нам нужен кортеж с фиксированным числом элементов, да ещё и с удобным доступом по имени, т.е., фактически C'шная struct мы создаем функцию с пустым телом, e.g. func(param1, param2){}, вызываем её с определенными фактическими параметрами, e.g. func(5, []), а результат передаем туда, где ожидается кортеж. Например, a=func(5, []). Теперь мы можем обращаться к элементам кортежа таким способом: a.param1. А присваивания b=a.param1; c=a.param2; можно тогда кратко записать как b, c = a;.

Это было бы приятной мелочью! Согласен, x, y, z удобнее, чем [0], [1], [2]. А вот какой предлагаю способ (функций-конструкторов это не отменит, хотя можно будет и без них, если сделать особый синтаксис). Пусть множество может нести строку-тег, которая никак не влияет на вычисления, этакая метаинформация. Пусть теги хранятся в табличке, и к ним привязана некоторая дополнительная информация и со стороны CLR: к примеру, какие свойства переводить в какие индексы, если перед нами кортеж с таким тегом (а если там будет не кортеж — наверно, положимся на пунктуальность и assert, о котором вы что-то ниже упоминали). Итого: функция возвращает кортеж, тегированный нужной строкой (только мы сами это в её теле укажем), а где-то выше-выше вместе с её определением добавляются свойства этого «типа». А если мы введём простой синтаксис для смены тега у данного значения (получает одно, отдаёт одно), можно обойтись и без функций. Как вам такой подход?

[Circiter]

2arseniiv

Цитата:

Тогда надо будет или использовать какой-то там алгоритм, разделяющий правильно операции и операнды с учётом приоритета, или довольно большйю грамматику — и тут я буду вынуждени использовать парсер, который берёт на вход, кроме файла, ещё и скомпилированную грамматику

Все это -- очень просто. Парсинг выражения C-языка реализуется полсотней кода на C. Для начала. С кодогенерацией вопрос отдельный...

Цитата:

Спасибо, что написали много примеров! Почитаю. Завтра на день рождения сделаю себе подарок

Читайте, не пейте много. :) Я так, понимаю, с днем рождения принято поздравлять. Что и делаю. Заодно ещё раз предлагаю свое участие в этом проекте -- в конце-концов мне же просто интересно. Иначе все-равно свой fork сделаю и буду поддерживать его независимо. Это угроза. :)

Цитата:

Операция , будет преобразована в ; — блоки возвращают значение последнего оператора, все операторы являются выражениями.

Да, наверное... По крайней мере это традиционный подход в таких странноватых языках. Но чем же тогда будет выражение (a, b, c)? Цепочкой выражений, --- т.е. блоком, --- или кортежем? Всё, приехали -- тело функции будет кортежем. Возможно я вас не очень понял. Надо подумать; да и ваших уточнений жду.

Кстати, код может изобиловать излишествами проде f([(...)]). Не стоит ли попробовать ввести сахар, позволяющий выбрасывать лишние скобки? То есть, обычно функция вызывается с круглыми скобками, но если есть другие, то с ними. Делать безскобочные вызовы функций не хочется. Хотя встроенные операторы вроде return'а будут работать именно так.

-- Вт сен 06, 2011 01:17:33 --

Цитата:

На кортежах будут ещё операции типа строковых, как считаете?

Наверное, это стоит реализовывать библиотечными функциями на самом infty.

Цитата:

С другой стороны, если сделать синтаксис для кортежей, она отпадает как сахар (или такой синтаксис отпадает, если сделать именно функцию).

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

-- Вт сен 06, 2011 01:27:19 --

Цитата:

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

Увы, я ничего не понял, приведите примеры кода. :)

[arseniiv]

Блоки не будут кортежами, думаю. Функции от кортежей можно, как в Lua, и правда вызывать без скобок (а там ещё и функции от строк так, но у нас-то их нет. Или есть?). А кортежи лучше всё же поглубже интегрировать в язык.

Про ;, похоже, моё изложение было мутное. Имел в виду, что , используется только в кортежах, а ; только в блоках. Если все управляющие структуры сделать с чем-то, завершающим блоки (типа endif), то надобность в фигурных скобках для окружения блоков вообще отпадёт.

arseniiv в сообщении #480607 писал(а):

Читайте, не пейте много. :)

О, этого и не делаю никогда принципиально.

Circiter в сообщении #480626 писал(а):

Все это -- очень просто. Парсинг выражения C-языка реализуется полсотней кода на C. Для начала. С кодогенерацией вопрос отдельный...

Думаю, не буду городить велосипедов, всё же воспользуюсь библиотекой, которая будет парсить за меня. А с кодогенерацией можно быть довольно просто, если не оптимизировать (куда уж там, в таком богатом на ситуации языке). Построим при чтении дерево и будем его сажать в землю поглубже!

Следующее писал до того, как увидел ответ:

Circiter в сообщении #480496 писал(а):

Думаю не помешают именованные фактические параметры функций, что-то вроде f(param1=1, param2=2).

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

Circiter в сообщении #480496 писал(а):

затем придумать низкоуровневое представление (ассемблер для VM), ну и заодно написать саму VM (со сборщиком мусора!). (Пока здесь, имхо, нативный код не нужен. Выигрыш будет ничтожным из-за гипертрофированной высокоуровневости языка.)

Да, нативный не стоит, я обеими руками и ногами тоже за. Только когда дойдёт время до сборщика мусора, не поможете?

Кстати, адвайте сделаем поддержку логических значений (отдельные операции для них мы уже и так используем). Т. е., конечно, они будут представлены множествами (пусть $\mathrm{false} \equiv \varnothing$, $\mathrm{true} \equiv \{\varnothing\}$), но мы ещё ни разу не обсуждали их. Надо их упомянуть, а то вдруг ещё забудутся.

В общем, после некоторого устоявшегося консенсуса надо будет:
1. Определить операции.
2syn. Придумать синтаксис этим операциям; синтаксис для обычных императивных конструкций примерно ясен, а вот хорошие обозначения для множества операций (теоретико-множественные, кортежно-цепочечные ( ), числовые… что-то вроде ещё было).
2vm. Придумать конструкции для VM.
3. Всё остальное.
Хороший подход?

Кстати, вы за/против функций-значений в этом языке? Они иногда удобны, а в функциональный язык превратить не смогут. Только тогда придётся ввести им отдельный тип, ибо представлять их множествами как-то небезопасно (и неудобно).

Думаю, сначала лучше ограничиться реализацией попроще и смотреть, что выходит (не обязательно тестами, можно и просто в REPLе смотреть), и добавлять желаемое в следующую версию.

Попытаюсь дочитать остальное.

-- Вт сен 06, 2011 01:42:07 --

Circiter в сообщении #480496 писал(а):

Вообще, надо выписать внушительнй список названий, проверить конфликты в поисковике, ну и выбрать наиболее подходящее.

Тогда можно назвать Ajleroen. (Я его специально так выдумал, чтобы не находилось. А теперь по нему два результата.) Правда, это шутка. Всё-таки, называть математический императивный язык «спасибо» странновато.

-- Вт сен 06, 2011 01:50:58 --

Circiter в сообщении #480496 писал(а):

Сначала поясните, что вы имели ввиду, когда говорили "должно быть обязательное указание множеств, из которых берутся все переменные в левой части такого конструктора"? Т.е. вы хотели бы видеть что-то вроде R=[x in R : x>=0];?

В том и дело, что слева их воткнуть нереально: там может быть выражение с любой структурой и повторением переменных несколько раз. Оттуда вытаскивать принадлежность будет тоже неудобно. Можно сделать как-то так: [x: x in R: x >= 0]. Довольно мило.
Кстати, можно сделать перечисление в средней конструкции таких «определений» переменных запятой (круглых скобок нет, нет и многозначности). Или можно сделать что-то типа множественного присваивания. Т. е. ни к чему писать [(x + n, y): x in R && y in R && n in Z: x >= 0], когда можно [(x + n, y): x, y in R, n in Z : x >= 0] или [(x + n, y): x, y, n in R, R, Z: x >= 0]! К тому же, в средней части конъюнкция вообще как-то неестественна…

(Ой, уже лучше пойду. Завтра пары, хоть и после обеда. Сплю ужасно много.)

[Circiter]

2arseniiv

Цитата:

Если все управляющие структуры сделать с чем-то, завершающим блоки

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

Цитата:

Только когда дойдёт время до сборщика мусора, не поможете?

Не знаю, получится ли это интегрировать в вашу инфраструтуру. Я вот в третий раз предлагаю как-раз таки фронт-енд, парсер и все такое пописать за вас (сборщик мусора у меня получится тривиальным, я шибко этим не увлекался). :) Кстати, о какой библиотеке парсинга вообще речь шла? Вы понимаете, что у вас контекстно-зависимые грабли в грамматике скорее всего будут (например, в C++ они есть)?

Ok, я наверное все-таки попробую сделать небольшой форк, вы не против? Потом можно будет при желании объединить наиболее удачные куски кода. Надо подумать над лицензиями, стилем кодирования и т.д... Так что выбирайте название для своей ветки -- если оно будет отлично от infty, то последнее я беру для своей экспериментальной поделки.

Цитата:

Надо их упомянуть, а то вдруг ещё забудутся.

Упоминули. :) Но, раз они могут выражаться через множества, то в чем проблема-то? Кстати, истиной лучше пусть будет любое непустое множество.

Цитата:

Кстати, вы за/против функций-значений в этом языке?

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

Цитата:

можно и просто в REPLе смотреть

Ещё раз обращаю ваше внимание на то, что repl -- довольно таки высокотехнологичная (но при этом, имхо, бесполезная в конечном счете) штуковина и начинать с такого интерактивного режима будет сложновато. Но это, опять же, имхо.

Цитата:

В том и дело, что слева их воткнуть нереально: там может быть выражение с любой структурой и повторением переменных несколько раз. Оттуда вытаскивать принадлежность будет тоже неудобно.

Не, это не так уж и сложно. Уж точно не сложнее чем сопоставление с образцом.

Цитата:

Кстати, можно сделать перечисление в средней конструкции таких «определений» переменных запятой

В моих примерах так и было.

P.S.: Надеюсь, дочитаете мое сообщение до конца и прокомментируете другие существенные части.

(Оффтоп)

Цитата:

Ой, уже лучше пойду. Завтра пары, хоть и после обеда. Сплю ужасно много

Первый раз вижу программиста, регулярно спящего ночью. :) Хотя, да, универ вносит коррективы...

-- Вт сен 06, 2011 02:40:00 --

И, чуть не забыл, вы на чем писать собирались? Я, наверное, попробую на чистом C начать (сначала думал о C++, но вовремя одумался, тем более что кое-какие разрозненные куски C-кода уже имеются)... Не факт, что доведу до конца, но компилятор протейших программулек (вроде тех, примеры которых приводились мной выше) должен получится. Например, парсер почти готов, но он ничто по сравнению с кодогенератором для реализации которого пока даже набор инструкций не придуман.

Цитата:

Спасибо! Теперь не перед кем извиняться за отсутствие их будет.

А вы помедитировали над powerset(Z)?

[arseniiv]

Circiter в сообщении #480667 писал(а):

Ok, я наверное все-таки попробую сделать небольшой форк, вы не против?

Совсем не против! Хоть кто-то будет что-то делать.

Circiter в сообщении #480667 писал(а):

Вы понимаете, что у вас контекстно-зависимые грабли в грамматике скорее всего будут (например, в C++ они есть)?

Да? Мне казалось, ничего контекстно-зависимого мы не сделали пока.

Circiter в сообщении #480667 писал(а):

Кстати, истиной лучше пусть будет любое непустое множество.

А, ну да, забыл. Но логические операции пусть возвращают только те два.

Circiter в сообщении #480667 писал(а):

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

Не знаю даже. Лексические замыкания очень удобная вещь, но их реализация меня пугает. Может, в первой версии без них, а потом добавить? Безымянные соответственно, ведь они тоже должны, по идее, быть замыканиями того, где их определили (в таком случае все функции можно сделать формально безымянными, присвоенными переменным, как много где).

Circiter в сообщении #480667 писал(а):

Ещё раз обращаю ваше внимание на то, что repl -- довольно таки высокотехнологичная (но при этом, имхо, бесполезная в конечном счете) штуковина и начинать с такого интерактивного режима будет сложновато. Но это, опять же, имхо.

Как основной режим я, естественно, его не хочу. Это потом надстройка над интерпретатором будет. (Мне просто в REPLе как-то удобно тестировать возможности языков.)

Circiter в сообщении #480667 писал(а):

Уж точно не сложнее чем сопоставление с образцом.

А оно несложное?

(Оффтоп)

Circiter в сообщении #480667 писал(а):

Первый раз вижу программиста, регулярно спящего ночью. :) Хотя, да, универ вносит коррективы...

Спящего, да часто недосыпающего. Пока ещё, правда, не началось, но скоро начнётся.

Circiter в сообщении #480667 писал(а):

И, чуть не забыл, вы на чем писать собирались?

Можно меня поругать — на C#. У меня там тоже, кстати, маленький кусочек реализации множеств есть. Недописанный, правда.

Circiter в сообщении #480667 писал(а):

А вы помедитировали над powerset(Z)?

Реализация будет страшненькая через него. Хотя способ естественный.

Вечером дочитаю и допишу.

[Circiter]

2arseniiv

Цитата:

Совсем не против! Хоть кто-то будет что-то делать.

Тогда я беру название infty для этой ветки. Название, честно говоря, не очень, но это рабочее, кодовое имя. Проект можно будет заморозить или провести ребрендинг в любое время. Но я пока не собираюсь делать именно Продукт; просто маленькая собственная реализация.

Цитата:

А, ну да, забыл. Но логические операции пусть возвращают только те два.

Ok.

Цитата:

Лексические замыкания очень удобная вещь, но их реализация меня пугает.

У меня они уже, можно сказать, реализованы, только сам байткод пока не генерируется, до этого ещё далеко.

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

mkadder=_(x)
{
    return _(y)
    {
        return x+y;
    };
}

adder=mkadder(5);
_assert(adder(3)==8);

Интересно, что если в только что приведенном фрагменте вообще этот символ выбросить? Приемлем (разбираем парсером) ли будет такой синтаксис?

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

Безымянные замыкания позволят вот такие вот ужасы писать, в данном случае это рекуррентно заданная, но нерекурсивная (ни одна функция не вызывает сама себя, ни прямо, ни косвенно) реализация факториала:

Y(g)
{
    a=_(f){return f(f);}
    return a(_(f){return g(_(x){return f(f)(x);});});
}

F(f) {return _(n){return n?n*f(n-1):1;}}
fac(x) {return Y(F)(x);}

test() {_assert(fac(5)==120);}

(Да, да, мой парсер считает такой синтаксис корректным!)
В то же время теор-множественная нотация приводит к другому решению:

fac(n)
{
    s=[x in N : x<=n];
    p=1;
    while(s) p*=select s;
    return p;
}

test() {_assert(fac(6)==720);}

(Мой парсер пока это не распознает из-за недоделанного list comprehension.)

Внимание: Если у нас числа будут представляться множествами, то как быть с операцияими арифметики и теории множеств? Что означает 5*3? Ой, ужас.
Не, ваши реплики о возможности введения endif'ов, наталкивают на мысль, что вы и на словесное представление теор-множественных операторов готовы (union, in, subset, и т.д.). :) Здесь нужно думать. А у меня голова что-то сейчас плохо варит.

[arseniiv]

Circiter в сообщении #480893 писал(а):

Ой, ужас.

Да. Может, и словесное представления. А может, я у себя побалуюсь уникодом. (Кстати, а разве в 1С он используется кроме русских идентификаторов? А мне нужны только символы оттуда.) А ещё можно сделать что-то типа ++, **, \\…

[kotenok gav]

(Похоже, у меня сегодня день некропостинга)
Надо придумать, как реализовать арифметические операции с числами (т.е. $0=[]$, $1=[[]]$, $2=[[], [[]]]$, $3=[[], [[]], [[], [[]]]]$, etc). Вроде выходит так (если разрешить операцию "заворачивания" множества в множество (хотя очень хочется ее запретить)):

nextNumber(num) {
    return num + [num];
}

addNumbers(num1, num2) {
    ans = num1;
    safeNum2 = num2;
    whilene (safeNum2) {
        a = select(safeNum2);
        ans = nextNumber(ans);
    }
    return ans;
}

multiplyNumbers(num1, num2) {
    ans = [];
    safeNum2 = num2;
    whilene (safeNum2) {
        a = select(safeNum2);
        ans = addNumbers(ans, num1);
    }
    return ans;
}

А вот как сделать вычитание? Да и отрицательные числа сделать хочется (вопрос: как их реализовать и не поломают ли они функцию сложения?)...