Scheme - 'globally' defined lists...very basic question

Author

'globally' defined lists...very basic question

falcon

2005-12-02, 9:24 pm

This question seems so basic that I hesitated posting it for a w

.
Unfortunately, I can't figure out how to define a 'global' list!

I would like to have a list which gets data appended to it, and
extracted from it by various procedures. Simple as that. I thought
something like this might work:

(define myspecificdata '()) ;; empty list

(define (insert-data data) (cons data myspecificdata )) ;;this
procedure is supposed to know where to insert this data
(define (sum-data) (accumulate + 0 myspecificdata) ;;this procedure is
supposed to know which list I'd like to sum up
etc., etc.

This obviously doesn't work. the myspecificdata variable obviously
doesn't point to my list as a whole but the empty list, which becomes
part of my new consed list rather than pointing to it.

So how can I have an accessable list? I realize my Java trained brain
probably can't see something obvious. Is what I'm trying to do
non-functional (repeated operations on this list may produce different
results)...do I need to use set! or something similar???

(btw: the motivation behind it is something like a database, i'd like
the list to be a 'table' and I'd like to put information in it,
retrieve it, manipulate it, etc.)

Thanks.

Jussi Piitulainen

2005-12-02, 9:24 pm

falcon writes:

> non-functional (repeated operations on this list may produce
> different results)...do I need to use set! or something similar???

Yes.

(define *data* '())

(define (add-datum! datum)
(set! *data* (cons datum *data*)))

The stars are a convention to mark variables that vary, just like the
bang in procedure names and syntactic keywords.

falcon

2005-12-02, 9:24 pm

I'll try that, thanks. I tried doing something similar:

(define mylist '())
(define (insert data) (define mylist (cons data mylist))

That didn't work, I needed to use set! :)

Bruce Lewis

2005-12-02, 9:24 pm

"falcon" <shahbazc@gmail.com> writes:

> This question seems so basic that I hesitated posting it for a w

.
> Unfortunately, I can't figure out how to define a 'global' list!
>
> I would like to have a list which gets data appended to it, and
> extracted from it by various procedures. Simple as that. I thought
> something like this might work:
>
> (define myspecificdata '()) ;; empty list
>
> (define (insert-data data) (cons data myspecificdata )) ;;this
> procedure is supposed to know where to insert this data

The expression (cons data myspecificdata) returns the list you want.
Are you sure you want to mutate myspecificdata? Mutation makes it
harder to figure out how a program works, in that an object used in one
place might be changed in another with unexpected results.

If you really want to do mutation, the simplest is
(define (insert-data! data)
(set! myspecificdata (cons data myspecificdata)))

That constructs a list with data prepended to myspecificdata, and points
the variable myspecificdata at the new list.

With this kind of mutation, other variables that point to the value of
myspecificdata will continue to point to the old value. If you want to
really confuse things and have them point at a new list, there's this
technique:

(define (push! data)
(set-cdr! myspecificdata (cons (car myspecificdata)
(cdr myspecificdata)))
(set-car! myspecificdata data))

> So how can I have an accessable list? I realize my Java trained brain
> probably can't see something obvious. Is what I'm trying to do
> non-functional (repeated operations on this list may produce different
> results)...do I need to use set! or something similar???

What you're trying to do is non-functional. You might want to pick a
book (HTDP?) and run through the examples. You can certainly do
non-functional programming in Scheme using set!, etc. But you'll be
missing out on some important learning if you do.

Ulrich Hobelmann

2005-12-02, 9:24 pm

falcon wrote:
> I'll try that, thanks. I tried doing something similar:
>
> (define mylist '())
> (define (insert data) (define mylist (cons data mylist))
>
> That didn't work, I needed to use set! :)

That's because DEFINE only creates a new binding for the name MYLIST,
but in this case inside the INSERT function, so it won't be any more
visible after the function returns.

set! OTOH modifies the current binding (which in your case is the global
variable, but it could be shadowed by a local one).

--
The road to hell is paved with good intentions.

Jussi Piitulainen

2005-12-02, 9:24 pm

falcon writes:

> I'll try that, thanks. I tried doing something similar:
>
> (define mylist '())
> (define (insert data) (define mylist (cons data mylist))
>
> That didn't work, I needed to use set! :)

Yes. A local variable that is distinct from the global, an empty body,
and an attempt to bind a variable to the value of an expression where
it needs to be bound already. Won't work.

When your data structures get more complex, you may want to replace
the set! with procedures like set-car! and set-cdr!, but keep it
simple while you can.

falcon

2005-12-02, 9:24 pm

This doesn't seem to work if I define my add-datum! function to be
generic enough to work with any list (think of the ability to insert
into a number of different tables rather than just one). The following
is my code...as far as I can tell, a more generic add-datum!/insert! is
the only real difference (does this have to do with lazy vs. eager
evaluation?...applicative/normal, don't know for sure what its called):

(define *system-tables* '())
(define *system-table-columns* '())

(define (create-table table-name table-columns)
(insert! table-name *system-tables*)
(map (lambda (x) (insert! x *system-table-columns*)) table-columns)
)

(define (insert! data table) (set! table (cons data table)))

(insert! "hello world" *system-tables*) ;;just a test of the insert!
function

(display "system-tables\n")
*system-tables*
(display "system-table-columns\n")
*system-table-columns*

-------result -------------
Welcome to DrScheme, version 299.400p1.
Language: Standard (R5RS).
system-tables
()
system-table-columns
()

falcon

2005-12-02, 9:24 pm

I recently received HTDP and SICP, I have EOPL and I worked through the
first few chapters of The Little Schemer. I have The Seasoned Schemer
and The Reasoned Schemer at home, waiting to be opened. I am also
watched 5 or 6 lectures of SICP video and a Scheme course available on
the web at Berkeley.

Instead of flipping through a few pages of each book, I really should
just go through one book completely....no matter how boring :) In any
case, I've decided to drown my self in Scheme for a while, until it
(slowly) starts to soak in :)

Gary Baumgartner

2005-12-02, 9:24 pm

In article <1133381372.239786.159080@g43g2000cwa.googlegroups.com>,
falcon <shahbazc@gmail.com> wrote:
>This doesn't seem to work if I define my add-datum! function to be
>generic enough to work with any list (think of the ability to insert
>into a number of different tables rather than just one). The following
>is my code...as far as I can tell, a more generic add-datum!/insert! is
>the only real difference (does this have to do with lazy vs. eager
>evaluation?...applicative/normal, don't know for sure what its called):
>
>(define *system-tables* '())
>(define *system-table-columns* '())
>
>(define (create-table table-name table-columns)
> (insert! table-name *system-tables*)
> (map (lambda (x) (insert! x *system-table-columns*)) table-columns)
> )
>
>(define (insert! data table) (set! table (cons data table)))
>
>
>(insert! "hello world" *system-tables*) ;;just a test of the insert!
>function

The issue is pass-by-value.

When you called

(insert! "hello world" *system-tables*)

it's as if you called

(insert! "hello world" '()) ; () is the value of *system-tables*

and inside insert!, the table parameter is a local variable which gets
updated by set! and then forgotten.

Gary Baumgartner

>
>(display "system-tables\n")
>*system-tables*
>(display "system-table-columns\n")
>*system-table-columns*
>
>-------result -------------
>Welcome to DrScheme, version 299.400p1.
>Language: Standard (R5RS).
>system-tables
>()
>system-table-columns
>()
>

falcon

2005-12-02, 9:24 pm

So how can I get insert! to understand that I don't want the value
passed? I tried several variations of 'delay' but it didn't work. Do
I have to use macros?
[color=darkred]

Ulrich Hobelmann

2005-12-02, 9:24 pm

falcon wrote:
> So how can I get insert! to understand that I don't want the value
> passed? I tried several variations of 'delay' but it didn't work. Do
> I have to use macros?

You don't want what value passed?

insert!, as Gary defined it, just modifies the table, like a typical
function in C or Java would.

--
The road to hell is paved with good intentions.

Anton van Straaten

2005-12-02, 9:24 pm

falcon wrote:
> So how can I get insert! to understand that I don't want the value
> passed? I tried several variations of 'delay' but it didn't work. Do
> I have to use macros?

Here's some homework reading:
http://mitpress.mit.edu/sicp/full-t...ook/node60.html

But really, what you're dealing with isn't really any different than
Java, which you mentioned being familiar with. Looking at equivalent
code in Java might help.

First, here's the relevant Scheme which you provided:

(define *system-tables* '())
(define (insert! data table) (set! table (cons data table)))
(insert! "hello world" *system-tables*)

Here's some equivalent Java, assuming you have a Pair class which
corresponds to a Scheme pair:

class Foo {
static Pair system_tables = null;

static void insert(Object data, Pair table) {
table = new Pair(data, table);
}

public static void main(String args[]) {
Foo.insert("hello world", system_tables);
System.out.println(system_tables);
}
}

What will that do? In particular, what effect does the assignment to
'table' in the 'insert' method have? Note that the semantics of that
assignment are basically identical to that of SET! in Scheme.

How, in Java, would you make this do what you want?

Actually, a typical answer for Java might not end up being completely
appropriate in Scheme, but thinking about it should give you a better
feel for the issues, based on what you already know.

Anton

falcon

2005-12-02, 9:24 pm

Anton,
I actually started re-reading chapter 3 from SICP last night. I think
that solves my problem. I'll post a solution when I get a chance.
Thanks.

Gary Baumgartner

2005-12-02, 9:24 pm

In article <1133399623.849590.148460@g49g2000cwa.googlegroups.com>,
falcon <shahbazc@gmail.com> wrote:
>So how can I get insert! to understand that I don't want the value
>passed? I tried several variations of 'delay' but it didn't work. Do
>I have to use macros?

I can think of four general approaches to updating your variable.

1. Pass the value to a procedure, have the procedure return a new value,
update the variable where you called the procedure.

2. Pass a modifiable value to a procedure, have the procedure modify
the value.

3. `Capture' the variable, pass it to a procedure, have the procedure
manipulate the variable.

4. `Inline' the procedure body in the caller's environment, via a macro.

Let's see each of these.

1. I think you were specifically asking how to avoid this, since you
originally asked about "global" variables. But let's look at it
as a point of comparison.

(define (insert data table) (cons data table))

(define *table* '())
(set! *table* (insert "hello world" *table*))

A macro can be made to capture the idea of applying a procedure to the
value of a variable and updating the variable.

(define-syntax set!!
(syntax-rules ()
((set!! procedure variable arguments ...)
(set! variable (procedure variable arguments ...)))))

Then if we had defined insert with the table argument first:

(define (insert table data) (cons data table))

(set!! insert *table* "hello world")

This is a generalization of Java's assignment operators (e.g. +=).

(define x 2)
(set!! + x 5)

2. We can't start with (), because it's not mutable (it's like null in Java).
Other than that, Bruce Lewis demonstrated the approach.

(define (insert! data table)
; Standard linked-list manipulation
; car and cdr are like getData() and getLink()
; set-car! and set-cdr! are like setData(Object) and setLink(Node)
; cons is like new Node(data, next)
(set-cdr! table (cons (car table) (cdr table)))
(set-car! table data))

(define *table* (cons "hello world" '()))
(insert! "goodbye world" *table*)

3. You were getting close to this with "delay". Let's make a procedure
that sets the variable depending on whether it is given an argument.
This procedure is complicated to first make, but then can be passed
to various procedures.

(define (insert! data table-variable-manipulator)
(table-variable-manipulator
(cons data (table-variable-manipulator))))

(define *table* '())
(define (table-manipulator . args)
(if (null? args) *table*
(set! *table* (car args))))
(insert! "hello world" table-manipulator)

We can make a macro to generate such variable manipulators. It has to
be a macro since we have the same problem of telling it a variable
rather than the variable's value. I use "&" here in analogy with C's
"address-of".

;;; (& var) => a procedure p with
;;; (p): return value of var [i.e. var]
;;; (p val): update var to be val [i.e. (set! var val)]
(define-syntax &
(syntax-rules ()
((& var)
(lambda args
(if (null? args) var
(set! var (car args)))))))

(insert! "hello world" (& *table*))

4. Rather than being as general as #3, we can combine insert! and &.

(define-syntax insert!
(syntax-rules ()
((insert! data table)
(set! table (cons data table)))))

(define *table* '())
(insert! "hello world" *table*)

Gary Baumgartner

Sponsored Links