car implementation in scheme

Question

I am trying to write by myself the cons function in scheme. I have written this code:

(define (car. z)
    (z (lambda (p q) p)))

and I am trying to run :

(car. '(1 2 3))

I expect to get the number 1, but it does not work properly.

In your definition of `car.` the argument z is used as a function applied to another function. In the call you pass instead a list, not a function. — Renzo, Jan 01 '19 at 10:23
`car.` wants a "lambda-encoded" list, not a Scheme list. You need to implement the corresponding `cons.` operation, so you can create such lists. — molbdnilo, Jan 01 '19 at 10:25
As @molbdnilo said in the comment, you must decide if you want to represent lists as functional objects (the definition of the function `car.`), or as data structures (as in your call), and act uniformely. If you represent lists as functional objects, you must define first `cons`, and pass the result of this function to `car.`. — Renzo, Jan 01 '19 at 10:28
In practice the genuine `car`, `cdr` and `cons` are builtins (and they have to be). Read Queinnec's [Lisp In Small Pieces](https://en.wikipedia.org/wiki/Lisp_in_Small_Pieces) — Basile Starynkevitch, Jan 01 '19 at 10:42
There are many examples of how to implement these operations in the lambda calculus available online. — molbdnilo, Jan 01 '19 at 10:47
@user10853826, you can find everything in [this great free book online](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html). Or see for instance this [SO question](https://stackoverflow.com/questions/21769348/use-of-lambda-for-cons-car-cdr-definition-in-sicp) — Renzo, Jan 01 '19 at 11:28
`car`, `cdr`, and `cons` don't need to be builtin if your language has things like `struct` as a primitive construct (though in theory, people usually do it the other way around -- that is to build `struct` from `cons` -- because `cons` is much simpler). — Sorawee Porncharoenwase, Jan 01 '19 at 11:36
`car.`'s argument must be a result of a call to `cons.`. `'(1 2 3)` is built by `(cons 1 (cons 2 (cons 3 '())))`. mind the dot. — Will Ness, Jan 02 '19 at 21:57
`(cons. a b)` creates a function that expects another function, and applies it to the two values so that that function can decide what to do with the two values: `(define ((cons. a b) f) (f a b))`. For instance, `((cons. a b) (lambda (p q) p)) = ((lambda (p q) p) a b) = a`. — Will Ness, Jan 02 '19 at 22:19

Sylwester · Answer 1 · 2019-01-01T19:05:16.850

When you implement language data structures you need to supply constructors and accessors that conform to the contract:

(car (cons 1 2))   ; ==> 1
(cdr (cons 1 2))   ; ==> 2
(pair? (cons 1 2)) ; ==> 2

Here is an example:

(define (cons a d)
  (vector a d))
(define (car p)
  (vector-ref p 0))
(define (cdr p)
  (vector-ref p 1))

Now if you make an implementation you would implement read to be conformant to this way of doing pairs so that '(1 2 3) would create the correct data structure the simple rules above is still the same.

From looking at car I imagine cons looks like this:

(define (cons a d)
  (lambda (p) (p a d)))

It works with closures. Now A stack machine implementation of Scheme would analyze the code for free variables living passed their scope and thus create them as boxes. Closures containing a, and d aren't much different than vectors.

I urge you to implement a minimalistic Scheme interpreter. First in Scheme since you can use the host language, then a different than a lisp language. You can even do it in an esoteric language, but it is very time consuming.

Mulan · Answer 2 · 2019-01-02T21:12:22.183

Sylwester's answer is great. Here's another possible implementation of null, null?, cons, car, cdr -

(define null 'null)

(define (null? xs)
  (eq? null xs))

(define (cons a b)
  (define (dispatch message)
    (match message
      ('car a)
      ('cdr b)
      (_ (error 'cons "unsupported message" message))
  dispatch)

(define (car xs)
  (if (null? xs)
      (error 'car "cannot call car on an empty pair")
      (xs 'car)))

(define (cdr xs)
  (if (null? xs)
      (error 'cdr "cannot call cdr on an empty pair")
      (xs 'cdr)))

It works like this -

(define xs (cons 'a (cons 'b (cons 'c null))))

(printf "~a -> ~a -> ~a\n"
        (car xs)
        (car (cdr xs))
        (car (cdr (cdr xs))))
;; a -> b -> c

It raises errors in these scenarios -

(cdr null)
; car: cannot call car on an empty pair

(cdr null)
; cdr: cannot call cdr on an empty pair

((cons 'a 'b) 'foo)
;; cons: unsupported dispatch: foo

define/match adds a little sugar, if you like sweet things -

(define (cons a b)
  (define/match (dispatch msg)
    (('car) a)
    (('cdr) b)
    (('pair?) #t)
    ((_) (error 'cons "unsupported dispatch: ~a" msg)))
  dispatch)

((cons 1 2) 'car)   ;; 1
((cons 1 2) 'cdr)   ;; 2
((cons 1 2) 'pair?) ;; #t
((cons 1 2) 'foo)   ;; cons: unsupported dispatch: foo

car implementation in scheme

2 Answers2