자료형

C언어

• primitive(기본형)
• derived(파생형)

Java

• primitive type(기본 자료형)
• reference type(참조 자료형) → class, array, interface

Python

• primitive
• container

descriptor란?

변수의 속성 모음

Primitive type

integer

• java는 signed만 있음.

floating point

complex

• python에서만 기본자료형으로 지원.
• java는 class로 지원
• c,c++ 는 #include 로 사용가능

decimal

• c#만 지원한다.

boolean

• readability를 위해 사용한다

character

character string type

• primitive type인가?
  • python에서는 primitive
  • java에서는 class를 통해 primitive 처럼
  • c, c++는 배열로 취급
• String 길이는 static/ dynamic?
  • static: java
  • limited dynamic: c/c++ → 널 문자 사용
  • dynamic: python

enumeration

• writability떨어지지만, readability와 reliability가 좋다
• c, c++에서만 primitive

not primitive

array types

• homogeneous: 동일종류 집합 배열
• heterogeneous: 다른 자료형도 들어가있는 경우
• array indexing = subscripting
• index range check 하는가?
  • 하는 언어: Java, Python
  • 안하는 언어: C, C++ (이상한 값이 나온다)

index binding, storage binding에 따른 4가지 분류

💡 2가지가 compile time에 이루어지느냐, runtime에 이루어지느냐에 따라 4가지로 분류

1. Static
   • static 키워드 사용
   • global, 상수
   • 전역변수
   • 접근이 빠르다, 하지만 메모리를 많이 잡아먹는다
2. Fixed stack dynamic
   • subscript range (index range)는 compile할때 static하게 결정, 메모리 할당은 동적으로 runtime에 이루어짐 → 선언문이 나올 때.
   • c, c++, java의 local 변수
   • 메모리 관리에 좋다
3. Fixed heap dynamic
   • c, c++, java의 malloc, new (new 쓰면 무조건 heap)
   • 메모리 할당이 동적으로 내 요청에 의해 명시적으로 이루어짐 → heap
4. Heap dynamic
   • 파이썬은 무조건!!! heap dynamic
   • 파이썬의 배열은 list, 동적으로 메모리 관리.
   • flexible좋지만 메모리 관리의 최적화 어렵다

array operation

• python → reference change. aliasing → 값 바꾸면 같이 영향 미침

jagged array

• 모든 언어 지원.
• c, c++, java의 경우 뒤에 size 주지 않고 new를 통해 만들면 된다.

slices

• 파이썬에서 배열의 일부 잘라냄

multi demensioned arrays

• row major order
• column major order

associative arrays

indexing 숫자가 아니라, key값으로 찾는 것

• python → dictionary의 key
• c, c++, java는 지원x.
• elements를 reference하는 형태는?
  • key
• dynamic하게 size 바꿀 수 있는가?
  • yes. dictionary descriptor에 current length가 있다.

record type (structure)

• c, c++에 있음.
• heterogeneous 하다.
• 요소를 각 field의 이름으로 찾는다.
• 필드를 참조할 때 쓰는 문법은?
  • dot (.)
• 생략된 참조 (elliptical reference)가 허용되는가?
  • 안됨
• 배열보다 빠르다.

tuple types (python)

• [] 는 list
• ( )는 tuple
• multi value를 리턴하는 함수의 리턴값 받기 위해서 사용
• immutable
• tuple끼리 합치거나 통채로 삭제는 가능하지만, 요소 하나를 건드는 것은 불가능

list (python)

• python은 배열 대신 list 사용
• 원소가 같을 필요 없음, heterogeneous
• index로 접근 가능, 리스트의 원소로 리스트도 가능
• mutable하다.

array list (java)

• data type으로 지원하지 않고, class를 통해 지원한다.
• 배열의 크기가 동적으로 변한다.
• 다양한 타입 객체 지정 가능. (heterogeneous)

pointer and reference types

• C: pointer만 지원
• C++: 둘다 지원
• Java, Python: reference만 지원.
• 둘의 차이
  • 가리키는 것 바꿀 수 있다: pointer
  • 가리키는 것 바꿀 수 없다: reference
  • referece는 주소에 대한 직접적 access 불가
• Pointer Operations
  • assignment : & , 포인터에게 주소값 주는 것
  • dereferencing: *, 포인터가 가리키는 값을 뽑아오는 것
    • explicit할 수도, 아닐 수도 있다.
    • c++는 *를 사용해 explicit하게 표현한다.
    • dereferencing을 이용한 assignment도 가능
• pointer의 문제
  • dangling pointers: 너무 빨리 delete했을 때
  • garbage (lost heap-dynamic variable): delete를 안해서 해당 메모리가 garbage 되어버림 → java는 시스템이 내부적으로 해결하지만, c는 아니다.
• *void로 다양한 type 가리킬 수 있다.

기말고사 범위

Reference Types

포인터는 불편하다.

cformal parameter에게 actual parameter를 전달하는 기본 방식: pass by value(복사해서 넘김) → 단점: 저장공간 불필요하게 낭비. 더 큰 단점은 호출하는 함수에서 넘겨주는 값을 변경하고자 할때 불가능하다.

• c에서는 pointer를 통해서 함
• C++ & 로 가능하게 함 (reference type)
• java는 primitive type 제외하고 전부 reference type임
  • class, array, interface → Object에서 상속받은 reference type
• C#은 포인터, reference type 둘다 지원

Reference type의 문제, 해결 방법

1. Dangling pointer 문제 해결

   1. Tombstone: memory cell과 pointer 사이에 Tombstone을 세워서 제일 처음 memory cell을 가리키는 포인터 생성될때는 Tombstone을 통해 연결 (indirect하게)

      • 포인터 여러개중 하나가 메모리 해제하려고 할때, Tombstone자체를 NULL로 바꾸는 작업을 한다.
      • 문제: 쓸데없이 tombstone공간이 쓰임으로 인한 메모리 낭비, 포인터가 메모리 여러번 찾아가야하는 수행시간이 더 걸림
   • Locks and keys: pointer가 address뿐만 아니라 key도 가지게 함 (key, addr) → 처음 포인터 생성할때 lock변수도 생성해서 lock과 key값을 맞춰줌, address가 memory cell을 가리키게 함. address는 memory cell을 가리키게 함.
     • deallocation할때 lock값 refresh → 접근할때마다 key값과 lock값 비교해서 둘이 같을때만 제대로 접근했다고 생각하여 허용함
       • 시간적 문제 (비교연산, 느려짐)
       • 불필요한 메모리 공간 (lock, key공간)
2. garbage 문제 (메모리공간 낭비 문제)
   • heap memory 상의 garbage문제
   • 해결법
     • Reference counters (eager approach)
       • 각 메모리 셀마다 카운터 하나씩 붙임 → 나를 가리키는 포인터가 몇개인지 셈. 나를 가리키는 포인터 없으면 available space로
       • 그때마다 heap 공간의 free한 공간 return 받음
         • 장점: delay가 크지 않음
         • 단점: counter로 인한 공간 사용, execution time 사용
       • 오버헤드가 너무 많이 생기기 때문에 대부분 시스템은 lazy approach 사용
     • Mark-sweep (lazy approach) → 한번에 몰아서 (급할때 쓰는 방법)
       • 현재 포인터에 의해 가리켜지고 있는 것들만 marking
       • marking 안된 것들은 한번에 garbage collector로 모음
       • 수행시간이 길다
       • marking을 어떻게 할 것인가?
       • 각 자료구조에 할당되는 memory cell 이 그때마다 다른 경우는? (variable size cell)
         • initial setting에 모두 garbage라고 세팅할 때, 어느 단위로 세팅할지가 어려움

시험문제

💡 C, C++ : Static, Weak
💡 Java: Static, Strong
💡 Python: Dynamic, Strong
💡 JavaScript: Dynamic, Weak

Name Type Equivalence

• Type이 같다는 것은 compatible한 것과 다름 (conversion 고려하지 않음)
• 판단 기준
  • Name (훨씬 엄격한 방법) → 둘다 같은 이름일때만 동일하다고 판단(Integer, String 등)
  • Structure → 두개가 갖는 자료가 같으면 같다고 판단 (implementation 어떻게 하느냐에 따라 정도의 차이가 생김), 구현에 따라 달라진다

Type Theory

• 걍 이론적인 내용, formal한 형식을 기준으로 type 정의
• type system: type+ type rule (type에 규칙과 타입을 합한 것)
  • type은 값,연산으로 정의됨
  • sound type system: 안전한 type system, 이안에서 코딩되면 type error는 0이 보장됨
  • 가장 안전한 프로그램 (syntax error도 없고 type error도 없는 경우)