LINUX.ORG.RU
ФорумTalks

Про сложность языков программирования

 , , ,


1

1

Невеяло видео:
Что бесит программиста | Анастасия Лукьяненко
Ravens - Intelligent Rascals of the Skies | Free Documentary Nature
Если ворон сумел освоить тачскрин, то скоро его наймут писать софт для андроида. Ну или хотя бы веб-приложухи на JS.

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

programming languages performance benchmarks (комментарий)

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

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

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

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

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

Есть ли выход из Тьюринг-западни? То есть, существуют ли/можно ли создать инструменты, на которых сможет достаточно эффективно писать даже умственно осталая мартышка? Очевидно, есть Тьюринг-неполные языки, которые просты и достаточно мощны для некоего узкого набора задач. Регулярные выражения, SQL, в конце-концов подмножества обычных ЯП, или какая-нибудь Clojure, построенная на персистентных структурах данных с очень хорошей предсказуемостью поведения и ограничением применения макросов. Даже Rust в каком-то смысле тоже попытался пойти именно по этому направлению, то есть, через ограничение применения изменяемого состояния, характерного для Тьюринг-машины.

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

Или когда пользователь хочет отсортировать некий массив или даже банально посчитать сумму, ему совсем не обязательно писать цикл, ему не нужно проходить по массиву последовательно от первого элемента до последнего — исходный порядок здесь не имеет значения. Но Тьюринг-машины научили нас, что действия должны выполняться строго последовательно, и нынче никто уже никто не ставит под сомнение такой подход. Функциональные языки, даже весьма «чистые», имеют функции reduce, но я не видел еще ни одного языка, который имел бы реализацию reduce, безразличную к порядку прохода по элементам, вроде иерархического агрегирования аки агрегатные функции в SQL.

Одна из относительной свежих попыток решить эту проблему для разработки фронтэнда — React.js. Не Angular, который значительно сложнее и мартышку за него не посадишь, а именно React, который если и тьюринг-полон, то эту тьюринг полноту непросто достичь. С позиции программиста-пользователя React, имеет тупейше прямолинейное преобразование данных в отображение, и такую же простую функциональность для измения состояния по событиям пользователського ввода, причем, механизм «ввод->изменение модели» развязан с механизмом «модель->данные», и оба они развязаны между отдельными компонентами, потому косяки реализации мартыхой одного компонента не рушат другой.

Продолжайте список, какие инструменты/приемы вы знаете или о каких вы думали/мечтали.

PS: давно хочу вкатиться в ограниченное подмножество C++ без наследования, без зубодробильных шаблонов, с минимумом исключений. Потому что на Си неудобно писать без обобщений и замыканий. Буду благодарен за литературу и/или готовые опенсорсные проекты, реализованные в подобном стиле. Знаю, что Unity сделан в этом духе, но беда в том, что Unity проприетарен.

★★★

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

Я нхнп, но вдохновилась. Борща?

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

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

Лизка, ты ж вроде с этого акка за мальчика проходил

Harald ★★★★★ ()

Есть ли выход из Тьюринг-западни? То есть, существуют ли/можно ли создать инструменты, на которых сможет достаточно эффективно писать даже умственно осталая мартышка?

Q# + Quantum Algorithm Zoo ©.

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

Я сам борщ никогда не делал, но разве он не на свекле делается?

Миксуют же. Вот классика:

https://eda.ru/recepty/supy/borsch-mjasnoj-14622

Белокачанная капуста дает специфическую легкую остроту. Сразу подчеркну, что состав хоть и правильный, но способ приготовления по ссылке — полная дичь, не делайте так.

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

За уксус незачёт. Он портит вкус и запах и вообще не нужен. Кислоты достаточно от помидоров и капусты.

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

Хватит любой поток сознания называть философией. Ты не знаешь что такое философия.

BceM_IIpuBeT ★★★☆☆ ()

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

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

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

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

Охлол, интересно почему бы это. man ассоциативность.

t184256 ★★★★★ ()

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

В С++ не гарантируется порядок обхода при reduce. (поэтому reduce может быть многопоточным и использовать SIMD)

The behavior is non-deterministic if binary_op is not associative or not commutative.

The behavior is undefined if binary_op modifies any element or invalidates any iterator in [first; last], including the end iterator. 
in other words, reduce behaves like std::accumulate except the elements of the range may be grouped and rearranged in arbitrary order 

https://en.cppreference.com/w/cpp/algorithm/reduce

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

ограниченное подмножество C++ без наследования, без зубодробильных шаблонов, с минимумом исключений.

По описанию смахивает на Go. Но я бы лучше борща навернул.

Nervous ★★★★★ ()

Ты это, если хотел к ней подкатить просто бы куда то написал мол "НихошЪ ко мне на газировку? А у меня ещё вафэльки эеть, типа ванильныэ. А потом я тебе могу шопена на катушке тесла сыграть, ну чё мадам. Подём ко мне? " И всё. Ты слишком из далека зашёл :D

LINUX-ORG-RU ★★ ()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 1)

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

Из моих последних изысканий мне понравился Го, там есть минимум для построения другого уровня абстрактного программирования и способа мышления. Но его по-прежнему одолевают недуги своих предков… А может просто мой мозг не готов, хз :)

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

Невеяло видео

Я тоже посматриваю этот канал, но к сожалению, иногда туда зовут откровенно некомпетентных людей. И Анастасия из их числа.

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

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

Вот именно — какая разница, в каком порядке идти. Но компилятор машины Тьюринга не всегда понимает, что разницы нет.

Иерархическое агрегирование — это про то, что исходный массив данных разбит на блоки, и результат вычисления над одним блоком используется для следующего этапа вычислений. Есть еще алгоритмы сортировки, который массив отдельными блоками обрабатывают.

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

В С++ не гарантируется порядок обхода при reduce. (поэтому reduce может быть многопоточным и использовать SIMD)

Да, действительно, теперь я могу сказать, что такая реализация есть в чьей-то стандартной либе. Правда, это C++17, но в любом случае — кресты с каждым годом радуют больше и больше.

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

ограниченное подмножество C++ без наследования, без зубодробильных шаблонов, с минимумом исключений.

По описанию смахивает на Go. Но я бы лучше борща навернул

Я тоже за борщ. Go имеет сборку мусора, потому пролетает для целого ряда системщины.

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

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

Я с перлом плохо знаком — в каком месте он позволял писать мета-код? Для меня эта новость стала полным сюрпризом.

Из моих последних изысканий мне понравился Го, там есть минимум для построения другого уровня абстрактного программирования и способа мышления

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

byko3y ★★★ ()

PS: давно хочу вкатиться в ограниченное подмножество C++ без наследования, без зубодробильных шаблонов, с минимумом исключений.

RAII, std::unique_ptr/shared_ptr, лямбды, наследование интерфейсов.

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

Я тоже посматриваю этот канал, но к сожалению, иногда туда зовут откровенно некомпетентных людей. И Анастасия из их числа

Зато лицо вдувабельно. Честно говоря, я даже не смотрел и не слушал его толком. Я просто подумал, что вообще-то и я сам знаю баб-программистов, а это уже тревожный звоночек, потому что ладно курьеров садят программы писать — это можно как-то проигнорировать, а тут уже не получится, нужно реагировать. Я не отреагировал в стели «прочь из моей профессии» — нет, я не претендую на те ниши, в которых они сидят. Наоборот, я с радостью готов писать инструменты, которыми будут пользоваться все — скромная роль господа-творца меня вполне устраивет.

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

RAII, std::unique_ptr/shared_ptr, лямбды, наследование интерфейсов

Да, хороший набор. Кто-то пишет на этом?

PS:

SerenityOS

Ага, почитаю

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

Буду благодарен за литературу и/или готовые опенсорсные проекты, реализованные в подобном стиле.

Serenity OS

Kernel/FileSystem/Weakable.h
class Weakable
...
Kernel/FileSystem/RefCounted.h
class RefCountedBase
...
class RefCounted : public RefCountedBase
...
Kernel/FileSystem/Inode.h
class Inode : public RefCounted<Inode>
    , public Weakable<Inode> {
    friend class VFS;
    friend class FS;
...
Kernel/FileSystem/Ext2FileSystem.h
class Ext2FSInode final : public Inode {
    friend class Ext2FS;

Это блевотнейший стиль со множественным наследование реализации. Интерфейсы там есть, но они описаны в упомянутом выше Inode, в котором смешано множественное наследование реализации с этими самыми интерфейсами. В остальном private где ни попадя, а поскольку видимости членов класса проставлены как обычно от балды, то выясняется, что из кучи классов нужно иметь доступ к этим private членам, откуда горы классов-друзей.

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

Интерфейсы там есть, но они описаны в упомянутом выше Inode, в котором смешано множественное наследование реализации с этими самыми интерфейсами.

А как ещё если в Inode нужен счётчик ссылок? Для каждого интерфейса выдумывать свою реализацию счётчика ссылок? Тогда получится ужасный монстр COM с тоннами boilerplate кода.

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

А как ещё если в Inode нужен счётчик ссылок? Для каждого интерфейса выдумывать свою реализацию счётчика ссылок? Тогда получится ужасный монстр COM с тоннами boilerplate кода

std::shared_ptr<Inode>

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

std::shared_ptr

Он создаёт дополнительные накладные расходы в виде дополнительного объекта на куче если я не ошибаюсь. Для ядра это не желательно.

shared_ptr has a significant overhead for creation because of it’s memory allocation for the control block (which keeps the ref counter and a pointer list to all weak references). It has also a huge memory overhead because of this and the fact that std::shared_ptr is always a 2 pointer tuple (one to the object, one to the control block).

If you pass a shared_pointer to a function as a value parameter then it will be at least 10 times slower then a normal call and create lots of codes in the code segment for the stack unwinding. If you pass it by reference you get an additional indirection which can be also pretty worse in terms of performance.

https://stackoverflow.com/a/47853989

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

std::shared_ptr

Он создаёт дополнительные накладные расходы в виде дополнительного объекта на куче если я не ошибаюсь

Я в курсе накладных расходов, только RefCounted точно так же использует атомарный счетчик ссылок.

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

Я в курсе накладных расходов, только RefCounted точно так же использует атомарный счетчик ссылок.

У RefCounted счётчик ссылок находится в том же блоке памяти что и сам объект. Ссылка на объект содержит только один указатель, а не два как у shared_ptr.

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

Я тоже за борщ. Go имеет сборку мусора, потому пролетает для целого ряда системщины

А борщ разве не? Хотя вроде бы есть какие-то разновидности без сборки мусора.

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

Зато лицо вдувабельно.

Звучит не очень. Как будто ты бы вдул только в лицо.

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

У RefCounted счётчик ссылок находится в том же блоке памяти что и сам объект. Ссылка на объект содержит только один указатель, а не два как у shared_ptr

Какая разница для уровня этой ОС? Я бы еще понял, если бы это была ОС уровня прода, которая гонялась за последними процентами производительности. Современные манагеры памяти позволяют выделять малые блоки памяти с околонулевыми накладными расходами.

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

Какая разница для уровня этой ОС?

Зачем закладывать тормоза в основу ОС? В Haiku тоже есть класс BReferenceable, от которого наследуются объекты со счётчиком ссылок.

std::shared_ptr вообще противоречит парадигме C++ zero-cost абстракций.

В Си это обычно так же делается с одним блоком памяти.

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

Я сам борщ никогда не делал, но разве он не на свекле делается?

это одна из любимых тем лора по кулинарии если что

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

а я пока что в городе не встречал

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

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

Пора в оффтопик-лист добавлять.

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

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

У RefCounted счётчик ссылок находится в том же блоке памяти что и сам объект. Ссылка на объект содержит только один указатель, а не два как у shared_ptr.

у std::shared_ptr тоже может быть одна ссылка, если используется make_shared.

https://github.com/microsoft/STL/blob/1866b848f0175c3361a916680a4318e7f0cc5482/stl/inc/memory#L2771-L2776

https://github.com/microsoft/STL/blob/1866b848f0175c3361a916680a4318e7f0cc5482/stl/inc/memory#L2040-L2077

https://github.com/microsoft/STL/blob/1866b848f0175c3361a916680a4318e7f0cc5482/stl/inc/memory#L1075-L1151

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

Зачем закладывать тормоза в основу ОС? В Haiku тоже есть класс BReferenceable, от которого наследуются объекты со счётчиком ссылок.
std::shared_ptr вообще противоречит парадигме C++ zero-cost абстракций

Счетчик ссылок в принципе не может быть zero-cost. Как правило, это значит, что у тебя есть данные, которые неизвестно кем будут использованы и неизвестно когда будут освобождены — альтернативой является только сборка мусора. А основный «тормоза» там возникают именно из-за атомарного дергания счетчикам — именно потому в высокопроизводительном коде от счетчика вообще отказываются, а если подсчет ссылок действительно нужен, то изменение счетчика делают минимально возможное число раз.

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

Счетчик ссылок в принципе не может быть zero-cost.

std::shared_ptr создаёт дополнительные расходы помимо счётчика ссылок. Также там есть ещё один счётчик ссылок для слабых указателей, который обычно не нужен.

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

std::shared_ptr создаёт дополнительные расходы помимо счётчика ссылок. Также там есть ещё один счётчик ссылок для слабых указателей, который обычно не нужен

Ну ёшки-матрешки, сделайте свой, правильный shared_ptr, у которого не будет поддержки слабых ссылок. Тем более, что в сорцах Serenity немало реализаций самодельных классов-ссылок.

byko3y ★★★ ()

если программа успешно отработала на одном наборе входных данных, то нет никакой гарантии, что она успешно отработает на другом наборе входных данных;

ты изобрёл теорему Райса

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

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

ты изобрёл теорему Райса

А теперь ищем фразу «теорема Райса» на этой странице.

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

А никто не спорит, что какой-нибудь клей для тьюринг-неполных конструкций нужно писать на чем-то тьюринг-полном. Но для большей части кода тьюринг-неполных конструкций более чем достаточно, а они могут быть намного, намного проще.

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

Почему код Microsoft? GCC/Clang не осилили убрать накладные расходы?

скорее всего у них тоже что-то похожее

https://en.cppreference.com/w/cpp/memory/shared_ptr/make_shared

The storage is typically larger than sizeof(T) in order to use one allocation for both the control block of the shared pointer and the T object

fsb4000 ★★★★★ ()
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)