Dec 092017
 
Some list handling words for FPC forth.
File FLISP.ZIP from The Programmer’s Corner in
Category Forth Source Code
Some list handling words for FPC forth.
File Name File Size Zip Size Zip Type
FLISP.SEQ 27963 8504 deflated
FLISP.TXT 14254 4873 deflated
HEAP.TXT 4823 2082 deflated
LHEAP.SEQ 16092 5898 deflated

Download File FLISP.ZIP Here

Contents of the FLISP.TXT file


FLISP.txt
Handling Linear Lists in a Single Far Segment

David Sharp
607 W. 184th St., Apt 1WF
N.Y.C., NY 10033
212-568-9519

some acknowledgements:
Tom Zimmer's F-PC
Martin Tracy's "A Forth Lisp" in DR. DOBBS TOOLBOOK of FORTH II, Chpt 28
Forth source screens which, though incomplete in some respects,
were easy to adapt. The main functions in this file are modelled after,
or are identical to, or fill in gaps between those in Tracy's
article.
Dick Pountain's OBJECT ORIENTED FORTH, Chpt 3
An excellent tutorial reference on forth data structures. A number
of the words he defines are adapted here. And chapter 4 of Pountain's
book were a model for Kenneth O'Heskin's Heap.seq
Kenneth O'Heskin's HEAP.SEQ 11/06/89
Used here without shame and slight modification. I renamed NIL
to ZERO, fixed a bug in GET.HANDLE, and commented out some stuff.
Because of the little bug fix I am including the entire file in
this package. Heap.seq itself could be used as a model for far
list handling.
Also: 12/21/91 changed heap from being allocated
via dos (alloc) to using POINTER
-----------------------------------------------------------------------
This file is a small rudimentary LISP-like list processing package which is
meant to enable you to run lisp functions on lists which are outside of the
normal Forth code segment. I am developing it as a "logical" verneer for
an interactive interface to lists of data structures as sort of an
"accessory". My main concern as far as memory usage goes is for the
lisp-y interpreter to not use much of the code segment. The flisp.seq together
with Kenneth O'Heskin's Heap.seq use a total of about 1K of CS and about 5K
of dictionary. Basically, the immediate objective of the defined words is as
a basis on which to build other lisp functions. In researching LISP, I have
heard that there are really only 5 basic functions (the "primitives") you
need to get the rest: CAR, CDR, CONS, EQ, and ATOMP. I did find that once
these basic functions were defined an infinite number of possibilities for
playing with this stuff become apparent. I have started working my way
through The Little Lisper (Daniel P. Friedman and Matthias Felleisen) and am
starting to believe that all of their examples can be implemented
(Forth-style syntax) with the words included in Flisp.seq. One limitation
I have found is the number of levels of recursion available. I don't know
what the limit actually is and haven't gotten around to changing it. Which
reminds me, these routines rarely check to see if what you are asking them
to do is proper. But if you didn't get some kind of thrill out seeing all
your drive lights on simultaneously while your screen flashes on and off
you probably wouldn't be programming in Forth, would you?


The main idea:
A list consists of a number of cells each of which contains two pieces of
information: 1) the cell's value and 2) where to find the next cell in the
list. The easiest way to do this in a single segment is to simply have
the first 2 bytes point to the next link and the second two bytes hold the
cell's value. FIG B2 below is meant to show how these cells can be all over
the place in memory. We can refer to a link by referring to the address
of its first cell. Any cell is the first cell of a list which can be
traversed by going cell to cell following the addresses stored in the first
slot of the cell you are currently in. The address stored there is called,
in lisp, the CDR of the list, or the REST of the list. The value of the cell
is the list's CAR or FIRST element. This value can refer to nearly any sort
of object, including other lists. In traversing a list, you know when you've
reached the end when you reach a cell whose CDR is NIL. NIL, in this
implementation, is set to the offset of the last cell in the "list space"
(the section of HPSEG alloted to lists) so that no other cell or atom can
coincidentally have NIL for its address. A cell whose CAR slot contains NIL
would be a list whose first element is the empty list.

single cell or list address ( called "list" in the stack diagrams)


points to next value of cell.
link in list a pointer to an FIG A.
atom or "sub-list"
CDR CAR

2 bytes 2 bytes

When the file is loaded, the "list-space" is initialized as a single list
called FREE-LINKS. When a new cell is needed in constructing a list, the
first cell in free-links is removed from free-links and used. When we are
through with a cell, it can be returned to free-links by FREE-A-CELL. In
FIG B, the free-links list is shown linked by o's










Memory structure for an example list:

(BANJO BOY 3521 (BOY WONDER ) SINGS )

You could name this list BANJO-BOY by storing the address of its first cell,
say L1 (i.e., its offset into HPSEG ), in a variable or value ( or whatever )
named BANJO-BOY.
e.g.
newlist BANJO-BOY
L1 banjo-boy !

CODE SEGMENT ---------------------------------------------------- FIG B1
BANJO-BOY
pfa
L1 points to the first cell of the list

FREE-LINKS
pfa
FL1


END OF CS--------------------------------------------------------------
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
BEGINNING OF HEAP SEGMENT (HPSEG)------------------------------------
[email protected]-- FIG B2

"dot-pair"
cell's value can DL
L4be a list BANJO-BOY AH5 AH6
L5 L6 first cell
L1L1+2 L3
last cell L2 AH1 L4 L8
L5
NIL AH3 "BANJO" 3521

"SINGS" FL2
L2 o FL3 0
L3 AH2 o
L7 o o
NIL AH4 "BOY" o o
o o
"WONDER" o o o o o o
o literal o
L6 o L8numbers o
L7 AH2 o 0 3521 have o
o cdr=0 o
"BOY" o o
o FL1o
o o o o o o o o o o FL3 FL2 0
FL4o FL4 0
FL5 0 "free-links"
o
o FL5 FL6
o o o o FL6 0 o NIL 0
NIL
end of free-links NIL NIL
---------------- END OF LINKS -----------------------------------
-------------------------------ATOM$------------------------------
FIG B3
ATOM$10700B A N J O -1 1 ATOM$20500B O Y 0-1
^^
0 1 (the 2 bytes at the end of each atom$
are "property" bytes)

ATOM$30700S I N G S -1 0 ATOM$40800W O N D E R -1 2

| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | |
| | | | | | | | | handles to atomic strings|
| | | | handles grow|AH4AH3AH2AH1links
| | | | down from endatom$4atom$3atom$2atom$1 L?

(ptr to
END OF HEAP SEGMENT-------------------------------------------------- 1st link
cell)


You could construct such a list with the line:

quote-list ( BANJO BOY 3521 (BOY WONDER ) SINGS ) set-to banjo-boy
or the equivalent
'( BANJO BOY 3521 (BOY WONDER ) SINGS ) set-to banjo-boy

It is necessary to have a space before any right (closing) parentheses.
'( is a forth word and so needs a space following it.
SET-TO creates a "list-value" and gives it the value of the just quoted list.
This list can be displayed with the line:
banjo-boy type-list

You could give a list a name simply by storing the list value (its address
in HPSEG ) into a variable without using SET-TO or NEWLIST, but using
that name to call up the list after a garbage-run (CLEAN-UP) will probably
crash you.

CLEAN-UP does a simple-minded and slow garbage-collection.
Each time we name an object with SET-TO or NEWLIST*, the name's pfa is
added to the list NAMED. Now we can go through all the lists and
atoms and "mark" all those used in "named" lists. What BANJO BOY _MARK
would actually do is send the value of BANJO-BOY and all its constituent
expressions to a pile in MARKSEG, which SWEEP-LINKS and SWEEP-ATOM$ look
through to see if a particular expression should be kept. This scheme
has its contradictory aspects, like, if garbage collection is supposed to
help use memory more efficiently, should we be growing a list of named
objects in our memory area? CLEAN-UP is "manual" in that it is up to you
to decide when it should be invoked. It takes several seconds for 10K of list
space, partly because in my naive approach the free-links list is saved too.


Some examples:

Input Screen Display Forth stack
============================================================================
quote house (atom$1)
dup -type house (atom$1)
nil cons (list1)
dup -type ( house ) (list1)
quote the (list1 atom$2)
swap cons dup -type ( the house ) (list2)
dup car -type the (list2)
quote in swap cons (list3)
quote ( fireworks ) (list3 list4)
cons set-to BANG (---)
bang -type ( ( fireworks ) in the house ) (---)
bang car explode dup -type ( f i r e w o r k s ) (list5)
reverse implode dup -type ( skrowerif ) (list6)
quote ( skowerif ) (list6 list7)
2dup eq . 0 (list6 list7)
list-equal . -1 (---)
quote 5 quote 6 (l#1 l#2)
plus -type #11 (---)
quote ( '5 6 ) (list8)
-type ( 5 #6 ) (---)
quote (killer) (list9)

clean-up **********Time*************************

bang -type ( ( fireworks ) in the house ) (list9)
-type ^K L k --- scrolling junk (---)

============================================================================

Offhand Suggested Improvements:
(things I wish somebody would do)

Write some interesting lisp-type functions (and send them to me!). Get a
book on lisp and try duplicating what you find there.
Objectify the heap structure, lists, atoms, etc. That is, create more abstract
data types ala Object Oriented Forth, Chpt 2.
Apply the lisp functions to lists of MIDI event arrays for algorthmic
composition.
A more efficient way to mark expressions for garbage collection. Some way
to "physically" alter an expression where it is. (add an extra
"mark byte" to each expression?)



I am very interested in your application, questions, comments, suggestions,
improvements, additions, thoughts and criticism of this.
Write, call, or e-mail (D.SHARP3 on GEnie).



 December 9, 2017  Add comments

Leave a Reply