vote for meeting time and first paper
Constantin Berzan
Please vote for a regular meeting time for the reading group:
http://doodle.com/uznvau6ry34ykrmn
and for the first paper to read:
http://doodle.com/9pqf4rd8uesxndgf
The abstracts of the papers are attached below.
Our first meeting will probably be during the week of October 3.
Have a great weekend!
-Constantin
==============================================================================
Functional Reactive Animation [11p]
Elliott, Hudak (1997)
Abstract:
Fran (Functional Reactive Animation) is a collection of data types and
functions for composing richly interactive, multimedia animations. The
key ideas in Fran are its notions of behaviors and events. Behaviors
are time-varying, reactive values, while events are sets of
arbitrarily complex conditions, carrying possibly rich information.
Most traditional values can be treated as behaviors, and when images
are thus treated, they become animations. Although these notions are
captured as data types rather than a programming language, we provide
them with a denotational semantics, including a proper treatment of
real time, to guide reasoning and implementation. A method to
effectively and efficiently perform event detection using interval
analysis is also described, which relies on the partial information
structure on the domain of event times. Fran has been implemented in
Hugs, yielding surprisingly good performance for an interpreter-based
system. Several examples are given, including the ability to describe
physical phenomena involving gravity, springs, velocity, acceleration,
etc. using ordinary differential equations.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.7696&rep=rep1&type=pdf
==============================================================================
Proof of a Program: Find [17p]
Hoare; 1989
Abstract:
A proof is given of the correctness of the algorithm Find. First, an
informal description is given of the purpose of the program and the
method used. A systematic technique is described for constructing the
program proof during the process of coding it, in such a way as to
prevent the intrusion of logical errors. The proof of termination is
treated as a separate exercise. Finally, some conclusions relating to
general programming methodology are drawn.
http://portal.acm.org/citation.cfm?id=63445 (website of the book in
which the essay is contained)
==============================================================================
Dynamo: Amazon’s Highly Available Key-value Store [16p]
DeCandia and other folks from Amazon; 2007
Abstract:
Reliability at massive scale is one of the biggest challenges we face
at Amazon.com, one of the largest e-commerce operations in the world;
even the slightest outage has significant financial consequences and
impacts customer trust. The Amazon.com platform, which provides
services for many web sites worldwide, is implemented on top of an
infrastructure of tens of thousands of servers and network components
located in many datacenters around the world. At this scale, small and
large components fail continuously and the way persistent state is
managed in the face of these failures drives the reliability and
scalability of the software systems.
This paper presents the design and implementation of Dynamo, a highly
available key-value storage system that some of Amazon's core services
use to provide an "always-on" experience. To achieve this level of
availability, Dynamo sacrifices consistency under certain failure
scenarios. It makes extensive use of object versioning and
application-assisted conflict resolution in a manner that provides a
novel interface for developers to use.
http://portal.acm.org/citation.cfm?id=1294281
==============================================================================
Convex partitions with 2-edge connected dual graphs [16p]
Al-Jubeh, Hoffmann, Ishaque, Souvaine, Tóth (Tufts folks!); 2009
Abstract:
It is shown that for every finite set of disjoint convex polygonal
obstacles in the plane, with a total of <em>n</em> vertices, the free
space around the obstacles can be partitioned into open convex cells
whose dual graph (defined below) is 2-edge connected. Intuitively,
every edge of the dual graph corresponds to a pair of adjacent cells
that are both incident to the same vertex.
Aichholzer et al. recently conjectured that given an even number of
line-segment obstacles, one can construct a convex partition by
successively extending the segments along their supporting lines such
that the dual graph is the union of two edge-disjoint spanning trees.
Here we present a counterexamples to this conjecture, with n disjoint
line segments for any n >= 15, such that the dual graph of any convex
partition constructed by this method has a <em>bridge</em> edge, and
thus the dual graph cannot be partitioned into two spanning trees.
http://www.eecs.tufts.edu/~mishaq01/JOCO-2010.pdf
==============================================================================
Plan 9 from Bell Labs [9p]
Pike, Presotto, Thompson, Trickey; 1995
Abstract:
Plan 9 is a distributed computing environment. It is assembled from
separate machines acting as CPU servers, file servers, and terminals.
The pieces are connected by a single file-oriented protocol and local
name space operations. By building the system from distinct,
specialised components rather than from similar general-purpose
components, Plan 9 achieves levels of efficiency, security,
simplicity, and reliability seldom realised in other distributed
systems. This paper discusses the building blocks, interconnections,
and conventions of Plan 9.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.8671&rep=rep1&type=pdf
==============================================================================
Induction of Decision Trees [26p]
Quinlan; 1986
Abstract:
The technology for building knowledge-based systems by inductive
inference from examples has been demonstrated successfully in several
practical applications. This paper summarizes an approach to
synthesizing decision trees that has been used in a variety of
systems, and it describes one such system, ID3, in detail. Results
from recent studies show ways in which the methodology can be modified
to deal with information that is noisy and/or incomplete. A reported
shortcoming of the basic algorithm is discussed and two means of
overcoming it are compared. The paper concludes with illustrations of
current research directions.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.167.3624&rep=rep1&type=pdf
==============================================================================
The Hardness of Cache-Conscious Data Placement [11p]
Petrank, Rawitz, 2002
Abstract:
The growing gap between the speed of memory access and cache access
has made cache misses an in uential factor in program eciency. Much
eort has been spent recently on reducing the number of cache misses
during program run. This eort includes wise rearranging of program
code, cache-conscious data placement, and algorithmic modications that
improve the program cache behavior. In this work we investigate the
complexity of nding the optimal placement of objects (or code) in the
memory, in the sense that this placement reduces the cache misses to
the minimum. We show that this problem is one of the toughest amongst
the interesting algorithmic problems in computer science. In
particular, suppose one is given a sequence of memory accesses and one
has to place the data in the memory so as to minimize the number of
cache misses for this sequence. We show that if P != NP, then one
cannot eciently approximate the optimal solution even up to a very
liberal approximation ratio. Thus, this problem joins the small family
of extremely inapproximable optimization problems. The other two
famous members in this family are minimum coloring and maximum clique.
http://www.cs.tufts.edu/~sguyer/classes/comp150-2006/papers/petrank02hardness.pdf
==============================================================================
On the translation of languages from left to right [33p]
Knuth, 1965
Abstract:
There has been much recent interest in languages whose grammar is
sufficiently simple that an efficient left-to-right parsing algorithm
can be mechanically produced from the grammar. In this paper, we
define LR(k) grammars, which are perhaps the most general ones of this
type, and they provide the basis for understanding all of the special
tricks which have been used in the construction of parsing algorithms
for languages with simple structure, e.g. algebraic languages. We give
algorithms for deciding if a given grammar satisfies the LR (k)
condition, for given k, and also give methods for generating
recognizers for LR(k) grammars. It is shown that the problem of
whether or not a grammar is LR(k) for some k is undecidable, and the
paper concludes by establishing various connections between LR(k)
grammars and deterministic languages. In particular, the LR(]c)
condition is a natural analogue, for grammars, of the deterministic
condition, for languages.
http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf
==============================================================================
Program development by stepwise refinement [13p]
Wirth, 1971
Abstract:
The creative activity of programming - to be distinguished from coding
- is usually taught by examples serving to exhibit certain techniques.
It is here considered as a sequence of design decisions concerning the
decomposition of tasks into subtasks and of data into data structures.
The process of successive refinement of specifications is illustrated
by a short but nontrivial example, from which a number of conclusions
are drawn regarding the art and the instruction of programming.
http://www.ehu.es/~ljrf/AED/2010/practicas/lenguaje_C/StepwiseRefinement_Wirth.pdf
==============================================================================
Garbage Collection in an Uncooperative Environment [17p]
Boehm, Weiser, 1988
Abstract:
We describe a technique for storage allocation and garbage collection
in the absence of significant cooperation from the code using the
allocator. This limits garbage collection overhead to the time
actually required for garbage collection. In particular, application
programs that rarely or never make use of the collector no longer
encounter a substantial performance penalty. This approach greatly
simplifies the implementation of languages supporting garbage
collection. It further allows conventional compilers to be used with a
garbage collector, either as the primary means of storage reclamation,
or as a debugging tool.
Our approach has two potential disadvantages. First, some garbage may
fail to be reclaimed. Second, we use a ‘‘stop and collect’’ approach,
thus making the strategy unsuitable for applications with severe
real-time constraints. We argue that the first problem is, to some
extent, inherent in any garbage collection system. Furthermore, based
on our experience, it is usually not significant in practice. In spite
of the second problem, we have had favorable experiences with
interactive applications, including some that use a heap of several
megabytes.
http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/preprint.pdf
==============================================================================
Automated re-invention of six patented optimal lens systems using
genetic programming [8p]
Koza, 2005
Abstract:
This paper describes how genetic programming was used as an invention
machine to automatically synthesize complete designs for six optical
lens systems that duplicated the functionality of previously patented
lens systems. The automatic synthesis was done "from scratch"-that is,
without starting from a pre-existing good design and without
pre-specifying the number of lenses, the physical layout of the
lenses, the numerical parameters of the lenses, or the non-numerical
parameters of the lenses. One of the six genetically evolved lens
systems infringed a previously issued patent; three contained many of
the essential features of the patents, without infringing; and the
others were non-infringing novel designs that duplicated (or improved
upon) the performance specifications contained in the patents. One of
the six patents was issued in the 21st-century. The six designs were
created in a substantially similar and routine way, suggesting that
the approach used may have widespread utility. The genetically evolved
designs are instances of human-competitive results produced by genetic
programming in the field of optical design.
http://portal.acm.org/citation.cfm?id=1068337
==============================================================================
Demonstrating the Evolution of Complex Genetic Representations: An
Evolution of Artificial Plants [12p]
Toussaint, 2003
Abstract:
A common idea is that complex evolutionary adaptation is enabled by
complex genetic representations of phenotypic traits. This paper
demonstrates how, according to a recently developed theory, genetic
representations can self-adapt in favor of evolvability, i.e., the
chance of adaptive mutations. The key for the adaptability of genetic
representations is neutrality inherent in non-trivial
genotype-phenotype mappings and neutral mutations that allow for
transitions between genetic representations of the same phenotype. We
model an evolution of artificial plants, encoded by grammar-like
genotypes, to demonstrate this theory.
http://www.springerlink.com/content/ad524w1bvpvbjyh7/fulltext.pdf
==============================================================================
You and Your Research
Hamming (transcribed), 1986
At a seminar in the Bell Communications Research Colloquia Series, Dr.
Richard W. Hamming, a Professor at the Naval Postgraduate School in
Monterey, California and a retired Bell Labs scientist, gave a very
interesting and stimulating talk, You and Your Research to an overflow
audience of some 200 Bellcore staff members and visitors at the Morris
Research and Engineering Center on March 7, 1986. This talk centered
on Hamming's observations and research on the question ``Why do so few
scientists make significant contributions and so many are forgotten in
the long run?'' From his more than forty years of experience, thirty
of which were at Bell Laboratories, he has made a number of direct
observations, asked very pointed questions of scientists about what,
how, and why they did things, studied the lives of great scientists
and great contributions, and has done introspection and studied
theories of creativity. The talk is about what he has learned in terms
of the properties of the individual scientists, their abilities,
traits, working habits, attitudes, and philosophy.
http://www.cs.virginia.edu/~robins/YouAndYourResearch.pdf
==============================================================================
How to Grow a Mind: Statistics, Structure, and Abstraction
Tenenbaum, Kemp, Griffiths, Goodman (2011)
Abstract:
In coming to understand the world—in learning concepts, acquiring
language, and grasping causal relations—our minds make inferences that
appear to go far beyond the data available. How do we do it? This
review describes recent approaches to reverse-engineering human
learning and cognitive development and, in parallel, engineering more
humanlike machine learning systems. Computational models that perform
probabilistic inference over hierarchies of flexibly structured
representations can address some of the deepest questions about the
nature and origins of human thought: How does abstract knowledge guide
learning and reasoning from sparse data? What forms does our knowledge
take, across different domains and tasks? And how is that abstract
knowledge itself acquired?
==============================================================================