[Pl-seminar] Semantics Seminar Schedule

[Mitchell Wand]

NU Programming Languages Seminar
Wednesday, January 28, 2004
206 Egan  Hall, Northeastern University
    (building 60 on http://www.campusmap.neu.edu/)  
1145-145. Bring your lunch.

Mitchell Wand

Northeastern University

Relating Backtracking Monads 

(joint work with Dale Vaillancourt)

There are two well-known models of backtracking computation: the
stream model and the two-continuation model.  The stream model treats
backtracking computations with a stream of possible answers, and the
two-continuation model uses a success continuation and a failure
continuation.  Hughes [2000] defined a "backtracking monad" to be a
monad with additional operations "disj" and "fail" satisfying 5
additional axioms.  Both the stream model and the two-continuation
model are backtracking monads, but this fact does not give us any
deeper relation between the two.

Past attempts to relate these models have met with limited success:
either the types do not work out, or the relation works in one
direction but not the other, or the relation does not work for
higher-order values.

We show how to relate the two models in a simple way.  We relate
streams of scalars using a representation inspired by Danvy et
al. [2001].  We then extend this to higher-order values using logical
relations.  At observable types this turns into the identity relation,
so we get a denotational equivalence between the values in each model.
All of this is done with only elementary mathematics; no category
theory is necessary!

Note:  Snow is forecast for Tuesday evening and Wed morning.  Check
the NU web site at http://www.neu.edu for University closing
information.  Even if the University is open, my plan is to be sane.
If the talk has to be cancelled at the last minute, I will send out
email and post a notice to the pl-seminar home page,
http://www.ccs.neu.edu/home/wand/pl-seminar.html .

Upcoming Events:

Volunteers needed for 2/4 et seq

--Mitch