Select this to skip to main content [CSUSB] >> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CSci620] >> 02 [Source]
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Grading]
Thu Apr 1 16:33:17 PST 2004

Contents


    CSCI620 Session 2

      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

      1. Abstraction
      2. 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

      1. Syntax -- a number is a sequence of digits.
      2. number::= digit | number digit.
      3. For example: "123".

      4. 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
      5. value(d) = d - value('0').
      6. 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
      1. In general must read one character at a time.
      2. Do NO error checking -- we don't have time and it takes the focus from mapping input to meaning.
      3. In C++ you may NOT use 'cin'.... No strstream, no atoi!
      4. Use
         		getchar()
        to read one character at a time. For example:
         		int ch;
         		while( ( ch=getchar() ) != '\n' ){....}
      5. Construct the answer as long int not an int:
         		long int result....

      6. 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

      7. In the second exercise: result becomes a double.
        Net
        1. floating_point_number::= number "." number.
        2. value( n "." m ) = value(n) + value(m)/10^(-length(m)). -- check!

        (End of Net)

      8. Hint: syntax determines program structure...

      (End of Net)

    . . . . . . . . . ( end of section Questions) <<Contents | Index>>

    Exercises

    Page 13 exercise 3 -- iff time. No time....

    Laboratory 2

    Page 13: Exercises 1 and 2.

    My answers are in [ lab01a.cpp ] and [ lab01b.cpp ] , enjoy.

    Next

    Study chapter 2 on syntax and prepare a set of notes including at least one question to ask in class. Outline will be posted [ 03.html ] ASAP.

. . . . . . . . . ( end of section CSCI620 Session 2) <<Contents | Index>>

Glossary

  • BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
  • EBNF::="Extended " BNF.
  • HTML::= "HyperText Markup Language", used on the WWW.
  • HTML_page::syntax= "<HTML>" head body.
  • Java::="An " OO " Language from Sun".
  • LISP::= "LISt Processing Language".
  • LRM::="Language Reference Manual".
  • OO::="Object-Oriented".
  • Prolog::="Programming in Logic".
  • TBA::="To Be Announced".
  • UML::="Unified Modeling Language".
  • URL::=Universal_Resource_Locator,
  • Universal_Resource_Locator::syntax= protocol ":" location, where
    Net
    1. protocol::= "http" | "ftp" | "mailto" | ... ,
    2. location::= O( "//" host) O(pathname).

    (End of Net)
  • WWW::= See http://www.csci.csusb.edu/dick/cs620/, index to web site for this class.
  • XBNF::="eXtreme" BNF, developed by the teacher from EBNF, designed to ASCII input of suntax, semantics, and other formal specifications.


    Formulae and Definitions in Alphabetical Order