Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #7710 > unrolled thread
| Started by | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| First post | 2011-12-03 19:07 +0000 |
| Last post | 2011-12-08 03:37 -0600 |
| Articles | 20 on this page of 187 — 17 participants |
Back to article view | Back to comp.lang.forth
Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-03 19:07 +0000
Re: Memoizing recursive words "A. K." <akk@nospam.org> - 2011-12-04 13:21 +0100
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-04 14:20 +0000
Re: Memoizing recursive words Josh Grams <josh@qualdan.com> - 2011-12-04 16:03 +0000
Re: Memoizing recursive words "A. K." <akk@nospam.org> - 2011-12-04 17:25 +0100
Re: Memoizing recursive words BruceMcF <agila61@netscape.net> - 2011-12-04 10:51 -0800
Re: Memoizing recursive words "Elizabeth D. Rather" <erather@forth.com> - 2011-12-04 12:50 -1000
Re: Memoizing recursive words BruceMcF <agila61@netscape.net> - 2011-12-04 15:40 -0800
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-05 11:17 +0000
Re: Memoizing recursive words "Elizabeth D. Rather" <erather@forth.com> - 2011-12-04 08:24 -1000
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-04 19:14 +0000
Re: Memoizing recursive words BruceMcF <agila61@netscape.net> - 2011-12-04 12:09 -0800
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-05 04:00 +0000
Re: Memoizing recursive words BruceMcF <agila61@netscape.net> - 2011-12-07 12:41 -0800
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-05 11:04 -0600
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-06 07:24 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-06 04:02 -0600
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-06 08:03 +0000
Re: Memoizing recursive words stephenXXX@mpeforth.com (Stephen Pelc) - 2011-12-06 10:46 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-06 04:54 -0600
Re: Memoizing recursive words Hans Bezemer <thebeez@xs4all.nl> - 2011-12-08 00:08 +0100
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-06 12:36 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-06 10:28 -0600
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-06 16:32 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-06 10:40 -0600
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-06 16:51 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-06 12:03 -0600
Re: Memoizing recursive words Hans Bezemer <thebeez@xs4all.nl> - 2011-12-07 23:55 +0100
Re: Memoizing recursive words Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-07 01:06 +0100
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-07 03:37 -0600
Re: Memoizing recursive words stephenXXX@mpeforth.com (Stephen Pelc) - 2011-12-07 10:36 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-07 06:23 -0600
Re: Memoizing recursive words stephenXXX@mpeforth.com (Stephen Pelc) - 2011-12-07 13:50 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-07 11:49 -0600
Re: Memoizing recursive words anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-08 15:36 +0000
Re: Memoizing recursive words anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-08 16:15 +0000
Re: Memoizing recursive words Albert van der Horst <albert@spenarnc.xs4all.nl> - 2011-12-10 17:23 +0000
Re: Memoizing recursive words stephenXXX@mpeforth.com (Stephen Pelc) - 2011-12-10 17:34 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-10 11:43 -0600
return address manipulation (was: Memoizing recursive words) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-07 13:29 +0000
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-07 11:55 -0600
Re: return address manipulation Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-08 00:03 +0100
Re: return address manipulation BruceMcF <agila61@netscape.net> - 2011-12-07 15:11 -0800
Re: return address manipulation Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-08 01:52 +0100
Re: return address manipulation Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2011-12-08 11:12 +0000
Re: return address manipulation Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-08 18:04 +0100
Re: return address manipulation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-08 15:51 +0000
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-08 12:17 -0600
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-13 13:07 -0600
Re: return address manipulation Alex McDonald <blog@rivadpm.com> - 2011-12-13 13:37 -0800
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-14 03:45 -0600
Re: return address manipulation Alex McDonald <blog@rivadpm.com> - 2011-12-14 01:58 -0800
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-14 04:09 -0600
Re: return address manipulation "Elizabeth D. Rather" <erather@forth.com> - 2011-12-14 10:43 -1000
Re: return address manipulation Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-14 14:08 +0100
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-14 09:18 -0600
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-14 09:48 -0600
Re: return address manipulation Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-14 23:24 +0100
Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 04:50 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 07:45 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-15 15:48 +0000
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 08:08 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 10:44 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 09:07 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-15 17:16 +0000
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 09:44 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-15 17:55 +0000
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 10:13 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-16 17:24 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 11:25 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 09:40 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 12:11 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 19:01 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-16 03:14 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-16 07:54 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-16 16:58 +0000
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-17 09:58 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-19 14:36 +0000
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-19 12:49 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-20 02:55 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-20 06:34 -0800
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 10:22 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 12:44 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-16 17:27 +0000
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 09:33 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 12:52 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-15 11:07 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-16 03:16 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-16 08:10 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-16 12:38 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-16 08:13 -0800
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-16 12:43 -0600
Re: Quotations [Was: return address manipulation] Sieur de Bienville <morrimichael@gmail.com> - 2011-12-17 15:35 -0800
Re: Quotations [Was: return address manipulation] Roelf Toxopeus <rt4all@notthis.hetnet.nl> - 2011-12-19 20:40 +0100
Re: Quotations [Was: return address manipulation] Sieur de Bienville <morrimichael@gmail.com> - 2011-12-19 13:41 -0800
Re: Quotations [Was: return address manipulation] Mark Wills <markrobertwills@yahoo.co.uk> - 2011-12-27 07:30 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-27 16:21 +0000
Re: Quotations [Was: return address manipulation] Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-27 20:55 +0100
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-27 14:42 -0600
Re: Quotations [Was: return address manipulation] Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-27 22:58 +0100
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-27 16:43 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-30 12:00 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-30 06:09 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-30 13:23 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-30 08:13 -0600
Re: Quotations [Was: return address manipulation] mhx@iae.nl (Marcel Hendrix) - 2011-12-30 16:48 +0200
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-30 16:36 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2011-12-30 15:16 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-31 14:00 +0000
Re: Quotations [Was: return address manipulation] Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-01-01 12:22 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-01 06:09 -0600
Re: Quotations [Was: return address manipulation] mhx@iae.nl (Marcel Hendrix) - 2012-01-01 14:17 +0200
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-01 09:50 -0600
Re: Quotations [Was: return address manipulation] Bernd Paysan <bernd.paysan@gmx.de> - 2012-01-01 18:15 +0100
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-01 11:48 -0600
Re: Quotations [Was: return address manipulation] Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-01-02 11:19 +0000
Re: Quotations [Was: return address manipulation] mhx@iae.nl (Marcel Hendrix) - 2012-01-01 14:02 +0200
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-01 09:37 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-02 14:30 +0000
Re: Quotations [Was: return address manipulation] Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-01-03 13:28 +0000
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2012-01-01 13:35 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-02 14:14 +0000
Re: Quotations [Was: return address manipulation] Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-01-03 12:04 +0000
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-31 14:19 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-31 11:46 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-02 13:47 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-02 10:19 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-03 09:08 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-03 04:47 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-03 16:55 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-03 11:28 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-04 14:52 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-04 09:54 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-04 17:28 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-04 12:10 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2012-01-03 10:09 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-04 17:14 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-04 11:26 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-04 17:49 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-04 12:11 -0600
Re: Quotations [Was: return address manipulation] BruceMcF <agila61@netscape.net> - 2012-01-04 12:59 -0800
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-05 16:46 +0000
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-03 16:34 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-03 11:40 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-04 15:03 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-01-04 12:01 -0600
Re: Quotations [Was: return address manipulation] Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-01-04 21:02 +0000
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-05 16:38 +0000
Re: Quotations [Was: return address manipulation] Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-01-07 14:27 +0000
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-30 11:33 +0000
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-30 11:53 +0000
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-16 17:18 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-16 13:16 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-19 15:01 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 10:40 -0600
Re: Quotations [Was: return address manipulation] anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-22 16:21 +0000
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-22 11:40 -0600
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-26 13:01 -0600
Re: Quotations [Was: return address manipulation] Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-27 03:54 -0600
Re: Quotations [Was: return address manipulation] Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-15 20:11 +0100
Quotations (was: return address manipulation) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-14 15:27 +0000
Re: Quotations Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-14 09:50 -0600
Re: Quotations Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-14 22:38 +0100
Re: Quotations Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2011-12-14 23:03 +0000
Re: Quotations anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-15 15:56 +0000
Re: return address manipulation stephenXXX@mpeforth.com (Stephen Pelc) - 2011-12-09 14:48 +0000
Re: return address manipulation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-09 16:35 +0000
Re: return address manipulation BruceMcF <agila61@netscape.net> - 2011-12-09 10:18 -0800
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-09 12:36 -0600
Re: return address manipulation BruceMcF <agila61@netscape.net> - 2011-12-09 12:07 -0800
Re: return address manipulation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-10 12:37 +0000
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-10 11:49 -0600
Re: return address manipulation BruceMcF <agila61@netscape.net> - 2011-12-10 10:06 -0800
Re: return address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-10 12:37 -0600
Re: return address manipulation BruceMcF <agila61@netscape.net> - 2011-12-10 11:28 -0800
Re: return address manipulation "Elizabeth D. Rather" <erather@forth.com> - 2011-12-09 08:39 -1000
Re: return address manipulation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-10 12:34 +0000
Re: return address manipulation BruceMcF <agila61@netscape.net> - 2011-12-10 06:39 -0800
Re: return address manipulation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-11 11:30 +0000
Re: Memoizing recursive words stephenXXX@mpeforth.com (Stephen Pelc) - 2011-12-06 17:18 +0000
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-07 14:30 +0000
Re: Memoizing recursive words anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-07 15:33 +0000
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-07 17:09 +0000
Re: Memoizing recursive words anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-07 17:26 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-07 12:08 -0600
Re: Memoizing recursive words Arnold Doray <thinksquared@gmail.com> - 2011-12-08 00:05 +0000
Re: Memoizing recursive words Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-08 03:37 -0600
Page 1 of 10 [1] 2 3 … 10 Next page →
| From | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| Date | 2011-12-03 19:07 +0000 |
| Subject | Memoizing recursive words |
| Message-ID | <jbds1r$1v8$1@dont-email.me> |
Here is my attempt at a set of Forth words to memoize recursive words. It
works for functions with 1 argument and 1 value.
The key words are :: used to define a recursive word and recurse* which
is used instead of recurse.
For example, you'd define the Fibonacci series thus:
3 :: fib
dup 1 > if dup 1- recurse* swap 2 - recurse* + then ;
This sets up a memoization table with 3 slots. :: leaves the address of
the memoization table on the stack, which the programmer can use to free
memory. The memoization table is a palimpsest/circular buffer, so old
entries are wiped out.
I've included 2 other examples ( mutually recursive functions and doubly
recursive functions ) in the listing below.
The code has been tested on GForth and VFX. I've only used ANS words.
It's my first real Forth program, so I'd greatly appreciate your
criticisms.
Cheers
Arnold
\
\ Memoizes 1 parameter recursive functions with 1 return value.
\ Copyright 2011 by Arnold Doray
\ v 0.0
\ Requires the Memory Allocation and Exception wordsets
\
\ unsigned minimum. Most Forths have this. But not in spec.
: umin ( u1 u2 -- u3 )
2dup u> if swap then drop ;
\ temporarily holds addr of memoization table
\ Used at compile time only
variable mt
\ checks if memory allocation is OK
: cannot-allocate? ( ior -- )
if -1 throw then ;
\ gets max number of entries in memoization table
: mt-size ( addr -- n )
@ ;
\ address of read/write top of memoization table
: rwtop ( addr -- addr' )
1 cells + ;
\ start address of memoization table body
: >mt-body ( addr -- addr' )
2 cells + ;
\ total length of memoization table in cells.
\ there are <size> key/value entries.
: mt-length ( size -- length )
1+ 2* cells ;
\ start address of next key on the memoization table
: next-key ( addr -- addr' )
2 cells + ;
\ start address of a value given the entry's address
: the-value ( addr -- addr' )
1 cells + ;
\ start address of a key given the entry's address
: the-key ( addr -- addr' ) ;
\ puts the mt's size and rwtop on the stack
: rwtop-n-size ( addr -- rwtop size )
dup rwtop @ swap mt-size ;
\ finds the limit to read to
: rtop ( addr -- rtop )
rwtop-n-size umin ;
\ write pointer to circular buffer
: wtop ( addr -- wtop )
rwtop-n-size mod ;
\ increments the top
: +rwtop ( addr -- )
rwtop 1 swap +! ;
\ start address of entry n in the memoization table
: entry ( addr n -- addr' )
2* cells swap >mt-body + ;
\ creates and initialies the memoization table
\ the memoization table format is <size><read/write top> ( <key><value> )*
: create-mt ( size -- addr )
dup mt-length allocate ( size addr ior )
cannot-allocate? \ throws an exception on failure
dup >R ! \ initialize size
0 R@ rwtop ! \ init read/write top to 0
R> ;
\ finds the value given a key. O(size) operation
: assoc ( key addr size -- value false | key true )
dup 0= if 2drop true exit then \ termination
>R \ save size
2dup @ = \ key found?
if
swap R> 2drop
the-value @ false exit
then
next-key R> 1- recurse ;
\ gets a value from a memoization table
: get-value ( key addr -- value false | key true )
dup >mt-body swap rtop assoc ;
\ sets a value to the memoization table
: set-value ( key value addr -- )
>R
R@ dup wtop entry >R
R@ the-value !
R> the-key !
R> +rwtop ;
\ Quotes words in a macro
: `
postpone postpone ; immediate
\ the addr of the memoization table found at compile time
: mt,
mt @ postpone literal ; immediate
\ macro for memoized recursion. Use this instead of RECURSE.
: recurse*
postpone mt, ` get-value
` if
` dup postpone recurse
` tuck
postpone mt, ` set-value
` then ; immediate
\ To define memoized recursive words.
\ The address of the memoization table is
\ placed on the stack, when the recursive
\ word is defined. Use this address to free the table
\ Usage: <mt size> :: <name> <definition> ;
: :: ( size -- addr )
create-mt dup mt ! : ;
\ ------------------------------------------------------- EXAMPLE USAGE
\ Example 1 : Basic recursion
\ The Fibonacci Series
\ Needs only a small fixed sized memoization table
\ Use a memoization table with 3 slots
3 :: fib
dup 1 > if dup 1- recurse* swap 2 - recurse* + then ;
\ calculate the 45th fibonacci number
45 fib cr .
\ calculate the 46th fibonacci number
46 fib cr .
\ free the memoization table
free drop
\ Example 2 : Mutually recursive functions
\ Hofstandter's Male and Female sequences
\ Probably needs an O(log(n)) sized memoization table
defer F
10 :: M
dup 0= if 1+ exit then
dup 1- recurse* F - ;
10 :: (F)
dup 0= if exit then
dup 1- recurse* M - ;
' (F) is F
200 F cr .
200 M cr .
free drop
free drop
\ Example 3 : Doubly-recursive sequences
\ Hofstadter-Conway $10,000 sequence
\ Probably needs an O(n) sized table.
30 :: a
dup 2 > if
dup 1- recurse* recurse* swap
dup 1- recurse* - recurse*
+
else
drop 1
then ;
100 a cr .
free drop
[toc] | [next] | [standalone]
| From | "A. K." <akk@nospam.org> |
|---|---|
| Date | 2011-12-04 13:21 +0100 |
| Message-ID | <4edb65cc$0$6555$9b4e6d93@newsspool4.arcor-online.net> |
| In reply to | #7710 |
On 03.12.2011 20:07, Arnold Doray wrote: > Here is my attempt at a set of Forth words to memoize recursive words. It > works for functions with 1 argument and 1 value. > > The key words are :: used to define a recursive word and recurse* which > is used instead of recurse. > > For example, you'd define the Fibonacci series thus: > > 3 :: fib > dup 1> if dup 1- recurse* swap 2 - recurse* + then ; > > This sets up a memoization table with 3 slots. :: leaves the address of > the memoization table on the stack, which the programmer can use to free > memory. The memoization table is a palimpsest/circular buffer, so old > entries are wiped out. > > I've included 2 other examples ( mutually recursive functions and doubly > recursive functions ) in the listing below. > > The code has been tested on GForth and VFX. I've only used ANS words. > > It's my first real Forth program, so I'd greatly appreciate your > criticisms. > > Cheers > Arnold <snip> Thank you for this interesting work! It made me also look up how memoizing lookup tables are used in other languages. I won't criticize. My remarks are tinted by my own personal coding taste (others may object) but here they are: - it is well documented, good! - it seems a bit overfactorized - the syntax does not seem 'natural' to me - I wouldn't use allocate (in some machines it is slow) but allot the table - the ` back-accent is awkward on some keyboards and can be confused with ' tick Regards Andreas
[toc] | [prev] | [next] | [standalone]
| From | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| Date | 2011-12-04 14:20 +0000 |
| Message-ID | <jbfvk2$4ds$1@dont-email.me> |
| In reply to | #7715 |
On Sun, 04 Dec 2011 13:21:30 +0100, A. K. wrote: > Thank you for this interesting work! It made me also look up how > memoizing lookup tables are used in other languages. > > Thank you for your comments Andreas. Until I tried out these examples, I wasn't aware that different recursive functions require very different table sizes (ie, in order to calculate the recursive function in O(n) time, making it effectively an iteration). Eg, for the Fibonacci series, you only need to remember 3 values. But for other series, you need more, either O(log(n)) or O(n) or more. Might be a good measure of the complexity of the recursive function. I wonder if there is any literature on this? Incidentally, I tried to calculate the Ackermann function A(m,n) with m=4 but failed at A(4,1). Not because of memoization, but because of a return stack overflow. > - the syntax does not seem 'natural' to me - I wouldn't use allocate (in > some machines it is slow) but allot the table > About using ALLOCATE -- I wanted to create an anonymous array, sort of an equivalent of :NONAME but for arrays. I tried ALLOT at first, but (a) this needs a name to attach to, as far as I can see. and (b) the space is created on the dictionary (I believe!) so I'm not sure how to free it up when the function is no longer used. Some memoization tables can be quite large, so I don't want to fill up the dictionary with junk. ALLOCATE seems to solve both these problems. I also don't have to worry about other technicalities like alignment. Latency is an issue, but it's only one-off during compile time. It isn't an issue when the functions are used. Or are you saying that arrays created using ALLOCATE are slower to use compared to those created with ALLOT? Or is there a better way to create fast anonymous arrays in Forth? ( Yes, I could have used a named array, but this has other problems. ) > - the ` back-accent is awkward on some keyboards and can be confused > with ' tick Too true! The symbol has to be unobtrusive since I'm using it to delay execution of words in the macro. The traditional Lisp quote ' is taken up in standard Forth. The double quote " is free, but could be confusing. ` was the best I could come up with! What I am after is a simple way to create a C-like macro, which is what RECURSE* really is. Is there a better way to do this in Forth? Thanks, Arnold
[toc] | [prev] | [next] | [standalone]
| From | Josh Grams <josh@qualdan.com> |
|---|---|
| Date | 2011-12-04 16:03 +0000 |
| Message-ID | <4edb99c5$0$23268$882e7ee2@usenet-news.net> |
| In reply to | #7716 |
Arnold Doray wrote: > On Sun, 04 Dec 2011 13:21:30 +0100, A. K. wrote: > About using ALLOCATE -- I wanted to create an anonymous array, sort of an > equivalent of :NONAME but for arrays. I tried ALLOT at first, but (a) this > needs a name to attach to, as far as I can see. and (b) the space is > created on the dictionary (I believe!) so I'm not sure how to free it up > when the function is no longer used. Some memoization tables can be quite > large, so I don't want to fill up the dictionary with junk. > > ALLOCATE seems to solve both these problems. I also don't have to worry > about other technicalities like alignment. Latency is an issue, but it's > only one-off during compile time. It isn't an issue when the functions > are used. Or are you saying that arrays created using ALLOCATE are slower > to use compared to those created with ALLOT? No, it's all the same RAM. It doesn't matter whether you get the address from ALLOT or ALLOCATE. And if you have a function which is slow enough that it needs to be memoized, I doubt you'll notice the time taken to ALLOCATE memory... The problem I see with ALLOCATE is that you're hard-coding the address into the word, but if you free the table, the word is still there, so you have to be careful never to call it again. >> - the ` back-accent is awkward on some keyboards and can be confused >> with ' tick > > Too true! > > The symbol has to be unobtrusive since I'm using it to delay execution of > words in the macro. The traditional Lisp quote ' is taken up in standard > Forth. The double quote " is free, but could be confusing. ` was the best > I could come up with! Backtick is the usual nickname for POSTPONE. I don't know much about keyboard layouts from other countries, but I'd be surprised to find that it was more awkward than typing eight characters. And if you have trouble tellling ` from ' then you need to get a font which doesn't suck. > What I am after is a simple way to create a C-like macro, which is what > RECURSE* really is. Is there a better way to do this in Forth? Nope, that's pretty much the way to do it. The other thing which jumps out at me is that I'd use the Forth200x +FIELD (or FIELD:) or gforth's FIELD to define your structure fields. That would make the structure stand out better and make all that boilerplate more compact and look less excessive. Also I would move the definition of `mt` down to the bottom, since that's the only place where it is actually used. And you left out a `the-key` in `assoc`. Looks good to me. I'm sure there are people here who wouldn't bother naming the structure fields at all and just hard-code offsets, since it's such a small piece of code. But that's personal preference. --Josh
[toc] | [prev] | [next] | [standalone]
| From | "A. K." <akk@nospam.org> |
|---|---|
| Date | 2011-12-04 17:25 +0100 |
| Message-ID | <4edb9f0d$0$6581$9b4e6d93@newsspool3.arcor-online.net> |
| In reply to | #7717 |
On 04.12.2011 17:03, Josh Grams wrote: > Arnold Doray wrote: > No, it's all the same RAM. It doesn't matter whether you get the > address from ALLOT or ALLOCATE. There ARE system where it matters, believe me. ;-) And there are even systems that do not provide the memory allocation wordset at all.
[toc] | [prev] | [next] | [standalone]
| From | BruceMcF <agila61@netscape.net> |
|---|---|
| Date | 2011-12-04 10:51 -0800 |
| Message-ID | <bdecab61-54fa-4392-9ccd-c52ee6fa23fe@z12g2000yqm.googlegroups.com> |
| In reply to | #7717 |
On Dec 4, 11:03 am, Josh Grams <j...@qualdan.com> wrote: > No, it's all the same RAM. It doesn't matter whether you get the > address from ALLOT or ALLOCATE. In some cases it is NOT the same RAM. And if you've saved a dictionary as a system it can make a substantial difference, as ALLOT will be in the saved system and ALLOCATE will be called either as needed or in the start up word when the system is loaded. BUFFER is a word that addresses that issue without the overhead of ALLOCATE ~ it would be implemented with ALLOT in an implementation that does not have one built in, but for an implementation with a native BUFFER, it would be space that would not be embedded within a saved system but reserved for use.
[toc] | [prev] | [next] | [standalone]
| From | "Elizabeth D. Rather" <erather@forth.com> |
|---|---|
| Date | 2011-12-04 12:50 -1000 |
| Message-ID | <2dGdnY-W7qupZEbTnZ2dnUVZ_g-dnZ2d@supernews.com> |
| In reply to | #7723 |
On 12/4/11 8:51 AM, BruceMcF wrote: > On Dec 4, 11:03 am, Josh Grams<j...@qualdan.com> wrote: >> No, it's all the same RAM. It doesn't matter whether you get the >> address from ALLOT or ALLOCATE. > > In some cases it is NOT the same RAM. It certainly cannot be "the same" in the sense of ALLOCATEd space being intermingled with ALLOTted space, since the whole point of ALLOCATE is to be able to FREE space when it's no longer needed, and there is no provision for freeing or rearranging ALLOTted space. Whether there are two separately managed regions of data space in the same bank of RAM is entirely an implementation issue, though. > And if you've saved a dictionary as a system it can make a substantial > difference, as ALLOT will be in the saved system and ALLOCATE will be > called either as needed or in the start up word when the system is > loaded. > > BUFFER is a word that addresses that issue without the overhead of > ALLOCATE ~ it would be implemented with ALLOT in an implementation > that does not have one built in, but for an implementation with a > native BUFFER, it would be space that would not be embedded within a > saved system but reserved for use. Do you mean BUFFER: ? Cheers, Elizabeth -- ================================================== Elizabeth D. Rather (US & Canada) 800-55-FORTH FORTH Inc. +1 310.999.6784 5959 West Century Blvd. Suite 700 Los Angeles, CA 90045 http://www.forth.com "Forth-based products and Services for real-time applications since 1973." ==================================================
[toc] | [prev] | [next] | [standalone]
| From | BruceMcF <agila61@netscape.net> |
|---|---|
| Date | 2011-12-04 15:40 -0800 |
| Message-ID | <f7dc7b08-d8c1-458b-911e-2808b391ab17@o13g2000vbo.googlegroups.com> |
| In reply to | #7727 |
On Dec 4, 5:50 pm, "Elizabeth D. Rather" <erat...@forth.com> wrote: > > BUFFER is a word that ... > Do you mean BUFFER: ? Yes, that's the one, http://www.forth200x.org/buffer.html
[toc] | [prev] | [next] | [standalone]
| From | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| Date | 2011-12-05 11:17 +0000 |
| Message-ID | <jbi97l$h6u$1@dont-email.me> |
| In reply to | #7717 |
On Sun, 04 Dec 2011 16:03:17 +0000, Josh Grams wrote:
> The problem I see with ALLOCATE is that you're hard-coding the address
> into the word, but if you free the table, the word is still there, so
> you have to be careful never to call it again.
Yes, this bothers me too. In fact there is a related problem: My solution
only memoizes when recurse* is called. So, a call to fib(45) doesn't
memoize that value, only arguments less than 45. I realized early on that
both issues can be solved this way:
: (F) ... ; \ does the actual function calculation
: F
<mt-addr> mt-exists?
dup <mt-addr> get-value
if
(F)
then
save-value-to-mt ;
This would solve the mt check efficiently and memoize the last function
call. As a bonus, you'd then memoize *any* function, not just recursive
ones.
Unfortunately, I can't figure out a way to do it. My attempt was:
: ::
create-mt dup mt ! \ run once when fn is defined ,
<somehow create the name> \ read fn name and create dict entry
postpone mt, ` mt-exists? \ mt-exists? called at fn's runtime
` dup postpone mt, ` get-value
` if
:noname ...
Here's where I run into trouble.
How to terminate :noname's parsing action at ::'s
runtime so that the rest of :: is executed?
compile, \ compile the xt of the :noname into fn
` then
` save-value-to-mt ;
Any pointers?
Thanks,
Arnold
[toc] | [prev] | [next] | [standalone]
| From | "Elizabeth D. Rather" <erather@forth.com> |
|---|---|
| Date | 2011-12-04 08:24 -1000 |
| Message-ID | <5YKdnYwL6IllJ0bTnZ2dnUVZ_tCdnZ2d@supernews.com> |
| In reply to | #7716 |
On 12/4/11 4:20 AM, Arnold Doray wrote: ... > > About using ALLOCATE -- I wanted to create an anonymous array, sort of an > equivalent of :NONAME but for arrays. I tried ALLOT at first, but (a) this > needs a name to attach to, as far as I can see. and (b) the space is > created on the dictionary (I believe!) so I'm not sure how to free it up > when the function is no longer used. Some memoization tables can be quite > large, so I don't want to fill up the dictionary with junk. > > ALLOCATE seems to solve both these problems. I also don't have to worry > about other technicalities like alignment. Latency is an issue, but it's > only one-off during compile time. It isn't an issue when the functions > are used. Or are you saying that arrays created using ALLOCATE are slower > to use compared to those created with ALLOT? > > Or is there a better way to create fast anonymous arrays in Forth? > > ( Yes, I could have used a named array, but this has other problems. ) You can certainly get an anonymous array by using HERE <n> ALLOT (which leaves the address of the start of the space on the stack just as ALLOCATE does). It is true that this space cannot be released as ALLOCATEd space can, but in general, this isn't a problem. In particular, since you're hard-coding the address, you appear to be treating it as permanent. Alignment is not significantly different between the two approaches. If you have reason to believe your data space is unaligned (e.g. you have just explicitly ALLOTed an odd number of AU) you can just say ALIGN and everything will be fine. I'm also unclear as to what problems you see with named arrays. Cheers, Elizabeth -- ================================================== Elizabeth D. Rather (US & Canada) 800-55-FORTH FORTH Inc. +1 310.999.6784 5959 West Century Blvd. Suite 700 Los Angeles, CA 90045 http://www.forth.com "Forth-based products and Services for real-time applications since 1973." ==================================================
[toc] | [prev] | [next] | [standalone]
| From | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| Date | 2011-12-04 19:14 +0000 |
| Message-ID | <jbggri$97m$1@dont-email.me> |
| In reply to | #7720 |
On Sun, 04 Dec 2011 08:24:54 -1000, Elizabeth D. Rather wrote: > > You can certainly get an anonymous array by using HERE <n> ALLOT (which > leaves the address of the start of the space on the stack just as Thanks! That was very useful. > ALLOCATE does). It is true that this space cannot be released as > ALLOCATEd space can, but in general, this isn't a problem. In > particular, since you're hard-coding the address, you appear to be > treating it as permanent. > With ALLOCATE, you give the programmer the *option* of freeing up the space, while with ALLOT the programmer has no choice but to live with junk in the dictionary. The memoization tables could be large, especially for the more interesting recursive functions. > > I'm also unclear as to what problems you see with named arrays. > Besides the problem of junk in the dictionary that can't be freed up, the problem is creating the name itself. The options are (a) asking the programmer to do it, eg: 100 memoize fib-mt :: fib .... ; Which creates an unnecessary name, fib-mt, besides being more verbose compared to: 100 :: fib ... ; The latter is a more elegant solution, IMHO because of these reasons. You don't need to name the structure. All you need is the address. (b) Putting in some plumbing to create a named array automatically when the function is defined. This is quite beyond me at this stage. I would essentially need to re-write my own version of : Cheers, Arnold
[toc] | [prev] | [next] | [standalone]
| From | BruceMcF <agila61@netscape.net> |
|---|---|
| Date | 2011-12-04 12:09 -0800 |
| Message-ID | <d3be942f-2ab2-4197-9fd6-99904d77098b@h42g2000yqd.googlegroups.com> |
| In reply to | #7725 |
On Dec 4, 2:14 pm, Arnold Doray <thinksqua...@gmail.com> wrote: > (b) Putting in some plumbing to create a named array automatically when > the function is defined. This is quite beyond me at this stage. I would > essentially need to re-write my own version of : If it was useful to name the array ~ say, for debugging ~ you could save that spot in the parsing, create the named array in a side wordlist, then come back and define the word with the original ":". WORDLIST CONSTANT Memoize-Arrays : :: ( ... create array ... -- addr size ) >IN @ GET-CURRENT ( addr size #in current-wid ) Memoize-Arrays SET-CURRENT 2SWAP 2DUP 2CONSTANT 2>R SET-CURRENT >IN ! : 2>R ( r: addr size ) ; But that could also be added later, after first going with an anonymous array embedded in the definition of the word to be defined. : :: ( ... create array .. -- addr size ) 2>R : 2R> ;
[toc] | [prev] | [next] | [standalone]
| From | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| Date | 2011-12-05 04:00 +0000 |
| Message-ID | <jbhflg$ohb$1@dont-email.me> |
| In reply to | #7726 |
On Sun, 04 Dec 2011 12:09:36 -0800, BruceMcF wrote: > On Dec 4, 2:14 pm, Arnold Doray <thinksqua...@gmail.com> wrote: >> (b) Putting in some plumbing to create a named array automatically when >> the function is defined. This is quite beyond me at this stage. I would >> essentially need to re-write my own version of : > > If it was useful to name the array ~ say, for debugging ~ you could save > that spot in the parsing, create the named array in a side wordlist, > then come back and define the word with the original ":". > > WORDLIST CONSTANT Memoize-Arrays > > : :: ( ... create array ... -- addr size ) > >IN @ GET-CURRENT ( addr size #in current-wid ) > Memoize-Arrays SET-CURRENT 2SWAP 2DUP 2CONSTANT 2>R SET-CURRENT >IN ! > : 2>R ( r: addr size ) ; Thanks Bruce. This is really useful to know. Cheers, Arnold
[toc] | [prev] | [next] | [standalone]
| From | BruceMcF <agila61@netscape.net> |
|---|---|
| Date | 2011-12-07 12:41 -0800 |
| Message-ID | <873ca9c3-1404-4cf6-b812-f9e53ba442a4@y18g2000yqy.googlegroups.com> |
| In reply to | #7732 |
On Dec 4, 11:00 pm, Arnold Doray <thinksqua...@gmail.com> wrote: > On Sun, 04 Dec 2011 12:09:36 -0800, BruceMcF wrote: >> : :: ( ... create array ... -- addr size ) >> >IN @ GET-CURRENT ( addr size #in current-wid ) >> Memoize-Arrays SET-CURRENT 2SWAP 2DUP 2CONSTANT 2>R SET-CURRENT >IN ! >> : 2>R ( r: addr size ) ; > Thanks Bruce. This is really useful to know. Typo (well, typo plus lagged edit): : :: ( ... create array ... -- addr size ) >IN @ GET-CURRENT ( addr size #in current-wid ) Memoize-Arrays SET-CURRENT 2SWAP 2DUP 2CONSTANT 2>R SET-CURRENT >IN ! : 2R> ( addr size ) ;
[toc] | [prev] | [next] | [standalone]
| From | Andrew Haley <andrew29@littlepinkcloud.invalid> |
|---|---|
| Date | 2011-12-05 11:04 -0600 |
| Message-ID | <VLKdnayez7QlZEHTnZ2dnUVZ_gOdnZ2d@supernews.com> |
| In reply to | #7710 |
Arnold Doray <thinksquared@gmail.com> wrote: > Here is my attempt at a set of Forth words to memoize recursive words. It > works for functions with 1 argument and 1 value. > > The key words are :: used to define a recursive word and recurse* which > is used instead of recurse. > > For example, you'd define the Fibonacci series thus: > > 3 :: fib > dup 1 > if dup 1- recurse* swap 2 - recurse* + then ; > > This sets up a memoization table with 3 slots. :: leaves the address of > the memoization table on the stack, which the programmer can use to free > memory. The memoization table is a palimpsest/circular buffer, so old > entries are wiped out. > > I've included 2 other examples ( mutually recursive functions and doubly > recursive functions ) in the listing below. > > The code has been tested on GForth and VFX. I've only used ANS words. > > It's my first real Forth program, so I'd greatly appreciate your > criticisms. OK. Firstly, the good things. It looks pretty well-engineered, it's heavily commented, and as far as I can see it looks like it's probably correct. On the downside, it's big; it needs some heavy filleting. This is a fairly common characteristic of beginners' forth programs. There are some stylistic nits I'll point out inline. > \ checks if memory allocation is OK > : cannot-allocate? ( ior -- ) > if -1 throw then ; You don't really need this: the standard idiom is ALLOCATE THROW . > > \ gets max number of entries in memoization table > : mt-size ( addr -- n ) > @ ; > > \ address of read/write top of memoization table > : rwtop ( addr -- addr' ) > 1 cells + ; > > \ start address of memoization table body > : >mt-body ( addr -- addr' ) > 2 cells + ; It would make sense to use the Forth 200x structures extension for these fields. > \ increments the top > : +rwtop ( addr -- ) > rwtop 1 swap +! ; This isn't really a good factor. If you want something to bump a count, it's better to do something like: : ++ ( addr -- ) 1 swap +! ; I'm not recommending ++ as a name. Perhaps BUMP or TALLY would be better. But it's even easier to read as 1 over rwtop +! > \ creates and initialies the memoization table > \ the memoization table format is <size><read/write top> ( <key><value> )* > : create-mt ( size -- addr ) > dup mt-length allocate ( size addr ior ) > cannot-allocate? \ throws an exception on failure > dup >R ! \ initialize size > 0 R@ rwtop ! \ init read/write top to 0 > R> ; The use of ALLOCATE versus ALLOT has been adddressed at some length already. > > \ finds the value given a key. O(size) operation > : assoc ( key addr size -- value false | key true ) > dup 0= if 2drop true exit then \ termination > >R \ save size > 2dup @ = \ key found? > if > swap R> 2drop > the-value @ false exit > then > next-key R> 1- recurse ; RECURSE is very non-idiomatic here: this is plain iteration. > \ macro for memoized recursion. Use this instead of RECURSE. > : recurse* > postpone mt, ` get-value > ` if > ` dup postpone recurse > ` tuck > postpone mt, ` set-value > ` then ; immediate > > \ To define memoized recursive words. > \ The address of the memoization table is > \ placed on the stack, when the recursive > \ word is defined. Use this address to free the table > \ Usage: <mt size> :: <name> <definition> ; > : :: ( size -- addr ) > create-mt dup mt ! : ; The use of IMMEDIATE and defining a special version of RECURSE is a rather complex way of solving the problem. Also, as you've already noticed, the definition itself is not memoized, only its internal recursion is. Andrew.
[toc] | [prev] | [next] | [standalone]
| From | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| Date | 2011-12-06 07:24 +0000 |
| Message-ID | <jbkfug$uq3$1@dont-email.me> |
| In reply to | #7737 |
On Mon, 05 Dec 2011 11:04:56 -0600, Andrew Haley wrote:
Many thanks for the comments. I found them very helpful.
I have a couple of questions:
>> \ finds the value given a key. O(size) operation : assoc ( key addr
>> size -- value false | key true )
>> dup 0= if 2drop true exit then \ termination
>> >R \ save size
>> 2dup @ = \ key found? if
>> swap R> 2drop
>> the-value @ false exit
>> then
>> next-key R> 1- recurse ;
>
> RECURSE is very non-idiomatic here: this is plain iteration.
>
Hmm. Iteration was my first choice, but it is more verbose:
: assoc ( key addr size -- value false | key true )
dup 0= if 2drop true exit then \ termination
0 do
2dup
loop
2drop
>> \ macro for memoized recursion. Use this instead of RECURSE. : recurse*
>> postpone mt, ` get-value
>> ` if
>> ` dup postpone recurse
>> ` tuck
>> postpone mt, ` set-value
>> ` then ; immediate
>>
>> \ To define memoized recursive words. \ The address of the memoization
>> table is \ placed on the stack, when the recursive \ word is defined.
>> Use this address to free the table \ Usage: <mt size> :: <name>
>> <definition> ; : :: ( size -- addr )
>> create-mt dup mt ! : ;
>
> The use of IMMEDIATE and defining a special version of RECURSE is a
> rather complex way of solving the problem. Also, as you've already
> noticed, the definition itself is not memoized, only its internal
> recursion is.
>
> Andrew.
[toc] | [prev] | [next] | [standalone]
| From | Andrew Haley <andrew29@littlepinkcloud.invalid> |
|---|---|
| Date | 2011-12-06 04:02 -0600 |
| Message-ID | <0YOdnfgq0OOjdUDTnZ2dnUVZ_r6dnZ2d@supernews.com> |
| In reply to | #7744 |
Arnold Doray <thinksquared@gmail.com> wrote: > On Mon, 05 Dec 2011 11:04:56 -0600, Andrew Haley wrote: > > Many thanks for the comments. I found them very helpful. > > I have a couple of questions: > >>> \ finds the value given a key. O(size) operation : assoc ( key addr >>> size -- value false | key true ) >>> dup 0= if 2drop true exit then \ termination >>> >R \ save size >>> 2dup @ = \ key found? if >>> swap R> 2drop >>> the-value @ false exit >>> then >>> next-key R> 1- recurse ; >> >> RECURSE is very non-idiomatic here: this is plain iteration. > > Hmm. Iteration was my first choice, but it is more verbose: : foo ... recurse ; is equivalent to : foo begin ... again ; Andrew.
[toc] | [prev] | [next] | [standalone]
| From | Arnold Doray <thinksquared@gmail.com> |
|---|---|
| Date | 2011-12-06 08:03 +0000 |
| Message-ID | <jbki7m$uq3$2@dont-email.me> |
| In reply to | #7737 |
On Mon, 05 Dec 2011 11:04:56 -0600, Andrew Haley wrote:
Whoops. Here is my completed post:
>> \ finds the value given a key. O(size) operation : assoc ( key addr
>> size -- value false | key true )
>> dup 0= if 2drop true exit then \ termination
>> >R \ save size
>> 2dup @ = \ key found? if
>> swap R> 2drop
>> the-value @ false exit
>> then
>> next-key R> 1- recurse ;
>
> RECURSE is very non-idiomatic here: this is plain iteration.
>
The iterative version is:
: next-key ( addr index -- addr' )
2* cells + ;
: assoc ( key addr size -- value false | key true )
dup 0= if 2drop true exit then
0 do
2dup i next-key = if
swap drop
the-value @ false unloop exit
then
loop
2drop true ;
I preferred the recursive definition because it is slightly less verbose
and has only one exit point.
It is also slightly more efficient since NEXT-KEY in the iterative
version requires 3 operations ( 2* cells + ) while the recursive version
only requires one operation ( 2 cells + ) -- or two, depending on the
compiler.
I notice that SwiftForth nicely does a JMP for this tail-recursive ASSOC,
while VFX, ( which seems otherwise to be an excellent compiler, IMHO )
uses a CALL.
>> \ macro for memoized recursion. Use this instead of RECURSE. : recurse*
>> postpone mt, ` get-value
>> ` if
>> ` dup postpone recurse
>> ` tuck
>> postpone mt, ` set-value
>> ` then ; immediate
>>
>> \ To define memoized recursive words. \ The address of the memoization
>> table is \ placed on the stack, when the recursive \ word is defined.
>> Use this address to free the table \ Usage: <mt size> :: <name>
>> <definition> ; : :: ( size -- addr )
>> create-mt dup mt ! : ;
>
> The use of IMMEDIATE and defining a special version of RECURSE is a
> rather complex way of solving the problem. Also, as you've already
> noticed, the definition itself is not memoized, only its internal
> recursion is.
>
Good point. I thought long and hard about this, and every solution I
could come up with that's simple for the user involves retrofitting
RECURSE.
I would have preferred to do is something like :
: ::
<initialize mt>
<define function>
mt-exists? \ throws exception if not
get-value if
<delegate to actual function>
<save latest value>
then ;
Where the "delegated" function does the actual work. Probably defined
with :NONAME. But it would have to itself call the outer function, so
that involves a retrofitting or re-writing of RECURSE too.
Or do you have a simpler solution in mind?
In any case, as I explained in another post, I don't have the Forth chops
to execute this idea.
The basic problem is getting the last defined XT when :: executes. Gforth
has this really neat word -- LATESTXT but it is not in the '94 spec.
And unfortunately, the various implementations I've tested (except for VFX
and Swift) don't put the :NONAME's XT until the function actually exits:
variable latestxt
: def :noname dup latestxt ! ;
def ." hello world" ;
latestxt @ execute
when run with VFX or Swift, this works as expected. But not with Gforth
or BigForth. These former two put "turds" onto the stack at DEF's
runtime.
Is there a portable way to know the last defined XT? I can imagine all
sorts of uses for something like LATESTXT -- adding automatic finalizers
to words, retrofitting recursion and slightly better mutual recursion,
just off the top of my head.
Cheers,
Arnold
[toc] | [prev] | [next] | [standalone]
| From | stephenXXX@mpeforth.com (Stephen Pelc) |
|---|---|
| Date | 2011-12-06 10:46 +0000 |
| Message-ID | <4eddf07f.57544369@192.168.0.50> |
| In reply to | #7747 |
On Tue, 6 Dec 2011 08:03:03 +0000 (UTC), Arnold Doray <thinksquared@gmail.com> wrote: >I notice that SwiftForth nicely does a JMP for this tail-recursive ASSOC, >while VFX, ( which seems otherwise to be an excellent compiler, IMHO ) >uses a CALL. The performance gain for the tail recursive CALL/JMP change is often marginal, while the loss of reliability (it's a hidden return stack transformation) can be significant. The discussions at MPE on this issue were long and heated. Overall, we went for reliability. Show me a measurement where the impact is significant, and I'll rethink my attitude. I haven't measured it on current desktop CPUs, but on some architectures, JMP and CALL take the same space and execution time. Stephen -- Stephen Pelc, stephenXXX@mpeforth.com MicroProcessor Engineering Ltd - More Real, Less Time 133 Hill Lane, Southampton SO15 5AF, England tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691 web: http://www.mpeforth.com - free VFX Forth downloads
[toc] | [prev] | [next] | [standalone]
| From | Andrew Haley <andrew29@littlepinkcloud.invalid> |
|---|---|
| Date | 2011-12-06 04:54 -0600 |
| Message-ID | <osidnTnzKcD3aUDTnZ2dnUVZ_omdnZ2d@supernews.com> |
| In reply to | #7749 |
Stephen Pelc <stephenXXX@mpeforth.com> wrote: > On Tue, 6 Dec 2011 08:03:03 +0000 (UTC), Arnold Doray > <thinksquared@gmail.com> wrote: > >>I notice that SwiftForth nicely does a JMP for this tail-recursive ASSOC, >>while VFX, ( which seems otherwise to be an excellent compiler, IMHO ) >>uses a CALL. > > The performance gain for the tail recursive CALL/JMP change is often > marginal, while the loss of reliability (it's a hidden return stack > transformation) can be significant. The discussions at MPE on this > issue were long and heated. Overall, we went for reliability. That makes some sense. > I haven't measured it on current desktop CPUs, but on some > architectures, JMP and CALL take the same space and execution time. Mmm, but the difference is between CALL ; RET and just JMP . It's not the difference between a simple CALL and a JMP . Andrew.
[toc] | [prev] | [next] | [standalone]
Page 1 of 10 [1] 2 3 … 10 Next page →
Back to top | Article view | comp.lang.forth
csiph-web