Собственная линейная алгебра на лиспе 1

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

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

Будем писать векторные операции для трехмерного вектора с SINGLE-FLOAT в качестве типа каждой компоненты. Массивы в лиспе создаются функцией MAKE-ARRAY. Таким образом, чтобы создать новый вектор с координатами (50 60 70) нужно написать


(make-array 3 :element-type 'single-float :initial-contents (list 50.0 60.0 70.0))


Код прост и понятен, но слишком длинный, да и запомнить такое не так просто. Хотелось бы писать что-то вроде (vec3f 50.0 60.0 70.0), и чтоб компилятор вместо этого выражения сам бы подставлял make-array с нужными параметрами. (На самом деле, в лиспе принято функции и макросы создания данных называть начиная с «make-», то есть в моём случае должно было бы быть «(make-vec3f 50.0 60.0 70.0)», но из соображений лаконичности я оставлю vec3f.) Напрашивается такой вот макрос


(defmacro vec3f (x y z) "Создание вектора по координатам"
  `(make-array 3 :element-type 'single-float :initial-contents (list ,x ,y ,z)))


Теперь уже можно писать (vec3f 50.0 60.0 70.0). Для работы с вектором крайне полезно уметь узнавать его координаты. В лиспе для доступа к элементам массива используется функция ELT, т.е. получение x-координаты вектора v можно осуществить вызовом (elt v 0), y-координаты — (elt v 1), z-координаты — (elt v 2). Подобные записи не всегда являются наглядными, многие люди (и я в том числе) привыкли к «x», «y» и «z», поэтому напрашивается еще тройка макросов:


;;; Привычное обращение к координатам вектора

(defmacro vec3f-x (v)   `(elt ,v 0))
(defmacro vec3f-y (v)   `(elt ,v 1))
(defmacro vec3f-z (v)   `(elt ,v 2))


База написана, приступаем к содержательной части. Так как я хочу добиться быстродействия и не сильно беспокоюсь за размер скомпилированного кода, — буду пользоваться преимущественно макросами, чтобы компилятор разворачивал выражения в код, использующий только MAKE-ARRAY, ELT и арифметические функции. Возможно, что это ошибочный подход, — поживём-увидим.

При помощи написанного можно сходу написать пачку полезных операторов:


(defmacro mul3f (v s) "Покомпонентное умножение вектора v на скаляр s"
  `(vec3f (* (vec3f-x ,v) ,s) 
          (* (vec3f-y ,v) ,s) 
          (* (vec3f-z ,v) ,s)))

(defmacro div3f (v s) "Покомпонентное деление вектора v на скаляр s"
  `(vec3f (/ (vec3f-x ,v) ,s) 
          (/ (vec3f-y ,v) ,s) 
          (/ (vec3f-z ,v) ,s)))

(defmacro dot3f (a b) "Скалярное произведение векторов"
  `(+ (* (vec3f-x ,a) (vec3f-x ,b)) 
      (* (vec3f-y ,a) (vec3f-y ,b))
      (* (vec3f-z ,a) (vec3f-z ,b))))

(defmacro qlen3f (v)  "Квадрат длины вектора"  `(dot3f ,v ,v))
(defmacro len3f  (v)  "Длина вектора"          `(sqrt (qlen3f ,v)))
(defmacro norm3f (v)  "Нормирование вектора"  
  `(div3f ,v (len3f ,v)))


Теперь вызов (len3f (vec3f 30.0 40.0 0.0)) выдаст «50.0». Осталось самое сложное в этом посте: сложение и вычитание векторов.

Сложность заключается в том, что мы хотим написать макрос не для сложения двух векторов, а для сложения сколь угодного кол-ва векторов. Например, (add3f a b c d) должно сложить четыре вектора.

Чтобы это провернуть, нужно задействовать сразу несколько возможностей лиспа. Во-первых, — возможность передавать произвольное кол-во параметров в функцию. Это осуществляется ключем &rest в списке параметров, тогда параметры передадутся списком.

Во-вторых, для вычисления x-координаты результата нужно собрать все x-координаты каждого вектора в список и сложить их всех. Например, если нам на вход дали список векторов (a b c d), то для получения x-координаты результата мы должны просуммировать элементы списка ((vec3f-x a) (vec3f-x b) (vec3f-x c) (vec3f-x d)).

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


(map 'list (lambda(v) (vec3f-x v)) (list (vec3f 1.0 2.0 3.0) (vec3f 4.0 5.0 6.0) (vec3f 7.0 8.0 9.0)))


вернёт список (1.0 4.0 7.0) — будет применена функция под lambda к каждому элементу под list.

Теперь вернёмся к нашим сложениям. В макросе нужно получить список выражений вида «((vec3f-x v1) (vec3f-x v2) ...)» и подставить этот список под знак суммирования в «(+ ...)». Подстановка списка в выражение осуществляется конструкцией «,@». Приходим к такому вот:


(defmacro add3f (&rest vecs) "Сложение векторов"
  `(vec3f (+ ,@(map 'list (lambda(v) `(vec3f-x ,v)) vecs)) 
          (+ ,@(map 'list (lambda(v) `(vec3f-y ,v)) vecs)) 
          (+ ,@(map 'list (lambda(v) `(vec3f-z ,v)) vecs))))


Аналогично для разности:


(defmacro sub3f (&rest vecs) "Вычитание векторов"
  `(vec3f (- ,@(map 'list (lambda(v) `(vec3f-x ,v)) vecs)) 
          (- ,@(map 'list (lambda(v) `(vec3f-y ,v)) vecs)) 
          (- ,@(map 'list (lambda(v) `(vec3f-z ,v)) vecs))))


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


(macroexpand '(add3f a b c d e f))


получим:


(MAKE-ARRAY 3 :ELEMENT-TYPE 'SINGLE-FLOAT :INITIAL-CONTENTS
    (LIST (+ (VEC3F-X A) (VEC3F-X B) (VEC3F-X C) (VEC3F-X D) 
             (VEC3F-X E) (VEC3F-X F))
          (+ (VEC3F-Y A) (VEC3F-Y B) (VEC3F-Y C) (VEC3F-Y D) 
             (VEC3F-Y E) (VEC3F-Y F))
          (+ (VEC3F-Z A) (VEC3F-Z B) (VEC3F-Z C) (VEC3F-Z D) 
             (VEC3F-Z E) (VEC3F-Z F))))


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

Реализовать функцию cross3f, вычисляющую векторное произведение, оставлю на домашнее задание. На этом пока всё.

Читать дальше......

(print "Hello world!")

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

Около месяца в свободное время проектировал стандартный набор функций и как это все должно действовать, написал интерпретатор. А сегодня я узнал о Common Lisp и осознал, что всё, что я напридумывал, уже придумали до меня.

Теперь временно приостанавливаю собственные потуги по написанию лиспа, и начинаю изучать Common Lisp :)

Читать дальше......

Печать нестандартных символов

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

Сегодня нашел удобную программу для ввода нестандартных символов — «Type It Easy».

Теперь тире и кавычки набираю комбинациями «Alt -», «Alt <» и «Alt >» соответственно. Причем прямо в редакторе, аське или браузере, т.е. «Type It Easy» действует как «Punto Switcher».

Любой юникод-символ можно таким же образом назначить на любую клавишу. Поэтому печать частоиспользуемых математических символов тоже упростилась.

Очень удобно.

Читать дальше......

dpp: лямбда-функции

Занялся написанием лямбда-функций.

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

Именно эту проблему и решают мои лямбда-функции:
FButton.OnClick := #l(Button: TButton) FWindow.Close;

Конструкция #l создает метод у класса, внутри которого она вызывается. Так записывается вызов процедуры и функции соответственно:
ObjectUpdate := #l(Obj: TMyObject) Obj.Update;
ObjectFilter := #l(Obj: TMyObject): Boolean = Obj is TSuperObject;

Внутри можно писать и несколько операторов, разделенных символом ;

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

lsimple уже реализовано и работает.

При реализации сразу же я столкнулся с множеством проблем.

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

Во-вторых, есть более серьезная проблема при использовании локальных переменных. Например, сейчас такой код не заработает:
for I := 0 to 3 do
    FButtons[I].OnClick := #l(Button: TButton) FWindows[I].Show;
хотя очень хотелось бы.

Даже если отбросить тот факт, что это сложно реализовать технически (нужно создавать промежуточный класс, который запомнит значение переменной I в момент вызова, и у этого класса могут начаться трудности в получении доступа к приватному полю FWindows, да и вообще к FWindows нужно будет каким-то макаром приписать что-то типа FOwner.FWindows), даже отбросив - совершенно непонятно сколько этот класс должен жить в памяти. Узнать когда кнопка перестанет ссылаться на метод этого класса невозможно.

Кроме того, хочется в дальнейшем делать встроенные лямбы, а не только в конце строк:
RegistHandler($10, $32, #l(Packet: TPacket) DoSomething#);
А в этом плане символ # очень неудачен, трудно определить кто из них открывающий, а кто закрывающий, и при вложенностях получится путаница.

Поэтому, наверно, будет введена конструкция [# ... #] для встроенных в строки команд.

Читать дальше......

dpp: линейные команды #assert и #return

Только что написал две новые команды, которые может обработать dpp:

#assert булево выражение
Пример вызова:
          #assert (2 + 2 = 4) and (0 = Cardinal(nil))
Проверяет истинность утверждения, если оно не выполняется - выводит в лог информацию о том в каком файле, в какой строке, когда, и какое утверждение не верно.

#return результат
Пример:
          #return ERROR_CANNOT_DO_ANYTHING
Возвращает из функции указанный результат, и выходит из функции

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


  // Line - текущая обрабатываемая строка в файле
  // Fragment - часть строки, идущая после приставки
  //            (см. StartWord в RegistLineProcessor)
  // через S возвращается то, что нужно вставить
  // вместо приставки и Fragment'а
  TLineProcessor = procedure (
                         PreProcessor: TPreProcessor;
                         const Line, Fragment: TString;
                         out S: TString
                       ) of object;


К примеру, обработчик конструкции #assert выглядит так:


procedure TDebugProcessor.AssertProcess(
      PreProcessor: TPreProcessor;
      const Line, Fragment: TString;
      out S: TString
    );
begin
  S := 'Debug.Assert(' + Fragment + ', ''' +
        PreProcessor.CurrentFileName +
        '(' + IntToStr(PreProcessor.CurrentLine) + ') ' +
        Stringalize(Fragment) + ''');';
end;


Единственное, что я прокомментирую в этом коде, - функция Stringalize преобразует строку к печатному виду. А именно, если написать
          #assert S = 'hello'
то чтобы сконструировать строку, содержащую "S = 'hello'" для печати в лог, мы должны удвоить кавычки по правилам паскаля. Именно это и делает Stringalize.

Для полного счастья осталось зарегистрировать функцию в обработчике:


PreProcessor.RegistLineProcessor('#assert', '*', AssertProcess);


Первый параметр (я его называю приставкой или StartWord) - с чего должна начинаться конструкция.

Второй параметр - паттерн, задающий как должна выглядет строка после приставки. В данном случае может быть что угодно, но, например, конструкция
          #(6, 7, 2, 'hello')-> Notifier
не имеет опознавательных знаков в приставке, и потому задается паттерном
          (*)->*
(на самом деле он другой, но это не важно).

Совершенно аналогично написан #return.

Читать дальше......

Математические символы

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

символ	описание	html	unicode
←	стрелка влево	←
↑	стрелка вверх	↑
→	стрелка вправо	→
↓	стрелка вниз	↓
↔	стрелка влево и вправо	↔
¬	Знак отрицания	¬
∧	логическое И	∧	U+2227 ISOtech
∨	логическое ИЛИ	∨	U+2228 ISOtech
∀	для всех	∀	U+2200 ISOtech
∃	существует	∃	U+2203 ISOtech
∅	пустое множество/диаметр		U+2205 ISOamso
≠	не равно	≠	U+2260 ISOtech
≡	совпадает с		U+2261 ISOtech
⊥	перпендикулярно	⊥	U+22A5 ISOtech
⊤	истина	⊤
⊦	выводимо	⊦
⊬	не выводимо	⊬
⊩	двойное выводимо	⊩
⊮	двойное не выводимо	⊮
⊪	тройное выводимо	⊪
⊨ ⊧	верно	⊨
⊭	не верно	⊭
⊫	двойное верно	⊫
⊯	двойное не верно	⊯
∈	входит	∈	U+2208 ISOtech
∉	не входит	∉	U+2209 ISOtech
⊂	является подмножеством	⊂	U+2282 ISOtech
⊃	является надмножеством	⊃	U+2283 ISOtech
⊆	является подмножеством или совпадает	⊆	U+2286 ISOtech
⊇	является надмножеством или совпадает	⊇	U+2287 ISOtech
⇒	двойная стрелка вправо	⇒	U+21D2 ISOtech
⇔	двойная стрелка влево-вправо	⇔	U+21D4 ISOamsa
∏	n-арное произведение = знак произведения	∏	U+220F ISOamsb prod
∑	n-арное суммироание	∑	U+2211 ISOamsb sum
∞	бесконечность	∞	U+221E ISOtech
∣	вертикальная палка	∣
□	незакрашенный маленький квадрат	□
■	закрашенный маленький квадрат	■
∎	закрашенный квадрат
⊡	квадрат с точкой	⊡
▣	квадрат с квадратом	▣
⊟	квадрат с горизонтальной полосой	⊟
◫	квадрат с вертикальной полоской	◫
⊞	квадрат с плюсом	⊞
▤	квадрат с горизонтальными полосами	▤
▥	квадрат с вертикальными полосами	▥
◧	лево полузакрашенный квадрат	◧
◨	право полузакрашенный квадрат	◨
◩	закрашенный квадрат с откусанным правым нижним уголком	◩
◪	закрашенный квадрат с откусанным левым верхним уголком	◪
∫	интеграл	∫
μ	мю	μ

◊ вытянутый ромб (◊) &loz;
◇ ромб &#x25C7;
◆ закрашенный ромб &#x25C6;
◈ ромб с точкой &#x25C8;

○ маленький кружочек &#x25CB;
● маленький закрашенный кружочек &#x25CF;
◌ маленький пунктирный кружочек &#x25CC;
▢ ?кружочек &#x25A2;
⊝ кружочек с минусом &#x229D;
⊖ кружочек с горизонтальной чертой &#x2296;
⊕ кружочек с плюсом &#x2295;
⊜ кружочек с двумя полосами &#x229C;
◍ кружочек с вертикальной полосатостью &#x25CD;
⊘ кружочек с косой чертой &#x2298;
⊗ кружочек с крестом &#x2297;
⊙ кружочек с точкой &#x2299;
◉ кружочек с жирной точкой &#x25C9;
⊚ кружочек с кружочком &#x229A;
◎ кружочек с большим кружочком &#x25CE;
⊛ кружочек со звездочкой &#x229B;
◐ кружочек левозакрашенный &#x25D0;
◑ кружочек правозакрашенный &#x25D1;
◒ кружочек нижнезакрашенный &#x25D2;
◓ кружочек верхнезакрашенный &#x25D3;
◔ кружочек с закрашенным верхним правым углом &#x25D4;
◕ закрашенный кружочек с незакрашенным верхним левым углом &#x25D5;

Читать дальше......

Собственный препроцессор (aka dpp)

Все больше и больше утыкаюсь в ограничения возможностей Free Pascal'я. Сегодня решил начать осуществлять свою давнюю задумку - препроцессор.

Итак, в чем заключается задумка. Есть файлы, написанные на моем расширенном паскале, имеют расширение dpp. Препроцессор просматривает папки, ищет такие файлы, и на их основе генерирует pas-файлы, которые уже можно просто скомпилировать free pascal'ем.

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

Сделано это странное ограничение для того, чтобы компилятор Free Pascal когда сообщал об ошибках, указывал бы номера строки и столбца ошибки совпадающие с соответствующими строками и столбцами в dpp-файла.

Моя утилитка dpp будет open source и ей сможет пользоваться любой желающий.

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

1) Событийную систему. К сожалению, мне не удалось на чистом fpc написать красиво отправку сообщения, поэтому ввожу такую конструкцию
#(5, 3, 'hello', Obj)-> Notifier
Она отправляет сообщение в Notifier с параметрами 5, 3, 'hello', Obj.

2) Автоматические создание и освобождение классов. Две конструкции

#autoclass(FMyClass: TMyClass) TMyExtendedClass.Create('hello')
Описывается внутри описания класса. Создает у класса поле FMyClass, которое будет автоматически создаваться во всех конструкторах вызовом TMyExtendedClass.Create('hello') и автоматически освобождаться в каждом деструкторе. По сути, время жизни поля привязывается к времени жизни хозяина - частоиспользуемая схема.

#stackclass(MyClass: TMyClass) TMyExtendedClass.Create('hello', Param1)
Описывается внутри описания метода. Автоматически создает в начале метода, автоматически уничтожает в конце

3) Система сериализации классов (для генерации кода по загрузке/сохранению). Тут немного сложнее, основные конструкции примерно такие:

#streaminterface
#streamimplementation(TMyClass)
Создает все необходимые функции по сохранению/загрузке класса TMyClass

#streamfield(FImportantValue: Integer)
Создает поле у класса, которое необходимо сохранять

4) Продвинутое RTTI.
#RTTIclass(MyRTTIVar) from TMyClass
Записывает в MyRTTIVar RTTI-информацию о классе TMyClass

5) Вставка в код название текущего файла/текущего метода/содержимого текущей строки/номера текущей строки. Очень удобно для логов.
#currentfilename_______________
#currentmethodname_____________
#currentline___________________
#currentlinenumber_____________

6) Собственно, печать в лог с указанием всей нужной инфы из пункта 5
#log 'error ' + IntToStr(ErrorId) + '!'

Пока что готов только пункт 1 :)

Читать дальше......