Tính năng "Nhược điểm" hoạt động như thế nào trong Lisp?

Question

Tôi đã học Lisp và tôi không có kinh nghiệm trong lập trình Lisp. Trong một phần của nghiên cứu của tôi, tôi gặp phải những ví dụ dưới đây:

> (cons ‘a ‘(a b)) ----> (A A B) 
> (cons ‘(a b) ‘a) ----> ((A B).A) 

tôi đã tự hỏi tại sao khi chúng ta có (khuyết điểm 'a' (ab)) phản ứng là (AAB) và tại sao khi chúng ta thay đổi một chút và đặt 'a sau (ab), câu trả lời là một danh sách chấm chấm như ((AB) .A)? Sự khác nhau giữa dòng mã đầu tiên và dòng mã thứ hai là gì? Điều gì đang xảy ra đằng sau những mã này?

Answer 1

Thật dễ hiểu nếu bạn nghĩ về chúng là cons-cells.

Tóm lại, ô khuyết điểm bao gồm chính xác hai giá trị. Ký pháp thông thường cho điều này là sử dụng dấu chấm, ví dụ:

(cons 'a 'b) ==> (A . B) 

Nhưng vì danh sách được sử dụng thường xuyên trong LISP, ký hiệu tốt hơn là thả dấu chấm. Danh sách được thực hiện bằng cách có phần tử thứ hai là ô đối âm mới, với kết thúc cuối cùng là một terminator (thường là nil, hoặc '() trong Common Lisp). Vì vậy, hai người đều bình đẳng:

(cons 'a (cons 'b '())) ==> (A B) 
(list 'a 'b) ==> (A B) 

Vì vậy (cons 'a 'b) tạo ra một tế bào [a,b], và (list 'a 'b) sẽ tạo [a, [b, nil]]. Lưu ý quy ước cho danh sách mã hóa trong ô đối sánh: Chúng kết thúc bằng một bên trong nil.

Bây giờ, nếu bạn chống số 'a vào danh sách cuối cùng, bạn tạo ô đối âm mới có chứa [[a, [b, nil]], a]. Vì đây không phải là danh sách "phù hợp", tức là danh sách này không bị chấm dứt bằng nil, cách viết ra là sử dụng dấu chấm: (cons '(a b) 'a) ==> ((a b) . a).

Nếu chấm không được in, nó sẽ phải là danh sách có cấu trúc [[a, [b, nil]], [a, nil]].

dụ bạn

Khi bạn làm (cons 'a '(a b)) nó sẽ mất biểu tượng 'a và danh sách '(a b) và đặt chúng trong một tế bào khuyết điểm mới. Vì vậy, điều này sẽ bao gồm [a, [a, [b, nil]]]. Vì điều này tự nhiên kết thúc với một bên trong nil, nó được viết mà không có dấu chấm.

Đối với (cons '(a b) 'a), bây giờ bạn sẽ nhận được [[a, [b, nil]], a]. Điều này làm không chấm dứt với một bên trong nil và do đó ký hiệu dấu chấm sẽ được sử dụng.

Chúng ta có thể sử dụng khuyết điểm để làm ví dụ cuối cùng với một số không?Vâng, nếu chúng ta làm

(cons '(a b) (cons 'a '())) ==> ((A B) A) 

Và, cuối cùng,

(list '(a b) 'a)) 

tương đương với

(cons (cons (cons 'a (cons 'b '())) (cons 'a '()))) 

Answer 2

Một danh sách (abc) được đại diện (được lưu trữ nội bộ) như ba tế bào khuyết điểm: (cons 'a (cons 'b (cons 'c '()). Lưu ý rằng cặp cuối cùng có '() trong cdr của nó.

Loạt ô đối sánh có cdr cuối cùng là '() được in dưới dạng danh sách của máy in. Ví dụ được in như (a b c).

Hãy xem: (cons 'a '(a b)). .

Danh sách '(ab) được biểu diễn dưới dạng (khuyết điểm' một (khuyết điểm 'b'()) Điều này có nghĩa rằng (cons 'a '(a b)) sản xuất:. (cons 'a (cons 'a (cons 'b '()))

Hãy xem tại địa chỉ:. (cons '(a b) 'a)

Các danh sách '(ab) được biểu diễn dưới dạng (khuyết điểm' một (khuyết điểm 'b'()). Điều này có nghĩa rằng (cons (cons '(a b) 'a)) sản xuất (cons (cons 'a (cons 'b '()) 'a).

Lưu ý rằng loạt bài này không kết thúc trong '(). Để hiển thị rằng máy in sử dụng dấu chấm ký hiệu. (... . 'a) có nghĩa là một giá trị bao gồm một loạt các ô đối ứng và cdr cuối cùng chứa 'a. Do đó, giá trị (cons (cons 'a (cons 'b '()) 'a) được in dưới dạng '((a b) . a).

Answer 3

Xem hình dung này:

CL-USER 7 > (sdraw:sdraw '(A A B)) 

[*|*]--->[*|*]--->[*|*]--->NIL 
|  |  | 
v  v  v 
A  A  B 

CL-USER 8 > (sdraw:sdraw '((A B) . A)) 

[*|*]--->A 
| 
v 
[*|*]--->[*|*]--->NIL 
|  | 
v  v 
A  B 

Ngoài ra:

CL-USER 9 > (sdraw:sdraw '(A B)) 

[*|*]--->[*|*]--->NIL 
|  | 
v  v 
A  B 

CL-USER 10 > (sdraw:sdraw (cons 'A '(A B))) 

[*|*]--->[*|*]--->[*|*]--->NIL 
|  |  | 
v  v  v 
A  A  B 

CL-USER 11 > (sdraw:sdraw (cons '(A B) 'A)) 

[*|*]--->A 
| 
v 
[*|*]--->[*|*]--->NIL 
|  | 
v  v 
A  B 

Answer 4

Một cons là một cấu trúc dữ liệu có thể chứa hai giá trị. Ví dụ: (cons 1 2) ; ==> (1 . 2). Phần đầu tiên là car, phần thứ hai là cdr. A cons là list nếu đó là cdr là nil hoặc list. Do đó, (1 . (2 . (3 .()))) là một danh sách.

Khi in cons chấm được bỏ qua khi cdr là cons hoặc nil. Các dấu ngoặc đơn bên ngoài của cdr cũng bị bỏ qua. Do đó (3 .()) được in (3) và (1 . (2 . (3 .()))) được in (1 2 3). Đó là cấu trúc tương tự, nhưng với hình dung khác nhau. A cons trong số car không có quy tắc này.

Chức năng đọc đọc cons có dấu chấm và định dạng in đặc biệt lạ khi cdr là danh sách. Nó sẽ ở thời gian đọc hành xử như thể nó là cons.

Với quy tắc đặc biệt cho cả read và print, ảo ảnh của danh sách hoàn tất ngay cả khi đó là chuỗi cons.

(cons ‘a ‘(a b)) ----> (A . (A B)) 
(cons ‘(a b) ‘a) ----> ((A B) . A) 

Khi in, danh sách thứ nhất gồm 3 thành phần từ cdr là danh sách.