. sed script dc greg ubben sed stud

. sed script dc greg ubben sed stud

Post by Al A » Mon, 03 Mar 1997 04:00:00



[ comp.unix.wizards mod's note: a little off-topic, ]
[ but too incredible  to pass up...   includes some ]
[ sed resources at the end FYI, too.  --john        ]

---------- Forwarded message ----------
Date: Thu, 27 Feb 1997 14:15:15 -0500 (EST)
From: Greg Ubben <g...@romulus.ncsc.mil>
To: af...@torfree.net
Subject: dc.sed

Seders,

    Here is the big sed project I've been working on for fun -- a complete
implementation of the UNIX dc command!  If you've never used it before,
dc is an arbitrary precision reverse-polish (stacking) "desk" calculator.
Besides supporting calculations on very long numbers, it also handles
non-decimal input and output bases (even negative and fractional bases),
and has a set of stackable registers in which can be stored numbers,
strings, or executable macros.  For details on operating dc, see the dc
manual page on any UNIX system or on the web (one URL you can use is
http://www.delorie.com/gnu/docs/bc/dc.1.html).  But here's a short demo:

$ ./dc.sed              # start running dc.sed interactively
10k                     # set the scale (fractional digits) to 10
_375 2.5 .716 +/p       # compute and print -375 / (2.5 + .716)
                        # hit return again to see result
sa                      # store the last result (still on stack) in register a
la d *p                 # load register a, duplicate, square, and print
                        # hit return again to see result
vp                      # now take square root and print
q                       # we're done - quit (hit return twice)

    Note that because sed reads ahead a line, you have to hit RETURN twice
to see the effects of your last command.  Of course, the script is limited
by the size of your sed's buffer.  This is about 4000 characters on SunOS
-- enough for you to sling around 500-digit numbers if there's not much on
the stack or in registers, and you don't mind waiting a few hours for your
answer.  As far as I know, dc.sed is actually less buggy than the UNIX and
GNU versions, barring the memory and speed limitations.  Let me know if you
find any bugs.

    This script is actually surprisingly fast using SunOS 4.1.4 /bin/sed.
On my Sun host, it calculates 10k2vp (sqrt(2) to 10 places) in just a
couple seconds.  However GNU sed 2.05 (compiled with cc -O2) was 168 times
slower.  (304 times slower with cc -g)  In real time, I watched a 1-hour
TV show waiting for GNU sed to finish the calculation.  I'd be interested
in hearing experiences running it on other sed implementations.  It should
give any sed a good work-out, and would make a good test to profile GNU
sed against to find the bottlenecks.

    Another limitation you may run into is the number of sed commands.
I had to really squeeze to get this script to fit into the 199-command
limit on SunOS.  If your sed has lower limits, you may be out of luck.

    What few explanatory comments there were have been removed from this
copy of the script just to make it more obfuscated and interesting.  :-)
I may post a better-commented version later if there's interest.  If you
want to try to tinker, here's an exercise:  see if you can add a "pi"
command that will push the number 3.14159265 on the stack.  As an advanced
(difficult) exercise for hard-core hackers, try implementing associative
arrays per my comments in the script.  In any case, enjoy, and never again
let it be said that sed can't do arithmetic.

Next time:  perl.sed  (whfg xvqqvat)

Greg

------------------------------------------------------------------------
#!/bin/sed -f
#  dc.sed - an arbitrary precision RPN calculator
#  Created by Greg Ubben <g...@romulus.ncsc.mil> early 1995, late 1996
#
#  Dedicated to MAC's memory of the IBM 1620 ("CADET") computer.
#  @(#)GSU dc.sed 1.0 27-Feb-1997 [non-explanatory]
#
#  Examples:
#       sqrt(2) to 10 digits:   echo "10k 2vp" | dc.sed
#       20 factorial:           echo "[d1-d1<!*]s! 20l!xp" | dc.sed
#       sin(ln(7)):             echo "s(l(7))" | bc -c /usr/lib/lib.b | dc.sed
#       hex to base 60:         echo "60o16i 6B407.CAFE p" | dc.sed
#
#  To debug or analyze, give the dc Y command as input or add it to
#  embedded dc routines, or add the sed p command to the beginning of
#  the main loop or at various points in the low-level sed routines.
#  If you need to allow [|~] characters in the input, filter this
#  script through "tr '|~' '\36\37'" first.
#
#  Not implemented:     ! \
#  But implemented:     K Y t # !< !> != fractional-bases
#  SunOS limits:        199/199 commands (though could pack in 10-20 more)
#  Limitations:         scale <= 999; |obase| >= 1; input digits in [0..F]
#  Completed:           1am Feb 4, 1997

s/^/|P|K0|I10|O10|?~/

: next
s/|?./|?/
s/|?#[   -}]*/|?/
/|?!*[lLsS;:<>=]\{0,1\}$/N
/|?!*[-+*/%^<>=]/b binop
/^|.*|?[dpPfQXZvxkiosStT;:]/b binop
/|?[_0-9A-F.]/b number
/|?\[/b string
/|?l/b load
/|?L/b Load
/|?[sS]/b save
/|?c/ s/[^|]*//
/|?d/ s/[^~]*~/&&/
/|?f/ s//&[pSbz0<aLb]dSaxsaLa/
/|?x/ s/\([^~]*~\)\(.*|?x\)~*/\2\1/
/|?[KIO]/ s/.*|\([KIO]\)\([^|]*\).*|?\1/\2~&/
/|?T/ s/\.*0*~/~/
#  a slow, non-stackable array implementation in dc, just for completeness
#  A fast, stackable, associative array implementation could be done in sed
#  (format: {key}value{key}value...), but would be longer, like load & save.
/|?;/ s/|?;\([^{}]\)/|?~[s}s{L{s}q]S}[S}l\1L}1-d0>}s\1L\1l{xS\1]dS{xL}/
/|?:/ s/|?:\([^{}]\)/|?~[s}L{s}L{s}L}s\1q]S}S}S{[L}1-d0>}S}l\1s\1L\1l{xS\1]dS{x/
/|?[ ~  cdfxKIOT]/b next
/|?\n/b next
/|?[pP]/b print
/|?k/ s/^\([0-9]\{1,3\}\)\([.~].*|K\)[^|]*/\2\1/
/|?i/ s/^\(-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}\)\(~.*|I\)[^|]*/\2\1/
/|?o/ s/^\(-\{0,1\}[1-9][0-9]*\.\{0,1\}[0-9]*\)\(~.*|O\)[^|]*/\2\1/
/|?[kio]/b pop
/|?t/b trunc
/|??/b input
/|?Q/b break
/|?q/b quit
h
/|?[XZz]/b count
/|?v/b sqrt
s/.*|?\([^Y]\).*/\1 is unimplemented/
s/\n/\\n/g
l
g
b next

: print
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~.*|?p/!b Print
/|O10|/b Print

#  Print a number in a non-decimal output base.  Uses registers a,b,c,d.
#  Handles fractional output bases (O<-1 or O>=1), unlike other dc's.
#  Converts the fraction correctly on negative output bases, unlike
#  UNIX dc.  Also scales the fraction more accurately than UNIX dc.
#
s,|?p,&KSa0kd[[-]Psa0la-]Sad0>a[0P]sad0=a[A*2+]saOtd0>a1-ZSd[[[[ ]P]sclb1\
!=cSbLdlbtZ[[[-]P0lb-sb]sclb0>c1+]sclb0!<c[0P1+dld>c]scdld>cscSdLbP]q]Sb\
[t[1P1-d0<c]scd0<c]ScO_1>bO1!<cO[16]<bOX0<b[[q]sc[dSbdA>c[A]sbdA=c[B]sbd\
B=c[C]sbdC=c[D]sbdD=c[E]sbdE=c[F]sb]xscLbP]~Sd[dtdZOZ+k1O/Tdsb[.5]*[.1]O\
X^*dZkdXK-1+ktsc0kdSb-[Lbdlb*lc+tdSbO*-lb0!=aldx]dsaxLbsb]sad1!>a[[.]POX\
+sb1[SbO*dtdldx-LbO*dZlb!<a]dsax]sadXd0<asbsasaLasbLbscLcsdLdsdLdLak[]pP,
b next

: Print
/|?p/s/[^~]*/&\
~&/
s/\(.*|P\)\([^|]*\)/\
\2\1/
s/\([^~]*\)\n\([^~]*\)\(.*|P\)/\1\3\2/
h
s/~.*//
/./{ s/.//; p; }
#  Just s/.//p would work if we knew we were running under the -n option.
#  Using l vs p would kind of do \ continuations, but would break strings.
g

: pop
s/[^~]*~//
b next

: load
s/\(.*|?.\)\(.\)/\20~\1/
s/^\(.\)0\(.*|r\1\([^~|]*\)~\)/\1\3\2/
s/.//
b next

: Load
s/\(.*|?.\)\(.\)/\2\1/
s/^\(.\)\(.*|r\1\)\([^~|]*~\)/|\3\2/
/^|/!i\
register empty
s/.//
b next

: save
s/\(.*|?.\)\(.\)/\2\1/
/^\(.\).*|r\1/ !s/\(.\).*|/&r\1|/
/|?S/ s/\(.\).*|r\1/&~/
s/\(.\)\([^~]*~\)\(.*|r\1\)[^~|]*~\{0,1\}/\3\2/
b next

: quit
t quit
s/|?[^~]*~[^~]*~/|?q/
t next
#  Really should be using the -n option to avoid printing a final newline.
s/.*|P\([^|]*\).*/\1/
q

: break
s/[0-9]*/&;987654321009;/
: break1
s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^;]*\3\(9*\).*|?.\)[^~]*~/\1\5\6\4/
t break1
b pop

: input
N
s/|??\(.*\)\(\n.*\)/|?\2~\1/
b next

: count
/|?Z/ s/~.*//
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}$/ s/[-.0]*\([^.]*\)\.*/\1/
/|?X/ s/-*[0-9A-F]*\.*\([0-9A-F]*\).*/\1/
s/|.*//
/~/ s/[^~]//g

s/./a/g
: count1
        s/a\{10\}/b/g
        s/b*a*/&a9876543210;/
        s/a.\{9\}\(.\).*;/\1/
        y/b/a/
/a/b count1
G
/|?z/ s/\n/&~/
s/\n[^~]*//
b next

: trunc
#  for efficiency, doesn't pad with 0s, so 10k 2 5/ returns just .40
#  The X* here and in a couple other places works around a SunOS 4.x sed bug.
s/\([^.~]*\.*\)\(.*|K\([^|]*\)\)/\3;9876543210009909:\1,\2/
: trunc1
        s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^:]*X*\3\(9*\)[^,]*\),\([0-9]\)/\1\5\6\4\7,/
t trunc1
s/[^:]*:\([^,]*\)[^~]*/\1/
b normal

: number
s/\(.*|?\)\(_\{0,1\}[0-9A-F]*\.\{0,1\}[0-9A-F]*\)/\2~\1~/
s/^_/-/
/^[^A-F~]*~.*|I10|/b normal
/^[-0.]*~/b normal
s:\([^.~]*\)\.*\([^~]*\):[Ilb^lbk/,\1\2~0A1B2C3D4E5F1=11223344556677889900;.\2:
: digit
    s/^\([^,]*\),\(-*\)\([0-F]\)\([^;]*\(.\)\3[^1;]*\(1*\)\)/I*+\1\2\6\5~,\2\4/
t digit
s:...\([^/]*.\)\([^,]*\)[^.]*\(.*|?.\):\2\3KSb[99]k\1]SaSaXSbLalb0<aLakLbktLbk:
b next

: string
/|?[^]]*$/N
s/\(|?[^]]*\)\[\([^]]*\)]/\1|{\2|}/
/|?\[/b string
s/\(.*|?\)|{\(.*\)|}/\2~\1[/
s/|{/[/g
s/|}/]/g
b next

: binop
/^[^~|]*~[^|]/ !i\
stack empty
//!b next
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/[^~]*\(.*|?!*[^!=<>]\)/0\1/
/^[^~]*~-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/~[^~]*\(.*|?!*[^!=<>]\)/~0\1/
h
/|?\*/b mul
/|?\//b div
/|?%/b rem
/|?^/b exp

/|?[+-]/ s/^\(-*\)\([^~]*~\)\(-*\)\([^~]*~\).*|?\(-\{0,1\}\).*/\2\4s\3o\1\3\5/
s/\([^.~]*\)\([^~]*~[^.~]*\)\(.*\)/<\1,\2,\3|=-~.0,123456789<></
/^<\([^,]*,[^~]*\)\.*0*~\1\.*0*~/ s/</=/
: cmp1
        s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/
t cmp1
/^<\([^~]*\)\([^~]\)[^~]*~\1\(.\).*|=.*\3.*\2/ s/</>/
/|?/{
        s/^\([<>]\)\(-[^~]*~-.*\1\)\(.\)/\3\2/
        s/^\(.\)\(.*|?!*\)\1/\2!\1/
        s/|?![^!]\(.\)/&l\1x/
        s/[^~]*~[^~]*~\(.*|?\)!*.\(.*\)|=.*/\1\2/
        b next
}
s/\(-*\)\1|=.*/;9876543210;9876543210/
/o-/ s/;9876543210/;0123456789/
s/^>\([^~]*~\)\([^~]*~\)s\(-*\)\(-*o\3\(-*\)\)/>\2\1s\5\4/

s/,\([0-9]*\)\.*\([^,]*\),\([0-9]*\)\.*\([0-9]*\)/\1,\2\3.,\4;0/
: right1
        s/,\([0-9]\)\([^,]*\),;*\([0-9]\)\([0-9]*\);*0*/\1,\2\3,\4;0/
t right1
s/.\([^,]*\),~\(.*\);0~s\(-*\)o-*/\1~\30\2~/

: addsub1
        s/\(.\{0,1\}\)\(~[^,]*\)\([0-9]\)\(\.*\),\([^;]*\)\(;\([^;]*\(\3[^;]*\)\).*X*\1\(.*\)\)/\2,\4\5\9\8\7\6/
        s/,\([^~]*~\).\{10\}\(.\)[^;]\{0,9\}\([^;]\{0,1\}\)[^;]*/,\2\1\3/
        #  could be done in one s/// if we could have >9 back-refs...
/^~.*~;/!b addsub1

: endbin
s/.\([^,]*\),\([0-9.]*\).*/\1\2/
G
s/\n[^~]*~[^~]*//

: normal
s/^\(-*\)0*\([0-9.]*[0-9]\)[^~]*/\1\2/
s/^[^1-9~]*~/0~/
b next

: mul
s/\(-*\)\([0-9]*\)\.*\([0-9]*\)~\(-*\)\([0-9]*\)\.*\([0-9]*\).*|K\([^|]*\).*/\1\4\2\5.!\3\6,|\2<\3~\5>\6:\7;9876543210009909/

: mul1
    s/![0-9]\([^<]*\)<\([0-9]\{0,1\}\)\([^>]*\)>\([0-9]\{0,1\}\)/0!\1\2<\3\4>/
    /![0-9]/ s/\(:[^;]*\)\([1-9]\)\(0*\)\([^0]*\2\(.\).*X*\3\(9*\)\)/\1\5\6\4/
/<~[^>]*>:0*;/!t mul1

s/\(-*\)\1\([^>]*\).*/;\2^>:9876543210aaaaaaaaa/

: mul2
    s/\([0-9]~*\)^/^\1/
    s/<\([0-9]*\)\(.*[~^]\)\([0-9]*\)>/\1<\2>\3/

    : mul3
        s/>\([0-9]\)\(.*\1.\{9\}\(a*\)\)/\1>\2;9\38\37\36\35\34\33\32\31\30/
        s/\(;[^<]*\)\([0-9]\)<\([^;]*\).*\2[0-9]*\(.*\)/\4\1<\2\3/
        s/a[0-9]/a/g
        s/a\{10\}/b/g
        s/b\{10\}/c/g
    /|0*[1-9][^>]*>0*[1-9]/b mul3

    s/;/a9876543210;/
    s/a.\{9\}\(.\)[^;]*\([^,]*\)[0-9]\([.!]*\),/\2,\1\3/
    y/cb/ba/
/|<^/!b mul2
b endbin

: div
#  CDDET
/^[-.0]*[1-9]/ !i\
divide by 0
//!b pop
s/\(-*\)\([0-9]*\)\.*\([^~]*~-*\)\([0-9]*\)\.*\([^~]*\)/\2.\3\1;0\4.\5;0/
: div1
        s/^\.0\([^.]*\)\.;*\([0-9]\)\([0-9]*\);*0*/.\1\2.\3;0/
        s/^\([^.]*\)\([0-9]\)\.\([^;]*;\)0*\([0-9]*\)\([0-9]\)\./\1.\2\30\4.\5/
t div1
s/~\(-*\)\1\(-*\);0*\([^;]*[0-9]\)[^~]*/~123456789743222111~\2\3/
s/\(.\(.\)[^~]*\)[^9]*\2.\{8\}\(.\)[^~]*/\3~\1/
s,|?.,&SaSadSaKdlaZ+LaX-1+[sb1]Sbd1>bkLatsbLa[dSa2lbla*-*dLa!=a]dSaxsakLasbLb*t,
b next

: rem
s,|?%,&Sadla/LaKSa[999]k*Lak-,
b next

: exp
#  This decimal method is just a little faster than the binary method done
#  totally in dc:  1LaKLb [kdSb*LbK]Sb [[.5]*d0ktdSa<bkd*KLad1<a]Sa d1<a kk*
/^[^~]*\./i\
fraction in exponent ignored
s,[^-0-9].*,;9d**dd*8*d*d7dd**d*6d**d5d*d*4*d3d*2lbd**1lb*0,
: exp1
        s/\([0-9]\);\(.*\1\([d*]*\)[^l]*\([^*]*\)\(\**\)\)/;dd*d**d*\4\3\5\2/
t exp1
G
s,-*.\{9\}\([^9]*\)[^0]*0.\(.*|?.\),\2~saSaKdsaLb0kLbkK*+k1\1LaktsbkLax,
s,|?.,&SadSbdXSaZla-SbKLaLadSb[0Lb-d1lb-*d+K+0kkSb[1Lb/]q]Sa0>a[dk]sadK<a[Lb],
b next

: sqrt
#  first square root using sed:  8k2v at 1:30am Dec 17, 1996
/^-/i\
square root of negative number
/^[-0]/b next
s/~.*//
/^\./ s/0\([0-9]\)/\1/g
/^\./ !s/[0-9][0-9]/7/g
G
s/\n/~/
s,|?.,&KSbSb[dk]SadXdK<asadlb/lb+[.5]*[sbdlb/lb+[.5]*dlb>a]dsaxsasaLbsaLatLbk,
b next

#  END OF GSU dc.sed
=============================================================================

---------- Forwarded message ----------
Date: Fri, 28 Feb 1997 10:01:06 -0000
From: Casper BodenCummins <bo...@Sherwood.co.uk>
To: 'Al Aab' <af...@freenet.toronto.on.ca>
Subject: Hahahaaa! (dc.sed)

I just got Greg's script. This is *soo* neat. I had trouble not laughing
out loud in the office. To think that it's faster and possibly more
accurate than a C implementation of dc!

This one's going up on my wall at home for posterity. Might even make a
T-shirt of it.

See you,
Casper.
--
Very delighted.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    for a 1stop sed needs, join seders, the informal sed mailing list.      
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                        sed informal mailin list
af...@torfree.net                 seders informal mailing list & moderator

                                ----

                           3 sed web pages

http://www.wollery.demon.co.uk   seders grab bag (seders official web page)
                                             hosted by a seder,
                                                  Casper.
http://www.math.fu-berlin.de/~guckes/sed/       run by a seder, Herr Guckes
http://www.math.fu-berlin.de/~leitner/sed/     run by a seder, Herr Leitner
http://www.dbnet.ece.ntua.gr/~george/#seders  seder, engineer, Dr2b Yiorgos

                                ----

                       my favourite DOS/UNIX sed :

 ftp://uiarchive.uiuc.edu/pub/systems/pc/simtelnet/msdos/txtutl/sed15.zip
 ftp://uiarchive.uiuc.edu/pub/systems/pc/simtelnet/msdos/txtutl/sed15x...

Directory: /pub/systems/pc/simtelnet/msdos/txtutl/
Filename    Type Length  Date    Description
===============================================================================
sed15.zip    B    62082  910930  Unix-compatible streaming editor v1.5 TC src
sed15x.zip   B    20300  910930  Unix-compatible streaming editor v1.5 EXE/docs

              sed15.zip has C source, compilable for UNIX.

             Also, check simtel for u-sedit. has nice docs.

                                ----

                        alt.comp.editors.batch            

             seders news group (much more than just  sed),
                  hosted by a seder, engineer Yiorgos.    

         most newsfeeds do not carry alt.comp.editors.batch
         but everyone can get it via  dejanews (and others)
  you can even follow up, reply to the poster, etc.  dejanews is great

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~