User loginNavigation 
TheoryOn the Unusual Effectiveness of Logic in Computer Science
In 2001, Moshe Vardi organised a workshop devoted to a the topic of The Unusual Effectiveness of Logic in Computer Science with papers presented covering such topics as "Logic as the calculus of computer science" (Vardi) and "Descriptive complexity" (Immerman), and later a gang consisting of Halpern, Harper, Immerman, Kolaitis, Vardi, and Vianu published a likewise named 24 page article in the July 2002 issue of the Bulletin of Symbolic Logic.
The title is derived from Wigner's famous article on The Unreasonable Effectiveness of Mathematics in the Natural Sciences, which was devoted to raising and attempting to answer the important question: why should mathematics have been so useful to natural scientists? With respect to logic, my answer for the effectiveness of LICS is that, while computation is a physical phenomenon, it is a phenomenon that is best understood via powerful abstractions, and the most powerful abstractions we have at the moment are abstractions in mathematical logic, because of the fundamental relationship of Turing completeness to Goedelian incompleteness. Links derived from Richard Zach's Motivating Intro Logic for Philosophy majors (and others). Recovering resources in the picalculusRecovering resources in the picalculus
By Andris Birkmanis at 20050403 07:48  Parallel/Distributed  Theory  6 comments  other blogs  7065 reads
How to remove a dynamic prompt: static and dynamic delimited continuation operators are equally expressible
The report (by Oleg Kiselyov) shows that shift, control, shift0, etc. delimited
continuation operators are macroexpressible in terms of each
other. The report thus confirms the result first established by
Chungchieh Shan in Shift to Control. The operators shift, control, control0, shift0 are the members of a single parameterized family, and the standard CPS is sufficient to express their denotational semantics.
The report uses a more uniform method and it formally proves that 'control' implemented via 'shift' indeed has its standard reduction semantics. It is common knowledge that firstclass continuations are quite tricky  and delimited continuations are trickier still. Therefore, a formal proof is a necessity. On the practical side, the report shows the simplest known Scheme implementations of control, shift0 and control0 (similar to `cupto'). The method in the report lets us design 700 more delimited control operators, which compose stack fragments in arbitrary ways. I love this sort of thing, and since section 4 includes Scheme code, you can try to skip the theory if you find it intimidating. I know this stuff can look a bit hairy. If there's interest, I hope Oleg would agree to help people new to this sort of material in understanding sections 2 and 3. But you have to ask nicely... A Tutorial on Proof Theoretic Foundations of Logic Programming
A Tutorial on Proof Theoretic Foundations of Logic Programming. Paola Bruscoli and Alessio Guglielmi. ICLP'03.
I just glanced through this tutorial, but since I know quite a few LtU readers are into proof theory, I thought I'd share the link. By Ehud Lamm at 20050320 22:17  Logic/Declarative  Theory  2 comments  other blogs  5461 reads
The POPLmark Challenge
(via TYPES)
How close are we to a world where every paper on programming languages is accompanied by an electronic appendix with machinechecked proofs? To gauge progress in this area, we issue here a set of challenge problems, dubbed the POPLmark Challenge, chosen to exercise many aspects of programming languages that are known to be difficult to formalize. A valid solution to the challenge will consist of appropriate software tools, a language representation strategy, and a demonstration that this infrastructure is sufficient to formalize the challenge problems. The POPLmark team explains,
We are not ourselves automated reasoning experts but rather potential users; our impression is that current tools are almost at the point where they can be used routinely. It's time to bring mechanized metatheory to the masses  go to it! A New Approach to Abstract Syntax with Variable BindingPitts and Gabbay, A New Approach to Abstract Syntax with Variable Binding, FAC 2001. In the lambda calculus, the particular choice of variable names  even free variables  is irrelevant. Names serve two purposes:
In a theory of binders, only the latter purpose is relevant. This is why it's so annoying to have to deal with captureavoiding substitution, the Barendregt variable convention,
There are several standard ways to deal with this. Generating fresh names with This paper introduces a theory of fresh names that restores algebraic reasoning, referential transparency, and structural induction to algebraic datatypes with a HOASlike notation for introducing binders into an abstract syntax. This is the settheoretical basis for the authors' work on FreshML and FreshO'Caml, which we've discussed a little bit on LtU in the past. By Dave Herman at 20050314 15:53  Lambda Calculus  MetaProgramming  Theory  7 comments  other blogs  5855 reads
Linear ForwardersLinear forwarders are actually the basic mechanism of an earlier implementation of the pi calculus called the fusion machine. We modify the fusion machine, replacing fusions by forwarders. The result is more robust in the presence of failures, and more fundamental. And also: The point of this paper is to solve the problem of input capability with a language that is “just right” – it neither disallows more features than necessary (as does the join calculus), nor adds more implementation work than is necessary (as does the fusion machine). Yes, these are the same capabilities as in capabilitybased security. I am looking forward to read the complete paper, as it seems to confirm my unclear ideas of how capabilities and various pi calculi are related. By Andris Birkmanis at 20050308 13:58  Parallel/Distributed  Theory  2 comments  other blogs  4330 reads
μABC: A Minimal Aspect Calculus
Aspectoriented programming is emerging as a powerful tool for system design and development. In this paper, we study aspects as primitive computational entities on par with objects, functions and hornclauses. To this end, we introduce μABC, a namebased calculus, that incorporates aspects as primitive. In contrast to earlier work on aspects in the context of objectoriented and functional programming, the only computational entities in μABC are aspects. We establish a compositional translations into μABC from a functional language with aspects and higherorder functions. Further, we delineate the features required to support an aspectoriented style by presenting a translation of μABC into an extended πcalculus. Proof and Counterexample
Greg Restall is
writing a book, entitled Proof and Counterexample (or PnC for short). It's on logic viewed through the lens of proof theory. In particular, it covers natural deduction, sequent calculus, normalisation and cutelimination. It's designed to both be stateoftheart reseearch on these topics, together with an introduction appropriate for an advanced undergraduate. (We'll see how that works. I'll be testdriving the material with honours students from February to June in 2005.) Newcomers to the field might wonder why this is relevant to programming languages, and some readers would regard this as pointless theory... But if you are one of us guys excited by CurryHoward, you might enjoy this wiki a lot. The Kell Calculus
The Kell Calculus: A Family of HigherOrder Distributed Process Calculi
This paper presents the Kell calculus, a family of distributed process calculi, parameterized by languages for input patterns, that is intended as a basis for studying componentbased distributed programming. The Kell calculus is built around a picalculus core, and follows five design principles which are essential for a foundational model of distributed and mobile programming: hierarchical localities, local actions, higherorder communication, programmable membranes, and dynamic binding. The paper discusses these principles, and defines the syntax and operational semantics common to all calculi in the Kell calculus family. The paper provides a coinductive characterization of contextual equivalence for Kell calculi, under sufficient conditions on pattern languages, by means of a form of higherorder bisimulation called strong context bisimulation. The paper also contains several examples that illustrate the expressive power of Kell calculi. NB: a family of calculi, parameterized by languages See also: The Kell Calculus In this page you will find information about the current state of the Kell calculus, links to published papers and drafts, information about where the Kell calculus is going[...] By Andris Birkmanis at 20050214 08:55  Parallel/Distributed  Theory  1 comment  other blogs  13041 reads

Browse archivesActive forum topics 
Recent comments
1 hour 11 min ago
3 hours 35 min ago
14 hours 39 min ago
15 hours 4 min ago
15 hours 7 min ago
18 hours 55 min ago
19 hours 32 min ago
23 hours 59 min ago
1 day 3 hours ago
1 day 4 hours ago