[plt-scheme] append!?

Personally, I've always liked Joe Marshall's definition of a
functional language as one that you can program in CPS in.  This
includes Scheme, but not C, and maybe not Java.

sam th

On 10/22/07, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>
> 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
> >
>
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>


-- 
sam th
samth at ccs.neu.edu