destructive updates in Haskell
Paul Hudak answers a question concerning mutations of unshared structures: >George, I think you are implying that if an unshared list is passed to >this function then it can be mutated instead of copied. But >determining that it is unshared can be very difficult (of course it is >undecideable in general). Note in particular that you have to >determine if any of the list's SUBSTRUCTURE is shared. Could you be more specific? I don't understand why it is necessary to establish the uniqueness/non-uniqueness of the substructures just to (eventually) replace them? I would appreciate very much learning more about this subject, for example from the paper mentioned by Paul Hudak. But I have another question: what is the attitude of the Haskell gurus with respect to the solution proposed by the CONCURRENT CLEAN people - the usage of an explicit annotation UNQ to mark the un-shared objects and to allow their massacre? Jerzy Karczmarczuk, dept. of comp. sci., University of Caen Caen, Normandy, France. [EMAIL PROTECTED]
Re: destructive updates in Haskell
>George, I think you are implying that if an unshared list is passed to >this function then it can be mutated instead of copied. But >determining that it is unshared can be very difficult (of course it is >undecideable in general). Note in particular that you have to >determine if any of the list's SUBSTRUCTURE is shared. Could you be more specific? I don't understand why it is necessary to establish the uniqueness/non-uniqueness of the substructures just to (eventually) replace them? Here's a simple example: let x = [3,4] y = 1:2:x in (change y 3 5, x) where "change" is as George Nelan defined it. Now, y is not shared, and it's value is [1,2,3,4]. "change y 3 5" should return [1,2,3,5]. But if it does so destructively then the overall result will be ([1,2,3,5], [3,5]) which is clearly wrong. This is a result of a y's substructure being shared (x). I would appreciate very much learning more about this subject, for example from the paper mentioned by Paul Hudak. This topic has blossomed into a very active research area. Does anyone have a fairly comprehensive bibliography? If not maybe I should try to put one together. I should also mention that Martin Odersky and I have organized an ACM workshop on State in Programming Languages (SIPL) which will be held between FPCA and PEPM in Copenhagen this June. "State" is also of interest to imperative language researchers (:-). But I have another question: what is the attitude of the Haskell gurus with respect to the solution proposed by the CONCURRENT CLEAN people - the usage of an explicit annotation UNQ to mark the un-shared objects and to allow their massacre? I thought the Clean folks were using a linear type system of some sort; is UNQ part of that? If so, I think it's a very promising direction to pursue. The jury is not in on any of this. -Paul
Re: general update notation
Date: Tue, 27 Apr 1993 08:38:34 +0100 From: Simon L Peyton Jones People reading the update-notation thread might also be interested in "Imperative functional programming" Peyton Jones & Wadler, POPL 93 The paper mainly deals with I/O and updatable arrays, but the same technology allows other update-in-place data structures too. It is all implemented in the Glasgow Haskell compiler. I highly recommend Simon's paper, too. I should also mention that in Yale Haskell we have implemented a very general interface to Common Lisp similar to what the Glasgow folks have done for C. Using it we have implemented a completely functional interface to the CL-X library (X-windows), for example. But, it should be understood that NEITHER of these techniques makes any "guarantees" about in-place updateability -- i.e. the burden is completely on you, the programmer, and if you're not careful you can destroy referential transparency. The purpose of the paper that I referred to in my previous message is to show (i.e. prove) when the idea works and when it doesn't, and to give a translation mechanism to derive new axioms from the old. I don't know of any work similar to this. -Paul
Re: general update notation
People reading the update-notation thread might also be interested in "Imperative functional programming" Peyton Jones & Wadler, POPL 93 which you can grab by ftp fromftp.dcs.glasgow.ac.uk in pub/glasgow-fp/papers/imperative.ps.Z The paper mainly deals with I/O and updatable arrays, but the same technology allows other update-in-place data structures too. It is all implemented in the Glasgow Haskell compiler. No claims here that our approach, which is generally similar to the one Paul describes, solves all the problems. I completely agree that the difficulty of reasoning about space and time behaviour is a Problem for non-strict languages. Simon
