CIS 400 Lecture 10

Continuing with iteration issues from previous lecture

Loop issues

· What type of values may loop variable assume?

· Complexity of loop expression?

· How often is loop variable checked against final value?

· Can loop variable be assignment inside loop body?

· When evaluate stopping expression?

· Transfer permitted outside loop?

· Scope of loop variable?

6) Multiple loop exits

7) "Loop and a half", (variation of #6 with a test in middle of loop)

8) Iterator, (like Lisp)

goto's

Advantages:

· Found in virtually every language

· Conditional or non-conditional

· Easy to use

· Simulate ANY missing control structure

Computed goto:

go to (10,20,30) INDEX //goes to 10, 20 or 30 depending on value of INDEX

Assigned goto:

//assign value, say 10, to LABEL

go to LABEL, (10, 20, 30) //goes to label depending on what was assigned to LABEL

Approaches to LABEL

· Ada- labels as local syntactic tags, evaluated at compilation

· Algol- restricted data items, (all possible values defined at translation)

· Snobol/APL- unrestricted data types

Disadvantages of goto's:

· Readability

· Source order has little bearing on execution

· Groups of statements may serve multiple purposes

Functional programming

Up until now, we have been covering…

· VonNewmann architecture, (single instruction at a time)

· Assignment statement oriented

(imperative languages)

Functional languages:

More expressive, the expression is more important than assignment or control statement

i.e. in C:

max = x > y? x : y;

OR

if x > y then

max = x;

else max = y;

But what is "x" in the following expression?

f(x) + (x) = 2 * f(x)

Functional programming º applicative languages

f(x) = x * x

f(2) = 2 * 2

f(z + 1) = (z + 1) * (z + 1)

"lambda" notation:

(lx x*x)2 = 2 * 2 = 4

f = lx.x*x

global º non-lambda variable

f º g o h = g(h(x)) functional languages permit this imperative do not

Functional/ applicative languages

· Set of "primitives"

· Set of functional forms, (for new functions)

· Application operation, (apply function to arguments)

· Set of data objects

How math functions differ form computational functions

· Modifiable variable in computing

· Program functions have side effects

· Programming functions define procedurally in steps-math functions typically done in terms of other functions

· Both can be recursive

Strongly advised to go to Xlisp home page and download a free implementation of Xlisp

Lisp: John McCarthy-MIT 1960

Distinctive features of Lisp:

· Equivalence of form for data and program

· Heavy reliance on recursion over iteration

· Use of linked list as intrinsic data structure

Data objects in Lisp

· "Atoms", (either literal or numeric, i.e. 'sam or 3)

· List- groups of atoms or lists nested list representation is ((1 2 ) (3 4 ))

· Expression- atoms and lists together

There are no reserved words for literal except:

· The literal T is for boolean true

· The literal NIL º '( ) or false

In Lisp

; is for commenting like // for C++. So ; this comment is not recognized by interpreter

' is to read "as is" and not for interpretation

Simulated Lisp input/output:

> 3

3

> sam

undefined variable

> 'sam

sam

> T

T

> NIL

NIL

> (a (b c) d)

undefined function call ;;;;;; interpreter thinks "a" is a function, not a list element

> '(a (b c) d)

(a (b c) d)

In Lisp (a (b c) d)

"car" from contents of address register-the first element of a list

"cdr" from contents of decrement register-everything EXCEPT the first element

to exit Lisp:

> (exit)

exit

an atom "A" has:

· A name

· A value

· A property list

In functional languages parameter transmission is by value, (there may be some by name parameter transmission)

Read/ Evaluate loop- and expression is read and evaluated, a value is returned, then the system waits (infinitely) for the next expression

An example of some kind of "by name" parameter transmission:

> (setq x 3)

3

> x

3

> (setq x '(a b c)) ; the apostrophe is needed!!!

(a b c)

> x

(a b c)

> 'x

x