Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #3175

Re: Auto-caching, memoizing

Show all headers | View raw

On Saturday, August 26, 2017 at 11:53:07 PM UTC-5, luser droog wrote:

> For the benefit of spectators, here's some additional commentary.
> 
> > Norah@laptop ~
> > $ cat memo.ps
> > %!
> 
> We start with two procedures /pusherr and /poperr which provide
> the capability of stacking error handlers. They're a little weird
> because they use the regular operand stack as the stack as well
> as using the stack for argument passing. So /pusherr, after a 
> casual glance at the stack effect comment, might appear not to
> do anything useful at all. But it installs the new handler given
> as an argument and returns the old handler. And /poperr takes
> an argument handler and simply installs it. 
> 
> Don't worry. It /is/ confusing.
> 
> > 
> > <<
> > /pusherr { % /errname {handler}  -->  /errname {old-handler}
> >     errordict 3 1 roll  % d n p
> >     3 copy pop get      % d n p op
> >     2 index exch 5 2 roll put
> > }
> > 
> > /poperr { % /errname {handler}
> >     errordict 3 1 roll put
> > }
> > 
> 
> I probably could factor it to use /poperr in the code for /pusherr.
> Or something internally complicated, maintaining a stack data structure,
> in exchange for a cleaner interface... hmmm....
> 
> On to the meat, ...
> 
> > /memo-func {
> >     {
> >         DICT begin
> >         /undefined { pop dup default dup 3 1 roll def } pusherr 3 2 roll
> >             load
> >         3 1 roll poperr
> >         end
> >     }
> >     dup length array copy
> >     dup 3 2 roll 0 exch put cvx
> > }
> > >> begin
> > 
> 
> If you've been following my other recent threads, the idea should
> be familiar. It's generating a procedure body specified by the
> template but with the DICT replaced by the dict argument.
> 
> The resulting procedure simply pushes the local dict (again this
> should be familiar), then pushes an error handler for the /undefined
> error, then just does `load`, and pops the handler and the dict.
> 
> The error handler calls the procedure named /default and saves
> the input and output as a new definition in the local dict.
> 
> > 
> > /fib <<
> >     0 1
> >     1 1
> >     /default { dup 2 sub fib  exch 1 sub fib  add }
> > >> 100 dict copy  memo-func  def
> > 
> > 0 1 25 {  fib =  } for
> > 
> 
> And the usage. Pretty close to the textbook mathematical form, I think.
> 
> fib(x) = { 0 -> 1
>          | 1 -> 1
>          { fib(x-2) + fib(x-1)
> 
> And it runs, produces good looking results, and pretty fast! Hurray!
> 
> > 
> > Norah@laptop ~
> > $ time gsnd -dBATCH memo.ps
> > GPL Ghostscript 9.19 (2016-03-23)
> > Copyright (C) 2016 Artifex Software, Inc.  All rights reserved.
> > This software comes with NO WARRANTY: see the file PUBLIC for details.
> > 1
> > 1
> > 2
> > 3
> > 5
> > 8
> > 13
> > 21
> > 34
> > 55
> > 89
> > 144
> > 233
> > 377
> > 610
> > 987
> > 1597
> > 2584
> > 4181
> > 6765
> > 10946
> > 17711
> > 28657
> > 46368
> > 75025
> > 121393
> > 
> > real    0m0.167s
> > user    0m0.109s
> > sys     0m0.030s

Here's an updated version which maintains an internal stack as lisp-like
linked-list. I think it makes the code much nicer to read by removing
the extra stack juggling. But it's a little slower than the stackwise
version according to naive testing. It allocates lots of 2- and 3- element
arrays for its data.

%!                                                                                                                 

<<
/errorstack null  % [ {errordict/errname{handler}} null ]                                                          

/pusherr {
    errordict 3 1 roll 3 copy pop 2 copy get    % ed /n {new} ed /n {old}                                          
    3 array astore cvx  errorstack   2 array astore  /errorstack exch store
    put
}

/poperr {
    errorstack dup null ne {
        aload pop  /errorstack exch store
        exec put
    } if
}

/memo-func {
    {
        DICT begin
            /undefined { pop dup default dup 3 1 roll def } pusherr
                load
            poperr
        end
    }
    dup length array copy
    dup 3 2 roll 0 exch put cvx
}
>> begin


/fib <<
    0 1
    1 1
    /default { dup 2 sub fib  exch 1 sub fib  add }
>> 100 dict copy  memo-func  def

0 1 100 {  fib =  } for

Back to comp.lang.postscript | Previous | Next — Previous in thread | Find similar

Thread

Auto-caching, memoizing luser droog <luser.droog@gmail.com> - 2017-08-23 13:10 -0700
  Re: Auto-caching, memoizing luser droog <luser.droog@gmail.com> - 2017-08-23 13:33 -0700
    Re: Auto-caching, memoizing luser droog <luser.droog@gmail.com> - 2017-08-23 13:38 -0700
      Re: Auto-caching, memoizing luser droog <luser.droog@gmail.com> - 2017-08-23 13:40 -0700
        Re: Auto-caching, memoizing luser droog <luser.droog@gmail.com> - 2017-08-26 21:53 -0700
          Re: Auto-caching, memoizing luser droog <luser.droog@gmail.com> - 2017-09-02 20:16 -0700

csiph-web