$theTitle=wp_title(" - ", false); if($theTitle != "") { ?>
One Stop Computer Science
1 Jan // php the_time('Y') ?>
Introduction
–Only specification of results are stated (not detailed procedures for producing them)
Compound Terms
–Mathematical function is a mapping
–Can be written as a table
–Functor: function symbol that names the relationship
–Ordered list of parameters (tuple)
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
–a string of letters, digits, and underscores beginning with a lowercase letter
–a string of printable ASCII characters delimited by apostrophes
–Lasts only as long as it takes to satisfy one complete goal
functor(parameter list)
Overview of Logic Programming
–There is a simple way to determine the meaning of each statement
–Simpler than the semantics of imperative languages
–Programs do not state now a result is to be computed, but rather the form of the result
Rule Statements
–May be single term or conjunction
–Must be single term
Goal Statements
man(fred)
father(X, mike)
Approaches
Subgoal Strategies
–Depth-first search: find a complete proof for the first subgoal before working on others
–Breadth-first search: work on all subgoals in parallel
–Can be done with fewer computer resources
Backtracking
Trace
–Call (beginning of attempt to satisfy goal)
–Exit (when a goal has been satisfied)
–Redo (when backtrack occurs)
–Fail (when goal fails)
List Structures
[apple, prune, grape, kumquat]
[] (empty list)
[X | Y] (head X and tail Y)
Deficiencies of Prolog
–In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently
–The only knowledge is what is in the database
–Anything not stated in the database is assumed to be false
–It is easy to state a sort process in logic, but difficult to actually do—it doesn’t know how to sort
1 Jan // php the_time('Y') ?>
Introduction
Mathematical Functions
l(x) x * x * x
for the function cube(x) = x * x * x
Lambda Expression
e.g., (l(x) x * x * x)(2)
which evaluates to 8
Function Composition
LISP Data Type and Structures
e.g., (A B (C D) E)
LISP Interpretation
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
Special Form Function: DEFINE
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
List Functions
–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 ′apple ′orange ′grape) returns
(apple orange grape)
Predicate Functions
(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? 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? ‘()) yields #T
(NULL? ‘(())) yields #F
Tail Recursion in Scheme
Functional Form
–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
–Efficient execution
–Complex semantics
–Complex syntax
–Concurrency is programmer designed
–Simple semantics
–Simple syntax
–Less efficient execution
–Programs can automatically be made concurrent
1 Jan // php the_time('Y') ?>
Introduction
Exception Handling
–When an exception occurs, control goes to the operating system, where a message is displayed and the program is terminated
–Programs are allowed to trap some exceptions, thereby providing the possibility of fixing the problem and continuing
Event Handling
Comparison of Exception Handling in C++ and Java
Both languages use try, catch and throw keywords for exception handling, and meaning of try, catch 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:
C#:
A radio button is tested with the Boolean Checked property of the button
private void rb_CheckedChanged (object o,
EventArgs e) {
if (plain.Checked) …
…
}
plain.CheckedChanged +=
new EventHandler (rb_CheckedChanged);
1 Jan // php the_time('Y') ?>
1 Jan // php the_time('Y') ?>
Introduction
–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
–Polymorphism
Inheritance
–ADTs are difficult to reuse—always need changes
–All ADTs are independent and at the same level
–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
Dynamic Binding
Dynamic Binding Concept
Exclusivity of Objects
–Advantage – elegance and purity
–Disadvantage – slow operations on simple objects
–Advantage – fast operations on simple objects
–Disadvantage – results in a confusing type system (two kinds of entities)
–Advantage – fast operations on simple objects and a relatively small typing system
–Disadvantage – still some confusion because of the two type systems
Nested 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
–Which facilities of the nesting class should be visible to the nested class and vice versa
Dynamic Binding of Methods Calls
–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.
1 Jan // php the_time('Y') ?>
Concept of Abstraction
Encapsulation Construct
–Some means of organization, other than simply division into subprograms
–Some means of partial compilation (compilation units that are smaller than the whole program)
Nested Subprograms
Encapsulation in C
Encapsulation in C++
–The class is used as the interface (prototypes)
–The member definitions are defined in a separate file
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
–Can place each library in its own namespace and qualify names used outside with the namespace
–C# also includes namespaces
–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.
Access to the contents of a module is requested with the require method.
21 Dec // php the_time('Y') ?>
Setiap subprogram memiliki single entry point. Sebuah program yang dipanggil saat eksekusi disebut subprogram.
Local Variable
Keuntungan:
Kerugian:
Parameter Passing Methods
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.
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
21 Dec // php the_time('Y') ?>
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++:
loop body
loop body
while (control_expr)
Iteration Based on Data Structures
Contoh:
– current points at one element of the array
– next moves current to the next element
– reset moves current to the first element
For arrays and any other class that implements the Iterable interface, e.g., ArrayList
–
for (String myElement : myList) { … }
30 Nov // php the_time('Y') ?>
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
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:
Berikut adalah urutan eksekusi operator:
Berikut adalah urutan evaluasi operand:
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>
19 Oct // php the_time('Y') ?>
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:
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:
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:
Implementasi dari User-Defined Ordinal Types
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.
Recent Comments