[plt-scheme] append!?

From: Sam TH (samth at ccs.neu.edu)
Date: Mon Oct 22 11:06:17 EDT 2007

I suppose that any CPS program can be written in C by lambda-lifting
all the closures to the top level, so I guess it counts.  The lack of
tail calls are a problem, though.

sam th

On 10/22/07, Robby Findler <robby at cs.uchicago.edu> wrote:
> 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
> >
>


-- 
sam th
samth at ccs.neu.edu


Posted on the users mailing list.