Title: Software Development Using Generalized Semantic Games

Speaker: Karl Lieberherr, College of Computer and Information Science, Northeastern University, Boston.

Date: July 16, 2013
Time: 11.00 am
Where: ETH Zurich, Room to be announced
Host: Thomas Gross, Laboratory for Software Technology

Abstract

We start from software requirements written as interpreted logic statements, for example, by expressing preconditions and postconditions. We use generalized semantic games associated with the interpreted logic statements as the foundation for supporting the process of developing code. Developers create avatars that play the generalized semantic game on their behalf. These avatars contain components for solving the given computational problem as well as for testing other avatars. It is guaranteed by the definition of generalized semantic games that the avatars that have the correct components can never lose. The overall process makes development a fun activity which has a collaborative and competitive nature. We call our approach the Scientific Community Game (SCG). SCG generalizes the approach of TopCoder. SCG also has other applications in education and in building the Formal Science Wikipedia, a repository of "clever constructions".

The generalization of the semantic games includes a new concept, called the Contradiction-Agreement Game, which fairly forces users to play devil's advocate. The generalization also includes a novel way of scaling semantic games to a community of users employing an evidence-based evaluation approach. We describe a proof of concept implementation of SCG which uses a modular construct, called a lab, to group related claims and to solve labs incrementally through lab relations, which are themselves captured as labs. We report on the usage of earlier versions of SCG for teaching software development and algorithms (2007-2012).

SCG internally uses the solution of several computational problems which might currently not be solved optimally. However, we can make an SCG lab out of every such computational problem and use SCG to improve SCG, making SCG a self-improving system.

Joint work with Ahmed Abdelmeged and Yizhou Sun

Short Bio of Speaker:

Karl Lieberherr started his research career in computer science as a theoretical computer scientist, focusing on the theory of P-optimal algorithms for the generalized maximum satisfiability problem (MAX-CSP), still an active area of research. Much later, in 2007, this work has motivated the development of a gaming platform for formal decision making, called the Scientific Community Game (SCG) also known as the Specker Challenge Game, named after former ETH Professor Ernst Specker. He also invented, independently and simultaneously on the other side of the Atlantic (at ETH Zurich), an early form of non-chronological backtracking based on learned clauses (superresolution), which has become a key feature of most state-of-the-art SAT and CSP solvers.

In the mid 1980s, he switched to Object-Oriented and Aspect-Oriented Software Development and focused on issues of software design and modularity. He founded the Demeter research team, which studied the then-novel idea of Adaptive Programming, also known as structure-shy programming and produced the Law of Demeter ("talk only to your friends": an explicit form of coupling control) and several systems for separating concerns in an object-oriented programming context: From Demeter/Flavors to DemeterF.

Dr. Lieberherr is a Professor in the College of Computer and Information Science at Northeastern University.