[Programming Language Week2] Data type, Specification, Type Checking, Floating point vs Fixed point

makeitcloud·2020년 9월 14일
1

Computer Science

목록 보기
3/9

Introduction

Three major components in a programming language

  • Data
    : Basic information unit to hold values to determine the state of a system
  • Operations
    : Actions to manipulate data or sequencing
  • Control
    : A mechanism provided to control the sequence of instructions

Basic Concepts for Data

  • Data storage of an actual computer
    -- Memory, register or external media
    -- Usually have simple structure as sequence of bits comprising bytes or words

  • Data storage of a virtual computer
    -- Arrays, stacks, numbers, character strings

In C) arrays
int arr[10]={1,2,3,4,5,6,7,8,9,10};
char arr2[12]="hello world";

-- Usually have more complex organization

In C) structure
struct info{
	int number;
    	int age;
    	char name[4]; } person; 
  • Data Object
    -- Run-time grouping of one or more pieces of data in a virtual computer
    -- Some are defined by programmer (variables, constants, arrays) and others are defined by system for house keeping(activation records)

    -- Container for a data value (a single number, character or a memory location)
    -- Classified as elementary object (manipulated as a single unit) or structured object (aggregated)
    -- Each data object has a lifetime (extent)

  • Attributes associated with a data object
    -- Name: Represent the object and is referred during execution time (N, M)
    -- Type: Specify the data values that the object may contain (int, char)
    -- Location: Address of the storage where the object is located (0x3a789b85)
    -- Value: Actual value that the object containes (30, 20)
    -- Component: The binding of a data object to one or more data objects (S[10])
    -- Operations: Mechanisms to manipulate the object (+, -)

  • Variable
    -- A data object that is defined and named by programmer explicitly in a program
    -- The content(value) of a variable can be changed during its life time
    -- Simple variable : an elementary data object with a name
    -- Complex variable : group of variables

  • Constant
    -- A data object with a name which is bound to a value permanently during its lifetime
    -- Types of constants
    -- Literal : representation is the written representation of the value
    -- Programmer defined constant : name is chosen by the programmer


  • Data type
    : A class of data objects together with a set of operations for creation and manipulation
    : Examples of types are array, integer, file, float, etc.
    -- Classes of data type
    -- Primitive data type: built into the language
    -- User-defined data type: with facilities that the language provides
    -- Self-modifying types: content of data object is modified without programmer's control
    -- Specification and Implementation of data types
    -- Specification : a way of specifying defined data type as an object with attributes, values and operations
    -- Implementation : a way of simulating defined data type on the virtual computer wirh representation and algorithm

  • Specification
    -- Attributes: that distinguish data objects of that type
    ex) Number of dimensions, subject range, data type of components
    -- Values: that data objects of that type may have
    ex) Set of numbers
    -- Operations: that define the possible manipulations of data objects of that type
    ex) consider array data type
    Subscribing to select a component, create array, change shape, access attributes, and perform arithmetic on a pair of array

  • Implementation
    -- Storage representation: used to represent the data object of that type (integer is stored in a word)
    -- Algorithm: manner in which the operations are defined to manipulate the data object(procedures)

Elementary Data Type

  • What is the Elementary Data Type?
    : It contains a single data value, with various operations
    : Integer, Real, Character, Boolean, Enumeration, Pointer
  • Specification of Elementary Data Types
  1. Attributes
    -- Basic attributes(name, data type) are invariant during its life time
    -- Attribute information could be stored in dope vector(descriptor) or only used to determine storage size
  2. Values
    -- Type of an object determines the set of possible data values
    -- Usually closely related to the values that the underlying hardware provides
    -- The set of values for a data type is usually an ordered set
  3. Operations
    -- Determine how data objects of that type may be manipulated
    -- Primitive operation: part of language definition
    -- Programmer defined operation: form of subprograms, or method declaration
    -- Elements of an operation
    Domain : a set of possible input values
    Range : a set of result values
    Action : determines results from any given set of input values
    -- Signature is used to specify and operation's elements

  • Four main factors that combine to obsucre the definitions of operations
  1. Operations undefined for centain inputs or outputs
  2. Implicit arguments: use of global variable
  3. Side effects (implicit results): change global variable
  4. Self-modification: history sensitive actions like counter, random number generator, LISP allows self modification through code change ( + 4 5 )
  • Subtype (subtype polymorphism)
    -- a form in which a datatype is related to another datatype (the super type)
    -- program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype
    -- Time & Space complexity are reduced


  • Implementation of elementary data types
    -- Storage representation for data objects and values of that type
    -- Strongly influenced on underlying hardware (efficient)
    -- Sometimes it is software simulated(inefficient)
    -- Data attributes are determined by compiler in many languages or sometimes data attributes are stored in a descriptor vector (e.g. LISP)
    -- Set of algorithms or procedures that defines the operations of the type
    -- Directly implemented by hardware
    -- As a procedure or function subprogram
    -- As in-line code sequence

  • Declarations
    -- Definition
    : Statements that specify information about the name, type of data object, and lifetime of each object
    -- Explicit declaration vs. Implicit (default) declaration

    -- Declaration of operations can be done by the signature of each operation

  • Purpose of declaration

  1. Choice of stroage representation for translator
  2. Storage management by specifying the lifetime of variables
  3. Polymorphic operations
  4. Type checking
  • Polymorphic operations
    -- Polymorphic function : a subprogram of function that can assume more than one type
    -- Ex) f(x) = x in PASCAL
    function f(x:int): int;
    function f(x:boolean): boolean;
    function f(x:real): real;
  1. Ad hoc polymorphism
    : Different code for different manifestations of the operators
    : Overloading
    : Implicit coercion
  2. Universal polymorphsim (Generic Polymorphism)
    : A function name selects on a variety of implementations depending on the types of its arguments

  • Type Checking
    : Checking the proper number of arguments of the proper data type of each operations
  1. Static type checking
    -- Operation checking: number and types of arguments and results
    -- Variable checking: type of object under the name
    -- Type of constant: syntactic form of literals
    -- Efficient but not flexible
  2. Dynamic type checking
    -- Difficult to debug
    -- Slow execution speed for type checking
    -- Limit the compiler optimization due to unknown factors
    -- Flexibility is enhanced but inefficient
  3. Strong typing
    -- Detect all type errors statically
  • Volatile Type
    -- Variable type whose value could be changed by outside operation
    -- Optimization is not applied to the volatile variables
    -- Use of volatile types
    (1) MMIO (Memory-mapped I/O)
    (2) Interrupt Service Routine
    (3) Multi-Thread Environment
  • Type safe system
    : A function cannot generate result with a type outside of the signature

  • Type inference
    -- Types can be resolved from the program by how they are used
    -- Ex) fun area (length : int, width: int)
    int= length*width

  • Type conversion
    -- Takes one type and produce the corresponding type
    -- Explicit type conversion by using a set of built-in functions
    -- Implicit type conversion (type coercion = 묵시적형변환) as specified in the language
    -- Basic principle is "not to lose information" called widening, or promotion


Integers

  1. Specification
  • Attribute : type attribute integer only
  • Value : ordered and finite subset of integer values
  • Operations :
    -- Arithmetic operations - BinaryOp( +, -, x, /, mod ), UnaryOp(-, +, abs)
    -- Relational operations - ( equal, not equal, less-than... )
    -- Assignment operations - ( :=, = )
    -- Bit operations - ( &, | , <<, >> )
  1. Implementation
  • Use complete memory word
  • Three possible storage representation
    -- No runtime descriptor
    -- Descriptor stored in seperate words (LISP)
    -- Descriptor stored in the same word

Floating point real numbers

  1. Specification
  • Attribute: type attribute real
  • Value: hardware determined numbers from min to max, and not evenly distributed
  • Operations: same operations with integers except boolean that has some restrictions(=)
  1. Implementation

    -- Split the storage location into mantissa and exponent (IEEE-754)

ex) Convert 118.625 (Decimal number) in IEEE 754 format
(1) Sign bit = 1
(2) Convert it to binary number : 1110110.101
(3) Left shift to make 1110110.101 = 1. 110110101 x 2^6 : Floating poing number
(4) Padding with 0's to make 23 bits : 110 1101 0100 0000 0000 0000
(5) Exponent is 6, thus add bias (127) and add 6 + 127 = 133 (1000 0101)

Fixed-point real numbers

  1. Specification
    -- Digit sequence of fixed length
    -- Avoid round-off errors (e.g. dollar and cents)
    -- Scale factor

  2. Implementation
    -- Either supported by hardware or simulated by software

    -- Calcultation is done after converting the numbers in the same format

Enumeration

  1. Specification
  • Allow a programmer to define and manipulate subranged variables more directly
  1. Implementation
  • Allocated within the minimum number of bits needed
  • Each entry is numbered with 1,2,3, ... and simple operations on the index numbers are used
  • Use primitive operations of the superset
profile
Business & Software 💗🏳️‍🌈🌎

0개의 댓글