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

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

Bug in beginner's linked-list code

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

Contents

  Bug in beginner's linked-list code laheadle@gmail.com - 2013-01-31 08:52 -0800
    Re: Bug in beginner's linked-list code mhx@iae.nl (Marcel Hendrix) - 2013-01-31 20:47 +0200
      Re: Bug in beginner's linked-list code laheadle@gmail.com - 2013-02-01 07:57 -0800
        Re: Bug in beginner's linked-list code "Elizabeth D. Rather" <erather@forth.com> - 2013-02-01 09:21 -1000
          Re: Bug in beginner's linked-list code Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-02-04 17:04 -0800
            Re: Bug in beginner's linked-list code november.nihal@gmail.com - 2013-02-05 16:15 -0800

#19317 — Bug in beginner's linked-list code

I am building a simple linked-list structure using FreeForth, but my code has a bug. 

When I create a node, then attempt to create another node and insert the second node after the first node, I get a segmentation fault. Can anyone help?
  
Here is the code that crashes:
4 newNode 5 insertAfter ;

Thanks,
Lyn Headley

\ \\ linked list of integers

\ 2 fields: val, next@ 
: fieldsize 4 ;
: numfields 2 ;

: nodesize fieldsize numfields * ;

\ @ -- n
: nodeVal 
 @
;

\ @ -- @
: nextNode
 fieldsize + @
;

\ @next @node --
: nextNodeSet
 fieldsize + !
;

\ val -- @
: newNode 
  nodesize malloc dup>r
  ! \ set node value
  0 r nextNodeSet \ initially null
  r> \ return addr
;

( start@ val -- )
: insertAfter
 newNode swap \ newNode@ start@ 
 dup nextNode \ -- newNode@ start@ cnext@
 0- 0= IF \ last one
  drop
  nextNodeSet
 ELSE
  >r over >r \ -- newNode@ start@ |  == cnext@ newNode@ 
  nextNodeSet
  r> r> swap nextNodeSet
 THEN
;

[toc] | [next] | [standalone]

#19327

laheadle@gmail.com writes Re: Bug in beginner's linked-list code

> I am building a simple linked-list structure using FreeForth, 
> but my code has a bug. 

> When I create a node, then attempt to create another node and 
> insert the second node after the first node, I get a segmentation 
> fault. Can anyone help?
  
> Here is the code that crashes:
> 4 newNode 5 insertAfter ;

You didn't type the ";" I hope?

> ( start@ val -- )
> : insertAfter
> newNode swap \ newNode@ start@ 
>  dup nextNode \ -- newNode@ start@ cnext@
>  0- 0= IF \ last one
>   drop
[..]
> ;

Try DUP instead of 0- .

Several pieces seem to be missing from your algorithm.

-marcel

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

#19352

> 
> You didn't type the ";" I hope?
> 

Yes I did. FreeForth seems to require it. To quote ff.asm:

;;; However, users of usual Forth systems may be surprised by the unusual need
;;; to close a FreeForth adef with a ";" (after trying "1 2 + ." and not seeing
;;; the expected "3" answer, some have thought FreeForth isn't worth another
;;; try). However, as sson as they understand, "1 2 + . ;" indeed displays "3",
;;; and they can even try adefs with control structures (that can't be inter-
;;; preted by usual Forth systems) such as "4 TIMES r . REPEAT ;" which simply
;;; displays "3 2 1 0".


> 
> >  dup nextNode \ -- newNode@ start@ cnext@
> 
> >  0- 0= IF \ last one
> 
> 
> Try DUP instead of 0- .
> 
> 

I believe this is another FreeForth-specific aspect. FreeForth comparisons don't consume stack (they set x86 register values).

EG:

 0; 6 0- 0= IF 4 ELSE 5 THEN ;
 2; . . ;
5 6  0;

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

#19357

On 2/1/13 5:57 AM, laheadle@gmail.com wrote:
>>
>> You didn't type the ";" I hope?
>>
>
> Yes I did. FreeForth seems to require it. To quote ff.asm:
>
> ;;; However, users of usual Forth systems may be surprised by the unusual need
> ;;; to close a FreeForth adef with a ";" (after trying "1 2 + ." and not seeing
> ;;; the expected "3" answer, some have thought FreeForth isn't worth another
> ;;; try). However, as sson as they understand, "1 2 + . ;" indeed displays "3",
> ;;; and they can even try adefs with control structures (that can't be inter-
> ;;; preted by usual Forth systems) such as "4 TIMES r . REPEAT ;" which simply
> ;;; displays "3 2 1 0".
>
>
>>
>>>   dup nextNode \ -- newNode@ start@ cnext@
>>
>>>   0- 0= IF \ last one
>>
>>
>> Try DUP instead of 0- .
>>
>>
>
> I believe this is another FreeForth-specific aspect. FreeForth comparisons don't consume stack (they set x86 register values).
>
> EG:
>
>   0; 6 0- 0= IF 4 ELSE 5 THEN ;
>   2; . . ;
> 5 6  0;
>

I don't know anything about FreeForth, but as a newbie I think you'd do 
better with a more mainstream Forth, which would have better support and 
be covered by the standard books. Also, we'll be able to give you more 
useful advice here.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

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

#19437

On Feb 1, 12:21 pm, "Elizabeth D. Rather" <erat...@forth.com> wrote:
> I don't know anything about FreeForth, but as a newbie I think you'd do
> better with a more mainstream Forth, which would have better support and
> be covered by the standard books. Also, we'll be able to give you more
> useful advice here.

Which "standard books" provide code for linked lists? I've read
everything from Forth Inc., and I've never seen an implementation of a
linked list. I've never seen an implementation of structs in any Forth
Inc. book either, which is a necessary prerequisite for implementing
linked lists or any other data structure.

My novice package has a linked-list implementation (see LIST.4TH):
http://www.forth.org/novice.html

I think that it is a big mistake for novices to spend time
implementing low-level code, such as linked lists. Novices should
write application programs. This is a lot more fun, and when they
finish they have a program that does something useful, that they can
be proud of. Implementing basic data structures such as linked lists,
arrays, etc., is boring --- and when they finish, they still can't
claim to have ever written a program in Forth, so they are really not
Forth programmers yet. The only way to become a Forth programmer is to
write programs in Forth --- dinking around with linked lists or
whatever, isn't helping at all.

If people implement linked lists when they still don't know Forth very
well, their implementation is going to be badly written. The problem
with this, is that they will then write programs that use those badly-
written linked lists, and the programs will hence be badly written too
--- like building a house on sand. If novices write programs that use
a well-written linked-list implementation, then they will have a solid
foundation --- this doesn't guarantee that their programs will be well-
written, but it at least makes it possible for their programs to be
well-written.

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

#19491

This is not in freeforth, but hopefully you will be able to adapt. 

\ -------------------------------------------
\ linked list
\

: newNode ( val -- a ) 
	here >r
	  , \ value
	0 , \ pointer to next
	r> ;

: nodeVal     ( a -- v  ) @ ;
: nodeNext    ( a -- nn ) cell+ @ ;
: nodeNextSet ( nn a -- ) cell+ ! ;

: addNode ( nn l -- l' )
	dup @ 0= if \ empty list
		!
	else \ non empty list
		2dup @ swap nodeNextSet
		!
	then
	;

: nodeFindLast ( a -- a' ) \ precond: a non zero
	begin dup nodeNext dup while nip repeat drop ;

: addAfterNode ( nn l -- l' )
	dup @ 0= if \ empty list
		!
	else \ non empty list
		@ nodeFindLast nodeNextSet
	then
	;

: showlist ( a -- )
	@ dup 0= if \ empty list
		drop
		." {}"
	else \ non empty list
		." { "
		begin dup nodeVal . nodeNext dup 0= until drop
		." }"
	then
	;

\ -------------------------------------------

variable a \ the example list

cls
.( Linked list example ) cr cr

.( Add to front of list ) cr
0 a ! \ empty list
a showlist cr

: test1 ( -- ) 10 0 do
		100 random 1+ newnode \ some random value 0..99
		a addNode \ add it to the list
		a showlist cr \ lets see the list
	loop ; test1

cr .( Add end of list ) cr
0 a ! \ empty list
a showlist cr

: test2 ( -- ) 10 0 do
		100 random 1+ newnode
		a addAfterNode
		a showlist cr
	loop ; test2

.( The end. ) cr cr

\ -------------------------------------------

[toc] | [prev] | [standalone]

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

csiph-web