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

[_Ivana]

kotenok gav в сообщении #1445599 писал(а):

А вот как сделать вычитание?

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

kotenok gav в сообщении #1445599 писал(а):

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

Это ж у вас обычное пианино, можете добавить отдельное поле знака.

[kotenok gav]

_Ivana в сообщении #1445700 писал(а):

инкрементировать вычитаемое пока не получим уменьшаемое

А, точно.

_Ivana в сообщении #1445700 писал(а):

простейшее рекурсивное сравнение на равенство

Зачем, если у нас есть операция симметрической разности?

_Ivana в сообщении #1445700 писал(а):

отдельное поле знака

Так хочется же число одной переменным-множеством обозначать. Можно, конечно, писать нечто типа [n, [n, 0]] и [n, [n, 1]], но это уже извращение и непонятно, как для него функцию следующего числа реализовывать.

-- 20 мар 2020, 02:27 --

Для вычитания такая программа получается:

substractNumbers(num1, num2) {
    safeNum2 = num2;
    ans = [];
    whilene (safeNum2 ~ num1) {
        safeNum2 = nextNumber(safeNum2);
        ans = nextNumber(ans);
    }
    return ans;
}

-- 20 мар 2020, 02:31 --

А сложение и умножение лучше чуть поправить (иначе оно использует небольшой хак):

addNumbers(num1, num2) {
    ans = num1;
    countNum2 = [];
    whilene (countNum2 ~ num2) {
        countNum2 = nextNumber(countNum2);
        ans = nextNumber(ans);
    }
    return ans;
}

multiplyNumbers(num1, num2) {
    ans = [];
    countNum2 = [];
    whilene (countNum2 ~ num2) {
        countNum2 = nextNumber(countNum2);
        ans = addNumbers(ans, num1);
    }
    return ans;
}

[_Ivana]

kotenok gav в сообщении #1445701 писал(а):

Зачем, если у нас есть операция симметрической разности?

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

kotenok gav в сообщении #1445701 писал(а):

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

Тут надо определиться, что такое число. Если божественное пианино, то оно уже вот оно. Если же остальные творения рук человеческих, то придется лепить костыли. Например, для рациональных вам придется делать пару из двух пианин. Для комплексных - больше, и т.д. Поэтому придется собраться с духом и решиться на расширения.

[kotenok gav]

_Ivana в сообщении #1445704 писал(а):

Ну кто же знал, что она у вас есть.

Ну как бы это говорилось в стартовом посте.

_Ivana в сообщении #1445704 писал(а):

Тут надо определиться, что такое число.

Некое множество. Любую пару множеств можно, конечно, сделать множеством ([a, [a, b]]), но как же операции реализовывать тогда?

-- 20 мар 2020, 02:44 --

Удобнее даже [[a], [[a], [b]]], кажись.

[arseniiv]

kotenok gav в сообщении #1445599 писал(а):

т.е. $0=[]$, $1=[[]]$, $2=[[], [[]]]$, $3=[[], [[]], [[], [[]]]]$, etc

Способ фон Неймана может быть неудобен в этом случае, а может быть проще представлять числа как [], [[]], [[[]]], [[[[]]]], …

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

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

switch (s)
case 0 {
    // выполняется, если s == 0
}
case [x, *xs] {
    // выполняется, если s != 0, притом
    // x = select(s) и xs = s - x
}

а отдельный select удалить как нежелательный. Теперь язык не нуждается в вываливании с ошибкой посреди кода. И тогда эта конструкция очень хорошо ляжет на кодирование машин Минского этим языком, потому что она в точности реализует, если s код числа, команду JZDEC, или как я её там звал.

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

Вот код, аналогичный вашему, но с вычитанием и делением, и я не стану заводить отдельную функцию для последователя числа, раз это просто [n]:

prev(x) { // ниже prev не используется
    switch (x)
    case 0 { return 0; } // лучше уж так, когда нам вообще пригодится prev в виде функции
    case [prev_x, *_] { return prev_x; }
}

add(x, y) {
    switch (x)
    case 0 { return y; }
    case [prev_x, *_] { return add(prev_x, [y]); }
}

// Два варианта вычитания, достаточно полезных для натуральных чисел

sub(x, y) { // truncated subtraction
    switch (x)
    case 0 { return 0; }
    case [prev_x, *_] {
        switch (y)
        case 0 { return x; }
        case [prev_y, *_] {
            return sub(prev_x, prev_y);
        }
    }
}

sub2(x, y) { // symmetric subtraction
    return add(sub(x, y), sub(y, x)) // если лень определять его с нуля
}

not(x) { // непусто тогда, когда x == 0, и наоборот
    switch (x)
    case 0 { return [0]; }
    case [_, *_] { return 0; }
}

eq(x, y) { // непусто ровно когда x == y
    return not(sub2(x, y)) // можно и минимальнее, конечно, опять же
}

mult(x, y) {
    switch (x)
    case 0 { return 0; }
    case [prev_x, *_] { return add(y, mult(prev_x, y)); }
}

div(x, y) {
    // ife (y) { return 0; } // раскомментировать, если не хотим зацикливания при делении на ноль
    ifne (sub(x, y) + eq(x, y)) { // если x > y или x == y
        return [div(sub(x, y), y)];
    }
    else {
        return 0;
    }
}

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

-- Пт мар 20, 2020 05:00:22 --

Ой, я всю эту страницу пропустил как-то, извините.

-- Пт мар 20, 2020 05:05:11 --

kotenok gav в сообщении #1445599 писал(а):

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

Парой натурального со знаком может быть не очень удобно, а может и быть, ну и пара из двух, вида $(m,0)$ или $(0,n)$ (хотя можно брать вообще все, а к такому каноническому виду приводить через раз).

kotenok gav в сообщении #1445706 писал(а):

Любую пару множеств можно, конечно, сделать множеством ([a, [a, b]]), но как же операции реализовывать тогда?

-- 20 мар 2020, 02:44 --

Удобнее даже [[a], [[a], [b]]], кажись.

А вот про возможность выражать пары средствами самого языка, не уходя в числа, я забыл! Надо подумать, это могло бы быть в каком-то смысле быстрее, если мы вдруг начнём оптимизировать количество операций.

-- Пт мар 20, 2020 05:17:19 --

Тут так и быть попользуюсь ещё selectом. Пара Куратовского $\{\{x\},\{x,y\}\}$ нормально отыгрывает, можно не добавлять вложенности (а вот снять скобки с одинокого икса будет уже чревато обработкой кучи лишнего):

cons(x, y) { // для нелисперов, это собрание в пару
    return [[x], [x, y]]
}

car(p) { // для нелисперов, это извлечение первого элемента пары
    a = select(p);
    b = select(p);
    c = select(a);
    ife (a) { return c; }
    d = select(b);
    ife (b) { return d; }
}

cdr(p) { // для нелисперов, это извлечение второго элемента пары
    a = select(p);
    b = select(p);
    c = select(a);
    d = select(b);
    ife (a) {
        ife (c ~ d) {
            e = select(b);
            return e;
        }
        else { return d; }
    }
    ife (b) {
        ife (c ~ d) {
            e = select(a);
            return e;
        }
        else { return c; }
    }
}

-- Пт мар 20, 2020 05:28:41 --

А, ну в кодах выше надо читать [] вместо 0, вроде такого раньше не было.

[kotenok gav]

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

[kotenok gav]

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

[arseniiv]

kotenok gav в сообщении #1445770 писал(а):

1) рекурсия (это легко поправимо)

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

kotenok gav в сообщении #1445770 писал(а):

и 2) излишнее использование select'а. Мои функции его не используют.

Да, select довольно неудобен. Кстати я вчера писал, что своей нетотальностью (не определён для []), но на самом деле он больше наверно плох тем, что требует принимать переменную (которую он мутирует), а все остальные конструкции языка (кроме присваивания, конечно) не требуют. Кстати switch вот тоже хорош тем, что не требует.

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

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

И ещё как автор темы покажу свой не очень давний язык с похожей метаидеей («есть только один тип данных, достаточно отличающийся от привычных»): https://esolangs.org/wiki/Punctree. Он немного страшненький, потому что кроме идеи использовать продырявленные деревья, там ещё посягательства на организацию стека данных, а вот использование конкатенативного синтаксиса — это давно уже не ново (зато просто в написании парсера для языка). Описание не самое понятное, но если кому-то интересно, есть reference implementation на Python, ссылка там же.

[kotenok gav]

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

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

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

-- 21 мар 2020, 04:29 --

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

-- 21 мар 2020, 04:45 --

(Целые числа обозначаются кортежом $(n, 0)$ для положительных и $(-n, 1)$ для отрицательных)

substractIntegers(int1, int2) {
    num1 = car(int1)
    signInt1 = cdr(int1);
    num2 = car(int2)
    signInt2 = cdr(int2);
    ife (signInt1) {
        ife (signInt2) {
            ife ([num1] * num2) {
                return cons(substractNumbers(num1, num2), []);
            }
            ifne ([num1] * num2) {
                return cons(substractNumbers(num2, num1), [[]]);
            }
        }
        ife (signInt2 ~ [[]]) {
            return cons(addNumbers(num1, num2), []);
        }
    }
    ife (signInt1 ~ [[]]) {
        ife (signInt2) {
            return cons(addNumbers(num1, num2), [[]]);
        }
        ife (signInt2 ~ [[]]) {
            ife ([num1] * num2) {
                return cons(substractNumbers(num1, num2), [[]]);
            }
            ifne ([num1] * num2) {
                return cons(substractNumbers(num2, num1), []);
            }
        }
    }
}

[arseniiv]

kotenok gav в сообщении #1445943 писал(а):

А оптимизируется она куда? Правильно, в циклы.

(Да, но пользователь языка может спокойно об этом не думать или не знать. А циклы вон оптимизируются компилируются в условные переходы, но мы же не будем добавлять во все языки goto.)

kotenok gav в сообщении #1445943 писал(а):

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

Да, я согласен.

Вообще код с циклами конечно может быть иногда яснее кода с рекурсией. (Хотя в таком случае я бы сказал, что код с named let будет ещё яснее.)

kotenok gav в сообщении #1445943 писал(а):

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

А зачем для вычисления разности проверять? Будем вычитать хоть и в том же цикле по единице от обоих чисел, пока одно из них не занулится, и после этого решим, что вернуть, в зависимости от вида разности. Хотя хорошо, если можно сравнить числа, не сводя уже это сравнение к вычислению разности, вот это может быть удобно. (Но такое представление неэкономно пространственно, если мы об оптимизациях.)

-- Пт мар 20, 2020 23:26:19 --

А, вы про кодирование целых со знаком!

-- Пт мар 20, 2020 23:27:39 --

А в кодировании «однородными парами» не надо будет проверять, что больше чего, чтобы найти разность: достаточно просто сложить одно с обращением знака второго, а обращение знака делается сменой местами элементов пары.

[kotenok gav]

Угу. В моей записи натуральных проверка $num1\leq num2$ -

ife ([num1] * num2)

.

-- 21 мар 2020, 04:59 --

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

А в кодировании «однородными парами» не надо будет проверять, что больше чего, чтобы найти разность: достаточно просто сложить одно с обращением знака второго, а обращение знака делается сменой местами элементов пары.

Так тут тогда надо уметь складывать целые числа. А для этого тоже надо делать "больше или равно".

[kotenok gav]

addIntegers(int1, int2) {
    num1 = car(int1);
    signInt1 = cdr(int1);
    num2 = car(int2);
    signInt2 = cdr(int2);
    ife (signInt1) {
        ife (signInt2) {
            return cons(addNumbers(num1, num2), []);
        }
        ife (signInt2 ~ [[]]) {
            ife ([num1] * num2) {
                return cons(substractNumbers(num1, num2), []);
            }
            ifne ([num1] * num2) {
                return cons(substractNumbers(num2, num1), [[]]);
            }
        }
    }
    ife (signInt1 ~ [[]]) {
        ife (signInt2) {
            ife ([num1] * num2) {
                return cons(substractNumbers(num1, num2), [[]]);
            }
            ifne ([num1] * num2) {
                return cons(substractNumbers(num2, num1), []);
            }
        }
        ife (signInt2 ~ [[]]) {
            return cons(addNumbers(num1, num2), [[]]);
        }
    }
}

substractIntegers(int1, int2) {
    num2 = car(int2);
    signInt2 = cdr(int2);
    return addIntegers(int1, cons(num2, signInt2 ~ [[]]));
}

Для будущих рациональных еще надо написать целые умножение и GCD.

-- 24 мар 2020, 00:42 --

multiplyIntegers(int1, int2) {
    num1 = car(int1);
    signInt1 = cdr(int1);
    num2 = car(int2);
    signInt2 = cdr(int2);
    ife (signInt1 ~ signInt2) {
        return cons(multiplyNumbers(num1, num2), []);
     }
     ifne (signInt1 ~ signInt2) {
        return cons(multiplyNumbers(num1, num2), [[]]);
     }
}

-- 24 мар 2020, 00:48 --

А, и деление с остатком нужно.

-- 24 мар 2020, 01:11 --

divideIntegers(int1, int2) {
    num1 = car(int1);
    signInt1 = cdr(int1); //int2 - положительное число
    ife (signInt1) {
        remainder = int1;
        quotient = cons([], []);
        whilee ([remainder] * int2) {
            remainder = substractIntegers(remainder, int2);
            quotient = addIntegers(quotient, cons([[]], []));
        }
        return cons(remainder, quotient);
    }
    ife (signInt1 ~ [[]]) {
        remainder = int1;
        quotient = cons([], []);
        whilee (cdr(remainder) ~ [[]]) {
            remainder = addIntegers(remainder, int2);
            quotient = substractIntegers(quotient, cons([[]], []));
        }
        return cons(remainder, quotient);
    }
}

Кстати, я бы добавил бы в сам язык еще функции input, print и операторы else, elseife и elseifne.

[arseniiv]

Для сравнения — сложение и вычитание для целых в виде пар натуральных. Все процедуры, получая нормализованные представления, выдают нормализованное.

normalize(int) {
    pos = car(int);
    neg = cdr(int);
    ife (not(pos) + not(neg)) { // оба ненулевые
        return cons(prev(pos), prev(neg));
    }
    return int;
}

addIntegers(int1, int2) {
    pos1 = car(int1);
    pos2 = car(int2);
    neg1 = cdr(int1);
    neg2 = cdr(int2);
    return normalize(cons(add(pos1, pos2), add(neg1, neg2)));
}

negate(int) {
    pos = car(int);
    neg = cdr(int);
    return cons(neg, pos);
}

subtractIntegers(int1, int2) {
    return addIntegers(int1, negate(int2));
}

-- Пн мар 23, 2020 19:43:51 --

kotenok gav в сообщении #1446537 писал(а):

Кстати, я бы добавил бы в сам язык еще функции input, print и операторы else, elseife и elseifne.

И assert для хоть какого-то написания тестов. (Что станет полезным конечно только с появлением транслятора.)

В принципе я мог бы взяться написать на Python + parsita… но я как раз хотел поисследовать другой язык…

[kotenok gav]

Про assert я тоже думал, но можно просто if и print использовать.
Интерпретатор я сам хочу написать (тоже на Python, кстати).

[arseniiv]

(Добавление.) Да, нормализованность такого представления делает его почти таким же мало-оверхедным как и представление с явным знаком: все вычисления над нулём и чем-нибудь быстро заканчиваются. В умножении $(p, n) \cdot_{\mathsf{int}} (p', n') := (pp' + nn', pn' + np')$ в результате хотя бы одно из слагаемых в каждом элементе пары будет произведением нуля на что-то, и хотя бы в одном элементе такими будут даже оба слагаемых, так что это очень быстро упростится до солидного нуля. Чтобы все такие движения занимали здесь $O(1)$, те мои рекурсивные определения: сложение лучше поправить, чтобы оно возвращало другое слагаемое, если любое из них ноль, и аналогично с умножением.

assert как примитив хорош тем, что его можно включать только в отладочной версии, и ммм… что-то ещё было, ну и наконец запись положительного условия (что должно быть) часто понятнее, чем запись отрицательного, хотя в нашем случае ife ↔ ifne и дело в шляпе, да.

-- Пн мар 23, 2020 19:55:09 --

Ну кто первый напишем, реализацию того и будем критиковать.