TOY언어 예시

유인물.lips-like->함수언어
언어가 어케 만들어지고 어케 확장되는가 그리고 이것을 어떻게 bnf로 표현하나.

함수언어
함수(fuction) -> 정의역-함수-치역 매핑
toy란 언어는 term으로 구성되어있다.
연산의 대상은 여기서는 integer만 있음.
FUN은 언어의 함수의 집합임. minus,if 2가지 함수가 존재함
Z 노테이션은 integer의 집합을 의미한다.ZxZ to Z

term의 종류 3가지가 있다.
t1: variable
t2: constant
t3: (minus t1 t2) (IF t1 t2)

M((If 1 2)(M 3 4)) -> 3
2- (-1)

언어의 문법에 대해 생각을 해보자.syntax

start symbol: TOY
<TOY> -> <term>
<term>-><var>|<term>
        | (minus <term><term>)
  		| (IF <term> <term>)	
  
<var>-> <char>{<char>|<digits>}
<char>->a|b|c...
<digits>-> 0|1|2|3...
<const>->[-]<digits>{digits}

%3,%sum,%(if 1 2) 등등은 sematics(의미)이다.

5.1 intro

imperative language(명령형 언어), 주류언어는 폰노이만 구조에 기반을 둔다.memory에 instruction,data가 올라가 cpu에 fetch되어 연산된다.
변수에 대한 이야기를 하겠다.

5.2 Names

그 프로그램에서 특수한 의미를 가진 이름을 keyword라 한다.
변수명,함수명으로 이름이 쓰인다.
case sensitive-> 대소문자를 구분하느냐.
reserved word-> keyword 특별한 의미를 갖는 문자열

5.3 variables

기계어에서는 변수를 주소로 했지만, 하이레벨에서는 이름으로 변수를 가리킬 수 있다.
225p

변수의 6가지 속성

• name

• address // l-value

• value // r-value

• type//6장

• lifetime//변수가 메모리를 할당받은 시간

• scope //변수를 프로그램의 어디에서 접근할 수 있나

5장에서는 lifetime,scope에 집중한다.

5.3.2 address

변수의 주소를 l-value라 한다. 변수의 값을 r-value라 한다.
(left-right)

aliases(별명)-> 주소에 여러 이름으로 접근
3가지 경우 -226p

• union type
  하나의 data structure를 다른 이름,자료구조로 선언할 수 있는 그래서 하나의 메모리 영역을 서로 다른이름으로 접근가능하게 하는 것
• 포인터 변수
  p=q
  포인터 변수라면 별명으로 기능해 두 변수가 같은 주소를 가리킴.
• subprogram parameter(formal parameter=정의할 때 쓰이는 파라미터,actual parameter=실제로 호출할 떄 넘겨주는 값)

5.4 binding

bing이란? entity,변수에 어떤 속성이 결합되는 것.
sum이란 변수에 int타입을 정하는 것, sum에 100이란 값을 정하는 것.
이 속성이 결합되는 시점이 binding time이다
2가지

• 컴파일할 때
• 런타임 때

5.4.1 binding of attributes to variables

static binding vs dynamic binding
컴파일타임 binding - 런타임 binding

5.4.2 Type binding

int sum;
대부분의 언어는 static binding을 사용함.
-> 세살 버릇 여든까지 간다.

-dynamic type binding
type이 실행 시에 계속 바뀔 수 있다.
이를 위해선 결국 변수가 포인터의 역할을 해야 한다.
사이즈를 알 수 가없음-> 그때그때 달라져서

주로 함수언어에서 사용했음.
원래 주로 static binding이 사용되었으나
90년대 중반이후 python,luby,javascript,PHP등에서 dynamic binding사용

230,231p
dynamic binding문제
-type checking이 안됨.
-포인터 변수로 구현->runtime cost큼, 실행시간 늦음
주로 pure interpreter방식을 사용함.

5.4.3 storage binding and lifetime

메모리의 공간
코드공간// static공간 // dynamic 공간

• static variables //전역변수

• stack-dynamic //지역변수-stack영역

• explicit heap dynamic //동적 자료구조-heap영역

• implicit heap dynamic //dynamic type binding에서 사용

storage binding

메모리에 변수를 할당하는 것
메모리에 instruction들이 올라오고, data영역이 할당됨.
변수들 중 일부는 static,dynamic하게 할당됨.
이 때 전역변수는 static하게 할당됨.->메모리에 고정적으로 할당
반면 지역변수는 dynamic하게 함수의 실행 중에 할당됨.

dynamic할당 크게 2가지.

• 지역변수
• 동적 자료구조(malloc같은 것)

232p
지역변수이면서 history sensitive해야 할 일이 있다.
함수의 호출마다 변수가 축적되어야 하면 지역변수도 static으로 선언하면 된다.
자바의 static은 조금 다르다. 클래스에 하나 있는 클래스 변수를 의미한다.

지역변수와 stack

main-> A함수->
스택에 A의 지역변수 할당, 그 위에 B의 지역변수 할당
리턴하면 위에서부터 사라진다 -> stack

동적 자료구조

malloc 메모리에 필요한 공간이 동적으로 할당됨.

234p
자바의 기본형 외의 모든 자료구조는 object이므로 동적으로 할당된다.
이것은 포인터 변수가 사용되는데 -> 2가지 문제

• 포인터가 사라져도 데이터가 남아있음: garbage
• 데이터가 없어졌는데 포인터가 남음/엉뚱한 데 가리킴 : dangling pointer

자바에서는 dangling pointer를 없애기 위해 프로그래머가 인스턴스를 지울 수 있는 방법이 없고 garbage collector 가 주기적으로 돌며 필요없어진 인스턴스를 자동으로 지운다.

• implicit heap dynamiv variables

5.5 scope

변수가 프로그램의 어느 부분에서 visible(접근가능)하냐.
global: 프로그램의 전부분에서
local:함수 안에서

함수의 목적: 재사용의 단위
처리에 대한abstraction
information hidity(은닉)

• static scope
  프로그램의 구조 상(함수를 어떻게 만드느냐)에 따라 결정됨
  2가지 종류 있음 -> nested static scope
  non-loacal
  nesting: sub함수는 자기부모 함수의 변수에 접근이 가능하다.->
  부모는 자식함수 변수 접근 불가능.

5.6 scope and lifetime

전역변수는 scope가 아무데서나 다 보이고 static 할당됨.
지역변수 함수 안에서만 visible하고 dynmic하게 할당됨.
static 식별자 이용해 변수를 선언하면 함수내에서 vicible하지만
lifetime은 프로그램 전체로 확장됨.

5.7 referencing environments

• active
  subprogram이 active하다. activate되었다는 것은
  시작은 했으나 끝나지 않았다는 것이다.
  main->A->B->C 상태라면
  실행 중인것은 C이나 active인 것은 함수 전부이다.
  지역변수는 함수가 active 상태일 떄만 공간을 할당받는다.

dynamic scope방법에서는
구조에 따라서가 아니라 active되있냐에 따라 변수에 접근 가능하다.

5.8 named constant

• named constant
  값에 한번만 할당되는 변수이다.