Intensional Computation

A/Prof Barry Jay (QCIS, School of Software, University of Technology Sydney)

LOGIC AND COMPUTATION SEMINAR

DATE: 2012-09-04
TIME: 16:00:00 - 17:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
Intensional computation is concerned with the ability to query internal structure. Most commonly, the structure is a database, and the goal is select or update the data in the structure. However, it is common to represent functions, such as computer programs, by a structure, and to query this structure, as when looking for computer viruses, or compiling a program.

Till now, queries have received little attention within the foundations of computing. Classical theorems reduce all computation to extensional computation, as represented by, say, lambda calculus or combinators built from extensional operators (usually, S, K and I). However, there are intensional operators, able to support generic queries, that cannot be defined in terms of extensional operators.

This talk will introduce the factorisation operator, and use it to define generic queries for selecting and updating, as pattern-matching functions. If there is time, a self-interpreter will be defined, and shown to have a statically defined type taken from System F.
BIO:
Associate Professor Barry Jay is a member of the School of Software and the Centre for Quantum Computing and Intelligent Systems at the University of Technology, Sydney. He obtained his BSc (Hons, pure mathematics) from the University of Sydney (1980) and his PhD (mathematics) from McGill University, Montreal (1984). He learned about computing as a senior research fellow at the Laboratory for the Foundations of Computer Science in Edinburgh before moving to UTS in 1993. His current research develops the pattern calculus and its implications for programming in his language bondi, as set out in his recent Springer monograph "Pattern Calculus: Computing with Functions and Structures".