Explore topic-wise InterviewSolutions in .

Continuation Passing STYLE is a programming method that ASSUMES that every user defined procedure f$ carries a continuation, which is a future computation specification CONT, in the form of a procedure, that needs to apply once the computation of f$ ends.

Since a CPS procedure carries a future computation, they are written as iterative PROCEDURES:

The “bottom” action is directly applied, and all depending actions are postponed to the continuation. A CPS procedure has one of the following formats:

1. (continuation (primitive-procedure ....))
2. (CSP-user-procedure .... continuation)
3. A conditional with the above ALTERNATIVES

Continuation Passing Style is a programming method that assumes that every user defined procedure f$ carries a continuation, which is a future computation specification cont, in the form of a procedure, that needs to apply once the computation of f$ ends.

Since a CPS procedure carries a future computation, they are written as iterative procedures:

The “bottom” action is directly applied, and all depending actions are postponed to the continuation. A CPS procedure has one of the following formats:

Syntax notions: expressions, variables, symbols, forms

Semantic notions: types, values

The purpose of type management in programming languages is to prevent unfeasible computations, i.e., computations that cannot be completed due to improper applications of procedures to values. For example, prevent:

> (+ ((lambda (x) x) (lambda (x) x)) 4)

+: expects type <number> as 1st argument, given: #<procedure:x>; other

arguments were: 4

Language expressions (syntax) are assigned a type (semantics), so that well typing rules can be checked. For example, the above expression is not well typed, since that type of the + PRIMITIVE procedure is [number*Number –> Number], while the types of the given arguments

were [T –> T] and Number.

But, can we guarantee that expressions are well typed? CONSIDER:

> (define x 4)
> (+ 3
(if (> x 0)
(+ x 1)
"non-positive value"))
5
and
> (define x 0)
> (+ 3
(if (> x 0)
(+ x 1)
"non-positive value"))

+: expects type <number> as 2nd argument, given: "non-positive value";

other arguments were: 3

What happened? The expression (if (> x 0) (+ x 1) “non-positive value”) is not well typed. Depending on the runtime value of the variable x, it evaluates either to a number or to a string. Such expressions might CAUSE runetime errors when combined with other OPERATIONS.

Programming languages that enforce type checking at static time (before runtime), usually prohibit conditional expressions that might evaluate to different types. In Scheme (Dr. Racket), since types are checked at runetime, such conditionals are allowed, but should be handled with much care.

Syntax notions: expressions, variables, symbols, forms

Semantic notions: types, values

The purpose of type management in programming languages is to prevent unfeasible computations, i.e., computations that cannot be completed due to improper applications of procedures to values. For example, prevent:

> (+ ((lambda (x) x) (lambda (x) x)) 4)

+: expects type <number> as 1st argument, given: #<procedure:x>; other

arguments were: 4

Language expressions (syntax) are assigned a type (semantics), so that well typing rules can be checked. For example, the above expression is not well typed, since that type of the + primitive procedure is [number*Number –> Number], while the types of the given arguments

were [T –> T] and Number.

But, can we guarantee that expressions are well typed? Consider:

> (define x 4)
> (+ 3
(if (> x 0)
(+ x 1)
"non-positive value"))
5
and
> (define x 0)
> (+ 3
(if (> x 0)
(+ x 1)
"non-positive value"))

+: expects type <number> as 2nd argument, given: "non-positive value";

other arguments were: 3

What happened? The expression (if (> x 0) (+ x 1) “non-positive value”) is not well typed. Depending on the runtime value of the variable x, it evaluates either to a number or to a string. Such expressions might cause runetime errors when combined with other operations.

Programming languages that enforce type checking at static time (before runtime), usually prohibit conditional expressions that might evaluate to different types. In Scheme (Dr. Racket), since types are checked at runetime, such conditionals are allowed, but should be handled with much care.

1. FIRST, the sum procedure prevents DUPLICATIONS of the computation pattern of SUMMING a sequence elements between given boundaries. Duplication in software is bad for many reasons, that can be SUMMARIZED by management difficulties, and lack of abstraction – which leads to the second point.
2. Second, and more important, the sum procedure expresses the mathematical notion of sequence summation. Having this notion, further abstractions can be formulated, on top of it. This is SIMILAR to the role of interface in object-oriented languages.

The problem is in the conditional that has clauses that return values from different types: Number and BOOLEAN. In ORDER to accommodate such conditionals we allow union types in CONTRACT specifications. The resulting contracts:

Signature: bounded-sqrt(x,bound)

Purpose: To compute the square root of x, using Newton’s approximations method, if number of iterations does not exceed ’bound’

Type: [Number*Number -> Number union Boolean]

Example:

(sqrt 16. 7) should produce 4.000000636692939
(sqrt 16. 4) should produce #f

Pre-conditions: x >= 0, bound >= 0
Signature: bounded-sqrt-iter(guess,x,bound)

Purpose: To compute the square root of x, starting with ’guess’ as INITIAL guess, if number of iterations does not exceed ’bound’

Type: [Number*Number*Number -> Number union Boolean]

Example:

(sqrt 1 16. 7) should produce 4.000000636692939
(sqrt 1 16. 4) should produce #f
Pre-conditions: x >= 0, bound >= 0, guess != 0

The problem is in the conditional that has clauses that return values from different types: Number and Boolean. In order to accommodate such conditionals we allow union types in contract specifications. The resulting contracts:

Signature: bounded-sqrt(x,bound)

Purpose: To compute the square root of x, using Newton’s approximations method, if number of iterations does not exceed ’bound’

Type: [Number*Number -> Number union Boolean]

Example:

(sqrt 16. 7) should produce 4.000000636692939
(sqrt 16. 4) should produce #f

Pre-conditions: x >= 0, bound >= 0
Signature: bounded-sqrt-iter(guess,x,bound)

Purpose: To compute the square root of x, starting with ’guess’ as initial guess, if number of iterations does not exceed ’bound’

Type: [Number*Number*Number -> Number union Boolean]

Example:

(sqrt 1 16. 7) should produce 4.000000636692939
(sqrt 1 16. 4) should produce #f
Pre-conditions: x >= 0, bound >= 0, guess != 0

The type of a conditional expression depends on the type of the VALUES of the CLAUSES of the conditional. But what if different conditionals evaluate to values that belong to different types. For EXAMPLE, the value of (if x 3 #f) depends on the value of x: MIGHT be 3 and might be #f.

The type of a conditional expression depends on the type of the values of the clauses of the conditional. But what if different conditionals evaluate to values that belong to different types. For example, the value of (if x 3 #f) depends on the value of x: might be 3 and might be #f.

The NOTION of data is USUALLY understood as something consumed by procedures. But in FUNCTIONAL languages, procedures are first CLASS citizens, i.e., handled LIKE values of other types. Therefore in such languages the distinction between data and procedures is especially obscure.

The notion of data is usually understood as something consumed by procedures. But in functional languages, procedures are first class citizens, i.e., handled like values of other types. Therefore in such languages the distinction between data and procedures is especially obscure.

Whereas a FIXED-point of a first-order function (a function on "simple" values such as integers) is a first-order value, a fixed point of a higher-order function F is ANOTHER function f-fix such that

F(F-fix) = F-fix.

A fixed point operator is a function FIX which produces such a fixed point f-fix for any function F:

FIX(F) = F-fix.

Therefore: F( FIX(F) ) = FIX(F).

Fixed point combinators allow the definition of anonymous recursive functions. Somewhat surprisingly, they can be defined with non-recursive lambda ABSTRACTIONS.

Whereas a fixed-point of a first-order function (a function on "simple" values such as integers) is a first-order value, a fixed point of a higher-order function F is another function f-fix such that

F(F-fix) = F-fix.

A fixed point operator is a function FIX which produces such a fixed point f-fix for any function F:

FIX(F) = F-fix.

Therefore: F( FIX(F) ) = FIX(F).

Fixed point combinators allow the definition of anonymous recursive functions. Somewhat surprisingly, they can be defined with non-recursive lambda abstractions.

<P>Most programming languages are TYPED, i.e., the sets of their computed values are SPLIT into subsets, termed types, that collect TOGETHER values of a similar KIND. In the part of Scheme that we study:

Computed_values = {Numbers, Booleans, Symbols, P rocedures, T uples}

where
Numbers = {1, 2, 5.1,−3, ....}
Booleans = {#t, #f}
Symbols = {a, ab1, moshe, ...}

P rocedures = set of all primitive procedures and closures over values, which is internally split into 1-ary closures from numbers to numbers, 2-ary closures from number pairs to closures, etc.

T uples = set of all tuples of values, which is internally split into pairs of numbers, pairs of closures, triplets, quadruples of values, etc.

Most programming languages are typed, i.e., the sets of their computed values are split into subsets, termed types, that collect together values of a similar kind. In the part of Scheme that we study:

Computed_values = {Numbers, Booleans, Symbols, P rocedures, T uples}

where
Numbers = {1, 2, 5.1,−3, ....}
Booleans = {#t, #f}
Symbols = {a, ab1, moshe, ...}

P rocedures = set of all primitive procedures and closures over values, which is internally split into 1-ary closures from numbers to numbers, 2-ary closures from number pairs to closures, etc.

T uples = set of all tuples of values, which is internally split into pairs of numbers, pairs of closures, triplets, quadruples of values, etc.

In COMPUTER science, Backus-Naur Form (BNF) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. JOHN Backus and Peter Naur developed a context free GRAMMAR to define the syntax of a programming language by using two sets of RULES: i.e., lexical rules and syntactic rules.

BNF is widely used as a notation for the grammars of computer programming languages, instruction sets and COMMUNICATION protocols, as well as a notation for representing parts of natural language grammars.

In computer science, Backus-Naur Form (BNF) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. John Backus and Peter Naur developed a context free grammar to define the syntax of a programming language by using two sets of rules: i.e., lexical rules and syntactic rules.

BNF is widely used as a notation for the grammars of computer programming languages, instruction sets and communication protocols, as well as a notation for representing parts of natural language grammars.

The Von-Neumann architecture, which is the BASIS for Turing machines, is based on the idea of STORED and changing states. The operational SEMANTICS of a PROGRAM is given by a SEQUENCE of systemstates (configurations).

The Von-Neumann architecture, which is the basis for Turing machines, is based on the idea of stored and changing states. The operational semantics of a program is given by a sequence of systemstates (configurations).

A parse tree or PARSING tree or derivation tree or CONCRETE syntax tree is an ORDERED, rooted tree that REPRESENTS the SYNTACTIC structure of a string according to some context-free grammar.

A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar.

Trade’s off of translation are:

• • COMPILATION
  – lower level machine may be faster, so PROGRAMS run faster
  – compilation can be expensive
  – examples: C
• • Interpretation
  – more ABILITY to perform DIAGNOSTICS (or changes) at run-time
  – examples: Basic, UNIX shells, Lisp

Trade’s off of translation are:

TYPES of translation are:

• Compilation
  – Translate instructions into suitable (LOWER level) MACHINE code
  – During EXECUTION, machine maintains program STATE information
• Interpretation
  – May involve some translation
  – Interpreter maintains program state

Types of translation are:

ISSUES are-

• Can it be understood by people and PROCESSED by MACHINES?
  Although translation may be required.
• Sufficient expressive power?
  Can we say what needs to be SAID, at an appropriate level of abstraction?

Issues are-

VARIOUS types of languages are-

• Document languages, e.g. LaTeX, POSTSCRIPT
• COMMAND languages, e.g. bash, MATLAB
• Markup languages, e.g. HTML and XML
• Specification languages, e.g. UML

Various types of languages are-

MODELS are:

• RAM machine
  Procedural
• DIRECTED acyclic graphs
  Smalltalk model of O-O
• PARTIAL recursive functions
  Lisp and ML
• MARKOV algorithms
  Prolog is LOOSELY based on these

Models are:

The choice of paradigm and therefore language DEPENDS on how HUMAN’s best think about the problem.

Other considerations are:

• EFFICIENCY
• COMPATIBILITY with existing code
• AVAILABILITY of translators

The choice of paradigm and therefore language depends on how human’s best think about the problem.

Other considerations are:

Several PARADIGMS are-

• Procedural
  examples: C, Pascal, Basic, Fortran
• Functional
  examples: Lisp, ML
• Object-oriented
  examples: C++, JAVA, Smalltalk
• Rule-based (or Logic)
  example: PROLOG

Several paradigms are-

Objectives are:

• To introduce several DIFFERENT PARADIGMS of programming
• To GAIN experience with these paradigms by using example programming languages
• To understand concepts of syntax, TRANSLATION, abstraction, and IMPLEMENTATION

Objectives are:

It is a set of RULES governed to communicate instructions to a MACHINE, PARTICULARLY a computer.

It is a set of rules governed to communicate instructions to a machine, particularly a computer.