2
누구든지 LISP와 같은 링크 된리스트가 컴퓨터의 메모리에 어떻게 표현되는지에 대한 개요를 제공 할 수 있습니까? 컴퓨터가 포인터를 머리 부분과 나머지 목록을 유지하기 위해 CPU 레지스터를 사용합니까, 아니면 사용되는 힙입니까?LISP와 같은 링크 된리스트의 표현
A
답변
4
이 강하게 특정 컴파일러 및 언어 런타임을 사용중인에 따라 달라집니다. 그러나 일반적으로 Lisp과 같은 언어의 데이터 구조는 이웃에 대한 포인터가있는 힙 할당 셀입니다. 그런 다음 함수가 데이터에서 작동 할 때 하드웨어 레지스터에로드됩니다.
1 :
data [a] = [] | a : [a]
주어진 목록으로 작성 될 수있다 : (2- (3 (4
하스켈 링크 된리스트 유형을 고려 (5 : []))))이상의 간결 :
[1,2,3,4,5]
이것은 힙 ALLOC로 표현되는 폼을 ated 개체 :
화살표 포인터를 나타내는
; (:)은 "cons 셀", 현재 요소에 대한 포인터를 저장하는 작은 구조 및 목록의 꼬리를 나타냅니다.
이제 함수가이 데이터 구조에 액세스하면 구조체에 대한 포인터를 레지스터에로드하고 해당 포인터에서 데이터로드를 시작합니다. 정확한 세부 사항은 컴파일 모델과 런타임 시스템 모델에 따라 다릅니다. 예 : GHC 하스켈의 경우 이것은 STG Machine에 의해 주어진다. 또한 포인터의 하단 비트는 가리키는 특정 생성자를 나타내는 데 사용할 수 있습니다. 평가 상태 (평가되었거나 평가되지 않음) 및 작은 경우 값 자체 (심지어 pointer tagging optimization)가 포함됩니다.
2
에 따라 다릅니다. Stackoverflow는 실제 문제가있는 경우 가장 좋습니다.
'LISP'는 많은 언어와 수백 가지의 다른 구현물입니다.
링크드 목록을 구현하는 모든 종류의 방법이 이미 시도되었습니다.
Lisp 구현에 대한 책이 있으며 연구 할 크고 작은 오픈 소스 Lisp 구현이 많이 있습니다.
관련 문헌은 여기에 예를 들어 볼 수 있습니다 : http://library.readscheme.org/page8.html
3
Lisp에 관한 철학적 질문의 경우 가장 고무적인 소스 중 하나는 Anatomy of Lisp입니다. 비록 조금이라도 날짜가되어 있더라도. 이 책을 읽는 것은 (수년 전에) Lisp에 관한 것뿐만 아니라 일반적으로 프로그래밍에 대한 깨달음이었습니다. Lisp 구현에 대한 또 다른 우수한 책은 Lisp in Small Pieces입니다. Lisp 내부를 배우는 데 진지한 사람이라면이 두 가지가 도움이 될 것입니다.