[Pl-seminar] Semantics Seminar Schedule
David Van Horn <[email protected]>
| Newsgroups | gmane.org.ballistichelmet.lambda |
|---|---|
| Message-ID | <[email protected]> |
-------- Original Message -------- Subject: [Pl-seminar] Semantics Seminar Schedule Date: Tue, 27 Jan 2004 00:05:01 -0500 From: Mitchell Wand <[email protected]> To: [email protected] 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 _______________________________________________ pl-seminar mailing list [email protected] https://lists.ccs.neu.edu/bin/listinfo/pl-seminar