[plt-scheme] append!?

From: Robby Findler (robby at cs.uchicago.edu)
Date: Mon Oct 22 10:55:48 EDT 2007

You mean programming with explicit closures somehow doesn't count? (I
can probably make C macros that help me avoid most of the boilerplate
associated with it.)

Robby

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


Posted on the users mailing list.