Кіріспе

Компьютерлік ғылымда CDR кодтамасы – Lisp тізімдері үшін қысылған деректерді ұсыну тәсілі. Ол MIT Жасанды интеллект зертханасында әзірленді және патенттелді, сондай-ақ MIT CADR-ден туындаған бірнеше Lisp машиналарында компьютерлік аппараттық құралдарда іске асырылды. CDR кодтау, шын мәнінде, өте жалпы идея; егер деректер объектісі A басқа деректер құрылымы B-ға сілтемемен аяқталса, онда біз B құрылымын өзімен бірге, A-ның соңына дейін қосып, одан асырып орналастыра аламыз. Осылайша сілтемеге қажетті орын босатылады, егер мұны көп рет жасасақ, ол жинақталуы мүмкін, сонымен қатар деректерге қолжетімділікті жақсартамыз, бұл заманауи машиналардың өнімділігін арттырады. Бұл трансформация, әсіресе, оны жасау үшін арналған cons-негізделген тізімдер үшін тиімді; бұл трансформацияны орындайтын әрбір түйін үшін шамамен жартылай орын босатылады. Бұл алмастыруды орындау әрқашан мүмкін емес, себебі A-ның соңынан кейін жеткілікті үлкен бос орын болмауы мүмкін. Сондықтан, кейбір объектілер нақты сілтемемен аяқталады, ал кейбіреулері сілтемеленген объектімен, ал машина соңғы жасушаны оқып, қайсысы екенін анықтауы керек. Бұл бағдарламалық жасақтамада белгілі бір тиімсіздікпен, таңбаланған сілтемелерді пайдалану арқылы жүзеге асырылуы мүмкін, олар соңғы позициядағы сілтемені осылай тануға мүмкіндік береді, бірақ аппараттық құралдарда жақсырақ орындалады. Өзгертілетін объектілер болған жағдайда CDR кодтамасы күрделене түседі. Егер сілтеме басқа объектке жаңартылса, бірақ қазіргі уақытта сол өрісте сақталған объект болса, онда объект оны басқа да сілтемелермен бірге жылжытылуы керек. Мұндай жылжытулар әдетте қымбатқа түседі немесе мүмкін емес, сонымен қатар уақыт өте келе деректер сақталымының фрагментациясына әкеледі. Бұл мәселені әдетте CDR кодтамасын тек өзгертілмейтін деректер құрылымдарында қолдану арқылы болдырмайды.