Programming Language Concept

One Stop Computer Science

Archive for the ‘Uncategorized’ Category

Introduction

  • Programs in logic languages are expressed in a form of symbolic logic
  • Use a logical inferencing process to produce results
  • Declarative rather that procedural:

–Only specification of results are stated (not detailed procedures for producing them)

Compound Terms

  • Atomic propositions consist of compound terms
  • Compound term: one element of a mathematical relation, written like a mathematical function

–Mathematical function is a mapping

–Can be written as a table

  • Compound term composed of two parts

–Functor: function symbol that names the relationship

–Ordered list of parameters (tuple)

  • Examples:

student(jon)

like(seth, OSX)

like(nick, windows)

like(jim, linux)

Logical Operators

Name Symbol Example Meaning
negation Ø Ø a not a
conjunction Ç a Ç b a and b
disjunction È a È b a or b
equivalence º a º b a is equivalent to b
implication É

Ì

a É b

a Ì b

a implies b

b implies a

Quantifiers

Name Example Meaning
universal “X.P For all X, P is true
existential $X.P There exists a value of X such that P is true

Terms

  • This book uses the Edinburgh syntax of Prolog
  • Term: a constant, variable, or structure
  • Constant: an atom or an integer
  • Atom: symbolic value of Prolog
  • Atom consists of either:

–a string of letters, digits, and underscores beginning with a lowercase letter

–a string of printable ASCII characters delimited by apostrophes

  • Variable: any string of letters, digits, and underscores beginning with an uppercase letter
  • Instantiation: binding of a variable to a value

–Lasts only as long as it takes to satisfy one complete goal

  • Structure: represents atomic proposition

functor(parameter list)

Overview of Logic Programming

  • Declarative semantics

–There is a simple way to determine the meaning of each statement

–Simpler than the semantics of imperative languages

  • Programming is nonprocedural

–Programs do not state now a result is to be computed, but rather the form of the result

Rule Statements

  • Used for the hypotheses
  • Headed Horn clause
  • Right side: antecedent (if part)

–May be single term or conjunction

  • Left side: consequent (then part)

–Must be single term

  • Conjunction: multiple terms separated by logical AND operations (implied)

Goal Statements

  • For theorem proving, theorem is in form of proposition that we want system to prove or disprove – goal statement
  • Same format as headless Horn

  man(fred)

  • Conjunctive propositions and propositions with variables also legal goals

  father(X, mike)

Approaches

  • Matching is the process of proving a proposition
  • Proving a subgoal is called satisfying the subgoal
  • Bottom-up resolution, forward chaining
  • Top-down resolution, backward chaining
  • Prolog implementations use backward chaining

Subgoal Strategies

  • When goal has more than one subgoal, can use either

–Depth-first search:  find a complete proof for the first subgoal before working on others

–Breadth-first search: work on all subgoals in parallel

  • Prolog uses depth-first search

–Can be done with fewer computer resources

Backtracking

  • With a goal with multiple subgoals, if fail to show truth of one of subgoals, reconsider previous subgoal to find an alternative solution: backtracking
  • Begin search where previous search left off
  • Can take lots of time and space because may find all possible proofs to every subgoal

Trace

  • Built-in structure that displays instantiations at each step
  • Tracing model of execution – four events:

Call (beginning of attempt to satisfy goal)

Exit (when a goal has been satisfied)

Redo (when backtrack occurs)

Fail (when goal fails)

List Structures

  • Other basic data structure (besides atomic propositions we have already seen): list
  • List is a sequence of any number of elements
  • Elements can be atoms, atomic propositions, or other terms (including other lists)

  [apple, prune, grape, kumquat]

[]   (empty list)

  [X | Y]   (head X and tail Y)

Deficiencies of Prolog

  • Resolution order control

–In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently

  • The closed-world assumption

–The only knowledge is what is in the database

  • The negation problem

–Anything not stated in the database is assumed to be false

  • Intrinsic limitations

–It is easy to state a sort process in logic, but difficult to actually do—it doesn’t know how to sort

  • 0 Comments
  • Filed under: Uncategorized
  • Introduction

    • The design of the imperative languages is based directly on the von Neumann architecture
    • The design of the functional languages is based on mathematical functions

    Mathematical Functions

    • A mathematical function is a mapping of members of one set, called the domain set, to another set, called the range set
    • A lambda expression specifies the parameter(s) and the mapping of a function in the following form

    l(x) x * x * x

    for the function  cube(x) = x * x * x

    Lambda Expression

    • Lambda expressions describe nameless functions
    • Lambda expressions are applied to parameter(s) by placing the parameter(s) after the expression

    e.g.,   (l(x) x * x * x)(2)

    which evaluates to 8

    Function Composition

    • A functional form that takes two functions as parameters and yields a function whose value is the first actual parameter function applied to the application of the second

     

    LISP Data Type and Structures

    • Data object types: originally only atoms and lists
    • List form: parenthesized collections of sublists and/or atoms

    e.g., (A B (C D) E)

    • Originally, LISP was a typeless language
    • LISP lists are stored internally as single-linked lists

    LISP Interpretation

    • Lambda notation is used to specify functions and function definitions. Function applications and data have the same form.

    e.g., If the list (A B C) is interpreted as data it is

    a simple list of three atoms, A, B, and C

    If it is interpreted as a function application,

    it means that the function named A is

    applied to the two parameters, B and C

    • The first LISP interpreter appeared only as a demonstration of the universality of the computational capabilities of the notation

    Special Form Function: DEFINE

    • DEFINE – Two forms:

    1.To bind a symbol to an expression

    e.g., (DEFINE pi 3.141593)

    Example use: (DEFINE two_pi (* 2 pi))

    These symbols are not variables – they are like the names bound by Java’s final declarations

    2.To bind names to lambda expressions (LAMBDA is implicit)

    e.g., (DEFINE (square x) (* x x))

    Example use: (square 5)

    – The evaluation process for DEFINE is different! The first parameter is never evaluated. The second parameter is evaluated and bound to the first parameter.

    Output Function

    • Usually not needed, because the interpreter always displays the result of a function evaluated at the top level (not nested)
    • Scheme has PRINTF, which is similar to the printf function of C
    • Note: explicit input and output are not part of the pure functional programming model, because input operations change the state of the program and output operations are side effects

    List Functions

    • QUOTE – takes one parameter; returns the parameter without evaluation

    –QUOTE is required because the Scheme interpreter, named EVAL, always evaluates parameters to function applications before applying the function.  QUOTE is used to avoid parameter evaluation when it is not appropriate

    –QUOTE can be abbreviated with the apostrophe prefix operator

    ‘(A B) is equivalent to (QUOTE (A B))

    • LIST is a function for building a list from any number of parameters

    (LIST ′apple ′orange ′grape) returns

    (apple orange grape)

    Predicate Functions

    • EQ? takes two expressions as parameters (usually two atoms); it returns #T if both parameters have the same pointer value; otherwise #F

    (EQ? ‘A ‘A) yields #T

    (EQ? ‘A ‘B) yields #F

    (EQ? ‘A ‘(A B)) yields #F

    (EQ? ‘(A B) ‘(A B)) yields #T or #F

    (EQ? 3.4 (+ 3 0.4))) yields #T or #F

    • EQV? is like EQ?, except that it works for both symbolic and numeric atoms; it is a value comparison, not a pointer comparison

    (EQV? 3 3) yields #T

    (EQV? ‘A 3) yields #F

    (EQV 3.4 (+ 3 0.4)) yields #T

    (EQV? 3.0 3) yields #F  (floats and integers are different)

    • LIST? takes one parameter; it returns #T if the parameter is a list; otherwise #F

    (LIST? ‘()) yields #T

    • NULL? takes one parameter; it returns #T if the parameter is the empty list; otherwise #F

    (NULL? ‘(())) yields #F

    Tail Recursion in Scheme

    • Definition: A function is tail recursive if its recursive call is the last operation in the function
    • A tail recursive function can be automatically converted by a compiler to use iteration, making it faster
    • Scheme language definition requires that Scheme language systems convert all tail recursive functions to use iteration

    Functional Form

    • Composition

    –If h is the composition of f and g, h(x) = f(g(x))

    (DEFINE (g x) (* 3 x))

    (DEFINE (f x) (+ 2 x))

    (DEFINE h x) (+ 2 (* 3 x)))  (The composition)

    –In Scheme, the functional composition function compose can be written:

    (DEFINE (compose f g) (LAMBDA (x) (f (g x))))

    ((compose CAR CDR) ‘((a b) c d)) yields c

    (DEFINE (third a_list)

    ((compose CAR (compose CDR CDR)) a_list))

    is equivalent to CADDR

    Comparing Functional and Imperative Language

    • Imperative Languages:

    –Efficient execution

    –Complex semantics

    –Complex syntax

    –Concurrency is programmer designed

    • Functional Languages:

    –Simple semantics

    –Simple syntax

    –Less efficient execution

    –Programs can automatically be made concurrent

  • 0 Comments
  • Filed under: Uncategorized
  • Introduction

    Exception Handling

    • In a language without exception handling

    –When an exception occurs, control goes to the operating system, where a message is displayed and the program is terminated

    • In a language with exception handling

    –Programs are allowed to trap some exceptions, thereby providing the possibility of fixing the problem and continuing

    Event Handling

    • An event is a notification that something specific has occurred, such as a mouse click on a graphical button
    • The event handler is a segment of code that is executed in response to an event

    Comparison of Exception Handling in C++ and Java

    Both languages use trycatch and throw keywords for exception handling, and meaning of trycatch and free blocks is also same in both languages. Following are the differences between Java and C++ exception handling.

    1) In C++, all types (including primitive and pointer) can be thrown as exception. But in Java only throwable objects (Throwable objects are instances of any subclass of the Throwable class) can be thrown as exception. For example, following type of code works in C++, but similar code doesn’t work in Java.

    #include <iostream>
    using namespace std;
    int main()
    {
       int x = -1;
       // some other stuff  
       try {
          // some other stuff
          if( x < 0 )
          {
             throw x;
          }  
       }
       catch (int x ) {
          cout << "Exception occurred: thrown value is " << x << endl;
       }
       getchar();
       return 0;
    }

    Output:
    Exception occurred: thrown value is -1

    2) In C++, there is a special catch called “catch all” that can catch all kind of exceptions.

    #include <iostream>
    using namespace std;
    int main()
    {
       int x = -1;
       char *ptr;
       
       ptr = new char[256];
       
       // some other stuff  
       try {
          // some other stuff
          if( x < 0 )
          {
             throw x;
          }     
          if(ptr == NULL)
          {
             throw " ptr is NULL ";
          }  
       }
       catch (...) // catch all
       {
          cout << "Exception occurred: exiting "<< endl;
          exit(0);
       }
       
       getchar();
       return 0;
    }

    Output:
    Exception occurred: exiting

    In Java, for all practical purposes, we can catch Exception object to catch all kind of exceptions. Because, normally we do not catch Throwable(s) other than Exception(s) (which are Errors)

    catch(Exception e){
      …….
    }

    3) In Java, there is a block called finally that is always executed after the try-catch block. This block can be used to do cleanup work. There is no such block in C++.

    // creating an exception type
    class Test extends Exception { }
    class Main {
       public static void main(String args[]) {
          try {
             throw new Test();
          }
          catch(Test t) {
             System.out.println("Got the Test Exception");
          }
          finally {
             System.out.println("Inside finally block ");
          }
      }
    }

    Output:
    Got the error
    Inside finally block

    4) In C++, all exceptions are unchecked. In Java, there are two types of exceptions – checked and unchecked. See this for more details on checked vs Unchecked exceptions.

    5) In Java, a new keyword throws is used to list exceptions that can be thrown by a function. In C++, there is no throws keyword, the same keyword throw is used for this purpose also.

    Event Handling

    Java:

    • One class of events is ItemEvent, which is associated with the event of clicking a checkbox, a radio button, or a list item
    • The ItemListener interface prescribes a method, itemStateChanged, which is a handler for ItemEvent events
    • The listener is created with addItemListener

    C#:

    • An application subclasses the Form predefined class (defined in System.Windows.Forms)
    • Label objects are used to place text in the window
    • Radio buttons are objects of the RadioButton class
    • An event handler can have any name

    A radio button is tested with the Boolean Checked property of the button

    private void rb_CheckedChanged (object o,

    EventArgs e) {

    if (plain.Checked) …

    }

    • To register an event, a new EventHandler object must be created and added to the predefined delegate for the event
    • When a radio button changes from unchecked to checked, the CheckedChanged event is raised
    • The associated delegate is referenced by the name of the event
    • If the handler was named rb_CheckedChanged, we could register it on the radio button named plain with:

    plain.CheckedChanged +=

    new EventHandler (rb_CheckedChanged);

  • 0 Comments
  • Filed under: Uncategorized
  • Session X: Concurrency

    Introduction
    Concurrency can occur at four levels:
    • Machine instruction level
    • High-level language statement level
    • Unit level
    • Program level
    Because there are no language issues in instruction- and program-level concurrency, they are not addressed here
     
    Introduction to Subprogram-Level Concurrency
    •A task or process or thread is a program unit that can be in concurrent execution with other program units
    •Tasks differ from ordinary subprograms in that:
    – A task may be implicitly started
    – When a program unit starts the execution of a task, it is not necessarily suspended
    – When a task’s execution is completed, control may not return to the caller
    •Tasks usually work together
     
    Two General Categories of Tasks
    • Heavyweight tasks execute in their own address space
    • Lightweight tasks all run in the same address space – more efficient
    A task is disjoint if it does not communicate with or affect the execution of any other task in the program in any way
     
    Task Synchronization
    •A mechanism that controls the order in which tasks execute
    •Two kinds of synchronization
    Cooperation synchronization
    Competition synchronization
    •Task communication is necessary for synchronization, provided by: – Shared nonlocal variables – Parameters – Message passing
     
    Kinds of synchronization
    • Cooperation: Task A must wait for task B to complete some specific activity before task A can continue its execution, e.g., the producer-consumer problem
    • Competition: Two or more tasks must use some resource that cannot be simultaneously used, e.g., a shared counter
    Competition is usually provided by mutually exclusive access.
     
    Need for Competition Synchronization
     
    Scheduler
    • Providing synchronization requires a mechanism for delaying task execution
    • Task execution control is maintained by a program called the scheduler, which maps task execution onto available processors
    Task Execution States
    1. New – created but not yet started
    2. Ready – ready to run but not currently running (no available processor)
    3. Running
    4. Blocked – has been running, but cannot now continue (usually waiting for some event to occur)
    5. Dead – no longer active in any sense
    Liveness and Deadlock
    Liveness is a characteristic that a program unit may or may not have – In sequential code, it means the unit will eventually complete its execution
    •In a concurrent environment, a task can easily lose its liveness
    •If all tasks in a concurrent environment lose their liveness, it is called deadlock
     
    Methods of Providing Synchronization
    • Semaphores
    • Monitors
    • Message Passing
    Competition Synchronization with Semaphores
    • A third semaphore, named access, is used to control access (competition synchronization)
    – The counter of access will only have the values 0 and 1
    – Such a semaphore is called a binary semaphore
    • Note that wait and release must be atomic!
    Competition Synchronization
    • Shared data is resident in the monitor (rather than in the client units)
    • All access resident in the monitor
    –Monitor implementation guarantee synchronized access by allowing only one access at a time
    –Calls to monitor procedures are implicitly queued if the monitor is busy at the time of the call
     
    Cooperation Synchronization
    Cooperation between processes is still a programming task
    As a Programmer must guarantee that a shared buffer does not experience underflow or overflow
    Message Passing
    •Message passing is a general model for concurrency
    – It can model both semaphores and monitors
    – It is not just for competition synchronization
    •Central idea: task communication is like seeing a doctor–most of the time she waits for you or you wait for her, but when you are both ready, you get together, or rendezvous
     
    Rendezvous Time Lines
     
     
    Message Passing: Server/Actor Tasks
    •A task that has accept clauses, but no other code is called a server task (the example above is a server task)
    •A task without accept clauses is called an actor task
    – An actor task can send messages to other tasks
    – Note: A sender must know the entry name of the receiver, but not vice versa (asymmetric)
     
    Graphical Representation of a Rendezvous
     
     
    Multiple Entry Points
    Tasks can have more than one entry point
    – The specification task has an entry clause for each
    – The task body has an accept clause for each entry clause, placed in a select clause, which is in a loop
     
    Cooperation Synchronization with Message Passing
    Provided by Guarded accept clauses
     
    An accept clause with a with a when clause is either open or closed –A clause whose guard is true is called open –A clause whose guard is false is called closed –A clause without a guard is always open
  • 0 Comments
  • Filed under: Uncategorized
  • Introduction

    • Many object-oriented programming (OOP) languages

    –Some support procedural and data-oriented programming (e.g., Ada 95+ and C++)

    –Some support functional program (e.g., CLOS)

    –Newer languages do not support other paradigms but use their imperative structures (e.g., Java and C#)

    –Some are pure OOP language (e.g., Smalltalk & Ruby)

    –Some functional languages support OOP, but they are not discussed in this chapter.

    Three major language features:

    –Abstract data types (Chapter VIII)

    –Inheritance

    • Inheritance is the central theme in OOP and languages that support it

    –Polymorphism

    Inheritance

    • Productivity increases can come from reuse

    –ADTs are difficult to reuse—always need changes

    –All ADTs are independent and at the same level

    • Inheritance allows new classes defined in terms of existing ones, i.e., by allowing them to inherit common parts
    • Inheritance addresses both of the above concerns–reuse ADTs after minor changes and define classes in a hierarchy
    • Inheritance can be complicated by access controls to encapsulated entities–A class can hide entities from its subclasses

      –A class can hide entities from its clients

      –A class can also hide entities for its clients while allowing its subclasses to see them

      –The new one overrides the inherited one

      –The method in the parent is overriden

      Besides inheriting methods as is, a class can modify an inherited method

    Object Oriented Concepts

    • ADTs are usually called classes
    • Class instances are called objects
    • A class that inherits is a derived class or a subclass
    • The class from which another class inherits is a parent class or superclass
    • Subprograms that define operations on objects are called methods
    • Calls to methods are called messages
    • The entire collection of methods of an object is called its message protocol or message interface
    • Messages have two parts–a method name and the destination object
    • In the simplest case, a class inherits all of the entities of its parent

    Dynamic Binding

    • A polymorphic variable can be defined in a class that is able to reference (or point to) objects of the class and objects of any of its descendants
    • When a class hierarchy includes classes that override methods and such methods are called through a polymorphic variable, the binding to the correct method will be dynamic
    • Allows software systems to be more easily extended during both development and maintenance

    Dynamic Binding Concept

    • An abstract method is one that does not include a definition (it only defines a protocol)
    • An abstract class is one that includes at least one virtual method
    • An abstract class cannot be instantiated

    Exclusivity of Objects

    • Everything is an object

    –Advantage – elegance and purity

    –Disadvantage – slow operations on simple objects

    • Add objects to a complete typing system

    –Advantage – fast operations on simple objects

    –Disadvantage – results in a confusing type system (two kinds of entities)

    • Include an imperative-style typing system for primitives but make everything else objects

    –Advantage – fast operations on simple objects and a relatively small typing system

    –Disadvantage – still some confusion because of the two type systems

    Nested Classes

    • If a new class is needed by only one class, there is no reason to define so it can be seen by other classes

    –Can the new class be nested inside the class that uses it?

    –In some cases, the new class is nested inside  a subprogram rather than directly in another class

    • Other issues:

    –Which facilities of the nesting class should be visible to the nested class and vice versa

    Dynamic Binding of Methods Calls

    • Methods in a class that are statically bound need not be involved in the CIR; methods that will be dynamically bound must have entries in the CIR

    –Calls to dynamically bound methods can be connected to the corresponding code thru a pointer in the CIR

    –The storage structure is sometimes called virtual method tables  (vtable)

    –Method calls can be represented as offsets from the beginning of the vtable.

  • 0 Comments
  • Filed under: Uncategorized
  • Session VIII: Abstract Data Type

    Concept of Abstraction

    • An abstraction is a view or representation of an entity that includes only the most significant attributes
    • The concept of abstraction is fundamental in programming (and computer science)
    • Nearly all programming languages support process abstraction with subprograms
    • Nearly all programming languages designed since 1980 support data abstraction

    Encapsulation Construct

    • Large programs have two special needs:

    –Some means of organization, other than simply division into subprograms

    –Some means of partial compilation (compilation units that are smaller than the whole program)

    • Obvious solution: a grouping of subprograms that are logically related into a unit that can be separately compiled (compilation units)
    • Such collections are called encapsulation

    Nested Subprograms

    • Organizing programs by nesting subprogram definitions inside the logically larger subprograms that use them
    • Nested subprograms are supported in Ada, Fortran 95+, Python, JavaScript, and Ruby

    Encapsulation in C

    • Files containing one or more subprograms can be independently compiled
    • The interface is placed in a header file
    • Problem: the linker does not check types between a header and associated implementation
    • #include preprocessor specification – used to include header files in applications

    Encapsulation in C++

    • Can define header and code files, similar to those of C
    • Or, classes can be used for encapsulation

    –The class is used as the interface (prototypes)

    –The member definitions are defined in a separate file

    • Friends provide a way to grant access to private members of a class

    The danger of C’s approach to encapsulation:
    There are two problems with this approach. First, the documentation of the dependence of the client program on the library (and its header file) is lost. Second, the author of the library could change the header file and the implementation file, but the client could attempt to use the new implementation file (not realizing it had changed) but with the old header file, which the user had copied into his or her client program.

    Naming Encapsulation

    • Large programs define many global names; need a way to divide into logical groupings
    • A naming encapsulation is used to create a new scope for names
    • C++ Namespaces

    –Can place each library in its own namespace and qualify names used outside with the namespace

    –C# also includes namespaces

    • Java Packages

    –Packages can contain more than one class definition; classes in a package are partial friends

    –Clients of a package can use fully qualified name or use the import declaration

    Similarities between Java Packages dan C++ Namespace:

    1) Java Packages are namespaces system while C++ also has namespace
    2) Both are abstract containers for classes
    3) Java Packages and namespaces provide breakup for class names
    4) both make the code cleaner and less redundant, by enabling some
    parts of the code.
    Difference between Java Packages and C++ Namespace:
    1) Java packages are about modules meanwhile, in C++ namespaces are just about partitioning the available names.
    2) In Java language, namespaces are intended to avoid conflicts between names in different parts of class libraries.
    3) C++ namespaces have an extra way to encapsulate stuff within an already existing system.

    • Ruby classes are name encapsulations, but Ruby also has modules
    • Typically encapsulate collections of constants and methods
    • Modules cannot be instantiated or subclassed, and they cannot define variables
    • Methods defined in a module must include the module’s name

    Access to the contents of a module is requested with the require method.

  • 0 Comments
  • Filed under: Uncategorized
  • Session VII: Subprograms

    Setiap subprogram memiliki single entry point. Sebuah program yang dipanggil saat eksekusi disebut subprogram.

    Local Variable

    Keuntungan:

    • mendukung rekursi
    • penyimpanan untuk local variable dapat berbagi dengan beberapa subprogram

    Kerugian:

    • Allocation/de-allocation, initialization time
    • Indirect addressing
    • Subprogram tidak history sensitive
    • Local variable dapat menjadi static.

    Parameter Passing Methods

    1. Pass-by-Value

    Nilai dari actual parameter digunakan untuk inisialisasi corresponding formal parameter. Dapat diimplementasikan dengan copying atau dapat pula diimplementasikan dengan mentransmit sebuah access path tetapi tidak direkomendasikan.

    Kerugian bila menggunakan physical move: membutuhkan storage tambahan dan actual move dapat menimbulkan kerugian materi.

    Kerugian bila menggunakan access path method: harus menggunakan write-protect dalam subprogram dan access memakan cost lebih.

    2. Pass-by-Result

    Dalam proses ini, tidak ada nilai yang ditransmit ke subprogram, corresponding formal parameter bertindak sebagai local variable. Membutuhkan extra storage dan copy operation.

    3. Pass-by-Reference

    Melalui sebuah access path. Biasa dikenal juga dengan nama pass-by-sharing.

    Keuntungan: proses dilakukan dengan efisien (tanpa copying dan tanpa extra storage).

    Kerugian: proses berjalan lebih lamban dibandingkan pass-by-value, berpotensi menimbulkan efek samping dan aliases yang tidak diinginkan.

    Overloaded Subprogram

    • An overloaded subprogram is one that has the same name as another subprogram in the same referencing environment.

    • Every version of an overloaded subprogram has a unique protocol.
    • C++, Java, C#, and Ada include predefined overloaded subprograms.

    • In Ada, the return type of an overloaded function can be used to disambiguate calls (thus two overloaded functions can have the same parameters).

    • Ada, Java, C++, and C# allow users to write multiple versions of subprograms with the same name.

    Generic Subprogram

    • A generic or polymorphic subprogram takes parameters of different types on different activations.

    • Overloaded subprograms provide ad hoc polymorphism.

    • Subtype polymorphism means that a variable of type T can access any object of type T or any type derived from T (OOP languages).

    • A subprogram that takes a generic parameter that is used in a type expression that describes the type of the parameters of the subprogram provides parametric polymorphism.

    • A cheap compile-time substitute for dynamic binding

  • 0 Comments
  • Filed under: Uncategorized
  • Control structure adalah sebuah stament yang eksekusinya dikontrol oleh control statement.

    Selection statement mengartikan pilihan antara dua atau lebih statement yang akan dieksekusi. Terdapat dua kategori, yaitu: two way selectors dan multiple way selectors.

    Contoh dari two way selectors adalah nesting selector. Contohnya dalam Java:

    if (sum == 0)

    if (count == 0)

    result = 0;

    else result = 1;

    Contohnya dalam C, C++, dan C#:

    if (sum == 0) {

    if (count == 0)

    result = 0;

    }

    else result = 1;

    Contohnya dalam bahasa Ruby:

    if sum == 0 then

    if count == 0 then

    result = 0

    else

    result = 1

    end

    end

    Contohnya dalam bahasa Phyton:

    if sum == 0 :

    if count == 0 :

    result = 0

    else :

    result = 1

    Contoh dari multiple way selectors adalah switch() case dan if else if.

    Contohnya dalam C, C++, Java, dan JavaScript:

      switch (expression) {

    case const_expr1: stmt1;

    case const_exprn: stmtn;

    [default: stmtn+1]

    }

    Contohnya dalam bahasa Ruby:

    leap = case

    when year % 400 == 0 then true

    when year % 100 == 0 then false

    else year % 4 == 0

    end

    Contohnya dalam Phyton:

    if count < 10 :

    bag1 = True

    elif count < 100 :

    bag2 = True

    elif count < 1000 :

    bag3 = True

     

    Iterative Statements

    iterative statements adalah sebuah perulangan eksekusi dari suatu statement atau compound statement yang dilakukan oleh iterasi maupun rekursi.

    Counter Controlled Loops

    Counter Controlled Loops adalah sebuah perhitungan iterative statement yang memiliki loop variable, memiliki initial dan terminal yang jelas, dan stepsize value.

    Logically Controlled Loops

    Logically controlled loops adalah perulangan yang dikontrol berdasarkan dari Boolean expression. Logically controlled loops dibagi menjadi 2, yaitu: pre-test dan post-test. Contoh dari pre-test adalah operasi while, dan contoh dari post-test adalah do-while. Contoh dalam bahasa C dan C++:

    • while (control_expr)

    loop body

    • do

    loop body

    while (control_expr)

    Iteration Based on Data Structures

    Contoh:

    • PHP

    – current points at one element of the array

    – next moves current to the next element

    – reset moves current to the first element

    • Java 5.0 (uses for, although it is called foreach)

    For arrays and any other class that implements the Iterable interface, e.g., ArrayList

    for (String myElement : myList) { … }

  • 0 Comments
  • Filed under: Uncategorized
  • Introduction

    Expression adalah dasar dari komputasi kompleks dalam bahasa pemrogaman. Untuk memahami expression, kita harus terlebih dahulu memahami urutan operator dan evaluasi operand.

    Expression terdiri dari 4 bagian, yaitu:

    • Short Circuit Evaluation
    • Arithmatic Expression
    • Relational Expression
    • Boolean Expression

    Short Circuit Evaluation

    Short circuit evaluation adalah sebuah expression yang hasilnya tidak ditentukan dari evaluasi seluruh operand dan atau semua operator. Short circuit evaluation dalam C, C++, dan Java digunakan untuk Boolean operators (&& dan ||), tetapi juga menyediakan bitwise Boolean operators yang tidak short circuit evaluation (& dan |).

    Arithmatic Expression

    Arithmatic expression terdiri dari operator, operand, parentheses, dan function calls.

    Berbagai macam operator:

    • Unary operator memiliki 1 operand.
    • Binary operator memiliki 2 operand.
    • Ternary operator memiliki 3 operand.

    Berikut adalah urutan eksekusi operator:

    • Parentheses
    • unary operators
    • ** (jika bahasa yang digunakan support)
    • *,/
    • +,-

    Berikut adalah urutan evaluasi operand:

    • Variables
    • Constants
    • Parenthesized Expression
    • Operand yang merupakan function call.

    Relational Expressions

    Relational expression menggunakan relational operators dan operands dari berbagai type. Relational expression dapat dievaluasi dalam sebagian Boolean representation.  Relational expression memiliki 2 operand dan 1 operator serta memiliki hasil Boolean.

    Boolean Expression

    Boolean expression menggunakan operand Boolean dan hasilnya adalah Boolean. Operatornya merupakan function call (and, or, not).

    Grammar

    I. A Grammar for Small Language

    <program> -> begin<stmt,list>end

    <stmt,list> -> <stmt>

    |<stmt>;<stmt,list>

    <stmt> -> <var>=<expr>

    <var> -> A|B|C

    <expr> -> <var>+<var>

    |<var>-<var>

    |<var>

    II. A Grammar for Simple Assignment Statement

    <asign> -> <id>=<expr>

    <id> -> A|B|C

    <expr> -> <id>+<expr>

    |<id>*<expr>

    |(<expr>)

    |<id>

    III. An Unambiguous Grammar for Expressions

    <asign> -> <id>=<expr>

    <id> -> A|B|C

    <expr> -> <expr>+<term>

    |<expr>

    <term> -> <term>*<factor>

    |<factor>

    <factor> -> (<expr>)

    |<id>

  • 0 Comments
  • Filed under: Uncategorized
  • Session IV: Data Types

    Introduction

    Data Type adalah sebuah koleksi data dari objek dan sebuah set dari operasi yang telah ditentukan terhadap objek tersebut.

    Descriptor adalah koleksi dari atribut sebuah variabel.

    Sebuah objek mewakili contoh dari sebuah tipe user-defined (abstract data).

    Primitive Data Types

    Hampir seluruh bahasa pemrograman menyediakan primitive data types. Contoh Primitive Data Types adalah integer, floating point, complex, decimal, boolean, character.

    Character String Types

    Nilainya merupakan sekumpulan karakter. Contoh: assignment and copying, comparison, catenation, substring reference, dan pattern matching.

    Implementation:

    • Static length: compile-time descriptor
    • Limited dynamic length: membutuhkan run-time descriptor untuk length.
    • Dynamic length: membutuhkan run-time descriptor; alokasi/dealokasi merupakan masalah terbesar dalam implementasi.

    User-Defined Ordinal Types

    Ordinal type memiliki jangkauan yang dapat dengan mudah dikaitkan dengan sebuah set dari integer positif. Contoh: integer, char, boolean.

    Enumeration Types

    Semua nilai yang memungkinkan (named constants) dapat dimengerti. Contoh: enum days {mon, tue, wed, thu, fri, sat, sun};

    Keuntungan menggunakan Enumerated type:

    • readability: tidak diperlukan untuk mengkode warna sebagai angka.
    • reliability: compiler dapat memeriksa: operasi (tidak mengijinkan warna untuk ditambahkan), tidak ada enumeration variable yang dapat mendaftarkan nilai diluar jangkauannya.

    Subrange Types

    Subrange types adalah tipe data yang terdiri atas data yang berasal dari data type lain dalam jangkauan. Contoh:

    type Days is (mon, tue, wed, thu, fri, sat, sun);

    subtype Weekdays is Days range mon..fri;

    subtype Index is Integer range 1..100;

    Day1: Days;

    Day2: Weekday;

    Day2 := Day1;

    Keuntungan:

    • readability: menjelaskan kepada pembaca bahwa variabel dari subrange hanya dapat menyimpan dalam jangkauan tertentu.
    • reliability: nilai yang berada diluar jangkauan tertentu akan menyebabkan error.

    Implementasi dari User-Defined Ordinal Types

    • Enumeration types diimplementasikan sebagai integer
    • Subrange types diimplementasikan seperi tipe induk dengan kode yang dimasukan oleh compiler untuk memberi jangkauan kepada subrange variables.

    Decimal Data Types

    Keuntungannya adalah dapat menyimpan nilai desimal dengan tepat dalam kisaran terbatas yang tidak dapat dilakukan oleh floating point. Kelemahannya ialah nilai dibatasi karena tidak ada eksponen dan memakan agak banyak memori.

    Nilai desimal disimpan seperti karakter string (menggunakan kode biner untuk setiap digit desimal). Hal ini disebut binary coded decimal (BCD). Terkadang BCD disimpan satu digit per byte namun terkadang pula disimpan dua digit per byte. Hal ini menyebabkan nilai desimal memakan lebih banyak memory dibandingkan binary (paling sedikit membutuhkan empat bits untuk mengkode sebuah digit desimal, sedangkan untuk angka yang sama, binary hanya membutuhkan 20 bits.

    Type Checking

    Type checking adalah aktifitas yang memeriksa apakah operands dari sebuah operator sesuai dengan data type yang digunakan. Compatible type adalah operator yang sesuai ataupun yang dibawah aturan bahasa dapat dikonversi oleh compiler-generated code menjadi legal type. Type error adalah kesalahan yang disinyalir oleh operator kepada operand dari tipe yang tidak sesuai.

    Static Type Checking and Dynamic Type Checking

    Static type checking dapat menemukan kesalahan mengetik pada awal development cycle, dapat mengkompilasi (compile) lebih cepat karena kompiler mengetahui data type yang digunakan, lebih teliti (dapat mendeteksi type error yang sulit ditemukan), menghasilkan kode yang lebih optimal.
    Sedangkan pada dynamic type checking, dapat terjadi run time error dikarenakan type error dan menghasilkan kode yang kurang optimal.

    Strong Typing

    Aturan coercion sangat berpengaruh terhadap strong typing. Aturan coercion adalah koversi atau perubahan nilai (operand dari sebuah operator) ke data type (legal type dari compiler-generated code) lain secara implisit yang dilakukan secara otomatis.
    Contoh: sebuah variabel int dan float 6.13 Strong Typing 303 variable ditambahkan di Java, maka nilai variabel int akan dipaksa berubah menjadi float dan ditambahkan floating point. Aturan coercion sangat melemahkan strong typing. Aturan coercion mengurangi kemampuan mendeteksi type error dari kompiler. Aturan coercion merupakan konversi otomatis ke sebuah legal type operand dari sebuah operator yang artinya legal type tidak akan dibaca sebagi type error.
    Contoh: jika sebuah program memiliki a dan b sebagai variabel int dan d sebagai variable float. Sang programmer ingin mengetik a + b namun secara tidak sengaja mengetik a + d, kesalahan ini tidak akan dideteksi oleh compiler. Nilai a akan dipaksa berubah menjadi float. Sehingga, nilai strong typing akan dilemahkan oleh coercion.

  • 0 Comments
  • Filed under: Uncategorized