Schemeのequal?の実装について調べたメモ

R7RSでは、equal?に循環オブジェクトを入力した場合でも必ず終了することが要求されていて、その実装方針について調べていた。
探している答えそのものな内容の論文が見つかった。
“Efficient Nondestructive Equality Checking for Trees and Graphs"という論文でunifon-findを使って循環オブジェクトを効率的に処理しようというものだった。

以下すごく雑なメモ
1、2章、読んでない
3章、pairやvectorを比較するとき、それらをunion-findを用いて、同じ集合にまとめて、次に同じ比較をするときや、不要な比較のケースをはぶいてしまおうという内容。
4章、サイズが小さく、循環構造を含まないものを比較するときに、union-findの部分が足をひっぱるので、union-findなしでk回比較して、終わらなかったらunion-findを使おうという内容
5章、4章の方針の場合、サイズが大きいものを比較する場合、結局union-findの分遅くなるので、各頂点ごとにunion-findありのものとなしのものを併用していくという内容。
6章、4章と5章を融合させるという内容。つまり、5章の方針の前にunion-findなしでk回比較させるという内容。

ELFヘッダのe_identについて調べました。

ELFはメジャーなオブジェクトファイルのフォーマット。
今回は、そのELFファイルの最初の16バイトであるe_identについて調べる。
e_identは、ELFヘッダの一部なので、readelf -hで確認することができる。

$readelf -h a.out                                                                                                                                                                                   0 < 02:49:50
ELF ヘッダ:
  マジック:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  クラス:                            ELF64
  データ:                            2 の補数、リトルエンディアン
  バージョン:                        1 (current)
  OS/ABI:                            UNIX - System V
  ABI バージョン:                    0
  型:                                DYN (共有オブジェクトファイル)
  マシン:                            Advanced Micro Devices X86-64
  バージョン:                        0x1
  エントリポイントアドレス:               0x570
  プログラムの開始ヘッダ:          64 (バイト)
  セクションヘッダ始点:          6560 (バイト)
  フラグ:                            0x0
  このヘッダのサイズ:                64 (バイト)
  プログラムヘッダサイズ:            56 (バイト)
  プログラムヘッダ数:                9
  セクションヘッダ:                  64 (バイト)
  セクションヘッダサイズ:            29
  セクションヘッダ文字列表索引:      28



中身が分かったので、ひとつづつ確認していく。
頭から16バイトをとりだす。

 $od -An -tx1 -N16 a.out                                                                                                                                                         
 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00



最初の4バイト(7f 45 4c 46)はマジックナンバー
0x7f ‘E’ ‘L’ ‘F'となっているね。

次の1バイト(02)は32bitか64bitかの区別。
/usr/include/elf.hによると02なので64-bit object。

#define ELFCLASSNONE  0    /* Invalid class */
#define ELFCLASS32  1    /* 32-bit objects */                                                                                                                                                                      
#define ELFCLASS64  2    /* 64-bit objects */
#define ELFCLASSNUM  3



次の1バイト(01)は、エンディアン
同様に確認すると、2の補数、little endianとなっている。

#define ELFDATANONE  0    /* Invalid data encoding */
#define ELFDATA2LSB  1    /* 2's complement, little endian */
#define ELFDATA2MSB  2    /* 2's complement, big endian */                                                                                                                                                         
#define ELFDATANUM  3



次の1バイト(01)はバージョン。
必ず1になっていなくてはいけないっぽい

#define EV_NONE    0    /* Invalid ELF version */
#define EV_CURRENT  1    /* Current version */                                                                                                                                                                     
#define EV_NUM    2



次の1バイト(00)は、ABI。
ABIについては、ちゃんと理解してないのだけどWikipediaでも見ればいいかな。
後回し。
00なので、ABIがSYSVであることは分かった。

#define ELFOSABI_NONE    0  /* UNIX System V ABI */
#define ELFOSABI_SYSV    0  /* Alias.  */
#define ELFOSABI_HPUX    1  /* HP-UX */
#define ELFOSABI_NETBSD    2  /* NetBSD.  */
#define ELFOSABI_GNU    3  /* Object uses GNU ELF extensions.  */
#define ELFOSABI_LINUX    ELFOSABI_GNU /* Compatibility alias.  */
#define ELFOSABI_SOLARIS  6  /* Sun Solaris.  */
#define ELFOSABI_AIX    7  /* IBM AIX.  */
#define ELFOSABI_IRIX    8  /* SGI Irix.  */
#define ELFOSABI_FREEBSD  9  /* FreeBSD.  */
#define ELFOSABI_TRU64    10  /* Compaq TRU64 UNIX.  */
#define ELFOSABI_MODESTO  11  /* Novell Modesto.  */
#define ELFOSABI_OPENBSD  12  /* OpenBSD.  */
#define ELFOSABI_ARM_AEABI  64  /* ARM EABI */
#define ELFOSABI_ARM    97  /* ARM */
#define ELFOSABI_STANDALONE  255  /* Standalone (embedded) application */

のこりの8バイトは、ABIバージョンと予約で開けられている。
ABIバージョンの形式は、ABI依存。

pycのマジックナンバーについて調べました。

Pythonバイトコードのpycの最初の4バイトにはマジックナンバーがあって、どのバージョンで作成されたのか分かるようになっている。 各バージョンのマジックナンバー
Lib/importlib/_bootstrap_external.pyを見れば分かる。 マジックナンバーは、各バージョンごとに用意されている2バイトの数値+168627479になっている。

pycからバージョンを調べる

まず、中身をみる。

$ od -tx1 a.pyc                                                  
0000000 17 0d 0d 0a b2 cb 3e 59 1f 00 00 00 e3 00 00 00
0000020 00 00 00 00 00 00 00 00 00 02 00 00 00 40 00 00
0000040 00 73 10 00 00 00 64 00 00 64 01 00 84 00 00 5a
0000060 00 00 64 02 00 53 29 03 63 02 00 00 00 00 00 00
0000100 00 02 00 00 00 02 00 00 00 43 00 00 00 73 08 00
0000120 00 00 7c 00 00 7c 01 00 17 53 29 01 4e a9 00 29
0000140 02 da 01 61 da 01 62 72 01 00 00 00 72 01 00 00
0000160 00 fa 04 61 2e 70 79 da 03 66 6f 6f 01 00 00 00
0000200 73 02 00 00 00 00 01 72 05 00 00 00 4e 29 01 72
0000220 05 00 00 00 72 01 00 00 00 72 01 00 00 00 72 01
0000240 00 00 00 72 04 00 00 00 da 08 3c 6d 6f 64 75 6c
0000260 65 3e 01 00 00 00 73 00 00 00 00
0000273

最初の4バイトは,17 0d 0d 0aなので、

>>> 23 + 13 * (1<<8) + 13 * (1<<16) + 10 * (1<<24)
168627479

マジックナンバーは168627479で、下2バイトをとりだす。

>>>168627479 & int("FFFF",16)
3351

あとは、一覧を眺めて同じやつを見つける。

#     Python 3.5b1  3330 (PEP 448: Additional Unpacking Generalizations)
#     Python 3.5b2  3340 (fix dictionary display evaluation order #11205)
#     Python 3.5b2  3350 (add GET_YIELD_FROM_ITER opcode #24400)
#     Python 3.5.2  3351 (fix BUILD_MAP_UNPACK_WITH_CALL opcode #27286)
#     Python 3.6a0  3360 (add FORMAT_VALUE opcode #25483
#     Python 3.6a0  3361 (lineno delta of code.co_lnotab becomes signed)
#     Python 3.6a1  3370 (16 bit wordcode)
#     Python 3.6a1  3371 (add BUILD_CONST_KEY_MAP opcode #27140)
#     Python 3.6a1  3372 (MAKE_FUNCTION simplification, remove MAKE_CLOSURE
#                         #27095)
#     Python 3.6b1  3373 (add BUILD_STRING opcode #27078)
#     Python 3.6b1  3375 (add SETUP_ANNOTATIONS and STORE_ANNOTATION opcodes
#                         #27985)
#     Python 3.6b1  3376 (simplify CALL_FUNCTIONs & BUILD_MAP_UNPACK_WITH_CALL)
#     Python 3.6b1  3377 (set __class__ cell from type.__new__ #23722)
#     Python 3.6b2  3378 (add BUILD_TUPLE_UNPACK_WITH_CALL #28257)
#     Python 3.6rc1 3379 (more thorough __class__ validation #23722)
#     Python 3.7a0  3390 (add LOAD_METHOD and CALL_METHOD opcodes)

バージョン3.5.2だね。

処理系からマジックナンバーを調べる

>>> import importlib.util
>>> importlib.util.MAGIC_NUMBER
b'\x17\r\r\n'
>>> int.from_bytes(importlib.util.MAGIC_NUMBER,"little")
168627479

glutで画像を表示したぞ。

ppm形式(raw)の画像を用意して、それをglutで表示する。
座標とかはやってない。
高さx幅xRGBのサイズのarrayを用意して、画像を読み込み、glDrawPixelsを実行するだけ。

コンパイル方法。(オプションが多いね。)

gcc a.c -lglut -lGL

コード

#include<GL/glut.h>
#include<stdio.h>
#include<stdlib.h>

unsigned char image[400][640][3];

int ppm_read(char *filename, unsigned char *pimage){
  FILE *fp;
  if((fp=fopen(filename,"rb"))==NULL){
     printf("ERROR:%s\n",filename);
     exit(-1);
  }
  fscanf(fp,"P6\n640 480\n255\n");
  fread(pimage,sizeof(char),640*400*3,fp);
  fclose(fp);
  return 0;
}


void disp(){
    glClear(GL_COLOR_BUFFER_BIT);
    glDrawPixels(640, 400, GL_RGB, GL_UNSIGNED_BYTE, &image[0][0][0]); 
    glFlush();
}

void resize(){

}

void keyboard(unsigned char key,int x,int y){

}

void mouse(int button,int state,int x,int y){

}

void motion(int x,int y){
    
}


void init(){
    glClearColor(0.0, 0.0, 1.0, 1.0);
    ppm_read("a.ppm",&image[0][0][0]);
}

int main(int argc,char *argv[]){
    glutInit(&argc,argv);
    glutCreateWindow("TITLE NAME");
    glutInitDisplayMode(GLUT_RGBA);
 
    glutDisplayFunc(disp);
    glutKeyboardFunc(keyboard);
    glutReshapeFunc(resize);
    glutMouseFunc(mouse);
    glutMotionFunc(motion);
 
    init();
    glutMainLoop();
    return 0;
}

syntax-rulesの同じ深さの<ellipsis>

同じ深さので、違う場所で宣言された場合どうなるのか確認した。
多くの処理系では、短いほうが優先される。

(define-syntax foo
  (syntax-rules ()
    ((_ ((a ...) ...) (( b ... ) ... ))
     (quote ( ((a b) ...) ... )))))

(display 
  (foo ((a b)(c d e)) ((A B)(C D E))));(((a A) (b B)) ((c C) (d D) (e E)))

(newline)

(display
  (foo ((a b) ( c d )) ((A B)(C D E )) ));(((a A) (b B)) ((c C) (d D)))
(newline)

Schemeでライブラリを定義するぞ

Schemeのr7rsにはライブラリを定義する構文がある。
例↓

(define-library (niyarin test)
    (import (scheme base))
    (export foo1 foo2)
    (begin 
      (define (foo1 a) (+ a 1 ))
      (define (foo2 a) (- a 1))))

Schemeのライブラリ名は、ライブラリを一意に判別するため、識別子と正の整数のリストを使う。
define-libraryでは、外側の環境へアクセスできないので、使いたい機能をimportする必要があり、また外側の環境で使う場合どの識別子を見られるようにするのかexportで指定する必要がある。
あとは、begin内にlibrary本体を記述すれば最低限使えるようになると思う。
define-library内では、例が使われたものの他にinclude include-ci include-library-declarations cond-expandが使える。

作ったライブラリを使うには、もちろんimportするだけでよい。
ただし、ライブラリ自体は現在の環境から見えるようにする必要があるので、外側のファイルに書いた場合なんかは、include、loadなどする必要がある。

(import (niyarin test) (scheme write))
(display (foo1 1));2

無事使えた。
以上。

dynamic-wind。

dynamic-windについてまとめた。

dynamic-windのつかいかた

(dynamic-wind before thunk after)
  • 引数はすべてthunk(引数0の手続き)。
  • before、thunk、afterの順に実行する。
  • ただし、真ん中のthunkで継続を取り出して外側から呼び出した場合や中から外側の継続を呼び出した場合は特別な動きをする。
  • 外側から継続を呼び出した場合、呼び出す前にbefore、後にafterを呼ぶ。
  • 内側から外側の継続を呼び出した場合その継続が呼ばれる前にafterを呼ぶ。(もちろんbeforeはその前に呼ばれている)


実行例

(define cont #f)

(dynamic-wind 
  (lambda () (display 1))
  (lambda  () (display (call/cc (lambda (c) (set! cont c) 2))))
  (lambda () (display 3)(newline)))

(cont 0)

結果

123
103

やること。
beforeで1を表示、afterで3と表示して改行
真ん中のthunkで、継続を取り出してその結果を標準出力する。
そして外側から継続を呼ぶ。