A Scheme Idiom

June 16, 2017

We begin with a simple setter:

(define (make-setter x)
  (case-lambda
    (() x)
    ((y) (set! x y) x)))

> (define x (make-setter #f))
> x
#<procedure>
> (x)
#f
> (x "hello")
"hello"
> (x)
"hello"

Next we write an accumulator, as in the code I was reading:

(define (make-accumulator n)
  (case-lambda
    (() n)
    ((m) (set! n (+ n m)) n)))

> (define n (make-accumulator 10))
> (n)
10
> (n 20)
30
> (n)
30

Finally we have a setter for vectors:

(define (make-vector-setter vec)
  (case-lambda
    ((idx) (vector-ref vec idx))
    ((idx val) (vector-set! vec idx val) vec)))

> (define v (make-vector-setter (make-vector 3 #f)))
> (v 0 "hello")
#("hello" #f #f)
> (v 1 "goodbye")
#("hello" "goodbye" #f)
> (v 2 "Scheme is fun!")
#("hello" "goodbye" "Scheme is fun!")
> (v 2)
"Scheme is fun!"
> (v 0)
"hello"
> (v 1)
"goodbye"

This is useful because it simplifies the syntax for dealing with vectors. The standard method of incrementing a vector element looks like this:

(vector-set! vec idx (+ (vector-ref vec idx) 1))

But with the idiom, we can write it like this:

(vec idx (+ (vec idx) 1))

That’s simpler and easier to read. But it does come at a cost in execution time:

> (time (let ((vec (make-vector 100 0)))
          (do ((i 0 (+ i 1))) ((= i 1000000))
            (do ((j 0 (+ j 1))) ((= j 100))
              (vector-set! vec j
                (+ (vector-ref vec j) 1))))
          (vector-ref vec 50)))
(time (let ((...)) ...))
    17 collections
    9189 ms elapsed cpu time, including 0 ms collecting
    9214 ms elapsed real time, including 1 ms collecting
    72002728 bytes allocated, including 71454184 bytes reclaimed
1000000
> (time (let ((vec (make-vector-setter (make-vector 1000000 0))))
          (do ((i 0 (+ i 1))) ((= i 1000000))
            (do ((j 0 (+ j 1))) ((= j 100))
              (vec j (+ (vec j) 1))))
          (vec 50)))
(time (let ((...)) ...))
    208 collections
    15007 ms elapsed cpu time, including 30 ms collecting
    15018 ms elapsed real time, including 23 ms collecting
    876027512 bytes allocated, including 873920680 bytes reclaimed
1000000

Fifteen seconds versus nine seconds is a lot to pay for the readability and safety of the idiom, and probably explains why I’ve never seen it before. Regardless, it is a delightful way to show off the power of closures, and a good lesson in the power of Scheme; you can’t do that in most other languages.

You can run the program at http://ideone.com/7maOBT.

Advertisements

Pages: 1 2

3 Responses to “A Scheme Idiom”

  1. mcmillhj said

    Perl has a cool idiom that was borrowed from LISP called the Schwartzian transform, named after Randal Schwartz, the first person to document its use in Perl. The basic idea is that you have a potentially expensive computation that you need to run on N elements and then you need to sort them. The Schwartzian Transform avoids recomputing the expensive computation for last passes of the sort.

    This lets you do interesting things like:

    1. Sort strings by their length

    #!perl
    
    use strict;
    use warnings;
    
    use feature qw/say/;
    
    my @strings = qw/
      eren
      mikasa
      armin
      levi
      erwin
      reiner
      ymir
      historia
      bertholdt
      pixis
    /;
    
    say join "\n",
        map  { $_->[0]             }
        sort { $a->[1] cmp $b->[1] }
        map  { [$_, length($_)]    } @strings;
    
    # eren
    # levi
    # ymir
    # armin
    # erwin
    # pixis
    # mikasa
    # reiner
    # historia
    # bertholdt
    

    2. Sort IPv4 addresses numerically

    #!/usr/bin/perl
    
    use strict;
    use warnings;
    
    use feature qw/say/;
    
    my @ips = qw/
       213.61.108.26
       235.94.112.131
       162.219.166.100
       26.190.195.43
       96.113.27.227
       96.112.27.227
       96.112.29.227
       96.112.29.255
       164.124.74.26
       58.5.201.175
       228.131.119.187
       191.226.212.172
       65.70.48.227
       35.214.73.61
       149.14.104.245
    /;
    
    say join "\n",
        map  { join '.', @$_ }
        sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] || $a->[2] <=> $b->[2] || $a->[3] <=> $b->[3] }
        map  { [split /\./]  } @ips;
    
    # 26.190.195.43
    # 35.214.73.61
    # 58.5.201.175
    # 65.70.48.227
    # 96.112.27.227
    # 96.112.29.227
    # 96.112.29.255
    # 96.113.27.227
    # 149.14.104.245
    # 162.219.166.100
    # 164.124.74.26
    # 191.226.212.172
    # 213.61.108.26
    # 228.131.119.187
    # 235.94.112.131
    
  2. @programmingpraxis: Is this a closure? Seems I’ve seen something similar before and it was termed a closure.

  3. programmingpraxis said

    @bookofstevegraham: Yes, this is a closure. The value of the variable n is enclosed within the function, and not available to the rest of the program except through the interface defined by the function.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: