Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #50554 > unrolled thread
| Started by | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| First post | 2016-08-29 18:41 +0200 |
| Last post | 2016-10-22 02:43 +0200 |
| Articles | 20 on this page of 83 — 14 participants |
Back to article view | Back to comp.lang.forth
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 1 of 5 [1] 2 3 4 5 Next page →
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-08-29 18:41 +0200 |
| Subject | Implementing lisp in Forth. Chapter 4. |
| Message-ID | <nq1ojd$rvh$1@cherry.spenarnc.xs4all.nl> |
The following is inspired by the website
http://www.buildyourownlisp.com
This site is beyond brilliant. A comparison with the lisp's in
Forth I've seen is ... well let's not compare.
The idea behind this website is that the best way to learn
programming in C is to build a lisp.
We all know that the best way to learn Forth is to build a Forth.
That I've done already. Now I'll improve my Forth skills and,
probably, my Forth by trying to build a lisp.
Moreover I'll try to prove that ciforth is a superior implementation
language. That means I'll use its full power, without regards to ISO
to build a lisp that is on a par with one written in C.
The lisp has the silly Dutch name "effelispe". I leave it to the community
to properly pronounce it in their own language.
I don't need to learn programming in C. So we start with chapter 4.
This is about making a REPL , a read-evaluate-print-loop, what we call
the high level interpreter.
The first version of the REPL is a program that you can call names
and then it gets right back at you.
Here is a session of this program from the site, as presented there.
*****************************************************
* Lispy Version 0.0.0.0.1 *
* Press Ctrl+c to Exit *
* *
* lispy> hello *
* No You're a hello *
* lispy> my name is Dan *
* No You're a my name is Dan *
* lispy> Stop being so rude! *
* No You're a Stop being so rude! *
* lispy> *
*****************************************************
My version handling is done by RCS so my init is
: init "
effelispe snapshot $Revision: 1.2 $ $Date: 2016/08/29 16:32:15 $
Supplied under GPL 2.0, quality but no warranty
Press Ctrl+c to Exit
" TYPE ;
The prompt is handled by revectoring OK:
: prompt "
effelispe>" TYPE ;
'prompt >DFA @ 'OK >DFA !
This is a prompt in the sense of "Hurry up dummy!" as Charles Moore
put it, so the program will need an extra prompt between the init
and the REPL. Our REPL is of course just QUIT.
: repl init prompt QUIT ;
That was though. Now for the fun part.
We need a word to reflect what its input like so:
WANT .FORMAT
: YOU'RE NAME "No You're a %s %n" .FORMAT ; PREFIX
Let's try it
*****************************************************
* YOU'RE douche-bak *
* No You're a douche-bak *
* OK *
* YOU'REdouche-bak *
* No You're a douche-bak *
*****************************************************
Because it is a prefix, it can get a TOKEN that is collated.
Let's get the name of NAME correct while we're at it:
"TOKEN" $, 'NAME >NFA !
The word NAME has its name changed in TOKEN.
The rest is easy:
"" $, 'YOU'RE >NFA !
Now YOU'RE has become an empty prefix that will match everything.
After gathering the code an executable is made with :
lina64 -c effelispe.frt
Let's see whether it behaves.
* *******************************************************************
* ~/PROJECT/ciforth/lisp$ effelispe *
* *
* effelispe snapshot $Revision: 1.2 $ $Date: 2016/08/29 16:32:15 $ *
* Supplied under GPL 2.0, quality but no warranty *
* Press Ctrl+c to Exit *
* *
* effelispe>douche-bak *
* No You're a douche-bak *
* *
* effelispe>kloho *
* No You're a kloho *
* *
* effelispe>^C *
* ~/PROJECT/ciforth/lisp$ *
* *******************************************************************
For good measure here is version 4 of the program. (I'll follow
the chapter numbering.)
----------------------------------8<--------------------------------
\ $Id: chap4.txt,v 1.2 2016/08/29 16:32:15 albert Exp $
\ Copyright (2016): Albert van der Horst {by GNU Public License}
WANT .FORMAT
: init "
effelispe snapshot $Revision: 1.2 $ $Date: 2016/08/29 16:32:15 $
Supplied under GPL 2.0, quality but no warranty
Press Ctrl+c to Exit
" TYPE ;
\ Replace Forth prompt.
: prompt CR "effelispe>" TYPE ;
'prompt >DFA @ 'OK >DFA !
\ Change the name of NAME to TOKEN.
"TOKEN" $, 'NAME >NFA !
\ Calling names.
: YOU'RE TOKEN "No You're a %s %n" .FORMAT ; PREFIX
: install-repl "" $, 'YOU'RE >NFA ! ;
: doit install-repl init prompt QUIT ;
----------------------------------8<--------------------------------
The installation of the repl must wait till run time, otherwise
the compiler starts calling you names ("No You're a TURKEY")
Groetjes Albert
P.S. I hope douche-bak is not too offensive. I heard it in comedy
series like Southpark and I've no idea what it means.
--
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] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-08-29 09:39 -0700 |
| Message-ID | <87fupnpm1g.fsf@jester.gateway.pace.com> |
| In reply to | #50554 |
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: > P.S. I hope douche-bak is not too offensive. I heard it in comedy > series like Southpark and I've no idea what it means. The word is "douche bag" and you could look it up :).
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-08-30 10:49 +0200 |
| Message-ID | <nq3hb2$2oq$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50555 |
In article <87fupnpm1g.fsf@jester.gateway.pace.com>, Paul Rubin <no.email@nospam.invalid> wrote: >albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: >> P.S. I hope douche-bak is not too offensive. I heard it in comedy >> series like Southpark and I've no idea what it means. > >The word is "douche bag" and you could look it up :). I forgot the smiley. Actually douche bak is the Dutch name for the part of a douche that catches the water, and kloho is not a word, but could be associated with an offensive peiorative. If HA publishes his Straight Forth , the publisher will ask him to change his "hotties" example. I can have nothing of that. 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]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-08-29 09:46 -0700 |
| Message-ID | <87bn0bplpm.fsf@jester.gateway.pace.com> |
| In reply to | #50554 |
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: > The following is inspired by the website > http://www.buildyourownlisp.com > This site is beyond brilliant. A comparison with the lisp's in > Forth I've seen is ... well let's not compare. You might also like: https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours Or just look at source code of many of the Lisps out there that are written in C or in Lisp itself. You should probably also read SICP at some point: https://mitpress.mit.edu/sicp/ It looks like the Lisp from buildyourownlisp.com is very limited.
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-08-30 11:07 +0200 |
| Message-ID | <nq3ibl$2u3$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50556 |
In article <87bn0bplpm.fsf@jester.gateway.pace.com>, Paul Rubin <no.email@nospam.invalid> wrote: >albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: >> The following is inspired by the website >> http://www.buildyourownlisp.com >> This site is beyond brilliant. A comparison with the lisp's in >> Forth I've seen is ... well let's not compare. > >You might also like: > >https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours This looks similar, but I don't know Haskell. On the other hand, c I know inside out. > >Or just look at source code of many of the Lisps out there that are >written in C or in Lisp itself. Done that, but a step by step instruction for a familiar language with lots of explanation is hard to beat. I've a lisp in C and it works. I've seen the undocumented lisp in Forth and I can't even run the example. I estimate my changes for a 10 hour search to get something better very slim. > >You should probably also read SICP at some point: > > https://mitpress.mit.edu/sicp/ I'm almost at the end. > >It looks like the Lisp from buildyourownlisp.com is very limited. Please elaborate. I see chapter 16, " Only the Beginning ". This is what the author proposes to add with some remarks about how to do it. That suggests to me that the lisp generated is a reasonable starting point. Native Types User Defined Types List Literal Operating System Interaction Macros Variable Hashtable Pool Allocation Garbage Collection Tail Call Optimisation Lexical Scoping Static Typing Conclusion Which of those are in the 1000 lines toy lisps that is written in Forth or c anyway? Note that my ambition goes no further than writing such a toy lisp but with mature implementation techniques such that one could seriously consider Forth to be an implementation language for other languages. Thanks for the comment. I hope you will look at the next chapters too. The next step is parsing. It generates data structures. It will require major design decisions how to do that in Forth. My hope is that by allocating part of those structures (objects) on the data stack, much of the freeing will be swift and painless. 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]
| From | Rod Pemberton <NoHaveNotOne@zxdehrnyya.cam> |
|---|---|
| Date | 2016-08-30 08:00 -0400 |
| Message-ID | <20160830080019.141d1792@_> |
| In reply to | #50567 |
On Tue, 30 Aug 2016 11:07:01 +0200 (CEST) albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) wrote: > Paul Rubin <no.email@nospam.invalid> wrote: > >Or just look at source code of many of the Lisps out there that are > >written in C or in Lisp itself. > > Done that, but a step by step instruction for a familiar > language with lots of explanation is hard to beat. I've a lisp > in C and it works. I've seen the undocumented lisp in Forth > and I can't even run the example. > I estimate my changes for a 10 hour search to get something > better very slim. > LISP can be built up from a small set of primitives just like Forth. Stutter lisp car, cdr, cons, equal, if, lambda, quote, set https://groups.google.com/d/msg/comp.lang.lisp/priOn-wu2Ek/cNlWzkYxJ0kJ Message-ID: <3985f411.278996525@judy>#1/1 McCarthy atom, car, cdr, cons, eq https://groups.google.com/d/msg/comp.lang.lisp/k8PZ8a9qJwc/iGWw9r8CO9EJ Message-ID: <1136@wrs.wrs.com> common atom, car, cdr, cond, cons, eq, lambda, quote https://groups.google.com/d/msg/comp.lang.lisp/NYMDTjWKJPg/j-bQ2NRynpgJ Message-ID: <87vff8xxjs.fsf@thalassa.informatimago.com> minimal CL atom, car, cdr, cond, cons, defun, eq, quote https://groups.google.com/d/msg/comp.lang.lisp/hYJBg3PzgDw/UAQ4ZcsQ-E4J Message-ID: <1153129866.032243.27260@m73g2000cwd.googlegroups.com> Rod Pemberton
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-09-02 12:34 +0200 |
| Message-ID | <nqbkj3$4qk$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50570 |
In article <20160830080019.141d1792@_>, Rod Pemberton <NoHaveNotOne@zxdehrnyya.cam> wrote: >On Tue, 30 Aug 2016 11:07:01 +0200 (CEST) >albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) wrote: > >> Paul Rubin <no.email@nospam.invalid> wrote: > >> >Or just look at source code of many of the Lisps out there that are >> >written in C or in Lisp itself. >> >> Done that, but a step by step instruction for a familiar >> language with lots of explanation is hard to beat. I've a lisp >> in C and it works. I've seen the undocumented lisp in Forth >> and I can't even run the example. >> I estimate my changes for a 10 hour search to get something >> better very slim. >> > >LISP can be built up from a small set of primitives just like Forth. > >Stutter lisp >car, cdr, cons, equal, if, lambda, quote, set >https://groups.google.com/d/msg/comp.lang.lisp/priOn-wu2Ek/cNlWzkYxJ0kJ >Message-ID: <3985f411.278996525@judy>#1/1 > >McCarthy >atom, car, cdr, cons, eq >https://groups.google.com/d/msg/comp.lang.lisp/k8PZ8a9qJwc/iGWw9r8CO9EJ >Message-ID: <1136@wrs.wrs.com> > >common >atom, car, cdr, cond, cons, eq, lambda, quote >https://groups.google.com/d/msg/comp.lang.lisp/NYMDTjWKJPg/j-bQ2NRynpgJ >Message-ID: <87vff8xxjs.fsf@thalassa.informatimago.com> > >minimal CL >atom, car, cdr, cond, cons, defun, eq, quote >https://groups.google.com/d/msg/comp.lang.lisp/hYJBg3PzgDw/UAQ4ZcsQ-E4J >Message-ID: <1153129866.032243.27260@m73g2000cwd.googlegroups.com> Interesting and hope giving. I feel that this may not be the same as what Forthers mean by a minimal set. How could you multiply two numbers in such a lisp, or write a program to do that, or even represent numbers? The only way I can think off is the Turing machine way, using a sequence of loose bits or maybe digits. >Rod Pemberton -- 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]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-08-31 14:23 -0700 |
| Message-ID | <8737lkpr8n.fsf@jester.gateway.pace.com> |
| In reply to | #50567 |
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: > Native Types ... > Which of those are in the 1000 lines toy lisps that is written > in Forth or c anyway? That is all pretty standard, though 1kloc may be a bit light. You could look at the early versions of SIOD (Scheme In One Day) by George Carrette, or more recently Tinyscheme (used in GIMP etc). > Thanks for the comment. I hope you will look at the next chapters too. > The next step is parsing. It generates data structures. It will require > major design decisions how to do that in Forth. My hope is that by > allocating part of those structures (objects) on the data stack, much > of the freeing will be swift and painless. That's not realistic, a useful Lisp needs garbage collection. I'm not impressed by that book's approach to parsing either (using fancy parser combinators written in C). Lisp is syntactically very simple, almost like Forth. Forth just uses non-whitespace tokens delimited by whitespace, giving a linear structure. Lisp adds parentheses to denote lists of conses, so you get tree structure. I haven't completely thought this through so maybe there is a fatal flaw, but if I wanted to write a Lisp in Forth, I'd consider this approach: - write the reader and printer in Lisp, using an existing Lisp for bootstrapping and testing. - Write the usual Lisp primitives (CONS, CAR, CDR) etc. as Forth words that call alloc to get storage for new conses. - Have the reader intern new symbols into the Forth dictionary (might need carnal knowledge or hacking of your Forth) putting DEFER around everything, since Lisp uses late binding. Self-evaluating symbols would call a Forth word that takes an address arg. (define (f x) ...) would make an IS to actually bind the "f" symbol (earlier interned as a deferred) to a code address. - Use Anton's Boehm-style garbage collector instead of attempting precise GC - Don't have an evaluator but instead have a compiler written in Lisp, that tree-walks Lisp functions and emits Forth code, either as threaded code to be run by your Forth's address interpreter, or as Forth source code that you'd pass through a text interpreter. (It wouldn't look like human-written code because of all the deferred symbols, the use of special Lisp operators like "Lisp+" instead of "+" that would have to dispatch on types, etc. But still, now your Lisp code can call Forth words and vice versa, maybe using a small FFI to convert between tagged and untagged values.
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-09-01 02:15 +0200 |
| Message-ID | <nq7rv3$lhl$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50585 |
In article <8737lkpr8n.fsf@jester.gateway.pace.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
>albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>> Native Types ...
>> Which of those are in the 1000 lines toy lisps that is written
>> in Forth or c anyway?
>
>That is all pretty standard, though 1kloc may be a bit light. You could
>look at the early versions of SIOD (Scheme In One Day) by George
>Carrette, or more recently Tinyscheme (used in GIMP etc).
>
>> Thanks for the comment. I hope you will look at the next chapters too.
>> The next step is parsing. It generates data structures. It will require
>> major design decisions how to do that in Forth. My hope is that by
>> allocating part of those structures (objects) on the data stack, much
>> of the freeing will be swift and painless.
>
>That's not realistic, a useful Lisp needs garbage collection.
Don't get me wrong, I understand that. But some allocate/free pairs
may be saved by using our usual stack approach for some of the
temporary data.
>
>I'm not impressed by that book's approach to parsing either (using fancy
>parser combinators written in C). Lisp is syntactically very simple,
>almost like Forth. Forth just uses non-whitespace tokens delimited by
>whitespace, giving a linear structure. Lisp adds parentheses to denote
>lists of conses, so you get tree structure.
Was gonna implement the parentheses as prefix/recognizer and no way
a overkill c-library to be used.
way a
>
>I haven't completely thought this through so maybe there is a fatal
>flaw, but if I wanted to write a Lisp in Forth, I'd consider this
>approach:
There may be a fatal flaw. The lists of lvalues are not with links but
are allocated arrays. If an lvalue is appended the arrays is
realloced. If the first value is to be removed the array is moved
down. This looks like O(N^2) but it all depends on what lvalues are
and how long these lists grow. It may be a reasonable design choice
but at first sight it smells.
>
>- write the reader and printer in Lisp, using an existing Lisp for
> bootstrapping and testing.
>
>- Write the usual Lisp primitives (CONS, CAR, CDR) etc. as Forth words
> that call alloc to get storage for new conses.
>
>- Have the reader intern new symbols into the Forth dictionary (might
> need carnal knowledge or hacking of your Forth) putting DEFER
> around everything, since Lisp uses late binding. Self-evaluating
> symbols would call a Forth word that takes an address arg.
> (define (f x) ...) would make an IS to actually bind the "f" symbol
> (earlier interned as a deferred) to a code address.
>
>- Use Anton's Boehm-style garbage collector instead of attempting
> precise GC
>
>- Don't have an evaluator but instead have a compiler written in Lisp,
> that tree-walks Lisp functions and emits Forth code, either as
> threaded code to be run by your Forth's address interpreter, or as
> Forth source code that you'd pass through a text interpreter. (It
> wouldn't look like human-written code because of all the deferred
> symbols, the use of special Lisp operators like "Lisp+" instead of "+"
> that would have to dispatch on types, etc. But still, now your Lisp
> code can call Forth words and vice versa, maybe using a small
> FFI to convert between tagged and untagged values.
My idea was for e.g.
(* 1 20 (+ 1 2 3) )
a LISP vacobulary with compiling words
( prefix
*
+
-
- prefix
0 prefix
...
9 prefix
All words are compiling.
Then after the line is compiled, there is tree structure
that if EXECUTEd in the Forth sense result in an evaluation
of the expression.
So the parsing of 12
results in a loose Forth word that pushes the atom 12 to the stack.
My PREFIXes have no trouble with that.
Something along the lines of
'BL >CFA @ CONSTANT docon \ code routine for constants.
HERE 1)
docon , \ code field
( 12 ) , \ data field
_ , \ flag field
_ , \ name field
_ , \ link field
_ , \ source field
The HERE can now be compiled into a list using , ( putisically COMPILE,)
The above example would look decompiled
: temp1 + 1 2 3 ;
: temp2 * 1 20 temp1 ;
The * in the lisp vocabulary would look like
: *
DEPTH temp !
CO \ execute remainder of caller
BEGIN DEPTH 1+ temp @ <> WHILE * ( Forth's *) REPEAT ;
(I see that you name that Lisp* )
I'll save this article of yours. There is a lot in it, that I
do not yet understand.
This saturday Willem Ouwerker is going to present a two and a
sex legged robot at a combined meeting of the Robot and AI
user groups. I'll meet an AI Lisp expert there.
Groetjes Albert
1)
(Of course all dummy fields can be left out, as docon doesn't
inspect them, but otherwise it looks like I was implmenting LIT).
--
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]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-09-01 19:49 -0700 |
| Message-ID | <87twdznhhz.fsf@jester.gateway.pace.com> |
| In reply to | #50587 |
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: >>a useful Lisp needs garbage collection. > Don't get me wrong, I understand that. But some allocate/free pairs > may be saved by using our usual stack approach Yes probably true, that's just an optimization though, and it's easiest to follow a straightforward approach first. If there's a GC you might as well use it, especially for stuff like the reader (Lisp terminology for the thing that parses S-expressions). Your Lisp isn't going to spend much of its time doing that. > Was gonna implement the parentheses as prefix/recognizer Would that also handle trailing parens (foo (bar (.... baz))) instead of treating "baz)))" as a Forth word? > There may be a fatal flaw. The lists of lvalues are not with links but > are allocated arrays. I'm not sure what you mean by that: traditionally you'd use cons nodes that each hold two values. > a LISP vacobulary with compiling words > ( prefix I wouldn't try to use the Forth text interpreter directly as a Lisp reader. You start wanting read macros written in Lisp, etc. Assuming the target machine is a PC or comparable, I wouldn't worry about the efficiency of the reader. I doubt you're planning to run megabytes of Lisp code. > This saturday Willem Ouwerker is going to present a two and a > sex legged robot at a combined meeting of the Robot and AI > user groups. I'll meet an AI Lisp expert there. Nice. It occurs to me given your interest in Euler problems, that your Lisp should also have bignums.
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-09-02 11:49 +0200 |
| Message-ID | <nqbhus$4fp$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50603 |
In article <87twdznhhz.fsf@jester.gateway.pace.com>, Paul Rubin <no.email@nospam.invalid> wrote: >albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: >>>a useful Lisp needs garbage collection. >> Don't get me wrong, I understand that. But some allocate/free pairs >> may be saved by using our usual stack approach > >Yes probably true, that's just an optimization though, and it's easiest >to follow a straightforward approach first. If there's a GC you might >as well use it, especially for stuff like the reader (Lisp terminology >for the thing that parses S-expressions). Your Lisp isn't going to >spend much of its time doing that. That approach will be brutally straightforward, I promise. 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? 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. > >> Was gonna implement the parentheses as prefix/recognizer > >Would that also handle trailing parens (foo (bar (.... baz))) instead of >treating "baz)))" as a Forth word? You got me here. I've have to change PARSE-NAME aka token. : TOKEN _ BEGIN DROP PP@@ ?BLANK OVER SRC CELL+ @ - AND 0= UNTIL _ BEGIN DROP PP@@ ?BLANK UNTIL OVER - ; I'll need a TOKEN2 with the second ?BLANK replaced by ?BLANK-OR-) : ?BLANK-OR-) DUP &) = SWAP ?BLANK OR ; Or I may just require (+ 1 2 3 baz ) instead of (+ 1 2 3 baz) > >> There may be a fatal flaw. The lists of lvalues are not with links but >> are allocated arrays. > >I'm not sure what you mean by that: traditionally you'd use cons nodes >that each hold two values. > >> a LISP vacobulary with compiling words >> ( prefix > >I wouldn't try to use the Forth text interpreter directly as a Lisp >reader. You start wanting read macros written in Lisp, etc. Assuming >the target machine is a PC or comparable, I wouldn't worry about the >efficiency of the reader. I doubt you're planning to run megabytes of >Lisp code. > >> This saturday Willem Ouwerker is going to present a two and a >> sex legged robot at a combined meeting of the Robot and AI >> user groups. I'll meet an AI Lisp expert there. > >Nice. It occurs to me given your interest in Euler problems, that your >Lisp should also have bignums. 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. 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]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-09-04 11:28 -0700 |
| Message-ID | <87fupfo6xl.fsf@jester.gateway.pace.com> |
| In reply to | #50609 |
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. > 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. >> 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...... > 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.
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-09-05 03:31 +0200 |
| Message-ID | <nqihtb$vns$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50661 |
Newsgroups: comp.lang.forth
References: <nq1ojd$rvh$1@cherry.spenarnc.xs4all.nl> <87twdznhhz.fsf@jester.gateway.pace.com> <nqbhus$4fp$1@cherry.spenarnc.xs4all.nl> <87fupfo6xl.fsf@jester.gateway.pace.com>
Subject: Re: Implementing lisp in Forth. Chapter 4.
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.
The constraints that package imposes interferes with the non-existing
constraints I will impose on a yet non-existent lisp.
I tell you what I'll do. I just ALLOCATE away in my 16 Gbyte space.
If I know I can FREE I'll do it. Then I'll add GC as an afterthought.
That that is possible will be the final proof that my design was okay.
About garbage: Is this correct (the infamous Fibonacci series)?
After:
(define (fib n)
(do ((i 1 (+ 1 i))
(a 1 (+ a b))
(b 1 a ))
((>= i n ) b)))
the fib procedure remains there in all eternity and there is nothing
to collect. I can do (fib 10) any time I please.
Or will there be anonymous memory places and are the
boxes they are in such as (a,b,i,n) collectable?
But what with (directly calculating the 100-th fib number)
(do ((i 1 (+ 1 i))
(a 1 (+ a b))
(b 1 a ))
((>= i 100 ) b )
)
354224848179261915075
does that leave garbage in your run of the mill scheme?
(Because it might not in mine.)
In the procedure fib can I optimise the fib into machine code with
(optimise fib)
that optimises the underlying Forth code, without getting on
someones toes?
Obviously that may leave some garbage that may be harder to collect.
>
>> 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, not in the Forth philosophy. The reader is the glue and
Lisp doesn't exist, it is just turtles all the way down.
(If you don't get that, look at the number formatting in Forth, or
better still control flow. There is no number formatting. There are
just simple words, calling even simpler words.)
(It may well be that Lisp doesn't exist in the Lisp philosophy,
just cdr's all the way down to the atom's. Dunno yet.)
>
>>> 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.
It is not the gain, it is the loss. I loose an interpreter for Backus
Naur forms. Less is more.
>
>> Or I may just require (+ 1 2 3 baz )
>
>Noooo......
It is my party ... But as it just requires a couple of bytes,
I will make it even more complicated:
: ?BLANK-OR-SPECIAL >R """'])}" R@ $^ 0<> R> ?BLANK OR ;
>
>> 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.
I just read the description of Guile. That is a Scheme dialect and Scheme
is supposed to be simple. I can't detect the simplicity in it (not
from the info file). It kind of deters me.
I see that guile binary is 3K, that seems okay, but it calls
horrific c-libraries like the infamous readline, maybe even malloc.
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]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-09-04 21:03 -0700 |
| Message-ID | <87bn03ngbt.fsf@jester.gateway.pace.com> |
| In reply to | #50672 |
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: >> http://www.complang.tuwien.ac.at/forth/garbage-collection.zip > The constraints that package imposes interferes with the non-existing > constraints I will impose on a yet non-existent lisp. I'd be interested to know what your objections are. The technique that package uses works very well and its C counterpart is used in many real-world systems. > I tell you what I'll do. I just ALLOCATE away in my 16 Gbyte space. > If I know I can FREE I'll do it. Then I'll add GC as an afterthought. Well, that's a start, though if you were doing a serious implementation then a lot of the implementation details would be enmeshed in the gc strategy so you'd want to think it all through from the beginning. > the fib procedure remains there in all eternity and there is nothing > to collect. I can do (fib 10) any time I please. Or will there be > anonymous memory places and are the boxes they are in such as > (a,b,i,n) collectable? It depends on your scheme's implementation details, the number representation, etc. But if they are fixnums and you have a compiler that looks for such chances, that function can avoid consing. A simple implementation would just cons everything. CPython works like that (it caches 100 or so small integers and conses/gc's the rest) and tons of people use it. It's not as bad as it sounds. > 354224848179261915075 does that leave garbage in your run of the mill > scheme? Yes, bignums are usually heap-allocated so if you create them as intermediate results, they will leave garbage. > In the procedure fib can I optimise the fib into machine code with > (optimise fib) > that optimises the underlying Forth code, without getting on > someones toes? In principle that could be ok. You could look at Chicken Scheme, which compiles Scheme to C if I remember properly. > Obviously that may leave some garbage that may be harder to collect. I don't think you should worry about optimizing this, especially for your first implementation. Just spew garbage wherever it's convenient and let the GC take care of it. > No it isn't, not in the Forth philosophy. The reader is the glue and > Lisp doesn't exist, it is just turtles all the way down. But I thought the idea of implementing Lisp was so you could program with the Lisp philosophy, which is much different from the Forth philosophy. Forth is like building a brick outhouse, carefully cementing each brick in place before moving to the next, getting something compact and solid. Lisp is more like dancing in the air. You can create a palace of data with a wave of your hand, use it for something, then fly away from it, leaving the GC to reclaim the building materials for you to use in your next adventure. > (It may well be that Lisp doesn't exist in the Lisp philosophy, > just cdr's all the way down to the atom's. Dunno yet.) Lisp very much exists in the traditional Lisp philosophy (you can build up programs and eval them), even though this isn't supported in Scheme. > It is not the gain, it is the loss. I loose an interpreter for Backus > Naur forms. Less is more. There's no BNF in a usual Lisp reader, but rather just a simple recursive procedure that recognizes a few special characters and otherwise acts like a Forth parser. But you then have a tree to manipulate, maybe for macro expansion or other purposes. It's easier to handle that in Lisp than in Forth. > I just read the description of Guile. That is a Scheme dialect and > Scheme is supposed to be simple. I can't detect the simplicity in it > (not from the info file). It kind of deters me. I see that guile > binary is 3K, that seems okay, but it calls horrific c-libraries like > the infamous readline, maybe even malloc. Guile is quite large and complex these days, maybe to compete with higher end Javascript implementations like v8. That 3k binary is certainly a dynamic loader client that pulls in other libraries. It looks like libguile-2.0.so.22 on my system is about 1.6MB and it also pulls in a lot of other code. You might look at this old (2.0) version of SIOD if you want to see a minimal Scheme: http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/scheme/impl/siod/siod_20.tgz This version is nice because it has two different gc's (mark-sweep and copying) where you choose which one you want with a command line option. Each gc is just a few dozen LOC. Earlier versions only had the copying GC. Later versions became bigger and more complicated, maybe more useful for practical purposes, but less easy to study. SIOD stands for Scheme In One Day because the original version was supposedly written in under 24 hours. It's around 1 KLOC of C.
[toc] | [prev] | [next] | [standalone]
| From | Spiros Bousbouras <spibou@gmail.com> |
|---|---|
| Date | 2016-09-05 07:47 +0000 |
| Message-ID | <_p9zz.1142663$OC.48142@fx39.am4> |
| In reply to | #50672 |
On Mon, 5 Sep 2016 03:31:23 +0200 (CEST)
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) wrote:
>
> 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.
>
> The constraints that package imposes interferes with the non-existing
> constraints I will impose on a yet non-existent lisp.
> I tell you what I'll do. I just ALLOCATE away in my 16 Gbyte space.
> If I know I can FREE I'll do it. Then I'll add GC as an afterthought.
> That that is possible will be the final proof that my design was okay.
I don't think that garbage collection is something to be added as an
afterthought. The existence of garbage collection affects the allocation (and
possible recollection) of every object (see examples below) so it's one of
the issues you need to be thinking about from the start. It's likely more
fundamental than the syntax of the language. Having said that , it's not that
big a hurdle. I don't know why you don't like Anton Ertl's package but there
is also the Boehm-Demers-Weiser garbage collector which is used in Embeddable
Common Lisp , Guile Scheme and was used in an early implementation of Racket
Scheme. Even writing your own precise garbage collector is not terribly
difficult , see
http://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec24.htm
for a simple algorithm.
> About garbage: Is this correct (the infamous Fibonacci series)?
>
> After:
> (define (fib n)
> (do ((i 1 (+ 1 i))
> (a 1 (+ a b))
> (b 1 a ))
> ((>= i n ) b)))
> the fib procedure remains there in all eternity and there is nothing
> to collect. I can do (fib 10) any time I please.
> Or will there be anonymous memory places and are the
> boxes they are in such as (a,b,i,n) collectable?
As long as you don't redefine it then yes it remains there for all eternity.
But if you call it then the arguments fib and n as well as the local
(lexical in Lisp parlance) variables i , a , b will have to be allocated
somewhere. So whether they create garbage , which will need to be reclaimed
eventually , depends on the allocation strategy of the implementation. A
perfectly reasonable strategy is that the implementation gets a big chunk of
memory from the operating system and every time it needs a new object it uses
the smallest address from that space which it hasn't used yet. If the space
fills up then the implementation may ask for more memory from the operating
system or do garbage collection ; obviously , eventually it will have to do
garbage collection rather than keep asking for more and more memory. With
such an allocation scheme , every time you call fib and it returns then it
will create garbage for fib , n , etc. Now a sufficiently clever Lisp
implementation may be able to prove that none of the variables of fib can
be referenced after fib terminates and therefore allocate them on the
hardware stack as it would (likely) happen in a language like C.
en.wikipedia.org/wiki/Escape_analysis has some related content. But if it's
not that clever then every call to fib creates garbage and if that garbage
isn't cleared every now and again , it will consume eventually all available
memory.
> But what with (directly calculating the 100-th fib number)
> (do ((i 1 (+ 1 i))
> (a 1 (+ a b))
> (b 1 a ))
> ((>= i 100 ) b )
> )
> 354224848179261915075
> does that leave garbage in your run of the mill scheme?
> (Because it might not in mine.)
Same as above ; if the Lisp implementation is clever enough to see that
i , a , b cannot be accessed after the piece of code terminates then it will
allocate them in such a way as to not create garbage (like on the hardware
stack) , otherwise they will be garbage. Note also , which Paul Rubin pointed
out in a different post , that even 354224848179261915075 may create garbage
if it's so large that it won't fit in a register. Since
354224848179261915075 > 2^64 then even in a 64 bit machine it may create
garbage. Even just writing on the REPL
354224848179261915075
may create garbage.
> In the procedure fib can I optimise the fib into machine code with
> (optimise fib)
> that optimises the underlying Forth code, without getting on
> someones toes?
> Obviously that may leave some garbage that may be harder to collect.
Every garbage collection algorithm I've heard of deals with low level
pointers so turning your high level language into machine code won't make
garbage collection harder. But in any case , your concern shows again that
garbage collection is something you have to incorporate into your design from
the start , not something you add as an afterthought.
[...]
> I just read the description of Guile. That is a Scheme dialect and Scheme
> is supposed to be simple. I can't detect the simplicity in it (not
> from the info file). It kind of deters me.
> I see that guile binary is 3K, that seems okay, but it calls
> horrific c-libraries like the infamous readline, maybe even malloc.
Every Scheme intended for real work will have plenty of extensions on top of
the Scheme standard. en.wikipedia.org/wiki/Scheme_(programming_language) :
The R6RS standard has caused controversy because it is seen to
have departed from the minimalist philosophy. In August 2009, the
Scheme Steering Committee which oversees the standardization
process announced its intention to recommend splitting Scheme
into two languages: a large modern programming language for
programmers, and a subset of the large version retaining the
minimalism praised by educators and casual implementors
I don't know why you think readline is infamous but it's for providing a more
pleasant interface and not necessary. On the other hand , Guile certainly
uses the GNU multiprecision library and being able to handle arbitrarily
large integers *is* part of the core functionality. Since it uses the
Boehm-Demers-Weiser garbage collector , I'm guessing it doesn't call malloc()
(or realloc()) but the analogous functions Boehm-Demers-Weiser provides.
--
For network programming today, my first-hand choice is to use the
Boost.Asio C++ library, with nonblocking sockets and no threads.
Jorgen Grahn
Didn't see that coming. That wouldn't be my last choice; it wouldn't
even make the list of choices. I'd rather open a fruit stand.
James K. Lowden
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-09-05 12:05 +0200 |
| Message-ID | <nqjg16$3j7$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50684 |
I've cross posted to comp.lang.lisp The context is writing a minimal lisp, but with Forth instead of c as the implementation language. In article <_p9zz.1142663$OC.48142@fx39.am4>, Spiros Bousbouras <spibou@gmail.com> wrote: <SNIP> > >I don't think that garbage collection is something to be added as an >afterthought. The existence of garbage collection affects the allocation (and >possible recollection) of every object (see examples below) so it's one of >the issues you need to be thinking about from the start. It's likely more >fundamental than the syntax of the language. Having said that , it's not that >big a hurdle. I don't know why you don't like Anton Ertl's package but there >is also the Boehm-Demers-Weiser garbage collector which is used in Embeddable >Common Lisp , Guile Scheme and was used in an early implementation of Racket >Scheme. Even writing your own precise garbage collector is not terribly >difficult , see > http://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec24.htm >for a simple algorithm. > >> About garbage: Is this correct (the infamous Fibonacci series)? >> >> After: >> (define (fib n) >> (do ((i 1 (+ 1 i)) >> (a 1 (+ a b)) >> (b 1 a )) >> ((>= i n ) b))) >> the fib procedure remains there in all eternity and there is nothing >> to collect. I can do (fib 10) any time I please. >> Or will there be anonymous memory places and are the >> boxes they are in such as (a,b,i,n) collectable? > >As long as you don't redefine it then yes it remains there for all eternity. Maybe there is a confusion between dynamic allocation / knowing exactly where each piece of memory hangs out, and garbage collection. Such a fib consist (in my view) of a Forth word header of 5 CELLS which is dynamically allocated *using my Forth ALLOCATE* and pointed to by some pointer sitting in some tree or list or hash as a global heap. Then the code is high level Forth code, and again it is allocated dynamically and a pointer to it is present in the header. (High level Forth code is, of course a list of code tokens.) Contrary to malloc, my ALLOCATE knows a lot about the size etc of pieces allocated. Of course I make sure that analysing the heap is possible to find out what is no longer needed. But I call actually doing that the garbage collection. There is no doubt in my mind that I can implement a garbage collector even if it is very inefficient. What one needs is all knowledge about pointers to dynamically allocated area and into dynamically allocated area and know which is which, and a means to know the sizes. That may not be properly called an afterthought. If I wouldn't keep that information from the start, an attempt to write a Lisp would be ludricous indeed. If I want to investigate how a Forth can morph into a lisp, I can't have an external tool dictate me how to do the allocation. Using my own ALLOCATE I can change it, if I want properties specifically needed for LISP >But if you call it then the arguments fib and n as well as the local >(lexical in Lisp parlance) variables i , a , b will have to be allocated >somewhere. So whether they create garbage , which will need to be reclaimed >eventually , depends on the allocation strategy of the implementation. A >perfectly reasonable strategy is that the implementation gets a big chunk of >memory from the operating system and every time it needs a new object it uses >the smallest address from that space which it hasn't used yet. If the space >fills up then the implementation may ask for more memory from the operating >system or do garbage collection ; obviously , eventually it will have to do >garbage collection rather than keep asking for more and more memory. With >such an allocation scheme , every time you call fib and it returns then it >will create garbage for fib , n , etc. Now a sufficiently clever Lisp >implementation may be able to prove that none of the variables of fib can >be referenced after fib terminates and therefore allocate them on the >hardware stack as it would (likely) happen in a language like C. >en.wikipedia.org/wiki/Escape_analysis has some related content. But if it's >not that clever then every call to fib creates garbage and if that garbage >isn't cleared every now and again , it will consume eventually all available >memory. My Forth allocation strategy is simpler. At the start a large chunk is asked from Linux (which overcommits memory). Then my ALLOCATE gives out memory on a first free basis. Maybe I get stuck and have to do garbage collection, which amounts to calling FREE from the allocator. If the large stuck wasn't enough, that is the end. With a toy Lisp and a 16 gByte heap, I can do a lot of testing before the GC needs to kick in. > >> But what with (directly calculating the 100-th fib number) >> (do ((i 1 (+ 1 i)) >> (a 1 (+ a b)) >> (b 1 a )) >> ((>= i 100 ) b ) >> ) >> 354224848179261915075 >> does that leave garbage in your run of the mill scheme? >> (Because it might not in mine.) > >Same as above ; if the Lisp implementation is clever enough to see that >i , a , b cannot be accessed after the piece of code terminates then it will >allocate them in such a way as to not create garbage (like on the hardware >stack) , otherwise they will be garbage. Note also , which Paul Rubin pointed >out in a different post , that even 354224848179261915075 may create garbage >if it's so large that it won't fit in a register. Since >354224848179261915075 > 2^64 then even in a 64 bit machine it may create >garbage. Even just writing on the REPL > 354224848179261915075 >may create garbage. That is interesting. The Forth REPL can interpret the line .( aap) and it will print aap. The string aap is a temporary object and disappears automatically. It will not be allocated anywhere, only a string descriptor will be on the Forth stack. "aap" TYPE likewise will print aap, otoh it will allocate a string (in ciforth). Its descriptor is thrown away, so the string itself becomes garbage. Normally in Forth this garbage is collected using FORGET/MARKER a very primitive mechanism that basically only restores a previous memory situation. > >> In the procedure fib can I optimise the fib into machine code with >> (optimise fib) >> that optimises the underlying Forth code, without getting on >> someones toes? >> Obviously that may leave some garbage that may be harder to collect. > >Every garbage collection algorithm I've heard of deals with low level >pointers so turning your high level language into machine code won't make >garbage collection harder. But in any case , your concern shows again that >garbage collection is something you have to incorporate into your design from >the start , not something you add as an afterthought. > >[...] > >> I just read the description of Guile. That is a Scheme dialect and Scheme >> is supposed to be simple. I can't detect the simplicity in it (not >> from the info file). It kind of deters me. >> I see that guile binary is 3K, that seems okay, but it calls >> horrific c-libraries like the infamous readline, maybe even malloc. > >Every Scheme intended for real work will have plenty of extensions on top of >the Scheme standard. en.wikipedia.org/wiki/Scheme_(programming_language) : > > The R6RS standard has caused controversy because it is seen to > have departed from the minimalist philosophy. In August 2009, the > Scheme Steering Committee which oversees the standardization > process announced its intention to recommend splitting Scheme > into two languages: a large modern programming language for > programmers, and a subset of the large version retaining the > minimalism praised by educators and casual implementors Thank you. good to know that. I have no objection to extensions of course. My statically linked lina is 30 kbyte. If you want floating point, you have to load it from a source library, so then you've to load an assembler first from a source library. > >I don't know why you think readline is infamous but it's for providing a more >pleasant interface and not necessary. On the other hand , Guile certainly >uses the GNU multiprecision library and being able to handle arbitrarily >large integers *is* part of the core functionality. Since it uses the >Boehm-Demers-Weiser garbage collector , I'm guessing it doesn't call malloc() >(or realloc()) but the analogous functions Boehm-Demers-Weiser provides. (In the context of toy lisps that can be implemented in 1000 lines, I hate readline which is itself couple of hundred lines, is not written in lisp and is not strictly needed. I'm glad to see that it is a loadable extension to Guile.) BDW is a c-package? I'm disappointed, because people told me that Lisp can be implemented using 5 basic operations. That means something different than saying that yourforth is implemented with 38 basic words (in assembler) apparently. In analysing what is minimally needed in Forth always KEY and EMIT come up. That is realistic. If you can't tell the computer what to do, and can't see what it has done, your language is incomplete. Lispers seem to think that REPL is a tucked on part. If you would program a LISP machine like I have a Forth machine (just a tower that has Forth in the boot sector), would it then contain a couple of giant binary blobs being the GNU multiprecision lib, the compiled readline lib and maybe even a compiled BDW library written in C? Eech! > Jorgen Grahn > James K. Lowden Two names in a signature, but you're Spiros? -- 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]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-09-05 12:04 -0700 |
| Message-ID | <87zinmmams.fsf@jester.gateway.pace.com> |
| In reply to | #50693 |
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
> With a toy Lisp and a 16 gByte heap, I can do a lot of testing before
> the GC needs to kick in.
I suppose that's a reasonable way to start.
>> 354224848179261915075 may create garbage
> That is interesting. The Forth REPL can interpret the line .( aap)
> and it will print aap. The string aap is a temporary object and
> disappears automatically. It will not be allocated anywhere,
What happens if you enter the line "123" to leave the number 123 on the
stack? It goes into a stack cell (machine word) that's reclaimed
automatically when you pop the stack--that's how Forth works. But what
if the number is 354224848179261915075? It won't fit in a cell. It's a
bignum that must occupy multiple cells, so you'd use something like
ALLOCATE to get those cells, put the number in them, and leave just a
pointer on the stack. Later once the number is no longer in use, you'll
want to reclaim the memory. That's why we say entering
354224848179261915075 in a Lisp REPL might create garbage.
> Normally in Forth this garbage is collected using FORGET/MARKER
> a very primitive mechanism that basically only restores a previous
> memory situation.
Having GC frees you from having to think about stuff like that.
Edsger W. Dijkstra in his 1972 Turing Award lecture said,
"With a few very basic principles at its foundation, it [LISP] has
shown a remarkable stability. Besides that, LISP has been the
carrier for a considerable number of in a sense our most
sophisticated computer applications. LISP has jokingly been
described as “the most intelligent way to misuse a computer”. I
think that description a great compliment because it transmits the
full flavour of liberation: it has assisted a number of our most
gifted fellow humans in thinking previously impossible
thoughts."
Part of the way it did that was by handling stuff like memory management
for you behind the scenes, in a manner mostly unknown in other languages
of that era. These days, of course, everybody does it.
> BDW is a c-package? I'm disappointed, because people told me that
> Lisp can be implemented using 5 basic operations.
That's too vague to be meaningful. Lisp code is written with the
illusion of infinite memory, and the GC reclaims the actual underlying
memory behind the scenes, invisibly to the program. GC has to munge on
actual raw memory which Lisp doesn't have a way to do. BDW is one
approach to GC but there are others, all of which need machine-level
primitives. Some Lisps include memory-access primitives so the GC can
itself be written in Lisp, but that stuff has to be done very carefully
to avoid creating garbage while the GC is running. I believe that
Scheme-48 (s48.org) works that way.
> If you would program a LISP machine like I have a Forth machine (just
> a tower that has Forth in the boot sector), would it then contain a
> couple of giant binary blobs being the GNU multiprecision lib, the
> compiled readline lib and maybe even a compiled BDW library written in
> C? Eech!
BDW is a nice simple way to get GC for a small Lisp, but the higher
performance ones tend to use other methods. And of course Lisp is much
older than the GNU project. Traditionally bignums would have been
implemented in assembly language. The historical Lisp machines had
hardware-assisted GC, I believe.
There's a bare-metal Scheme for the Raspberry Pi but I don't know if
anyone actually uses it. Big Lisp systems usually run under OS's rather
than on bare metal. Although control systems have been done in Lisp,
Lisp usually hasn't been in the same niche as Forth. It's more for
computation than for control, so it usually doesn't care much about low
level hardware access.
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-09-06 11:48 +0200 |
| Message-ID | <nqm3cs$dmm$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50699 |
In article <87zinmmams.fsf@jester.gateway.pace.com>, Paul Rubin <no.email@nospam.invalid> wrote: >albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes: <SNIP> >> If you would program a LISP machine like I have a Forth machine (just >> a tower that has Forth in the boot sector), would it then contain a >> couple of giant binary blobs being the GNU multiprecision lib, the >> compiled readline lib and maybe even a compiled BDW library written in >> C? Eech! > >BDW is a nice simple way to get GC for a small Lisp, but the higher >performance ones tend to use other methods. And of course Lisp is much >older than the GNU project. Traditionally bignums would have been >implemented in assembly language. The historical Lisp machines had >hardware-assisted GC, I believe. How can a c-package that has the same API as malloc ever know what is garbage to LISP? Why would my ALLOCATE fare any less than BDW if it has access to that same information? A package with an ALLOCATE and a FREE is not a garbage collector. Garbage collecting is about knowing what can be freed. (Merging free areas into one is done automatically and incrementally in my Forth ALLOCATE. I hope not that this is called garbage collection. My Forth ALLOCATE knows the size of all allocated area's, so it is superior to malloc() in all respects except speed.) I can imagine there is a "fat" FREE to be called from lisp. It frees the area pointed to and recursively via pointers stored there all areas indirectly pointed to. I can add a fat FREE to my ALLOCATE in a heartbeat. But surely only Lisp can decide when to call it. If there are any aliasing pointers to one of those areas, it can't fatFREE it. > >There's a bare-metal Scheme for the Raspberry Pi but I don't know if >anyone actually uses it. Big Lisp systems usually run under OS's rather >than on bare metal. Although control systems have been done in Lisp, >Lisp usually hasn't been in the same niche as Forth. It's more for >computation than for control, so it usually doesn't care much about low >level hardware access. > 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]
| From | Spiros Bousbouras <spibou@gmail.com> |
|---|---|
| Date | 2016-09-06 15:32 +0000 |
| Message-ID | <jkBzz.1477$xE.246@fx35.am4> |
| In reply to | #50703 |
On Tue, 6 Sep 2016 11:48:12 +0200 (CEST)
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) wrote:
> In article <87zinmmams.fsf@jester.gateway.pace.com>,
> Paul Rubin <no.email@nospam.invalid> wrote:
> >
> >BDW is a nice simple way to get GC for a small Lisp, but the higher
> >performance ones tend to use other methods. And of course Lisp is much
> >older than the GNU project. Traditionally bignums would have been
> >implemented in assembly language. The historical Lisp machines had
> >hardware-assisted GC, I believe.
>
> How can a c-package that has the same API as malloc ever know what
> is garbage to LISP? Why would my ALLOCATE fare any less than BDW
> if it has access to that same information?
The basic idea is as follows : the application which uses BDW
(Boehm-Demers-Weiser) always uses the replacements for malloc() and realloc()
BDW provides to allocate memory. So the BDW library internally knows all the
ranges of addresses which the application has allocated. When BDW needs to do
garbage collection then it scans all the "data" of the application meaning ,
heap , hardware stack and processor registers. Every time it finds something
which could be interpreted as a pointer to a section of allocated memory then
it marks that section as in use. Then it scans each such section for pointers
and continues recursively in the same fashion until it has traversed the whole
references graph. After it has done so , each allocated memory section which
has not being marked during the traversal as in being in use , can be freed.
For more details I will refer you to the following :
http://www.iecc.com/gclist/GC-algorithms.html#Conservative%20collection
Conservative collection
Conservative garbage collection makes use of the observation
that if you are not relocating (copying) objects, then you
need not be quite so certain about exactly what is a pointer.
It suffices to scan the root set (and objects) for any
pointer-like bit patterns, and treat those pointer-like bit
patterns as actual pointers while marking. The result is that
the "true" reachable objects are all found, along with a few
others. This works surprisingly well in practice (if a few
additional tricks are added) and often permits the use of
garbage collection with oblivious source code and compilers.
Conservative collection is very important because it permits
the use of garbage collection with programs that were not
written with garbage collection in mind. That is, it simpifies
the use of garbage collection with existing (non-garbage-collected)
libraries of code.
or
http://hboehm.info/gc/gcdescr.html
Conservative GC Algorithmic Overview
This is a description of the algorithms and data structures used in
our conservative garbage collector.
Note that the techniques work for any application whatsoever not just a Lisp
compiler.
> A package with an ALLOCATE and a FREE is not a garbage collector.
> Garbage collecting is about knowing what can be freed.
> (Merging free areas into one is done automatically and incrementally
> in my Forth ALLOCATE. I hope not that this is called garbage collection.
> My Forth ALLOCATE knows the size of all allocated area's, so it is
> superior to malloc() in all respects except speed.)
As I said in a previous post , the malloc() library also knows internally the
size of all allocated areas otherwise it wouldn't work. The advantage you have
if you have control of both the memory allocation "infrastructure" (which would
be your own Forth in this case) as well as the application (which would be the
Lisp compiler you want to write) is that the application can appropriately mark
all objects which are pointers so that you can have *precise* garbage
collection as opposed to conservative garbage collection ; in the latter , the
algorithm I describe above can mistake as pointers objects which the
application uses as integers simply because accidentally they have a value
which corresponds to one of the allocated memory areas. So the application is
not going to use such an object as a reference to other objects but the garbage
collector doesn't know this so it has to assume the worst (i.e. be
conservative) and treat it as a pointer.
Here's an example of how such marking might work : say you have an architecture
where all objects have to be aligned at even memory addresses. This means that
every bit pattern which corresponds to a pointer will have the 0-th bit be
zero. So a garbage collected programming language may use the 0-th bit as a tag
bit to indicate integers and make this always 1. So for example , if it wants
to store the integer 4 it will not store bit pattern 100 (or appropriate width)
but 1001. This of course means that in order to add 2 integers you cannot just
use the assembly instruction but you have to shift both of them 1 position
right , then add them as normal , then shift the result 1 position left and
finally make the 0-th bit 1 again to tag the result as an integer. Similarly
for other mathematical operations. This is comparatively slow (plus you
sacrifice one value bit as a tag) but in the grand scheme of things , which
includes efficient and precise garbage collection , it's worth it. If I
remember correctly , the OCaml implementation does something like this. But the
main point is that for such a scheme to work , there has to be cooperation
between the garbage collector and the application which runs on top of it.
> I can imagine there is a "fat" FREE to be called from lisp.
> It frees the area pointed to and recursively via pointers stored
> there all areas indirectly pointed to. I can add a fat FREE to
> my ALLOCATE in a heartbeat. But surely only Lisp can decide
> when to call it. If there are any aliasing pointers to one
> of those areas, it can't fatFREE it.
Actually the garbage collector tends to decide when to do garbage collection as
opposed to say requesting more memory from the operating system. Having said
that , if the programming language has a command to do garbage collection then
it's a plus. If for an example an application knows it's going to be idle for a
while , then it may as well ask for a garbage collection to happen.
--
It is better that some innocent men remain in jail than that the
integrity of the English judicial system be impugned.
https://en.wikipedia.org/wiki/Lord_Denning
[toc] | [prev] | [next] | [standalone]
| From | albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2016-09-06 21:27 +0200 |
| Message-ID | <nqn5a6$hds$1@cherry.spenarnc.xs4all.nl> |
| In reply to | #50708 |
In article <jkBzz.1477$xE.246@fx35.am4>,
Spiros Bousbouras <spibou@gmail.com> wrote:
>On Tue, 6 Sep 2016 11:48:12 +0200 (CEST)
>albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) wrote:
>> In article <87zinmmams.fsf@jester.gateway.pace.com>,
>> Paul Rubin <no.email@nospam.invalid> wrote:
>> >
>> >BDW is a nice simple way to get GC for a small Lisp, but the higher
>> >performance ones tend to use other methods. And of course Lisp is much
>> >older than the GNU project. Traditionally bignums would have been
>> >implemented in assembly language. The historical Lisp machines had
>> >hardware-assisted GC, I believe.
>>
>> How can a c-package that has the same API as malloc ever know what
>> is garbage to LISP? Why would my ALLOCATE fare any less than BDW
>> if it has access to that same information?
>
>The basic idea is as follows : the application which uses BDW
>(Boehm-Demers-Weiser) always uses the replacements for malloc() and realloc()
>BDW provides to allocate memory. So the BDW library internally knows all the
>ranges of addresses which the application has allocated. When BDW needs to do
>garbage collection then it scans all the "data" of the application meaning ,
>heap , hardware stack and processor registers. Every time it finds something
>which could be interpreted as a pointer to a section of allocated memory then
>it marks that section as in use. Then it scans each such section for pointers
>and continues recursively in the same fashion until it has traversed the whole
>references graph. After it has done so , each allocated memory section which
>has not being marked during the traversal as in being in use , can be freed.
>For more details I will refer you to the following :
>
> http://www.iecc.com/gclist/GC-algorithms.html#Conservative%20collection
>
> Conservative collection
>
> Conservative garbage collection makes use of the observation
> that if you are not relocating (copying) objects, then you
> need not be quite so certain about exactly what is a pointer.
> It suffices to scan the root set (and objects) for any
> pointer-like bit patterns, and treat those pointer-like bit
> patterns as actual pointers while marking. The result is that
> the "true" reachable objects are all found, along with a few
> others. This works surprisingly well in practice (if a few
> additional tricks are added) and often permits the use of
> garbage collection with oblivious source code and compilers.
>
> Conservative collection is very important because it permits
> the use of garbage collection with programs that were not
> written with garbage collection in mind. That is, it simpifies
> the use of garbage collection with existing (non-garbage-collected)
> libraries of code.
>
>or
>
> http://hboehm.info/gc/gcdescr.html
> Conservative GC Algorithmic Overview
> This is a description of the algorithms and data structures used in
> our conservative garbage collector.
>
>Note that the techniques work for any application whatsoever not just a Lisp
>compiler.
That is a whole of a lot better than the wikipedia entry. I feel like pasting
that whole text into wikipedia.
The crucial points are
the whole memory in use by the application is considered as potential pointers
conservative: garbage may not be freed, but if it is freed it is
certainly garbage
Neither of these points came through from wikipedia.
What about pointers in the middle of an area?
Do they prevent the area from being freed?
<SNIP>
Thanks for the helpful information.
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]
Page 1 of 5 [1] 2 3 4 5 Next page →
Back to top | Article view | comp.lang.forth
csiph-web