Session 13

Session 13

Saturday, 13 January 2018

Today is the last session before the final exam. This session talks about "Logic Programming Language". This session, Miss Yanfi make a mind-map/concept-map for us.

Programs in logic languages are expressed in a form of symbolic logic. Symbolic logic is logic which can be used for the basic needs of formal logic.

Objects in propositions are represented by simple terms: either constants or variables. Atomic propositions consist of compound terms,  elements of a mathematical relation, written like a mathematical function. 

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.

The origin of prolog:

• University of Aix-Marseille (Calmerauer & Roussel)

– Natural language processing.

• University of Edinburgh (Kowalski)

– Automated theorem proving.

Term is a constant, variable, or structure. Constant is an atom or an integer. Atom is symbolic value of Prolog. Atom consists of either a string of letters, digits, and underscores beginning with a lowercase letter or a string of printable ASCII characters delimited by apostrophes.

Variable is any string of letters, digits, and underscores beginning with an uppercase letter. Instantiation is binding of a variable to a value, lasts only as long as it takes to satisfy one complete goal. Structure represents atomic proposition.

Fact Statements and Rule Statements are used for the hypothesis. The different is Fact Statements are headless horn clause and Rule Statements are headed horn clause. Goal Statements are statements that are in form of proposition that we want system to prove or disprove.

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.

When goal has more than one subgoal, can use either Depth-first search or Breadth-first search. Prolog uses depth-first search, can be done with fewer computer resources. 

Backtracking is reconsidering previous subgoal to find an alternative solution if fail to show truth of one of subgoals in a goal with multiple subgoals. Backtracking can take lots of time and space.

Trace is 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)

Application of Logic Programming :

• Relational database management systems.

• Expert systems.

• Natural language processing.

Thats all for today session.

Session 12 - GSLC

Session 12 - GSLC

Saturday, 6 January 2018

This session is GSLC session, so Miss Yanfi give us assignment. The Questions are :
1. What is the different between a language with exception handling and without exception handling? 2. Define exception, exception handler, raising an exception, disabling an exception, continuation, finalization, and built-in exception.
3. What are the alternatives of exception handling?
4. What are the advantages of having support for exception handling built-in to a language?
5. What is tail recursion?
 6. What are the differences between functional and imperative languages?
7. What is the basic concept of declarative semantics?
 8. Explain about the rule statements.
9. What are the differences between depth-first search and breadth-first search?
10. Explain the negation problem with Prolog. Why this is a limitation?

And my answers are:

1. In a language with exception handling

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

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.

2. - Exception : any unusual event, erroneous or not, that is detectable by either hardware or software and that may require special processing.

– Exception handler : a code unit which processes an exception.

– Raising an exception : When a event associated with an exception occurs.

– Disabling an exception : Ignoring a certain hardware-detectable exceptions.

– Continuation : Control transfer to somewhere in the program outside of the handler code or program might terminate .

– Finalization : ability to complete some computation regardless of how subprogram execution terminates.

– Built-in exception : Exception that is not made by the user, but rather comes as default.

3. Alternatives:

– Send an auxiliary parameter or use the return value to indicate the return status of a subprogram.

– Pass a label parameter to all subprograms (error return is to the passed label).

– Pass an exception handling subprogram to all subprograms.

4. - Error detection code is tedious to write and it clutters the program.

- Exception handling encourages programmers to consider many different possible errors.

- Exception propagation allows a high level of reuse of exception handling code.

5. Tail recursive is a special kind of recursion where the recursive call is the very last thing in the function

6. •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 

7. The basic concept of declarative semantics is there is a simple way to determine the meaning of each statement, and it does not depend on how the statement might be used to solve a problem.

8. Rule statements are used for the hypotheses and headed Horn clause

•Right side: antecedent (if part)

–May be single term or conjunction

•Left side: consequent (then part)

–Must be single term

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

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

10. 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.

Session 11

Session 11

Saturday, 16 December 2017

This is the last session in 2017 year. This session talks about exception handling and event 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.

An exception is any unusual event, either erroneous or not, detectable by either hardware or software, that may require special processing. The special processing that may be required after detection of an exception is called exception handling. The exception handling code unit is called an exception handler.

Exception Handling Alternatives:
–Send an auxiliary parameter or use the return value to indicate the return status of a subprogram.
–Pass a label parameter to all subprograms (error return is to the passed label).
–Pass an exception handling subprogram to all subprograms.

Advantages of built-in Exception Handling :

•Error detection code is tedious to write and it clutters the program.
•Exception handling encourages programmers to consider many different possible errors.
•Exception propagation allows a high level of reuse of exception handling code.

Catch is the name of all handlers--it is an overloaded name, so the formal parameter of each must be unique.

Exceptions are all raised explicitly by the statement:
throw [expression];

An unhandled exception is propagated to the caller of the function in which it is raised. If no handler is found, default handler is called. After a handler completes its execution, control flows to the first statement after the last handler in the sequence of handlers of which it is an element.

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.

That's all for this session. 

Session 10

Session 10

Saturday, 6 January 2018

Miss Yanni has business on 9 december and decided to change the class date to 6 january 2018 from 9 december 2017. Today session talks about concurrency. 

Concurrency can occur at four levels:

• Machine instruction level.
• High-level language statement level.
• Unit level.
• Program level.

A task/process/thread is a program unit that can be in concurrent execution with other program units. Tasks usually work together. There're 2 general categories of tasks, such as Heavyweight tasks and lightweight tasks. Heavyweight tasks execute in their own address space and 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. 

A mechanism that controls the order in which tasks execute is called task synchronization. There's 2 kind of synchronization : cooperation synchronization and competition synchronization. Cooperation synchronization means task A must wait for task B to complete specific activity before task A can continue its execution. Competition synchronization means two or more tasks must use some resource that cannot be simultaneously used. For task synchronization, task communication is necessary and provided by shared nonlocal variables, parameters, and message passing.

Providing those 2 synchronization requires a mechanism for delaying task execution. Those task execution control is maintained by a program that is called the scheduler. 

Task execution states :

• New - created but not yet started
• Ready - ready to run but not currently running (no available processor)
• Running 
• Blocked - has been running, but cannot now continue (usually waiting for some event to occur)
• Dead - no longer active in any sense

A characteristic that a program unit may or may not eventually complete its execution is called liveness. If all tasks in a concurrent environment lose their liveness, it is called deadlock.

Methods of providing synchronization are semaphores, monitors, and message passing. 

Semaphore is a data structure consisting of a counter and a queue for storing task descriptors(data structure that stores all of the relevant information about the execution state of the task).

Monitor is an abstract data type for shared data. Message passing is a general model for concurrency.

That's all for this session.