Programming Language Concepts

Front 1

Logic programming
* Facts
* Rules

Back 1

Facts = logical statements assumed to be true (axioms)
Rules = logical statements that derive new facts from existing facts that support the premise

Solve a problem or compute a result by posing a query to the system.

Goal: logical statement proven to be true

Front 2

Forward chaining

Back 2

Start with the facts and work forward towards the query (the goal)

When a fact matches the antecedent of a rule, the rule fires, and the conclusion of the rule is added to the database of facts

Front 3

Backward chaining

Back 3

Start with the query/goal/conclusion and work backwards saving any facts that support the goal

More appropriate in cases where a particular conclusion is to be proved

When a conclusion matches the conclusion of a rule in a database, the antecedents of the rule are compared with facts in the database

Front 4

Forward chaining is ___-driven and backward chaining is ___-driven

Back 4

Forward chaining = data-driven, best for automatic, "unconscious" processing (object recognition, routine decisions). May do lots of work irrelevant to the goal

Backward chaining = goal-driven, more appropriate for problem solving. Where are my keys? How do I get into a PhD program? Often used in medical diagnosis.

Front 5

Headless horn clause in Prolog syntax
(one of two basic statement forms)

Back 5

Unconditional assertion (assumed to be true).

male(bill).
father(bill, jake).
opposite(X, Y).

Front 6

Headed horn clause in Prolog syntax
(one of two basic statement forms)

Back 6

consequence :- antecedent_expression
ancestor(mary, shelley) :- mother(mary, shelley)

* Variables in the consequence are assumed to be universally quantified.
* Variables in the antecedent expression are assumed to be existentially quantified.

Front 7

Goal statement (queries) in Prolog

Back 7

Propositions that we want the system to either prove or disprove. In the form of a headless horn statement

?- female(Jean).

system will reply either yes or no

Front 8

"is" operator in Prolog

Back 8

takes arithmetic expression as right operand and variable as left operand

?- X is 1 + 2
X = 3

?- 1+2 is 4-1 % the first argument 1+2 is already instantiated
false.

Front 9

Prolog tracing model of execution has four events:

Back 9

Call - beginning of attempt to satisfy goal
Exit - when a goal has been satisfied
Fail - when a goal fails
Redo - when backtracking occurs

Front 10

In terms of context-free grammars, what is BNF?

Back 10

Backus-Naur Form - one of two main notation techniques

Front 11

Why have a methodology or notation for language semantics?

Back 11

* Programmers need to know what statements mean
* Compiler writers must know exactly what language constructs do
* Correctness proofs would be possible
* Compiler generators would be possible
* Designers could detect ambiguities and inconsistencies

Front 12

Short-Circuit Evaluation

Back 12

(13 * a) * (b / 13 - 1)

If a is zero, no need to evaluate (b / 13 - 1)

Front 13

What are the three primary methods of describing dynamic (as opposed to static) semantics?

Back 13

Operational, Denotational, Axiomatic

Note that there is no single widely acceptable notation or formalism for describing dynamic language semantics

Front 14

Operational semantics

Back 14

Describe the meaning of a program by executing statements on a machine, either simulated or actual

The change in the state of the machine (memory, registers, etc.) defines the meaning of the statement

Front 15

Denotational semantics

Back 15

Based on recursive function theory:
Define a mathematical object for each language entity
Define a function that maps instances of the language entities onto instances of the corresponding mathematical objects

Front 16

Operational vs. Denotational

Back 16

In operational semantics, the state changes are defined by coded algorithms
In denotational semantics, the state changes are defined by rigorous mathematical functions

Front 17

Axiomatic semantics

Back 17

Based on formal logic (predicate calculus)
Original purpose: formal program verification
Axioms or inference rules are defined for each statement type in the language to allow transformations of logical expressions into more formal logical expressions
The logical expressions are called assertions

Front 18

What are the design issues in arithmetic expressions?

Back 18

Operator precedence rules?
Operator associativity rules?
Order of operand evaluation?
Operand evaluation side effects?
Operator overloading?
Type mixing in expressions?