Реализован простейший язык для тестирования на зацикливания - Философия программирования

Здраствуйте!

Реализовал транслятор простейшего языка программирования.
Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
и если зависает то на каких наборах данных.

Вот описание языка:
* This is specification of Simple Language *
* Copyright (c) 2009 PETR PETROV *

* This is an example of comment *

* Please note that indentifiers are case-sentensive *

* now we declares subprogram *
SUBPROGRAM someSubProgram
* now we declares that our subprogram accepts "arg1" as argument and has int8 type (like "char" type in C) *
INPUT arg1 TYPE int8
* output variable *
OUTPUT res1 TYPE int8
* temporary variables (local variables) default values are zeros *
VAR temp0 TYPE int8
VAR temp1 TYPE int8
* subprogram body begins *
BEGIN
* set "temp1" variable to "13" value *
SET temp1 13
* declare label with name *
LABEL abc
* If arg1 == temp1 then goto label abc *
IFEQUAL arg1 temp1 GOTO abc EIF
* arg1 = arg1 — 1 *
DEC arg1
* res1 = res1 + 1 *
INC res1
* res1 = res1 + 1 *
INC res1
* If arg1 == temp0 then goto label end *
IFEQUAL arg1 temp0 GOTO end EIF
* goto abc *
GOTO abc
LABEL end
END

* PROGRAM is similar to SUBPROGRAM but defines the entry point of the application *
* PROGRAM must be single in entire file *
* input variables can be entered by user *

PROGRAM ProgramA
INPUT arg1 TYPE int8
OUTPUT res1 TYPE int8
VAR localVar TYPE int8
BEGIN
CALL someSubProgram arg1 res1
END

* some features of Simple Language *
SUBPROGRAM example
INPUT arg1 TYPE int8
OUTPUT res1 TYPE int8
VAR temp0 TYPE int8
BEGIN
* set the value of variable *
SET temp0 50
* res1 = arg1 *
LET res1 arg1
* if arg1 > arg1 then goto label1 else label2 *
IFGREAT arg1 arg2 GOTO label1 ELSE label2
* if arg1 < arg1 then goto label1 else label2 *
IFLESS arg1 arg2 GOTO label1 ELSE label2
* res1 = arg1 / temp0 *
DIV res1 arg1 temp0
* res1 = arg1 & temp0 *
MOD res1 arg1 temp0
* res1 = arg1 x temp0 *
MUL res1 arg1 temp0
* res1 = arg1 + temp0 *
ADD res1 arg1 temp0
* res1 = arg1 — temp0 *
SUB res1 arg1 temp0

* calling a subprogram someSubProgram(temp0,res1) *
CALL someSubProgram temp0 res1

END

Реализовал также и сам анализатор, который определяет зацикливается ли входной алгоритм или нет.

С Уважением,
Петр

01.03.09 15:35: Перенесено из 'Shareware и бизнес'

Здравствуйте, GhostCoders, Вы писали:

GC>Здраствуйте!

И вам не хворать.
Можно объяснить, каким боком эта набившая оскомину тема относится к Shareware и бизнесу?

GC>Реализовал транслятор простейшего языка программирования.
GC>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>и если зависает то на каких наборах данных.

Слушай, это случайно не твой сайт здесь ?

Здравствуйте, retalik, Вы писали:

R>И вам не хворать.
R>Можно объяснить, каким боком эта набившая оскомину тема относится к Shareware и бизнесу?

Его же в философии без соли съедят

Здравствуйте, GhostCoders, Вы писали:

GC>Реализовал транслятор простейшего языка программирования.

Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
http://rsdn.ru/forum/Default.aspx?mid=3307978
и узнать, наконец-то ответ!

GC>* now we declares subprogram *

Лучше бы по-русски писал, все равно это не английский.

Здравствуйте, D. Mon, Вы писали:

DM>Здравствуйте, GhostCoders, Вы писали:

GC>>Реализовал транслятор простейшего языка программирования.

DM>Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
DM>http://rsdn.ru/forum/Default.aspx?mid=3307978
DM>и узнать, наконец-то ответ!

Вот пример данной функции на этом языке:

* This is function from RomikT *

PROGRAM RomikT
INPUT n TYPE int8
OUTPUT res TYPE int8
VAR value_1 TYPE int8
VAR value_2 TYPE int8
VAR value_3 TYPE int8
VAR value_0 TYPE int8
VAR temp0 TYPE int8
BEGIN
SET value_1 1
SET value_2 2
SET value_3 3
SET value_0 0
LABEL while_cycle
IFEQUAL n value_1 GOTO end EIF
MOD temp0 n value_2
IFEQUAL temp0 value_0 GOTO _even EIF
MUL n n value_3
INC n
GOTO c_cont
LABEL _even
DIV n n value_2
LABEL c_cont
GOTO while_cycle
LABEL end
LET res n
END

Вот результат работы моего анализатора (только первая часть, так как случаев с зависанием много):
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 0
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 15
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 23
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 30
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 35
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 39
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 45
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 46
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 49
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 53

.... и т.д.
и в конце немного "статистики".
RESULTS:
total : 256
halted: 146
passed: 110
Q = 0.570313 (то самое "магическое" омега, которое было описано здесь: http://elementy.ru/lib/430319)

Здравствуйте, Kubyshev Andrey, Вы писали:

GC>>Реализовал транслятор простейшего языка программирования.
GC>>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>>и если зависает то на каких наборах данных.

KA>Слушай, это случайно не твой сайт здесь ?
Нет, сайт не мой, но сайт моего партнера здесь http://www.pdf3d.co.uk

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, retalik, Вы писали:

R>>И вам не хворать.
R>>Можно объяснить, каким боком эта набившая оскомину тема относится к Shareware и бизнесу?

FR>Его же в философии без соли съедят

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

Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, D. Mon, Вы писали:

DM>>Здравствуйте, GhostCoders, Вы писали:

GC>>>Реализовал транслятор простейшего языка программирования.

DM>>Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
DM>>http://rsdn.ru/forum/Default.aspx?mid=3307978
DM>>и узнать, наконец-то ответ!

GC>Вот пример данной функции на этом языке:

GC>* This is function from RomikT *

GC>PROGRAM RomikT
GC>INPUT n TYPE int8

Как бы так помягче выразиться.. С какого перепугу N тут int8? "Анализатор" тупо перебирает все возможные значения входных параметров??

Автор, это уже не смешно. Реальная клиника.

Здравствуйте, GhostCoders, Вы писали:

GC>Реализовал транслятор простейшего языка программирования.
GC>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>и если зависает то на каких наборах данных.

Интересно получилось

И так быстро!

Так что там с одним из предложенных тестовых заданиий:

"Если где-либо в дробной части числа "пи" встречается последовательность цифр 84327411834783744390087539249 — завершить цикл"

?
Что на это скажет анализатор?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, GhostCoders, Вы писали:

GC>>Здравствуйте, D. Mon, Вы писали:

DM>>>Здравствуйте, GhostCoders, Вы писали:

GC>>>>Реализовал транслятор простейшего языка программирования.

DM>>>Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
DM>>>http://rsdn.ru/forum/Default.aspx?mid=3307978
DM>>>и узнать, наконец-то ответ!

GC>>Вот пример данной функции на этом языке:

GC>>* This is function from RomikT *

GC>>PROGRAM RomikT
GC>>INPUT n TYPE int8

А>Как бы так помягче выразиться.. С какого перепугу N тут int8? "Анализатор" тупо перебирает все возможные значения входных параметров??

А почему бы и нет?

Здравствуйте, GhostCoders, Вы писали:

GC>Реализовал транслятор простейшего языка программирования.

Мне почему-то сразу вот это напомнило:
http://www.rus-os.narod.ru

Здравствуйте, Alexey F, Вы писали:

AF>Здравствуйте, GhostCoders, Вы писали:

GC>>Реализовал транслятор простейшего языка программирования.
GC>>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>>и если зависает то на каких наборах данных.

AF>Интересно получилось

И так быстро!

AF>Так что там с одним из предложенных тестовых заданиий:
AF>

AF>"Если где-либо в дробной части числа "пи" встречается последовательность цифр 84327411834783744390087539249 — завершить цикл"

AF>?
AF>Что на это скажет анализатор?

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

Мой анализатор проверит это дело, то только до того знака, до которого позволяет float.

Можно использовать double, точность болше, знаков после запятой тоже. Но число знаков тоже КОНЕЧНО.

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

Здравствуйте, PolyTech, Вы писали:

PT>Здравствуйте, GhostCoders, Вы писали:

GC>>Реализовал транслятор простейшего языка программирования.

PT>Мне почему-то сразу вот это напомнило:
PT>http://www.rus-os.narod.ru

а мне нет

Здравствуйте, GhostCoders, Вы писали:

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

Пардон, всё же мне надо чётче формулировать свои мысли

Число "пи" было взято как пример числа, вычисление которого с бесконечной точностью занимает бесконечное время, причём мы не можем предугадать, какое число появится следующим при следующей итерации вычислений. Ближайший аналог — ГСЧ, если условиться, что генерируемые им числа не предсказуемы.
Т.е.:

// Якобы, следующее число в "пи" :)
int getNextNumberInPi () {
    return std::rand () % 10;
}

будет достаточно

Здравствуйте, Alexey F, Вы писали:

AF>Здравствуйте, GhostCoders, Вы писали:

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

AF>Пардон, всё же мне надо чётче формулировать свои мысли

AF>Число "пи" было взято как пример числа, вычисление которого с бесконечной точностью занимает бесконечное время, причём мы не можем предугадать, какое число появится следующим при следующей итерации вычислений. Ближайший аналог — ГСЧ, если условиться, что генерируемые им числа не предсказуемы.

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

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

Здравствуйте, GhostCoders, Вы писали:

GC>Вот только если условиться. На самом деле, если не использовать никаких апаратных средств (использование ввода пользователя), а только обходиться исключительно самой программой для генерации случайных чисел ->
GC>это генерация псевдослучайных чисел.
Конечно условиться

Эта условность накладывает ограничение на анализатор — он не должен знать устройство getNextNumberInPi.

GC>Тем более если "пи" вычисляется с бесконечной точностью бесконечное время то необходимо сохранять результат вычислений,
GC>а на это потребуется бесконечная память.
Зря я "пи" в пример привёл

Представьте себе, что есть некая волшебная функция getNextNumberInPi, которая возвращает очередное дробное число в числе "пи" (может, это число считает пользователь и по одной цифре с клавиатуры вводит

). Для того, чтобы узнать:

встречается последовательность цифр 8432741183478374439008753924

или нет, нам потребуется буфер для хранения всего лишь strlen ( "8432741183478374439008753924" ) == 28 символов. Первый же несовпавший символ очищает буфер и всё начинается сначала.

Здравствуйте, Alexey F, Вы писали:

AF>Здравствуйте, GhostCoders, Вы писали:

GC>>Тем более если "пи" вычисляется с бесконечной точностью бесконечное время то необходимо сохранять результат вычислений,
GC>>а на это потребуется бесконечная память.
AF>Зря я "пи" в пример привёл

AF>Представьте себе, что есть некая волшебная функция getNextNumberInPi, которая возвращает очередное дробное число в числе "пи" (может, это число считает пользователь и по одной цифре с клавиатуры вводит

). Для того, чтобы узнать:
AF>

AF>встречается последовательность цифр 8432741183478374439008753924

AF>или нет, нам потребуется буфер для хранения всего лишь strlen ( "8432741183478374439008753924" ) == 28 символов. Первый же несовпавший символ очищает буфер и всё начинается сначала.

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

Python 2.5.1 (r251:54863, Apr 18 2007, 08:51:08) [MSC v.1310 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> 123 ** 123
11437436793461719009988029522806627674621807845185022977588797505236950478566689
64466065683652015421696499747277306288423453431965811348959199428208744498372120
99476648958359023796078549041949007807220625356526926729664064846685758382803707
100766740220839267L

Здравствуйте, GhostCoders, Вы писали:

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

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

GC>Мой анализатор проверит это дело, то только до того знака, до которого позволяет float.

Насколько быстрее чем методом простого перебора, к примеру?

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

А если не бесконечное чило бит а просто очень большое? Определить зацикливание не сложно... Видимо все дело в скорости... Насколько быстр ваш алгоритм?

	От:	GhostCoders
	Дата:	01.03.09 00:43
	Оценка:	4 (1)

От:	retalik	www.airbandits.com/
Дата:	01.03.09 01:55
Оценка:

	От:	Kubyshev Andrey
	Дата:	01.03.09 05:36
	Оценка:

	От:	FR
	Дата:	01.03.09 05:55
	Оценка:

От:	D. Mon	http://thedeemon.livejournal.com
Дата:	01.03.09 07:20
Оценка:	+1

От:	PolyTech	https://vmpsoft.com
Дата:	01.03.09 11:05
Оценка: