Summer Camp on Programming 2017

General information

9 ~ 11, August, 2017
Josh Ko, hsiang-shang [at] nii [dot] ac [dot] jp
Zirun Zhu, zhu [at] nii [dot] ac [dot] jp
Train + bus. Click to see detailed access information. Briefly:
  1. Take a train to Zushi station or Shin-Zushi station.
    • From Tokyo station, use JR Yokosuka Line.
    • From Shinjuku station, use JR Shonan-Shinjuku Line.
    • From Shinagawa station, use Keihin Kyuko (Keikyu) Line
  2. After arriving at Zushi station or Shin-Zushi station, please take Keikyu bus NO.16 (逗16) or Keikyu bus NO.26 (逗26) at bus platform 1 and get off at Shonan Kokusaimura Center Mae.
  3. Take a five-minutes walk to the Shonan Village Center
  • It takes about 60 minutes from Tokyo station or Shinjuku station to Zushi station.
  • The bus from Zushi station to the venue takes 30 minutes, however, there are few buses from Zushi station to Shonan Village Center. See the bus time table for NO.16 and NO.26. For August 9 and 10, use the column 平日. For August 11, use the column 休日.
  • More tips will be added after the programme is fixed.


A Co-Relational Model of Data for Large Shared Data Banks

Erik Meijer and Bierman In Communications of the ACM (2011).

Contrary to popular belief, SQL and noSQL are really just two sides of the same coin.

Speaker: Hiroyuki Kato (National Institute of Informatics, Japan)

Copatterns: Programming Infinite Structures by Observations

Abel et al. In POPL 2013.

Inductive datatypes provide mechanisms to define finite data such as finite lists and trees via constructors and allow programmers to analyze and manipulate finite data via pattern matching. In this paper, we develop a dual approach for working with infinite data structures such as streams. Infinite data inhabits coinductive datatypes which denote greatest fixpoints. Unlike finite data which is defined by constructors we define infinite data by observations. Dual to pattern matching, a tool for analyzing finite data, we develop the concept of copattern matching, which allows us to synthesize infinite data. This leads to a symmetric language design where pattern matching on finite and infinite data can be mixed.

We present a core language for programming with infinite structures by observations together with its operational semantics based on (co)pattern matching and describe coverage of copatterns. Our language naturally supports both call-by-name and call-by-value interpretations and can be seamlessly integrated into existing languages like Haskell and ML. We prove type soundness for our language and sketch how copatterns open new directions for solving problems in the interaction of coinductive and dependent types.

Speaker: Josh Ko (National Institute of Informatics, Japan)

Lectures on Computational Complexity

Speaker: Yuxi Fu (Shanghai Jiao Tong University, China)

Identifying Functionally Similar Code in Complex Codebases

Su et al. In ICPC 2016.

Identifying similar code in software systems can assist many software engineering tasks such as program understanding and software refactoring. While most approaches focus on identifying code that looks alike, some techniques aim at detecting code that functions alike. Detecting these functional clones - code that functions alike - in object oriented languages remains an open question because of the difficulty in exposing and comparing programs' functionality effectively. We propose a novel technique, In-Vivo Clone Detection, that detects functional clones in arbitrary programs by identifying and mining their inputs and outputs. The key insight is to use existing workloads to execute programs and then measure functional similarities between programs based on their inputs and outputs, which mitigates the problems in object oriented languages reported by prior work. We implement such technique in our system, HitoshiIO, which is open source and freely available. Our experimental results show that HitoshiIO detects more than 800 functional clones across a corpus of 118 projects. In a random sample of the detected clones, HitoshiIO achieves 68+% true positive rate with only 15% false positive rate.

Speaker: Chunmiao Li (Shanghai Jiao Tong University, China)

Is Mutation an Appropriate Tool for Testing Experiments?

Andrews et al. In ICSE 2005.

The empirical assessment of test techniques plays an important role in software testing research. One common practice is to instrument faults, either manually or by using mutation operators. The latter allows the systematic, repeatable seeding of large numbers of faults; however, we do not know whether empirical results obtained this way lead to valid, representative conclusions. This paper investigates this important question based on a number of programs with comprehensive pools of test cases and known faults. It is concluded that, based on the data available thus far, the use of mutation operators is yielding trustworthy results (generated mutants are similar to real faults). Mutants appear however to be different from hand-seeded faults that seem to be harder to detect than real faults.

Speaker: Ali Mili (New Jersey Institute of Technology, USA)

Do Developers Read Compiler Error Messages?

Barik et al. In ICSE 2017.

In integrated development environments, developers receive compiler error messages through a variety of textual and visual mechanisms, such as popups and wavy red underlines. Although error messages are the primary means of communicating defects to developers, researchers have a limited understanding on how developers actually use these messages to resolve defects. To understand how developers use error messages, we conducted an eye tracking study with 56 participants from undergraduate and graduate software engineering courses at our university. The participants attempted to resolve common, yet problematic defects in a Java code base within the Eclipse development environment. We found that: 1) participants read error messages and the difficulty of reading these messages is comparable to the difficulty of reading source code, 2) difficulty reading error messages significantly predicts participants' task performance, and 3) participants allocate a substantial portion of their total task to reading error messages (13%--25%). The results of our study offer empirical justification for the need to improve compiler error messages for developers.

Speaker: Kanae Tsushima (National Institute of Informatics, Japan)

SELF: The Power of Simplicity

Ungar and Smith. In LISP and Symbolic Computation (1991).

Self is an object-oriented language for exploratory programming based on a small number of simple and concrete ideas: prototypes, slots, and behavior. Prototypes combine inheritance and instantiation to provide a framework that is simpler and more flexible than most object-oriented languages. Slots unite variables and procedures into a single construct. This permits the inheritance hierarchy to take over the function of lexical scoping in conventional languages. Finally, because Self does not distinguish state from behavior, it narrows the gaps between ordinary objects, procedures, and closures. Self’s simplicity and expressiveness offer new insights into object-oriented computation.

Speaker: Zirun Zhu (National Institute of Informatics, Japan)

Bayesian networks without tears: making Bayesian networks more accessible to the probabilistically unsophisticated Eugene Charniak

Charniak. In AI Magazine (1991).

I give an introduction to Bayesian networks for AI researchers with a limited grounding in probability theory. Over the last few years, this method of reasoning using probabilities has become popular within the AI probability and uncertainty community. Indeed, it is probably fair to say that Bayesian networks are to a large segment of the AI-uncertainty community what resolution theorem proving is to the AI-logic community. Nevertheless, despite what seems to be their obvious importance, the ideas and techniques have not spread much beyond the research community responsible for them. This is probably because the ideas and techniques are not that easy to understand. I hope to rectify this situation by making Bayesian networks more accessible to the probabilistically unsophisticated

Speaker: Kailun Wang (Shanghai Jiao Tong University, China)

The Game of Hex: An Automatic Theorem Proving Approach to Game Programming

Anshelevich. In AAAI 2000.

The game of Hex is a two-player game with simple rules, a deep underlying mathematical beauty, and a strategic complexity comparable to that of Chess and Go. The massive game-tree search techniques developed mostly for Chess, and successfully used for Checkers, Othello, and a number of other games, become less useful for games with large branching factors like Go and Hex. We offer a new approach, which results in superior playing strength. This approach emphasizes deep analysis of relatively few game positions. In order to reach this goal, we develop an automatic theorem proving technique for topological analysis of Hex positions. We also discuss in detail an idea of modeling Hex positions with electrical resistor circuits. We explain how this approach is implemented in Hexy - the strongest known Hex-playing computer program, able to compete with best human players.

Speaker: Yongzhe Zhang (National Insititute of Informatics, Japan)

On regularity of context-free languages

Ehrenfeucht et al. In Theoretical Computer Science (1983).

This paper considers conditions under which a context-free language is regular and conditions which imposed on (productions of) a rewriting system generating a context-free language will guarantee that the generated language is regular. In particular:

  1. necessary and sufficient conditions on productions of a unitary grammar are given that guarantee the generated language to be regular (a unitary grammar is a semi-Thue system in which the left-hand of each production is the empty word), and
  2. it is proved that commutativity of a linear language implies its regularity. To obtain the former result, we give a generalization of the Myhill–Nerode characterization of the regular languages in terms of well-quasi orders, along with a generalization of Higman's well-quasi order result concerning the subsequence embedding relation on Σ*. In obtaining the latter results, we introduce the class of periodic languages, and demonstrate how they can be used to characterize the commutative regular languages. Here we also utilize the theory of well-quasi orders.

Speaker: Mizuhito Ogawa (Japan Advanced Institute of Science and Technology)

Finite and Infinite Calculus

Graham et al. In Concrete Mathematics (1994).

Mathematicians have developed a “finite calculus,” analogous to the more traditional in nite calculus, by which it’s possible to approach summation in a nice, systematic fashion.

Speaker: Zhenjiang Hu (National Institute of Informatics, Japan)

The camp starts from 15:00
If you plan to have lunch in Tokyo, we recommend the following plans.
If you plan to have lunch in Zushi, the following travel plans will work:
In eithr case
14:05, get on the Keikyu bus NO.16 (逗16) at bus platform 1 and get off at Shonan Kokusaimura Center Mae.

Timetable for Keikyu bus No.16 (逗16) from Shonan Kokusaimura Center Mae (湘南国際村センター前) to Zushi (逗子) station on
August 11, after lunch: 13:45 , 14:45 , 15:45 , 16:45 , 17:45 , 18:31

Trains from Zushi to Tokyo/Shinjuku stations are somehow dense, for every 10 ~ 15 minutes.

If you do not want to make any transfer, use the following trains:
To Tokyo:
14:42, JR Yokosuka line, heading for Tokyo, platform 2
14:54, JR Yokosuka line, heading for Kazusa-Ichinomiya (上総一ノ宮), platform 1
15:53, JR Yokosuka line, heading for Kazusa-Ichinomiya (上総一ノ宮), platform 1
16:09, JR Airport line, heading for Narita / Narita Airport (成田・成田空港), platform 1

To Shinjuku:
14:33, JR Shonan-Shinjuku line, heading for Utsunomiya (宇都宮), platform 1
15:02, JR Shonan-Shinjuku line (express), heading for Utsunomiya (宇都宮), no platform info
15:32, JR Shonan-Shinjuku line, heading for Koganei (小金井), platform 3
16:02, JR Shonan-Shinjuku line (express), heading for Utsunomiya (宇都宮), platform 2