March 1997 - Categories - categories.org.au

JFP Editorial
by Philip Wadler 27 Mar '97

27 Mar '97

The following editorial will appear in the next issue of the Journal of Functional Programming. It reiterates our scope, and announces some changes in our editorial staff. Our web address appears below, and e-mail addresses for the people mentioned below appear above. I look forward to seeing your submissions to JFP! -- P A HOT opportunity The Java phenomenon means that programmers that once laughed at garbage collection and strong typing have started to use it daily, and this opens up a wonderful opportunity for the functional programming community. Bob Harper coined the acronym HOT to summarise much of what functional programmers have to offer the world: expertise in languages that are Higher-Order and Typed. Bob argued for a broad interpretation of these terms, so that Higher-Order includes languages where objects contain methods (even though functions are not first-class citizens), and Typed includes both static and dynamic typing. By these criteria Java is HOT, and so are Haskell, ML, and Scheme. Not all functional languages of interest are all that HOT. Ericsson is using the functional and concurrent language Erlang to build phone switches containing hundreds of thousands of lines of code. Erlang is a first-order language with dynamic types (though recent work has added higher-order, and static types are in the offing). The key to Erlang's success is similar to Java's: both have thrived by focussing on an application area, the web for Java, telephony for Erlang. Those who strive to eke another five percent speed-up out of their compilers should note another similarity between Java and Erlang: both achieved their initial success based on byte code interpreters of modest efficiency (though fast native code compilers for both are coming along). We should continue to seek ``killer apps'' for functional programming. The Journal of Functional Programming encourages all attempts at outreach, from our area to others, from theory to practice. JFP has published papers on the higher-order and typed aspects of Modula-3, Algol, and Actors. We have run (or are about to run) papers on applications to animation, artificial intelligence, music, protein analysis, scientific programming, and text processing. We have had a special issue devoted to type systems for object-oriented programming, and another to applications. As always, we remain a broad church. Send us your HOT papers, your application papers, your papers on links to other areas. Send us papers about languages typed or untyped, strict or lazy, pure or stateful, sequential or concurrent. --- On the home front, there are some changes to announce. Sad to say, Henk Barendregt, due to pressures of work, has resigned as an editor of JFP. However, we are delighted that he has agreed to remain as editor of our Theoretical Pearls column. So continue to send Henk any beautiful and brief candidates for his column, but please send other submissions to one of the other JFP editors. Please join us in thanking Henk for his help in founding JFP, and for his seven years of devoted service. And please join us in welcoming our new editor, Thierry Coquand. Thierry brings special expertise in the HOT area of type theory, and is generally knowledgeable in all things theoretical. To give Thierry the warmest welcome, send him a paper today; submission details are on the inside back cover, addresses on the inside front. The theory editor is dead, long live the Thierry editor! Please also join us in welcoming Simon Thompson as book review editor. Publishers are keen to give away books in return for reviews, we are keen to run discriminating reviews, and the reviewer gets to keep the book. Let Simon know if you'd like to register as a reviewer, if there's some book you want to review, or if there's a book you'd like to see us review. His address is inside the front cover. This is also a good point to thank Richard Bird for his continuing effort as editor of Functional Pearls. If you have a contribution that is small, rounded, and pleasant, you'll find his address, too, on the inside front. Richard continues to contribute regular columns, setting a high standard for the rest of us. And when you do send a paper, just how long will it take to get a response? Answer: about three months, on average. We at JFP have no patience for journals that sit on papers for years. The editors all aim to reach a decision (accept, revise, or reject) on each paper within four months of receipt, a goal which Simon, Paul, and John met for every paper processed in the last year, and which Phil failed to meet just once (by four days). To achieve this, we ask our reviewers to acknowledge papers immediately and to provide reviews promptly, typically within a month. And we get back to them if we don't hear from them. This leads us to our penultimate thank you: to the reviewers who make the process work. Without them, our science would grind to a halt. --- A venerable curse reads ``May you live in interesting times''. The written word is increasingly viewed on the screen rather than on the page, and our web site at www.dcs.glasgow.ac.uk/jfp is increasingly a part of what we do. Nonetheless, we intend to publish as atoms rather than as bits for a while longer. Atoms or bits, journals will remain at the core of scientific progress. Their key ingredients are not ink and pulp, nor Latex and HTML, but writers, reviewers, and readers. Our final thank you is to you, for your contribution to JFP. We look forward to taking, with you, our next step into interesting times. -- Philip Wadler, for the editors of JFP ----------------------------------------------------------------------- Philip Wadler wadler(a)research.bell-labs.com Bell Laboratories http://cm.bell-labs.com/cm/cs/who/wadler/ Lucent Technologies office: +1 908 582 4004 700 Mountain Ave, Room 2T-304 fax: +1 908 582 5857 Murray Hill, NJ 07974-0636 USA home: +1 908 626 9252 -----------------------------------------------------------------------

1 0

Lectureships at Edinburgh CS Dept.
by Gordon Plotkin 24 Mar '97

24 Mar '97

Two Lectureships are available at the Department of Computer Science of the University of Edinburgh. One is strongly LFCS (Laboratory for the Foundations of Computer Science) related, and the other is general. For details, see http://www.dcs.ed.ac.uk/jobs/ Gordon Plotkin

1 0

Morphisms of diagrams
by Charles Wells 21 Mar '97

21 Mar '97

Let C be a category and I and I' graphs (or categories if you prefer). Define a morphism of diagrams psi:(delta:I-->C)-->(delta':I'-->C) to be a graph morphism (or functor if you prefer) psi:I-->I' together with a natural transformation alpha:delta' o psi-->delta. This definition turns Lim into a contravariant functor from the category of diagrams to C (when C is complete, anyway). I believe this construction has been familiar since the early days of category theory, but I don't know a reference and would be glad to learn of any. By the way, Barr in SLN 236 (page 52) defines an entirely different notion of morphism of diagrams which Tholen and Tozzi develop extensively in "Completions of Categories and Initial Completions", Cahiers 1989, pages 127-156. This makes Lim a covariant functor. Charles Wells, 105 South Cedar Street, Oberlin, Ohio 44074, USA. (I am on sabbatical until 20 August 1997 and cannot easily be reached at Case Western Reserve University.) EMAIL: cfw2(a)po.cwru.edu. HOME PHONE: 216 774 1926. FAX: Same as home phone. HOME PAGE: URL http://www.cwru.edu/CWRU/Dept/Artsci/math/wells/home.html "Some have said that I can't sing. But no one will say that I _didn't_ sing." --Florence Foster Jenkins

3 2

Readership
by Dr. P.T. Johnstone 20 Mar '97

20 Mar '97

Many thanks to all of you who have sent good wishes to me on my promotion. I apologise for not replying individually, but there really are too many of you! Peter Johnstone

1 0

good news!
by Peter Freyd 19 Mar '97

19 Mar '97

It's official: Peter Johnstone becomes a Reader in Maths. Three categorical readers at Cambridge -- not bad that.

1 0

BRICS International PhD School: Call for Applications
by Uffe Henrik Engberg 19 Mar '97

19 Mar '97

BRICS International PhD School in Computer Science University of Aarhus, Denmark Announcement and Call for Applications An international PhD School in computer science is opening at the University of Aarhus. This is its initial call for admissions and grant applications. The School is an integrated part of the BRICS (Basic Research in Computer Science) Research Centre, and both are funded by the Danish National Research Foundation. The school admits 10-12 students annually, and provides a substantial number of grants for Danish as well as foreign students. The PhD School wishes to recruit foreign PhD students of the highest international standards. It provides an excellent research environment and scientific training facilities, and aims at making its PhD graduates attractive for a wide spectrum of employers - in private and public research and development institutions, both in Denmark and abroad. So, if you are a computer science student and soon to complete at least four years of full-time study, highly motivated for a PhD study in a truly international environment, please send us an application following the instructions below. For more details please visit http://www.brics.dk, or contact us by e-mail at phdschool(a)brics.dk. Also, we would appreciate your passing on this information to interested students and colleagues at your university or research institute. BRICS The Research Centre BRICS (Basic Research In Computer Science) was founded in 1994 by the Danish National Research Foundation at the University of Aarhus in association with the University of Aalborg. BRICS supports basic research in Algorithmics, Logic and Semantics, mainly through an extensive programme of short- and long-term visiting scientists. Research Areas The core areas of the PhD School are: Semantics of Computation; Logic in Computer Science; Computational Complexity; Design and Analysis of Algorithms; Programming Languages; Distributed Computing; Verification; and Data Security and Cryptology. The school will provide its students with a solid background in the theoretical foundation centred around BRICS activities. From this foundation, the students may either continue in one of the core areas or venture into areas of a more applied or experimental nature as possible areas of thesis specialisation. Admission Prerequisites and Study Structure Admission is based on knowledge corresponding to four years of full-time studies, including basic courses in programming and programming languages, algorithms and data structures, computer architecture, computability and mathematics. (This list is based on the current undergraduate education at the University of Aarhus, and will be interpreted in a flexible way.) The time allocated for the PhD studies is a further four years, where the first two years include some mandatory course work and introductory research, concluded by a qualifying examination, whereas the last two years are dedicated to the writing of the thesis, finishing with a defence. All students admitted to the school will enter this study structure. We may, however, take into account merits from previous study. Students are normally admitted for the semester start September 1st, but admission may take place throughout the year. PhD Student Grants The school offers student grants of different types covering tuition waivers and/or living expenses. School Start The BRICS International PhD School formally started January 1st 1997. The first school students will be admitted by September 1st 1997. The school will admit approximately 10-12 students per year, of which half are expected to be foreign. How to apply 1. Fill in the application form on http://www.brics.dk/PhDSchool/Application.html Alternatively, send an e-mail to phdschool(a)brics.dk with subject "Application" including: - your full name, personal address and phone number, college / university, URL of home page (if applicable), e-mail address, - type of application, i.e. a combination of: admission; tuition waiver; studentship covering living expenses (for details see http://www.brics.dk) 2. Send by ordinary mail to the address below - a covering letter, including the information from your application form/e-mail, - a short curriculum vitae, - complete official transcripts from colleges or univer- sities, documenting minimally four years of full time study, - names of three people whom we may ask for letters of recommendation, - an indication of applicant's motivation for a PhD study, and particular research area of initial interest (max 2 pages). There are no general deadlines, but applications for admission September 1st, 1997 should be sent as soon as possible and preferably before April 15th. Further Information For further information, please e-mail phdschool(a)brics.dk or visit http://www.brics.dk Address BRICS PhD School Department of Computer Science University of Aarhus Ny Munkegade, Bldg. 540 DK-8000 Aarhus C. Denmark Phone: +45 8942 3264

1 0

a characterisation of factorisation systems
by Paul-Andre Mellies 18 Mar '97

18 Mar '97

Dear categorists, I have recently proved an (E,M)-factorisation theorem in the framework of axiomatic rewriting systems: every derivation X -> Y factorises (up to Levy permutation equivalence) into a head reduction X -> Z followed by a non-head reduction Z -> Y. One special difficulty in my case is that I do not define the class M of non-head reductions as a category. So, I need a characterisation of factorisation system (E,M) without any assumption of categoricity of E or M. Here is the statement of the theorem I finally proved: ----------------------------------------------------------------------------- Let E and M be two classes of morphisms in a category C. (E,M) is a factorisation system of C if and only if the four following properties hold: 1. every morphism f in C can be factored as f=me with m in M and e in E, 2. if e is a morphism in E and m is a morphism in M then e is orthogonal to m, 3. if i is an iso left composable to e in E, then ie is in E, 4. if i is an iso right composable to m in M, then mi is in M. ----------------------------------------------------------------------------- I do not know if this characterisation already exists in the litterature on factorisation systems. If it does, please send me the reference to integrate in my paper. People interested in the paper can load it there: http://www.dcs.ed.ac.uk/home/paulm/

3 2

2-Tangles
by John Baez 18 Mar '97

18 Mar '97

Here is a short paper summarizing some work done by my student Laurel Langford. ----------------------------------------------------------------------- 2-Tangles John C. Baez and Laurel Langford Just as links may be algebraically described as certain morphisms in the category of tangles, compact surfaces smoothly embedded in R^4 may be described as certain 2-morphisms in the 2-category of `2-tangles in 4 dimensions'. In this announcement we give a purely algebraic characterization of the 2-category of unframed unoriented 2-tangles in 4 dimensions as the `free semistrict braided monoidal 2-category with duals on one unframed self-dual object'. A forthcoming paper will contain a proof of this result using the movie moves of Carter, Rieger and Saito. We comment on how one might use this result to construct invariants of 2-tangles. One can get a Postscript version of this paper at http://math.ucr.edu/home/baez/2tang.ps or by anonymous ftp to math.ucr.edu, where it's in the directory pub/baez, as the file 2tang.ps

1 0

AMS Special session in categories
by Robert A. G. Seely 13 Mar '97

13 Mar '97

Mike Barr has asked me to relay the following information (my source was the following URL: <http://www.ams.org/amsmtgs/>) The pertinent fact of interest to this list is the special session on Category Theory and its Applications which he, Ieke Moerdijk, and Myles Tierney are organizing. For further information, contact the organizers; updates will be posted to this list as appropriate. = rags = -------------------------------------------------------------------------- Notice of AMS Meeting September 26-28, 1997 Montreal, Quebec Canada (1997 Fall Eastern Sectional Meeting) Meeting # 924, Notices Program Issue: October 1997 Deadline for Contributed Papers for consideration in Special Sessions: May 1, 1997 Deadline for Abstract Submission: June 26, 1997 Special Sessions and Invited Addresses Invited Addresses Jacob E. Goodman, City University of New York, City College , Title to be announced Dieter Kotschick, University of Basel, Switzerland , Title to be announced Francois Lalonde, University of Quebec at Montreal , Title to be announced I. Moerdijk, University of Utrecht, Netherlands , Title to be announced Special Session on Category Theory and Its Applications Organizers: Michael Barr, McGill University barr(a)triples.math.mcgill.ca Ieke Moerdijk, University of Utrecht. Netherlands moerdijk(a)math.ruu.ne Myles Tierney, Rutgers University tierney(a)math.rutgers.edu

1 1

Research Associate Position
by Roy L. Crole 11 Mar '97

11 Mar '97

UNIVERSITY OF LEICESTER Department of Mathematics and Computer Science RESEARCH ASSOCIATE Applications are invited for a post of Research Associate available for up to three years to work on an EPSRC funded project entitled "The Complexity of Problems in Infinite Groups". The aims of the project are to further develop and extend links between Theoretical Computer Science and Mathematics. Candidates should possess, or be completing, a PhD in Mathematics or Theoretical Computer Science. Salary will be towards the lower end of the R&A 1A Scale (14,732 - 22,143 GBpounds pa) depending on qualifications and experience. Further information can be obtained from Dr R. M. Thomas (rmt(a)mcs.le.ac.uk) or Prof I. A. Stewart (i.a.stewart(a)mcs.le.ac.uk) particulars are also available on the web (http://www.mcs.le.ac.uk/~rthomas/Particulars) Application forms and further particulars are available from the Personnel and Planning Office (Research Appointments), University of Leicester, University Road, Leicester LE1 7RH. Tel (0116) 223 1341. Please quote reference number R7025/Web. Closing date for receipt of applications is 4th April 1997.

1 0