How to hide the type ?

Jan Krynicky jkry3025@barbora.ms.mff.cuni.cz
Wed, 26 Feb 1997 21:43:55 -0800


This is a multi-part message in MIME format.

--------------53C86EF51C7D
Content-Type: text/plain; charset=iso-8859-2
Content-Transfer-Encoding: 7bit

I'm trying to simulate pointers in a purely functional language 
(namely Concurrent Clean), by means of mapping functions.
Simply the pointer (one of several types) is a function of type

 :: (item -> output,item) heap -> ( output, heap)

that maps a function working with an object onto the whole 'heap'.

Where the 'item' is the type of the object this is a pointer to.

When I add an object to the heap, I provide it with necessary
'pointers' to other objects.

The problem appears when I want to save this 'pointer'
into an object. I cannot place it there as a polymorphic
function. 

:: Obj heap = {state :: SameType; next :: (item -> output,item) heap ->
( output, heap)}

This doesn't compile.
I can restrict it to some type :

:: Obj heap = {state :: SameType; next :: (item -> Int,item) heap -> (
Int, heap)}

But then I would have to have several pointers to one object
distinquished
only by the type.

If I make the type explicit :

:: Obj heap output = {state :: SameType; next :: (item -> output,item)
heap -> ( output, heap)}

I don't get anything cause again as soon as I use the pointer 
the type instantiates. So I different objects can have pointers
with different outputs, but a single poitner of a single object is bound
to one type.

I tried even to make the output existentialy typed, but it didn't work
either.

:: Obj heap = E.output : {state :: SameType; next :: (item ->
output,item) heap -> ( output, heap)}


Ex.

change obj heap = ( obj`, heap`)
 where
  obj` = { obj & x = obj.x + bx }
  ( bx, heap`) = obj.next g heap
  g b = ( b.x, b)

change2 obj heap = ( obj`, heap`)
 where
  obj` = { obj & y = obj.y + by }
  ( by, heap`) = obj.next g heap
  g b = ( b.y, b)

I can use these two functions on the same object ONLY if the type of b.x
is equal to the type of b.y.
Which is silly. The type of output is not used anyhow by the pointer.
And as soon as I specify the function I want to map by this pointer, the
type of the 
result is defined.

Can I somehow hide the output type?

Jenda

P.S.: I send a little working example of this approach as an attachment.
With output bound to be Int.

---------- crosposed to comp.lang.functional --- and ---
------------clean-list&cs.kun.nl -----------------------

--------------53C86EF51C7D
Content-Type: text/plain; charset=iso-8859-2; name="HEAP.ICL"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="HEAP.ICL"

module Heap

import StdReal,StdMisc,StdInt,StdFunc


:: Fun heap op_heap :== .heap -> ( [op_heap], .heap)    // a hack to preserve unigueness
:: Op .heap :==  (Fun heap (Op heap))
   // operation on heap, such an operation can not only change the heap,
   // but also return new operations to be executed.

// several different kinds of pointers

:: PtrVal heap item output :== (item -> ( output, item)) heap -> (output, heap)
   // a pointer to an object, mapping function
   
:: PtrFun heap input output :==  input heap -> ( output, heap)
   // a pointer to a method, we give the input and get the result

:: PtrOp heap item :== (item heap -> ( [Op heap], item, heap)) heap -> ( [ Op heap], heap)
   // a pointer to an object, call a method with access to heap.
   //   These pointers may not be used directly, you should return them as operations.

:: PtrOpFun heap input :== input heap -> ( [ Op heap], heap)
   // similar to PtrOp but points to a method.
   //   These pointers may not be used directly, you should return them as operations.


// A container for a collection of pointers
:: Pointers heap item outputVal inputFun outputFun inputOpFun 
 = { ptrVal   :: PtrVal heap item outputVal, 
     ptrFun   :: ( inputFun item -> ( outputFun, item)) -> PtrFun heap inputFun outputFun,
     ptrOp    :: PtrOp heap item,
     ptrOpFun :: ( inputOpFun item heap -> ( [Op heap], item, heap)) -> PtrOpFun heap inputOpFun
   }


// function creating the pointers, you must specify how to get and set the element
// if you want to preserve uniqueness of the element, replace it by 'undef'
// or better 'abort "Ilegal call to an object." '.

makePointers :: (a -> .(b,a)) (b -> .(a -> a)) -> .Pointers a b .c d e f;
makePointers get set = { ptrVal=ptr_val, ptrFun=ptr_fun, ptrOp=ptr_op, ptrOpFun=ptr_opfun}
 where
  ptr_val f t = ( res, t``)
   where
    ( a, t`) = get t
    ( res, a`) = f a
    t`` = set a` t`

  ptr_fun f input heap = ( output, top``)
   where
    ( a, top`) = get heap
    ( output, a`) = f input a
    top`` = set a` top`
  
  ptr_op f heap = ( ops, top```)
   where
    ( a, top`) = get heap
    ( ops, a`, top``) = f a top`
    top``` = set a` top``

  ptr_opfun f input heap = ( ops, top```)
   where
    ( a, top`) = get heap
    ( ops, a`, top``) = f input a top`
    top``` = set a` top`` 


processOp :: (Op .a) .a -> .a;
processOp op heap = processOps newop top`
 where
  ( newop, top`) = op heap

processOps :: [Op .a] .a -> .a;
processOps [] heap = heap
processOps [op : tail] heap = processOps tail (processOp op heap)
  
// processing the operations

// example

:: Heap = {a :: .Obj , b :: .Obj}

:: Obj = {x :: Int , ptr :: (Obj -> ( Int , Obj)) Heap -> ( Int, Heap),
          ptrop ::  PtrOp Heap Obj}


heap :: .Heap
heap = {a = {x=1, ptr=b_ptrs.ptrVal, ptrop=b_ptrs.ptrOp} , b = {x=2, ptr=a_ptrs.ptrVal , ptrop=a_ptrs.ptrOp}}

a_ptrs = makePointers g s
 where
  s new heap = { heap & a = new }
  g heap = ( heap.a, { heap & a = undef })  
   // to preserve uniqueness I have to delete myself
   // from the heap, other objects may not try to use pointers to me, anyway 
   // they shouldn't have the heap variable, so they cannot.

b_ptrs = makePointers g s
 where
  s new heap = { heap & b = new }
  g heap = ( heap.b, { heap & b = undef })


chng obj heap = ( if (obj`.x<100) [obj`.ptrop chng] [], obj`, heap`)
 where
  obj` = { obj & x = obj.x+bx }
  ptr = obj.ptr
  ( bx, heap`) = ptr g heap
  g b = ( b.x, b)

/*   // these two at once do not work.
chng2 obj heap = ( if (obj`.x<100) [obj`.ptrop chng] [], obj`, heap`)
 where
  obj` = { obj & x = obj.x + toInt bx }
  ptr = obj.ptr
  ( bx, heap`) = ptr g heap
  g b = ( toReal b.x, b)
*/

Start = processOp (a_ptrs.ptrOp chng) heap


--------------53C86EF51C7D--