CSC 253 Fall 2016

CSC 253/453 Dynamic Language & Software Development

Prerequisites: CSC 252 and CSC 254 are required for CSC 453 and recommended for others. Familiarity with a dynamic programming language such as Python.
Crosslisted: TCS 453

This course studies dynamically-typed programming languages and modular software development. Topics include principles and practice of modular design, functional and object-oriented programming techniques, software engineering concepts, software correctness and reliability, programming tools, and design examples. Ruby is used as the main instruction language. The lessons complement those in traditional compilers and programming languages courses, which focus mainly on statically-typed languages and individual algorithms rather than system design. A significant portion of the assignment is a group project.

Teaching Staff and office hours:  Prof. Chen Ding, Fridays 11am to 12pm in CSB 720; John Jacobs, Thursdays 3:30-4:30pm in CSB 720.

Preparation (before first class):

“No Silver Bullet — Essence and Accidents of Software Engineering” is a classic paper on software engineering written by Turing Award winner Fred Brooks in 1986.  Read the paper (available here if accessed inside the UR network) especially pages 3 to 5 on the “essential difficulties” of software development.

“A former member of the SD10 Panel on Computing in Support of Battle Management explains why he believes the ‘star wars’ effort will not achieve its stated goals.”  Read the paper (available here if accessed inside the UR network) pages 2 to 4 the section titled “Why software is unreliable.”  Which of the “essential difficulties” was Parnas discussing?

More background of this debate, detailed rationales and an illuminating discussion of the ethical issues can be found in another article of Parnas: “SDI: A Violation of Professional Responsibility”.  The article does not seem to have a free version online, but you can read it by borrowing the book “Software Fundamentals” (included as Chapter 27) from the textbook reserve for CSC 253/453 at the Carlson Library.  The lease is two hours.

Further material will be distributed through the Blackboard web site  for students who have registered.  Contact the instructor if you have problem accessing the site.

Textbooks:
Design patterns in Ruby
Author: Olsen, Russ.
Imprint: Upper Saddle River, NJ : Addison-Wesley, c2008.
On Reserve at: Internet

Fundamentals of software engineering
Author: Ghezzi, Carlo.
Imprint: Upper Saddle River, N.J. : Prentice Hall, c2003.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.758 .G47 2003

Object-oriented and classical software engineering
Author: Schach, Stephen R.
Imprint: New York : McGraw-Hill, c2011.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.758 .S318 2011

PROGRAMMING LANGUAGE PRAGMATICS, 3rd ed
Author: Scott, Michael L.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: CRL PersCpy

Software fundamentals : collected papers by David L. Parnas
Author: Parnas, David Lorge.
Imprint: Boston : Addison-Wesley, 2001.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.754 .P365 2001

Programming Languages: Application and Interpretation (http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/)
Copyright © 2003-07, Shriram Krishnamurthi
(Also see Prof. Findler’s course EECS 321 at https://www.eecs.northwestern.edu/~robby/courses/)

Topics:

schedule

schedule.numbers-2016 topics

 

Does Real Locality Exist?

After the post on computational locality, it is interesting to examine our understanding of physical locality.  There is a fascinating storyline in the history of physics.

Einstein is one of the greatest physicists.  However, he was always troubled by quantum mechanics whose results, unlike Newton mechanics, are inherently probabilistic rather than deterministic.   For example, his quote “God does not play dice with the universe” was actually a direct criticism.

The discovery of two-particle quantum entanglement gave him a chance to formulate his objection precisely.  In 1935, Einstein, Boris Podolsky and Nathan Rosen distributed the so-called EPR paradox.  They laid out four premises of a physics theory:

[Greenberger et al. 1990] state in EPR’s words.

  • (i) Perfect correlation: If the spins of particles 1 and 2 are measured along the same direction, then with certainty the outcomes will be found to be opposite.
  • (ii) Locality: “Since at the time the two systems no longer interact, no real change can take place in the second system in consequence of anything that may be done to the first system.”
  • (iii) Reality: “If, without in any way disturbing a system, we can predict with certainty the value of a physical quantity, then there exists an element of physical reality corresponding to this physical quantity.”
  • (iv) Completeness: “Every element of the physical reality must have a counterpart in the [complete] physical theory.”

For a two-particle entanglement, the measurement of particle 1 can cause no real change in particle 2.   Until the measurement, the states of particles 1 and 2 have no definite values from the theory of quantum mechanics.  Therefore, as a theory quantum mechanics is incomplete.

These objections were unresolved (and largely ignored) by physicists in the next fifty years.  A series of studies on Bell Inequality were made, but the experimental setups were open to criticism.

In late 1980s, researchers at University of Rochester especially Leonard Mandel, Professor of Physics and Optics, and his students followed on their studies on the quantum properties of light and invented a technique called parametric down-conversion to produce entangled photons.

Daniel Greenberger, while visitingVienna with Anton Zeilinger, found that a perfect correlation among three particles was enough to disprove EPR.  Michael Horne, back at Boston, discovered Mandel’s two-particle interference design based on a “folded diamond. ”

The paper by Greenberger et al. was published in 1990.  It shows that for 3 or more particle entanglement, the four EPR premises would derive contradictory results.  No theory that meets these four premises can explain the perfect correlation in such entanglements.  In the proof by Greenberger et al., (Section III, slightly more than 1 page), “the manipulation of an additional degree of freedom is essential to the exhibition of a contradiction.”

The contradiction shows that either locality or reality assumptions do not hold.  The combination of the two is now called “local realism.”

Scully et al. wrote that “In an ingenious experiment with [Zhe-Yu] Ou, Leonard utilized polarization entanglement for photon pairs produced in down conversion to achieve a violation of Bell’s inequality (i.e., local realism).”

I first heard about the story from the book by Aczel and taught the 1990 paper in the opening lecture of a graduate seminar in Spring 2005 on Modeling and Improving Large-Scale Program Behavior.

References

Greenberger, Daniel M., et al. “Bell’s theorem without inequalities.” Am. J. Phys 58.12 (1990): 1131-1143.

ROBERT J. SCULLY, MARLAN O. SCULLY, AND H. JEFF KIMBLE, “Leonard Mandel,” Biographical Memoirs: Volume 87,  The National Academies Press  (2005)

Zhe-Yu Ou and Leonard Mandel. Violation of Bell’s inequality and classical probability in a two-photon correlation experiment. Phys. Rev. Lett.61(1988):50.

Amir D. Aczel, Entanglement: The Greatest Mystery in Physics.  Random House, Inc. (2002)