Автор Тема: Приспособим PureBuilder для разработки игр  (Прочитано 42286 раз)

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Приспособим PureBuilder для разработки игр
« : Февраль 17, 2011, 03:43:16 am »
Цитата: Сергей Прохоренко
Уже полгода на моем рабочем столе лежит презентация The Next Mainstream Programming Language: A Game Developer’s Perspective - крик души разработчика игр. Лежит как напоминание о том, что хороший структурный редактор должен соответствовать этим ясно выраженным потребностям. Должен признать, что предложенные автором решения мне понравились. А компьютерные игры - это передовой край Computer Science, эталон пригодности инструментального программного обеспечения к решению сложных задач.

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

По поводу нулевых указателей и неинициализированных переменных. Я уже выступал на оригинальном форуме (http://forum.oberoncore.ru) и наверняка есть ЯП в которых эта проблема в каком то виде решена, но если подытожить применительно к оберону и структурному редактору, то основные тезисы такие:
- Неинициализированных переменных нет, потому что объявление переменной совмещено с ее инициализацией синтаксически. A-ля VAR i: INTEGER := 3.
- Указатели по умолчанию ненулевые (обязаны быть проинициализированы реальным объектом или другим ненулевым указателем).
- Можно объявить нулевой указатель. Это другой тип, совместимый с ненулевым указателем в одну сторону: ненулевой указатель может быть приведен к нулевому, но не наоборот. Нулевой указатель не может быть разыменован.
- Для получения ненулевого указателя из нулевого есть специальная синтаксическая конструкция вроде обероновской проверки/приведения типа с помощью WITH. Если проверка сработала, то выполняется ветка кода, где "виден" ненулевой указатель.

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #1 : Февраль 17, 2011, 06:29:47 am »
В том моём сообщении, исковерканном Темиргалеевым (да ещё и с оскорбительной уничижительной пометкой "экспертное" -- именно в кавычках) я по пунктам ответил Сергею Прохоренко, что фактически ничего этого в КП/ББ нет, даже сборщик мусора -- и тот не реалтаймный (GC, замораживающий мир, в интерактивных играх типа Unreal неприемлем).
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #2 : Февраль 17, 2011, 07:34:27 am »
Я вообще говоря долго думал о эффективном и при этом безопасном языке. Безопасный -- я имею ввиду проверка на ошибки на этапе компиляции. Эффективный -- проверка ИСКЛЮЧИТЕЛЬНО на этапе компиляции.

В частности проверка численных переполнений и выход за границы массива.

Таки вот, я пришел к выводу, что сделать подобное для тьюринг-полного языка невозможно (я это даже помнится доказал). Следовательно нужно попробовать построить тьюринг-не полный подъязык. Кроме того, мне интуитивно кажется, что процентов 90 всего кода в современных приложениях может быть писано на таком вот подъязыке. Я пробовал на наколеночном прототипе написать quicksort -- получилось. И оно даже внятней смотрелось, чем вариант даденый Виртом в своей книжке.

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

Вот как-то так.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #3 : Февраль 17, 2011, 07:38:33 am »
Т.е. программа должна получаться верна по построению. Не должно быть зацикливаний, выходов за границы, численных переполнений.

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

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #4 : Февраль 17, 2011, 07:52:08 am »
Кстати, если мне память не изменяет, то языки с зависимыми типами, вроде Agda и т.п., где как раз на этапе компиляции проверяется всё от и до, не являются тьюринг полными (точнее то их подмножество где всё это как раз проверяется и доказывается). Правда они таки функциональные, я мне хочется тут императивный. Ну и хочется без столь страшной доказательной математике (я не верю что масс-программист её осилит, собственно даже хаскеля народ боится).
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #5 : Февраль 17, 2011, 08:13:31 am »
Я пробовал на наколеночном прототипе написать quicksort -- получилось.
И как оно выглядит?

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #6 : Февраль 17, 2011, 08:17:45 am »
Я в конфу кидал исходник. Но тогда вроде бы логи не велись ещё, поэтому оно пока кануло в лету. :-)
Постараюсь на выходных восстановить.

Там небыло while'ов. Там небыло произвольного доступа к индексам массивов. Циклы шли четко по множествам индексов, на каждой итерации цикла выкидывался из множества индексов как минимум один индекс (можно выкинуть больше). Добавить во множество индексов ничего нельзя. Из цикла можно преждевременно выйти (break), потому как этот выход на безопасность алгоритма никак не влияет (с т.з. выходов за границы, целочисленного переполнения и т.п.).

У меня проблемы случились позже, после qsort'a -- я попытался построить алгоритм с экспоненциальной сложностью, и у меня с ходу не получилось это вменяемо сделать. Надо думать дальше.
« Последнее редактирование: Февраль 17, 2011, 08:22:08 am от valexey »
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #7 : Февраль 17, 2011, 08:45:14 am »
Надо бы выделить эти размышления о таком безопасном языке в отдельную тему...

Проверки на отсутствие зацикливаний -- это уже из области тотального ФП -- там все функции заведомо завершаемые, то есть полностью вычислимые.
А для работы с бесконечными циклами -- а такие тоже иногда нужны -- корекурсия, то есть типа кофункции.
Всё никак не могу заставить себя перевести статью Дэвида Тёрнера про тотальное ФП. Надо сделать -- небольшая она...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #8 : Февраль 17, 2011, 09:27:52 am »
Ну, мой тезис таков, что это может быть не ФП, а вполне себе ИП, но не тьюринг полное просто. Т.е. это ортогонально ФП и ИП. Кстати, такой мелкий и убогий язычок очень пригодился бы для, например, написания nif'ов в ерланге (где важна как раз надежность, скорость и гарантированное завершение за определеный квант времени).

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

Почему я говорю именно про ИЯ? Потому, что для не тьюринг-полного языка не нужна иммутабельность. По кр. мере тотальная иммутабельность. В общем, тут можно и нужно много о чем ещё подумать, поэкспериментировать. Любые коментарии мысли (даже в порядке полного бреда) приветствуются.

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

Galkov

  • Newbie
  • *
  • Сообщений: 3
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #9 : Февраль 17, 2011, 10:43:58 am »
Потому, что для не тьюринг-полного языка не нужна иммутабельность. По кр. мере тотальная иммутабельность.
Хм...
Вот помню цитату из Лебедя (сам слышал): "у нас в армии на такое говорили - не делайте умное лицо, ведь Вы же Офицер!!!"

В смысле - разжуйте по буквам эту цитату. Честное слово, я быстро учусь  :D


А, да... ВСЕМ ПРИВЕТ !!!


valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #10 : Февраль 17, 2011, 10:52:12 am »
Т.е. в отличае от современного ФП, где грубо говоря нет присваиваний вообще и нет изменения значений чего-либо, в императивном не тьюринг полном языке, я думаю что можно будет разрешить некоторые типы изменений по крайней мере локальных переменных.

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

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #11 : Февраль 17, 2011, 11:35:26 am »
Всё же мне кажется, что можно сделать вполне внутри настоящий чистый и тотальный язык, но замаскировать его таким синтаксисом, что будет похоже на ИЯ, но с такими ограничениями, которые дадут ему безопасность.
Под маскировкой я имею в виду, например, библиотеку Language.Basic в Хаскелле, позволяющую писать на Хаскелле такие во программы:
{-# OPTIONS_GHC -fno-warn-type-defaults #-}
{-# LANGUAGE ExtendedDefaultRules, OverloadedStrings #-}
module HiLo where
import Language.BASIC

main :: IO ()
main = runBASIC $ do
    10 GOSUB 1000
    20 PRINT "* Welcome to HiLo *"
    30 GOSUB 1000

    100 LET I := INT(100 * RND(X))
--    110 PRINT I
    200 PRINT "Guess my number:"
    210 INPUT X
    220 LET S := SGN(I-X)
    230 IF S <> 0 THEN 300

    240 FOR X := 1 TO 5
    250  PRINT X*X;" You won!"
    260 NEXT X
    270 STOP

    300 IF S <> 1 THEN 400
    310 PRINT "Your guess ";X;" is too low."
    320 GOTO 200

    400 PRINT "Your guess ";X;" is too high."
    410 GOTO 200

    1000 PRINT "*******************"
    1010 RETURN

    9999 END
http://augustss.blogspot.com/2009/02/regression-they-say-that-as-you-get.html
« Последнее редактирование: Февраль 17, 2011, 11:39:33 am от Geniepro »
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #12 : Февраль 17, 2011, 11:45:25 am »
Да, я тоже полагаю что на хаскеле можно сделать такой EDSL и с типизацией там будет всё хорошо. Хаскель тем и хорош, что там можно обкатывать новые парадигмы :-) Собственно для того он и делался, делается и будет делаться.

Но в последствии неплохо бы иметь отдельный компилятор для такого язычка. Потому как ghc это явный оверкил :-)

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

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #13 : Февраль 17, 2011, 12:59:53 pm »
Т.е. программа должна получаться верна по построению. Не должно быть зацикливаний, выходов за границы, численных переполнений.

А чем, собственно, зацикливание отличается от просто очень долгого алгоритма? С точки зрения конечного результата в виде "зависания".

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re:Приспособим PureBuilder для разработки игр
« Ответ #14 : Февраль 17, 2011, 01:03:58 pm »
А чем, собственно, зацикливание отличается от просто очень долгого алгоритма? С точки зрения конечного результата в виде "зависания".
Ну, очень долгий алгоритм в конце концов всё же завершится с каким-то результатом, а зацикливание типа "10 GOTO 10" не завершится никогда.
При определённом подходе к программированию (например тотальное ФП) можно получить гарантию того, что алгоритм рано или поздно завершится, а иначе программа просто не скомпилируется из-за ошибки типизации.
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…