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

Мы напишем МКЭ для расчёта упругой двумерной пластины на прочность и жёсткость. Код займёт 1200 строк. Туда войдёт всё: интерактивный редактор, разбиение модели на треугольные элементы, вычисление напряжений и деформаций, визуализация результата. Ни одна часть алгоритма не спрячется от нас в недрах MATLAB или NumPy. Код будет ужасно неоптимальным, но максимально ясным.

Размышление над задачей и написание кода заняли у меня неделю. Будь у меня перед глазами такая статья, как эта, — справился бы быстрее. У меня её не было. Зато теперь она есть у вас.

Только что вышла новая версия 1.3 моего встраиваемого скриптового языка Umka со статической типизацией. С момента выпуска версии 1.0 язык пополнился замыканиями, инструкцией выбора switch по фактическому типу интерфейса, тернарным условным оператором, более удобным API для взаимодействия с кодом на C, другими мелкими радостями.

Маленькое, но упрямое сообщество пользователей Umka всерьёз озаботилось библиотеками, появился менеджер пакетов UmBox, загружающий и устанавливающий библиотеки и отслеживающий их зависимости.

Umka живёт в ядре фреймворка Tophat для создания 2D игр. На основе этого фреймворка развивается платформер-головоломка SaveScum. Коллекция пробных уровней для игры была выпущена в декабре в виде адвент-календаря, принеся с собой дух простого геймерского счастья в наш проект.

После трёх лет неторопливой разработки вышла версия 1.0 моего скриптового языка Umka. Это статически типизированный язык, предназначенный для встраивания в программы на C/C++. Синтаксис и некоторые особенности семантики Umka были вдохновлены языком Go, однако Umka никак не зависит от экосистемы Go и не требует для работы ничего, кроме стандартной библиотеки C.

Основным применением языка стал игровой фреймворк Tophat, созданный Марком Машкаринцем. Версия Tophat 1.0 вышла одновременно с Umka. Это очень простой модульный фреймворк для создания 2D игр. Несколько мини-игр на нём были написаны для участия в джемах. Сейчас в разработке находятся два более крупных игровых проекта — платформер-головоломка и игра о диспетчеризации железнодорожного движения.

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

Вдохновением для этих занятий послужила замечательная статья из Science, которая убедила меня и многих других в том, что к таким задачам в принципе можно подступиться. Как и у авторов статьи, наш пример будет немного игрушечным, хоть и для совсем другой физической системы. Более того, мы ещё сильнее ограничим пространство поиска (до формул, что тоже немало), зато обойдёмся без 32 процессорных ядер и без GPU, а решение получим меньше чем за минуту против десятков минут или даже пары дней, как в статье. Для всего этого нам понадобится лишь 300 строк кода на C — и никаких фреймворков.

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

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

Итак, обсудим четыре ключевых практических проблемы, с которыми пришлось столкнуться при реализации подсчёта ссылок в языке Umka.

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

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

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

Разработка моего статически типизированного скриптового языка Umka вошла в ту стадию, когда потребовалась проверка языковых возможностей на более сложных примерах, чем скрипты в пару десятков строк. Для этого я решил реализовать на своём языке интерпретатор Lisp. На это меня вдохновил педагогический эксперимент Роба Пайка, одного из создателей языка Go. Недавно Пайк опубликовал маленький интерпретатор Lisp на Go. Особенно впечатлило замечание Пайка, что описание интерпретатора заключено на одной странице 13 древнего руководства по Lisp 1.5. Учитывая синтаксическое родство Umka и Go, было трудно не поддаться соблазну построить такой интерпретатор на Umka, но не буквальным переносом кода Пайка, а полностью заново, от основ. Надеюсь, знатоки Lisp и функциональных языков простят мне наивное изумление от соприкосновения с прекрасным.

Origins

О чём речь

Истоки