Previous
[ 01.html ]
Preparation
Study Chapter 1 of the text and prepare some notes and
at least one question you need to ask on it.
Topics
Motivation
Language Research and Computer Science
Theoretical Language Research
- Abstraction
- Features of a good language
Experimentation
. . . . . . . . . ( end of section Topics) <<Contents | Index>>
Questions
How does a data structure help the translation of postfix to prefix (page 5)
One of the standard results from compiler theory and language theory
(push-down automaton >= finite-state automaton)
is that a stack (Last-In, First-Out) is very helpful for holding
intermediate results when translating between different kinds of
expressions. Sadly FORTRAN I predated this insight and had no
stack data structure.... just arrays of 1, 2, or 3 dimensions.
In fact the early FORTRAN compilers attempted to compiler expressions
without using a stack as well....
An alternative (more complex) data structure would be a tree structure.
Worse it is not easy to add a stack (or any other data structure) to the
early FORTRANs.
What are the features of a good programming language
We brainstormed the following list (with my comment in parentheses):
- Should be like a natural language (an example was COBOL).
- Object Orientation (See Java later...)
- Fast Compilation (or a good interpreter).
- It would be nice to switch languages (I have a vague memory of COBOL doing this.
This is really a topic for a term paper or thesis).
- Portable (See Java later: Write Once, Debug Everywhere)
- Reusable (A long term dream... each technology has helped a little bit... with Aspect Oriented Programming being the latest great thing...)
- Ease of use: need English and math. (Expressions have been part of all languages but LOGO (I think)).
- Readability
- Library ( Libraries -- plus a tool for accessing them).
- Concise ( a goal but APL tends to show that one can be too
Concise... follow links on
[ APL in resources ]
to see some example "one line" programs: "guess what this does!").
- No Overloading (excellent idea but in the extreme it means that one needs
to distinguish floating point addition from int addition).
- Self writing programs (a true dream but a long way off. Seeing there exist
problems that can not be solved by a program it is asking a lot of
a compiler to solve them. Intractability raises the problem that
automatically generated code can be very inefficient.)
I also pointed out that languages succeed not because of their merits
but because they are given away free until they have a large user
base. There is little correlation between theoretical language quality
and success in the market place: the price has to be right first!
Conclusions
- Take any feature to extremes and the language gets worse!
- No language is really perfect.
- Pick your defects!
- You can not argue from success to quality.
Can you define Syntax and Semantics
Syntax defines the form of a language. Syntax rules tell you
what is legal in the language.
Semantics define what the syntactically correct things mean.
They are rules that reject some syntactically OK statements as
meaningless..... but provide a way to figure out what the rest mean.
For example:
Net
- Syntax -- a number is a sequence of digits.
- number::= digit | number digit.
- For example: "123".
- Semantics -- the value of a number n followed by a digit d is 10 times
the value of n plus the value of d:A
- value(d) = d - value('0').
- value(n d) = 10*value(n) + value(d).
(End of Net)
More later.
Can an algorithm or program test if a problem is tractable or not.
No!
Firstly, we haven't proved that the boundary between the tractable and
the intractable problems exist. We may find a clever way to make
any program run in polynomial time. However, this is rather unlikely.
Notice that being able to spot one of the 300 know intractable problems
and 4000 tractable ones does not mean you have solved the problem.
What is needed is a decision procedure that always makes the
correct diagnosis.
Notice that it is similarly NOT possible to spot if an unknown problem
is unsolvable (or solvable).
Didn't Object-Orientation Help Abstraction and Information hiding
Yes.... but less than you might expect.
We had data abstraction (hiding the actual
data behind public operations) long before we had objects in most languages.
Ada, C, Pascal, Modular, etc. etc. all had ways of packaging some data
and attaching operations to it, so that the original data was private
and hidden, but the operations public and visible.
Object orientation adds one very nice feature to data abstraction: you
can access an object by a pointer and its behavior depends on the object
not on the type of the pointer. This is called polymorphism.
Can you define what is needed in the laboratory today
Net
- In general must read one character at a time.
- Do NO error checking -- we don't have time and it takes the focus from
mapping input to meaning.
- In C++ you may NOT use 'cin'.... No strstream, no atoi!
- Use
getchar()
to read one character at a time. For example:
int ch;
while( ( ch=getchar() ) != '\n' ){....}
- Construct the answer as long int not an int:
long int result....
- Here is fact worth knowing about C/C++:
if ch is a character containing a digit like '5' for example then
ch-'0'
is the value of the digit in almost all character codes: so
'5'-'0' == 5
- In the second exercise: result becomes a double.
Net
- floating_point_number::= number "." number.
- value( n "." m ) = value(n) + value(m)/10^(-length(m)). -- check!
(End of Net)
- Hint: syntax determines program structure...
(End of Net)
