simhでCategorical Programming Languageを動かす

[CPL](https://ja.wikipedia.org/wiki/CPL_(%E5%9C%8F%E8%AB%96%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E8%A8%80%E8%AA%9E)) (Categorical Programming Language) は圏論に基づいたプログラミング言語で、1987年に開発された。

2016年ごろにこの言語のオリジナル実装のソースコードが公開されたのを見て実行方法をまとめようとしていたが、長らく放置していたので4年越しでまとめ直してみた（雰囲気でsimhを使っているのでいろいろ間違っているかもしれない）。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">萩野先生が圏論言語CPLのオリジナル実装を <a href="https://t.co/J4xz9jwkZl">https://t.co/J4xz9jwkZl</a> で公開してくれました。わーい。 ただし、当時のコードそのままなので今は動かないかも。 Franz Lisp + C で書かれている。 端末UI(?)のコードがあって驚いた。</p>&mdash; Masahiro Sakai (@masahiro_sakai) <a href="https://twitter.com/masahiro_sakai/status/697422114622574593?ref_src=twsrc%5Etfw">February 10, 2016</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script> 

# 環境構築

オリジナルの CPL は VAX UNIX 4.2 上で Franz Lisp を使って実装されている。現代でFranz Lispの環境を作るのは大変なので、 [simh](http://simh.trailing-edge.com/) でVAX ULTRIX 4.0の環境をつくり、その上で動かしてみることにする（環境構築方法は [#:g1: Ultrix 4.0でFranz Lispを動かしてみよう](https://g000001.cddddr.org/3651773576) と [#:g1: Ultrix 4.0でT 3.1を動かそう](https://g000001.cddddr.org/3639634701)も参考にした）。

## simhのインストール

macOSであれば、Homebrewでインストールできる。

```console
% brew install simh
```

## tap形式のデータの準備

simhでマウントできるtap形式のデータを用意する。ULTRIX からはテープデバイスとして見える。

ULTRIX自体とunsupportedユーティリティのtapデータは http://bitsavers.org/bits/DEC/vax/ultrix/4.0/  からダウンロードして `gunzip` しておく。

```console
% mkdir cpl
% cd cpl
% wget http://bitsavers.org/bits/DEC/vax/ultrix/4.0/Ultrix_4.0_Supported.tap.gz
% gunzip Ultrix_4.0_Supported.tap.gz
% wget http://bitsavers.org/bits/DEC/vax/ultrix/4.0/Ultrix_4.0_Unsupported.tap.gz
% gunzip Ultrix_4.0_Unsupported.tap.gz
```

CPLのソースコードは、 [corbieのブログ:SIMH - テープ作成コマンドの改良](http://blog.livedoor.jp/corbie/archives/4002149.html) の `tapewrite` プログラムを使ってtar形式からtap形式に変換する。

```
% cc -o tapewrite tapewrite.c
% wget http://web.sfc.keio.ac.jp/~hagino/cpl.tgz
% gzcat cpl.tgz| ./tapewrite > cpl.tap
```

## ULTRIX 4.0のインストール

[ULTRIX 4.0 under SIMH](https://apfelboymchen.net/gnu/UNIX/vax-ultrix.html)を参考にインストールを進める。

以下のような設定ファイルを用意する。

```ini:vax.conf
; chevron prompt (extended memory boot ROM) and non-volatile RAM for the
; emulated MicroVAX 3900
load -r /usr/local/share/simh/vax/ka655x.bin
att nvr ultrix.nvr

; 32MB RAM
set cpu 32m
set cpu conhalt

; console interface
set tto 7b
set tti 7b

; RA90 disk drive, 1.2GB
set rq0 ra90
att rq0 rq1.dsk

; tape
set tq tk50
att tq0 Ultrix_4.0_Supported.tap
;att tq0 Ultrix_4.0_Unsupported.tap
;att tq0 cpl.tap

; disable stuff
set cr dis
set lpt dis
set rl dis
set ry dis
set ts dis
set tq1 dis
set tq2 dis
set tq3 dis

; use "setcap cap_net_raw=ep /usr/bin/simh-vax" to be able to run SIMH as 
; non-root. This must be a dedicated NIC on the host, in up state.
at xq0 eth1

; start the VAX
boot cpu
exit
```

上記の設定ファイルを引数に `vax` コマンドを実行する。

```console
% vax vax.conf
```

対話的にインストールを進める。

```
KA655-B V5.3, VMB 2.7
Performing normal system tests.
40..39..38..37..36..35..34..33..32..31..30..29..28..27..26..25..
24..23..22..21..20..19..18..17..16..15..14..13..12..11..10..09..
08..07..06..05..04..03..
Tests completed.

>>>boot mua0
```

設定ファイルの `att` でアタッチしたテープ（`mua0`, `Ultrix_4.0_Supported.tap`）から起動する。

```
*** STANDALONE ULTRIX ENVIRONMENT ***

If you select the BASIC Installation option from the list that follows,
the installation software creates file systems on default partitions on
your system disk and loads the mandatory ULTRIX software subsets.

If you require additional installation choices, select the ADVANCED
Installation option.

Select one of the following options:

        1) BASIC Installation
        2) ADVANCED Installation
        3) System management

Enter your choice: 2
```

`ADVANCED Installation` を選択する。

```
*** SYSTEM DISK SELECTION ***

The installation booklet for your processor explains the following table 
of system disk drives.  Select one of the devices below to contain the
root file system: 

SYSTEM DISK TABLE 

Selection   Device     ULTRIX     Device       Controller   Controller 
            Name       Name       Number       Name         Number     
---------------------------------------------------------------------- 
    1       RA90        ra0          0         RQDX3          0
---------------------------------------------------------------------- 

Enter your choice: 1

You selected RA90, device number 0. Make sure this disk drive 
is on line and write-enabled (if applicable to your disk drive), then
confirm your choice.

Use RA90, ra0, for your system disk? (y/n) []: y
```

他に選択肢がないのでこのデバイスを選択する。

```
 *** BOOTSTRAP COMMAND SEQUENCE ***

Enter the following boot sequence at the console mode prompt
after the installation software halts the processor: 

        >>> b dua0


syncing disks... done

?06 HLT INST
        PC = 8005F28D

>>>b dua0
```

指示に従ってディスク（`dua0`）から起動しなおす。

```
 *** SYSTEM NAME SPECIFICATION ***

Select the name of your system using alphanumeric characters.
The first character must be a letter.   For example, tinker.
Enter your system name:  tinker

You selected tinker as the name of your system.  Is this
correct? (y/n) [y]: y
```

システム名を設定する。何でもいいので入力例通り `tinker` にしてみる。

```
*** DATE AND TIME SPECIFICATION ***

The current date and time should be specified using the following
format:

        yymmddhhmm

Use two digits for year (yy), month (mm), day (dd), hour (hh), and
minute (mm).  Enter the time in 24-hour format.  For example, 11:30
p.m. on May 3, 1990 would be entered as:

        9005032330

Enter the date and time: 9005032330
```

ULTRIXは2000年問題非対応らしいので、入力例の通りにして 1990-05-30T23:30 にしてみる。

```
*** TIME ZONE SELECTION ***
        
Select the time zone for your area, using the options listed in the
table below.  You can also enter the number of hours (-12 to 12) in
time east of Greenwich.

  Selection     Time Zone 
---------------------------------
      e         Eastern
      c         Central
      m         Mountain
      p         Pacific
      g         Greenwich
---------------------------------

Enter your choice: e

Does your area alternate between Daylight Savings and Standard
time? (y/n) [y]: y


Select your geographic area for Daylight Savings Time, using the
options in the table below.

  Selection     Geographic Area 
--------------------------------
      u         USA
      a         Australia
      e         Eastern Europe
      c         Central Europe
      w         Western Europe
--------------------------------

Enter your choice [u]: u

The current date and time is Thu May  3 23:30:37 EDT 1990
```

適当にタイムゾーンを設定する。

```
*** SPECIFY THE SUPERUSER PASSWORD ***
The installation booklet for your processor instructs
you on how to enter the superuser password.
Changing password for root
Enter new password:
Verify:
```

root のパスワードを適当に決める。

```
*** FILE SYSTEM DEFAULT OPTION ***

The following table shows the default file system layout on RA90, ra0:

partition     bottom        top       size    overlap       default
    a              0      32767      32768    c             root
    b          32768     159839     127072    c             swap, dump
    d         159840     580036     420197    c,g           /usr

If you choose the defaults, the var area will be allocated to /usr/var.

Do you want to choose the default file system layout? (y/n): y
```

デフォルトに任せる。


```
Do you want to install ULTRIX Worksystem Software? y/n []: y
```

`y` を入力してULTRIX Worksystem Softwareのインストールに進む。

```
*** SUPPORTED SOFTWARE INSTALLATION ***

Please make sure your installation tape is mounted and on-line.
Are you ready (y/n)? y
```

テープはマウントされているので `y` を選択する。

```
*** Enter Subset Selections ***

The following subsets are mandatory and will be installed automatically:
 * Base System                           * Kernel Configuration Files           
 * TCP/IP Networking Utilities           * Network File System Utilities        
 * Extended (Berkeley) Mailer            * X11/DECwindows Servers               
 * X11/DECwindows User Environment       * X11/DECwindows 75dpi Fonts           

The subsets listed below are optional:
 1) System Exerciser Package             2) X11/DECwindows 100dpi Fonts         
 3) VS35XX X11/DECwindows Fonts          4) RAND Mail Handler                   
 5) Additional DECwindows Applications   6) Worksystem Development Software     
 7) Kerberos Network Authentication      8) Enhanced Security Features          
 9) Document Preparation Software       10) Printer Support Environment         
11) Adobe Font Metric Files             12) Software Development Utilities      
13) RPC Runtime Environment             14) RPC Development Environment         
15) Internationalization Tools          16) Source Code Control System          
17) Pascal Development Package          18) VAX C/ULTRIX                        
19) On Line Manual Pages                20) UWS Reference Pages                 
21) Accounting Software                 22) Communications Utilities            
23) Bisynchronous Communications        24) Maintenance Operations Protocol     
25) Unix-to-Unix Copy Facility          

26) All of the Above
27) None of the Above
28) Exit without installing subsets

Enter your choice(s): 27
```

CPLをコンパイル・実行するにはBase Systemだけで十分そうなので追加のものはインストールしない。

```
You are installing the following subsets:
   Base System                             Kernel Configuration Files           
   TCP/IP Networking Utilities             Network File System Utilities        
   Extended (Berkeley) Mailer              X11/DECwindows Servers               
   X11/DECwindows User Environment         X11/DECwindows 75dpi Fonts           

Is this correct? (y/n): y
```

確認して `y` を選択する。

```
*** CONFIGURATION FILE KERNEL OPTION SELECTION *** 

    Selection   Kernel Option 
---------------------------------------------------------------
        1       Local Area Transport (LAT)
        2       Bisynchronous Communication protocol (VAX only)
        3       Computer Interconnect (CI) network
        4       Ethernet Packet Filter
        5       Enhanced Security Features
        6       DECnet
        7       All of the above
        8       None of the above
----------------------------------------------------------------

Enter the selection number for each kernel option you want.
For example, 1 3 :  1 3
```

言われるままにしてみる。

```
You specified the following kernel options: 

        Local Area Transport (LAT)
        Computer Interconnect (CI) network

Is this correct? (y/n) [n]: y
```

大丈夫だと思う。

```
*** SYSTEM CONFIGURATION PROCEDURE ***
The installation software found these devices in the floating
address space:

        dz0             on uba0         at 0160100
        dz1             on uba0         at 0160110
        dz2             on uba0         at 0160120
        dz3             on uba0         at 0160130

Configuration file complete.

Do you want to edit the configuration file? (y/n) [n]: 
```

このまま進む。

```
Enter the following boot sequence at the console mode prompt
after the installation software halts the processor: 

        >>> b dua0


syncing disks... done

?06 HLT INST
        PC = 80080411
>>>b dua0
```

しばらく待つとインストールが完了するので、画面にしたがってディクスからブートする。

```
Loading system software.
No default boot device has been specified.

Available devices.
-DUA0 (RA90)
-DUA1 (RD54)
-DUA2 (RD54)
-DUA3 (RX50)
-MUA0 (TK50)
-XQA0 (08-00-2B-AA-BB-CC)

Device? [XQA0]: dua0
```

ブートデバイスを聞かれたので `dua0` と答えてみる。

```
ULTRIX V4.0 (Rev. 161) (tinker)

login: root
Password:
```

root でログインする。

```console
# ls
.cshrc		bin		lib		pcs750.bin	usr
.login		dev		lost+found	sys		var
.profile	etc		mnt		tmp		vmb.exe
.rhosts		genvmunix	opr		ultrixboot	vmunix
# halt
syncing disks... done
```

インストールできたようなので `halt` して `vax` コマンドを終了する。

## Franz Lispをインストールする

設定ファイルの `att` の部分を下記のように変更して、 `Ultrix_4.0_Unsupported.tap` をアタッチするようにする。

```
; tape
set tq tk50
;att tq0 Ultrix_4.0_Supported.tap
att tq0 Ultrix_4.0_Unsupported.tap
;att tq0 cpl.tap
```

再度 `vax` コマンドを実行する。

```
% vax vax.conf
```

```
Tests completed.
>>>b dua0
```

`dua0` から起動して先程と同じようにrootでログインする。

```console
# setld -a /dev/rmt0h

Please make sure your installation tape is mounted and on-line.
Are you ready (y/n)? y
Positioning Tape


*** Enter Subset Selections ***

The subsets listed below are optional:
 1) Base Extension                       2) GNU Emacs                           
 3) Games and Diversions                 4) Franz Lisp Development Package      
 5) Modula-2 Development Package         6) Raster Plotter Package              
 7) Supplementary Documentation          8) APL Development Package             
 9) Bibliographic Utilities             10) Remote Procedure Call Compiler      
11) CP/M 8in Diskette Utility           12) Auxiliary Command Line Interpreter  
13) Hyperchannel Utilities              14) ICON (Language) Development Packag  
15) Ingres DBMS                         16) USENET News Interface Software      
17) Notesfiles Package                  18) Revision Control System             
19) Software Project Management System  20) Miscellaneous User-Contributed Uti  
21) Unsupported Fortran Utilities       22) Computer Aided System Tutor         
23) Unsupported On-Line Documentation   24) Unsupported X11 Components          
25) Unsupported X10 to X11 tools        26) Unsupported X11 Reference Pages     

27) All of the Above
28) None of the Above
29) Exit without installing subsets

Enter your choice(s): 4

You are installing the following subsets:
   Franz Lisp Development Package       

Is this correct? (y/n): y

Copying Franz Lisp Development Package (ULXLISP400) from tape
Verifying Franz Lisp Development Package (ULXLISP400)
Rewinding Tape...
```

ULTRIX内で `setld` コマンドを実行してFranz Lispをインストールする。インタプリタの `lisp` コマンドと、コンパイラの `liszt` コマンドがインストールされる。

```console
# rehash
# lisp
Franz Lisp, Opus 38.79
-> t
t
-> ^D
Goodbye
# halt
```

`lisp` コマンドが実行できればインストールは成功。 `halt` して再度 `vax` コマンドを終了する。

## CPLをビルドする


設定ファイルの `att` の部分を下記のように変更して、 `cpl.tap` をアタッチするようにする。

```
; tape
set tq tk50
;att tq0 Ultrix_4.0_Supported.tap
;att tq0 Ultrix_4.0_Unsupported.tap
att tq0 cpl.tap
```

再度 `vax` コマンドを実行する。

```
% vax vax.conf
```

```
>>>b dua0
```

`dua0` から起動して先程と同じようにrootでログインする。

```console
# tar tv
tar: blocksize = 1
rwxr-xr-x 138/-15456       0 Jan  6 04:15 1998 cpl/
rwxr-xr-x 138/-15456       0 Jan  6 04:15 1998 cpl/src/
rwxr-xr-x 138/-15456       0 Jan  6 04:15 1998 cpl/system/
rw-r--r-- 138/-15456     348 Jun  9 07:39 1987 cpl/system/InfList
rw-r--r-- 138/-15456     444 Jun  9 06:42 1987 cpl/system/List
rw-r--r-- 138/-15456     283 Jun  9 06:42 1987 cpl/system/Sort
rw-r--r-- 138/-15456     972 Jun  9 06:42 1987 cpl/system/Nat
rw-r--r-- 138/-15456    8463 Jun  9 09:21 1987 cpl/system/log
rw-r--r-- 138/-15456    4525 Jun  9 06:42 1987 cpl/system/Nat.save
rw-r--r-- 138/-15456     192 Jun  9 09:21 1987 cpl/system/CoNat
rw-r--r-- 138/-15456   51176 Sep 25 09:02 1987 cpl/src/wm.c
rw-r--r-- 138/-15456   18610 Jun  9 06:42 1987 cpl/src/display.c
r--r--r-- 138/-15456   11036 Jun  9 06:42 1987 cpl/src/tv.l
rw-r--r-- 138/-15456    7228 Jun  9 06:42 1987 cpl/src/exm.tex
rw-r--r-- 138/-15456   16675 Jun  9 06:42 1987 cpl/src/winlib.c
rw-r--r-- 138/-15456   62505 Jun  9 06:42 1987 cpl/src/wcat.l
rw-r--r-- 138/-15456    2656 Jun  9 06:42 1987 cpl/src/term.h
rw-r--r-- 138/-15456    3702 Jun  9 06:42 1987 cpl/src/wcathelp.l
rw-r--r-- 138/-15456   20431 Jun  9 06:42 1987 cpl/src/handout.tex
rw-r--r-- 138/-15456   12914 Jun  9 06:42 1987 cpl/src/wmlib.l
rw-r--r-- 138/-15456    2645 Jun  9 06:42 1987 cpl/src/termcap
rw-r--r-- 138/-15456     707 Jun  9 06:42 1987 cpl/src/winlib.h
rw-r--r-- 138/-15456   13257 Jun  9 06:42 1987 cpl/src/wm.hlp
rw-r--r-- 138/-15456     777 Jun  9 06:42 1987 cpl/src/display.h
rw-r--r-- 138/-15456   15128 Jun  9 06:42 1987 cpl/src/wtrace.l
rw-r--r-- 138/-15456   20028 Jun  9 06:42 1987 cpl/src/wdia.l
rw-r--r-- 138/-15456    3189 Jun  9 06:42 1987 cpl/src/wm.cmd
rw-r--r-- 138/-15456    9918 Jun  9 06:42 1987 cpl/src/term.c
rw-r--r-- 138/-15456     732 Jun  9 06:42 1987 cpl/src/makefile
# tar x
tar: blocksize = 1
# cd cpl
# ls
src	system
```

CPLのソースコードがテーブデバイスとして見えているので `tar` で展開する。

```
# cd src
# make
```

`src` で `make` すると、 `liszt` で `.l` ファイルをコンパイルして実行ファイル `lcat` ができる。

# 動かしてみる

CPL自体の使い方は [萩野達也「カテゴリー理論的関数型プログラミング言語」1990年1月](https://www.jstage.jst.go.jp/article/jssst/7/1/7_1_16/_pdf/-char/ja) の5章なども参照。

```
# ./lcat
Categorical Programming Language (version 3)
cpl>help
edit    input or edit objects and morphisms
show    show objects and morphisms
delete  delete objects and morphisms
let     define morphisms
simp    simplify morphisms
expand  expand auxiliary morphisms
new     clear old definitions
read    read file
load    load saved file
save    save definitions onto file
diagram diagram editor
set     set flags
scroll  scroll show window
alias   set aliases
keypad  set keypad
help    print help message
quit    quit the system
```

`help` コマンドで使い方を確認する。

```
cpl>read ../system/Nat
productive right object 1 defined
productive right object prod(+,+) defined
productive right object exp(-,+) defined
coproductive left object coprod(+,+) defined
left object bool defined
left object nat defined
add : prod(nat,nat) -> nat defined
mult : prod(nat,nat) -> nat defined
fact : nat -> nat defined
sub1 : nat -> coprod(nat,1) defined
minus : prod(nat,nat) -> coprod(nat,1) defined
lesseq : prod(nat,nat) -> bool defined
and : prod(bool,bool) -> bool defined
or : prod(bool,bool) -> bool defined
not : bool -> bool defined
equal : prod(nat,nat) -> bool defined
```

`read` コマンドでファイルからCPLプログラムを読み込める。

```
cpl>simp mult.pair(s.s.0, s.s.s.0)
s.s.s.s.s.s.0
    :1 -> nat
```

上で読み込んだ `nat`, `prod` の定義と、 `simp` コマンドを使うとこんな感じで掛け算が計算できる。

```
cpl>quit
bye
```

`quit` で終了できる。

# Haskell版

CPLを試したいだけなら、たぶん[Haskell版実装](https://github.com/msakai/cpl)を使う方が楽です。