#:g1: sxhashの謎

Posted 2022-09-10 14:19:56 GMT

Common Lispのsxhashsxとはなんぞやという話がたまにあるのですが、Lispにおけるハッシュ関数/テーブルの導入の流れとして、

  1. BBN LISP(1971あたり)
  2. Interlisp(BBN LISPの後継)
  3. Lisp Machine Lisp
  4. Common Lisp

となっているため、この流れでの初出であるLisp Machine Lispがsxhashの初出でしょうね(なぜsxを付けたかは不明ですが)と、説明したりしていました。

とはいえ、sxS-Expressionの略称として使うというのは、Lisp Machine Lispには他に例がなく、ソースコードを検索しても、命名の慣習としても皆無に近い状況なので、一応、親戚のMACLISPのソースコードも検索してみたところ、sxを略称として使っているコードがちらほらある上にsxhash自体もMACLISPでは使われていることを知りました。

MACLISPにハッシュテーブルというデータ型がないので、一連のハッシュ関数/テーブルのユーティリティも存在しないと考えてしまったのですが、どうやらハッシュ関数だけは存在していたという落ちだったようです。

ちなみに、MACLISPにsxhashが導入されたのは、1973-03-22のようで、連鎖法によるシンボルのハッシュテーブルの実装が用例として挙げられています。

TO FACILITATE HASHCODING SCHEMES FOR S-EXPRESSIONSとあるので、sxs-expressionの略称であるという確証にもなるかなというところです。

BBN LISP(Interlisp)でもハッシュ関数とハッシュテーブル(hash-array)は分離しているのですが、MACLISPではハッシュ関数だけ取り入れたということなのかもしれません。
Lisp Machine Lispでは、Interlispからgethash等のハッシュ系ユーティリティを取り込むと共に、ハッシュ関数の名前だけは、MACLISPから取り入れ、そこからCommon Lispへ至ったのでしょう。

まとめ

Common Lispの関数の命名法の一貫性がないのは歴史的な事情に起因することが殆どですが、それらの起源を探るのは割合に困難で結局はよくわからないということがほとんどです……。


HTML generated by 3bmd in LispWorks 8.0.1

comments powered by Disqus