【Windows】LaTeX環境構築

VSCodeのインストールとupLaTeXを前提とする。

TexLive

1. https://www.tug.org/texlive/acquire-netinstall.htmlからインストーラをダウンロード。
2. 実行。Installを選択してNext。2枚目のウィンドウが開く。
3. 高度な設定
   • スキーム: basicスキーム(plain + latex)
   • カスタマイズ: LaTeX 推奨パッケージを追加。スキームの表示がカスタムスキームに変わる。
   • インストール。かなり長い。
4. コマンドプロンプトでlatexと打つと以下のように出る(Ctrl + cで抜ける)。

C:\Users\seaso>latex
This is pdfTeX, Version 3.141592653-2.6-1.40.25 (TeX Live 2023) (preloaded format=latex)
 restricted \write18 enabled.
**

確認

upLaTeX

uplatex, uplatex.windowsがインストール済み

1. test.texを作成。\documentclassにuplatexを指定。
2. uplatex test.tex: test.aux, test.dvi, test.logが作成される。
3. dvipdfmx test.dvi: test.pdfが作成される。

\documentclass[uplatex]{jsarticle}
\begin{document}

\title{タイトル}
\author{著者}
\maketitle

\section{見出し}
本文

\end{document}

latexmk

1. TLShell TeX Live ManagerからTeX Live Shellを起動。
2. 状態の未インストールを選択し、latexmkで検索。latexmk, latexmk.windowsの二つが出てくる。
3. 両方チェックを入れ、選択項目をインストール。インストール済みに二つが追加される。
4. C:\ユーザー\{ユーザー名}\に.latexmkrcファイルを作成。upLaTeXの場合以下のようにする。

$latex = 'uplatex %O -kanji=utf8 -no-guess-input-enc -synctex=1 -interaction=nonstopmode %S';
$biber = 'biber %O --bblencoding=utf8 -u -U --output_safechars %B';
$bibtex = 'upbibtex %O %B';
$makeindex = 'upmendex %O -o %D %S';
$dvipdf = 'dvipdfmx %O -o %D %S';
$pdf_mode = 3;
$pdf_previewer = "start %S"

> latexmk test.tex

で必要に応じて中間ファイルが生成され.dvi, .pdfが出力される。

> latexmk -pv test.tex

でpdfを出力した後、指定のビュワーで開く。

LaTeX Workshop

1. VSCodeでLaTeX Workshopをインストール
2. settings.jsonを編集し、latexmkを利用できるようにする。
3. .texファイルを開くと、ウィンドウの右上にBuild LaTeX projectボタンが表示される。押すとpdfが生成される。
4. ウィンドウの右上にView LaTeX PDF fileボタンが表示される。押すと分割タブでpdfが表示される。

    "latex-workshop.latex.tools": [
        {
          "name": "latexmk(uplatex)",
          "command": "latexmk",
          "args": [
            "-f", "-gg", "-synctex=1", "-interaction=nonstopmode", "-file-line-error", "%DOC%"
          ]
        },
    ],
    "latex-workshop.latex.recipes": [
        {
          "name": "upLaTeX",
          "tools": [
            "latexmk(uplatex)"
          ]
        },
    ],
    "latex-workshop.intellisense.package.enabled": true,
    "latex-workshop.latex.autoBuild.run": "never",
    "latex-workshop.latex.clean.fileTypes": [
        "*.aux", "*.bbl", "*.blg", "*.idx", "*.ind", "*.lof", "*.lot", "*.out", "*.toc", "*.acn", "*.acr", "*.alg", "*.glg", "*.glo", "*.gls", "*.ist", "*.fls", "*.log", "*.fdb_latexmk", "*.synctex.gz",
        // for Beamer files
        "_minted*", "*.nav", "*.snm", "*.vrb",
    ],
    "latex-workshop.latex.autoClean.run": "onBuilt",
    "latex-workshop.view.pdf.viewer": "tab",

参考

• 【大学生向け】LaTeX完全導入ガイド Windows編 (2022年) #VSCode - Qiita

座標不変プログラミング

計算機における座標不変性

ディスプレイのピクセルは縦横に並んでいるため、コンピュータ上の位置の指定は最終的にはデカルト座標で行う必要がある。物理シミュレーションのライブラリでも物体の運動はデカルト座標で指定するのが普通だ。しかしながら高レイヤ側では座標系をハードウェアに依存せず自由に取れる方が好ましい。デカルト座標への変換を与えたらプログラムが自動でデカルト座標での値を求めるようにしたい。

ハミルトン力学

ハミルトン形式の解析力学によれば、一般化座標、一般化運動量、ハミルトニアンに対して、正準方程式

が成り立つ。ハミルトニアンの偏微分が求められれば座標と運動量の時間微分が分かるので、適当に前進オイラー法で一般化座標と一般化運動量を求めた上でデカルト座標に変換する。このようにすることで座標に依存しないプログラムが可能となる。

つまり、簡単のため2次元で考えると、予めユーザーが与える情報は

1. 座標変換
2. デカルト座標系におけるハミルトニアン

であり、プログラムが実行する内容は

1. 座標変換によりデカルト座標のハミルトニアンを一般化座標のハミルトニアンに変換。
2. ハミルトニアンの偏微分を計算することで、一般化座標と一般化運動量の時間微分を計算。
3. 前進オイラー法で各時刻のを求める。
4. 座標変換から各時刻のを求め、描画ライブラリに渡す。

である。

2, 3, 4については、変数を計算グラフのノードで表し、記号微分と評価を行えば良い。1については、は自明にで表現できるので、がで表現可能か考える。

との関係を導く。一般化運動量はラグランジアンを用いて

と定義される。デカルト座標における運動量は

ここで

なので

つまり

ヤコビアンは座標変換から記号微分によって計算可能であり、をで表すことができる。

実装

例として単振り子の物理シミュレーションをHaskellで実装する。

まず計算グラフのノードを定義して、値を評価する関数evalと微分を計算する関数diffを実装。

data Node = Num Float
          | Var String
          | Add Node Node
          | Sub Node Node
          | Mul Node Node
          | Div Node Node
          | Pow Node Int
          | Neg Node
          | Exp Node
          | Log Node
          | Sin Node
          | Cos Node
          | Tan Node

eval :: Map.Map String Float -> Node -> Float
diff :: Node -> String -> Node

evalの第一引数は系の状態（一般化座標/運動量）を変数名と値の対応として表す。

次に上で示したように、座標変換を定義し、一般化座標/運動量からデカルト座標における運動量を計算。

    -- coodinate transformation
    let x = q1 * cos q2
        y = q1 * sin q2

    let a11 = diff x "q1"
        a12 = diff x "q2"
        a21 = diff y "q1"
        a22 = diff y "q2"

    let det = a11 * a22 - a12 * a21

    let b11 = a22 / det
        b12 = -a12 / det
        b21 = -a21 / det
        b22 = a11 / det

    let px = p1 * b11 + p2 * b21
        py = p1 * b12 + p2 * b22

単振り子のハミルトニアンを定義し、正準方程式から状態の時間微分を求める。

    -- Hamiltonian in Cartesian coodinate
    let h = (px /\ 2 + py /\ 2) / (2 * m) + m * g * y

    -- Euler method
    let dotq1 = diff h "p1"
        dotq2 = diff h "p2"
        dotp1 = - diff h "q1"
        dotp2 = - diff h "q2"

前進オイラー法で現在の状態から次の状態を計算する関数を定義。単振り子の場合は張力によって半径が一定になる拘束条件があるので、q1の更新をコメントアウトしている。

type Model = Map.Map String Float

eulerMethod :: (Node, Node, Node, Node) -> Float -> Model -> Model
eulerMethod (dotq1, dotq2, dotp1, dotp2) dt (state) = do
    let q1 = state Map.! "q1"
        q2 = state Map.! "q2"
        p1 = state Map.! "p1"
        p2 = state Map.! "p2"

    let q1Next = q1 -- + eval state dotq1 * dt
        q2Next = q2 + eval state dotq2 * dt
        p1Next = p1 + eval state dotp1 * dt
        p2Next = p2 + eval state dotp2 * dt

    let stateNext = Map.insert "q1" q1Next . Map.insert "q2" q2Next . Map.insert "p1" p1Next . Map.insert "p2" p2Next $ state

    stateNext

最後に初期条件と描画関数を与えてglossでアニメーションさせる。

-- initial model
    let initModel = Map.fromList [("q1", 150), ("q2", -pi / 3), ("p1", 0), ("p2", 0)]

    simulate window white 24 initModel (draw (x, y)) (\_ -> eulerMethod (dotq1, dotq2, dotp1, dotp2))

動いた（精度が悪いのか振れ幅が少しずつ大きくなっている）。

単振り子 pic.twitter.com/oDx8dEqSeE

— season (@season1618) 2023年6月14日

先行研究

あった...

• hamilton: Physics on generalized coordinate systems using Hamiltonian Mechanics and AD: ハミルトン力学と自動微分を用いた一般化座標系上の物理演算ライブラリ
• gloss: 動かして遊んで学ぶHaskell - Qiita: hamilton + glossを使った二重振り子のシミュレーション

手順は

1. 一般化座標とそのデカルト座標への変換を与える。
2. デカルト座標でのポテンシャルエネルギーの表示を与える。

で全く同じですね。。。大部分完成した段階で見つけてしまったのでめっちゃ萎えた。そう...ラグランジュ形式だと無理なのでハミルトン形式でやる必要があって...Haskellで書きたくなるよね...いやーその通りです。基本的に作りたいものとかない人間なんですが、今回は物理×情報で双方の知見がバランス良く役に立つ題材（そんな題材めったに思い付かないだろう）で結構テンション上がってたのであ～って感じですね。まあそりゃあるか...って感じだけど。

やる気なくなったのであんまりリファクタリングしてません笑。

github.com

2022年度の読書記録

『ハイパフォーマンスWebサイト』

3月にWeb Speed Hackathonに出ていてWebサイトの高速化に興味があった。

『可視化の技術と現代幾何学』

CGで用いられる離散微分幾何学とかトゥーンシェーディングなど。微分方程式を解の性質を変えずに離散化するという話が面白かった。

『講座心理学11 精神発達』

発達心理学。人の知性がどのような段階を経て発達するか。ピアジェの発達段階説とか。

『西洋建築様式史（上・下）』

建築系の西洋建築史が取れなかったので借りてきた。

『新幾何学思想史』

非ユークリッド幾何学が成立する前後の歴史を当時の数学者達の手紙などから明らかにする。面白い。ガウスやロバチェフスキーが少し前に発表されたカントの空間概念にかなり言及していた。カントが空間は先験的だと主張しているのに対して二人は経験的な概念であると考えていたのが現代的で興味深かった。リーマンが「幾何学の基礎をなす仮説について」という講演をしたのもそれなりの背景があったということらしい。数学者も当然のように物理や哲学に通じているのでやはりここは切り離せないなあと思った。

『チューリングの大聖堂 コンピュータの創造とデジタル世界の到来』

主にプリンストン高等研究所で進められた電子計算機開発プロジェクトについて詳しく書かれている。チューリングというよりノイマンが中心的な人物となる。

『近代建築史』五十嵐太郎、横手義洋

日本の近現代建築にも触れられている。

『デザイン的思考 つまようじからロゴマークまで』

デザインに興味があって読んだ。が、デザインそのものの話はほぼなかった。

『アルゴリズミック・アーキテクチュア』

建築におけるアルゴリズミックデザインの話。著者の一人の講演を以前視聴したことがあって興味があった。

www.youtube.com

『ウェブデザインの思考法 機能性と情緒性で導く論理的なウェブデザインの方針立案・構築』

『方法序説』ルネ・デカルト

哲学Bで心脳問題を扱ったときにデカルトが出てきたので読んだ。コギト・エルゴ・スムや神の存在証明など。

『省察』ルネ・デカルト

『方法序説』の内容に加えて心身二元論について。

『岩波講座ソフトウェア科学5 プログラミング言語処理系』

Cコンパイラを作るときの参考として。コンパイラだけでなくインタプリタにも触れている。

『ベンヤミン・コレクション1 近代の意味』

『複製技術時代の芸術作品』のみ。技術的複製が芸術作品の在り方を変えたという話だった。

『ジェネラティブ・アート Processingによる実践ガイド』

ほとんどProcessingの話であまり得るものはなかった。

『西洋美学史』

『コンピュータグラフィックス』

CGにまた興味が出たので勉強してた。

『CG Magic：レンダリング』

単に手法を示すだけでなく、物理としてどのような理屈を持ってモデル化されるかに言及している。

『集合・位相入門』松坂和夫

位相をちゃんとやろうと思った。

『四季 春』森博嗣

四季シリーズ第一作。なんかふわっとしてる。

『四季 夏』森博嗣

四季シリーズ第二作。『春』よりは分かりやすかった。

『脳はいかに意識をつくるのか 脳の異常から心の謎に迫る』

『コンピュータには何ができないか 哲学的人工知能批判』

人工知能の授業で紹介されていた。知性は形式的には記述できずデジタルコンピュータによって再現できないという結論だった。

『すべてがFになる』森博嗣

再読。

『ビューティフル・マインド 天才数学者の絶望と奇跡』

ノーベル経済学賞を受賞した数学者ジョン・ナッシュの半生を描いた作品。映画を小学か中学の時に見たことがある。

『多様体の基礎』松本幸夫

松本多様体。丁寧に書かれている。良書とされている本はやっぱり分かりやすいと思った。

『微分形式の理論 およびその物理科学への応用』

座標に依らない接ベクトルの定義から が基底となることの証明が載ってた。

『ラ・ロシュフコー箴言集』

箴言は格言・名言のこと。よう実のサブタイトルで何回か引用されてる。

『意志と表象としての世界 正編I』アルトゥール・ショーペンハウアー

時空をア・プリオリな直観と考えているのはカントと同じ。一方で出版された時期が非ユークリッド幾何学の発見された時代と重なるのは興味深い。

『皇帝の新しい心 コンピュータ・心・物理法則』ロジャー・ペンローズ

これも人工知能も授業で紹介されていた。

『C++の設計と進化』ビャーネ・ストロウストラップ

言語の様々な機能とそれが導入された理由に興味があった。途中まで。

『アルゴリズムの自動微分と応用』

自動微分の数値計算への応用など。

『プログラミング言語の基礎概念』

『型システム入門 プログラミング言語と型の理論』

TaPLとして知られる型理論/型システムの本。単純型、部分型、再帰型、多相性の型安全性や型推論、実装など。型システムはプログラムを安全にする手段の一つに過ぎないと思っていたけど、例外処理やオブジェクト、モジュールシステムと深く関わっているという印象を受けた。

『フレーゲ・デデキント・ペアノを読む 現代における自然数論の成立』

科学史Bの中間レポートで数理論理学の歴史について書くことにしたので参考文献として。自然数論の歴史だが論理学とも関連が深い。

『ゲーデルと20世紀の論理学 1ゲーデルの20世紀』

上と同じ。論理に関する哲学的な議論が面白い。

『記号と再帰 記号論の形式・プログラムの必然』

記号論の二つの形式が関数型とオブジェクト指向のプログラミングパラダイムに対応するという話。強引な部分もある気がした。メタプログラミングの話は面白かった。

『現代の量子力学(上)』J・J・サクライ

物理学系の量子力学IIを受けいていたので借りた。3章の角運動量の理論が面白い。

『量子論の基礎 その本質のやさしい理解のために』清水明

清水量子論。量子論の立場がいくつかあることを説明した上で一般性を失わない記述をしているのでありがたい。基本的な五つの要請から始めていて、細かい部分で主張を明示しているのも分かりやすかった。量子論に限らず物理学一般のスタイルを知ることができる。

『貴嶋先生の静かな世界』森博嗣

主人公の大学院生が貴嶋先生の下で研究の世界にのめり込んでいく物語。

『量子力学における群論的方法』

水素原子のシュレーディンガー方程式の解を求めるときに変数分離する根拠が気になっていた時に見つけた。

『相対論とゲージ場の古典論を読み解く』

相対論とかゲージ対称性について軽く復習できる薄めの本。

『プログラミングTypeScript スケールするアプリケーション開発』

軽く読んだだけ。自分にとって新しい言語機能はあまりなかった。

『デュシャンは語る』マルセル・デュシャン

芸術Bでデュシャンの話が出てきたので期末レポートの参考文献がてら読んでた。芸術家の創造性についての話など。半分くらいで飽きた。

『科学と仮説』アンリ・ポアンカレ

これも芸術Bでキュビズムの画家が良く読んでいた本として取り上げられていた。初版は1902年で相対論が発表される前だが、現実の空間が非ユークリッドである可能性について言及している。対象を目で追うときの筋肉感覚が成す群から三次元の観念を獲得する、という話をしていて面白かった。

『固有値問題30講』

量子力学に出てくるエルミート作用素の固有値問題を真面目に勉強しようと思った。

『Haskell入門 関数型プログラミング言語の基礎と実践』

モナドとかの話は全然理解してない。

『日本語組版入門 その構造とアルゴリズム』

組版に興味があった。組版処理はかなり複雑なことをやっているのだなあと知った。

『数式組版』

筆者の組版に対する意識の高さが窺えた。構文の曖昧さによって回避しきれない誤読の可能性を微妙な書体やスペースの使い分けによって極限まで排除しようということらしい。人間の複雑な美的感覚を大量の記号分類と配置規則によって手懐けている、という印象を受けた。

『関数解析』

関数解析は高校の時に図書館の本で勉強したはずだが、成人式で実家に帰ったときに当時のメモを見つけることができなかったのでもう一度勉強することにした。

『ヒューマンコンピュータインタラクション入門』

なんというか体系化されない知識の集合。

『量子力学の数学的基礎』ジョン・フォン・ノイマン

量子力学に数学的な基礎付けを与えた古典。数学書のスタイルで書いていそうなタイトルだが、定理を本文から独立させる書き方をしていたのは2章くらいで、他は普通に物理の本という感じだった。エルミート作用素の固有値問題に関して命題を明示していたのは助かった。それ以外は昔の本ということで読みやすくはなかったので読んでない。

『計算機プログラムの構造と解釈』

魔術師本や紫本として知られる計算機科学の古典。Schemeのコンパイラを書こうと思って読んでいたLispを実装したくなったら読んでほしい本６選 - Arantium Maestumの中で取り上げられていた。情報工学系の関数型プログラミング基礎の参考書に上げられていたもので内容もほぼ同じだった。

modern compiler implementation in Java

Tiger Bookとして有名なコンパイラの教科書らしい。日本語だと『最新コンパイラ構成技法』。Haskell コンパイラを書こう！で知った。"in C"と"in ML"もあるが内容は同じらしい。東工大図書館では訳書が無く、電子本として"in ML"、物理本として"in Java"があった。洋書をある程度読んだのはこれが初めて。

関数型言語のコンパイラに言及しているコンパイラの本は探してみるとあまり多くない。第二部で関数型言語についての章があり、クロージャ変換やインライン展開、末尾呼び出し最適化などを扱っている。が、実装についてはあまり触れられていない。

『笑わない数学者』森博嗣

S&Mシリーズ第三作。オリオン像のトリックは分かったけど事件の方は分からなかった。算数の問題も面白かった。

【React + TypeScript】コードエディタとASTビュアーを作る

• [2024/2/24]: 追記・コード修正

Lispコードを書くと抽象構文木を表示してくれるWebアプリをReactで作った（正確には計算グラフとかProgram Dependence Graphというべき）。

Lispの構文木を表示してくれるWebアプリhttps://t.co/gc4bJ1u8Ughttps://t.co/AoFbQEfydKhttps://t.co/z4dGCb1n5H pic.twitter.com/384cz1W4t0

— season (@season1618) 2023年3月30日

github.com season1618.github.io

ReactもTypeScriptもまともに使ったことがないのでもっと良い書き方があるかもしれない。

構成

画面の左半分にエディタを置いて、右半分にCanvasを置いた。useContextで構文木を共有して、コードが変更されたときに右のViewも変更されるようにする。

function App() {
  const [node, setNode] = useState<Node | undefined>(initNode);

  return (
    <div id="app">
      <nav><h2>Lisp Syntax Viewer</h2></nav>
      <div id="flex">
        <NodeContext.Provider value={[node, setNode]}>
          <CodeEditor /><Canvas />
        </NodeContext.Provider>
      </div>
    </div>
  );
}

構文木を保持する変数nodeと更新関数であるsetNodeの両方を共有することになる。setNodeの型はエディタではReact.Dispatch<React.SetStateAction<Node | undefined>>と表示されているが、createContextで生成するときの型注釈は単に(node: Node | undefined) => voidで良いらしい（よく分からない）。

const initNode: Node | undefined = undefined;
export const NodeContext = createContext<[Node | undefined, (node: Node | undefined) => void]>([initNode, (node: Node | undefined) => {}])

コードエディタ

スタイル

<textarea>でやる。

• white-space: nowrap;で横スクロールが可能。
• textarea:focus { outline: 0; }でフォーカスが当たったときに輪郭が強調されるのをoffにする。
• textarea::selectionでテキストが選択されたときのスタイルを制御。

補完

基本的にはテキストが変更されたらそのまま反映すれば良い。デフォルトではTabキーでフォーカスが移ってしまうので、e.preventDefault()でフォーカスが移るのを防ぐ。

  return (
    <div id="editor">
      <textarea
        value={code}
        onChange={
          (e) => {
            format(e.target.selectionStart, e.target.value);
          }
        }
        onKeyDown={
          (e) => {
            if (e.key === 'Tab') {
              e.preventDefault();
              const target = e.target as HTMLTextAreaElement;
              formatTab(target.selectionStart);
            }
          }
        }
      />
    </div>
  );

カーソルの位置はHTMLTextAreaElementからセットする。

  let target: HTMLTextAreaElement;

  useEffect(
    () => {
      target = document.querySelector('textarea') as HTMLTextAreaElement;
    }
  );

  useEffect(
    () => {
      target.focus();
      target.setSelectionRange(cursorPos, cursorPos);
    },
    [cursorPos]
  );

その他、開き括弧が入力されたら閉じ括弧を補完する、引用符が入力されたらもう一個加えるなどの処理を行う。

  function format(pos: number, nextCode: string) {
    pos -= 1;
    if (code.length < nextCode.length) {
      switch (nextCode[pos]) {
        case '(':
          nextCode = nextCode.substring(0, pos + 1) + ')' + nextCode.substring(pos + 1, nextCode.length);
          break;
        case ')':
          if (pos + 1 < nextCode.length && nextCode[pos + 1] === ')') nextCode = code;
          break;
        case '\'':
          if (pos + 1 < nextCode.length && nextCode[pos + 1] === '\'') nextCode = code;
          else nextCode = nextCode.substring(0, pos + 1) + '\'' + nextCode.substring(pos + 1, nextCode.length);
          break;
      }
    }
    setCode(nextCode);
    setCursorPos(pos + 1);
  }

構文解析

TypeScriptにはunion型があるが、タグ無しなのでパターンマッチがなくkindメンバで場合分けして処理した。Callは関数適用、Primは定数やシンボルなどのprimaryノード、Varは変数で式を保持する。

export type Ast = Expr;
export type Expr = Call | Prim | Var;

基本的には通常の構文解析と同じだが、構文木を描画する関係で必要なデータを予め求めておく。この手のアプリケーションはレイアウトのアルゴリズムを考えるのと実装するのが一番大変。

depthは構文木の深さで、Canvas上でのノードのy座標を保持する。offsetはx座標を保持する。depthは深さ優先探索で根から順番に求めていける。ただし変数は複数参照されるので最大値を取る。offsetはdepthが決定した後にまとめて計算する。OffsetTableを用意しておき、depthごとに現在使われているものの最大値 + 1とそれぞれのノードに最適な位置(Callなら引数のoffsetの平均)のうち、大きい方を採用する。

  calcOffset(depth: number, offset: number = -1): number {
    if (!(depth in this.table)) {
      this.table[depth] = new Set();
    }
    let maxOffset = Math.max(-1, ...this.table[depth]);
    let finOffset = Math.max(maxOffset + 1, offset);
    this.table[depth].add(finOffset);
    return finOffset;
  }

ASTビュアー

構文木の描画(2024/2/24追記)

変数は複数のノードから参照されるので木構造ではないが、自分より深さが1小さいノードの一つを親として考える。構文木の描画はそのような木の描画として行う。木の描画はReingold-Tilfordアルゴリズムを用いる。

• Tidier Drawings of Trees: Reingold-Tilfordアルゴリズムの論文。
• Drawing Presentable Trees: 木構造を描画するアルゴリズムの歴史と解説。
• DRAWING TREES FUNCTIONALLY: REINGOLD AND TILFORD, 1981: Reingold-Tilfordアルゴリズムの解説とHaskell実装。

まずASTから描画するための座標などを保持するデータ構造に変換する。

class Node {
  label: string;
  shift: number; // 兄弟部分木と間隔を取るためのシフト量
  offset: number; // 最左兄弟ノードに対する相対座標 -> 絶対座標
  depth: number; // 深さ
  childs: Node[]; // DAGの隣接ノード
  belows: Node[]; // 木構造としての子ノード
  thread: Node | null; // Reingold-Tilfordアルゴリズムで用いる、木上の探索を効率化するためのポインタ

  visited: boolean;
  havePar: boolean;

  ...
}

ノードの深さは根からの最長距離になる。無駄な計算を省くためトポロジカル順序で更新する。

calcDepth() {
  const torder = this.tsortReverse().reverse();
  for (const node of torder) {
    for (const child of node.childs) {
      child.depth = Math.max(child.depth, node.depth + 1);
    }
  }
}

再帰的な処理を行うため、childsとは別に木構造としての子要素の配列belowsを求めておく。つまりbelowsを辿って再帰すると木上をDFSできる。条件は深さが自ノードより1大きいかつ親が決まっていないこと。

calcBelows() {
  for (const node of this.childs) {
    if (this.depth + 1 === node.depth && !node.havePar) {
      this.belows.push(node);
      node.havePar = true;
      node.calcBelows();
    }
  }
}

calcOffsetで最左兄弟ノードに対する相対座標を決定し、calcAbsoluteで絶対座標を算出する(offsetを使いまわす)。 最後に描画を行う。childsを辿って辺を描画し、belowsを辿って再帰。

function draw(node: Node, originX: number, originY: number) {
  let x = originX + width * node.offset;
  let y = originY + height * node.depth;
  drawNode(x, y, node.label);

  node.childs.forEach((child, index) => {
    let x1 = x + (index + 1) / (node.childs.length + 1) * 2 * r - r;
    let y1 = y + r;
    let x2 = originX + width * child.offset;
    let y2 = originY + height * child.depth - r;
    drawArrow(x1, y1, x2, y2);
  });

  node.belows.forEach((below) => {
    draw(below, originX, originY);
  });
}

有向辺は3次ベジェ曲線で描いている。やっぱり構文木の辺はベジェ曲線にするのがかっこいい。

function drawArrow(x1: number, y1: number, x2: number, y2: number) {
  context.beginPath();

  context.moveTo(x1, y1);
  context.lineTo(x1 - s, y1 + Math.sqrt(3) * s);
  context.lineTo(x1 + s, y1 + Math.sqrt(3) * s);
  context.closePath();
  context.fill();

  context.bezierCurveTo(x1, (y1 + y2) / 2, x2, (y1 + y2) / 2, x2, y2);
  context.stroke();
}

Canvasのマウス操作

season1618.hatenablog.jp

GitHub Pages

npm run buildするとbuildディレクトリ以下に生成物ができる。ディレクトリ名をdocsに変更した上でgithub pagesを設定。そのままだとindex.htmlでファイルのリンクが/...となってFailed to load resourceと出るので、package.jsonに"homepage": "."を追加。

参考文献

• React.jsで、textarea上でTabキーを押したときにスペースを入力する - Qiita: クラスコンポーネントによる方法。関数コンポーネントでやる場合はuseEffectを使えば良い。
• ReactでCanvasを使う - Qiita
• 【React + Typescript】useContext の値を子コンポーネントから更新 - Qiita
• Create React Appで作成したReact ApplicationをGitHub Pagesで公開する - プログラミング勉強記録
• npxでReactアプリを作成し，npm run buildでビルドしたが，build/index.htmlでパスのエラーが生じる

マウス操作によるCanvasの平行移動と拡大縮小

コード

function Canvas() {
  const [mousePressed, setMousePressed] = useState(false);
  const [mousePos, setMousePos] = useState({ x: 0, y: 0 });
  const [origin, setOrigin] = useState({ x: 0, y: 0 });
  const [logScale, setLogScale] = useState(0);

  function translateCanvas(x: number, y: number) {
    if (mousePressed) {
      setOrigin({ x: origin.x + x - mousePos.x, y: origin.y + y - mousePos.y });
    }
    setMousePos({ x, y });
  }

  function scaleCanvas(delta: number) {
    let nextX = mousePos.x + Math.pow(1.1, delta/100) * (origin.x - mousePos.x);
    let nextY = mousePos.y + Math.pow(1.1, delta/100) * (origin.y - mousePos.y);
    let nextLogScale = logScale + delta / 100;
    if (-50 < nextLogScale && nextLogScale < 50) {
      setOrigin({ x: nextX, y: nextY });
      setLogScale(nextLogScale);
    }
  }

  useEffect(
    () => {
      const canvas = document.querySelector('canvas') as HTMLCanvasElement;
      const context = canvas.getContext('2d') as CanvasRenderingContext2D;
      
      context.resetTransform();
      context.clearRect(0, 0, canvas.width, canvas.height);
      context.translate(origin.x, origin.y);
      context.scale(Math.pow(1.1, logScale), Math.pow(1.1, logScale));

      // 描画
    },
    [origin, logScale]
  );

  return (
    <canvas
      onMouseDown={(e) => setMousePressed(true)}
      onMouseUp={(e) => setMousePressed(false)}
      onMouseMove={
        (e) => {
          let target = e.currentTarget.getBoundingClientRect();
          translateCanvas(e.clientX - target.left, e.clientY - target.top);
        }
      }
      onWheel={(e) => scaleCanvas(-e.deltaY)}
    ></canvas>
  )
}

export default Canvas;

方針

Canvasの原点の位置originとlogスケールlogScaleを持って置く。拡大率はホイールの回転数について指数関数にしておくと滑らかになる気がするのでlogスケールで管理する。useEffectを使って、originとlogScaleが変更されたら再描画させる。

  const [origin, setOrigin] = useState({ x: 0, y: 0 });
  const [logScale, setLogScale] = useState(0);

変換の順番に注意する。原点を移動した上でスケールを変更する。

  useEffect(
    () => {
      const canvas = document.querySelector('canvas') as HTMLCanvasElement;
      const context = canvas.getContext('2d') as CanvasRenderingContext2D;
      
      context.resetTransform();
      context.clearRect(0, 0, canvas.width, canvas.height);
      context.translate(origin.x, origin.y);
      context.scale(Math.pow(1.1, logScale), Math.pow(1.1, logScale));

      // 描画
    },
    [origin, logScale]
  );

ドラッグで平行移動

現在マウスが押されているかをmousePressedで管理。マウスが押されている状態でMouseMoveが発生したら、Canvasの原点に現在のマウスの位置と直前の位置の差分を足し込む。

  function translateCanvas(x: number, y: number) {
    if (mousePressed) {
      setOrigin({ x: origin.x + x - mousePos.x, y: origin.y + y - mousePos.y });
    }
    setMousePos({ x, y });
  }

ホイールで拡大縮小

マウスの位置を中心に拡大縮小する。Canvasの原点は、現在のマウスの位置と原点の差を拡大縮小した上で元の座標に足す。logスケールは単純に足す。

  function scaleCanvas(delta: number) {
    let nextX = mousePos.x + Math.pow(1.1, delta/100) * (origin.x - mousePos.x);
    let nextY = mousePos.y + Math.pow(1.1, delta/100) * (origin.y - mousePos.y);
    let nextLogScale = logScale + delta / 100;
    if (-50 < nextLogScale && nextLogScale < 50) {
      setOrigin({ x: nextX, y: nextY });
      setLogScale(nextLogScale);
    }
  }

関数型言語の特徴

ガベージコレクション

多くの関数型言語ではリストが基本的なデータ構造となる。純粋な関数型言語では再束縛が不可となるので、forループで配列を扱うことはできず、リストを使って再帰関数で処理するのが基本となる。リストが関数の引数や返り値となるため、計算量的な事情からリストを指すポインタのみをやり取りする。関数内で宣言されたリストも返り値となるのでスタック領域ではなくヒープ領域に確保することになる。

ガベージコレクションはLISPが発表された1960年の論文Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part Iで初めて提案された。論文の4 The LISP Programming SystemではレジスタマシンにおけるLISPの実装について検討している。

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

Registers can be put back on the free-storage list when they are no longer needed. Even one register returned to the list is of value, but if expressions are stored linearly, it is difficult to make use of blocks of registers of odd sizes that may become available.

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

When the contents of a base register are changed, it may happen that the register to which the base register formerly pointed cannot be reached by a car − cdr chain from any base register. Such a register may be considered abandoned by the program because its contents can no longer be found by any possible program; hence its contents are no longer of interest, and so we would like to have it back on the free-storage list.

Lispでヒープアロケーションを多用することからガベージコレクションが導入されたらしい。

またクロージャを実装する手段の一つとしてもヒープアロケーションが使われる。

Closure (computer programming) - Wikipedia)

A language implementation cannot easily support full closures if its run-time memory model allocates all automatic variables on a linear stack. In such languages, a function's automatic local variables are deallocated when the function returns. However, a closure requires that the free variables it references survive the enclosing function's execution. Therefore, those variables must be allocated so that they persist until no longer needed, typically via heap allocation, rather than on the stack, and their lifetime must be managed so they survive until all closures referencing them are no longer in use.

This explains why, typically, languages that natively support closures also use garbage collection.

遅延評価

関数型言語では経時的に変化するようなオブジェクトを無限長リスト（ストリーム）で表現することがある。ストリームで表現することで状態をなくすことができる。粒子の状態をと定義すればそれは時刻によって変化するが、状態をの無限長リスト（世界線）で表現すれば状態は変化しない。その場合、将来のは分からないので評価を遅らせる必要が出てくる。また関数が参照透過なら引数の評価タイミングを任意にできるので遅延評価で無駄な計算を削減できる。Schemeはデフォルトで正格評価だけど遅延評価を利用することもできる。

関数型言語の分類

非純粋なら引数の評価タイミングが意味を持ってしまうので遅延評価は困難。動的型付けの純粋関数型言語として純Lispなどがあるがあまり多くないらしい。したがって関数型言語のパターンとして多いのは(静的，純粋，正格)，(静的，純粋，遅延)，(静的，非純粋，正格)，(動的，非純粋，正格)の四つ。属性の組合せごとに一個ずつ触れておくと良いかもしれない。

言語	型付け	純粋性	評価戦略
Idris	静的	純粋	正格
Haskell	静的	純粋	遅延
ML	静的	非純粋	正格
OCaml	静的	非純粋	正格
F#	静的	非純粋	正格
Scala	静的	非純粋	正格
Lisp	動的	非純粋	正格
Scheme	動的	非純粋	正格
Clojure	動的	非純粋	正格

遅延評価フラクタル

以前Haskellの遅延評価で良い感じにフラクタルが描けないかなあと思ったことがあって、最近Haskellの本読んでたのでやった。

github.com

gloss

2Dグラフィクスライブラリは適当にglossを選んだ。以下を参考にした。

• gloss: Painless 2D vector graphics, animations and simulations.
• glossではじめるグラフィック描画 :: Haskell入門の次に読む記事 - Qiita

stack exec lazy-fractal-exeするときにuser error (unknown GLUT entry glutInit)と出たので、

Haskell with OpenGL. (Unknown GLUT entry glutInit) - Stack Overflow

に従ってfreeglut/bin/x64/freeglut.dllを.stack-work/install/hoge/bin/にコピーしてglut32.dllにrenameしたら動いた。

フラクタルの描画

シェルピンスキーのギャスケットを描く。遅延評価を使えば無限長のリストが定義できるので、解像度を明示することなくフラクタル図形を表現可能だ。

30行しかないので読んだ方が早い。

gasketは三角形からなる無限長のリストを返す。一番外側の三角形の頂点を$a, b ,c$、それぞれの対辺の中点を$midA, midB, midC$として、再帰呼び出しして良い感じにマージする。takeGasketはフラクタルの粒度と全体のサイズを引数として、無限長のリストの先頭から相当する要素を抜き出す。

mid :: Point -> Point -> Point
mid a b = do
    let (x1, y1) = a
    let (x2, y2) = b
    ((x1 + x2) / 2, (y1 + y2) / 2)

mix :: [a] -> [a] -> [a] -> [a]
mix [] [] [] = []
mix x y z = (head x) : (head y) : (head z) : mix (tail x) (tail y) (tail z)

triangle :: Point -> Point -> Point -> Picture
triangle a b c = line [a, b, c, a]

gasket :: Point -> Point -> Point -> [Picture]
gasket a b c = do
    let midA = mid b c
    let midB = mid c a
    let midC = mid a b

    let subA = gasket    a midC midB
    let subB = gasket midC    b midA
    let subC = gasket midB midA    c
    
    (triangle a b c) : (mix subA subB subC)

takeGasket :: Int -> Float -> [Picture]
takeGasket level len = do
    let num = sum [3^x | x <- [0..level]]
    take num (gasket (-len / 2, 0) (len / 2, 0) (0, len * sqrt 3 / 2))

あとはpicturesに渡してウィンドウを作るだけ。

main :: IO ()
main = display window white (pictures (takeGasket 10 300))

本当は宣言的(図形Aを、Aを半分に縮小したものを三つ集めたものとして記述)に書きたかったけど、その場合レベルを明示しないとそもそも形が定まらない可能性があり難しい。よって操作的(レベル$n$のフラクタルに付加してレベル$n+1$のフラクタルを描く)に書くしかない。コッホ雪片などは、曲線に関しては外形が定まらないため削除命令を追加するか、内部の図形に関しては突起を追加するように描けるので内と外で色を分けるなどの工夫が必要になる。