Scalar and composite data

Slides:



Advertisements
Similar presentations
1 Prof. Young Jin Nam, Daegu University 컴퓨터 구조 (Computer Architecture) 명령어 세트 : 특성과 기능 남영진
Advertisements

Copyright © 2006 The McGraw-Hill Companies, Inc. 프로그래밍 언어론 2nd edition Tucker and Noonan 5 장 타입 “ 타입은 컴퓨터 프로그래밍의 효소이다 ; 프로그래밍은 타입을 통해 소화할만한 것이 된다.” 로빈.
제 4 장 변수, 영역, 수명 변수 바인딩 영역 기억장소 할당과 수명 변수와 그 환경 변수 초기화 상수와 변수.
Vision System Lab, Sang-Hun Han
Programming Languages Type Conversion Classifying Type Conversions According to the notation –Implicit Conversions (coercion) –Explicit Conversions (casting)
C++ Tutorial 1 서강대학교 데이터베이스 연구실.
Chapter 7 ARP and RARP.
컴퓨터 응용 및 실습 Part1. OOP&Java Programming data type Review
Chapter 3 – 프로그래밍 언어 설계 Outline 3.1 설계 기준의 역사적 변천 3.2 효율성
기본 컴퓨터 프로그래밍 Lecture #6.
제 6 장 데이터 타입 6.1 데이터 타입 및 타입 정보 6.2 타입의 용도 6.3 타입 구성자 6.4 사례 연구
Internet Computing KUT Youn-Hee Han
2주 실습강의 Java의 기본문법(1) 인공지능연구실.
바인딩, 메모리 관리 SANGJI University Kwangman Ko
프로그래밍언어론 2nd edition Tucker and Noonan
출처: IT CookBook, 컴퓨터 구조와 원리 2.0 제 12장
Numerical Analysis - preliminaries -
제 18 강 데이터 타입 타입, 변환, 캐스팅 shcho.pe.kr.
Chapter 9 – 부 프로그램 Outline 9.1 개요 9.2 매개변수 평가와 전달기법 9.3 형식 매개변수 명세
Ch2-2. VHDL Basic VHDL lexical element VHDL description
[INA240] Data Structures and Practice
제 5장. Context-Free Languages
컴퓨터 시스템의 개요.
Chapter 2. Finite Automata Exercises
운영체제 (Operating Systems)
제 2 장 변수와 상수.
2 데이터 표현과 컴퓨터 연산 IT CookBook, 컴퓨터 구조와 원리 2.0.
계수와 응용 (Counting and Its Applications)
2007년 1학기 전산학개론 성신여자대학교 컴퓨터정보학부
데이터의 표현과 컴퓨터 연산 Prof. Jae Young Choi (최재영 교수)
adopted from KNK C Programming : A Modern Approach
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
Chapter 2 Lexical Elements, Operators, and the C System
Formatted Input/Output
제 2장 어휘구조와 자료형 토 큰 리 터 럴 주 석 자 료 형 배 열 형.
Introduction to Programming Language
Java의 정석 제 2 장 변수(Variable) Java 정석 남궁성 강의
Signature, Strong Typing
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
프로그래밍언어론 2nd edition Tucker and Noonan
McGraw-Hill Technology Education
제 5장 변수, 바인딩, 식 및 제어문 5.1 변수 5.6 표현식 5.2 바인딩 5.7 조건문 5.3 선언 5.8 반복문
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
제 1 장. 자료구조와 알고리즘.
시스템 분석 및 설계 글로컬 IT 학과 김정기.
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
Chapter 4 변수 및 바인딩.
Java 3장. 자바의 기본 구조 I : 변수, 자료형, 연산자 public class SumTest {
Signature, Strong Typing
Signature, Strong Typing
Chapter 13 – 객체 지향 프로그래밍 Outline 13.1 소프트웨어의 재사용과 독립성
이산수학(Discrete Mathematics)
Signature, Strong Typing
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
점화와 응용 (Recurrence and Its Applications)
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
1. 관계 데이터 모델 (1) 관계 데이터 모델 정의 ① 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key) 와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델 ② 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)
Chapter 3 – 프로그래밍 언어 설계 Outline 3.1 설계 기준의 역사적 변천 3.2 효율성
이산수학(Discrete Mathematics)
Scalar and composite data
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
Signature, Strong Typing
Introduction to Computer System 컴퓨터의 이해 3: 데이터 표현
제03장 정보의 표현.
Signature, Strong Typing
[CPA340] Algorithms and Practice Youn-Hee Han
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
Chapter 4. Energy and Potential
Chapter 7: Deadlocks.
Presentation transcript:

Scalar and composite data Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Section 5.1-5.3

Data objects Scalar data objects: Numeric (Integers, Real) Booleans Characters Enumerations Composite objects: String Pointer Structured objects: Arrays Records Lists Sets Abstract data types: Classes Active Objects: Tasks Processes

Binding of data objects A compiler creates two classes of objects: Memory locations Numeric values A variable is a binding of a name to a memory location: (Static binding이면 Loading time에 binding, dynamic binding이면 run time에 binding) Contents of the location may change while running

Data types Each data object has a type: Values: for objects of that type Operations: for objects of that type Implementation: (Storage representation) for objects of that type Attributes: (e.g., name) for objects of that type Signature: (of operation f): f: type x type  type

L-value and R-value Location for an object is its L-value. Contents of that location is its R-value. Where did names L-value and R-value come from? Consider executing: A = B + C; 1. Pick up contents of location B 2. Add contents of location C 3. Store result into address A. For each named object, its position on the right-hand-side of the assignment operator (=) is a content-of access, and its position on the left-hand-side of the assignment operator is an address-of access. address-of then is an L-value contents-of then is an R-value Value, by itself, generally means R-value

Subtypes A is a subtype of B if every value of A is a value of B. Note: In C almost everything is a subtype of integer. Conversion between types: Given 2 variables A and B, when is A:=B legal? Explicit: All conversion between different types must be specified  casting(C, C++, Java) Implicit: Some conversions between different types implied by language definition  Coersion (Algol), C(++)와 Java의 자동형변환

Coersion examples Examples in Pascal: var A: real; B: integer; A := B - Implicit, called a coersion - an automatic conversion from one type to another A := B is called a widening since the type of A has more values than B. B := A (if it were allowed) would be called a narrowing since B has fewer values than A. Information could be lost in this case. In most languages widening coersions are usually allowed; narrowing coersions must be explicit: B := round(A); Go to integer nearest A B := trunc(A); Delete fractional part of A

Integer numeric data Integers: Binary representation in 2's complement arithmetic For 32-bit words: Maximum value: 231-1 Minimum value: -231 Positive values Negative values

Real numeric data Float (real): hardware representations Exponents usually biased e.g., if 8 bits (256 values) +128 added to exponent so exponent of 128 = 128-128 = 0 is true exponent so exponent of 129 = 129-128 = 1 is true exponent so exponent of 120 = 120-128 = -8 is true exponent

IEEE floating point format IEEE standard 754 specifies both a 32- and 64-bit standard. Numbers consist of three fields: S: a one-bit sign field. 0 is positive. E: an exponent in excess-127 notation. Values (8 bits) range from 0 to 255, corresponding to exponents of 2 that range from -127 to 128. M: a mantissa of 23 bits. Since the first bit of the mantissa in a normalized number is always 1, it can be omitted and inserted automatically by the hardware, yielding an extra 24th bit of precision.

Decoding IEEE format Given E, and M, the value of the representation is: Parameters Value E=255 and M  0 An invalid number E=255 and M = 0  0<E<255 2{E-127}(1.M) E=0 and M  0 2 {-126}.M E=0 and M=0 0

Example floating point numbers +1= 20*1= 2{127-127}*(1).0 (binary) 0 01111111 000000... +1.5= 20*1.5= 2{127-127}*(1).1 (binary) 0 01111111 100000... -5= -22*1.25= 2{129-127}*(1).01 (binary)1 10000001 010000... This gives a range from 10-38 to 1038. In 64-bit format,the exponent is extended to 11 bits giving a range from -1022 to +1023, yielding numbers in the range 10-308 to 10308.

Other numeric data Short integers (C) - 16 bit, 8 bit Long integers (C) - 64 bit Boolean or logical - 1 bit with value true or false Byte - 8 bits Character - Single 8-bit byte - 256 characters ASCII is a 7 bit 128 character code In C, a char variable is simply 8-bit integer numeric data

Enumerations typedef enum thing {A, B, C, D } NewType; Implemented as small integers with values: A = 0, B = 1, C = 2, D = 3 NewType X, Y, Z; X = A Why not simply write: X=0 instead of X=A? Readability Error detection Example: enum { fresh, soph, junior, senior} ClassLevel; enum { old, new } BreadStatus; BreadStatus = fresh; An error which can be detected

Declaring decimal data Fixed decimal in PL/I and COBOL (For financial applications) DECLARE X FIXED DECIMAL(p,q); p = number of decimal digits q = number of fractional digits Example of PL/I fixed decimal: DECLARE X FIXED DECIMAL (5,3), Y FIXED DECIMAL (6,2), Z FIXED DECIMAL (6,1); (8,3) X = 12.345; Y = 9876.54;

Using decimal data What is Z=X+Y?: By hand you would line up decimal points and add: 0012.345 9876.540 9888.885 = FIXED DECIMAL(8,3) p=8 since adding two 4 digit numbers can give 5 digit result and need 3 places for fractional part. p=8 and q=3 is known before addition Known during compilation - No runtime testing needed.

Implementing decimal data Algorithm: 1. Store each number as an integer (12.345, 9876.54) Compiler knows scale factor (S=3 for X, S=2 for Y). True value printed by dividing stored integer by 10S 2. To add, align decimal point. Adjust S by 1 by multiplying by 10. 3. 10*Y+X = 9876540 + 12345 = 9888.885, Compiler knows S=3 4. S=1 for Z, so need to adjust S of addition by 2; divide by 102 (9888.8) 5. Store 9888.8 into Z. Compiler knows S=1 Note: S never appears in memory, and there is no loss of accuracy by storing data as integers.

Composite data Character Strings: Primitive object made up of more primitive character data. Fixed length: char A[10] - C DCL B CHAR(10) - PL/I var C packed array [1..10] of char - Pascal Variable length: DCL D CHAR(20) VARYING - PL/I - 0 to 20 characters E = “ABC” - SNOBOL4 - any size, dynamic F = `ABCDEFG\0' - C - any size, programmer defined

String implementations

String operations In C, arrays and character strings are the same. Implementation: L-value(A[I]) = L-value(A[0]) + I

Pointer data Use of pointers to create arbitrary data structures Each pointer can point to an object of another data structure In general a very error prone construct and should be avoided

Pointer aliasing

⑴ 포인터는 심각한 type violation을 초래할 수 있다. PL/I   DECLARE P POINTER,             X FIXED BASED, /* INTEGER */              Y FLOAT BASED; /* REAL */ 위의 문장은 P를 포인터로, X는 정수로, Y는 실수로 선언했다. 그러므로 P→X는 포인터 P를 통해 정수 자료 X를 접근한다. ALLOCATE X SET P; 그러나, P는 정수와 실수로 동시에 선언되었으므로, P→Y에 의해 접근도 가능하다. 번역 과정에서는 이와 같은 오류를 찾을 수 없다. 유일한 방법은 형을 dynamic하게 검증할 수 밖에 없으나, 이를 위한 비용은 지나치게 높다. Static type checking보다 dynamic type checking이 더 많은 비용(처리속도와 기억용량)이 소요되는 이유를 생각해보자 따라서 일반적으로 사용자가 올바르게 사용했다고 가정하여 dynamic checking을 하지 않는다. 그러나 이 경우 심각한 수행오류(run-time error)를 초래할 수 있다.

(2) 포인터는 dangling하게 남을 수 있다. - PL/I   BEGIN;         DCL P POINTER;         BEGIN;              DCL X FIXED; /* ALLOCATE NEW */              P = ADDR(X); /* P NOW POINTS TO X */         END; /* X의 주소가 P에 assign되었다. 그러나 이 시점에서 X는 scope를 벗어났으므로 deallocate되었지만, P는 X의 주소를 가지고 있다. 여기서 X를 사용하면 어떻게 될까? */   END; ※ Algol 68과 PASCAL의 해결 - ⑴의 문제   PASCAL과 Algol 68에서는 포인터가 한 가지의 형을 가진 자료와만 연결시킨다(bind). 따라서 ⑴의 문제가 발생하지 않는다. - ⑵의 문제   : Algol 68 ⇒ 포인터에 주소를 assign할 때는 최소한 포인터보다 scope 상에서 더 밖에 있는 것만 assign할 수 있게 제한하고 있다.   : PASCAL ⇒ 변수의 주소를 포인터 변수에 assign하는 것 자체를 금지하고 있다. C언어에 대해 어떤 문제가 발생하는지 조사하여 제출한다.

그 외 PASCAL에서는 “new”로 heap의 기억장소를 배정받았을(allocate) 경우에, 꼭 “dispose”에 의해 사용후 deallocate 해야 한다. 그러나 많은 경우에 “dispose”를 행하지 않아 기억용량이 모자라게 되는 경우가 있다. 또한 배정받은 기억장소를 사용하고 있음에도 불구하고 “dispose” 시키면 dangling이 발생할 수도 있다. “C”도 같은 문제가 있다. 초기화하지 않고 포인터를 사용하면!!! Algol 68과 Simula 67에서는 heap 기억장소를 명시적으로 deallocate하지 않게하고 있다. 이에 따라서 grabage collection(쓰레기 줍기)이 필요하다. Lisp에서도 garbage collection이 사용된다. garbage collection에 대해 생각해 보자.