Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Obviously I was either onto something, or on something. -- Larry Wall on the creation of Perl

programming / comp.lang.asm.x86 / Infinite recursion detection criteria (Please correct me if I am

SubjectAuthor
* Infinite recursion detection criteria (Please correct me if I amolcott
+- Re: Infinite recursion detection criteria (Please correct me if I amolcott
`- Re: Infinite recursion detection criteria (Please correct me if I amKaz Kylheku

1
Subject: Infinite recursion detection criteria (Please correct me if I am
From: olcott
Newsgroups: comp.theory, comp.lang.c, comp.lang.c++, comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sat, 17 Apr 2021 14:15 UTC
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.theory,comp.lang.c,comp.lang.c++,comp.lang.asm.x86
Subject: Infinite recursion detection criteria (Please correct me if I am
Date: Sat, 17 Apr 2021 09:15:14 -0500
Organization: A noiseless patient Spider
Lines: 15
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <HridnZf_Jp3tcOf9nZ2dnUU7-KfNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="b0950cef0f32972b8c4a305d29b98026";
logging-data="764"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19wGGQ/hs3uSgwZwaUJsi4+qz9GeyJCxh8="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.9.1
Cancel-Lock: sha1:Z8bMWUqHxW+nPvgjAOwvki8I1LE=
View all headers
If a function X() is called by function Y() twice in sequence from the same machine address of Y() with the same parameters to X() and the execution trace shows no conditional branch instructions in Y() or function call returns in X() then the function call from Y() to X() is infinitely recursive unless X() stops it.

The referenced excution trace is on x86 machine language, disassembled for human consumption.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre minds." Einstein



Subject: Re: Infinite recursion detection criteria (Please correct me if I am
From: olcott
Newsgroups: comp.theory, comp.lang.c, comp.lang.c++, comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Sat, 17 Apr 2021 16:01 UTC
References: 1
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.theory,comp.lang.c,comp.lang.c++,comp.lang.asm.x86
Subject: Re: Infinite recursion detection criteria (Please correct me if I am
Date: Sat, 17 Apr 2021 11:01:42 -0500
Organization: A noiseless patient Spider
Lines: 94
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <4LKdnStuf-7-m-b9nZ2dnUU7-e_NnZ2d@giganews.com>
References: <HridnZf_Jp3tcOf9nZ2dnUU7-KfNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="b0950cef0f32972b8c4a305d29b98026";
logging-data="12665"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Hi4Z1Ks+DxPWggWjhJfh19XjuFUeomW8="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.9.1
Cancel-Lock: sha1:jpFcZ3P387s5q/00tcuTiXefObo=
View all headers
On 4/17/2021 9:15 AM, olcott wrote:
If a function X() is called by function Y() twice in sequence from the same machine address of Y() with the same parameters to X() and the execution trace shows no conditional branch instructions in Y() or function call returns in X() then the function call from Y() to X() is infinitely recursive unless X() stops it.

The referenced execution trace is on x86 machine language, disassembled for human consumption.


When Halts() uses an x86 emulator to simulate its input and maintains an execution trace of this emulation then it can examine this execution trace according to the above criteria and correctly decide that Y() is invoking X() in infinite recursion. On this basis it can stop simulating Y() and report that Y() would not halt unless its execution was aborted by Halts().

void Y(u32 P)
   Halts(P, P);
}


int main()
{
   Halts((u32)Y, (u32)Y);
}


_Y()
[000009ac](01)  55                      push ebp
[000009ad](02)  8bec                    mov ebp,esp
[000009af](03)  8b4508                  mov eax,[ebp+08]
[000009b2](01)  50                      push eax
[000009b3](03)  8b4d08                  mov ecx,[ebp+08]
[000009b6](01)  51                      push ecx
[000009b7](05)  e840feffff              call 000007fc
[000009bc](03)  83c408                  add esp,+08
[000009bf](01)  5d                      pop ebp
[000009c0](01)  c3                      ret
Size in bytes:(0021) [000009c0]

_main()
[000009cc](01)  55                      push ebp
[000009cd](02)  8bec                    mov ebp,esp
[000009cf](05)  68ac090000              push 000009ac
[000009d4](05)  68ac090000              push 000009ac
[000009d9](05)  e81efeffff              call 000007fc
[000009de](03)  83c408                  add esp,+08
[000009e1](02)  33c0                    xor eax,eax
[000009e3](01)  5d                      pop ebp
[000009e4](01)  c3                      ret
Size in bytes:(0025) [000009e4]

===============================
.....[000009cc][00011278][00000000](01)  55                      push ebp
.....[000009cd][00011278][00000000](02)  8bec                    mov ebp,esp
.....[000009cf][00011274][000009ac](05)  68ac090000              push 000009ac
.....[000009d4][00011270][000009ac](05)  68ac090000              push 000009ac
.....[000009d9][0001126c][000009de](05)  e81efeffff              call 000007fc
Begin Local Halt Decider Simulation at Machine Address:9ac
.....[000009ac][00031318][0003131c](01)  55                      push ebp
.....[000009ad][00031318][0003131c](02)  8bec                    mov ebp,esp
.....[000009af][00031318][0003131c](03)  8b4508                  mov eax,[ebp+08]
.....[000009b2][00031314][000009ac](01)  50                      push eax
.....[000009b3][00031314][000009ac](03)  8b4d08                  mov ecx,[ebp+08]
.....[000009b6][00031310][000009ac](01)  51                      push ecx
.....[000009b7][0003130c][000009bc](05)  e840feffff              call 000007fc
.....[000009ac][0007bd40][0007bd44](01)  55                      push ebp
.....[000009ad][0007bd40][0007bd44](02)  8bec                    mov ebp,esp
.....[000009af][0007bd40][0007bd44](03)  8b4508                  mov eax,[ebp+08]
.....[000009b2][0007bd3c][000009ac](01)  50                      push eax
.....[000009b3][0007bd3c][000009ac](03)  8b4d08                  mov ecx,[ebp+08]
.....[000009b6][0007bd38][000009ac](01)  51                      push ecx
.....[000009b7][0007bd34][000009bc](05)  e840feffff              call 000007fc
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
.....[000009de][00011278][00000000](03)  83c408                  add esp,+08
.....[000009e1][00011278][00000000](02)  33c0                    xor eax,eax
.....[000009e3][0001127c][00010000](01)  5d                      pop ebp
.....[000009e4][00011280][00000058](01)  c3                      ret
Number_of_User_Instructions(23)
Number of Instructions Executed(16920)
sizeof(Decoded_Line_Of_Code)(24)

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre minds." Einstein



Subject: Re: Infinite recursion detection criteria (Please correct me if I am
From: Kaz Kylheku
Newsgroups: comp.theory, comp.lang.c, comp.lang.c++, comp.lang.asm.x86
Followup: comp.lang.c
Organization: A noiseless patient Spider
Date: Sat, 17 Apr 2021 15:01 UTC
References: 1
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: 563-365-...@nospicedham.kylheku.com (Kaz Kylheku)
Newsgroups: comp.theory,comp.lang.c,comp.lang.c++,comp.lang.asm.x86
Subject: Re: Infinite recursion detection criteria (Please correct me if I am
Followup-To: comp.lang.c
Date: Sat, 17 Apr 2021 15:01:03 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 59
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <20210417074758.258@kylheku.com>
References: <HridnZf_Jp3tcOf9nZ2dnUU7-KfNnZ2d@giganews.com>
Injection-Info: reader02.eternal-september.org; posting-host="6f10c6db12fd65a62e680b6260b17350";
logging-data="18138"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX183ZoLRRo9scUj0lNyfGEg7mUq6JtYwMys="
User-Agent: slrn/1.0.3 (Linux)
Cancel-Lock: sha1:hbE4m2ZXGBud9PU3FB9ukMB0zfs=
View all headers
On 2021-04-17, olcott <NoOne@nospicedham.NoWhere.com> wrote:
If a function X() is called by function Y() twice in sequence from the
same machine address of Y() with the same parameters to X() and the
execution trace shows no conditional branch instructions in Y() or

The problem is, the execution trace only shows no such instructions
because you have concealed them. You have declared that X is part
of the "operating system" and not part of the test case.
So in your trace there is an illegal discontinuity. There is a JSR Halts
instruction executed, but then the next instruction which is traced
is not inside Halts, but inside H_Hat. The address does not match.

function call returns in X() then the function call from Y() to X() is
infinitely recursive unless X() stops it.

Problem is, the above decision about the traces is being made by X
itself. It is accessing these global tracers, which make X not a
function, but an imperative procedure.

Below is a quote from the following idiotic document:

http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf

Note how after every "call 00000833", the next instruction being traced is
not 00000833, but 00000A63.   A63 is _H_Hat.

The document  does not reveal the disassembly of code at 833, so we have no
idea what instructions are there. However, those instructions have to do
with the decision that leads to "Infinite Recursion Detected", which is not
possible without conditionals.

(01)[00000a93][000114f7][00000000] (01)  55              push ebp
(02)[00000a94][000114f7][00000000] (02)  8bec            mov ebp,esp
(03)[00000a96][000114f3][00000000] (01)  51              push ecx
(04)[00000a97][000114ef][00000a63] (05)  68630a0000      push 00000a63
(05)[00000a9c][000114eb][00000a63] (05)  68630a0000      push 00000a63
(06)[00000aa1][000114e7][00000aa6] (05)  e8ddfdffff      call 00000883
(07)[00000a63][00031577][0003157b] (01)  55              push ebp
(08)[00000a64][00031577][0003157b] (02)  8bec            mov ebp,esp
(09)[00000a66][00031573][00021547] (01)  51              push ecx
(10)[00000a67][00031573][00021547] (03)  8b4508          mov eax,[ebp+08]
(11)[00000a6a][0003156f][00000a63] (01)  50              push eax
(12)[00000a6b][0003156f][00000a63] (03)  8b4d08          mov ecx,[ebp+08]
(13)[00000a6e][0003156b][00000a63] (01)  51              push ecx
(14)[00000a6f][00031567][00000a74] (05)  e80ffeffff      call 00000883
(15)[00000a63][0004271f][00042723] (01)  55              push ebp
(16)[00000a64][0004271f][00042723] (02)  8bec            mov ebp,esp
(17)[00000a66][0004271b][000326ef] (01)  51              push ecx
(18)[00000a67][0004271b][000326ef] (03)  8b4508          mov eax,[ebp+08]
(19)[00000a6a][00042717][00000a63] (01)  50              push eax
(20)[00000a6b][00042717][00000a63] (03)  8b4d08          mov ecx,[ebp+08]
(21)[00000a6e][00042713][00000a63] (01)  51              push ecx
(22)[00000a6f][0004270f][00000a74] (05)  e80ffeffff      call 00000883
Infinite Recursion Detected Simulation Stopped

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal



1

rocksolid light 0.8.3
clearneti2ptor