게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

프로시져, 환경 질문

 
글 쓰기   답변 달기     게시판 인덱스 -> 4190.310 Programming Languages (Fall 2017)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
김현식



가입: 2017년 9월 5일
올린 글: 24

올리기올려짐: 2017년10월16일 21:32    주제: 프로시져, 환경 질문 인용과 함께 답변

1. procedure이 명령문을 이름 붙인 것이라고 이해하고 있었는데
형태가 id list * exp * env 인 것이 잘 이해가 안됩니다.
예시로
...
let proc f(x)= y:= x+y in S
..
라고 하면 f라는 procedure가 정의된 순간의 환경에서의 x값이 기록되고
f=({x}, y:=x+y , sigma{x->l}) 인건가요?
만약에 그렇다면 id list가 나타내는 것은 무엇인가요? 어짜피 env에 id list의 각 id에 해당하는 주소값이 저장되어 있는게 아닌가요?


2. 그리고 K- 프로그램에서는 기본적으로 env는 E(id -> Addr Loc.t or Proc id list * exp * env) 형태를 가질텐데 그럼 env가 하나의 id값만 저장할 수 있는 형태가 되어버리는게 아닌가요?

3. module Env에서 Env.empty가 E ( fun x -> raise Not_bound) 라고 되어있는데
K- 모듈안에서 불러오면 x는 id 타입일텐데 어느 x라도 존재하게 되면 빈게 아니니까 에러를 반환한다는 의미인가요? 아니면 이 x는 그냥 초기에 존재하는 아무 x인가요? x의 의미를 잘 모르겠네요..


매우 기초적인 문제일 수 있는데 책, ppt, 뼈대코드를 보고 한줄씩 이해해보려고 하는데 아직 매우 생소하고 이해한 것 같으면서도 코드를 보면 헷갈리네요.. 넓은 아량으로 이해해주시고 답변해주시면 큰 도움이 되겠습니다! 감사합니다^^
위로
사용자 정보 보기 비밀 메시지 보내기
신원준



가입: 2017년 9월 12일
올린 글: 23

올리기올려짐: 2017년10월17일 1:26    주제: 인용과 함께 답변

1. env에는 id -> location (변수의 메모리상의 주소) 의 바인딩을 가지고 있습니다. 즉 주소값이 저장되어 있는 것이 맞습니다.

LETF, 즉 procedure를 정의하는 시점에는 함수의 전달인자와 관련된 어떠한 변수도 메모리상의 주소를 할당받지 않습니다.

함수의 전달인자로 쓰이는 변수는, 함수가 호출될 때에 비로소 바인딩됩니다.

바인딩 대상은 새로 메모리공간을 할당해서 env에 추가해주거나 (CALLV), 호출된 환경의 변수와 연결해서 매핑합니다. (CALLR)

즉,

코드:

...
let proc f(x)= y:= x+y in S
...


이 사례의 경우, x의 "값"이 기록되는 것이 아니고, id list에는 "x"라는 identifier가 전달인자였다라는 사실을 저장한다고 보시면 됩니다.

x가 env에 등장해서 실제로 어떤 대상과 매핑되는 것은 호출시점입니다. (e2 중에 CALLV나 CALLR 등이 등장하는 시점)



1-1. f = ({x}, y:=x+y, sigma{f->[{x}, y:=x+y, sigma]}) 가 맞습니다.

서류상의 LETF를 보시면 시그마[env]에 뭘 넣음을 아실 수 있는데, 그건 procedure 자신을 바인딩해서 env에 넣어주는 것입니다.

(재귀호출을 위해서)



2. 저도 레코드 처음 구현할때 똑같은 오해를 했었는데요, 아닙니다.

레코드도 똑같은 구조로 되어 있으니 레코드로 설명하겠습니다.

레코드의 타입은 (id -> Loc.t) 인데, 동일한 논리대로라면 레코드도 하나의 id값만 저장할 수 있어야 할 것입니다.

하지만 실제론 아닙니다.

코드:

fun id ->
  if (id == "a") then
    Locations[0]
  else if (id == "b") then
    Locations[1]
  else if (id == "c") then
    Locations[2]
  else if ...


뭐 이렇게 구현하면, 임의 갯수의 매핑을 한 레코드 안에 넣을 수 있겠죠.

Env도 똑같은 원리로, 임의 갯수의 매핑을 넣을 수 있도록 설계된 타입입니다.



3. 비어있는 환경에는 어떠한 변수를 찾더라도 바인딩이 없습니다. (당연하죠. 비어있으니까)

이게 왜 동작하는지를 이해하시려면 Env.bind를 살펴보셔야 합니다.

코드:

let bind (E (env)) id loc = E (fun x -> if x = id then loc else env x)


Env는 다음과 같이 재귀적으로 id를 찾도록 구현되어 있습니다.

이를테면 a, b, c, d, e의 순서대로 bind한 경우, Env.bind를 다섯 번 호출한 뒤의 객체의 Env.find는 다음과 같습니다.

코드:

{
  e인 경우 e에 바인딩 된 값 리턴
  아닌 경우 {
    d인 경우 d에 바인딩 된 값 리턴
    아닌 경우 {
      c인 경우 c에 바인딩 된 값 리턴
      아닌 경우 {
        b인 경우 b에 바인딩 된 값 리턴
        아닌 경우 {
          a인 경우 a에 바인딩 된 값 리턴
          아닌 경우 {
            Env.empty 이므로 raise Not_bound
          }
        }
      }
    }
  }
}


저기에서 하나의 bracket으로 들어가는 것이, 재귀함수를 호출하는 것입니다.

저렇게 하나하나씩 쌓아서 Env를 구성하도록 되어 있습니다.

아마 과제 2를 하실 때 대부분 Set, Map 따위를 이용하셨을 텐데, 그거랑 전혀 다른 느낌입니다.



*: Env랑 Mem 자체가 어떻게 동작하는 지에 대해서는 자세하게는 모르셔도 될 거 같습니다.

이해 못하셔도 충분히 구현하실 수 있는데 불필요한데 힘 쏟으실까봐 말씀드려요.

ENV랑 MEM에 써 있는 주석 이해하시면 구현하기에 충분합니다.
위로
사용자 정보 보기 비밀 메시지 보내기
김성국17



가입: 2017년 9월 15일
올린 글: 16

올리기올려짐: 2017년10월17일 9:43    주제: 인용과 함께 답변

1.
사실 여기서 Proc은 closure라고 말하는게 더 정확합니다. closure가 무엇인지는 ppt에 있습니다.

procedure는 질문자분 말대로 코드에 이름을 붙인것인데, 우리가 이것의
의미를 다룰때 static scoping을 위해서 procedure가 정의될때의 환경까지 같이 기입해줍니다. 이 것을 closure라 부르고, 그 환경이 3번째의 env에 해당합니다. 그것이 없다면 dynamic scoping 밖에 할수가 없습니다.

그리고 재귀호출은 본이야기와 조금 무관한것 같습니다. 윗분이 1-1에서 말씀하신 부분에도 약간의 오류가 있는것 같은데 semantics정의된
것을 보면 closure는 자신의 환경에 자기자신의 bind하고 있지 않습니다. 단지 호출을 할때 임시로 bind한 환경을 씁니다. 뭐 bind를 해논다고해서 실행상에 차이는 없을것 같긴 합니다만 주어진 spec과는 다릅니다.

2.
f(x) = x^2의 타입은 실수->실수 입니다. 하나의 매핑만 있는것이 아닙니다.
위로
사용자 정보 보기 비밀 메시지 보내기
김현식



가입: 2017년 9월 5일
올린 글: 24

올리기올려짐: 2017년10월17일 10:55    주제: 답변 감사합니다^^ 인용과 함께 답변

두 분 답변 정말 도움 많이 되었습니다^^ 감사합니다~
위로
사용자 정보 보기 비밀 메시지 보내기
신원준



가입: 2017년 9월 12일
올린 글: 23

올리기올려짐: 2017년10월17일 14:21    주제: 인용과 함께 답변

어이쿠 제가 잘못 적었군요.

스펙에 따르면 call하는 시점에 환경에 바인딩하는 게 맞습니다.

(미리 바인딩해놔도 동작하긴 하겠네요..)
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> 4190.310 Programming Languages (Fall 2017) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay