#1
  1. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69

    Scheme. Reduce & filter


    Hi all,

    I'm just learning Scheme in my spare time while at Uni. Currently trying to write a simplementation of filter & reduce. I think I have filter working pretty well, maybe not like I said I'm new. Here's my code:

    Code:
    (define filter
      (lambda (fn values)
        "This function is a tail recursive implementation of the filter function
        found in other Lisp dialect."
        (let loop ((v values)
                   (rest '()))
          
          (let ((item (car v))
                (next (cdr v)))             ; Saves the car and cdr for efficiency.
    
            (if (fn item)
              ;; Add the current 'item to 'rest if 'fn returned #t, then continue
              ;; though the list. Return 'this AND 'rest revsered.
              (if (pair? next)
                (loop next (cons item rest))
                (reverse (cons item rest)))
                
              ;; Don't add the 'item to the 'rest list but continue on though the
              ;; list.
              (if (pair? next)
                (loop next rest)
                (reverse rest)))))))
    If anyone has any comments or tips please let me know I'd be very happy to hear them.

    Mark.
    programming language development: www.netytan.com Hula

  2. #2
  3. fork while true;
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    May 2005
    Location
    England, UK
    Posts
    5,538
    Rep Power
    1051
    car and cdr are equivalent to first and rest right?

    wouldn't it make more sense to choose one standard and stick with it?

    EDIT: apart from that, looks good
    Last edited by LinuxPenguin; January 11th, 2006 at 02:15 PM.
  4. #3
  5. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69
    They are but it's not common to use first and rest for some reason, go figure .

    I'm happy migrating between them right now because they all seem to teach something different or better, I'm playing with Scheme to improve my recursion, which sucks to be fair .

    Plus I love how tidy it is, CL wins out for real world dev. Though only because of the massive number of library functions it includes. Quantity over quality, I haven't decided.

    It'll get better,

    take care and loves LP.

    Mark.
    programming language development: www.netytan.com Hula

  6. #4
  7. fork while true;
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    May 2005
    Location
    England, UK
    Posts
    5,538
    Rep Power
    1051
    Originally Posted by netytan
    They are but it's not common to use first and rest for some reason, go figure .
    Well, i blame all the old hippies who grew up when they were still registers... Miserable buggers

    >>I'm happy migrating between them right now because they all seem to teach something different or better, I'm playing with Scheme to improve my recursion, which sucks to be fair .

    Recursion is reasonably well done in C, but i guess in lisp where there's not much choice, it could improve some more.

    >>Plus I love how tidy it is, CL wins out for real world dev. Though only because of the massive number of library functions it includes. Quantity over quality, I haven't decided.

    Well net effect is you'll end up writing your own library if you go the scheme route, CL is there in one package.

    --James
  8. #5
  9. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69
    Originally Posted by LinuxPenguin
    Recursion is reasonably well done in C, but i guess in lisp where there's not much choice, it could improve some more.

    Well net effect is you'll end up writing your own library if you go the scheme route, CL is there in one package.
    Recursion in Lisp if it's done correctly is as efficient as iteration, on a decent implementation with a native machine-code compiler you can in theory get better than C performance or even without depending on task .

    Note: with a Lisp -> C compiler you would obviously get C's speed also.

    Can't fault you there though, Scheme by its very nature in minimal. There are few large libraries for different tasks but not included by default i.e. SLIB

    Mark.
    programming language development: www.netytan.com Hula

  10. #6
  11. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69
    With a little help from Jens on comp.lang.scheme I came up with a revised version of the function based on a peice of code he posted. This looks a lot cleaner and should run as fast if not faster .

    Code:
    (define filter
      (lambda (fn values)
        "This function is a tail recursive implementation of the filter
        function found in other Lisp dialect."
        (let loop ((v values)
                   (rest '()))
    
          ;; If there are items in v then CAR and CDR are saved; return
          ;; rest after reversing.
          ;;
          ;;   Checks if fn  => #t  -> add item to rest & repeat.
          ;;                 => #f  -> loop without adding item.
          (if (pair? v)
            (let ((item (car v))
                  (next (cdr v)))
              (if (fn item)
                (loop next (cons item rest))
                (loop next rest)))
              (reverse rest)))))
    This simply involved moving the if to the outside and then everything fell into place, as you can see there is no duplicate code here .

    Mark.
    programming language development: www.netytan.com Hula

  12. #7
  13. fork while true;
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    May 2005
    Location
    England, UK
    Posts
    5,538
    Rep Power
    1051
    problem with lisp in general, sometimes it's a bitch to work around the logic
  14. #8
  15. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69
    Just means you have to be more intelegent LP or practice more, the latter being my approach.

    Lisp really isn't hard to read once you know what you're looking at, else it's just looks like masses off odd words and symbols like any other programming language You Don't Understand .

    Anyway back to the awesomeness of Scheme macro programming.

    Later,

    Mark.
    programming language development: www.netytan.com Hula

  16. #9
  17. Commie Mutant Traitor
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2004
    Location
    Alpharetta, GA
    Posts
    1,806
    Rep Power
    1570
    You might want to take a look at the Scheme Request For Implementations (SRFIs), which are a system for defining semi-official libraries and extensions. The SRFI developers are working closely with the group working on R6RS, so there is some close collaboration on the direction Scheme will go in the future. Most current Scheme implementations support at least some SRFIs.

    As for Scheme compilers, I usually use Dr Scheme for development (it has what I consider one of the best IDEs around), but if I were looking to ship the result I'd switch to a native-code compiler first (after compatibility checking against the MIT reference implementation and perhaps a few other such as SCM, Scheme-48 and STK if the code doesn't use any R5RS-specific code). Chicken, Gambit-C , Bigloo and Scheme->C (the last of which is only R4RS, though) are each supposed to be quite efficient. For real crunch, though, the winner has to be STALIN , which may well be the most heavily optimizing compiler for any language to date. Though it does take a while to finish a build and it doesn't support the hygenic macros. If you still want to do one of your own, though, you might want to check out the "90 Minute Scheme to C Compiler" article that was mentioned on Lambda-The-Ultimate a couple years back.

    Comments on this post

    • netytan agrees
    Last edited by Schol-R-LEA; February 9th, 2006 at 06:32 AM.
    Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
    #define KINSEY (rand() % 7) λ Scheme is the Red Pill
    Scheme in Short Understanding the C/C++ Preprocessor
    Taming Python A Highly Opinionated Review of Programming Languages for the Novice, v1.1

    FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov
  18. #10
  19. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Location
    Hull, UK
    Posts
    2,537
    Rep Power
    69
    Originally Posted by Schol-R-LEA
    You might want to take a look at the Scheme Request For Implementations (SRFIs), which are a system for defining semi-official libraries and extensions. The SRFI developers are working closely with the group working on R6RS, so there is some close collaboration on the direction Scheme will go in the future. Most current Scheme implementations support at least some SRFIs.

    As for Scheme compilers, I usually use Dr Scheme for development (it has what I consider one of the best IDEs around), but if I were looking to ship the result I'd switch to a native-code compiler first (after compatibility checking against the MIT reference implementation and perhaps a few other such as SCM, Scheme-48 and STK if the code doesn't use any R5RS-specific code). Chicken, Gambit-C , Bigloo and Scheme->C (the last of which is only R4RS, though) are each supposed to be quite efficient. For real crunch, though, the winner has to be STALIN , which may well be the most heavily optimizing compiler for any language to date. Though it does take a while to finish a build and it doesn't support the hygenic macros. If you still want to do one of your own, though, you might want to check out the "90 Minute Scheme to C Compiler" article that was mentioned on Lambda-The-Ultimate a couple years back.
    thanks Schol, I'm going to look at the links you posted. Just downloading the movies. You're signature is actually what first took me too schemers.org what seems like a Very long time ago.

    Didn't actually get into it until recently, after learning CL .

    Thanks again!

    Mark.
    programming language development: www.netytan.com Hula


IMN logo majestic logo threadwatch logo seochat tools logo