Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 18:36

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 120 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 8  След.
Автор Сообщение
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Вт июн 28, 2016 09:32 
Victor__v писал(а):
Но естественно можно придумать что-нибудь понадёжней
Ну, тут два вопроса, которые надо решать по отдельности. 1. Какая хэш ф-ия Вас устроит (Если хотите "понадежней" - возьмите, например, ГОСТ)? 2. Как ее запрограммировать повыгоднее? Предлагать сразу начать с обсуждения второго - очень неочевидно.

Байка. BRAD RODRIQUEZ в своей статье PATTERNFORTH так и написал: все хорошо, осталось придумать хэш функцию.

P.S. И, конечно, удобнее делать ее в кодах.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Вт июн 28, 2016 12:26 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
MD5/CRC32

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Вт июн 28, 2016 17:25 
Не в сети
Аватара пользователя

Зарегистрирован: Вт июн 28, 2016 03:17
Сообщения: 31
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
MD5 и CRC32 это весьма разные алгоритмы в плане назначения.

MD5 - имеет большую разрядность (128 бит) и, как следствие, гигантскую область значения (340 282366 920938 463463 374607 431768 211456 вариантов) к тому же имеет некоторые претензии на "безопастность" (Сложность подбора новой последовательности, генерирующую тот же хеш, что и исходная). Применение имеет смысл при проверке целостности больших файлов или достаточно устойчивой к подмене проверке данных, например - проверка правильности пароля при аутентификации пользователей, без необходимости хранения оригинала пароля.

CRC32 - имеет вменяемую удачную для современных систем разрядность (32 бита, что весьма неожиданно, правда?) но специально разработан, что бы максимально исключить коллизии хеша на близких входных данных (небольшие ошибки при передаче данных по несовершенным каналам) Т.е. алгоритм тратит некоторое дополнительное процессорное время, что бы обеспечить получение сильно отличающихся значений хеш функции на слабо различающихся входных данных. Опять же - хорошо показывает себя при проверке целостности последовательностей данных.

Какое применение для хеш функции планируется? Может быть лучше подошло что нибудь попроще, вроде ROT13?

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

_________________
Also, liebe Kolleginnen und Kollegen,
Es werde Hölle...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Вт июн 28, 2016 23:36 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1290
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
В моём случае длина строки в среднем меньше 100 байт, в конце строки нуль он не учитывается
Можно поступить так:
: hash
dup 2 mod + 2/
>R
0 swap
r> 0
do
dup i 2* +
w@
i 1+ *
swap
>r + r>
loop
drop
;
Что это за хрень? - возникает законный вопрос.
Отвечаю, комбинация из двух элементов более редка чем из одного, а ноль в конце строки гарантирует нам корректность происходящего. Но и комбинация двух элементов могу чередоваться в разных строках, что в свою очередь даёт одинаковый хеш. Поэтому мы нашу комбинацию домножаем на порядок следования в строке ( i 1+ * ).
Так надёжней.
Где-то на десяти тысячах ведёт себя более менее неплохо. Чисто субъективное мнение, не тестировал особо.
Сейчас тестирую на большем кол-ве строк, порядка 10 млн.

Думал о CRC32
Хороший вариант в плане уникальности хеша
Да и реализация есть в СПФ
~day\common\crc.f
Скорость, однако ж, не " ура Дед Мазай приплыл!"
Что есть не очень хорошо.
Но CRC32 надёжный запасной вариант.

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Вт июн 28, 2016 23:51 
Victor__v писал(а):
В моём случае длина строки в среднем меньше 100 байт
Хэш-ф-ии выбираются не по длине строк, а по требуемой длине результата. Длина же выбирается либо для непредсказуемости, либо соответствующая количеству хранимых в хэш-таблице строк (логарифм).

Кстати, "солидные" хэш-ф-ии состоят из красивых блоков, так и просящихся под слова (или, скорее, под кодовые макросы) - сдвиги, суммирования, перестановки...


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 01:39 
Не в сети
Аватара пользователя

Зарегистрирован: Вт июн 28, 2016 03:17
Сообщения: 31
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Какая то странноватвя у тебя хеш-функция...
на нулевой бит хеша влияет только первое слово последовательности. На 31 - только слова, начиная с 65536-го, т.е. на длинах строк порядка сотни символов (50 слов), биты 23-31 хеша гарантированно остануться в нуле.

Попробуй такую хеш функцию. Быстрая, очень простая, с хорошим распределением:

Писал в блокнотике, на живом форте не проверял,

Код:
: hash ( S_ADDR, S_# -- HASH)
( Forth impletation of Serge Vakulenko's ROT13 Hash algorythm )
( Need 32 bit forth )
   0 swap 0

    do
      swap
      dup i + C@
      rot +
      dup dup
      13 lshift swap
      19 rshift or -
    loop
   swap
   drop
;


Как это должно работать:
- Инициируем хеш (обычно нулём)
- пробегаем циклом по всем символам (побайтно) строки (от 0 до длинны строки).
- - берем iтый байт
- - прибавляем его к хешу
- - делаем копию хеша, и меняем в нём порядок бит
- - - - 31-30-29-28-27-26-25-24-23-22-21-20-19-18-17-16-15-14-13-12-11-10-09-08-07-06-05-04-03-02-01-00 станет
- - - - 18-17-16-15-14-13-12-11-10-09-08-07-06-05-04-03-02-01-00-31-30-29-28-27-26-25-24-23-22-21-20-19
- - вычитаем перемешанную копию из хеша
- после цикла выкидываем из стека адресс строки.

_________________
Also, liebe Kolleginnen und Kollegen,
Es werde Hölle...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 10:30 
Господа, не понятна цель данного флуда. Ведь, повтори, выбор "хорошей хэш-ф-ии" 1) определяется конкретной задачей и 2) не имеет никакого отношения к "хитростям FORTH".

Разве, что, в отличие от других методов программирования запись
Код:
: HASH ( СТРОКА) ОБНУЛЯТОР BEGIN СИМВОЛ WHILE ДОБАВЛЯТОР REPEAT ЗАЧИЩАТОР ;

(для строки со счетчиком, очевидно, не BEGIN, а DO) имеет в FORTH смысл сама по себе, а не служит очевидной парадигмой.

Но, это, опять же, очевидно.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 12:06 
Не в сети
Аватара пользователя

Зарегистрирован: Вт июн 28, 2016 03:17
Сообщения: 31
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Ну, в общем, да. Это вопрос алгоритмики скорее.

Тогда, что бы вернуть разговор в тему хитростей и форта:

Вводная:

- Хьюстон! У нас проблемы! Наши пользователи постоянно ломают центральный терминал системы управления программой MarsCol2k16 командами вроде '0 SPACES' и 'AU 150 10 9 power * !', где C объявлено через '149597870700 CONSTANT AU'! Сделайте с этим что нибудь! Вы же обещали проблемно-ориентированное ПО!

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

_________________
Also, liebe Kolleginnen und Kollegen,
Es werde Hölle...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 12:29 
Desutorakuta писал(а):
Вопрос сложный: Как расширить язык таким образом, что бы слова стали типобезопасными?

Изображение

Ответ очевиден: предложить пользователю проблемно-ориентированный язык, на котором не нужно лезть в машинно-зависимые дебри. Калькулятор по Броуди. Генератор отчетов по Муру. Хороший пример, кстати, оконные "языки", выдаваемые на-гора визуальными программистами: куча Controls на Form, которые можно жать почти как угодно (в случае "опасности" программа переспросит).

Desutorakuta писал(а):
Как на форте реализовать работающий механизм обработки исключений
Дык, он есть изначально - чуть что, начинай сначала.


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


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 13:57 
Не в сети
Аватара пользователя

Зарегистрирован: Вт июн 28, 2016 03:17
Сообщения: 31
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
gudleifr писал(а):
Ответ очевиден: предложить пользователю проблемно-ориентированный язык, на котором не нужно лезть в машинно-зависимые дебри.


Ну, собственно к похожему решению я в конце концов и пришел. Форт слишком идеален, что бы самостоятельно быть дружественен к непоседливому пользователю. А написать сейчас что-то вроде форта, что бы потом написать на нём что-то вроде лиспа мне сейчас несколько не фонтанирует. Отложу фортификацию, пожалуй, до лучших времен, и займусь написанием чего-то вроде лиспа напрямую =).

Цитата:
Дык, он есть изначально - чуть что, начинай сначала.


Этот подход работает пока рядом сидит програамист. И пока программисту не надоест чуть-что перезапускать форт-систему. Когда мы опускаемся до '40 повернуть башня танк' этот механизм может оказаться опрометчивым.

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

Цитата:
В Афганистане двое наводчиков-наблюдателей (канадцы) подсвечивали цель для наведения на нее бомбы. После сброса бомбы в GPS-приемнике закончились батарейки. Их быстро заменили. В результате ракета прилетела не туда. Причина была в том, что после подачи питания в прибор, переменные, отвечающие за координаты цели, автоматически инициализировались (присвоили значения) координатами текущего местоположения. Наводчики погибли от близкого разрыва.

_________________
Also, liebe Kolleginnen und Kollegen,
Es werde Hölle...


Последний раз редактировалось Desutorakuta Ср июн 29, 2016 16:37, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 14:10 
Desutorakuta писал(а):
А написать сейчас что-то вроде форта, что бы потом написать на нём что-то вроде ...
Это и есть главное назначение FORTH. Другое дело, что написать на FORTH LISP - это извращение (см. рисунок выше). Гораздо проще написать на FORTH то, что ВЫ хотели написать на LISP.

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

А FORTH это и есть концепция "тупой программист - умный пользователь". Программист лишь пишет на FORTH удобный язык (BASIC), а пользователь дальше сам как-нибудь...

Desutorakuta писал(а):
не хотелось бы каждый раз терять наводчиков.
Это неизбежно:

Цитата:
"Громадные машины со всем их сложным механизмом, где так сильно чувствуется отсутствие простоты, управляются людьми, которым по природе своей свойственно ошибаться; но теперь появляется еще новая опасность от тех неисправностей, которые могут произойти в самих машинах." /Х.Р.Вильсон "Броненосцы в бою" (1896г.)/

Чем мощнее оружие, тем уже его область (... строже требования, меньше вероятность) успешного применения.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 15:30 
Не в сети
Аватара пользователя

Зарегистрирован: Вт июн 28, 2016 03:17
Сообщения: 31
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Ну, каждый раз когда я начинаю работать над какой-то интересной для меня задачей (моя работа, к сожалению, не связана с программированием, так что это почти всегда хобийные задачи) Каждый раз получается или "нетипичный лисп без REPL" (когда входные данные структурированы), "нетипичный форт без компилятора" (если данные голые), или машина состояний/конечный автомат (если задача тривиальная или я сильно стеснён в ресурсах).

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

На одной чаше весов - форт. Проще, легче, быстрее, умеет в указатели. Но склонен к крахам, трюкам, не любит структуры данных, кроме божественного стека.

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

Ну и у обоих синтаксис отпугивающий людей, надрессированы на паскали, басики и прочие 1Спредприятии.

И я пришел к выводу, что структуры и типы данных мне нужнее. А прикручивать их к форту будет излишней монстрацией.

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

_________________
Also, liebe Kolleginnen und Kollegen,
Es werde Hölle...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 15:45 
Desutorakuta писал(а):
И написание первых двух вариантов занимает обычно больше времени, чем потом реализация остального функционала. Вот я и ищу сейчас решение, что бы такое написать, что бы можно было вокруг единого ядра строить свои проекты.

В таком случае возникает вопрос: что является "естественным языком" для Вашей "машины": отладчик, BASIC, shell, Perl...

Далее входим в цикл:

Пусть у нас в наличии некоторая OC. Уровень ее нам не важен: может, полуразобранный Спектрум, может, MS Excel... Пусть это будет, даже, не ОС в полном смысле слова, для примера не важно. Нам важно, чтобы была "машина", управляемая нашими командами и для которой мы мечтаем писать программы. Для определенности/понятности возьмем, например, MS-DOS. Теперь начнем "изобретать программирование".

0) Программирование нулевого уровня - ручной ввод команд одна за другой. В MS-DOS мы так и делали. Скопировать файл, запустить игру, почистить директорий...

1) Когда мы увидели, что набирать по одной команде лениво, мы начали писать командные файлы (скрипты) - несколько команд "упакованных в одну", возможно даже с какой-то примитивной логикой "если ошибка, то...".

2) Покопавшись в компьютерных журналах, мы узнали, что командные файлы можно научить не тупо выполнять "что прошито", но и спрашивать у пользователя "чего изволите?". Правда, изначально в DOS не было никаких средств для обращения к оператору, но их можно было легко создать или спереть готовые на стороне, не суть. Главное, что мы научились писать, как определил Мур "Программы с вводом".

Пропустим следующий этап и сразу перейдем к (4):

4) Мы стали системными программистами, и можем написать свой BASIC - систему, которая позволяет нам писать программы не на убогом командном языке MS-DOS, даже не знающем, что наш IBM PC может выводить на экран графику, а на крутой машине, умеющей работать с массивами и строками, бибикать ноты и рисовать цветные линии... По сути, мы возвращаемся к (0), но уже на новом технологическом уровне - можем вводить мощные команды, писать продвинутые скрипты-программы и т.д.

Теперь заткнем дыру:

3) Мы ищем способ не только увязывать команды в скрипты, но и создавать новые простые команды (а, заодно, и способы обмена информацией и передачи управления между ними). Т.к. результатом (4) будет новый язык (проблемно-ориентированный), то есть большое искушение назвать то, что, мы делаем на этом этапе, FORTH.
Однако, как ни назови, несомненно одно: нам придется залезть внутрь нашей исходной MS-DOS машины. И начать писать не на исходном языке команд command.com, а в кодах (например, в debug.com). И большая часть нашего BASIC-интерпретатора будет в этих кодах и написана (хотя он и сможет обращаться к MS-DOS, например, для работы с файлами). В случае же использования FORTH-метода "отскок в коды" будет совсем невелик - всего десяток основополагающих слов. Но, все равно, будет.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 16:35 
Не в сети
Аватара пользователя

Зарегистрирован: Вт июн 28, 2016 03:17
Сообщения: 31
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
gudleifr писал(а):
Теперь заткнем дыру:

3) Мы ищем способ не только увязывать команды в скрипты, но и создавать новые простые команды (а, заодно, и способы обмена информацией и передачи управления между ними). Т.к. результатом (4) будет новый язык (проблемно-ориентированный), то есть большое искушение назвать то, что, мы делаем на этом этапе, FORTH.


Код:
@echo off
mkdir C:\mycmds
set PATH=%PATH%:C:\mycmds
echo set PATH=%PATH%:C:\mycmds >> c:\autoexec.bat

echo @echo off > C:\mycmds\helloworld.bat
echo echo hello world >> C:\mycmds\helloworld.bat

call helloworld.bat


Когда в MS-DOS (в третьей версии) из юникса перекочевали пайпы и перенаправления, её функциональности стало хватать, на многое. Видел где-то тетрис, написанный целиком в одном bat-файле, павда он требовал драйвер ansi.sys для работы.

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

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

gudleifr писал(а):
В таком случае возникает вопрос: что является "естественным языком" для Вашей "машины"

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

_________________
Also, liebe Kolleginnen und Kollegen,
Es werde Hölle...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Маленькие хитрости
СообщениеДобавлено: Ср июн 29, 2016 16:47 
Desutorakuta писал(а):
И можно годами писать на нём проблемно-ориентированные системы, не спускаясь к уровню железа.
Сейчас у меня висит FORTH-проект, на стеке которого лежат целиком файлы.

Desutorakuta писал(а):
Вот тут проблема...
Проблема, однако. Тут, правда, есть нюанс: до MS Excel считалось нормой сосуществование процессов-окон на уровне ОС (что вполне тянет Tcl/Tk), после все стало делаться внутри одного окна, что требует наличия некоторого WIN-API-управлятора (впрочем, довольно простого).


Вернуться к началу
  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 120 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 8  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 31


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB