Юбилей у SBCL - 10 лет!

Да, забыл добавить, что если тип указать (unsigned-byte 32), то вся арифметика будет, как ты хочешь. Позже попробую показать, что получается.

(defun pseudo-rnd (x)
  (declare (type fixnum x))
  (logand (incf x (the fixnum (ash x -5))) 256))

Дает следующее. Тут внутри функции fixnum трактуется как 29-битное число со знаком. Младшие два бита — это 0. Сдвиг вправо на пять бит, потом вытираем младшие биты, потом AND с 1024. Результат — fixnum.

;* (disassemble 'pseudo-rnd)

; 0AA19C54:       8BC8             MOV ECX, EAX               ; no-arg-parsing entry point
;       56:       C1F905           SAR ECX, 5
;       59:       83E1FC           AND ECX, -4
;       5C:       01C8             ADD EAX, ECX
;       5E:       8BC8             MOV ECX, EAX
;       60:       8BC1             MOV EAX, ECX
;       62:       8BD1             MOV EDX, ECX
;       64:       81E200040000     AND EDX, 1024
;       6A:       8D65F8           LEA ESP, [EBP-8]
;       6D:       F8               CLC
;       6E:       8B6DFC           MOV EBP, [EBP-4]
;       71:       C20400           RET 4
;       74:       90               NOP
;       75:       90               NOP
;       76:       90               NOP
;       77:       90               NOP

Теперь с (unsigned-byte 32):

(defun pseudo-rnd (x)
  (declare (type (unsigned-byte 32) x))
  (logand (incf x (the (unsigned-byte 32) (ash x -5))) 256))

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

;* (disassemble 'pseudo-rnd)

; 0A9BCB50:       8BC8             MOV ECX, EAX               ; no-arg-parsing entry point
;       52:       C1E905           SHR ECX, 5
;       55:       01C8             ADD EAX, ECX
;       57:       8BC8             MOV ECX, EAX
;       59:       8BC1             MOV EAX, ECX
;       5B:       8BD1             MOV EDX, ECX
;       5D:       81E200010000     AND EDX, 256
;       63:       C1E202           SHL EDX, 2
;       66:       8D65F8           LEA ESP, [EBP-8]
;       69:       F8               CLC
;       6A:       8B6DFC           MOV EBP, [EBP-4]
;       6D:       C20400           RET 4

An = f(An-1) - как раз итеративные обозначения

Имелся ввиду императивный алгоритм. Тут им и не пахнет: A(n) = f(A(n-1))

А вот это уже вопрос философский.

> ...

Дает следующее. Тут внутри функции fixnum трактуется как 29-битное число со знаком. Младшие два бита — это 0. Сдвиг вправо на пять бит, потом вытираем младшие биты, потом AND с 1024. Результат — fixnum.

...

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

...

кстати, LispWorks и AllegroCL для второго случая (type (unsigned-byte 32)) генерят более длинный (раза в два минимум) ассемблерный код.

почему так? хреновые компиляторы?

> Имелся ввиду императивный алгоритм. Тут им и не пахнет: A(n) = f(A(n-1))

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

Новый код ломает старый код. Это губит весь дух полиморфизма т.к полиморфизм затевался именно для избегания подобных вещей.

и где он ломает? или же где будет облом с объявлениями типа struct Warrior; ?

Visitor2 можно добавить без перекомпиляции всего остального (кроме main.cxx, использующего его конечно)

==> code.hxx <==
#ifndef CODE_HXX
#define CODE_HXX

#include "visitor.hxx"

struct Warrior;
struct Goblin;

struct AbstractPerson: public AcceptorTo<Warrior,Goblin>
{
};

struct Warrior: public AbstractPerson
{
  virtual void Accept(Visitor* v) { v->Visit0(this); }
};

struct Goblin: public AbstractPerson
{
  virtual void Accept(Visitor* v) { v->Visit1(this); }
};

#endif
==> main.cxx <==
#include "code.hxx"
#include "visitor1.hxx"
#include "visitor2.hxx"

int main()
{
  AbstractPerson::Acceptor* g = new Goblin();
  AbstractPerson::Acceptor* w = new Warrior();
  AbstractPerson::Visitor* v  = new Visitor1();
  AbstractPerson::Visitor* vv = new Visitor2();

  g->Accept(v);
  w->Accept(vv);
  return 0;
}

==> visitor1.hxx <==
#include <iostream>
#include "visitor.hxx"
#include "code.hxx"

struct Visitor1: public VisitorFor<Warrior,Goblin>
{
  void Visit0(Warrior* p) { std::cout << "Warrior "<< (void*)p <<" visited by Visitor1\n"; }
  void Visit1(Goblin* p)  { std::cout << "Goblin  "<< (void*)p <<" visited by Visitor1\n"; }
};

==> visitor2.hxx <==
#include <iostream>
#include "visitor.hxx"
#include "code.hxx"

struct Visitor2: public VisitorFor<Warrior,Goblin>
{
  void Visit0(Warrior* p) { std::cout << "Warrior "<< (void*)p <<" visited by Visitor2\n"; }
  void Visit1(Goblin* p)  { std::cout << "Goblin  "<< (void*)p <<" visited by Visitor2\n"; }
};

==> visitor.hxx <==
#ifndef VISITOR_HXX
#define VISITOR_HXX

struct AbstractVisitor {};

template<class T0, class T1> struct VisitorFor: public AbstractVisitor
{
  virtual void Visit0(T0*) = 0;
  virtual void Visit1(T1*) = 0;
};

template<class T0, class T1> struct AcceptorTo
{
  typedef AcceptorTo<T0,T1> Acceptor;
  typedef VisitorFor<T0,T1> Visitor;
  virtual void Accept(Visitor*) = 0;
};

#endif

> Дает следующее. Тут внутри функции fixnum трактуется как 29-битное число со знаком. Младшие два бита — это 0

ok, работает с приемлемой скоростью и можно написать плюсовый эквивалент специально для сравнения с лиспом

только не понятно, почему у ловсана было то 28 бит, то 29

и желательно сделать 30-битное беззнаковое целое.

кстати, LispWorks и AllegroCL для второго случая (type (unsigned-byte 32)) генерят более длинный (раза в два минимум) ассемблерный код.

А можно показать? Предполагаю, что в данном конкретном случае SBCL делает хитрую оптимизацию. Он видит, что последняя операция (logand ... 256) никогда не даст результат больше размера 29 бит. Предполагаю, что ACL и LW такую оптимизацию не делают. Достаточно убрать операцию logand, и компилятор уже не будет иметь никаких оснований предполагать, что результат (incf x (the (unsigned-byte 32) (ash x -5)) не выйдет за границы. Поэтому и код станет чуть больше и проверка результата появится (TEST). Если результат вместился, то выдаем его. Если нет, то вызываем нечто ALLOC-UNSIGNED-BIGNUM-IN-EDX (предполагаю, что тогда результат размещается в иной форме). Вот, что без logand генерится:

* (disassemble 'pseudo-rnd)

; 0A992FF0:       8BC8             MOV ECX, EAX               ; no-arg-parsing entry point
;     2FF2:       C1E905           SHR ECX, 5
;     2FF5:       01C8             ADD EAX, ECX
;     2FF7:       8BC8             MOV ECX, EAX
;     2FF9:       8BC1             MOV EAX, ECX
;     2FFB:       F7C1000000E0     TEST ECX, 3758096384
;     3001:       8D148D00000000   LEA EDX, [ECX*4]
;     3008:       7407             JEQ L0
;     300A:       8BD1             MOV EDX, ECX
;     300C:       E862D866F6       CALL #x1000873             ; ALLOC-UNSIGNED-BIGNUM-IN-EDX
;     3011: L0:   8D65F8           LEA ESP, [EBP-8]
;     3014:       F8               CLC
;     3015:       8B6DFC           MOV EBP, [EBP-4]
;     3018:       C20400           RET 4
;     301B:       90               NOP
;     301C:       90               NOP
;     301D:       90               NOP
;     301E:       90               NOP
;     301F:       90               NOP

A(n) = f(A(n-1)) - рекурсивный. так как занимаемая память не константа. ведь здесь нет аккумулирующей переменной.

A(n) = f(A(n-1)) - рекурсивный. так как занимаемая память не константа. ведь здесь нет аккумулирующей переменной.

Что - никто не помнит в чем был вопрос at the first place? При чем тут занимаемая память.

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

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

Вопрос был в тех же самых яйцах или других и Кнуте, который «математически верно описал вычислительный процесс» с его Q. Кнут все начинает с описания понятия _императивного_ алгоритма, его алгоритм это реализация функции f: Q -> Q, над Q как изменяемым состоянием - то есть как раз определенной модели из двух предложенных - то есть у Кнута яйца «по определению» те же самые, мутабельные. А это как раз и есть предмет дискуссии, об чем я и заметил - что Кнут нам тут не друг, потому что он сходу определяет алгоритм императивными понятиями.

> А можно показать?

http://paste.lisp.org/display/92177

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

>http://paste.lisp.org/display/92177

Глянул. Везде внешний CALL идет. В LW, правда, условная попытка заинлайтинь ADD есть. Другими словами, идет работа с общим представлением чисел, которые не укладываются в 29 бит. Уверен, что та же функция, но с типом fixnum даст более эффектный код.

А так, любой, ф-й алгоритм является императивным. то есть множество ф-х алгоритмов является подмножеством императивных, или не?

Депендс от интерпретирующей машины. Если в переводе на существующее железо - то да. Если нет - то это всего лишь вариант низкоуровневой реализации. То же самое что аккумулирующий параметр для реализации хвостовызовов. Для достаточного для выполнения описания алгоритма он не нужен - он нужет только для того чтобы оптимизироваться в существующий бэкэнд. Примеры где алгоритм в принципе не императивный - например XSL трансформация. Сам трансформер представляет собой неимперативную трансформирующую машину управляему правилами типа match/select.

> Глянул. Везде внешний CALL идет. В LW, правда, условная попытка заинлайтинь ADD есть. Другими словами, идет работа с общим представлением чисел, которые не укладываются в 29 бит. Уверен, что та же функция, но с типом fixnum даст более эффектный код.

не знаю насчет более эффектного, я в асме не шарю, но вот:

http://paste.lisp.org/display/92207

Юhttp://paste.lisp.org/display/92207

Что и требовалось доказать. Код стал куда эффектнее. Что в LW, что в ACL.