Programming Languages

2008-07-03T11:30:00.001-07:00

	Calculator Project In VBA, make a form, and make a calculator, with a testbox and a series of buttons for addition, subtraction, multiplication, division, and equal. >> View/Complete Assignment: Calculator Project
	Prolog Homework 3 Trace through the conc procedure, appending a list of four elements to another list of four elements. Write the following prolog procedures, on lists. 1. subst(A,B,C,D) where list D is list C with element A substituted for all occurrences of element B. 2. equal(X,Y) if X and Y are the same set. Also, read thru the following: http://www.ling.helsinki.fi/kit/2004k/ctl272/Bangor/clbook_30.html and do copy and try out the examples. >> View/Complete Assignment: Prolog Homework 3
	Prolog Homework 2 Try to write Prolog rules corresponding to each of the following. Every farmer owns a donkey. Every farmer who owns a donkey beats it. If Pedro owns a donkey, he beats it. If Pedro is a farmer, he owns a donkey. If Pedro is a donkey-owning farmer then he beats his donkey. If Pedro is a donkey-owning farmer then he probably beats his donkey. Donkeys have a hard time. The infix predicate `=/2` takes two arguments and tries to unify them. We can use this to experiment with Prolog's pattern matching; for example: \| ?- X = [a,b]. X = [a,b] ? yes \| ?- [X] = [a, b]. no \| ?- X = a, X = Y. X = a, Y = a ? yes So, Prolog will tell us whether the terms on either side of the `=` unify, and if they do, it will provide us with the bindings for any variables that appear. For each of the following: specify whether the query submitted to Prolog succeeds or fails; and if it succeeds, specify what is assigned to the variables by the unification; if it fails, explain why. `\| ?- X = fred.` `\| ?- jane = fred.` `\| ?- X = fred, X = Y.` `\| ?- X = happy(jim).` `\| ?- X = Y.` `\| ?- 2 + 1 = 3.` `\| ?- f(X,a) = f(a,X).` `\| ?- fred = fred.` `\| ?- likes(jane, X) = likes(X, jim).` `\| ?- f(X,Y)=f(P,P).` `\| ?- A = b(c).` `\| ?- a = b(c).` `\| ?- a(b,C) = a(C,b).` `\| ?- a(b,C) = a(C,d).` `\| ?- A = B.` `\| ?- A = b(C).` `\| ?- 3 = 6/2.` `\| ?- a(b,c) = a(b,c).` `\| ?- a(B,C) = a(D,D).` `\| ?- member(a,L) = member(E,[b,c,d]).` `\| ?- A = b(A).` Write the `ancestor/2` predicate to a file, and add about ten facts along the lines of `parent(anna,belinda)`, `parent(belinda,celia)` etc. Then call `ancestor(anna,X)`. Use `;` to see all solutions, viewing the execution of the goal with trace. We can use the successor notation for addition to show an example of the interaction between unification and recursion. This example may appear a bit complex first, if you are not used to mathematical theory, but in fact it just shows how simple the ideas really are. The numbers 0, 1, 2, 3, 4...are defined by a set of axioms called the Peano axioms. The definition of the numbers themselves are based on two concepts: a STARTING POINT, which we call zero and write as 0; and the concept of BEING THE NEXT NUMBER, which we will represent as s(K). In this notation, 0 is 0, 1 is s(0), 2 is s(s(0)), 3 is s(s(s(0))), and so on. Note that although s is a function, there is no notion of it being evaluated. Using this representation, we can write a procedure which formalises the definition of addition: % succ_plus/3 % the definition of addition according to the Peano axioms % succ_plus(X,Y,Z) corresponds to X + Y = Z % X,Y,Z are all given in successor notation succ_plus(0,X,X). succ_plus(s(X),Y,s(Z)) :- succ_plus(X,Y,Z). Let's say that we want to add 3 and 2. 3 is the successor of the successor of the successor of 0 (s(s(s(0)))) and 2 is the successor of the successor of 0 (s(s(0))). To follow the execution of the goal, we use trace as usual: \| ?- trace,succ_plus(s(s(s(0))),s(s(0)),X). {The debugger will first creep -- showing everything (trace)} 1 1 Call: succ_plus(s(s(s(0))),s(s(0)),_128) ? 2 2 Call: succ_plus(s(s(0)),s(s(0)),_325) ? 3 3 Call: succ_plus(s(0),s(s(0)),_445) ? 4 4 Call: succ_plus(0,s(s(0)),_561) ? 4 4 Exit: succ_plus(0,s(s(0)),s(s(0))) ? 3 3 Exit: succ_plus(s(0),s(s(0)),s(s(s(0)))) ? 2 2 Exit: succ_plus(s(s(0)),s(s(0)),s(s(s(s(0))))) ? 1 1 Exit: succ_plus(s(s(s(0))),s(s(0)),s(s(s(s(s(0)))))) ? X = s(s(s(s(s(0))))) ? yes ?- Whenever the second clause of `addition/3` is used (i.e. every time the first term is not equal to 0) `X` matches the interior of a structure. For instance, in the first call, `s(X)` and `s(s(s(0)))` are unified, giving the substitution `X = s(s(0))`. The recursive clause is used until `X` is matched to 0--then we use the base case, and the third term is unified with the second term. As we step back through the recursive clause, `s(...)` is added on to the third term once for every `s(...)` we had to strip off to reach the base case. Try the program out with a few different numbers, until you understand how it works. Write a procedure for subtraction. This will only work when the first number is equal or greater to the second--why? >> View/Complete Assignment: Prolog Homework 2
	Prolog Homework 1 Download and install SW-I Prolog. Trace through the sam likes example. Then: Create files with the facts and rules discussed in this chapter. Try out various queries. Represent the following sentences as Prolog facts. Bill is tall. Bill is a teacher. Bill sings. Bill likes ice-cream. Mary hates ice-cream. Today is Friday. Jane hit Bill. Jane hit Bill with a cricket bat. Belinda bought a sweater. Belinda bought Jim a sweater. Belinda bought Jim a sweater at Jenner's. Belinda bought Jim a sweater for fifty pounds at Jenner's. Belinda is married to John. John is Belinda's husband. John and Belinda are married. Construct a file called `family.pl` containing the following Prolog clauses. % parent(Parent,Offspring) parent(mary,thomas). parent(mary,jane). parent(william,thomas). parent(william,jane). parent(thomas,lee). parent(thomas,sandy). % female(Female). female(mary). female(jane). female(sandy). % male(Male). male(thomas). male(william). male(lee). Load the contents of the `family` file into the Prolog interpreter. Display the contents of the database by using `listing/0`. Don't forget the full stop. Display parts of the contents by using the predicate `listing/1` whose argument should be the name of a predicate. For instance typing `listing(male)` will display all facts whose predicate is `male` regardless of arity. Look at the following queries. Try to work out what the interpreter will reply first, then try them out. Check if there is more than one solution using `;` if applicable. `\| ?- parent(mary,thomas).` `\| ?- parent(thomas,lee).` `\| ?- parent(thomas,mary).` `\| ?- male(william).` `\| ?- parent(thomas,Who).` `\| ?- parent(Parent,sandy).` `\| ?- parent(X,Y).` What queries would you use to find out the following? Is Mary the parent of Thomas and Jane? Do Jane and Thomas have the same parent? Does Sandy have a sister? Who is Thomas's mother? Establish a database with parent and gender facts for your own family. Write rules for commonly used family terms, such as sister, brother, mother, father, grandparent, grandfather, cousin, aunt, half-brother, etc. Try out the program, making sure that it gives the correct answers. Use trace to make sure you understand the different answers. >> View/Complete Assignment: Prolog Homework 1
	Homework #11: Dynamic Variables Read this article at Microsoft Research about "Dynamic Variables." Do not read the Appendix to the article just yet, only the main body of the article. Answer the following questions: 1) List two purposes for which they envision using these dynamically scoped variables? 2) Choose one of those two, and motivate it. That is, show what the code would look like when not using dynamic variables, and then what it would look like with dynamic variables. 3) Briefly describe the "simple" and the "novel" implementations. >> View/Complete Assignment: Homework #11: Dynamic Variables
	Static Scoping Read this article. Give four reasons why nesting in Ada programs is for the birds. What is the authors' suggestion? Also, read this article about regular expressions in Word, and try the find and replace example in the article. http://office.microsoft.com/en-us/help/HA010873051033.aspx >> View/Complete Assignment: Static Scoping
	HW #8 Using VBA for Excel, implement the first FSA from assignment #5. On the spreadsheet, include a formal description of the FSA. This includes the transition function delta. Rather than using Gotos, keep a variable which maintains the present state, and look up the appropriate transition to the next state, based on the present state and the input, from that lookup table on the Excel worksheet.
	HW #7 Using VBA for Excel, implement the first FSA from assignment #5. Read the input string from cell B1. Print "accept" or "reject" in C1. Print the sequence of states in cell A4 and down (A5, A6, etc). Use gotos and goto labels to represent the states. Use the MID function to extract letters sequentially from the input string.
	Assignment 6: FSAs FSA.doc (38 Kb) Answer the questions in the attached Microsoft Word document about two FSMs. Due Feb 11, 2008
	Assignment 5 Download G95 (sidebar) and install it on your computer. Name the files .f90 to be able to use FORTRAN 90 syntax. If you name it .f, you will have annoying restrictions, such as the first 6 characters on a line being reserved. Read through the beginning of the tutorial, here: http://www.cisl.ucar.edu/tcg/consweb/Fortran90/F90Tutorial/tutorial.html Specifically, start with "Exercises and Examples," and do Exercise 2.1 Due Feb 11, 2008
	Assignment #3, 4 #3: Due this Wednesday, Feb 6 In Visual Basic for Applications for Excel, create a macro that puts the numbers 1 through 13 in cells A1 through A13. If possible, do so using the functionality in which you can drag to extend an existing pattern of numbers. Copy the text of the VBA macro which was created, and submit that. #4: Due next Monday, Feb 11 Write two UDFs (User Defined Functions), with meaningful names of your own choosing. The first should take in X and Y and return X times Y. The second should take in X and return X factorial.
	Assignment #1, #2 1. Give a short evaluation (a few sentences) of Stroustrup's paper on Generalized Operator Overloading for C++ 2000 in terms of readability and writability. Due approximately Monday, Feb 4. 2. Take some programming language you know and discuss its positive and negative aspects in terms readability, writability, and reliability. (Two or three paragraphs.) Due approximately Monday, Feb 6.

subst in Prolog, pt i

2008-05-26T14:43:00.000-07:00

The assignment:
"Write subst(A,B,C,D) where list D is list C with element A substituted for all occurrences of element B."

The first case we want to handle is the base case. That is, if we have the empty list, it does not matter what A and B are, because there is nothing to replace. Therefore:
subst(A, B, [ ], [ ]).

Or, because we are using neither A nor B, we can write:
subst(_, _, [ ], [ ]).

The alternative is that we are not dealing with an empty list. In such a situation, we want to define subst recursively, such that we yank out the first element -- the head -- if it is B, and replace it with A. Unless of course the head is not element B, in which case we want to just leave it alone -- that is, put the head back on the list.

The way we pull apart such a list is as [H | T], where H is the head and T is the tail.

More on this later, but hopefully this gets you on the right track. It does not have to work exactly.

2008-05-14T14:41:00.000-07:00

8, 9, 10, 13, 15, 16

ch 8 -- control structures p 324 and on
if-fi
do

od

ch 9, ch 10: parameter passing
skip 380-387
focus on coroutines, on page 391

in ch 10, statis links, dynamic links

skip ch 11, 12, 14

do chapter 13

2008-05-14T10:54:00.001-07:00

http://docs.google.com/Doc?id=ajbqhgmq9qdz_110cscw9cc7

Common Lisp Tutorial

2008-05-12T12:55:00.000-07:00

http://www.notam02.no/internt/cm-sys/cm-2.2/doc/clt.html

Not Equal In Prolog

2008-05-08T14:24:00.001-07:00

After consulting with this website, actually connected with pop11. :)

The following interaction from SWI-Prolog when consulting j.pl. Use similar code to make sure sally is not her own sibling.

% c:/j.pl compiled 0.00 sec, -292 bytes
11 ?- listing.

myneq(A, B) :-
A\=B.

Yes
12 ?- myneq(a, a).

No
13 ?- myneq(a, b).

Yes

Download PopLog, a Free Lisp Interpreter

2008-04-28T10:18:00.000-07:00

Here

After installing, modify the shortcut to have a +clisp after the +startup. Try out the examples from the Wikipedia page on Lisp,

http://en.wikipedia.org/wiki/Lisp_%28programming_language%29

aside from any Lisp homework I may assign.

Video Solutions for HW 7 and 8

2008-04-04T12:06:00.000-07:00

Available here.

Prolog

2008-04-02T09:44:00.000-07:00

SW-I Prolog is a Prolog that works.

http://www.swi-prolog.org/

we will work through the examples here:
http://www.ling.helsinki.fi/kit/2004k/ctl272/Bangor/clbook.html

All About Gotos

2008-03-19T13:04:00.000-07:00

Read this article from Knuth, "Structured programming with go to statements"

Homework: Implement a CFG

2008-03-14T11:24:00.001-07:00

You can watch the video detailing the assignment here:
http://www.girsology.com/proglang/

And as soon as Revver approves the video, I will embed the video in this post as well.
Update: Here it is:

class notes for today

2008-03-05T19:46:00.001-08:00

type
colors ( red, blue, green, yellow, orage, white, black);

colorset = set of colors;

var
set1, set2 : colorset;

set1 := [ red, blue, yellow ];
set2 := set1;
set2 := [black, blue ];

if (ch = 'c' or ch = 'r' or ch = 'y')

if (ch in ['c', 'r', 'y'])

if (c in colorset)

as bitset

['a' ... 'p']

foo()
{
int * p, *y;
p = &f;
p = y;

cout *p;

cout p;
p = y;
*p = *y;
p =: y;
p =: f;

int * p = new int [100];

p = new int [100];

*(p + 7);
p[7];
cout 7[p];
*(7 + p);

int &r = t;

r
*r

}

Tombstone
lock and key

int *y;
foo()
{
Int *p;
p = new int;
y = p;
}

eager approach
lazy approach

refernce counting
garbage collection

The Three-Register Garbage Recycler, or Nodes for Free, by David Wise

2008-03-05T13:06:00.000-08:00

"The Three-Register Garbage Recycler, or Nodes for Free," by David Wise. Use the links to the image.

Questions to follow, or perhaps I will ask someone to present.

Read this paper on Distributed Cyclic Reference Counting

2008-03-05T12:58:00.000-08:00

Read this paper on "Distributed Cyclic Reference Counting" by Frank Dehne, Rafael D. Lins.

Questions on the paper to follow. Or perhaps I will ask someone to summarize the paper.

Some class notes

2008-03-03T14:41:00.000-08:00

1 4 6 8 5 32 0 -1
1 4 6 8 5 3 2 0 -1
1 8 2 4 5 0 6 3 -1
int list[10];cout list[k];
address(list[k]) = address(list[1]) + (k-lowerbound)*el_size= address(list[1])- lowerbound*el_size + k*el_size
descriptor for arrays_________arrayelem typeindex type# of dimensionsindex upper boundindex lower boundaddress
// using ] in place of greater than because of html%salaries = ("Cedric" =] 75000, "Perry" =]56000);$salaries{"Perry"} = 70000;$s = "Josh";$salaries{$s} = 8000;if exists $salaries{"Shelly"}delete $salaries{"Perry"};%salaries = ();
01 EMPLOYEE-RECORD 02 EMPLOYEE-NAME 05 FIRST PICTURE IS X(20) 05 MID PICTURE IS X(20) 05 LAST PICTURE IS X(20) 02 HOURLY-RATE PICTURE IS 99V99
01 employer-record 02 employer-name 05 FIRST PICTURE IS X(20) 05 LAST PICTURE IS X(20) 05 SSN PICTURE IS X(20)
FIRST OF EMPLOYEE-NAME OF EMPLOYEE-RECORD
FIRST OF EMPLOYEE-RECORD
STRUCT A{ STRUCT B { INT X; INT Y; } J; CHAR Z; } H;
H.J.X
class a{ int i; char * p; string g; a() { p = new char [60]; ~a() { delete [] p; }};
a b, c;
b = c;
b.g = c.g;
move corresponding employer-record to employee-record
dynamic variables as discussed in the papermain(){ int x, y; int z; set z : int = x -4 in { foo(); bar(); } bar();}
foo(){ int a, b; use z : int in { cout z;
}}
bar(){ int q; set z : int = q -4 in { foo(); }}

Homework #11: Variables With Dynamic Scope

2008-02-27T17:24:00.001-08:00

Read this article at Microsoft Research about "Dynamic Variables." Do not read the Appendix to the article just yet, only the main body of the article.

Answer the following questions:
1) List two purposes for which they envision using these dynamically scoped variables?
2) Choose one of those two, and motivate it. That is, show what the code would look like when not using dynamic variables, and then what it would look like with dynamic variables.
3) Briefly describe the "simple" and the "novel" implementations.

Homework #10

2008-02-25T20:05:00.000-08:00

1. Read this article about regular expressions in Word, and try the find and replace example in the article.

2. Read the Wolfe article posted on blackboard, "Nesting In Ada Programs Is For The Birds," and answer the questions: Give four reasons why nesting in Ada programs is for the birds. What is the authors' suggestion?

class notes from today

2008-02-25T14:46:00.000-08:00

some prolog:

father (terach, avraham).
father (avraham, yitzchak).
father (avraham, yishmael).

brother (A, B) :- father(C, A), father (C, B).

?- brother (yitzchak, yishmael)
True

?- brother (yitzchak, Z)
yishmael

floating point:
_______________
sign bit
exponent
fraction

decimal
_____________
part before decimal pt.
part after decimal pt.
1060 = 10.60

integers
______________
sign magnitude notation
two's complement
one's complement

descriptors for:

static length string

--------------
string
length
address
_________________

limited dynamic length string

_-________________________
limited dynamic string
maximum length
current length
address
___________________________

enum temperature { hot, cold, freezing };

enum proximity { near = 6, cold = 7, freezing =8};
proximity::cold

Some Class Notes

2008-02-14T05:09:00.001-08:00

int x[6];

int n;
cin >> n;
int x[n];

int * x = new int [n];
Backus-Naur Form
BNF
CFG - Context Free Grammar

Josh
josh

int int;

REAL APPLE;
INTEGER REAL;
REAL INTEGER;

int shakespeare;
shakespencil = 60;

FSA which recognize regular languages
NFA is equivalent to an FSA

regular langs are closed on the Operations of union, concatenation,
and kleene star

E is the input alphabet
G is the output alphabet

PDA = Push Down Automaton
can recognize CFLanguages,
which can be described with CFG, BNF

Getting Fortran to Run

2008-02-13T17:49:00.000-08:00

I am still working on getting FORTRAN installed in the labs, for G95. In the meantime, on your own personal machines, you can try installing the Silverfrost FTN95 compiler. It is free for personal use, but has an annoying screen before running any of your programs. And it integrates with the Visual Studio 2005 IDE, with makes it much easier to test out your programs. And it color codes keywords, and lets you step through the code, and so on. I tried it, and it worked with no headaches setting it up.

HW #8, with video intro

2008-02-12T07:04:00.000-08:00

Not to be confused with homework #7.

#8:
Using VBA for Excel, implement the first FSA from assignment #5. On the spreadsheet, include a formal description of the FSA. This includes the transition function delta. Rather than using Gotos, keep a variable which maintains the present state, and look up the appropriate transition to the next state, based on the present state and the input, from that lookup table on the Excel worksheet.

You can download the video here.

Class Notes

2008-02-11T14:41:00.000-08:00

LISP
(A B C D)
(A (B C) D)

Three operations closed on regular languages
Union
Concatenation
Kleene star
Kleene plus

A = { boy, girl}
B = {bad, good}

A.B {boybad, girlbad, boygood, girlgood}

C = {boy}
A* = { epsilon, boy, boyboy, boyboyboy, girl, girlboy, boygirl, girlgirlgirl, girlgirlboy

C* = { w^n | n >= 0, w is an element in C}

ab*a(a|b)

((a|b|c).a)+
((a|b|c).a). ((a|b|c).a)*

1 + 2

HW #9: More Fortran

2008-02-10T21:17:00.000-08:00

Due Feb 13.

In the tutorial, work through hands-on-exercise 2.2 and 2.3. For the former, you might find this video of some help.

You can download the video here:

The purpose of exercise 2.2 is to give you some experience reading a real Fortran program and understanding it to the level of being able to make some simple modifications. In exercise 2.3, we are introduced to internal functions, which are limitations of the scope of functions to within the program. This will help you apply what you read, to modify program 2.2 further. And more than that, it will give you practice in writing functions, and understanding in how they take in their parameters and how they give back their return value. Part of the assignment is also to give me the meaning of "intent" in this context. Google is your friend in this regard.

Homework #7, 8

2008-02-10T17:09:00.000-08:00

We continue with the Excel VBA assignments, and will be implementing various finite state automata (FSA). To be announced, discussed in class on Monday.

#7: Due Wednesday, Feb 13
Using VBA for Excel, implement the first FSA from assignment #5. Read the input string from cell B1. Print "accept" or "reject" in C1. Print the sequence of states in cell A4 and down (A5, A6, etc). Use gotos and goto labels to represent the states. Use the MID function to extract letters sequentially from the input string.

You can download the video here.

#8: Due Monday, Feb 18
Using VBA for Excel, implement the first FSA from assignment #5. On the spreadsheet, include a formal description of the FSA. This includes the transition function delta. Rather than using Gotos, keep a variable which maintains the present state, and look up the appropriate transition to the next state, based on the present state and the input, from that lookup table on the Excel worksheet.

Video to come.

Homework #6 Solution

2008-02-07T16:28:00.000-08:00

Here is a walkthrough of installing the G95 FORTRAN compiler and getting the Hello World program up and running.

You can download the video here.

Homework #5

2008-02-06T19:19:00.001-08:00

In the Sipser book, and up on Blackboard. Look at the FSAs and answer the questions.

Homework #3 Solution

2008-02-06T19:14:00.000-08:00

See the assignment definition here.

You can download the video here.

Some formal definitions from class about FSA

2008-02-06T14:44:00.000-08:00

A finite automoton is a 5-tuple (Q, E, delta, q0, F)
(We are using E for Sigma)

1. Q is a set of states
2. E is set called the alphabet
3. delta: Q X E -> Q is the transition function
4. q0 an element in Q is the start state
5. F subset of Q is the set of accept states

If A is the set of all strings accepted by FSM M, then Machine M recognizes A; could say accepts A. A is the language of machine M.

Also, we finished chapter 2's coverage of the FORTRANs, in the Concepts of Programming Languages book.

FORTRAN Assignment 1 (HW Assignment 6)

2008-02-06T13:51:00.000-08:00

Download G95 (sidebar) and install it on your computer. Name the files *.f90 to be able to use FORTRAN 90 syntax. If you name it *.f, you will have annoying restrictions, such as the first 6 characters on a line being reserved. Read through the beginning of the tutorial, here. Specifically, start with Exercises and Examples, and do Exercise 2.1

Homeworks #3, 4

2008-02-04T15:00:00.000-08:00

#3: Due this Wednesday, Feb 6
In Visual Basic for Applications for Excel, create a macro that puts the numbers 1 through 13 in cells A1 through A13. If possible, do so using the functionality in which you can drag to extend an existing pattern of numbers. Copy the text of the VBA macro which was created, and submit that.

#4: Due next Monday, Feb 11
Write two UDFs (User Defined Functions), with meaningful names of your own choosing. The first should take in X and Y and return X times Y. The second should take in X and return X factorial.

Class 2

2008-02-03T21:48:00.000-08:00

First:
From class 1: go over readability, writeability.

Then:
Class 2 from last time. Go over some of the features of language. Get to the beginning of FORTRAN. Much better reading than presenting, so it is a good reason to just get the book.

And introduction to a bit of VBA for Excel.

Then, beginning of other book. What is a Finite State Automaton? An state, a start state, an accept state, a transition, a state transition table. What is the language recognized by a specific FSA?

How to drop files into the Digital Dropbox

2008-01-31T18:29:00.001-08:00

and send them to the instructor.

I'll go over this in class.

Homework #1, #2

2008-01-30T19:03:00.000-08:00

1. Give a short evaluation (a few sentences) of Stroustrup's paper on Generalized Operator Overloading for C++ 2000 in terms of readability and writability.

Due approximately Monday, Feb 4.

2. Take some programming language you know and discuss its positive and negative aspects in terms readability, writability, and reliability. (Two or three paragraphs.)

Due approximately Monday, Feb 6.

Welcome to the Programming Languages course

2008-01-30T14:43:00.000-08:00

Here is a link to Robert Sebesta's website. He is the author of the main book for the class, and on that website he has a bunch of slides, which we may make use of.

Here is a link to the book on Amazon. It is called Concepts of Programming Languages (5th Edition). Please note that we are using the 5th edition. It costs $109 new, or actually $2 new and 39 cents used if you follow the link to "used and new," something I would advise.

We will hopefully get Blackboard up and running for this course soon.

Regular expressions

2008-01-29T10:50:00.000-08:00

For later.

Here are some interesting articles on wildcards and regular expression matching. We might cover some of this. Don't worry if you can't understand this just yet.

Add Power to Word Searches with regular expressions

this is somewhat powerful, but it is fairly easy to encounter limitations to its power.

Putting Regular Expressions to Work in Word

A follow up article. We might try going through these examples.

Regular Expressions in Excel
Regular Expressions in Visual Studio

Review - A Work In Progress

2006-05-25T04:43:00.000-07:00

Conceptual Summary - In Reverse Order
Here are some concepts to focus on in reviewing.

Exception Handling:
Dynamic vs static binding of exception handling. How is dynamic more flexible? How is static better?
Scoping and propagation.
How does Java improve over C++'s exception handling? How does the finally clause improve? How about the OO nature of Java? The handling of built in exceptions not explicitly raised by the user?
How can a lang without specific features for exception handling handle errors? what are drawbacks of this approach?

Concurrency:

What is cooperative, competitive synchronization?
Why do we need them?
How does a binary semaphore help with competitve synchronization?
How does a regular semaphore help with competitve synchronization?
what are the inner workings of wait and release for semaphores?
What is a monitor?
What is message passing? Rendezvous?
How can we use message passing to implement a binary semaphore? A monitor?
What mechanism is used for concurrency in Ada 83? Ada 95? Java?

Interactive Fiction:
Why is an object oriented language well suited for programming interactive fiction? Why is a natural language based programming language?

Implementing Subprograms:
FORTRAN 77 with no recursion vs ALGOL and on.

FORTRAN 77:
How handle activation records, access to nonlocals (but not globals either), transfer of control. Why does this present a problem in terms of recursion?

ALGOL:
with stacked activation records. how does this allow for recursion?
What does an activation record look like.
What is the difference between the dynamic and static link. Why is a static link chain O(n)? What is the idea behind a display, and how can this minimize lookup?
Where scoping is static, how does a pair (depth, offset) work to identify a nonlocal? Why can this not work for dynamic scoping, and what would we need to store instead?

LISP:

How would you write a LISP program to return N + 3?
To get the length of a list?
What is car? cdr? caadar? If I gave you a list, could you tell me caadar of that list?

Guarded Commands:
The od and fi constructs - how they work. How are guarded commands useful in terms of ensuring program accuracy?

How are guarded commands useful in concurrency to acheiving nondeterminism?

Subprograms:

in, out, inout parameters.
what are: pass by value, pass by result, pass by value-result,
pass by reference?
positional parameters vs. keyword parameters. default parameters.

Iterative Statements
Difference between pretest and posttest,

Control Structures:
Nothing

PROLOG:
Facts, goals, and rules.
the Terach example. How would you write a rule for ancestor?

Data types:
arrays: static, fixed-stack dynamic, stack-dynamic, heap-dynamic.

Functional Programming Languages:
What is a higher order function? What is mapcar?
In Haskell, what is an infinite list? Lazy evaluation.

Slides for Functional Programming Langs

2006-05-23T10:13:00.000-07:00

http://www.csee.umbc.edu/331/fall00/nicholas/lectures/fininfp.ppt

Exception Handling

2006-05-18T15:20:00.000-07:00

http://www.cs.ndsu.nodak.edu/~slator/html/CS372/sebesta-pdf/13.pdf

Read this White Paper

2006-05-15T12:36:00.000-07:00

by Graham Nelson on Inform and programming in English
http://www.inform-fiction.org/I7Downloads/Documents/WhitePaper.pdf

Read this on Java synchronization

2006-05-15T12:33:00.000-07:00

http://www.ccs.neu.edu/home/kenb/g712/res/tutorial.html

GNAT for Mac

2006-05-09T10:00:00.000-07:00

Check it out here:

http://www.macada.org/

Instructions on Setting Up Ada for DOS

2006-05-09T09:58:00.000-07:00

OK, I got a simple compilation working.
Go to this ftp site (open in Firefox or IE)
ftp://ftp.cs.kuleuven.ac.be/pub/Ada-Belgium/mirrors/gnu-ada/3.15p/winnt/

and download the gnat-3.15p-nt.exe file. running this file will install the ada compiler.
we do not really need an IDE (integrated development environment). we can start with just command line.
it should install to c:\gnat
inside c:\gnat\bin, there are a bunch of executables, but all are runnable from the one program gnat
so type gnat and you will see the options.
copy to that directory ..\examples\hello.ada, so that you need not worry about other directories.
hello.ada is the source program.

Then:
gnat compile hello.adb
(this will create a file hello.ali)
gnat bind -x hello.ali
(then we need to link)
gnat link hello.ali
(and finally will run the program)
hello

the output will be:
Hello World. Welcome to GNAT

similar steps are available for gnat on other platforms

Further Ada Assignment

2006-05-04T12:37:00.000-07:00

Work through the examples on this web site to familiarize yourself with concurrency in Ada.

http://linux.disco.unimib.it/~ferretti/lp/ada_task.html

Also read pgs 292 - 300 in the book, which covers much related info.

Assignment

2006-05-04T10:24:00.000-07:00

Download an Ada compiler, install it, and write a hello world program.
We are going to write a concurrent program in Ada.

Lecture Notes for Concurrency

2006-05-04T10:21:00.000-07:00

Available as a pdf here.

Definition of Race hazard (condition)

2006-05-04T10:00:00.000-07:00

at wikipedia:

A race hazard (or race condition) is a flaw in a system or process where the output exhibits unexpected critical dependence on the relative timing of events. The term originates with the idea of two signals racing each other to influence the output first.

Race hazards occur in poorly-designed electronics systems, especially logic circuits, but they may also arise in computer software.

...

Computing

Race hazards may arise in software, especially when communicating between separate processes or threads of execution.

Here is a simple example:

Let us assume that two threads T1 and T2 each want to increment the value of a global integer by one.

If the two threads run simultaneously without locking or synchronization, the outcome of the operation could be wrong

Integer i = 0;
T1 reads the value of i into a register : 0
T2 reads the value of i into a register : 0
T1 increments the value of i : 0 + 1 = 1
T2 increments the value of i : 0 + 1 = 1

The final value of i is 1 instead of the expected result of 2.

For another example, consider the following two tasks, in pseudocode:

global integer A = 0;

task Received() 
{
   A = A + 1;
   print "RX";
}

task Timeout() // Print only the even numbers
{
   if (A is divisible by 2)
   {
       print A;
   }
}

task Received is activated whenever an interrupt is received from the serial controller, and increments the value of A.

task Timeout occurs every second. If A is divisible by 2, it prints A. Output would look something like:

0
0
0
RX
RX
2
RX
RX
4
4

Now consider this chain of events, which might occur next:

timeout occurs, activating task Timeout
task Timeout evaluates A and finds it is divisible by 2, so elects to execute the "print A" next.
data is received on the serial port, causing an interrupt and a switch to task Received
task Received runs to completion, incrementing A and printing "RX"
control returns to task Timeout
task timeout executes print A, using the current value of A, which is 5.

Mutexes are used to address this problem in concurrent programming.

In filesystems, File locking provides a commonly-used solution. A more cumbersome remedy involves reorganizing the system in such a way that one unique process (running a daemon or the like) has exclusive access to the file, and all other processes that need to access the data in that file do so only via interprocess communication with that one process (which of course requires synchronization at the process level).

In networking, consider a distributed chat network like IRC, where a user acquires channel-operator privileges in any channel he starts. If two users on different servers, on different ends of the same network, try to start the same-named channel at the same time, each user's respective server will grant channel-operator privileges to each user, since neither server will yet have received the other server's signal that it has allocated that channel. (Note that this problem has been largely solved by various IRC server implementations.)

In this case of a race hazard, the concept of the "shared resource" covers the state of the network (what channels exist, as well as what users started them and therefore have what privileges), which each server can freely change as long as it signals the other servers on the network about the changes so that they can update their conception of the state of the network. However, the latency across the network makes possible the kind of race condition described. In this case, heading off race conditions by imposing a form of control over access to the shared resource—say, appointing one server to control who holds what privileges—would mean turning the distributed network into a centralized one (at least for that one part of the network operation). Where users find such a solution unacceptable, a pragmatic solution can have the system 1) recognize when a race hazard has occurred; and 2) repair the ill effects.

A race condition exemplifies an anti-pattern.

A particularly poignant example of a race condition was one of the problems that plagued the Therac-25 (a Life-critical system) accidents. Another example is the Energy Management System used by Ohio-based FirstEnergy Corp., that had a race condition in the alarm subsystem; when three sagging power lines were tripped simultaneously, the condition prevented alerts being raised to the monitoring technicians. This software flaw eventually led to the North American Blackout of 2003.

Concurrency

2006-05-02T14:39:00.000-07:00

Concurrency

program level
subprogram level
statement level
instruction level

first computers: general, i, o
early 60's: multiple processors - program level
Now: multi-processor: single instruction multiple data - eg. on vectors
mult instruc mult data: each general processor has own data. can be a distributed system

physical vs. logical concurrency
thread of control
coroutines - quasi-concurrent, because single thread of control

physical, logical concurrency - have, or can imagine have, different threads of control

task: a unit that can be in concurrent execution with other such units
vs. subprogram:
can be implicitly started rather than explicitly called
when task invoked, need not wait for return from that task (asynchronous)
on return, may not necessarily return control to the caller

Communication w other tasks
shared nonlocal variables
message passing
parameters
if no such communication, called disjoint
often used for simulations, so to coordinate need communication

Synchronization:
mechanism controlling order of task execution
coop vs competition.
cooperative when A must wait for B, in order for task A to continue sensibly
Competitive: both require same resource which cannot be used simultaneously
if A needs to access shared location x, which B is using, B must wait.

famous cooperation: producer/consumer problem. from OS
one unit produces, the other consumes.place in, take from a buffer.
cannot take from buffer if empty.

competitive:
int total = 3;
A: add 1 to total.
B: mult total by 2

each must fetch, modify
what can happen without syncronization?
3 values can result. 8 (correct),
if A, B fetch before other writes back, --- if A writes first, Total = 6. If B first, total = 4

mutual exclusion. each must request and then release the resource.

Also, if more tasks than processors, need a scheduler, which delays execution.
Can time slice. let process execute for X amount of time. OK if all processes have same priority. complications,
as e.g. they wait for i/o, delays for syncronization.

tasks can be in several states.
1. New - task created, not begun
2. runnable, ready - ready to run but not currently running. given processor time, or was running and was blocked
3. running - currently executing
4. blocked - was running, but interrupted by an event. i/o most common, since most slow.
5. dead - no longer actuve. execution finished or was killed.

different algorithms for choosing which ready task to make runnable when currently running one is blocked. e.g. priority queue.

characteristic: liveness - program continues ti execute, leading to its completion.
deadlike can break liveness. how so?
A and B need X and Y to continue, but A has X, B has Y. deadlock avoidance - in lang and program design.

Language support for concurrency: PL/I, Ada 95, Java.

to be continued

Common Blocks in Fortran 77

2006-04-25T12:31:00.000-07:00

http://www.nationalfacility.apac.edu.au/training/FortranAdvanced/slides/slides.017.html

Common blocks are a Fortran 77 construct, providing areas of shared storage between different subroutines. eg.

program main
   integer :: a, b
   real :: c
   common /d/ a, b, c
 ...
end program main

subroutine foo()
   integer :: a, b
   real :: c
   common /d/ a, b, c
 ...
end subroutine foo

the common storage is called d and contains the integers a, b and the real c. Setting these variables in one routine changes it in all. Common blocks are now replaced by modules in Fortran 90.

Implementing Subprograms

2006-04-25T11:38:00.000-07:00

Here:

A Lisp link

2006-04-06T13:39:00.000-07:00

Here:

Lisp Interepters

2006-04-04T09:21:00.000-07:00

Here

I'm going to try out UfaSoft's one.

LISP - reading assignment and homework

2006-04-03T14:51:00.000-07:00

Read chapter 9 in the book until page 318, or at least read pgs 317-318, and do exercise 9-2 questions 1 and 3.

Guarded Commands

2006-03-30T15:00:00.000-08:00

See here.

Subprograms

2006-03-30T14:55:00.000-08:00

Access the pdf here.

Iterative Statements

2006-03-28T09:54:00.000-08:00

FORTRAN I: do was posttest.
DO label var = init, terminal, stepsize
stepsize defaults to 1
unsigned int constants or simple positive int variables

FORTRAN 90: DO statement is pretest. fortran 77: allows loop var to be int, real, double.
loops can be expressions, with neg and pos values. eval at beginning of DO to arrive at an iteration count. It is this value, not the loop parameters, that control the loop. so one could change them.

no multiple entry, yes multiple exits.

ALGOL 60: a case in flexibility
[for_stmt] -) for var := [list_element] {, [list_element]} do [statement]
[list_element] -) [expression]
| [expression] step [expression] until [expression]
| [expression] while [Boolean_expr]

See this website: http://logos.cs.uic.edu/476/notes/overheads/ch7controlstructures.pdf

Pascal For Statement
for var = init (to | downto) final do statement

it grows or shrinks in steps of 1. loop var cannot be changed in the body.
after loop, loop var undefined. loop var is an ordinal, with scope of the loop.

init and final checked at the start, and not after, and so may be changed in the loop.
why do this? efficiency, reliability?

Ada For statement
for variable in [reverse] discrete_range loop
...
end loop

and note that loop var has loop scope, will mask variables with wider scope.

C, C++:
We know this.
for (int i = 9; i < style="font-weight: bold;">
any of the elements in the for may be missing.
scope until end of function.

Logically Controlled Loops (rather than counting loops)
posttest, pretest?
should it be special form of a counting loop?

examples of pretest, posttest in C++, Java.
do while vs. while.

how would we implement them (=operational semantics)

FORTRAN 90: has neither.
Ada: pretest, no posttest. why?
Perl: while and until.
how so? see here: http://vergil.chemistry.gatech.edu/resources/programming/perl-tutorial/control.html

  while ($food < $stomach_ache) {    $plop++;    $fizz--;    $oh_what_a_relief_it_is *= 5;  }

Like the unless statement above, it is easier to say "until something is true" (Schwartz 61). Thus, Perl provides the until statement:

  until ($x > 6) {
  print "$x is the number!\n";
  $x++;
}

Like C, Perl lets you do do, while loops, but Perl also adds do, until loops:

  # do while example
do {
  $junk++;
} while ($junk < aok =" @array_hooray[$x];">

and of course the for loop.
might as well talk about Perl conditionals here as well:

if and else statements are used as conditionals as in any other language. For example:

  if ($cow < $sheep) {    print "baaah....\n";  } else {    print "moo....\n";  }

unless statement is specific to Perl, in which you want to always just evaluate the false part instead of doing something when not true. For example:

  unless ($age <>

Pascal has a repeat...until statement, which is the reverse of C's do...while, same as Perl's do...until.

Think about it - when we have break statements, they are the reverse of a standard while conditional. repeat...until maintains that.

Post-tests not freq used. dangerous because loop always executed at least once, and programmer might forget this. put after loop body helps make this a bit clearer.

to be continued...

Control Structures

2006-03-23T11:43:00.000-08:00

Control Statement = control statement + statement(s) it controls
control execution path
without, all have are assignments and evaluating expressions.
two types: selection (among multiple execution paths) and repeated execution.
basically, if and while. but can add more = greater writability, but programmers only learn subset of lang.

how many statements do you allow in the control statement?
one or many. blocks. otherwise, restricted to single statement, or use of a goto. control structures can replace goto.

another q: can we enter into the middle of control structures (multiple entries) - langs differ. in terms of whether can exit multiply, not such a distinction since generally safe to do that - but there is a design philosophy.

Selection
generally 2 way vs. n way selectors (1 way "degenerate" form of the two way. fortran's 3 way selector).

design issue: what type of expression controls the selector? can we select more than a single statement? do we handle nested selection?

Two way: Logical If:
FORTRAN IV
IF (BOOL expression) statement
simple, inflexible. how do you get multiple statments? with goto circumventing.

IF (FLAG .NE. 1) GO TO 20
I = 1
J = 1
20 CONTINUE

but points off for lack of readability.

How about multiple entry? Yes. How?

ALGOL 60 and on (=Java, FORTRAN 90): two-way selector:
if (bool expr) then
statement
else
statement

only one or the other is executed.

and either of these can be compound, in which case it is the then clause and else clause, rather than statement.

how do we generate the degenerate 1-way if? how do we generate the two-way?

Nesting Selectors
Ambiguity.
if (a == 1)
if (b == 2)
result = 5;
else
result = 1;

Python: semantic interpretation based on indentation. other languages, no.

In Java, most other imperative langs - match most recent, so must indent the else.
by a rule, rather than in the syntax. but will the programmer know?

ALGOL 60 - by Syntax rather than by fiat (rule).
no if nested in another if. must nest in a begin/end clause.

How would we then write the code to get each interp? (Use {} as a shorthand.) Can get either effect in Java, but to match first if rather than second, must use {}.

Perl: then and else clauses must always be compound.

in C++, Java, the introduction of the else clause, or else by compounds, {}, marked the end of the statement or compound, and where this was a single statement with no immediate else, was ambiguity. And difference between marker of end of clause, if it is a compound of single statement.

In Ada, VB6, have end if;
how does this help?

Because "end if" closes the nested if, shows which one it matches. how do we write each in Ada?

Multiple Selection
generalization of 2-way, and can implement 2-way as multiple.

design issues
do we allow compound statements, type of expression (2 way selector needed only 2 vals), can we select more than one statement/compound? what if does not eval to one of specified vals?

FORTRAN I - the three-way selector: IF(X) 10, 20, 30

and here can go really anywhere - need not even immediately follow if, or each other. user responsible for gotos, and can omit with compiler not detecting.
Also in FORTRAN I
computed:
GO TO (label1, label2, labeln) expression

assigned:
GO TO var_or_const

C.A.R. Hoare, in ALGOL-W (1966)

case int_expression of
begin
statement1;
...
statementn;
end

and could be compounds.

Pascal similar, except
statement_i becomes:
constant_list_i: statement_i;

yet we cannot say goto caselabel in Pascal.

later Pascals: an else clause, = to default
no fallthru.

in C#:

      switch(n) 
{   
   case 1:
      cost += 25;
      break;            
   case 2:      
      cost += 25;
      goto case 1;     
   case 3:      
      cost += 50;
      goto case 1;   
   default:      
      Console.WriteLine("Invalid selection. Please select 1, 2, or 3.");      
      break;
 }

and they will not allow you to omit a break of a goto.

does not disallow multiple entry. and has fallthru. unless use break, which basically is a restricted goto.
but what if forget the break and get unwanted fallthru?

reliability vs. flexibility.

In Ada, allow ranges: 10..15, as well as 5 | 6 | 19, and have an others clause

this is good for basing on single value at the top. but sometimes, based on various boolean conditions. must use nested ifs. poor readability. some langs (FORTRAN 90, Ada, Perl) give way around this.

elsif vs a bunch of nestings and endifs

Iterative statements
execute statment 0, 1, more times
all prog langs.
sometimes by iterative constructs, sometimes by recursion.

at first, directly related to arrays. why? that was the problem domain.

design questions: how iteration controlled, where in the loop is the control mechanism?

body, pretest, posttest.

counter-controlled loops: inital, terminal values of loop var, + step size.
logically controlled loops more general, but not necessarily more commonly used. could be more complex to implement that counter-controlled.
often supported by machine architecture. sometimes lang features outlive machine architecture (Fortran's 3 way if)

more design qs:
type, scope of loop var. what value does it have at termination, can we change loop vars in the loop (what are effects of this?), are loop params eval once, or for every iteration (let us say the terminal condition changes)

FORTRAN I: do was posttest.
DO label var = init, terminal, stepsize
stepsize defaults to 1
unsigned int constants or simple positive int variables

FORTRAN 90: DO statement is pretest. fortran 77: allows loop var to be int, real, double

Expressions, Assignment Statements

2006-03-16T12:20:00.000-08:00

Overloaded Operators:
operator used for more than one purpose. writability vs. reliability. is this so? depends on how use it.

op overloading in C++. give me an example (<<, >>, +).

by language def, by user.

APL and SNOBOL have binary, unary versions of almost all operators, leads to confusion.

C++: & operator, as address of and bitwise and.
unrelated functions. similarly, * operator.

general problem of reusing symbols. comments, references, etc.
a /*p

unary, binary -.

"distinct symbols increase readability." is this so? + for string appending.
when used correctly, aids in readability.
add(matmul(A, B), matmul(C, D)
vs.
A * B + C * D
on the other hand, need know types of both operands to know meaning of operator.

example from Pascal, vs. C++: find sum of bunch of ints.
avg := sum / count;
avg = sum / count;

in Pascal, / specifies float result of division between two ints. VB as well, / vs
Type conversion
Narrowing vs. Widening conversion. widening generally safer.

mixed mode expressions = op has operands of different types. coercion to appropriate type where operator not defined on that type. also, there are explicit conversions via typecasting.

Diff langs disagree on whether to do coercion.

int a, b, c; float d;
a = b * d; // as an error for b * c

case in flexibility vs. efficiency:
PL/I - string can be combined with an int. string is scanned for numeric value, and if a decimal point, assumed to be a float, and coerce other operand to float. Coercion, and choice of coercion, at run time.

reduce flexibility in favor of reliability
Ada:
cannot mix int and float in arithmetic expression except for **, exponent.

most others, no such restrictions.

Java (byte, short), C++ (short, char). operators such as + first convert to int, and then convert back on assignment, even though both operands of the same type.

Explicit type conversion
Ada:
AVG := FLOAT(SUM) / FLOAT(COUNT)

C:
(int) angle
also C++'s function-like casting

errors can result from coercions. divide by zero when divide by a float.

Relational, Boolean Expressions
for the most part, similar. sometimes slight differences. FORTRAN used .EQ. and .NE. because symbols not on punch cards.
Ada uses = for comparison. /= for not equal.

relational given lower precedence than arithmetic, so that can say
a + b > c + d

Boolean expressions:
In Ada:
**, abs, not
*, /, mod, rem
unary +, -
etc.

lowest:
and, or, xor, and then, or else

these ops non-associative. A > B and A < k =" 0"> b > c.
Python handles this interestingly.

x <> z

This is interpreted by Python as::

if x <> z:
return y > z # 1 for plain comparisons
else:
return y > z # 0 for plain comparisons
else:
return x <>

Note that this requires testing the truth value of the result of
comparisons, with potential "shortcutting" of the right-side
comparison testings. In other words, the truth-value of the
result of a comparison determines the result of a chained
operation.

Which brings us to Short-circuiting.
When know answer already, can ignore rest.
(13 * a) * (b / 13 - 1)
what if a is 0? But not easily detected. By boolean, already considering truth value.
(a >= 0) and (b < style="font-weight: bold;">speed.
can use this shortcircuiting to your advantage.
if (index in range and a[index] > 9)
so as to prevent an error.

on the other hand, sometimes will not expect that it is shortcircuiting, so issue of reliability. calling a function, incrementing a variable.

how decide: FORTRAN 77: up to lang implementor, if part is a func which assigns to a nonlocal variable, that nonlocal becomes "undefined"
difficulty in detecting these side-effects of functions.

In Ada: and then, or else does short-circuiting.

In C++: &&, || do short-circuit. If wish to avoid short-circuit, force 1 and 0 results and use bitwise operators.

Assignment

A = B

what about A = B = C?
depends. in C, yes. In PL/I, Basic, Visual Basic, = also does comparison, so would assign truth value of B = C to A.

ALGOL 60: := for assignment.

Mult targets:
PL/I: Sum, Total = 0.
other langs, e.g., C, do not.

Conditional targets
?: to give an lval rather than an rval, in C++.

Compound Assignment
a = a + b
a += b

C, C++, Java.
interesting feature of C# that defines these for you.

Unary Assignment
in C, C++, Java, etc. ++a.
when apply two unary ops, one on left side, one on right, works right to left:
- (count ++) even without parens

Assignment has an expression value
in C.
while ((ch = getchar() != EOF)

Mixed mode assignment
Do the source, target need be same type? FORTRAN, C, C++: coercion.
Pascal: depends - int to real, but not real to int.
Ada, Modula2 - nope.

Java: differs from C++ - only if widening results. increases reliability.

Data Types - III

2006-03-07T11:23:00.000-08:00

Associative Arrays

Perl:
%ages = ("Josh" => 10, "John" = 32);
$ages{"Josh"} = 29;
// and assignment will create an element
delete $ages{"John"};
// or the entire hash:
@salaries = ();

Here is a Perl tutorial on hashes. Read through it. keys and values operator/collections.

    for my $key ( keys %hash ) {
my $value = $hash{$key};
print "$key => $value\n";
}

exists keyword, or else will create the element.
if (exists $ages{"Peter"} ) ...

Possible Implementation: Read this website about implementation of Perl hashes. Linked Lists - but then O(N). Could turn each string into unique index, and use array, but then very sparse. Can use a hash function. Handle collisions how? Better hash function, or else chaining. (Alternatively, red-black trees.) Read article for more info.

C++: Map, multimap. C#: Dictionary, etc.

Record:
Heterogeneous data structure.
First, COBOL. (Not in early Fortrans.) C's struct. C++'s class. Java has class, not struct. C# has both, but with different meanings (struct is treated as a primitive, unboxed).

COBOL:


01 EMPLOYEE-RECORD.
02   EMPLOYEE-NAME.
05   FIRST    PICTURE IS X(20).
05   MIDDLE   PICTURE IS X(10).
05   LAST     PICTURE IS X(20).
02   HOURLY-RATE   PICTURE IS 99V99.

Pascal, Ada, use record nesting rather than relative numbers.


EMPLOYEE-RECORD :
record
EMPLOYEE-NAME :
  record
    FIRST    : STRING(1..20);
    MIDDLE   : STRING(1..10);
    LAST     : STRING(1..20);.
  end record;
HOURLY-RATE   : FLOAT;
end record;

Referring to subelements:
COBOL: MIDDLE OF EMPLOYEE-NAME OF EMPLOYEE-RECORD
Others langs: dot, or -> for pointers to structs. Fortran: %

elliptical names - as long as unambiguous, can omit middle stuff.

with in Pascal, VB6. Can do this in C++ using references.

Record Ops
Assignment. types must be same. Ada: comparison for =, <>, initialization with literals.

COBOL: MOVE CORRESPONDING
if subfields have same name, copy it.

Implementation. adjacent memory, and field names associated with offset. descriptor has, for each field: Name, type, offset.

Unions
type that stores diff type values at diff times.
Q: Should we provide type-checking for current type, dynamically? Should unions be embedded in records?

free unions give programmer complete control, no type checking.
Pascal's unions, Ada's unions: have a tag or discriminant that tells current type.
more about this, but can read up on it. Ada adds constrained union such that in declaration, can restrict to one specific type, and thus do static type-checking.

Eval: flexibility vs. reliability.

Implementation:
Use same address for all members of union. enough storage for the largest.

Sets
C++ has but not exactly the same.
Until then, Pascal alone among imperative langs. max size implementation dependent, often < style="font-weight: bold;">type colors = {red, green, blue};
colorset = set of colors.
var set1, set2 : colorset;

set1 := [red, blue];

if ch in ['a', 'e', 'i', 'o', 'u'] ...

Check out ISETLW.

Eval
Ada, based on Pascal, but did not provide sets. rather, added membership op on enums.

other langs, use arrays and implement ops. unweildy, less efficient.

Impl
stored as bit strings. 0 if present, 1 if not present.

(C++ has a bitset.)

Pointers
We know about pointers, dereferencing, assignment to local, off heap, etc.

some problems with pointers:
dangling pointers - points to deallocated heap variable. and what if that memory claimed by s/t else?
lost heap-dynamic variable - lost in terms of no longer accessible. memory leak, vs. garbage collection.

Pascal: create new vars with new and elim with dispose, which sets all pointers pointing at this object to nil. implementation dependent.

Ada: access types. auto dealloc when ptr goes out of scope. elims problems caused by reliance on explicit dealloc. though gives deliberately unweildy alternate method.

C++, Java: ref types.

Handling dangling ptrs:
tombstones. ptrs only point to tombstones. tombstone points to actual memory. when deallocate, tombstone remains and is set to nil. costly in time and space. storage never reclaimed. no prog lang uses.

garbage collection vs. reference counters: lazy, eager approach.

reference counters - keep track how many things pointing to this, when ref count reaches zero, can be reclaimed.

garbage collection - when run out of space, or can explicitly invoke. how do we know when something not pointed to? keep track of each ptr. named ptrs, and following named ptrs as far as they go.

Next: Expressions, Assignment Statements
unary, binary, ternary ops.
usually Infix.

a + b * c

right to left, left to right, or operator precedence.

associativity to left, to right: a - b + c - d

use of parentheses.

side effects -what else happens as a result.
a + fun(a)
functional side-effects
FORTRAN only allows (=legal) if function does not change value. but s/t hard to determine, based on pointers, globals.

operator side-effects
b = a++ + a++;
reference point, e.g. assigning twice between two reference points.

to be continued...

More Prolog

2006-03-07T07:56:00.000-08:00

Here are some Prolog programs (written in Strawberry Prolog) and their output:

program
father(avraham, yitzchak).
father(yitzchak, yaakov).

ancestor(X, Y) :- father(X,Y).
ancestor(X, Y) :- father(X,Z), ancestor(Z, Y).

?- father(yitzchak, X), write(X), write("\n").

Output:
Compiling the file:
c:\father
0 errors, 0 warnings.

yaakov
Yes.

program
add1(X, Y) :- Y is X + 1.

?- add1(4, 5).

output
Yes.

program
add1(X, Y) :- Y is X + 1.

?- add1(4, 6).

output
No.

program
add1(X, Y) :- Y is X + 1.

?- add1(4, X), write(X), write("\n").

output
5
Yes.

program
add(X, Y, Z) :- Z is X + Y.

?- add(4, 5, X), write(X), write("\n").

output
9
Yes.

program
add(X, Y, Z) :- Z is X + Y.

?- add(4, "hello", X), write(X), write("\n").

output
4hello
Yes.

program
add(X, Y, Z) :- Z is X + Y.

?- add(4, Y, X), write(X), write("\n").

output
Compiling the file:
c:\father
0 errors, 0 warnings.

Runtime Error at step 3:
The argument 2 of "+"
is "var" but has to be "str" or "int" or "float".

No.

program
add(X, Y, Z) :- Z is X + Y.

?- add(4, 5, 9), write(X), write("\n").

output
_9
Yes.

program
father(avraham, yitzchak).
father(yitzchak, yaakov).

ancestor(X, Y) :- father(X,Y).
ancestor(X, Y) :- father(X,Z), ancestor(Z, Y).

?- ancestor(avraham, X), write(X), write("\n").

output (selecting Run, then Next Answer)
Compiling the file:
C:\father
0 errors, 0 warnings.

yitzchak
Yes.
yaakov
Yes.

program
abs(X, Y) :- X = Y, X >= 0.

?- abs(4, T), write(T), nl.

output
4
Yes.

program
abs(X, Y) :- X = Y, X >= 0.

?- abs(-4, T), write(T), nl.

output
No.

program
abs(X, Y) :- Y = X, X >= 0.
abs(X, Y) :- Y = 0 - X.

?- abs(-4, T), write(T), nl.

output
4
Yes.

program:
append([], L, L).
append([H | T] , L2, [H | L3] ) :- append(T, L2, L3).

1) empty list + L = L
2) recursion step
appending a list [H | T] to any list L2 produces the list [H | L3], on condition that L3 is formed by appending T to L2.

try out an example.

Prolog Compilers, Interpreters

2006-03-01T04:24:00.000-08:00

There is one that actually runs in your browser window if you have a Java-enabled browser. Click here, scroll down to "the distribution," and click on the button labelled "Start W-Prolog" to start the prolog interpreter Applet.

Copy the text of the facts and rules from the previous post, and run a query to see if terach is the father of yishmael.

There are some free compilers and interpreters here.

Prolog - I

2006-03-01T04:04:00.000-08:00

Facts, rules, and goals.

father(terach, avraham).
father(avraham, yitzchak).
father(avraham, yishmael).

ancestor(X, Y) :- father(X, Y).
ancestor(X, Y) :- father(X, Z), ancestor(Z, Y).

try this out. how would you write a brother rule?

Data Types 2

2006-02-28T12:57:00.000-08:00

Array = homogenous collection
q: what types for subscripts, do we rangecheck, are ranges bound, array alloc when, how many subscripts (1,2), initialization, are slices allowed?
FORTRAN:
SUM = SUM + B(I)
same () as functions so needs keep track. why? no other chars avail. Ada as well - because both are mappings of parameters to values. Pascal, C++, Java = []

obvious point: element type vs. subscript type. most often subrange of int. Pascal, Ada: Bool, char, enum.

subrange checking: Pascal, Ada, Java. Not C++, FORTRAN - out of bound errors. speed vs. reliability.

Binding of subscript type statically bound (usually) but value range can s/t vary dynamically.

lower bound: 0, 1, set by user.

4 cat, based on binding to subscript range and binding to storage.
static array - both ranges and binding to storage at compile time. no dynamic alloc dealloc. FORTRAN 77.
fixed stack-dynamic - subscripts bound statically, storage bound off the stack - C, Pascal.
stack-dynamic - same as above but subscript bound dynamically as well. but then remain fixed for lifetime of var. Ada:
GET (LIST_LEN)
declare
LIST : array (1..LIST_LEN) of INTEGER
begin
...
end
heap-dynamic - same, but can change many times during lifetime. FORTRAN 90:
INTEGER, ALLOCATABLE, ARRAY (:, :) :: MAT
ALLOCATE (MAT(10, NUMBER_OF_COLUMNS)
DEALLOCATE(MAT)
same idea in C, C++ using pointers.

Number of Subscripts
saw in fortran assignment that could use mult indices. original fortran restricted to 3. The ZERO-ONE-INFINITE principle. Let programmer bear the cost if he wants. FORTRAN IV it became 7. Modern - unlimited.

Array init: FORTRAN has it in the form of a DATA statement:
DATA MYVAR / 8, 9, 10/
in C, init of arrays, of strings, of arrays of strings. In Java.
Ada:
LIST : array (1..5) of INTEGER := (1, 4, 6, 8, 10)
LIST : array (1..5) of INTEGER := (1 => 3, 4 => 9, others =>0)

array ops

to be continued...

Class Notes - Data Types - 1

2006-02-23T11:55:00.000-08:00

Lifetime
Not same as scope. Example – subprogram in C where exists but hidden. Static in C.

Symbolic constants
Why? Readability. Reliability. Ease of changing the program. We saw in the program where can be useful. Two types – lvalues and rvalues. Const vs. #define.
Pascal - simple, Modula-2: complex expressions. manifest constants –simple due to static binding of values.
C++, Java, Ada: constants based on variables – bound at runtime

Initializing Variables
We know C++. int x = 6; FORTRAN has DATA statement
REAL PI
INTEGER SUM
DATA SUM /0/, PI /3.14/
Some langs do not have init statements. Just do assignment. Pascal.
When is this initialization done? Static vs. auto in C.

ALGOL 60
First, ALGOL 58, designed by international committee. 3 goals: close to standard mathematical notation; use to describe computing processes in publications; able to translate to machine code. JOVIAL, MAD, NELIAC. In general, taken to be guidelines for developing langs. IBM interested in promoting FORTRAN.
ALGOL 60, Peter Naur described using BNF, which while elegant, was not well understood back then.
Contributions: many langs based on this. Example: pascal, ALGOL 68, Ada, C++, PL/I, Java. Was only accepted way of describing algorithms. Influenced machine architecture to implement the concepts. Advances: block structure; pass by value and pass by name. recursive procs. Stack dynamic arrays. (now they have them in C, I think). But lacked standard IO = difficulty porting. People already using FORTRAN.

I posted before an initial ALGOL reading – 95 – 121. A summary of material covered there – Algol 58, use of BNF (with further discussion in next chapter), Algol 60. Blocks. Though ALGOL has static scoping, a discussion of dynamic scoping. Pg 118. generalized arrays by allowing lower bounds, dynamic arrays. Pg 119 – strong typing. Look thru the code.

Now 121-140. A lot of what we discussed. Pass by name, value. Recursive procedures. Introduction of for loop with step – very general. The switch.

months
For days := 31, 28, 31, 30, 31, 31, 31, 30, 31, 30 do
For days := 31, if (mod(year, 4) = 0 then 29, else 28, 31, 30, 31, 31, 31, 30, 31, 30

Homework: Print Oscillating sum
Homework: Set up Prolog

Data types:
Early on, model linked list, binary tree, with arrays. Think. How would do it?
COBOL – allowed specification of precision, structured data type for records. PL/I – extended precision to ints and floats. ALGOL 68: primitives and structure-defining ops. (examples of ops – in C: {}, (), *, []) User defined data types – able to associate name w/ data type. Abstract data types – use of a type differs from internal representation and ops available on type
Homogeneous (array) vs. heterogenous (record).

Primitives – not based on other types. Ints reflect storage in hardware. Others – in software.

Numerics – integers: signed (one’s complement, two’s complement), unsigned, short, int, long. Floats: 1 sign bit, 8 bit exponent, 23 bit fraction = 32. Double: 1/11/52 = 64.
Decimal: use byte or nibble per digit. Decimal point does not float. Boolean types. As bit, byte, int. Char type: ASCII, Unicode (2 byte).

String Types: might be built in or built upon array of char. Do we allow array ops on it. Should they be static or dynamic length?
Not primitive: C++, Pascal, Ada.
In Ada: array of char, can reference a single char. Various ops built in.
substr: name1(2:4)
& for concatenation. As in VB6.
C++: ignoring the stl. After all, literal strings are arrays of char, null terminated. Built in library functions – strcpy, strcat, etc.
FORTRAN 70+: they are primitives. Have assignment, relational ops, concatenation, substring.
Java: primitive type. String class: holds constant strings. StringBuffer. Why this is really annoying. String comparisons in Java.
SNOBOL4, Perl, Javascript: pattern matching string op. many other langs: as functions.
In SNOBOL4, patterns can be assigned to variables.
LETTER = ‘abcdefghijklmnopqrstuvwxyz’
WORDPATTERN = BREAK(LETTER) SPAN(LETTER) . WORD
Means skip until find a letter, then span letters, then assign (the .) to the variable WORD
TEXT WORDPATTERN
Perl: Based on regular expressions. /[A-Za-z][ [A-Za-z]+/ /\d+\. ?\d* | \.\d+/

static vs. dynamic string lengths
FORTRAN 90:
CHARACTER (LEN = 15) A, B
Always full, empty chars are blank.
C, C++: limited dynamic. Except for STL
SNOBOL4, JavaScript, Perl: dynamic
Talk about benefits, drawbacks of each scheme

Implementation
Static: at compile time: name of type, the length, the address
Limited dynamic: store capacity, current length. (though C++ needs this not)
No need for dynamic allocation.
Dynamic: as linked list, but have many pointers. Dense list. But what if space afterwards is claimed – must realloc and copy. We can use a mixture of the two approaches.

User-defined Ordinals.
enum. C, Ada
Design: In Pascal, a given enum val (e.g. January) not allowed to be used in more than a single enum, cannot be input or output, but can be assigned, compared, used in for loop.
Some languages allow overloading of these literals, but then need to specify type:
e.g. type letters is (‘A’, ‘B’, ‘C’, ‘D’ ….
type vowels is (‘A’, ‘E’, ‘I’, ‘O’, ‘U’)
for letter in ‘A’ ,,. ‘U’ loop
for letter in vowels(‘A’) ,,. Vowels(‘U’) loop

Ada’s BOOLEAN and CHARACTER are predefined enums

Ops: pred, successor, position. Pascal: pred(blue) is red. Ada, as attributes: Letter’Pred(‘B’) is ‘A’

Improves readability, reliability

Subrange types – continuous subsequence of an ordinal
Pascal:
type
uppercase = ‘A’ .. ‘Z’;
index = 1 .. 100;

In Ada, called subtypes. Assuming already defined an enum:
Subtype WEEKDAYS is DAYS range Mon .. Fri
Subtype INDEX is INTEGER range 1 .. 100

Ada allows assignment from parent to subtype unless it is not defined, so might assign Tuesday but not Sunday.
Recall that diff from Ada’s type, where cannot assign from parent to derived type.

Implementation: As parent types, but with range checking for each assignment.

Array Types

Syllabus - work in progress

2006-02-21T21:23:00.000-08:00

Work in progress - to be refined, added to, etc.

Preliminaries

why study programming languages, programming domains, criteria to evaluate languages, influences on language design, language categories, design trade-off.

Some History

pseudocodes, FORTRAN, ALGOL. discuss other languages later, as they come up.

Syntax

describing syntax, lexemes, tokens, language recognizers and generators, BNF and CFGs, EBNF, parse trees, ambiguity, precedence, associativity, regular expressions, FSA, NFSAs, PDAs.
Lexical analysis, parsing, lex and yacc.

Names, Bindings, Type Checking, Scopes, Lifetime. static and dynamic
Data Types

Primitives, strings, user-defined ordinals, arrays, associative arrays, records, unions, sets, pointers. Also, some discussion of ALGOL

Expressions and Assignment statements

arithmetics expressions, overloaded operators, type conversions, relational/boolean expressions, short circuit evaluation, assignment statements, mixed-mode assignment. More ALGOL.

Control Structures

compound statements, selection statements, iterative statements, unconditional branching, guarded commands

Subprograms

design issues, local referencing environments, parameter passing methods, overloaded subprograms, generic subprograms, separate and independent compilation, design issues for functions, accessing nonlocal environments, user-defined overloaded operators, coroutines.

Implementing subprograms

General semantics of calls and returns, implementing: FORTRAN subprograms, ALGOL subprograms, blocks, dynamic scoping, parameters that are subprogram names.

Encapsulation, OOP - we will probably skip since we already know this fairly well.
Concurrency - perhaps
Exception handling - perhaps if have time at the end, since will cover this elsewhere

in PL/I, in Ada, in C++, in Java

Functional Programming - we will do LISP

Mathematical functions, fundamentals of functional programming langs, LISP, Scheme, Common LISP, ML, Haskell, Applications of, comparison between functional and imperative languages

Logic Programming Languages - Prolog

Predicate Calculus, Proving Theorems, Logic Programming, Intro to Prolog, applications of

Bindings And Scope

2006-02-21T17:14:00.000-08:00

3. Variables
Replace absolute address with symbols. A tuple: (name, address, value, type, lifetime, scope).
address: can have many instantiations of same name at different addresses. via functions, different scope, recursion. vs.
alias - many names for one address. EQUIVALENCE in Fortran. Pascal and Ada's variant record structure. C's union. C's pointers, C++'s references.
type - defines value range and ops can perform. unsigned short int.
value - contents of mem cell.

4. Binding
Association between attrib and entity, or between op and symbol.
binding time = when binding takes place.
int count; ... count = count + 5;
Bindings and binding times:
set of poss types for count: lang design time
type of count: compile time
poss values for count: compiler design time
count's value: execution time
meanings of +: lang definition time
meaning of + in this statement: compile time
internal representation of 5: compiler design time

binding attribs to vars: static = before runtime. vs. dynamic.

Type Binding. static w/ or w/o explicit declarations. Modern: Perl, ML - no explicit. VB6 optional. Fortran, PL/I, Basic: implicit. we spoke about Fortran's convention, and about unreliability. C: declarations vs definitions. dynamic: not bound by declaration, but at assignment, and can be reassigned. =flexibility. func can deal with data of any type. C++ needs know type of the data. Consider swap in C.
Jscript: list = [1.4, 4.5] and can reassign to a scalar.
lack of reliability due to typos generating new vars, or if assignment should not work, will.
usually interpreted rather than compiled because hard to implement dynamic type changes in machine code.

Type inference: ML can infer type.
fun circum(r) = 3.14 * r * r;
fun square(x) : int = x * x; //int specifies return type

Storage Bindings/Lifetimes
allocation/deallocation. lifetime= time var bound to a specific address.
static vars - throughout program execution. retain history, speed 'cause no alloc/dealloc. no recursion, waste of space.
stack-dynamic - allocated when declaration statement reached. could either be when enter func (Ada) or when reach that pos (Java). Allows recursion, sharing of space.
explicit heap-dynamic - using new and delete
implicit heap-dynamic - Perl, Javascript arrays and strings. as a result of assignment.

Type-Checking
For both operations and functions. Type checking: make sure operands are of compatible types. compatible = legal for operator or can be implicitly converted (=coersion). type error - where cannot apply operator to operand.

depends on bindings of vars to types. if static, can do type checking statically. if dynamic, must be done at runtime = dynamic type checking. better to detect earlier. tradeoff of reliability with flexibility. What about variants, unions? Must maintain current type, if do actually check.

Strong Typing
Structured programming in 70's --> strong typing. each name has single type, defined statically = known at compile time. For variant records: type errors are always detected.
Pascal: almost strongly typed. allows type tag omission in variants.
Ada as well: variants dynamically checked. But can specify UNCHECKED_CONVERSION function. oiwerful, useful for using pointers as ints for user-defined storage allocation/deallocation. Modula-3: LOOPHOLE
C, C++: not. functions where parameters not type-checked. Namely, the "..." How do you think printf works?
ML: Strong: types all statically known, from declarations of inference.
Java: Strongly typed. Can do explicit conversion, resulting in type error, but no implicit conversion. at least in assignment. still some implicit coversion, in terms of evaluating expressions. int + float. string + int. "hello" + i + j.
more coercion --> less reliability.

Type Compatibility
in terms of assignment, most often. name type compatibility = only if have same names.
structure type compatibility - if structures are the same.

Consider the enum in C. Can we assign it to an int of v.v.?
When pass vars to funcs. if we define locally, who is to say that types are the same? Original Pascal - define it globally.

flexibility vs. difficulty implementing. compiler compare name, or compare each element type. What if have same structure in terms of data types but diff field names? Diff subscript ranges (0...9) vs (1..10)? Two enums with same num of components?

type celsuis = real;
type fahrenheit = real;

Pascal did not initally specify, which led to diff implementations. ISO Pascal - mixed: declaration equivalence - if define one type name = another type.

Ada: derived type vs subtype. derived:

type celsuis is new FLOAT;
type fahrenheit is new FLOAT;

cannot assign to each other, to and fro FLOATS, except literals.
subtype is compatible with parent:
subtype SMALL_TYPE is INTEGER [range 0 .. 99];

C: structural equivalence.
C++: name equivalence. typedef does not introduce new type, but acts as a macro.

Ada: need no type names
C, D : array (1 .. 10) of INTEGER; is incompatible
type: LIST_10 is array (1 .. 10) of INTEGER;
C, D: LIST_10;

Scope
scope = range in which is visible, ie can be referenced in a statement. locals vs. globals.

ALGOL 60: static scope. this is what we are used to. in C: globals seen in functions. within functions, nested ifs, blocks, etc. However, also nested procedures. static parent and ancestors.


procedure big;
var x : integer;
procedure sub1;
begin { sub1 }
...x...
end; {sub1}
procedure sub2;
var x : integer;
begin { sub2 }
...x...
end; {sub2}
begin { big }
...x...
end; {big}

Also, have narrower scop hiding wider scope. Scope resolution op in C++. C++ doesn't allow nested funcs, but do allow globals.

Blocks
Again, ALGOL 60.
In Ada:
declare TEMP : integer
begin
TEMP := FIRST
FIRST := SECOND
SECOND := FIRST
end;

C, Java: {}. for's changing scope.

Dynamic Scope
APL, SNOBOL4, early lisp
problems: cannot determine attributes statically.
1) less reliable, since subprograms, even far off textually, can modify local vars.
2) cannot do static type checking
3) akin to Spaghetti code.
4) speed issues - much slower to access
benefits: no need to pass vars, bec implicitly visible
But static is more readable and faster. perhaps later discuss implementation of each.

Reading in ALGOL, Compiling in ALGOL

2006-02-21T12:30:00.000-08:00

We are about ready to move on to the next programming language: ALGOL.

Here is a page with some free ALGOL compilers and interpreters. Try installing one and see if the following "hello world" code will run:

'BEGIN'
 'COMMENT' Hello World in Algol 60;
  OUTPUT(4,'(''('Hello World!')',/')')
'END'

Or in ALGOL 68:

( # Hello World in Algol 68 # print(("Hello World!",newline)))

In the book, read from pg. 95-121.

Here is a Wikipedia article on ALGOL:

Analysis of a FORTRAN Matrix Program - III

2006-02-21T10:06:00.000-08:00

The code, as a reminder:

! program to calculate whether a graph is strongly connected
! it calculates this my using matrix multiplication on the
! adjacency matrix representing the graph
PROGRAM matrix

INTEGER :: length
PARAMETER (length = 4)
INTEGER :: a,b, c, m(length,length), copy(length,length), total, d, e, f

m(1, :) = (/ 1, 0, 1, 0/)
m(2, :) = (/ 1, 0, 0, 0/)
m(3, :) = (/ 1, 1, 0, 1/)
m(4, :) = (/ 0, 0, 1, 0/)

!initialize a copy of m so that we may calculate N^2
copy = m

DO a = 1, length
DO b = 1, length
total = 0
DO c = 1, length
total = m(a,c) * copy(c,b) + total
END DO
IF (total > 0) THEN
m(a,b) = 1
ELSE
m(a,b) = 0
END IF
END DO
END DO

DO f = 1, length
PRINT *, m(f,1:4)
END DO

DO e = 1, length
total = 0
DO d = 1, length
IF( m(d,e) .EQ. 1 .AND. m(e,d) .EQ. 1 ) total = total + 2
END DO
IF ( total == 8 ) THEN
PRINT *, 'Strongly Connected At: ', e
ELSE
PRINT *, 'Not Strongly Connected At: ', e
END IF
END DO

END PROGRAM matrix

Now, while the example I used in class had only 1s and 0s in the result, in reality we may have higher numbers. This is fine. A zero in position (i,j) means that there is no path from i to j, but a number greater than zero, such as 1 or 3 or 8, means that there is a path. So we need not check specifically for a nonzero and set the result to 1.

One we know this, we may use the built-in matmul function that I suggested you use, rather than doing the matrix multiplication by hand. Doing matmul it by hand is certainly still good programming exercise, but if we have this function built in, it may just be incredibly optimized. Further, it saves programmer work. Further, it makes the code smaller and thus more readable and less error-prone.

There was actually a bug in this code, which I should comment upon before proceeding:


DO a = 1, length
DO b = 1, length
    total = 0

        ! the following code calculates a single dotproduct
    DO c = 1, length
        total = m(a,c) * copy(c,b) + total
    END DO

        ! and here we assign the result to m
    IF (total > 0) THEN
        m(a,b) = 1
    ELSE
        m(a,b) = 0
    END IF
END DO
END DO

The problem is twofold. Firstly, we are only doing a single matrix multiplication in this entire code - calculating M^2 rather than M^4. Secondly, we are not even calculating M^2 correctly! This is because we are modifying M in the middle of the multiplication! M(1,1) is being set, and then that value is being used to compute M(1,2), M(1,3), M(1,4), and M(2,1), M(3,1), and M(4,1). We could solve this by making a third matrix, result, and assigning to that matrix, and then stating m = result at the end. But let us skip this entire step and just use the built in matmul function. We no longer need the copy matrix for this purpose, but I will leave it in in case we need it for some other purpose. I will change the code, commenting out the previous code so we can see what changed. I will still only calculate M^2. We will deal with M^4 and the associated problem later.


! program to calculate whether a graph is strongly connected
! it calculates this my using matrix multiplication on the
! adjacency matrix representing the graph
PROGRAM matrix

INTEGER :: length
PARAMETER (length = 4)
INTEGER :: a,b, c, m(length,length), copy(length,length), total, d, e, f

m(1, :) = (/ 1, 0, 1, 0/)
m(2, :) = (/ 1, 0, 0, 0/)
m(3, :) = (/ 1, 1, 0, 1/)
m(4, :) = (/ 0, 0, 1, 0/)

!initialize a copy of m so that we may calculate N^2
copy = m

!DO a = 1, length
! DO b = 1, length
!  total = 0
!
!  DO c = 1, length
!   total = m(a,c) * copy(c,b) + total
!  END DO
!
!  IF (total > 0) THEN
!   m(a,b) = 1
!  ELSE
!   m(a,b) = 0
!  END IF
! END DO
!END DO

! calculate M^2
m = matmul(m, m)

DO f = 1, length
PRINT *, m(f,1:4)
END DO

DO e = 1, length
total = 0
DO d = 1, length
IF( m(d,e) .EQ. 1 .AND. m(e,d) .EQ. 1 ) total = total + 2
END DO
IF ( total == 8 ) THEN
PRINT *, 'Strongly Connected At: ', e
ELSE
PRINT *, 'Not Strongly Connected At: ', e
END IF
END DO

END PROGRAM matrix

Analysis of a FORTRAN Matrix Program - II

2006-02-21T09:45:00.000-08:00

The program already has a nice feature. It defines length to be 4 and then uses length throughout in the loops. That way, if we want to change the program to handle a 5 X 5 matrix, we can just change the declaration of our matrices to 5 X 5, and length to = 5, and the program will run. Using symbols instead of literals in this way makes the program mode readily adaptable.

The program, again:

! program to calculate whether a graph is strongly connected
! it calculates this my using matrix multiplication on the
! adjacency matrix representing the graph
PROGRAM matrix

INTEGER :: a,b, c, m(4,4), copy(4,4), total, length = 4, d, e, f

m(1, :) = (/ 1, 0, 1, 0/)
m(2, :) = (/ 1, 0, 0, 0/)
m(3, :) = (/ 1, 1, 0, 1/)
m(4, :) = (/ 0, 0, 1, 0/)

! copy(1, :) = (/ 1, 0, 1, 0/)
! copy(2, :) = (/ 1, 0, 0, 0/)
! copy(3, :) = (/ 1, 1, 0, 1/)
! copy(4, :) = (/ 0, 0, 1, 0/)

!initialize a copy of m so that we may calculate N^2
copy = m

DO a = 1, length
DO b = 1, length
total = 0
DO c = 1, length
total = m(a,c) * copy(c,b) + total
END DO
IF (total > 0) THEN
m(a,b) = 1
ELSE
m(a,b) = 0
END IF
END DO
END DO

DO f = 1, length
PRINT *, m(f,1:4)
END DO

DO e = 1, length
total = 0
DO d = 1, length
IF( m(d,e) .EQ. 1 .AND. m(e,d) .EQ. 1 ) total = total + 2
END DO
IF ( total == 8 ) THEN
PRINT *, 'Strongly Connected At: ', e
ELSE
PRINT *, 'Not Strongly Connected At: ', e
END IF
END DO

END PROGRAM matrix

However, as implemented, there are two things I would change. Firstly, length is declared as a variable. This means that somewhere in the program, I might change it by accident. It would be better to declare it a constant. But how do we do this in FORTRAN? The answer, we declare its data type and then set its value with a PARAMETER statement.

Another thing I would change: the declaration of our matrices m and copy use a literal 4. When modifying the program, I would not only have to change the definition of length but my matrix definitions as well. Instead, let us use our new constant to define the matrix size. We will also remove the old code that was commented out:

! program to calculate whether a graph is strongly connected
! it calculates this my using matrix multiplication on the
! adjacency matrix representing the graph
PROGRAM matrix

INTEGER :: length
PARAMETER (length = 4)
INTEGER :: a,b, c, m(length,length), copy(length,length), total, d, e, f

m(1, :) = (/ 1, 0, 1, 0/)
m(2, :) = (/ 1, 0, 0, 0/)
m(3, :) = (/ 1, 1, 0, 1/)
m(4, :) = (/ 0, 0, 1, 0/)

!initialize a copy of m so that we may calculate N^2
copy = m

DO a = 1, length
DO b = 1, length
total = 0
DO c = 1, length
total = m(a,c) * copy(c,b) + total
END DO
IF (total > 0) THEN
m(a,b) = 1
ELSE
m(a,b) = 0
END IF
END DO
END DO

DO f = 1, length
PRINT *, m(f,1:4)
END DO

DO e = 1, length
total = 0
DO d = 1, length
IF( m(d,e) .EQ. 1 .AND. m(e,d) .EQ. 1 ) total = total + 2
END DO
IF ( total == 8 ) THEN
PRINT *, 'Strongly Connected At: ', e
ELSE
PRINT *, 'Not Strongly Connected At: ', e
END IF
END DO

END PROGRAM matrix

Analysis of a FORTRAN Matrix Program - I

2006-02-21T09:31:00.000-08:00

Here I present a matrix homework. I will post comments and suggestions in a series of posts. First, here is the program at the outset.

PROGRAM matrix

INTEGER :: a,b, c, m(4,4), copy(4,4), total, length = 4, d, e, f

m(1, :) = (/ 1, 0, 1, 0/)
m(2, :) = (/ 1, 0, 0, 0/)
m(3, :) = (/ 1, 1, 0, 1/)
m(4, :) = (/ 0, 0, 1, 0/)

copy(1, :) = (/ 1, 0, 1, 0/)
copy(2, :) = (/ 1, 0, 0, 0/)
copy(3, :) = (/ 1, 1, 0, 1/)
copy(4, :) = (/ 0, 0, 1, 0/)

DO a = 1, length
DO b = 1, length
total = 0
DO c = 1, length
total = m(a,c) * copy(c,b) + total
END DO
IF (total > 0) THEN
m(a,b) = 1
ELSE
m(a,b) = 0
END IF
END DO
END DO

DO f = 1, length
PRINT *, m(f,1:4)
END DO

DO e = 1, length
total = 0
DO d = 1, length
IF( m(d,e) .EQ. 1 .AND. m(e,d) .EQ. 1 ) total = total + 2
END DO
IF ( total == 8 ) THEN
PRINT *, 'Strongly Connected At: ', e
ELSE
PRINT *, 'Not Strongly Connected At: ', e
END IF
END DO

END PROGRAM matrix

One thing that is missing from this program is comments. Tell me what the program is supposed to do, and what each section of the code is supposed to do. It used to be that the letter C at the beginning of the line would start a comment. Here, instead, we use the character !

Another thing to realize is that you can assign an entire matrix to another matrix with the = operator. You need not initialize copy separately, or even loop, copying elements. Rather, just use =. I will comment out the code and put in the new code in its place. My changes in red.

! program to calculate whether a graph is strongly connected
! it calculates this my using matrix multiplication on the
! adjacency matrix representing the graph
PROGRAM matrix

INTEGER :: a,b, c, m(4,4), copy(4,4), total, length = 4, d, e, f

m(1, :) = (/ 1, 0, 1, 0/)
m(2, :) = (/ 1, 0, 0, 0/)
m(3, :) = (/ 1, 1, 0, 1/)
m(4, :) = (/ 0, 0, 1, 0/)

! copy(1, :) = (/ 1, 0, 1, 0/)
! copy(2, :) = (/ 1, 0, 0, 0/)
! copy(3, :) = (/ 1, 1, 0, 1/)
! copy(4, :) = (/ 0, 0, 1, 0/)

!initialize a copy of m so that we may calculate N^2
copy = m

DO a = 1, length
DO b = 1, length
total = 0
DO c = 1, length
total = m(a,c) * copy(c,b) + total
END DO
IF (total > 0) THEN
m(a,b) = 1
ELSE
m(a,b) = 0
END IF
END DO
END DO

DO f = 1, length
PRINT *, m(f,1:4)
END DO

DO e = 1, length
total = 0
DO d = 1, length
IF( m(d,e) .EQ. 1 .AND. m(e,d) .EQ. 1 ) total = total + 2
END DO
IF ( total == 8 ) THEN
PRINT *, 'Strongly Connected At: ', e
ELSE
PRINT *, 'Not Strongly Connected At: ', e
END IF
END DO

END PROGRAM matrix

Some Pointers with the FORTRAN matrix assignment

2006-02-20T14:59:00.000-08:00

1)
Definition of Strongly Connected Graph

A directed graph is called strongly connected if for every pair of vertices u and v there is a path from u to v and a path from v to u.

2) A program that uses the built in matmul, and does assignment from one matrix to another:

! EXAMPLE 4
!
! Aprogram to compute the largest eigenvalue
! of a real, dense matrix by the power method

integer, parameter::devno=10, n=10, minit = 10, maxit=100
real::lambda_old, lambda_new
real::rel_err, tol = 2.0**(-20)
real,dimension(n)::x_new, x_old=(/(1.0/n,i=1,n)/)
real,dimension(n,n)::a
open(devno, file='a.dat')
read(10,10) ((a(i,j),j=1,n),i=1,n)
10 format(10f4.1)
iterate: do i=1,maxit
 write (*,*) "i = ", i
 x_new=matmul(a, x_old)
 lambda_new = sqrt(dot_product(x_new, x_new))
 write(*,*) "lambda_new = ", lambda_new
 if (i .gt. minit) then
    rel_err = abs((lambda_new - lambda_old)/lambda_old)
    if (rel_err .lt. tol) exit iterate
 endif
 if (i .eq. maxit) write (*,*) "Maximum Iterations reached"
 lambda_old = lambda_new
 x_old = x_new/lambda_new
end do iterate
write(*,*) "lambda = ", lambda_new
end

Another place that uses matmul.

Explaining Lex and Yacc

2006-02-17T11:22:00.000-08:00

Note: Change {} after includes to pointy brackets.
1)
What exactly are you doing when you process something with lex?

Well, lex takes your lex file, say example2.l and generates a file in the C language. The name of this file is lex.yy.c.

In class, I spoke about Finite State Machines, and how they can recognize regular languages. lex.yy.c is an implementation of a Finite State Machine based on your lex file. The regular expressions are inputs, and the actions or printfs are the outputs.

Thus, let us say we have example2.l:

%{
#include {stdio.h}
%}

%%
[0123456789]+           printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]*    printf("WORD\n");
%%

The stuff between %{ and %} will be included in the C file, which is important since we are using printf. The stuff between %% and %% are regular expressions together with the action to take after successfully recognizing that expression.

At the command line, we type:
lex example2.l

This generates the file lex.yy.c.

Pseudocode to explain what this file contains (obtained from this website):

        state= 0; get next input character
      while (not end of input) {
         depending on current state and input character
            match: /* input expected */
               calculate new state; get next input character
            accept: /* current pattern completely matched */
               state= 0; perform action corresponding to pattern
            error: /* input unexpected */
               state= 0; echo 1st character input after last accept or error;
               reset input to 2nd character input after last accept or error;
      }

Thus, we start at the start state, read input. So long as we are matching, we calculate a new state based on current state and input character. We do this until we enter an accept state. If we do, we go to the start state once again, so we can match the next string (=token), . If we go to an error state along the way, we say so and try matching again.

We need not go into detail here how exactly lex.yy.c implements this Finite State Machine in C. You can try examining the code if you want.

Now, if we want to run this Finite State Machine in lex.yy.c, we cannot, because it is written in C, not in machine language. Thus, we must compile the file.

There are two ways to compile it. We can incorporate the lex.yy.c with other files in a C project, and call the various functions and access the variables it exposes. We would need to do this because lex.yy.c does not have its own main function. Alternatively, we could specify that libl provide us with an appropriate main(). We do the latter.

Thus, at the command line, we type:
cc lex.yy.c -o example2 -ll

This -ll gets the main() function from libl. -o states that the output file should be what we specify, namely example2.

We can then run the executable, example2.

2) What exactly does yacc do?
yacc takes a yacc file which contains BNF and generates a C file which implements a Push Down Automaton (PDA) which accepts the context free language specified in the yacc file.

We use yacc together with lex.
Our lex file will recognize and inform us about tokens, while our yacc file will base itself upon those tokens and recognize a context free grammar.

Beforehand, we used the -ll option with the cc command, so that we were provided with a main() function.

Now, however, we want to compile more than just the lex.yy.c file. We want to incorporate it with C code generated by yacc. Thus, we will no longer use the -ll option. Instead, we will make sure that our yacc file has a main() function defined.

3)
Let us consider example4, which is the thermostat example.

Create a lex file, example4.l. The contents of this file should be:

%{
#include {stdio.h}
#include "y.tab.h"
%}
%%
[0-9]+                  return NUMBER;
heat                    return TOKHEAT;
on|off                  return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

Most of this should be familiar. We are matching tabs, newlines, the string "on" or "off", etcetera.

One thing is different, though. Rather that just having #include {stdio.h}, we have an additional line that we are explicitly marking to be included in the generated C file, lex.yy.c. That line is:

#include "y.tab.h"

y.tab.h is a header file needed in association with the C file generated by yacc, namely y.tab.c.

We now need a yacc file. The tutorial does a bad job here by separating parts of the file, and not . Basically, we need a single file that does three things:

Provide literal code that will include necessary .h files and provide needed functions such as main(). This part will be between %{ and %}
Give a definition of the tokens to be used in our grammar. This line will start %token.
Lay out the context free grammar, with rules, as well as actions to take (such as printf) after the rule has been satisfied. This should be embedded within %% and %% tags, but the tutorial omitted it, and thus you may have had a compile time error.

The contents of the file example4.y should be:

%{
#include
#include

void yyerror(const char *str)
{
fprintf(stderr,"error: %s\n",str);
}

int yywrap()
{
return 1;
}

main()
{
yyparse();
}

%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

%%
commands: /* empty */
| commands command
;

command:
heat_switch
|
target_set
;

heat_switch:
TOKHEAT STATE
{
printf("\tHeat turned on or off\n");
}
;

target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
printf("\tTemperature set\n");
}
;
%%

Save this file as example4.y. Then run yacc on it by typing at the command line:

yacc example4.y

This will generate two files, y.tab.h and y.tab.c.

Now, we have our three files:
lex.yy.c
y.tab.c
y.tab.h

We need to compile them. Remember we are not using the -ll option since we are providing our own main() function.

cc lex.yy.c y.tab.c -o example4

Then run example4.

Names and Binding

2006-02-16T17:03:00.000-08:00

We may return to talk more about parsing later.

1. Name forms:
max length, connector characters, case sensitivity, Limitation on max length to ease symbol table. C++ unlimited, but depends on implementation. does case sensitivity hurt readability, reliability, writability?
2. Special words = keywords vs. reserved words.
REAL APPLE
REAL = 3.4
INTEGER REAL
REAL INTEGER
predefined names in Ada. INTEGER and FLOAT are there by default but may be overridden. Pascal. Others in Ada brought in via with statements. printf and scanf in C.
3. Variables
Replace absolute address with symbols. A tuple: (name, address, value, type, scope).
address: can have many instantiations of same name at different addresses. via functions, different scope, recursion. vs.
alias - many names for one address. EQUIVALENCE in Fortran. Pascal and Ada's variant record structure. See here:
How do we implement this? Change size of allocate maximum.






TYPE Geom_Type IS (Unknown, Rectangle, Circle);
TYPE Geometric_Figure(Figure_Type : Geom_Type := Unknown) IS RECORD
-- Invariant data fields here
CASE Figure_Type IS
WHEN Rectangle =>
   Width  : Float;
   Height : Float;
WHEN Circle =>
   Radius : Float;
WHEN Unknown =>
   NULL;
END CASE;
END RECORD;

constrained vs. unconstrained.

GF : Geometric_Figure;
-- An unconstrained Geometric_Figure
GC : Geometric_Figure( Figure_Type => Circle );
-- A constrained Geometric Figure of Figure_Type Circle

discriminant, fixed, variant. reading allowed for all, var so long as proper type. writing: discr if dont change val or as record assignment. record assignment allowed if unconstrained, else discr must match. record compare if discr match/
C's union. C's pointers, C++'s references.

type - defines value range and ops can perform. unsigned short int.
value - contents of mem cell.

4. Binding
Association between attrib and entity, or between op and symbol.
binding time = when binding takes place.
int count; ... count = count + 5;
Bindings and binding times:
set of poss types for count: lang design time
type of count: compile time
poss values for count: compiler design time
count's value: execution time
meanings of +: lang definition time
meaning of + in this statement: compile time
internal representation of 5: compiler design time

binding attribs to vars: static = before runtime. vs. dynamic.

Type Binding. static w/ or w/o explicit declarations. Modern: Perl, ML - no explicit. VB6 optional. Fortran, PL/I, Basic: implicit. we spoke about Fortran's convention, and about unreliability. C: declarations vs definitions. dynamic: not bound by declaration, but at assignment, and can be reassigned. =flexibility. func can deal with data of any type. C++ needs know type of the data. Consider swap in C.
Jscript: list = [1.4, 4.5] and can reassign to a scalar.
lack of reliability due to typos generating new vars, or if assignment should not work, will.
usually interpreted rather than compiled because hard to implement dynamic type changes in machine code.

Type inference: ML can infer type.
fun circum(r) = 3.14 * r * r;
fun square(x) : int = x * x; //int specifies return type

Storage Bindings/Lifetimes
allocation/deallocation. lifetime= time var bound to a specific address.
static vars - throughout program execution. retain history, speed 'cause no alloc/dealloc. no recursion, waste of space.
stack-dynamic - allocated when declaration statement reached. could either be when enter func (Ada) or when reach that pos (Java). Allows recursion, sharing of space.
explicit heap-dynamic - using new and delete
implicit heap-dynamic - Perl, Javascript arrays and strings. as a result of assignment.

Some Linear Algebra

2006-02-16T12:44:00.000-08:00

Dot Product
1x + 3y + 7z = 7
[1 3 7] · [x y z] = 7
scalar result. transpose.

Solving sets of Linear equations. n equations and n unknowns

x + 4y + 6z = 6
2x + 5y + 15z = -1
2x + 5y = 9


[1 4  6]   [x]   [ 6 ]
[2 5 15] X [y] = [-1 ]
[2 5  0]   [z]   [ 9 ]

Matrix multiplication. Can implement various operations. Swap rows, add multiple of one row to another, etc.
Other matrix ops: multiplication by a scalar. matrix addition.

Matrix multiplication, addition, useful for finding cyles in graphs.
Adjacency matrix. A X A yields all cycles of length 2 in the diagonal.
Aⁿ yields all cycles of length n.
A + A² + A³ + ... Aⁿ. Looking at one full row or column will tell us if the graph is strongly connected.

Definitions: Finite State Machines

2006-02-14T17:55:00.000-08:00

The wikipedia entry on Finite State Machines, which breaks down into Deterministic and Nondeterministic finite state machines. Read up to and including the section on Acceptors and Recognizers, and Figure 2. Skip transducers if you wish, and read the mathematical model for acceptors.

If you want to read about PDAs, see here.

If you want, you can read about Turing Machines.

Linear Algebra: Definition of Matrix Multiplication

2006-02-14T17:05:00.000-08:00

Read this wikipedia article, up to but not including the section labelled the proportions-vectors method.

I hope to explain all this at the bigeinning of next class.

Linear Algebra: Definition of Dot Product

2006-02-14T16:59:00.000-08:00

From wikipedia:

In mathematics, the dot product, also known as the scalar product, is a binary operation which takes two vectors and returns a scalar quantity. It is the standard inner product of the Euclidean space.

The dot product of two vectors a = [a₁, a₂, … , a_n] and b = [b₁, b₂, … , b_n] is by definition

where Σ denotes summation notation. For example, the dot product of two three-dimensional vectors [1, 3, −2] and [4, −2, −1] is

[1, 3, −2]·[4, −2, −1] = 1×4 + 3×(−2) + (−2)×(−1) = 0.

Using matrix multiplication and treating the row vectors as 1×n matrices, the dot product can also be written as

where b^T denotes the transpose of the matrix b. Using the example from above, this would result in a 1×3 matrix (i.e. vector) multiplied by a 3×1 vector (which, by virtue of the matrix multiplication, results in a 1×1 matrix):

A bit on regular expressions

2006-02-13T06:45:00.000-08:00

From wikipedia:

Regular expressions consist of constants and operators that denote sets of strings and operations over these sets, respectively. Given a finite alphabet Σ the following constants are defined:

(empty set) ∅ denoting the set ∅
(empty string) ε denoting the set {ε}
(literal character) a in Σ denoting the set {a}

and the following operations:

(concatenation) RS denoting the set { αβ | α in R and β in S }. For example {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
(alternation) R|S denoting the set union of R and S.
(Kleene star) R* denoting the smallest superset of R that contains ε and is closed under string concatenation. This is the set of all strings that can be made by concatenating zero or more strings in R. For example, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }.

The above constants and operators form a Kleene algebra.

Many textbooks use the symbols ∪, +, or ∨ for alternation instead of the vertical bar.

To avoid brackets it is assumed that the Kleene star has the highest priority, then concatenation and then set union. If there is no ambiguity then brackets may be omitted. For example, (ab)c is written as abc and a|(b(c*)) can be written as a|bc*.

Examples:

a|b* denotes {ε, a, b, bb, bbb, ...}
(a|b)* denotes the set of all strings consisting of any number of a and b symbols, including the empty string
b*(ab*)* the same
ab*(c|ε) denotes the set of strings starting with a, then zero or more bs and finally optionally a c.
((a|ba(aa)*b)(b(aa)*b)*(a|ba(aa)*b)|b(aa)*b)*(a|ba(aa)*b)(b(aa)*b)* denotes the set of all strings which contain an even number of bs and an odd number of as. Note that this regular expression is of the form (X Y*X U Y)*X Y* with X = a|ba(aa)*b and Y = b(aa)*b.

The formal definition of regular expressions is purposefully parsimonious and avoids defining the redundant quantifiers ? and +, which can be expressed as follows: a⁺= aa*, and a? = (ε|a). Sometimes the complement operator ~ is added; ~R denotes the set of all strings over Σ that are not in R. The complement operator is redundant: it can always be expressed by only using the other operators.

Regular expressions in this sense can express exactly the class of languages accepted by finite state automata: the regular languages. There is, however, a significant difference in compactness: some classes of regular languages can only be described by automata that grow exponentially in size, while the length of the required regular expressions only grow linearly. Regular expressions correspond to the type 3 grammars of the Chomsky hierarchy and may be used to describe a regular language.

BNF in the book

2006-02-12T06:16:00.000-08:00

BNF is mentioned briefly in chapter 3, on page 96, in the book, and is described in greater detail in chapter 4, pgs 148-156

Class IV: Describing Syntax - BNF

2006-02-08T21:06:00.000-08:00

Formal definition of the syntax.
Why?
1) feedback cycle in language formation
2) implementors of compilers/interpreters
3) users of language

syntax = form of the language, vs. semantics = meaning of language

syntax of if:
if ({expr}) {statement}
but this tells us nothing about semantics.

ALGOL difficulties.

Describing Syntax:
1) Languages (natural and programming) are sets of strings of chars from an alphabet. These strings are sentences or statements. Syntax rules: which sentences are in the language.

Formal descriptions often don't deal with basic parts - lexemes, which might be specified by a separate lexical specification. Lex vs. Yacc. Lexemes: identifiers, literals, ops, keywords. programs = string of chars, or string of lexemes.

token = category of its lexemes. the output of Lex.
identifier might be total, count, etc..
plus_op just has + as the literal

index = 2 * count + 17;

Q: what are the tokens, what are the lexemes?

2) Two ways of defining lang: lang recognizer vs. lang generator. R (recognizer) takes in input and tells if it valid program. G generates all possible programs. These are related problems.

3) Formal methods of Describing Syntax:

BNF - Backus Naur Form. related to Chomsky's context free grammars, in context of natural language. ALGOL 58, ALGOL 60. Panini to describe Sanskrit.

series of rules, productions.
Alas, the limits of blogspot. {} instead of pointy brackets.
{assign} -> {var} = {expression}terminals vs. nonterminals. capital vs. lowercase. BNF grammar = collection of rules. | for "or." Pascal: {if_statement} -> if {logic_expression} then {statement} |{if_statement} -> if {logic_expression} then {statement} else {statement}

use recursion to describe lists: {identifier_list} -> identifier | identifier, {identifier_list}Grammars, derivations:
Start symbol S, {program}. Sentence generation called derivation.

{program} -> begin {statement_list} end
{statement_list} -> {statement} | {statement} ; {statement_list}
{statement} -> {var} = {expression}
{var} -> A | B | C
{expression} -> {var} + {var} | {var} - {var} | {var}

show derivation for begin A = B + C; B = C end

derivation order matters not, but this common approach is leftmost derivation.
HW: To implement such a grammar in C++ using STL and rand function, of by labelling rules.

Simple Grammar for Assignment:
{assign} -> {id} = {expr}
{id} -> A | B | C
{expr} -> {id} + {expr} | {id} * {expr} | ( {expr} ) | {id}

show derivation for A = B * (A+C)

4) Parse trees
show parse tree for above. parse tree matches a derivation.

5) Ambiguity
An ambiguous grammar:

{assign} -> {id} = {expr}
{id} -> A | B | C
{expr} -> {expr} + {expr} | {expr} * {expr} | ( {expr} ) | {id}

without using parentheses, what is the meaning of A = B + C * A?
Two parse trees, one with the first expansion of {expr} being the *, the other with the first being the +. Lower down in the tree, the higher its precedence.

No way to uniquely define the meaning of the structure.

6) Operator precedence:
An unambiguous grammar.
First, simple, example where went to {id} was unambiguous, but wrong precedence. Rightmost is lowest in tree, thus highest precedence.
Solution:

{assign} -> {id} = {expr}
{id} -> A | B | C
{expr} -> {expr} + {term} | {term}
{term} -> {term} * {factor} | {factor}
{factor} -> ({expr}) | {id}

show derivation of A = B + C * A on board, and simultaneously draw parse tree.

7) Associativity.
A = B + C + A
does grouping, ordering matter? Based on prev grammar, would do B + C at lowest level, first. Does in cases of large floats with limited precision. Using our unambiguous grammar, we get a left associative interpretation. (Right associative not possible because we do not have {expr} going into two {expr}s. Left associative because recursion all the way to the left. Left recursive. Can make right recursive and thus right associative.

e.g.

{factor} --> {expr} ** {factor} | {expr}
{expr} --> ({expr}) | {id}

Unambiguous if-else
look at if-else definition above. if have {statement} -> {if_statement}, ambiguity. example in C. show the two parse trees. can require begin and end
an unambiguous grammar:
the rule is that an else is matched with nearest previous unmatched then.

{statement} -> {matched} | {unmatched}
{matched} -> if {logic_expr} then {matched} else {matched} | any non-if statement
{unmatched} -> if {logic_expr} then {statement} |
if {logic_expr} then {matched} else {unmatched}

EBNF
{selection} -> if ({expr} ) {statement} [else {statement} ]
brackets for optional component rather than |. Optional recurring via actual curly braces, rather than using recursion:
{ident_list} -> {identifier} {{identifier}}

place options in non-terminal parentheses and separate via |.

Some allow number after right } to indicate upper limit on repetitions, or + to mean 1+.

2006-02-08T11:19:00.000-08:00

LEX and YACC tutorial.
regular expressions and context free grammars

Passing Subroutines to Other Subroutines in FORTRAN

2006-02-07T11:59:00.000-08:00

I hope to mention this in class today. Here is a discussion of how to.

The old-fashioned, non-profile-safe way:
SUBROUTINE SUB (ACTION)
EXTERNAL ACTION
* ...
CALL ACTION (arguments)
* ...
END

SUBROUTINE DEED (args)
* ...
END

* ...
EXTERNAL DEED
CALL SUB (DEED)

Class II - Some Early History - Pseudocodes and FORTRAN

2006-02-01T11:44:00.000-08:00

Machine Code:
benefits: fast
drawback: hard to write. ADD might be 14. Readability. Absolute addressing. Recomputing locations, NOPs for deletions. Gave rise to Assembler, with same benefit.

issues:
floats were simulated. indexing missing - adding var quantity to fixed address.

instead, bec of the von Neumann architecture, since the instruction was in memory, they modified the address portion of the instruction, which was error prone.

thus, subroutines to do floats, and to index. since most of time spent simulating floats, little overhead comparatively for doing other things. Thus, pseudocode interpreters were natural developement.

Short Code
Words are 72 bits, as 12 6-bit bytes. mathematic expressions to be evaluated. Byte-pair values. Some codes:

01 -    06 abs         1n (n+2)nd power
02 )    07 +           2n (n+2)nd root
03 =    08 pause       4n if <= n
04 /    09 (           58 print and tab

implemented as pure interpreted. 50X slower than machine code.

X0 = SQRT(ABS(Y0))
00 X0 03 20 Y0

Homework: How would we write Z0 = CUBEROOT(Y1 * Z0)? How would we write Z0=Y0?

pseudocode - generally used today as english description of code, not always going into specifics of implementation. here, means something else: an instruction diff than that provided by the machine. initially presented as way of saving space in memory, since pseudocode more compact.

Implemented a virtual computer, with own data types and operations, atop an actual computer.

Automation Principle: Automate mechanical, tedious, error-prone activities.
Also, simpler to understand since fewer exceptions, thus Regularity principle: Regular rules, w/o exceptions, are easier to read, learn, describe, implement.

Compiling routines mentioned in book are predecessor to macros.

Book designs a pseudocode, based on following capabilities:
float arithmetic and comparison, indexing, transfer of control, IO.
Syntax: Use numbers since many did not have alphabetic IO, 1 number on each card, each instruction one word. Choose how big addresses to be. Machine has only 2000 locations, so allow 3 decimal digits, and other 1000 for interpreter and program.
Impossible error Principle: rather than detecting errors, may them impossible to commit.

Since address is 3 digits and word is 10 digits, restricted to refer to 3 variables (mem locations), so commands of the form
operator operand1 operand2 dest. +1 means ADD
+1 010 150 200

Orthogonality Principle: they use + and - sign to denote reverse operations. +/-, */ divide, square/squareroot. Two orthogonal, or indep mechanisms: the number = operation, and sign=direct or reverse. two primitives combine in various ways. corollary of regularity principle.
Less to remember.

But orthogonality can go to far.

Similarly, = vs !=, and >= vs <. Need not reverse since just reverse order of operands. no need for positive, negative, zero tests. Can adopt convention that 000 contains 0. Moving: could be implemented via adding to 0, but adding floats is slow. (So do check if adding to 0 and make that a move op!) Chose 0 so that ops have easy to remember vals: move, add, multiply, square. regularity principle. Indexing and loops: x[i] -> z; x -> y[i]
+6 xxx iii zzz
-6 xxx yyy iii

Abstract out code common to all loops. Abstraction principle, corollary of Automation principle. eliminates possible source of error. "Avoid requiring something be stated more than once, factor out recurring pattern."
+7 iii nnn ddd
i = index; n=upper bound; d=location of beginning of loop. this is a do loop.
+8: read. -8 print
+9: stop

memory cards read in program as well as initial data, separated by 10 9's.
pg 20 has sample program.

Construct an interpreter for pseudocode.
read-execute cycle: called fetch-execute cycle before.

decoding by extracting their parts. similar to lexical parsing.
dest := abs(instruction) mod 1000

then, based on sign and instruction:

if sign is + then
do case op of:
0: move;
1: add;
...
if sign is - then
do case op of
0: // op if have negative 0
1: subtract;

etc.

Computational instructions:
multiply:
data[dest] := floating_product(Data[operand1], Data[operand2])

Test equality:
if floating equality (Data[operand1], Data[operand2]) then IP:=dest

Debugging:
Add to fetch-execute cycle a print of IP and the contents at IP

Statement Labels
As mentioned above, inserts into code shifts everything over.
Labeling Principle: Do not require the user to know absolute pos of item in a list, but rather associate labels with any pos that must be referenced elsewhere.

-7 0LL 000 000

this binds a symbolic label to absolute position.

Thus, equality test becomes
+4 xxx yyy 0LL

but then end up scanning program for the labels. can make label table instead.

By extension, symbol table for vars. In the data section:
+0 sss nnn 000
+d ddd ddd ddd

+0 666 150 000
+0 000 000 001
inits a 150 num array to 1s

This binds the symbol to the location at load time. And loader takes care of storage allocation, instead of having to initialize them all via cards like in the past.

+6 666 111 222
V222 := V666[V111]

Can check type info in symbol table to avoid out of bound errors.
Security Principle:
No prog that violates the def of language or intended structure should escape detection.

Extend to symbolic pseudo-code. Symbols for vars, ops.

To allow symbolic, look up ops and vars on symbol table and replace them with actual values, and then interpret. (Alteratively, could have interp directly.) Thus, first translation then interpretation.

In sum, pseudocodes provide virtual computer, which was more regular and at a higher level. Increased security, allow debugging such as traces (and breakpoints).

FORTRAN
And the IBM 704.
The engineer-coder bottleneck. On other hand, speed of execution an issue.
The IBM 704 developed together with the language, thus tightly integrated. IBM 704 supported floats directly, so no need for simulation, thus speed issue against pseudocodes, thus compiled language.
Skip features in language which not quickly produced in hardware. Thus, limits on statements, on control structures, no recursion.

FORTRAN 0: A design document. spoke of efficiency of machine code with ease of pseudocode. "FORTRAN would elim coding errors, thus little syntax error checking."

Environment: Computers slow, small, unreliable. Used primarily of scientific applications. No existing efficient way to program computers. High cost of computers vs. programmers.

FORTRAN I: Implementation introducing realities. Features: IO formatting, var names 6 chars, user defined subroutines, weird mathematical IF statement. DO Loop.
From Wikipedia:

10 dim i
20 i = 0
30 i = i + 1
40 if i <> 10 then goto 90
50 if i = 10 then goto 70
60 goto 30
70 print "Program Completed."
80 end
90 print i & " squared = " & i * i
100 goto 30

Here is the same code written using control structures.

dim i
for i = 1 to 10
   print i & " squared = " & square(i)
next
print "Program Completed."

function square(i)
   square = i * i
end function

No > in charset, 704 had 3 way mathematic branch instruction, which replaced FORTRAN 0's IF.
IF (arithmetic expression) N1, N2, N3

DO Loop. Was posttest rather than pretest because of 704's architecture, as well as other control statements.
No data typing. I_, J_, K_, L_, M_ are ints, rest are floats. because of scientific domain.

largest part of time spent developing spend optimizing.

FORTRAN II:
besides other features, independent compilation of subs. otherwise would crash before compiling, limiting programs to 300 - 400 lines.

FORTRAN IV:
Explicit type declarations. Why is this important? reduce errors by type checking, do not introduce new vars erroneously, expand set of names.
Logical IF construct.
Pass subs as parameters to subs.
How would we do this in C++? Digression into complex declarations in general.

Homework Assignment to print above avg nums in array.

A web site about development of FORTRAN - what features were added.

FORTRAN 77: adds char string handling, logical loop control statements (rather than just for loops), IF with optional ELSE.

FORTRAN 90: major differences. names up to 31 chars. ! as comment. collection of matrix functions: e.g. MATMUL, DOTPRODUCT, TRANSPOSE, MAXVAL, MINVAL, PRODUCT, SUM. User defined data type called "derived type." Dynamic allocation of these types, and dynamic allocation and deallocation of arrays. Vs. prev. only had static data. Select case. Exit = break, cycle = continue of C; recursion. Modules (with public and private data and methods). specification of numeric precision, ";" as statement separator. Lines up to 132 chars in length.
While array processing: A= B*Sin(A)
deprecating features.

FORTRAN 95: Minor changes. Forall, initialization of pointers, and of "derived types."
Also, NULL function, automatic garbage collection.

FORTRAN 2003:
Interop with C, international - allow , or . for decimal point. Access to command line arguments, environmental vars, procedure pointers, IO enhancements, OOP support, parameterized derived types, etc.

Some linear algebra and graph algorithm introduction. Describe the algorithm.

Next Time: Names and Binding, in more than just FORTRAN.

Class II - Some FORTRAN Basics - Assignment

2006-02-01T10:13:00.000-08:00

This ftp site has a bunch of demo Fortran programs. For each Fortran file I specify, read each program to get a feel for what it does, and then copy the text of the file, compile it, and execute it.

In each case, not every line is indented 6 spaces, so either make sure that each line is indented at least 6 spaces, or else save as *.f90. Otherwise, you will get a syntax error.

1) A Kind is an integer specification of data type for primitives, in general matching the sizeof the data type in bytes. Read this webpage for more details.

Compile and run this program.

2) Data types can be defined with the keyword TYPE. Members can be accessed with %.
Compile and run this program, which creates and uses a derived type for intervals. As requested in the comment, change the program so that it prints the interval length instead.

Compile and run this program which demonstrates nested types.

3) Pointers:
Read this document about FORTRAN pointers and array pointers. Then, compile and run this program. Modify the program as suggested in the comments and see what happens.

4) Do Loop and Cycle
This example demonstrates a do loop, equivalent to a for loop. Cycle is the equivalent of continue in C++.

5) Nested do loops with names, in this example.
Exit is equivalent to break. Note that we can break out of multiple levels of loop because of the named loops. This is similar to the labelled breaks in Java.

6) Select Case statement, as we have in VB6. Note this case statement works for ranges. Example here and here.

7) Functions.
Example here. Note that just as in C, the types of parameters are not specified in the declaration, but just the names. The types are specified subsequently. LOGICAL means boolean. Note the INTENT keyword, which is used to specify that these parameters are being passed in but not out of the program. Note that the function name is also assigned a type, = to the return type, and that assigning to the function name has the effect of specifying the return value. This is also found in VB6.

8) Arrays.
Note that the : character is used to specify a range. 2:5 means 2 through 5. Either side can be optional. The , character separates indexes when dealing with a matrix. Thus, in C++:
a[7][3]
would be written a[7,3] in FORTRAN
Try out this example and compare the source with the output carefully.

9) Intended Assignments:
A) Write a program that takes N as input, reads in N numbers into an array, and prints any number A[i] which is larger than the average.
B) Take advantage of the built in matrix manipulation functions in FORTRAN to write a program that takes in N, the size of a directed graph, followed by a series of edges, terminated by -1. Compute whether the graph is strongly connected.
C) Take advantage of the full capabilities of FORTRAN 90. Write a program that will take in a series of numbers, terminates by -1, and stores them in a binary search tree. Then take another series of numbers as input and output whether the numbers are in the binary tree. (All you need implement is insert and search).

Starting FORTRAN

2006-01-31T11:06:00.000-08:00

A free Fortran compiler: G95.

Download and install the binary under "Self-extracting Windows x86." Install to the C:\g95 directory.

Now, make your first program, to print 'Hello World' ten times. Spacing matters:


     PROGRAM HELLO
     DO 10, I=1,10
     PRINT *,'Hello World'
  10 CONTINUE
     STOP
     END

save this file as hello.f in the c:\g95\bin directory.
from the c:\g95\bin directory, type the following:
g95 hello.f

The compiler will create hello.exe in the same directory. Run it.

Now edit the file and create a syntax error. Change * to *a. Try to recompile and see what happens.

Class I - Homework

2006-01-30T11:58:00.000-08:00

Buy the book
Send me an email. JoshWaxman {at} gmail [dot] com.
implement Pascal string in C or C++
write a program that uses logical XOR
Read the first chapter (pg. 9-36)
The Regularity principle, mentioned on pg. 11 in the book, is similar to what concept mentioned in class?
Download and install the G95 Fortran compiler, and write and run the hello world program.

Class I - Preliminaries

2006-01-30T10:29:00.000-08:00

Why?

increased capacity to express ideas.
what can say depends on vocabulary, and prog. language limits what can express. by knowing other langs, know more lang constructs. These language constructs can be similated. e.g. Pascal strings. first homework assignment.
ability to choose appropriate language for the task. else fall back on what you know.
ability to learn new languages. if know data abstraction, easier constructing abstract data types in Java. similar to natural lang - better know grammar of own lang, easier to learn other language. also, learning second lang tells you more about your own language. e.g. logical XOR. second homework assignment.
better understand significance of implementation.

helps understand why designed as is --> better use of the language. know which constructs to use.
figure out bugs
understanding efficiency. how recursion works -> why so slow

Ability to design new languages. input format language.
enhancement of computing via natural selection. e.g. Algol 60 better control statements and other features than Fortran, but difficult to read and understand. Programmers did not appreciate features of Algol 60.

Programming domains -- produce languages that specifically suit it.

Scientific applications: deal with floating point arithmetic, simple data structures. Most common: arrays, matrices; most common control structures: loops. Competition: assembly, so needed to be fast. Fortran, Algol 60.
Business Applications: produce reports, precise ways of describing and storing decimal numbers and chars, decimal arithmetic ops. COBOL. Also, spreadsheet and database systems.
AI: Symbolic rather than numeric computation. Symbols, consisting of names instead of nums, are manipulated. Linked lists more convenient than arrays for this purpose. More flexibility required -- e.g. to create and run code segments during execution. LISP - functional language. Prolog - Logic programming.
Systems Programming: The OS and programming support tools = systems software. Fast execution (since always running) + low level features. Made special languages for the particular systems: IBM: PL/S, dialect of PL/I. Digital made BLISS, language just above assembly. Burroughs: extended ALGOL. UNIX written in C so easy to port - low level, efficient, easy to shoot self in foot.
Scripting Languages: Batch programming. DOS batch? sh = shell=calls to system subprograms. awk = for report generation, then became more general purpose. Perl began as sh + awk.
tcl - scripting language; tk - method of building X-Window applications.
Javascript.
Other special purpose languages. RPG - produce business reports, GPSS - systems simulation. Inform - Zork type games.

Lang Evaluation Criteria - What makes a language "good"

Readability - ability to be understood - in terms of problem domain. use ill-suited lang, will be unreadable.

Simplicity

small vs. large num of lang components - learn subset.
feature multiplicity: + 1 vs. ++, which have slightly diff meanings
operator overloading, if misused. + on arrays to return scalar sum rather than vector sum.
but simplicity can go too far. consider assembly. no control statements, complex data structures.

Orthogonality

small # primitives combined in small # of ways, consistently
e.g. pointers should point to any type.
VAX:
A Reg1, memory_cell
AR Reg1, Reg2

IBM:
ADDL operand_1, operand2
i before e, except after c. confusing
lack of orthogonality in C: can return structs but not arrays. structs cannot hold void or struct of same type. (not true in C#, Java) Array el cannot be void or a function. (but can be func pointer) a + b where A is a pointer does different things depending on pointer type.
Too much orthogonality. ALGOL 68. conditionals can appear on left side of assignment, also declarations, etc., so long as result is location.
Functional vs. Imperative lang. Functional, such as LISP - single construct. But efficiency problems. (I would add also readability/writability)

Control statements: gotos vs. while, for loops. spaghetti code. how to restrict: near targets, limited number, always precede targets except to form loops.
Data types and structures:

bool type in C++. timeout = 1 vs true.
Lack of structures in FORTRAN 77, req parallel arrays and use same subscript.

Syntax:

identifier forms. Basic: E or E3.
keywords that can identify. some lang, like FORTRAN 90, allows these to be used as var names as well.
end vs end if, end loop, {}
code self documenting such that semantics follows syntax. static has 2 or 3 meanings in C, C++. names such as "grep" requires special knowledge to understand.

Writability - how easy to code solution for given problem domain

Simplicity, Orthogonality = less programmer need know, since limited constructs and few limits on how to combine them
Abstraction - allow definition and use of complicated structures and ops allowing details to be ignored. increases naturalness of expression. e.g. function, rather than repeating commands each time with diff variables, creating clutter. data abstraction: example above of parallel arrays. or how to implement a binary tree in fortran vs. in C.

Expressivity.

to make less cumbersome. count++. and then to do short circuit (automatic in C), for loop. syntactic sugar.

Reliability - performs to specs under all conditions

more important in specific domains - control airplanes, medical equipment, etc., but in general.
type checking - C doesn't do it. C++ does. can cause errors
exception handling - Ada, C++, Java.
Aliasing - two items refer to same entity. can cause problems. but also powerful language feature. references, pointers, point to same location. unions.
Readability/Writability. unnaturalness leads to errors. also need maintain/modify.

Cost - diff definitions

training programmers, paying programmers to write it, time to compile, time to execute (and optimize diff things), price of the compiler/interpreter - Java, cost of poor reliability in human terms and in further business, cost of maintaining.

Other ways of evaluating langs exist. portability, generality (to wide range of applications), etc. and depends on perspective.

Influences on Lang Design:
Computer Architecture: von Neumann, variables model memory cells, assignment models piping data to CPU, and iteration is most efficient, because instructions stored in memory in adjacent locations. Recursion, functional langs inefficient.
Programming Methodologies: cost shift from hardware -> software.
type checking problems, lack of control statements.
then, more from process oriented to data oriented - data structures, then object oriented programming.

Language Categories:
Imperative, functional, Logic, Object oriented.
Logic: rule based lang. instead of specifying exactly how things are done algorithmically, rules specified in any order and lang implementation system chooses execution order. Prolog.

Implementation Methods:
cocentric circle diagram - bare machine, Macroinstruction interpreter, OS, C++ compiler, FORTRAN, C, Ada compiler, Assembler, Lisp interpreter, etc., all providing virtual language machine. OS command interpreter.
A) Compilation. diagram
Source program
lexical analyzer ---lexical units--> Syntax analyzer
Syntax analyzer --- parse trees ---> intermediate code generator/semantic analyzer

both lex and syn output to symbol table, which feeds the intermediate code generator/semantic analyzer as well as the code generator

intermediate code generator/semantic analyzer --intermediate code-->code generator
code generator --machine language-->computer
computer takes this and input and generates results.

Linking step to link to system calls (addresses of functions)
Based on von Neumann architechture, a fetch-execute cycle

initialize program counter
repeat forever
fetch instruction pointed to by program counter
program counter++
decode instruction
execute instruction
end repeat

von Neumann bottleneck a result of having to transfer instructions via the bus to the CPU.

benefits: speed
examples: C, FORTRAN.

B) Pure interpretation.
No compiling. benefits - symbol table present. errors easily found and can give line number. can fix. Examples: Lisp, APL, batch files. C, C++, debug mode. Source program and input data go directly to the interpreter.
drawbacks: slow.

C) Hybrid. All steps up to intermediate code, preserve symbol table, but run the intermediate code. Java runs in both hybrid and full compile mode.

The Book For This Course

2006-01-25T09:17:00.000-08:00

The book for this course is Principles of Programming Languages: Design, Evaluation, and Implementation, by Bruce J MacLennan. The ISBN number for the book is 0195113063.

The book is available for purchase and partial viewing at a number of locations. It will probably cost about $25, plus shipping and handling.

books.google.com has the book scanned, and has a bunch of links to sellers.
Amazon.com also has the book scanned, and offers the book for purchase.
Alibris.com offers the book used, and seems to have the best price, but for older editions of the book.