[plt-scheme] append!?

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Mon Oct 22 09:46:54 EDT 2007

You're correct of course. My message was tongue-in-cheek but just a bit.

A few things to think about:
  -- is Scheme a functional programming language?
  -- if so, what do you make of set!, set-cdr!, append! and friends?
  -- if you still agree that Scheme is a functional language, is Java  
such a language, too?
     (I claim its linguistics are but its implementation and its  
libraries are biased against FP (and OOP, see below))
  -- how about C? I can do FP in that language, if you allow the  
above primitives and ignore the lib issue.
     Indeed gcc is somewhat better for that purpose than javac on my  
machine. Though I will need to link in a gcc.
     (And pretty soon, my code will look like Matthew's.)

So what is FP? I'd like to propose the alternative of value-oriented  
programming:

  -- think of sets of values: V
  -- operations for creating them
       make-foo : X Y Z .. -> V for X, Y, Z of different sets of values

  -- operations for de-structuring them
       foo-select : V -> X

and if you really want to
  -- operations for mutating them
       foo-change : V X -> DONE
       where DONE = { 'the-mutation-is-finished }

Then programming is the task of creating functions that map sets of  
values to (other) sets of values

    program : V -> U

Specifically, it's about choosing operations for de-structuring the  
given inputs, creating (possibly temporary intermediate) values from  
other values, and returning such values. Sprinkle mutations in where  
needed. Compose existing programs when you can. (Think of if as an  
operation on booleans.)

In short, FP is a style of programming. Since OOP is about sending  
messages to objects and to combine the results with additional  
messages and constructors, what is the difference between FP and OOP?  
If OOPL designers were faithful to their origins, they'd equip their  
compilers with TCO (tail-call optimizations) and -- modulo syntax --  
you'd notice very little difference between OOP and FP (in Scheme).  
Not surprising of course if you think about the history of languages.

Sadly, most OOPL designers have instead chosen to create a pathway  
for imperative programmers -- EEs who masquerade as programmers by  
composing changes to the machine state with ";" -- and have  
sacrificed a huge part of the OO philosophy in return. As a result,  
these languages are really just low-level ImpPLs with OO features as  
decoration.

-- Matthias







On Oct 21, 2007, at 10:37 PM, Robert Nikander wrote:

> I know more about dysfunctional programming.
>
> I shouldn't have said you "can't" write a recursive function with  
> that list type.  I just meant that it is more convenient to write  
> recursive functions with the normal scheme lists.
>
> Rob
>
> On Oct 21, 2007, at 9:52 PM, Matthias Felleisen wrote:
>
>> I don't know what functional programming is but Kazimir's type  
>> description is perfectly fine data description for Scheme:
>>
>>   ListB is (box List)
>>
>>   List is one of:
>>    -- null
>>    -- (cons Data List)
>>
>>   Note: List is the built-in type.
>>
>> Now you really want to "lift" functions from the built-in type  
>> List to ListB, e.g.,
>>
>>  (define (mapB f l)
>>    (set-box! l (map f (unbox l))))
>>
>>  (define (appendB l1 l2)
>>    (set-box! l1 (append l1 l2)))
>>
>> etc.
>>
>> All he loses is the immediate applicability of the existing  
>> library. Ugly but doable.
>>
>> Unless he meant something else. -- Matthias
>>
>>
>> On Oct 21, 2007, at 8:32 PM, Robert Nikander wrote:
>>
>>>
>>> On Oct 21, 2007, at 6:45 PM, Majorinc, Kazimir wrote:
>>>>
>>>> type list is record
>>>>   next: (pointer to node) or NIL;
>>>> end
>>>> type node is record
>>>>  data: pointer to anything;
>>>>  next: (pointer to node) or NIL
>>>> end
>>>>
>>>> On that way there is no significant difference between empty and  
>>>> non-empty list, both are mutable. Obviously, it is not the Lisp  
>>>> way - but it begs for the question, why not? Did original  
>>>> designer or anyone else discussed it in some serious  
>>>> publication, or it was taken for granted without much  
>>>> questioning? I know, it is almost trivial topic, but I suspect  
>>>> it caused small but numerous troubles to Lisp users and  
>>>> implementors due to unnecessarily special nature of the empty list.
>>>
>>>
>>> It sounds like the problems you are talking about come from  
>>> trying to write imperative style in the functional language.
>>>
>>> The type above is a problem for recursive functions because  
>>> "next" is not a list, so you can't process the first item and  
>>> recurse on the rest.
>>>
>>> So, how do you iterate through the list?  Many imperative  
>>> languages have the concept of an "iterator", but often they  
>>> mutate, so you can't hang on to one as a pointer into your list.   
>>> If you try to create a "functional iterator", I bet you'll find  
>>> yourself reinventing the Lisp-style list -- your "iterator" will  
>>> have three operations, something like "done?" "current-item" and  
>>> "next".  And "next" will return a new iterator, not mutate  
>>> anything.  In other words, you'll have: null?, car, cdr.
>>>
>>> Rob
>>>
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>



Posted on the users mailing list.