Сетевые игры на основе лиспа

> Статическая типизация - это просто частный случай макросов.

допустим

Только типизация, в отличии от макросов, не дает соответствующей гибкости для доказательства гарантии корректности

не понял. Почитай про монады вот здесь: http://bartoszmilewski.wordpress.com/2011/01/09/monads-for-the-curious-progra...  — очень доступно изложено, не для хаскеллеторов, а даже для С++ быдлокодеров.

А теперь поясни, что именно не даёт нам гарантий корректности: теория категорий и монады, эндофункторы, морфизмы?

Или, какой гибкости не хватает для доказательства гарантий корректности?

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

и несет нехилый оверхед.

??? Допустим, макросы тоже несут оверхед, только это оверхед времени компиляции и в рантайме его не видно. Если типизация такая, что её тоже не видно в рантайме, то откуда оверхед?

//и правда, Frag и Maze of Monads чтой-то подтормаживают.

> http://news.ycombinator.com/item?id=699146 — неплохой SML/NJ

А это точно SML? O_o

> 1. Common Lisp, CL для друзей. SBCL - одна из его реализаций.

1.5. не CL: ISLISP (ISO standarts LISP) http://en.wikipedia.org/wiki/ISLISP (ближе к CL)
EuLisp: http://en.wikipedia.org/wiki/EuLisp https://github.com/Henry/EuLisp/ (ближе к Scheme)

Лиспы, компилируемые через С и прозрачно встраиваемые в C. Типичный размер рантайма составляет 20к..900к.

SBCL содержит довольно эффективный кодогенератор, по сравнению с прочими реализациями лиспа.

4. Всякие EmacsLisp, AutoLisp и многие другие лиспы используемые для скриптинга.

сюда же можно записать и Guile

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

пеара было больше у Пола Грэхема с его Arc. А Clojure, что особенного — просто нормальная интеграция с Java + STM.

И вообще, compile-time метапрограммирование, которое здесь называют «макросами» поддерживает очень и очень много языков.

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

это совсем не SML/NJ :)
он по синтаксису ближе к питону или Си. И по фичам более полон.

> это совсем не SML/NJ :)

Уфф. А то я уже думал, что читал неправильный учебник по SML.

см. http://mythryl.org/my-Mythryl_for_SML_Programmers.html http://mythryl.org/

примеры http://mythryl.org/my-Preface-5.html

>Даже конструктивную логику привлекли,

ага, внушаить:
Г.Чейтин «Пределы доказуемости» http://elementy.ru/lib/430319

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

А можно тебе немного помочь? :) Формулировка «сетевые игры на лиспе» не совсем правильная, вот «сетевые игры» - правильная. А как писать их на лиспе - также как и на других языках. В любой такой игре главными компонентами будут:

• Интерфейс, т.е. то, что будет видеть/слышать пользователь.
  • Графика. 2D - GTK, Qt, SDL. 3D - OpenGL, DX/D3D, Ogre (+ Bullet/NGD/ODE/Havok/PhysX).
  • Звук. SDL_mixer, OpenAL.
  • Какой-либо user events loop (т.е. асинхронщина с событиями клавиатуры/мыши).

• Представление, т.е. объекты игрового мира.
  • Сериализация, server-side - файлы или БД?
  • Расшаривание, client-side - UDP или TCP?

• Сетевой протокол.
  • P2P / not P2P / mixed. WinSock, SDL_net, DirectPlay, Raw TCP / UDP.

• Логика.

Дальше всё это реализуется на языке (или на языках). Например C++ и Lua (как пример очень распостранённый). Есть разные game engines - как интегрированные, так и компонентные.

В случае Common Lisp для простых игр достаточно использовать только CL и свои велосипеды, для более сложных можно тянуть FFI к внешним библиотекам.

• Интерфейс
  • Графика - есть хорошие биндинги к Qt (CommonQt, CL-Smoke), GTK+ (cl-gtk2), SDL (LispBuilder), OpenGL (тот же LispBuilder, cl-opengl). И полусырые биндинги к Ogre и Bullet (okra). У Love5an запланирован биндинг к DX/D3D.
  • Звук - тот же LispBuilder и cl-openal.

• Представление - CLOS, есть библиотеки сериализации, но в любом случае лучше делать это вручную.

• Сетевой протокол. USockets для raw TCP / UDP и мультиплексирования. IOLib лучше, но для всего кроме Windows.

• Логика - тоже CLOS.

И ещё кое-какие замечания:

1. Ты говоришь, что под «лиспом» подразумеваешь SBCL. Дело в том, что есть большой стек библиотек-обвёрток которые писались для того, чтобы под «лиспом» подразумевался просто CL. Т.е. всегда возможно написать код который будет работать _только_, например, на SBCL. Но очень хорошо то, что почти всегда возможно написать код который будет работать на всём (почти) десятке реализаций. Поэтому нужно использовать Bordeaux-Threads (для нативных threads), CFFI (для FFI), USockets (для sockets и io-loop), IOLib (но не для Windows), Trivial-Features, Closer-MOP (для MOP) ну так далее.

2. И ещё желательно ориентироваться на ASDF2 и Quicklisp.

3. И ни в коем случае нельзя писать по-русски код :) Можно документацию.

На твоём примере x/0 - план «покорения» может быть такой:

1. Представление - создаёшь пакет game.data, пишешь объект «игровое поле», пишешь метод его сериализации/десериализации в/из потока (stream).

2. Сетевой протокол - делаешь пакет game.net, создаёшь возможность «поднимать» сетевые потоки чтобы на них вызвать методы сериализации/десериализации представлений. Можешь прочитать titurial к IOLib.

3. Дальше пакет game.gui который содержит метод render для объекта «игровое поле» и может отрисовать его (GTK+, наверное).

4. И пакет game с логикой. На двух хостах запускаются два таких приложения и общаются в режиме P2P, активность хода переключается, собственно и всё.

Ещё посмотри вот этот пост и LispMud.

на схеме под айфон тоже симпатично выглядит

По первой ссылке уже был, по второй - нет. Ну хорошо, что хорошо.

А по теме рантайм обновление нафик не нужно, даже сервера прекрасно без этого обходятся. И вся архитектура получается стройной, лаконичной и простой. Примеров тому масса (systemd, runit, supervisord, gnunet-arm и т.д.).

а я (другой анонимус) видел рантайм обновление модулями на Oberon, Java. Тоже работает, с рядом ограничений. Не пойму, при чём тут лисп. Нужна фича под названием динамическая модульность . Такую фичу можно реализовать на любом языке.

Почитай про монады вот здесь

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

Я бы даже сказал, что есть «три монадических закона» с точки зрения CL (Scheme, JS, whatever):

«Там где в Haskell, для решения некой задачи, монады только появляются, в CL такая задача оказывается уже решённой.»

«Когда в Haskell монады начинают работать, в CL уже оказывается написан макрос, который делает CL-решение более оптимальным чем... это самое монадическое.»

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

> Можно начать с того, что эта недоподелка до сих пор не поддерживает бурно развивающуюся ARM.

есть форк sbcl llvm, заброшенный в течение года. llvm умеет ARM. Но это на уровне костылей: неясно, какие оптимизации из sbcl работают в sbcl-llvm.

> Во-вторых, я не догоняю как этот ваш суперлисп будет делать обновление кода в рантайме и прочие ненужные киллерфичи, если он транслирует код в C:

в ECL есть байткод. Там есть 2 режима компиляции, в байткод и интерпретация байткода или в Си, и транслируется в си: дёргается виртуальная машина из libecl.so, но компилируется всё целиком.

В Gambit похоже, только там ещё инкрементальный линкер есть, и 2 режима линковки: flat linker (типа -static) и инкрементальный: рантайм в flat либах + (типа -dynamic) разница между либами и своим кодом.

есть форк sbcl llvm

это не форк - расширение. Но он _очень_ сырой, фактически proof of concept только.

неясно, какие оптимизации из sbcl работают в sbcl-llvm.

только compiler macros, преобразования source to source и IR1 to IR1. Ничего из IR2.

кстати, напомнил вот полезную для топикстартера ссылку: Lispbuilder-SDL и вообще Lispbuilder

пример игрушки на нём

ещё есть непонятное

да, и конечно lispgames

книжка, где на обложке жопа с ручкой про игрушки на лиспе

это к тому анонимусу, вопросы.

в контексте вот этого утверждения

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

мне вот непонятно,
1. в чем этот «нехилый оверхед» выражается (ну, допустим, монады и Maze of Monads. Или, packrat PEG parser через монады и без них (без них сильно быстрее)).
2. Что гибкость, обеспечиваемая типизацией и сопутствующей теорией (типов,категорий, монад) недостаточна для «доказательства гарантии корректности».

1. — понятно, оверхед есть. Когда вместо динамически типизированного кода нужно пользоваться монадами, монады имеют оверхед в рантайме. Это можно тупо промерить, взять какой-либо парсер комбинатор через монады и без, и померять (в packrat так и замеряли).
2. — непонятно. Корректность чего гарантируем? Как, каким мат. аппаратом доказываем корректность? Где проявляется недостаточная гибкость этого мат. аппарата?
Каким другим мат. аппаратом это проще доказать?

Отмазки «тут доказывать вообще не надо» не катят.

1)

(Just foo) >>= do'one >>= do'two >>= do'three

Без хитростей со стороны компилятора (я не знаю есть ли там rules для этого) этот код _всегда_ будет вызывать все три do'*, тогда как в коде который тут абстрагируется (т.е. поледовательность case-ов) количество вызовов может быть как 1, так 2, так и 3.

2)

Мм... Честно говоря не знаю. Haskell код всегда более точный и проверенный чем любой CL код который я видел. Так что, наверно, достаточно.

А Agda код ещё более точный и проверенный.

А TFP код вообще можно не компилировать - зачем? Мы же и так всё доказали :)

> 1. — понятно, оверхед есть. Когда вместо динамически типизированного кода нужно пользоваться монадами, монады имеют оверхед в рантайме. Это можно тупо промерить, взять какой-либо парсер комбинатор через монады и без, и померять (в packrat так и замеряли).

Оверхед не по производительности, а по количеству бойлерплейта, трудозатрат и т.п.

2. — непонятно. Корректность чего гарантируем? Как, каким мат. аппаратом доказываем корректность? Где проявляется недостаточная гибкость этого мат. аппарата?

Каким другим мат. аппаратом это проще доказать?

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

2. Что гибкость, обеспечиваемая типизацией и сопутствующей теорией (типов,категорий, монад) недостаточна для «доказательства гарантии корректности».

Она достаточна, но макросы - более гибкий и эффективный инструмент, не более того. И что это еще за такая «теория монад»? Была такая, помнится, «монадология» у Лейбница, а больше никаких теорий монад современной науке неизвестно. Используете баззворды - потрудитесь выяснить их значения.

1. в чем этот «нехилый оверхед» выражается (ну, допустим, монады и Maze of Monads. Или, packrat PEG parser через монады и без них (без них сильно быстрее)).

При чем тут вообще монады? Монады - это просто некоторый (весьма примитивный, надо сказать) прием программирования, и статическая типизация с монадами никак не связана. Первое спокойно существует без второго, а второе - без первого.

Она достаточна, но макросы - более гибкий и эффективный инструмент

Это как «на Scheme мы можем писать программы», «на ассемблере мы можем писать программы и конторолировать порты ввода-вывода» - еследовательно ассемблер более ибкий и эффективный инструмент чем Scheme.

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

> Есть пример использование «макросов» (беру в кавычки, а то мало ли - может у вас какие-то волшебные макросы, такие которые решают все проблемы) для верификации программ в больших проектах?

Ну так любое применение дсл (в том числе любое использование статической типизации).

> Это как «на Scheme мы можем писать программы», «на ассемблере мы можем писать программы и конторолировать порты ввода-вывода» - еследовательно ассемблер более ибкий и эффективный инструмент чем Scheme

Да, это толковое замечание. В некоторых задачах (в тех где контроль за логикой сводится преимущественно к «не складывать коров со слонами») простые системы типов (вроде системы типов Хаскиля, например) весьма удобны, так что иметь такую систему типов, которая будет опционально включаться/отключаться (по желанию программиста) для тех или иных участков кода, было бы неплохо. Оптимально - иметь примитивы для того, чтобы быстренько накидать систему типов.

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

простые системы типов (вроде системы типов Хаскиля, например)

Это просто?

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

Вот кстати в Haskell идут по пути расширения системы типов, вплоть до того что она должна стать настолько мощной, что её будешь не замечать. Но пока она многое ограничивает.

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

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

В GHC typechecker это как раз модуль компилятора который делает некоторое количество этих проверок (на AST!). Только в этом модуле исходников на 1MB - можно конечно реализовать всё это в языке с макросами.

Даже super-compilation это оптимизация методами AST -> AST. Так что тоже можно её осуществить макросами (правда, встанет вопрос - а не слишком ли сложны Scheme или CL как языки для такой задачи).

Вообще, для меня всегда «можно сделать» это не аргумент. Нужно либо иметь это уже сделанным или сделать хотя бы в виде доказательства такой возможности.

Спасибо, доходчиво и по полочкам. Использовать буду для графики GTK+, И начинаю понимать как всё завязать.... Рисуется всё из базы, только клиент пользует удалённую базу сервера. В принципе можно делать доступ к одной базе или тупо передавать данные или s-выражения. Переключение хода тупо флаг можно использовать. Логика чисто на лиспе тут достаточно всё тривиально. Осталось научится обмену данными между двумя приложениями (в принципе это как раз и основная трудность, возникшая изначально)...

> Это просто?

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

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

А зачем тогда система типов? Система типов изначально нужна за тем, чтобы ограничивать. И чем мощнее система типов - тем сильнее она ограничивает. Если система типов «незаметна» - это значит, что она по-просту совершенно невыразительна. Например, как в динамической ЯП - есть всего один тип. Никто такой системы типов не замечает, но и выразить с ее помощью ничего хоть сколько-нибудь полезного невозможно.

Если смотреть на макросы как на таблицу с набором функций (AST -> AST) которую компилятор использует во время генерации

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

Только в этом модуле исходников на 1MB - можно конечно реализовать всё это в языке с макросами.

Но не нужно. Система типов - это универсальное решение. И, как любое универсальное решение, оно работает плохо везде. Макросы работают «точечно».

(правда, встанет вопрос - а не слишком ли сложны Scheme или CL как языки для такой задачи)

Ну у scheme в full-expanded коде есть хорошо если с десяток основных примитивов (define/lambda/set!/if/let/аппликация - вроде все) - материал для написания супер-компилятора вполне благодатный. syntax-примитивы можно из кода исключить (на исполнение рантайма они влияния не окажут), а вот как на суперкомпиляцию могут повлиять те же продолжения - интересный вопрос.

Вообще, для меня всегда «можно сделать» это не аргумент.

Можно сделать что? Прикрутить к лиспу систему типов? Ну неоднократно уже прикручивали. Тут проблема не в том, чтобы просто прикрутить систему типов (это легко), а в совместимости типизированного/нетипизированного кода - вот тут и начинают вылазить всякие экзотичные вещи типа variable-arity polymorphism или occurrence typing.

>пример игрушки под айфон на Gambit scheme

В свое время я искал сообщество у Схемы. Не нашел. В свое время искал сообщество у Окамла. Тоже не нашел.

А вот у Хаскеля нашел. И у Скалы нашел.

>А это точно SML? O_o

Хм. Не SML, это точно. А вот насколько он близок к ML'у, не мне судить. Автор взял достаточно заброшенный SML/NJ и пилит. И было бы замечательно, если бы автор обладал культурой пользования системой контроля версий. Но вроде бы кто-то из сообщников выкинул дерево на гитхаб, но там полная тишина...

И 32 бита. По нынешним временам - не серьезно.

> Автор взял достаточно заброшенный SML/NJ и пилит

Это уже не SML. Лучше, хуже, но уже не то. Еще один язычок без сообщества.

Эх, сделали бы для Скалы родной кодогенератор.

>сюда же можно записать и Guile

Guile какбы породистая R5RS Схема. Так что точно не сюда.

Вопрос в том, насколько легко это делать.

Вопрос очень интересный. Возьмем, например, TemplateHaskell. Или возьмем MetaLua. Или возьмем Scala 2.8. Или даже сановскую Java, есть там система позволяющая при компиляции подвесить определенные хуки на различные аннотации (которые существуют только в компайл-тайме)...

Главное ходить по ссылкам :)

Я уже накатал кое-что, вот примерный workflow:

Т.к. теперь структура проекта понятна, можно сразу создать её на файловой системе:

$ mkdir -p foo/game
$ cd foo
$ echo "Ma game, itz called Foo." > README
$ echo "Its free, like free beer." > LICENSE
$ touch foo.asd game/utils.lisp game/data.lisp game/net.lisp game/render.lisp game/logic.lisp
$ emacs foo.asd &

В foo.asd загружаются зависимости (iolib flexi-streams), если их нет локально - загрузятся из сети:

;;;;
;;;; foo.asd -- ASDF definition for the game Foo.
;;;;

#+quicklisp
(progn
  (ql:quickload "iolib.sockets")
  (ql:quickload "flexi-streams"))

(asdf:defsystem game
  :depends-on (#:iolib.sockets #:flexi-streams)
  :components
  ((:module
    "game"
    :components
    ((:file "utils")
     (:file "data")
     (:file "net")
     (:file "render")
     (:file "logic"))
    )))

Тут же, в emacs, открываем файл с утилитами:

C-x C-f g*/u*

И пишем:

;;;;
;;;; utils.lisp -- some staff for our game.
;;;;

(defpackage #:game.utils
  (:use     #:common-lisp)
  (:export  #:for-each))

(in-package #:game.utils)

;;; Iterate over the list and return mapped list.
;;;
(defmacro for-each ((v list) &body body)
  `(mapcar #'(lambda (,v) ,@body) ,list))

без этого for-each неудобно мапить списки. Открываем data.lisp:

C-x C-f d*

В этом файле нужно описать игровой мир, т.е. «клетки», «линии» и «игровое поле»:

;;;;
;;;; data.lisp -- representation of the game objects.
;;;;

(defpackage #:game.data
  (:use     #:common-lisp
            #:flexi-streams
            #:game.utils)
  (:export  #:field
            #:make-field
            #:serialize
            #:de-serialize-field))

(in-package #:game.data)

;;; All types in CLOS instances has fixed slot types.
;;;
(declaim (optimize (safety 3)))

;;; Top class in hierarchy.
;;;
(defclass object ()
  ())

(defclass cell (object)
  ((value
    :initarg  :value
    :accessor value
    :type     (member 0 1)))) ;; This is go to type checker in SBCL.
                              ;; Important for the network protocol.

(defclass row (object)
  ((cells
    :initarg  :cells
    :accessor cells
    :type     list))) ;; list of cells

(defclass field (object)
  ((rows
    :initarg  :rows
    :accessor rows
    :type     list))) ;; lost of rows

;;; Migrate from the CLOS country to the Lisp country.
;;;
(defgeneric ->sexp (object)
  
  (:method ((cell cell))
    (value cell))
  
  (:method ((row row))
    (mapcar '->sexp (cells row)))
  
  (:method ((field field))
    (mapcar '->sexp (rows field))))

;;; Pretty printing.
;;;
(defmethod print-object ((cell cell) stream)
  (format stream "#<CELL ~A>" (->sexp cell)))

(defmethod print-object ((row row) stream)
  (format stream "#<ROW ~A>" (->sexp row)))

(defmethod print-object ((field field) stream)
  (format stream "#<FIELD ~A>" (->sexp field)))

;;; Convert from sexp to the filed object.
;;;
(defun make-field (sexp)
  (make-instance
   'field
   :rows (for-each (s sexp)
           (make-instance
            'row
            :cells (for-each (a s)
                     (make-instance
                      'cell
                      :value a))))))

;;; Serialize game object to the stream.
;;;
;;;   Protocol specification:
;;;
;;;     0, 1 -- cells
;;;     2    -- end of row
;;;     3    -- end of filed
;;;
(defconstant +end-of-row+   2)
(defconstant +end-of-field+ 3)

(defgeneric serialize (object stream)

  (:method ((cell cell) stream)
    (write-byte (value cell) stream))

  (:method ((row row) stream)
    (for-each (cell (cells row))
      (serialize cell stream))
    (write-byte +end-of-row+ stream))
  
  (:method ((field field) stream)
    (for-each (row (rows field))
      (serialize row stream))
    (write-byte +end-of-field+ stream)))

;;; De-serialise game objects from the stream.
;;;
(defun de-serialize-cell (stream)
  (read-byte stream))

(defun de-serialize-row (stream)
  (let (byte row)
    (loop
       (setf byte (de-serialize-cell stream))
       (if (= byte +end-of-row+)
           (return-from de-serialize-row row)
           (push byte row)))))

(defun de-serialize-field (stream)
  (let (byte row field)
    (loop
      (setf row (de-serialize-row stream))
      (setf byte (peek-byte stream))
      (if (= byte +end-of-field+)
          (progn
            (read-byte stream)
            (return-from de-serialize-field (push row field)))
          (push row field)))))

;;; Test objects equality.
;;;
(defgeneric equal-p (object1 object2)

  (:method ((cell1 cell) (cell2 cell))
    (= (value cell1) (value cell2)))

  (:method ((row1 row) (row2 row))
    (loop :for cell1 :in (cells row1)
          :for cell2 :in (cells row2)
          :unless (equal-p cell1 cell2)
          :do (return-from equal-p nil))
    t)
  
  (:method ((field1 field) (field2 field))
    (loop :for row1 :in (rows field1)
          :for row2 :in (rows field2)
          :unless (equal-p row1 row2)
          :do (return-from equal-p nil))
    t))

;;; Tests
;;;
(defun test-serializer (file)
  (let ((field (make-field '((1 0 0) (0 1 0) (0 0 1)))))
    (with-open-file (s file :direction :output :element-type 'unsigned-byte)
      (serialize field s))
    (unless (equal-p field
                     (with-open-file (s file :direction :input :element-type 'unsigned-byte)
                       (setf s (make-flexi-stream s))
                       (de-serialize-field s)))
      (error "Serializer fails!")))
  (values))

Методы сериализации / десериализации в конце это основное - на самом деле можно воспользоваться мощью read / write и посылать игровой мир через сеть сразу в s-выражениях, но это лшишком жирно. Библиотеки сериализации тоже - непонятно что они генерируют на бинарном уровне. Поэтому эти методы создают свой (лёгкий) бинарный протокол, поле 3 x 3 будет весить 9+3+1 = 13 байт (на самом деле, можно упаковать в 2 байта путём битовых операций, можно даже сразу использовать именно битовые потоки, а не байтовые).

Вот, и тут есть тест - игровое поле сериализируется в файл, потом востанавливается. С сокетами будет то же самое. На уровне CL дескриптор сокета мало отличается от дескриптора файла у open / with-open-file.

Сетевая часть (net.lisp):

C-x C-f n*

;;;;
;;;; net.lisp -- do net :0
;;;;

(defpackage #:game.net
  (:use     #:common-lisp
            #:flexi-streams
            #:iolib.sockets
            #:game.utils
            #:game.data)
  (:export  #:user
            #:make-user
            #:me
            #:make-me
            #:get-world
            #:share-world))

(in-package #:game.net)

;;; USER representation -- somebody who in the game.
;;;
(defclass user ()
  ((name
    :initarg  :name
    :initform "anonymous"
    :reader   name
    :type     string)
   (host
    :initarg :host
    :reader  host
    :type    string)
   (port
    :initarg :port
    :reader  port
    :type    fixnum))) ;; port

(defun make-user (host port)
  (make-instance 'user :port port :host host))

;;; TODO: central server representation (if needed).

;;; This is me and I'am the user.
;;;
(defclass me (user)
  ())

(defun make-me (name port)
  (make-instance 'me :name name :port port :host "127.0.0.1"))

;;; Get world state from the user (or server).
;;;
(defgeneric get-world (user))

;;; Shere world state for the users (or server).
;;;
(defgeneric share-world (world me))

;;; All sockets staff is there!
;;;
;;;   Do TCP/IP.
;;;
(defun %get-world (host port peer)
  (with-open-socket (socket :connect         :active
                            :address-family  :internet
                            :type            :stream
                            :external-format '(:utf-8 :eol-style :crlf)
                            :ipv6            nil)
    (connect socket host :port port :wait t)
    (handler-case (progn
                    (setf socket (make-flexi-stream socket))
                    (de-serialize-field socket)) ;; ! look there,
                                                 ;; ! is the function from the game.data.
      (end-of-file ()
        (format t "<break> Peer ~A closed connection!~%" peer)))))

(defmethod get-world ((user user))
  (let ((host (lookup-hostname (host user)))
        (port (port user))
        (peer (name user)))
    (handler-case
        (%get-world host port peer)
      (socket-connection-refused-error ()
        (format t "<break> Connection refused to ~A (~A:~A). Maybe peer is not there?~%"
                peer host port)))))

(defmethod share-world ((world field) (me me))
  (with-open-socket (server :connect         :passive
                            :address-family  :internet
                            :type            :stream
                            :ipv6            nil
                            :external-format '(:utf-8 :eol-style :crlf))
    (bind-address server +ipv4-unspecified+ :port (port me) :reuse-addr t)
    (listen-on server :backlog 5)
    (loop
      (with-accept-connection (client server :wait t)
        (handler-case
            (progn
              (serialize world client)
              (finish-output client))
          (socket-connection-reset-error ()
            (format t "<break> Peer reset connection!~%"))
          (hangup ()
            (format t "<break> Peer closed conection!~%")))))
    ; (finish-output) in term of `deleting unreachable code'
    ))

render.lisp - пустой, но там нужно отрисовать поле с помощью Gtk или Qt. logic.lisp с логикой тоже пустой, только пакет для финальных эксперементов:

C-x C-f l*

;;;;
;;;; logic.lisp -- top level logic.
;;;;

(defpackage #:game.logic
  (:use     #:common-lisp
            #:game.data
            #:game.net)
  (:export  #:main))

(in-package #:game.logic)

Теперь можно попробывать - открываем два емакса и запускаем два SBCL. В обоих пишем:

(load "foo.asd")
(require :game)
(in-package #:game.logic)

В одном создаём «мир» и «себя»:

(defvar world (make-field '((0 0 0) (0 0 0) (0 0 0))))
; world
; => #<FIELD ((0 0 0) (0 0 0) (0 0 0))>
(defvar me (make-me "I'am" 8080))

и пытаемся расшарить свой мир:

(share-world world me)

управление не возвращается - это правильно, т.к. это запустился loop, раздающий мир.

В другом емаксе создаём «его» («я» в первом емаксе) и пытаемся получить его картину мира:

(defvar he (make-user "127.0.0.1" 8080))
(get-world he)
((0 0 0) (0 0 0) (0 0 0))

т.е. мир получили. Далее можно его изменить (т.е. лучше написать метод для совершения хода - он или меняет мир по setf, либо создаёт новый мир, тогда аккссоры у классов не нужны - только ридеры) и опубликовать. Остаются вопросы синхронизации. Можно, например, оставить share-world таким же, но запускать в отдельном потоке (тянем bt) и лочить во время изменения. Что касается глобальной синхронизации - создаётся класс world (уже field != world) и миру добавляется «мьютекс» (или другой примитив IPC), это нужно, чтобы не возникали коллизии вида множественных миров, т.е. чтобы все видели один и тот же мир.

>Эх, сделали бы для Скалы родной кодогенератор.

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

>Ну нет, в лиспе макросы шире.

S-выражения в лиспе — это способ записи лямбда-термов. А значит «макросы» изоморфны конструктивной логике. Значит на их основе можно строить систему типов.

Это одна из простейших систем типов, существующих на данный момент.

А что тогда сложнее? Зависимые типы Мартина-Лёфа и только тотальные функции? Ну они на самом деле не намного сильнее отличаются.

а про разрешимость я вообще молчу.

Та ссылка на System FC, ЕМНИП, система F уже не разрешима в чистом виде, а FC несколько сложнее.

Например, как в динамической ЯП

Ну вот, если вы определите экзистенциальный тип forall a. a -> Un, где Un это GADTs и добавите сюда возможность case по таким объектам - вы получите возможность писать как в динамическом языке с одним типом (Un). Т.е. система типов на месте - она ограничивает всё, но весь код в духе Un уже имеет другие свойства. Это своего рода рефлективность системы типов. Возможность просто оперировать с типом Any (но про возможность оперировать типами на уровне значений (которые типизируются), я конечно промолчу :)).

Ну нет, в лиспе макросы шире.

Именно так это реализовано. Я сказал - есть таблица пользовательских функции экспансии и компилятор её использует. Как он её использует - уже другой вопрос (call by macro expansion).

Ну у scheme в full-expanded коде есть хорошо если с десяток основных примитивов -

У CL - ажно 26. У HaskellCore 5-6 (плюс переменные / литералы). И это при том, что эксперименты пока ведутся на подмножестве Core.

(define/lambda/set!/if/let/аппликация - вроде все)

define это явно не отсюда, define это штука которая как раз суёт пару (символ . лямбда) в окружение. if это частный случай case, который также является основой для паттерн матчинга. Ещё добавьте сюда аппликацию (которую не видно за скобками) и кастование (если есть). И как раз получится HaskellCore. Но set! - он может убить всю идею, я сам знаю расширения TI для присваивания и примитива последовательного исполнения, но не знаю ничего о работах по SC языка без ссылочной прозрачности. Может уже есть такое?

материал для написания супер-компилятора вполне благодатный.

Для scheme - возможно. Но зачем Scheme пытается постоянно стать хаскельнее хаскеля - есть же хаскель.

Можно сделать что? Прикрутить к лиспу систему типов?

Да, мне показалось что там про это было (может псто другого анонимуса).

define это явно не отсюда

точне это просто (set! environment (cons (cons name lambda) environment))

> А что тогда сложнее? Зависимые типы Мартина-Лёфа и только тотальные функции?

Зависимые типы, CoC, сабтайпинг + что угодно, мир лямбда-кубом не ограничивается.

система F уже не разрешима в чистом виде

Для нее только вывод типов неразрешим (при полиморфизме выше 2 ранга) а тайпчек вполне себе разрешим.

Именно так это реализовано. Я сказал - есть таблица пользовательских функции экспансии и компилятор её использует. Как он её использует - уже другой вопрос (call by macro expansion).

Да нет, не так. Вы забываете, что у макросов есть сайдэффекты, так что к АСТ -> АСТ все свести нельзя. Потому что макрос невозможно смоделировать, как чистую функцию.

У CL - ажно 26. У HaskellCore 5-6 (плюс переменные / литералы). И это при том, что эксперименты пока ведутся на подмножестве Core.

Ну можно вообще только аппликацией и абстракцией обойтись, важно, чтобы набор форм был не только минимален, но и практичен.

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

Если редуцировать define до set-а, то с такой программой вообще ничего сделать будет нельзя. Чуть менее чем во всех реализациях define - спецформа.

if это частный случай case, который также является основой для паттерн матчинга.

Только наоборот :) Паттерн-матчинг - частный случай case, который выражается через if.

Но set! - он может убить всю идею, я сам знаю расширения TI для присваивания и примитива последовательного исполнения, но не знаю ничего о работах по SC языка без ссылочной прозрачности. Может уже есть такое?

Ну в расширениях рефала вроде есть присваивание. А лучше рефала языка для суперкомпиляции, по-моему, пока не придумали :)

Для scheme - возможно. Но зачем Scheme пытается постоянно стать хаскельнее хаскеля - есть же хаскель.

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

Да

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

CoC, сабтайпинг

Ура! Новые слова :)

Вы забываете, что у макросов есть сайдэффекты, так что к АСТ -> АСТ все свести нельзя.

Сайд эффекты у маросов существуют потому, что в теле макроса обычный код на языке (а не какой-то DSL) - если в самом языке есть присваивание, то и в макросах оно есть (если мы не ограничиваемся гигиеной). Но никто не использует сайд эффекты в маросах. Так как макросы имеют единственное назначение (AST -> AST, смещение вычислений в compile time), то этот код в их телах (в которых, в принципе, можно воздействовать на что-то извне макросов) используют только для этого (AST -> AST). И реализации заботятся только тем какой AST отдать в макрос (пользовательская функция раскрытия) и только тем, какой AST оттуда получить. Я не особо знаю Scheme (в смысле того, как принято писать прямо сейчас), так что если вы расскажите, что в Scheme в макросах воздействуют на окружающий мир - я очень удивлюсь. В CL такого нет.

Ну можно вообще только аппликацией и абстракцией обойтись, важно, чтобы набор форм был не только минимален, но и практичен.

Не, я не коцепты, я про реальные языки стараюсь говорить.

Для нее только вывод типов неразрешим (при полиморфизме выше 2 ранга) а тайпчек вполне себе разрешим.

Ну, осоновную ценность играет TI.

Если редуцировать define до set-а, то с такой программой вообще ничего сделать будет нельзя. Чуть менее чем во всех реализациях define - спецформа.

Ну вот, я не разбирал ни одной серьёзной реализации Scheme. Но по крайней мере в трёх реализациях ЯП с тайп чекингом я видел отсутсвие аналога define в core - нет там ничего подобного.

Т.е. это что-то такое scheme-специфичное. Вместо этого обычно разделяют let на рекурсивный (именно там замкнутые функции могут быть) и нерекурсивный).

if это частный случай case, который также является основой для паттерн матчинга.

Только наоборот :) Паттерн-матчинг - частный случай case, который выражается через if.

Вот я и говорю, что паттерн-матчинг превращается в case («case, который также является основой для паттерн матчинга»), а if это:

if' True  y z = y
if' False y z = z

что раскрывается в

if' x y z = case x of { True -> y; False -> z }

т.е. if - частный случай case (вы не найдёте if в core). Как вы будуте через if выражать матчинг по произвольным АТД?

А, да, в Scheme case это то же, что макрос case в CL который превращается в цепочку if-ов :) Даже в SICP об этом есть. Не, я про ML/хаскельный (TAPL-овый) case - по конструкторам.

Во-первых - причем тут хаскель вообще?

Для меня это пример «правильных вещей», т.е. логичной реализации того о чём мы начали тут говорить (но, модет, уже не самой правильной. Например, существование АТД и классов типов это ведь всего существование возможностей высказываться о принадлежности множеств к U (АТД) или U'(классы типов), но ведь можно и про U" говорить, и смешивать все U* в любом высказывании). Scheme изначально не был таким - сдвиг в typed scheme, в удобный матчинг, ленивость (в виде расширений) и прочее (всё что появляется в Racket, что заставляет говорить о нём как о новом языке, отличном от Scheme) - всё это я и имел ввиду.

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

Вот если будет индукция идей со стороны Scheme тогда я с вами соглашусь. Сейчас есть ряд идей которые ещё не «долетели» до Scheme.

Во-первых - неоднократно прикручивали (и пруверы прикручивали, которые по определению мощнее системы типов хаскеля), во-вторых - это само по себе никому не надо, а надо другое.

Ну вот, кто-то что-то в paper написал, но реально нифига нет. А что тогда нужно?

в cl-ных макросах на окружающий мир воздействуют обильно.
Нюанс, правда, в том, что обычно не в самих макросах, а в
(eval-when (:compile-toplevel :load-toplevel :execute) ...)

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

eval-when - условие на состояние окружающего мира. Как если бы в макросе был код (if *config* ...) - зависимость от внешней переменной.

Например макрос defun вроде как влияет на окружающий мир, но это не так - defun раскрывается как раз в eval-when (условие на состояние стадии выполнения) + %defun (про SBCL), т.е. единственный смысл defun как преобразователя AST это подготовка аргументов для %defun. А %defun это функция, она просто делает setf на fdefinition, т.е. тот самый побочный эффект.

Ну и потом нужно отделять макросы верхнего уровня (которые суть _специальные формы_ реализованные как макросы, то что делает этот язык CL - если их поменять, будет уже не то) от остальных макросов. Одни могут на что-то повлиять, а другим трудно придумать ещё применение кроме как сделать из кода код.

Если ваша реализация тут:

(funcall (macro-function 'defun) '(nil plus (a b) (+ a b)) nil)

меняет мир вместо AST->AST, то она по меньшей мере странная. В этих терминах никакой макрос не меняет мир, его меняет раскрытый код :)

Разве что

(defmacro foo ()
  (setq a '|Моя раскрыться!|)
  `())

(funcall (macro-function 'foo) '(nil) nil)
;=> NIL

; a
;=> |Моя раскрыться!|

но кто так пишет?

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

Это вообще распространенная практика - в одном, обычно toplevel, макросе что-то в (eval-when (:compile-topelvel ...) ...) определить, а потом его из других макросов использовать. А после этого, возможно, еще и переопределить и по-другому использовать(оное, кстати, происходит каждый раз при загрузке измененного файла).

Это не чистое ast->ast преобразование, потому что неявным(а может даже и явным!) параметром выступает состояние системы. И это именно то, что делает CL CL.

>> define это явно не отсюда

точне это просто (set! environment (cons (cons name lambda) environment))

анонимус говорил не про внутреннюю реализацию define, а про раскрытие. define в set! раскрыть нельзя, т.к. set! нельзя применять к неопределенным переменным, а локальные define в свою очередь можно писать только перед остальными формами тела. так в r5rs и r6rs.

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

Операция «чтение» не является побочным эффектом (о чём идёт речь), side effect это операция «запись». То что в макросах можно опираться на внешнии параметры - это понятно, но их не изменишь до back-quote (вопрос дизайна, конечно).

не чистое ast->ast преобразование

«нечистое» ast->ast преобразование, ок - язык-то тоже «нечистый» :)

Да, с define разобрался. Как примитив на уровне реализации - может быть, но вообще это лишний примитив - есть let.

обычно toplevel, макросе что-то в (eval-when (:compile-topelvel ...) ...) определить, а потом его из других макросов использовать

Т.е. есть toplevel макросы которые определяют переменные до обратной кавычки, прямо во время раскрытия?

> Но никто не использует сайд эффекты в маросах.

Чушь полная. Сайдэффекты в макросах постоянно применяются и _только_ за счет этого макросистема лиспа действительно сильна и позволяет делать то, что позволяет.

В CL такого нет.

Как это нет? Есть. На чем, по-вашему, основана система пекеджей?

Не, я не коцепты, я про реальные языки стараюсь говорить.

Ну вот я тоже про реальные.

Ну, осоновную ценность играет TI.

TI = тайпинференс? Ну он вообще никакой особой роли не играет, а full тайпинференс вообще, как известно, очень вредная вещь. И вводить в язык тайпинференс надо очень осторожно. Пока что наиболее правильным решением мне кажется разрешать вывод типов только для локальных переменных, но даже такого ограничения в общем случае не достаточно.

Ну вот, я не разбирал ни одной серьёзной реализации Scheme. Но по крайней мере в трёх реализациях ЯП с тайп чекингом я видел отсутсвие аналога define в core - нет там ничего подобного.

Ну в любом статически типизированном языке define либо аналог всегда есть в core, т.к. выразить эту конструкцию в рамках статического ЯП из примитивов невозможно - в данном случае все типы существуют исключительно в рантайме «виртуальной машины». А вообще речь тут шла о суперкомпиляции и любом другом анализе программы - если define выразить через (set! environment ...) то такая программа никакому анализу поддаваться не будет, т.к. мы не будем иметь доступа к тому самому environment во время этого анализа. Грубо говоря мы о такой программе не сможемсказать вообще ничего полезного.

а if это

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

т.е. if - частный случай case

case - последовательность вложенных ифов.

Как вы будуте через if выражать матчинг по произвольным АТД?

Ну так как это везде делается. Паттерн-матчинг и аналогичные конструкции вообще нельзя совать в core - они слишком сложны. Такой core будет бесполезен.

Не, я про ML/хаскельный (TAPL-овый) case - по конструкторам.

Ну это та же самая цепочка ифов.

Scheme изначально не был таким - сдвиг в typed scheme, в удобный матчинг, ленивость (в виде расширений) и прочее (всё что появляется в Racket, что заставляет говорить о нём как о новом языке, отличном от Scheme) - всё это я и имел ввиду.

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

Сейчас есть ряд идей которые ещё не «долетели» до Scheme.

Это какие?

А что тогда нужно?

Нужно понять, что лисп - это не хаскель. Не надо пытаться писать на хаскеле так, как на лиспе. Или на лиспе так, как на хаскеле. И делать из лиспа/хаскеля хаскель/лисп - не нужно. Там одинаковые задачи решаются разными средствами. И развивать следует именно эти средства, а просто тупо «перенести фичу» из однго ЯП в другой никому на хрен не надо. Эту фичу просто никто не будет использовать.

Ну вот, кто-то что-то в paper написал

Да нет, реализации же есть. Просто их никто не использует. Потому что не lisp-way.

Чушь полная. Сайдэффекты в макросах постоянно применяются и _только_ за счет этого макросистема лиспа действительно сильна и позволяет делать то, что позволяет.

Приводите контрпример. Я утверждаю, что все пряморукие реализации делают стандартные макрос функциями вида AST->AST которые не имеют побочных эффектов на этапе раскрытия (и все пряморукие пользовательские макросы в библиотеках).

Как это проверить:

(funcall (macro-function 'defun) '(nil plus (a b) (+ a b)) nil)

ничего не делает кроме генерации кода (который уже имеет влияние на рантайм).

Как это нет? Есть. На чем, по-вашему, основана система пекеджей?

Ещё раз:

(funcall (macro-function 'defpackage) '(nil package (:use :cl)) nil)

не имеет побочного эффекта, а только генерирует код который его производит (функция %defpackage). Вот в пряморуком SBCL можно проследить тенденцию такой аккуратности во всех макросах.

Впрочем, это мы уже сместились в обсуждения рантайма, а не языка (весь код можно записать без toplevel вещей, только средствами самого языка).

Ну он вообще никакой особой роли не играет

Ага, знать все типы на этапе компиляции - действительно, кому это нужно? :) Schemer-ам не нужно? Вот в GCC - нужно, можно ведь не boxed integer неограниченной длинны вида:

struct ... {
  TYPE type;
  long* n;
}

аллоцировать, а элементарно в регистрах всё поместить. И в CL тоже есть свой TI и прибивание типами термов, разве что динамикой нельзя поступится (типа (setf *use-static-typing* t)) чтобы делать суровый TI.

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

Это в scheme ;) Во всём остальном мире nested pattern matching ... и тут длинная такая хреновина с огромным количеством CASE-оф. И кроме case-оф ничего больше не нужно.

Ну это та же самая цепочка ифов.

Нет.

Разведём немного типологии:

data ABC = A | B | C

show' x
  = case x of
    A -> "A"
    B -> "B"
    C -> "C"

show'' x
  = if x == A
    then "A"
    else if x == B
         then "B"
         else "C"

При определении АТД принято транслировать эти АТД в некое упакованное бинарное представление. Первый show (можно ещё паттерн матчингом записать, но не суть) выражен через примитив case (который в core), второй - через последовательность if-ов. Какая разница? Последовательность if-ов выполняется последовательно (много операций), и каждый раз выполняет тяжёлую (ну или лёгкую, тоже не суть) операцию сравнения (==). А вот case производит всего одну (!) очень лёгкую операцию (в духе битовых масок - в core АТД ведь упакованы в лёгкое бинарное представление, как я сказал).

Про это есть в «Implementation of Functional Programming Language» (есть книжка и более поздний титуриал).

Ну так как это везде делается. Паттерн-матчинг и аналогичные конструкции вообще нельзя совать в core - они слишком сложны. Такой core будет бесполезен.

Ну а ячто писал - паттерн матчинг не в Core, он превращается в case - он в Core. If не в core :)

Ну это все с хаскелем никак не связано.

Ну хорошо, допустим это моё субъективное мнение.

Это какие?

Ну раз миграция идей отсутсвует по вашему - то, наверное, не важно.

Нужно понять, что лисп - это не хаскель. Не надо пытаться писать на хаскеле так, как на лиспе.

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

Там одинаковые задачи решаются разными средствами.

Точно, абсолютно по разному решаются одни и те же задичи. Какой curring, point free, рекурсия и ФВП - есть же итераторы! :)

Да нет, реализации же есть.

А есть нормальная и открытая для CL? (кроме Stela, то другой язык над CL). Это ведь был бы очевидный профит для качества кодогенерации (да и для проверок на некий класс ошибок).