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

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

Implementing lisp in Forth. Chapter 4.

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

Contents

  Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-08-29 18:41 +0200
    Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-08-29 09:39 -0700
      Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-08-30 10:49 +0200
    Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-08-29 09:46 -0700
      Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-08-30 11:07 +0200
        Re: Implementing lisp in Forth. Chapter 4. Rod Pemberton <NoHaveNotOne@zxdehrnyya.cam> - 2016-08-30 08:00 -0400
          Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-02 12:34 +0200
        Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-08-31 14:23 -0700
          Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-01 02:15 +0200
            Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-01 19:49 -0700
              Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-02 11:49 +0200
                Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-04 11:28 -0700
                  Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-05 03:31 +0200
                    Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-04 21:03 -0700
                    Re: Implementing lisp in Forth. Chapter 4. Spiros Bousbouras <spibou@gmail.com> - 2016-09-05 07:47 +0000
                      Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-05 12:05 +0200
                        Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-05 12:04 -0700
                          Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-06 11:48 +0200
                            Re: Implementing lisp in Forth. Chapter 4. Spiros Bousbouras <spibou@gmail.com> - 2016-09-06 15:32 +0000
                              Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-06 21:27 +0200
                                Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-06 19:50 +0000
                                  Re: Implementing lisp in Forth. Chapter 4. Stefan Monnier <monnier@iro.umontreal.ca> - 2016-09-08 12:15 -0400
                                    Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-08 20:09 +0200
                                      Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-08 12:34 -0700
                                      Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-12 10:17 +0000
                                        Re: Implementing lisp in Forth. Chapter 4. Stefan Monnier <monnier@iro.umontreal.ca> - 2016-09-12 11:50 -0400
                                          Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-12 16:48 +0000
                                            Re: Implementing lisp in Forth. Chapter 4. Stefan Monnier <monnier@iro.umontreal.ca> - 2016-09-12 13:41 -0400
                                Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-06 22:03 -0700
                                Re: Implementing lisp in Forth. Chapter 4. George Neuner <gneuner2@comcast.net> - 2016-09-08 16:50 -0400
                                  Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-08 16:34 -0700
                                    Re: Implementing lisp in Forth. Chapter 4. George Neuner <gneuner2@comcast.net> - 2016-09-09 00:12 -0400
                                      Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-08 22:22 -0700
                                Re: Implementing lisp in Forth. Chapter 4. Lars Brinkhoff <lars.spam@nocrew.org> - 2016-09-27 08:51 +0200
                                  Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-27 00:47 -0700
                        Re: Implementing lisp in Forth. Chapter 4. Spiros Bousbouras <spibou@gmail.com> - 2016-09-06 13:18 +0000
                          Re: Implementing lisp in Forth. Chapter 4. "WJ" <w_a_x_man@yahoo.com> - 2016-09-06 20:52 +0000
                          Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-11-02 19:15 +0100
                        Re: Implementing lisp in Forth. Chapter 4. Lars Brinkhoff <lars.spam@nocrew.org> - 2016-09-09 10:05 +0200
                          Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-12 10:11 +0000
                            Re: Implementing lisp in Forth. Chapter 4. Lars Brinkhoff <lars.spam@nocrew.org> - 2016-09-12 13:15 +0200
                              Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-12 17:25 +0000
                  Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-09 16:19 +0200
                    Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-09 10:55 -0700
                      Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-09 21:39 +0200
                        Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-09 13:06 -0700
                          Re: Implementing lisp in Forth. Chapter 4. franck.bensusan@gmail.com - 2016-09-10 07:23 -0700
                            Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-11 01:28 -0700
                            Re: Implementing lisp in Forth. Chapter 4. Spiros Bousbouras <spibou@gmail.com> - 2016-09-13 21:37 +0000
                              Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-14 09:55 +0200
                              Re: Implementing lisp in Forth. Chapter 4. franck.bensusan@gmail.com - 2016-09-14 01:04 -0700
                            Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-13 14:40 -0700
                              Re: Implementing lisp in Forth. Chapter 4. franck.bensusan@gmail.com - 2016-09-14 03:37 -0700
                  Re: Implementing lisp in Forth. Chapter 4. lawrencedo99@gmail.com - 2016-09-10 01:17 -0700
                    Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-10 12:01 -0700
                      Re: Implementing lisp in Forth. Chapter 4. lawrencedo99@gmail.com - 2016-09-10 21:57 -0700
                        Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-10 22:12 -0700
                          Re: Implementing lisp in Forth. Chapter 4. lawrencedo99@gmail.com - 2016-09-10 23:30 -0700
                            Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-10 23:48 -0700
                              Re: Implementing lisp in Forth. Chapter 4. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-09-11 02:59 -0500
                                Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-11 01:16 -0700
                                  Re: Implementing lisp in Forth. Chapter 4. lawrencedo99@gmail.com - 2016-09-11 19:02 -0700
                              Re: Implementing lisp in Forth. Chapter 4. lawrencedo99@gmail.com - 2016-09-11 19:00 -0700
                    Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-10 12:08 -0700
                    Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-12 09:43 +0000
                      Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-12 13:42 +0200
                        Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-12 17:26 +0000
                          Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-12 20:56 +0200
                            Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-12 13:08 -0700
                            Re: Implementing lisp in Forth. Chapter 4. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-14 07:38 +0000
      Re: Implementing lisp in Forth. Chapter 4. Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2016-09-30 07:48 +0100
        Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-30 11:22 +0200
        Re: Implementing lisp in Forth. Chapter 4. Paul Rubin <no.email@nospam.invalid> - 2016-09-30 18:36 -0700
          Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-10-01 11:19 +0200
            Re: Implementing lisp in Forth. Chapter 4. luser droog <mijoryx@yahoo.com> - 2016-10-01 19:34 -0700
    Implementing lisp in Forth. Garbage collection. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-06 12:30 +0200
      Re: Implementing lisp in Forth. Garbage collection. Spiros Bousbouras <spibou@gmail.com> - 2016-09-06 15:34 +0000
        Re: Implementing lisp in Forth. Garbage collection. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-06 21:12 +0200
      Re: Implementing lisp in Forth. Garbage collection. Paul Rubin <no.email@nospam.invalid> - 2016-09-06 14:52 -0700
        Re: Implementing lisp in Forth. Garbage collection. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-07 01:50 +0200
          Re: Implementing lisp in Forth. Garbage collection. Paul Rubin <no.email@nospam.invalid> - 2016-09-06 17:49 -0700
    Re: Implementing lisp in Forth. Chapter 4. luser droog <mijoryx@yahoo.com> - 2016-10-21 17:02 -0700
      Re: Implementing lisp in Forth. Chapter 4. albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-10-22 02:43 +0200

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

#50884

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> Lars Brinkhoff <lars.spam@nocrew.org> writes:
>>Can you make it Emacs Lisp, so we can use it to rewrite Emacs in Forth?
>>Just kidding.  Or maybe not?
> There is Forthmacs, but there the macro language is Forth.

I thought Forthmacs was a Forth implementation.  Did it have an Emacs
clone too?

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

#50902

Lars Brinkhoff <lars.spam@nocrew.org> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> Lars Brinkhoff <lars.spam@nocrew.org> writes:
>>>Can you make it Emacs Lisp, so we can use it to rewrite Emacs in Forth?
>>>Just kidding.  Or maybe not?
>> There is Forthmacs, but there the macro language is Forth.
>
>I thought Forthmacs was a Forth implementation.  Did it have an Emacs
>clone too?

I thought so, but I could be wrong.

- 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 2016: http://www.euroforth.org/ef16/

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

#50781

In article <87fupfo6xl.fsf@jester.gateway.pace.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>> The GC seems to be a difficult part. How can there be one if there
>> is no lisp yet to speak of? A c-library?
>
>Anton Ertl has already written one in Forth:
>
>  http://www.complang.tuwien.ac.at/forth/garbage-collection.zip
>
>It supplies an ALLOC word that gives you a chunk of memory of you
>desired size.  There is no corresponding FREE, since ALLOC notices if
>you're running low on memory, and performs a GC if you are.  I'm
>suggesting that you use Anton's package and write Lisp-callable words
>like CONS as Forth words that use ALLOC, so the GC part is already done
>for you.

Let's see. I want to show that Forth is an implementation language for
lisp. So I can't use a Forth that is c-based, then ultimately I would
create another c-based lisp. Boring. So I won't use gc.fs on gforth.
Porting gc.fs? It pulls in another 5 facilities, hmm. Including floating
point. Hmm. I just got fp recently on ciforth.

The alternative:
My ALLOCATE. It takes barely 2 screens. No dependancies. It works
with ciforth and I know it inside out. The discussion has shown that
any requirement that lisp might throw at it, I can add easily.

The choice is not hard.

>
>> The whole point of Forth is that such a reader be modular and handled
>> by the Forth interpreter. That is the crux of this exercise.
>
>If the exercise is just to write a Lisp reader in Forth, then ok; but in
>terms of getting a Lisp working, the reader is just a component.

No it isn't. It is to prove that the modular approach in Forth to
writing readers works for Lisp too. That is not a "Lisp reader in Forth".
My modular approach to denotations isn't even traditional Forth that
is stuck on recognizers, that were there in tforth 1993.

>
>>> instead oftreating "baz)))" as a Forth word?
>
>> I'll need a TOKEN2 with the second ?BLANK replaced by ?BLANK-OR-)
>> : ?BLANK-OR-) DUP &) = SWAP ?BLANK OR ;
>
>There are a few other characters like ' (quote) that you'll also want to
>treat specially.  It's not terrible but I don't see much gain from this
>approach.
>
>> Or I may just require (+ 1 2 3 baz )
>
>Noooo......

Just kidding, I can spare the two lines needed for that.

>
>> You got me wrong. I don't want to write a Lisp. I want to demonstrate
>> that Forth can be used to write a Lisp.
>
>I'm rather liking the idea of a Forth with a Lisp extension.  You could
>then use Forth directly to write the realtime or speed-intensive parts
>of a program and parts that need to address raw memory, and Lisp for
>higher-level parts, UI, etc.

This is of course the idea of using Forth as an implementation language.

Groetjes Albert

P.S. I'm getting more and more fond of a c-source I have.
It doesn't even use structs so it is dead-easy to transfer to
Forth. Once it works, I can make it better.
Already forgot from where it came ...
-- 
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]

#50785

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> The alternative: My ALLOCATE. It takes barely 2 screens. No
> dependancies. It works with ciforth and I know it inside out. The
> discussion has shown that any requirement that lisp might throw at it,
> I can add easily.  The choice is not hard.

Well, I understood you wanted to use ciforth, no problem.  I'm not
trying to pitch gc.fs: I've never used it myself, but I thought it was
intended to be fairly portable and I suggested it because it seemed like
the easiest way to go forward.  There's certainly other ways to handle
gc.

I'm not sure what you want to do with ALLOCATE though:

1. Don't collect garbage but just allocate til you run out of memory,
then give up, per your earlier post.  This is ok for testing and early
development, but in the end, you don't have Lisp if you can't reclaim
storage.

2. Add a gc.fs-style conservative gc to ALLOCATE.  That's fine though it
might be easier to just adapt gc.fs.

3. Implement some other gc scheme, e.g. a precise one with compaction.
This probably means keeping the Lisp heap separate from the Forth heap,
plus it complicates the interface between Lisp primitives and the GC.
But in some ways it's the most powerful approach.

Do you know what you have in mind?

>>in terms of getting a Lisp working, the reader is just a component.
> No it isn't. It is to prove that the modular approach in Forth to
> writing readers works for Lisp too.

The existence of parsing words shows that it doesn't even always work
for Forth.  It works often enough to be useful, for sure.  Another part
of the issue is that just as Forth users like to extend Forth syntax
with Forth, Lisp users like to extend the Lisp reader in Lisp.  You
might look at the spec for Common Lisp readers.  It's complicated and
I'm not saying you want to implement all of it, but looking at it might
give you ideas of what users like to do.

> My modular approach to denotations isn't even traditional Forth that
> is stuck on recognizers, that were there in tforth 1993.

I'm not sure what you're referring to but it sounds interesting--is
there more info online?

> P.S. I'm getting more and more fond of a c-source I have.  It doesn't
> even use structs so it is dead-easy to transfer to Forth.

Not sure what you mean: an existing Lisp in C?

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

#50786

In article <87twdpj6uo.fsf@jester.gateway.pace.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
<SNIP>
>
>I'm not sure what you want to do with ALLOCATE though:
>
>1. Don't collect garbage but just allocate til you run out of memory,
>then give up, per your earlier post.  This is ok for testing and early
>development, but in the end, you don't have Lisp if you can't reclaim
>storage.
>
>2. Add a gc.fs-style conservative gc to ALLOCATE.  That's fine though it
>might be easier to just adapt gc.fs.

This is a sequel to 1. My marking of the pieces in use will be exact,
so it is not a conservative gc. Then I've not given up on the idea
to just free things here and there which would work well with
my allocator.

>
>3. Implement some other gc scheme, e.g. a precise one with compaction.
>This probably means keeping the Lisp heap separate from the Forth heap,
>plus it complicates the interface between Lisp primitives and the GC.
>But in some ways it's the most powerful approach.

In particular there will be no fragmentation issues. Why is it that
I don't here about fragmentation in this context (of lisp)

>
>Do you know what you have in mind?
>
>>>in terms of getting a Lisp working, the reader is just a component.
>> No it isn't. It is to prove that the modular approach in Forth to
>> writing readers works for Lisp too.
>
>The existence of parsing words shows that it doesn't even always work
>for Forth.  It works often enough to be useful, for sure.  Another part
>of the issue is that just as Forth users like to extend Forth syntax
>with Forth, Lisp users like to extend the Lisp reader in Lisp.  You
>might look at the spec for Common Lisp readers.  It's complicated and
>I'm not saying you want to implement all of it, but looking at it might
>give you ideas of what users like to do.

If the basic Lisp facilities are there, I suppose the reader can be
extended in a Lisp way.

>
>> My modular approach to denotations isn't even traditional Forth that
>> is stuck on recognizers, that were there in tforth 1993.
>
>I'm not sure what you're referring to but it sounds interesting--is
>there more info online?

I'm referring to a trivial extension to Forth: if the search fails
and it is not a number, you've the option to execute some word.
This word can then interpret something as a special number or
whatever.
From the manual: ('thingies are vectors in tforth)
"
'NUMBER contains the execution token of the text interpreter
NUMBER? that converts a string to a number. It is executed whenever
Forth cannot find a word in the vocabulary. ... understands ...
different notations allowed in tforth.
... replace the content of 'NUMBER
however you should take care to obey its complicated stack behaviour.
... change without notice ..
"

You will find something similar probably in iForth, maybe even
the exact above text, as the iForth manual was copied from tForth.

>
>> P.S. I'm getting more and more fond of a c-source I have.  It doesn't
>> even use structs so it is dead-easy to transfer to Forth.
>
>Not sure what you mean: an existing Lisp in C?

Indeed. Also about 1000 lines, but I find it easier to understand than
the Forth Lisp from Anton Ertl's website. It contains comment on
the criticial spots.
Somwhat curious. It uses parallel arrays instead of structs.
So all lisp objects are just longs:
cdr[car[x]] instead of x.car->cdr

Groetjes Albert
-- 
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]

#50787

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>>2. Add a gc.fs-style conservative gc to ALLOCATE.
> My marking of the pieces in use will be exact, so it is not a
> conservative gc.

That complicates things somewhat but you get the benefit of an exact gc,
so fine.  I think Guile uses conservative gc partly to make writing C
extensions easier: they don't have to think about making sure
intermediate values are marked or how to mark any Lisp pointer that
might appear in a C structure, etc.  But requiring gc-aware extensions
isn't unbearable.

> Then I've not given up on the idea to just free things here and there
> which would work well with my allocator.

Well, it's a cost (complexity) vs benefit (speed-up) trade-off unless
you're worried about the gc missing stuff.

> In particular there will be no fragmentation issues. Why is it that
> I don't here about fragmentation in this context (of lisp)

With a conservative gc you can't prevent fragmentation.  The simplest
and most traditional exact gc (straightforward mark and sweep) doesn't
prevent fragmentation either.  Emacs has used non-compacting (except for
strings) mark/sweep for the past 30 years unless they changed it, and it
hasn't been a significant problem afaik.

If you want to defragment, the basic approaches are mark-and-compact, or
stop-and-copy.  Both of them relocating objects, which means any
pointers to those objects have to be updated.  Within those approaches
there are generational schemes that can improve performance a lot.
Hedgehog Lisp (https://github.com/sbp/hedgehog) has a simple
2-generation copying gc that you might examine.  There are some other
methods like having separate pages for each type of fixed-size object
("BIBOP", BIg Bag Of Pages) that I think have fallen into disuse.

In my experience, if you have a reasonable amount of memory, gc
performance isn't a big issue unless you've got a backend that generates
native machine code.  Otherwise your interpreter will spend most of its
time running user code rather than gc.

Here's a nice page about the Factor gc that I just happened to look at:

http://factor-language.blogspot.com/2009/11/mark-compact-garbage-collection-for.html

Factor uses a mark-compact scheme inspired by Clojure, that's also
described in the 2011 Jones et al book that's been mentioned here a few
times.

> I'm referring to a trivial extension to Forth: if the search fails
> and it is not a number, you've the option to execute some word.

I think you want to be able to call a user word even if the search
doesn't fail, or it's a number.  E.g. you may have to treat Lisp numbers
differently than Forth numbers.

>>Not sure what you mean: an existing Lisp in C?
> Indeed. Also about 1000 lines

Which one is that, if I can ask?  Is it online?

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

#50811

Le vendredi 9 septembre 2016 22:06:04 UTC+2, Paul Rubin a écrit :
> If you want to defragment, the basic approaches are mark-and-compact, or
> stop-and-copy.  Both of them relocating objects, which means any
> pointers to those objects have to be updated.  Within those approaches
> there are generational schemes that can improve performance a lot.
> Hedgehog Lisp (https://github.com/sbp/hedgehog) has a simple
> 2-generation copying gc that you might examine.  There are some other
> methods like having separate pages for each type of fixed-size object
> ("BIBOP", BIg Bag Of Pages) that I think have fallen into disuse.
> 

This is how Oforth allocates objects : using separate pages for
each object size. I didn't know this method has fallen into disuse. 
In fact, I though it was used a lot... 
Is there any drawback for this method to not be used anymore ? 
Not having fragmentation is better than needing a defragmentation phase, no ?

Anyway, still a BIBOP user here...

btw there is a page about how Oforth's GC works here :
http://www.oforth.com/memory.html

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

#50841

franck.bensusan@gmail.com writes:
>> ("BIBOP", BIg Bag Of Pages) that I think have fallen into disuse.
> This is how Oforth allocates objects...
> Is there any drawback for this method to not be used anymore ? 
> Not having fragmentation is better than needing a defragmentation
> phase, no ?

Well, I'm realizing my picture comes from talking to old-time Lisp guys
since I've never used a BIBOP system myself.  But my impression is that
BIBOP was used mostly in the era of expensive memory and comparatively
small address spaces.  For example, the PDP-10 had 18-bit addresses
(256k of 36-bit words = about 1MB of address space) and Maclisp on the
'10 used BIBOP.  The upper 9 bits of the 18-bit address indexed into a
512-entry segment table, and the segments were 512 words each.  (Thanks
to Alan Bawden for explaining this to me on comp.lang.lisp a while
back).  Once you get to 64-bit or even 32-bit addresses, those tables
start getting large and it's easier to put tags in the objects.

Lisp programs also have a fair number of arbitrary-sized objects like
strings and arrays, so there's still fragmentation issues.

Jones et al's book probably says more about this.  I might check it when
I get a chance.

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

#50949

On Sat, 10 Sep 2016 07:23:43 -0700 (PDT) franck.bensusan@gmail.com wrote:
> Paul Rubin on 2016-09-09T22:06:04+02:00
> > If you want to defragment, the basic approaches are mark-and-compact, or
> > stop-and-copy.  Both of them relocating objects, which means any
> > pointers to those objects have to be updated.  Within those approaches
> > there are generational schemes that can improve performance a lot.
> > Hedgehog Lisp (https://github.com/sbp/hedgehog) has a simple
> > 2-generation copying gc that you might examine.  There are some other
> > methods like having separate pages for each type of fixed-size object
> > ("BIBOP", BIg Bag Of Pages) that I think have fallen into disuse.
> 
> This is how Oforth allocates objects : using separate pages for
> each object size. I didn't know this method has fallen into disuse.
> In fact, I though it was used a lot...
> Is there any drawback for this method to not be used anymore ?
> Not having fragmentation is better than needing a defragmentation phase, no?
> 
> Anyway, still a BIBOP user here...
> 
> btw there is a page about how Oforth's GC works here :
> http://www.oforth.com/memory.html

I don't see what BiBOP has to do with defragmentation. Say you allocate
contiguous regions A , B , C , ... of the same type and a while afterwards ,
after garbage collection , the system sees that region B is no longer
accessed therefore it can be freed. Then either it copies the regions above B
to cover the range of addresses covered by B or you have fragmentation. As
far as I know , the usefulness of BiBOP is to save memory : instead of having
type tags for each allocated object you have 1 type tag per page so you can
determine the type of the object depending on which page it is allocated.
Obviously it would be impractical to do this for every type but it is
practical for the most commonly used types like integers.

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

#50957

In article <xk_Bz.1470863$3%1.1139973@fx40.am4>,
Spiros Bousbouras  <spibou@gmail.com> wrote:
>On Sat, 10 Sep 2016 07:23:43 -0700 (PDT) franck.bensusan@gmail.com wrote:
>> Paul Rubin on 2016-09-09T22:06:04+02:00
>> > If you want to defragment, the basic approaches are mark-and-compact, or
>> > stop-and-copy.  Both of them relocating objects, which means any
>> > pointers to those objects have to be updated.  Within those approaches
>> > there are generational schemes that can improve performance a lot.
>> > Hedgehog Lisp (https://github.com/sbp/hedgehog) has a simple
>> > 2-generation copying gc that you might examine.  There are some other
>> > methods like having separate pages for each type of fixed-size object
>> > ("BIBOP", BIg Bag Of Pages) that I think have fallen into disuse.
>>
>> This is how Oforth allocates objects : using separate pages for
>> each object size. I didn't know this method has fallen into disuse.
>> In fact, I though it was used a lot...
>> Is there any drawback for this method to not be used anymore ?
>> Not having fragmentation is better than needing a defragmentation phase, no?
>>
>> Anyway, still a BIBOP user here...
>>
>> btw there is a page about how Oforth's GC works here :
>> http://www.oforth.com/memory.html
>
>I don't see what BiBOP has to do with defragmentation. Say you allocate
>contiguous regions A , B , C , ... of the same type and a while afterwards ,
>after garbage collection , the system sees that region B is no longer
>accessed therefore it can be freed. Then either it copies the regions above B
>to cover the range of addresses covered by B or you have fragmentation. As
>far as I know , the usefulness of BiBOP is to save memory : instead of having
>type tags for each allocated object you have 1 type tag per page so you can
>determine the type of the object depending on which page it is allocated.
>Obviously it would be impractical to do this for every type but it is
>practical for the most commonly used types like integers.

I can see that. Suppose lisp object are normally 4 cells.
Then there are byte sequences (like character strings) and arrays
(like bignums). If the lisp objects are in a separate space,
you need not compact. In the above example, B can never become
an unusable fragment because one lisp object was there, and one new lisp
object still fits there.

Groetjes Albert
-- 
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]

#50960

Le mardi 13 septembre 2016 23:37:35 UTC+2, Spiros Bousbouras a écrit :
> On Sat, 10 Sep 2016 07:23:43 -0700 (PDT) franck.bensusan@gmail.com wrote:
> > Paul Rubin on 2016-09-09T22:06:04+02:00
> > > If you want to defragment, the basic approaches are mark-and-compact, or
> > > stop-and-copy.  Both of them relocating objects, which means any
> > > pointers to those objects have to be updated.  Within those approaches
> > > there are generational schemes that can improve performance a lot.
> > > Hedgehog Lisp (https://github.com/sbp/hedgehog) has a simple
> > > 2-generation copying gc that you might examine.  There are some other
> > > methods like having separate pages for each type of fixed-size object
> > > ("BIBOP", BIg Bag Of Pages) that I think have fallen into disuse.
> > 
> > This is how Oforth allocates objects : using separate pages for
> > each object size. I didn't know this method has fallen into disuse.
> > In fact, I though it was used a lot...
> > Is there any drawback for this method to not be used anymore ?
> > Not having fragmentation is better than needing a defragmentation phase, no?
> > 
> > Anyway, still a BIBOP user here...
> > 
> > btw there is a page about how Oforth's GC works here :
> > http://www.oforth.com/memory.html
> 
> I don't see what BiBOP has to do with defragmentation. Say you allocate
> contiguous regions A , B , C , ... of the same type and a while afterwards ,
> after garbage collection , the system sees that region B is no longer
> accessed therefore it can be freed. Then either it copies the regions above B
> to cover the range of addresses covered by B or you have fragmentation. As
> far as I know , the usefulness of BiBOP is to save memory : instead of having
> type tags for each allocated object you have 1 type tag per page so you can
> determine the type of the object depending on which page it is allocated.
> Obviously it would be impractical to do this for every type but it is
> practical for the most commonly used types like integers.


I'am not sure Oforth is a BIBOP system (I didn't know the name before Paul
used it) but Oforth allocates objects according to their size (ie number 
of attributes).

If you allocate contiguous regions A, B, C in the same page, it
means that objects at A, B and C addresses have the same size 
(but not necessarily the same type).

You are right, if the GC releases region B because the object is 
no more used, fragmentation happens, but the next (well, perhap's not
the next) object to be allocated with the same number of attributes ie the
same size (even if not the same type), will be allocated at B region,
because size of region B is exactly the size needed for the object to be 
allocated.

So objects allocation resorbs fragmentation : there is no compact or 
defragmentation phase during the GC (no copy, no pointer update, ...).

Franck

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

#50950

franck.bensusan@gmail.com writes:
> btw there is a page about how Oforth's GC works here :

Franck, was Oforth ever released as source code?  Are you still thinking
of doing that?  I half-remember an old conversation where you weren't
sure.  It's a nice looking system.

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

#50967

Le mardi 13 septembre 2016 23:41:00 UTC+2, Paul Rubin a écrit :
> franck.bensusan@gmail.com writes:
> > btw there is a page about how Oforth's GC works here :
> 
> Franck, was Oforth ever released as source code?  Are you still thinking
> of doing that?  I half-remember an old conversation where you weren't
> sure.  It's a nice looking system.

Thanks,

Yes, its planned for the V1.0 release.
Problem is V1.0 release date...
I think there will be another minor release, then V1.0

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

#50804

On Monday, September 5, 2016 at 6:28:59 AM UTC+12, Paul Rubin wrote:
> ... ALLOC notices if you're running low on memory, and performs a GC if you
> are.

How does it decide when you are “running low on memory”? Does it limit your heap size, like Java does?

Why not use reference-counting as a first resort, only falling back to GC when you need to, like Perl and Python do?

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

#50820

lawrencedo99@gmail.com writes:
>> ... ALLOC notices if you're running low on memory
> How does it decide when you are “running low on memory”?

"running low on memory" was a poor choice of words.  In the case of
gc.fs, I believe it gc's after every N bytes of allocations, where N is
a parameter you can set.  That is typical of simple gc's.  But I don't
have it in front of me.   Fancier GC's use more complicated schemes to
decide when and how to gc.

> Does it limit your heap size, like Java does?

You can set the gc.fs heap size to your liking when you initialize the
gc, but once you do, it can't be changed.

Java allows you to limit the heap size with the -Xmx option but doesn't
require you to, I thought.

> Why not use reference-counting as a first resort, only falling back to
> GC when you need to, like Perl and Python do?

I can't speak for Perl but I think refcounting was a poor design
decision in CPython.  It had a period of usefulness because before the
addition of the "with" statement, people relied on its undocumented
behaviour of finalizing objects as soon as the last reference went away
as a poor man's RAII.  But "with" and context managers are the right way
to do that in Python.  Refcounting clutters up the C API, misses
reclaiming cyclic data (so a gc had to be added after the fact), is
slower than decent gc even in a single thread, mandates the notorious
GIL when multiple threads are running, etc.

I don't know of any other Python implementations besides CPython that
use refcounting.  PyPy, MicroPython, IronPython, Jython, and another one
whose name I've forgotten all use gc.  Afaict, refcounting is a simple
and easily understood method that tempts naive programmers but gc is
better in most situations.

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

#50833

On Sunday, September 11, 2016 at 7:01:18 AM UTC+12, Paul Rubin wrote:

> Lawrence D’Oliveiro writes:
>
>> Does it limit your heap size, like Java does?
> 
> Java allows you to limit the heap size with the -Xmx option but doesn't
> require you to, I thought.

There is always a limit. If you don’t specify a limit, the Sun/Oracle Java VM calculates one for you <http://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/sizing.html#sthref22>. On Android, there is a fixed size, dependent on the device/OS build, that you cannot change--typically well under 100MB.

>> Why not use reference-counting as a first resort, only falling back to
>> GC when you need to, like Perl and Python do?
> 
> I can't speak for Perl but I think refcounting was a poor design
> decision in CPython.  It had a period of usefulness because before the
> addition of the "with" statement, people relied on its undocumented
> behaviour of finalizing objects as soon as the last reference went away
> as a poor man's RAII.  But "with" and context managers are the right way
> to do that in Python.

You are confusing two different things: efficient memory utilization, and semantically-guaranteed cleanup in the presence of exceptions.

> Refcounting clutters up the C API, misses reclaiming cyclic data
> (so a gc had to be added after the fact), is slower than decent gc even in
> a single thread, mandates the notorious GIL when multiple threads are
> running, etc.

The cyclic issue was why I said to use it as a “first resort”.

None of the rest of what you said is true. Example: the Linux kernel, which makes heavy use of reference-counting for its objects, yet manages to have high enough performance, and versatility, to be able to run on hardware as modest as Blackfin or ARM, all the way up to the world’s most powerful mainframes and supercomputers <http://lxr.free-electrons.com/source/arch/>. That includes massively-parallel hardware with thousands of cores.

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

#50834

lawrencedo99@gmail.com writes:
> There is always a limit. If you don’t specify a limit, the Sun/Oracle
> Java VM calculates one for you Android, there is a fixed size,

No idea about Android, I've only used java on servers.  I thought it
would just eat all the system memory if you didn't use -Xmx.  But
whatever.  Certainly other systems do that.

> None of the rest of what you said is true. Example: the Linux kernel,
> which makes heavy use of reference-counting for its objects,

That's somewhat different from a language implementation where there are
lots of structures with pointers and arbitrarily deep indirection, new
objects being allocated willy nilly etc.

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

#50835

On Sunday, September 11, 2016 at 5:12:59 PM UTC+12, Paul Rubin wrote:
> Lawrence D’Oliveiro writes:
>> There is always a limit. If you don’t specify a limit, the Sun/Oracle
>> Java VM calculates one for you Android, there is a fixed size,
> 
> I thought it would just eat all the system memory if you didn't use -Xmx.

That’s the big drawback with garbage collection.

>> None of the rest of what you said is true. Example: the Linux kernel,
>> which makes heavy use of reference-counting for its objects...
> 
> That's somewhat different from a language implementation where there are
> lots of structures with pointers and arbitrarily deep indirection, new
> objects being allocated willy nilly etc.

In other words, rather like a multiuser, multitasking, multiprocessing kernel running lots of concurrent applications on large, complex hardware with hardware virtualization, software-defined-networking, complex memory models, virtual filesystems and next-generation filesystems like ZFS or btrfs?

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

#50836

lawrencedo99@gmail.com writes:
>> I thought it would just eat all the system memory if you didn't use -Xmx.
> That’s the big drawback with garbage collection.

I dunno, if you have the memory then it's reasonable for the server to
expect that you want to use it.  If you want to use only part of it,
there's the -Xmx option for that purpose.  Weren't you complaining
earlier that it DID set a limit?  It's been a long while since I used it
so I don't remember what the default was, but I'd had the idea that it
was basically the amount of physical memory available.

> In other words, rather like a multiuser, multitasking, multiprocessing
> kernel running lots of concurrent applications on large, complex

We were talking about language implementations, which allocate a lot of
small objects (like cons cells in the case of lisp) rapidly, have
complicated and unpredictable reference graphs, etc.  In CPython, even
small integers like 135 are heap-allocated (integers less than 100 are
specially cached iirc).  That's a problem with different trade-offs than
an OS tracking large objects like page buffers, where the pointers live
in only a few types of other objects.  I do remember that Git uses
garbage collection on disk, though I have no idea how it works
underneath.

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

#50838

Paul Rubin <no.email@nospam.invalid> wrote:
> lawrencedo99@gmail.com writes:
> 
>> In other words, rather like a multiuser, multitasking, multiprocessing
>> kernel running lots of concurrent applications on large, complex
> 
> We were talking about language implementations, which allocate a lot
> of small objects (like cons cells in the case of lisp) rapidly, have
> complicated and unpredictable reference graphs, etc.  In CPython,
> even small integers like 135 are heap-allocated (integers less than
> 100 are specially cached iirc).

You're exactly right, and it's simple to see why.  With multi-core
systems and reference counting you need an atomic compare-and-
increment operation every time that you change a pointer.  Even worse,
that CAS is in the target of the pointer and causes lots of cache
maintanenance traffic.

Andrew.

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

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

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

csiph-web