Re: Cocoa semantics
Re: Cocoa semantics
- Subject: Re: Cocoa semantics
- From: Steven Majewski <email@hidden>
- Date: Sat, 17 Jul 2004 22:53:55 -0400
Tom,
You don't want to copy lists -- as others have pointed out, this
makes the performance of list operations like CONS vary according to
the length of the list.
Most functional programming languages build lists with reference
semantics. I say "reference semantics" rather than just "references"
because sometimes they will handle small "unboxed" immutable objects
(like integers) as values -- but since they are immutable, it doesn't
matter.
What a functional language does to avoid the problem you point out
is just to make those larger units also immutable -- forbidding all
those
sort of 'remove the last value' type operations.
A 'pure' functional language does not give you any way to do those
forbidden operations.
An 'impure' functional language like Lisp, can be used in a functional
style -- all you do is avoid using things like REPLACA or REPLACD which
change the state of an existing list.
You seem to be missing the point in your comments about loosing
access to the earlier version of the list. That really has nothing to
do with functional programming. You can keep references to all of the
sublists -- as long as THOSE SUBLISTS DO NOT CHANGE STATE.
There is a style of functional programming that doesn't use assignment,
but there is also another style call 'single assignment' that views
assignment as name binding. It doesn't matter if you keep and use those
names to reference those sublists. What is important is that you can't
change those sublists.
Does that make any more sense ?
-- Steve Majewski
On Jul 16, 2004, at 3:00 PM, Tom Davie wrote:
Hi,
I've been writing a very basic linked list class in Objective-C, and
have been having trouble thinking out exactly what the correct
semantics for a linked list is when using Objective-C. I am starting
looking at the list from a functional programming standpoint in which
the semantics are easy. You simply have two constructions: the empty
list (denoted []); and a method of constructing a new list from an
item and another list (denoted ':'), so for example the list
containing 2, 5, and 7 is made up by starting with the empty list ([])
adding 7 to it (7:[]), adding 5 to it (5:(7:[])), and then adding 2 to
it (2:(5:(7:[]))). Because this is a functional paradigm, there is no
state, so when you add 2 to the list, you loose access to what you had
before and (5:(7:[])) no longer exists on it's own - instead it is
only the tail of the new list.
When looking at this from the point of view of Objective-C, things
become quite a bit more complex. If we are to simply duplicate the
behavior of the functional model then we hit a problem. The empty
list constructor is relatively easy b we simply write something like
this:
+ (id)emptyList
{
return [[[LinkedList alloc] init] autorelease];
}
The cons operator though (:) is more complex, because after the
operation has happened we still have access to the tail end of the
list by other means i.e. if we have a linked list a and we then say b
= [LinkedList cons:newItem to:a];, we still have access to a, so then
doing [a removeItemAtIndex:5]; also has the side effect of removing
something from b. After much thought I think that I have found the
correct semantics for the class, but I wanted to check if my thoughts
matched those of the rest of the cocoa world. The conclusion I have
come to is that a class operator similar to cons should be provided,
but should in fact copy the old list, so b=[LinkedList cons:newItem
to:a]; would in fact create two entirely separate lists a and b, where
the contents of a also happen to be the contents of b (b having the
extra element newItem). Secondly, an object method should be provided
that would work as [a addItemToFront:newItem]; which simply modifies a
to be a list with newItem added first (much like cons, but not
returning the new list, instead modifying the original).
Your thoughts would be much appreciated.
Thanks
Tom Davie
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.