Hoare Logic에서 할당 규칙이 왜 그런가요?

https://cs.stackexchange.com/questions/118322

28-09-2020
|

문제

할당 규칙이 Hoare Logic/Axiomatic Semantics와 같은 방식인 이유는 무엇입니까?할당 규칙이 예상했던 것과 반대되는 이유를 머리로 이해할 수 없습니다.

나는 Hoare 논리가 명령이 실행될 때 프로그램 상태에 대한 공식적인 제안을 증명하는 데 사용된다는 것을 이해합니다.따라서 명령을 실행하면 $$x:=e$$ 나는 그럴 것이라고 예상했을 것이다. 다음 상태에 그런 대체가 있습니다...하지만 대체가 일어나는 것 같습니다 ~ 전에 우리는 내가 이상하다고 생각하는 임무를 수행합니다.나는 예상했을 것입니다 :

$$ \{ P \} x:= e \{P[e/x]\}$$

을 고려하면 $P$ 프로그램 상태에 대한 설명입니다.

나는 이것에 대한 좋은 설명이 있다고 확신하며 이것이 기본적인 질문이라면 죄송합니다.그런데 누군가 나에게 설명해 줄 수 있나요?

보너스 질문:

할당 규칙을 다음과 같이 작성하면 어떨까요?

$$ \{ Q \} x:= e \{Q[x/e]\}$$

우리가 가지고 있기 때문에 그것은 내 원래 제안과 동일하지 않습니다. $x$ 그리고 $e$ 이리저리 바꿨습니다.즉.포스트 조건에서 우리가 어디에 있든 $e$ 우리는 $x$ (우리가 방금 실행한 명령문은 다음과 같기 때문에 괜찮습니다. $x$ 의 가치를 갖고 있다 $e$, 그래서 우리는 교체할 수 있어야 합니다 $e$ ~을 위한 $x$ 사전 조건이 도움이 되는 경우 사후 조건에서.

내가 읽었지만 도움이 되지 않은 관련 게시물:

부록:

우리 난독증 환자의 경우, 이 질문에서 대체 표기법이 의미하는 바는 다음과 같습니다.

$$ P[e/x] = P[e o x] $$

즉.무료로 발생하는 모든 항목을 교체합니다. $x$ 표현/용어/사물 포함 $e$.

해결책

그래서 좀 더 읽고 생각해 본 후에 이것이 제 설명입니다(감사합니다 소프트웨어 기초):

나에게 가장 큰 혼란은 다음의 의미인 것 같다. $P[e/x]$ (x의 모든 무료 인스턴스를 e로 대체합니다).이것이 하는 일은 기호가 보이는 곳 어디에서나 가능합니다. $x$ 말 그대로 제거하고 배치 $e$.예를 들어 $ P[e/x] = (x+y+1)[e/x] o P[e/x] = (e+y+1)$ 그러니 어떻게 하는지 알아봐 $x$ 말 그대로 사라졌다 $P$.따라서 우리가 원하는 것은 일단 과제를 수행하는 것입니다.

$$ x:= e$$

만약 우리가 이 진술이 사실이라면 $x$ 대신에 $e$.따라서 규칙은 다음과 같습니다.

$$ \{ P[e/x] \} x:= e \{ P \}$$

그렇다면 우리가 원하는 것은 플러그를 꽂을 때입니다. $x$ ~을 위한 $e$ 우리는 고려중인 진술이 사실이기를 원합니다.따라서 코드를 시작하기 전에 우리는 $P[e/x]$.그런 다음 할당과 모든 인스턴스를 실행합니다. $e$ 사라지고 우리는 얻는다 $x$그들을 교체하는 것입니다.저것 ~ 해야 하다 실행된 코드가 할당인 경우 참입니다(이후 $x$ 이제 그 가치를 유지하세요 $e$, 제거할 수 있도록 $e$와 장소 $x$).

이것이 추상 개념에 대한 설명입니다.소프트웨어 기반(SF) 예제를 (뻔뻔스럽게) 사용해 보겠습니다.

{{ Y = 1 }} X ::= Y {{ X = 1 }} 영어로:Y 값이 1인 상태에서 시작하여 X에 Y를 할당하면 X가 1인 상태에서 끝납니다.즉, 1과 같다는 속성이 Y에서 X로 전달됩니다.

SF의 또 다른 유용한 단락:

마찬가지로 {{y + z = 1}} x :: = y + z {{x = 1}} 동일한 속성 (1과 동일)이 오른쪽의 y + z 표현에서 X로 옮겨집니다. 과제의 측면.보다 일반적으로 A a가 산술 표현식이라면 {{a = 1}} x :: = a {{x = 1}}은 유효한 Hoare 트리플입니다.

의견의 훌륭한 관찰에 대한 부록:

규칙 {p [e / x]} x : = e {p}는 표현식 e와 변수 x가 사후 조건에서 발생할 수 있음을 인식하는 것이 중요합니다.다시 말해, 추론 규칙을 사용하면 전제 조건에서 E의 발생 하위 집합이 X로 대체 된 후 전투를 추론 할 수 있습니다.게다가, 이러한 다양한 사후 조건을 모두 동시에 추론할 수 있습니다.

보너스 이유에 답장하다

1) $ \{P[e/x]\} x:=e \{P\} $

보다 낫다

2) $ \{ Q \} x:=e \{Q[x/e]\} $:

x를 눈에 보이지 않는 표현식으로 바꾸는 미묘한 점 외에도(예:e=0, 대체해야 할까요? $0$ 무한한 수로 $x$'에스?0이 없으면 어떻게 될까요...규칙은 구문론적이어야 하지만 그러한 혼란을 피하는 것이 더 낫다고 생각합니다.) 이것이 이유라고 생각합니다.

할당 규칙이 포착해야 하는 것은 표현식 e를 변수 x에 할당한다는 것입니다.따라서 x만 e로 "대체"되어야 합니다.직관적으로 코드(더 정확하게는 프로그램의 상태)에서 $\시그마$) x가 e 값을 보유하기 시작한다고 해서 e가 있을 수 있는 모든 곳에서 할당을 실행한 후 x가 된다는 것을 무작위로 의미하지는 않습니다. $x:=e$.실제로 이것이 의미하는 바는 이제 사후 조건에 x가 있다는 것입니다.이제 할당이 없는 경우 x의 값은 다음과 같아야 합니다. $e$ 즉.할당 명령이 수행한 교체/할당만 "실행 취소"합니다.다른 모든 무작위 표현식은 아닙니다. e.간단히 말해서, 올바른 e를 배치할 위치를 알 수 있는 유일한 방법은 할당이 완료된 후 post 조건에서 시작한 다음 거기에서 e를 배치하는 것입니다.거꾸로 수행하면 교체하고 싶지 않은 e를 교체할 수 있습니다(아마도 사실일지라도 x가 e를 x에 할당한 후 e 값을 보유한다고 말하고 있기 때문에 그렇게 해야 한다고 생각합니다).

다른 팁

프로그램 x := e 프로그램을 실행하고 $ \ sigma $ 을 초기 상태, $ \ sigma $ 최종 상태가됩니다.

여기서 중요한 직감은 최종 상태 $ x $ 의 값> $ \ sigma '$ 은 초기 상태 $ e $ 의 값과 동일합니다. "수학 용기"> $ \ sigma $ . 실제로, 후자는 $ x $ 명령을 입력합니다.

$ p (-) $ 은 값의 속성, 수식 $ p (\ mbox { $ x $-the-the-the-pinal-state}) $ 은 $ p (\ mbox {$ e $-in-the-itical-state})와 같습니다. $ . 즉, $ p (x) $ ( $ \ sigma)에서 $ p (x) $ $ )는 전처리 ( $ p (e) $ 과 정말로 동일합니다. 컨테이너 "> $ \ sigma $ ).

대체를 사용하여 $ x $ ", 즉 $ p (x) $ , $ p (e) $ 을 전제 조건으로 요구합니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 cs.stackexchange