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

Groups > comp.lang.forth > #59594 > unrolled thread

Forth and computer science

Back to article view | Back to comp.lang.forth

Contents

  Forth and computer science lehs <skydda.barnen@gmail.com> - 2017-05-20 05:48 -0700
    Re: Forth and computer science Coos Haak <htrofhc@gmail.com> - 2017-05-20 20:19 +0200
      Re: Forth and computer science lehs <skydda.barnen@gmail.com> - 2017-05-20 11:35 -0700
        Re: Forth and computer science Coos Haak <htrofhc@gmail.com> - 2017-05-20 20:50 +0200
          Re: Forth and computer science lehs <skydda.barnen@gmail.com> - 2017-05-21 00:08 -0700
            Re: Forth and computer science Julian Fondren <julian.fondren@gmail.com> - 2017-05-21 05:37 -0700
              Re: Forth and computer science anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-21 14:20 +0000
              Re: Forth and computer science lehs <skydda.barnen@gmail.com> - 2017-05-21 10:00 -0700
                Re: Forth and computer science anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-22 11:35 +0000
                  Re: Forth and computer science albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-05-22 16:25 +0200
                    Re: Forth and computer science anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-22 14:47 +0000
                      Re: Forth and computer science lehs <skydda.barnen@gmail.com> - 2017-05-22 10:00 -0700
    Re: Forth and computer science lehs <skydda.barnen@gmail.com> - 2017-06-05 02:52 -0700
      Re: Forth and computer science Julian Fondren <julian.fondren@gmail.com> - 2017-06-05 11:18 -0700

#59594 — Forth and computer science

I'm considering a make-over of my bigintegers, which originate from the very simple approach of arithmetic of ascii number strings. I never had the ambition to code a very efficient system - I did just go on to make it work. (Which I believe is the right thing to do.) It should be all standard Forth, which I think is the future. Sometime only the fastest code will work, but mostly standard code is fast enough. And it's really only a question of a time delay: what took minutes on mainframe computers 1970 is done in some milliseconds in standard Forth on a PC today.

Except from cleaning up, factoring and documenting better I will look over the algorithms and implement some new algorithms. But I will also try to improve the memory management.

I don't believe in Forth garbage collection. It's not the simple way. Stacks are dynamical structures with very simple memory management, managed once for all by the programmer. Up to now I've used simplest possible stacks of arrays, duplicating arrays when BDUP, BOVER, BTUCK and BPICK. Hughs string stack is about twice as efficient when repeating BDUP BDROP, but in typical operation the big cost come from the arithmetical algorithms repeating cell arithmetics.

Typical Forth words "eat" all input parameters, eventually by cleaning up the stack. With stacks of big arrays that isn't such an obvious thing to do. It might be an idea to define some alternative words for the most frequently used words. As an example the word 

B+ ( A B -- A+B ) 

use top of stack allocated for B as work space but leave A unchanged to be NIP-ed at the end. Therefore one could consider an alternative word

BSWAPTUCK+ ( A B -- A A+B ) 

that doesn't drop A, when A soon is needed. The word 

B< ( A B -- flag ) 

drops A and B at the end and an alternative could be

B2DUP< ( A B -- A B flag ) 

that doesn't clean up. 

Also, instead of copying an array that wont be altered, just read, one could construct words that reads the original arrays 

BOVER0= ( A B -- A B flag ) 

can easy be constructed on a lower level where no arrays are copied, to replace 

BOVER B0= 

which make an unnecessary copy of the second array on the bstack.

: bover0= \ u v -- u v flag
  len2 cell =    \ is it a one cell big number?
  second @ 0=    \ is that cell zero?
  and ;

Undoing the unnecessary big drops and big copies everywhere should be as efficient as memory management and 'only copy when write' system, in my opinion.

As I see it computer science is mainly directed towards solving problems that arise in the "other" languages. Forth is the perfect lab for computer science experiments, but I believe that Forth don't need most of the new ideas. What except algorithms has computer science brought to Forth? Instead of characterize Forth as "imperative", which is rather a negation of "strict functional" it should be characterized by words as simplicity and problem oriented. That's the paradigm of Forth.

[toc] | [next] | [standalone]

#59604

Op Sat, 20 May 2017 05:48:06 -0700 (PDT) schreef lehs:

<snip>
> use top of stack allocated for B as work space but leave A unchanged to be NIP-ed at the end. Therefore one could consider an alternative word
> 
> BSWAPTUCK+ ( A B -- A A+B ) 
Hints:
SWAP OVER is equivalent to TUCK
SWAP TUCK is equivalent to OVER

So, why not BOVER+ ?

groet Coos

[toc] | [prev] | [next] | [standalone]

#59605

Yes of cource, much better. Though giving the diagram ( a b -- a b+a ) instead of ( a b -- a a+b )    :).

[toc] | [prev] | [next] | [standalone]

#59608

Op Sat, 20 May 2017 11:35:20 -0700 (PDT) schreef lehs:

> Yes of cource, much better. Though giving the diagram ( a b -- a b+a ) instead of ( a b -- a a+b )    :).

Assuming bignum addition is commutative ;-)

groet Coos

[toc] | [prev] | [next] | [standalone]

#59631

Den lördag 20 maj 2017 kl. 20:50:37 UTC+2 skrev Coos Haak:
> Op Sat, 20 May 2017 11:35:20 -0700 (PDT) schreef lehs:
> 
> > Yes of cource, much better. Though giving the diagram ( a b -- a b+a ) instead of ( a b -- a a+b )    :).
> 
> Assuming bignum addition is commutative ;-)
> 
> groet Coos

I'm a mess. Of course OVER is exactly the same as SWAP TUCK and OVER+ exactly the same as SWAPTUCK+

It must be a inherent property of Forth that also sloppy and messy people can make Forth programs.

When I started bigintegers I didn't pay much attention to the stack juggling. I have a BX stack corresponding to the R stack which I used to make the juggling words. And until now I haven't looked at it a second time. But I just found out that the juggling words time simply could be reduced significantly without machine code.

I have a word BPUSHA ( ad n -- big ) that use MOVE to move the number array at ad n to the big stack. And a corresponding word for the BX stack. My first BSWAP was:

: BSWAP >BX >BX BY BX> XDROP ; 

which include 4 MOVE. It is now replaced with

: BSWAP BOVER TOP$ SEC$ 3 BDROPS BPUSHA BPUSHA ;

which include 3 MOVE. The corresponding change for BROT reduced from 10 MOVE to 4 MOVE. All this is will speed up bigintegers but I'm assured that the most time saving will come from looking over the arithmetic algorithms.

My goal is to over all double the speed.

[toc] | [prev] | [next] | [standalone]

#59648

On Sunday, May 21, 2017 at 2:08:45 AM UTC-5, lehs wrote:
> I'm a mess. Of course OVER is exactly the same as SWAP TUCK and OVER+ exactly the same as SWAPTUCK+
> 
> It must be a inherent property of Forth that also sloppy and messy people can make Forth programs.

It's an inherent property of Forth that an extra 'stack cleanup' step
is needed after operations that, in other languages, would not result
in anything to be cleaned up.

For example, suppose you want to change the parameter order of a word
from GO ( a b -- ) to GO ( b a -- ) . In most languages you can swap
all the parameters at the call sites of GO and you're done. In Forth
you can do this just as well, by preceding all invocations of GO with
a SWAP , but *just* doing that will result in code like SWAP SWAP GO
throughout your program. Stack management in words that used GO were
optimized for the previous parameter order of GO; they now are
suboptimal for GO, and much less blatant code than SWAP SWAP can
probably still be significantly improved if you look at it.

With a peephole optimizer it's not like SWAP SWAP is slow. With a
stack-analytic optimizer your 'stack cleanup' step may result in no
actual changes in generated code. But the code becomes messy.

On my scales this isn't much of a problem, but I can easily imagine
someone who would, rather than laugh and say "oh, that's due to some
incomplete refactoring", would be angry and humiliated by someone
patching SWAP SWAP -tier stack manipulation out from his code. Better
for a person like that to stick to languages that give the programmer
much less opportunity to be shown up.

Those languages aren't free of messy people, they just don't express
the messiness of those people as well.

[toc] | [prev] | [next] | [standalone]

#59652

Julian Fondren <julian.fondren@gmail.com> writes:
>On my scales this isn't much of a problem, but I can easily imagine
>someone who would, rather than laugh and say "oh, that's due to some
>incomplete refactoring", would be angry and humiliated by someone
>patching SWAP SWAP -tier stack manipulation out from his code. Better
>for a person like that to stick to languages that give the programmer
>much less opportunity to be shown up.
>
>Those languages aren't free of messy people, they just don't express
>the messiness of those people as well.

In my experience every language makes it easy to express the
functionality in code that can be easily condensed further.  In our
introductory programming course, I see more people writing

if (a<b)
  return true;
else
  return false;

than 

return a<b;

And even though we don't teach them to, there are lots of people
writing getter and setter methods for all fields of a class (and
getters and setters have recently been advocated as good practice
here).

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2017: http://www.euroforth.org/ef17/

[toc] | [prev] | [next] | [standalone]

#59671

No, I stay with Forth. I never succed passing the compilers control in the other languages.

During my make-over the time has come to the locals. Since I wasn't aware of the
ANS standard LOCALS|, I used soft stacks. Change to ANS locals made the system
run surprisingly faster. So bigintegers already is more than twice as fast - just enhence the
juggling words and using locals.

[toc] | [prev] | [next] | [standalone]

#59716

lehs <skydda.barnen@gmail.com> writes:
>ANS standard LOCALS|

Note that LOCALS| is obsolescent.  Instead of 

LOCALS| this read can you |

the Forth-2012 way is to write

{: you can read this :}

If your system does not have {: yet, you can find an implementation at

http://www.forth200x.org/reference-implementations/locals.fs

You may also need to first load

http://www.forth200x.org/reference-implementations/parse-name.fs

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2017: http://www.euroforth.org/ef17/

[toc] | [prev] | [next] | [standalone]

#59720

In article <2017May22.133529@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>lehs <skydda.barnen@gmail.com> writes:
>>ANS standard LOCALS|
>
>Note that LOCALS| is obsolescent.  Instead of
>
>LOCALS| this read can you |
>
>the Forth-2012 way is to write
>
>{: you can read this :}
>
>If your system does not have {: yet, you can find an implementation at
>
>http://www.forth200x.org/reference-implementations/locals.fs

It is worthwhile to note that your system already must have locals
in the form of (LOCAL) from the Optional Locals Word Set
(ISO 94 section 13).

>
>You may also need to first load
>
>http://www.forth200x.org/reference-implementations/parse-name.fs
>
>- anton
>--
>M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
>comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
>     New standard: http://www.forth200x.org/forth200x.html
>   EuroForth 2017: http://www.euroforth.org/ef17/
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#59724

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>In article <2017May22.133529@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>lehs <skydda.barnen@gmail.com> writes:
>>>ANS standard LOCALS|
>>
>>Note that LOCALS| is obsolescent.  Instead of
>>
>>LOCALS| this read can you |
>>
>>the Forth-2012 way is to write
>>
>>{: you can read this :}
>>
>>If your system does not have {: yet, you can find an implementation at
>>
>>http://www.forth200x.org/reference-implementations/locals.fs
>
>It is worthwhile to note that your system already must have locals
>in the form of (LOCAL) from the Optional Locals Word Set
>(ISO 94 section 13).

Yes.  It also must have locals (actually locals-ext) to use LOCALS|,
so requiring (LOCAL) is not an additional burden on the system, at
least as far as Forth-94 is concerned.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2017: http://www.euroforth.org/ef17/

[toc] | [prev] | [next] | [standalone]

#59730

Den måndag 22 maj 2017 kl. 16:51:54 UTC+2 skrev Anton Ertl:
> albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> >In article <2017May22.133529@mips.complang.tuwien.ac.at>,
> >Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> >>lehs <skydda.barnen@gmail.com> writes:
> >>>ANS standard LOCALS|
> >>
> >>Note that LOCALS| is obsolescent.  Instead of
> >>
> >>LOCALS| this read can you |
> >>
> >>the Forth-2012 way is to write
> >>
> >>{: you can read this :}
> >>
> >>If your system does not have {: yet, you can find an implementation at
> >>
> >>http://www.forth200x.org/reference-implementations/locals.fs
> >
> >It is worthwhile to note that your system already must have locals
> >in the form of (LOCAL) from the Optional Locals Word Set
> >(ISO 94 section 13).
> 
> Yes.  It also must have locals (actually locals-ext) to use LOCALS|,
> so requiring (LOCAL) is not an additional burden on the system, at
> least as far as Forth-94 is concerned.
> 
> - anton
> -- 
> M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
> comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
>      New standard: http://www.forth200x.org/forth200x.html
>    EuroForth 2017: http://www.euroforth.org/ef17/

I like LOCALS| and I like to refer to an ANS standard. I was surprised over how fast locals is in GForth. Changing from soft stacks to locals made the system faster, about 50 % faster.

Using that fast locals could clean up some clean up code.

[toc] | [prev] | [next] | [standalone]

#60333

After a make-over of bigintegers it has become faster, about twice as fast, and it's still ANS Forth and portable as far as I know. Even to systems with big endians and maybe to 16 bit ANS Forth - but I cant test that. 

There is a lot of features in GForth would be nice to define in ANS Forth, for example the [: .... ;]:

include bigz.4th
\ https://github.com/Lehs/ANS-Forth-libraries

1 1000 [: locals| x | x isprime x 1- sqr and :] intcond cr zet.
{2,5,17,37,101,197,257,401,577,677} ok

creates the set of all primes p in the intervall 1...999 such that p-1 is a perfect square. 

Can [: and ;] be implemented with :noname only with ANS words? Also is it possible to merge [: and locals| to a word [:| so I can write:

{ 1 100 | all } zdup cartprod [:| y x | x y < y sqr and x isprime and x nextprime y > and ;] paircond cr zet.
{(3,4),(7,9),(13,16),(23,25),(31,36),(47,49),(61,64),(79,81)} ok

I've tried but I've forgotten most extending-the-compiler techniques.

[toc] | [prev] | [next] | [standalone]

#60353

On Monday, June 5, 2017 at 4:52:19 AM UTC-5, lehs wrote:
> Can [: and ;] be implemented with :noname only with ANS words?

Interactively, :noname ... ; is the same as [: ... ;]

They differ when compiled into a word.

Given [: , this should work for [:|

  : [:| postpone [: postpone locals| ; immediate

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web