Is everything a list in scheme?

4
votes

Along with the book "Simply Scheme" (Second Edition) i'm watching the "Computer Science 61A - Lectures" on youtube. On the lectures , the tutor uses Stk interpreter, but i'm using chicken scheme interpreter.

In the first lecture he uses the "first" procedure which if it's called like : 

(first 'hello)

it returns "h".

On the book of "Simply Scheme" it has an example of how first can be implemented:

(define (first sent)
  (car sent))

Which to my testing and understanding works if sent is a list . I'm trying to understand if it's proper to say that "everything is a list" in scheme. To be more specific where's the list in 'hello and if there is one, why it doesn't work in first procedure as it's written in the book?

Also if every implementation is written with "everything is a list" in mind why the same code does not work in all scheme implementations?

3
listlispschemechicken-scheme
The short answer is "No, not everything in Scheme is a list." While lists predominate, there are other structures available. – Jerry Coffin
Simply Scheme is not following standard Scheme. In particular the function first has been redefined in Simply Scheme to work on symbols. See the package by @dyoo planet.plt-scheme.org/package-source/dyoo/simply-scheme.plt/2/2/… if you want to use Simply Scheme in DrRacket. – soegaard

3 Answers

4
votes

No, this is a common misconception because lists are so pervasive in Scheme programming (and often functional programming in general). Most Scheme implementations come with many data types like strings, symbols, vectors, maps/tables, records, sets, bytevectors, and so on.

This code snippet (first 'hello) is unlikely to work in most Schemes because it is not valid according to the standard. The expression 'hello denotes a symbol, which is an opaque value that can't be deconstructed as a list (the main thing you do with symbols is compare them with eq?). This is probably a quirk of Stk that is unfortunately taught by your book.

See The Scheme Programming Language for a more canonical description of the language. If you just want to learn programming, I recommend HtDP.

3
votes

Not everything is a list in Scheme. I'm a bit surprised that the example you're showing actually works, in other Scheme interpreters it will fail, as first is usually an alias for car, and car is defined only for cons pairs. For example, in Racket:

(first 'hello)
> first: expected argument of type <non-empty list>; given 'hello

(car 'hello)
> car: expects argument of type <pair>; given 'hello

Scheme's basic data structure is the cons pair, with it it's possible to build arbitrarily linked data structures - in particular, singly-linked lists. There are other data structures supported, like vectors and hash tables. And of course there are primitive types - booleans, symbols, numbers, strings, chars, etc. So it's erroneous to state that "everything is a list" in Scheme.

2
votes

With respect to Simply Scheme: the functions first and rest are not the standard ones from the Scheme standard, nor ones that come built-into DrRacket. The Simple Scheme API is designed as part of the Simply Scheme curriculum to make it easy to work uniformly on a variety of data. We can't make too many assumptions on how the underlying, low-level implementation works from just the experience of using the Simply Scheme teaching language! There's a runtime cost involved with making things that simple: it does not come for free.