カテゴリー: Haskell

素数夜曲とこれまでの内容

素数夜曲

これまでの内容

• 素数夜曲とプログラミング Scheme, Python, Haskell 第 1 回

B.2 名前と手続き

リストの一番左は特別: そこには手続きを置く.
命名と抽象化について割といいことが書いてある気がする.

太字で強調してあるところがあって,
何となく大事そうだからこちらにも書かせてもらおう.

プログラミングは命令的知識を扱い, 数学は宣言的知識を扱う.

命令的というのは「如何にして為すか」という意味で,
宣言的というのは「何であるか」という意味.

B.2.1 関数の定義

素数夜曲では「函数」と書いているがめんどいので関数と書くことにする.
いわゆるラムダの話から入る.
次の関数は $f(x) = x^2$ だ.
ラムダで書くと $\lambda x.x^2$.

ラムダ以外の書き方もあるがとりあえず本の順に沿って書いていこう.

(lambda (x) (* x x))
(write ((lambda (x) (* x x)) 5))

RESULT

25

一次関数 $x \mapsto ax + b$ は Scheme だと次のように書く.

(lambda (a) (lambda (b) (lambda (x) (+ (* a x) b))))
(write ((((lambda (a) (lambda (b) (lambda (x)
                                    (+ (* a x) b))))
          2) 3) 5))

RESULT

13

こんな鬱陶しいのは嫌だ.
LISP が嫌いになる理由として括弧が挙げられる理由を強く感じる.
慣れるとむしろ便利なくらいと聞くが道は遠い.

何はともあれもう少し簡単な書き方がラムダレベルでもあるし Scheme にもある.
$\lambda abx.ax+b$ で, Scheme は次の通り.

((lambda (a b x)
   (+ (* a x) b))
 2 3 5)

(write ((lambda (a b x)
          (+ (* a x) b))
        2 3 5))

RESULT

13

素数夜曲でいつ出てくるのかわからないが,
大分長いこと lambda をひっぱるようだ.
鬱陶しいので適当に検索してきて lambda 抜きの関数定義を書いておく.

(define (hello name)
  (string-append "Hello " name "!"))
(write (hello "World"))

RESULT

"Hello World!"

Python の lambda

$f(x) = x^2$ を書いてみよう.

myfunc = lambda x: x ** 2
print(myfunc(2))

RESULT

4

普通の関数で書いてみよう.

def f(x):
    return x**2
print(f(2))

RESULT

4

Haskell の lambda

Haskell での lambda は次の通り.

mysquareInt = \x -> x ^ 2
mysquareDouble = \x -> x ** 2

main = do
  print $ mysquareInt 2
  print $ mysquareDouble 2.0

RESULT

4
4.0

JavaScript の lambda

一般的な lambda と無名関数の違いがよくわかっていない.

var f = function(a) { return Math.pow(a, 2) };
console.log(f(3));
var a = (function(a){ return Math.pow(a, 2) })(3);
console.log(a);
console.log((function(a){ return Math.pow(a, 2) })(3));

RESULT

9
9
9

B.2.2 アルファ変換

いわゆる束縛変数の文字を変えるというやつ.

B.3 ラムダ算法

Lambda calculus だし,
たぶんいわゆるラムダ計算なのだろう.
プログラムじたいはないのでばっさり省略.

B.3.3 イータ変換

省略.

B.3.4 ラムダ項の定義

略.

B.3.5 コンビネータ

略.

B.3.6 簡約の戦略

略.

B.4 特殊形式 (special form)

対象に名前をつけてプログラム上のどこからでも使えるようにすることを,
トップレベル定義 (top-level definition) という.

1 次関数を定義する.

(define linear
  (lambda (a b x)
    (+ (* a x) b)))
(write linear)
(newline)
(write (linear 2 3 5))

RESULT

#<procedure linear (a b x)>
13

最後の (linear 2 3 5) は $2 \times 5 + 3$ を計算している.

Lambda を使わない省略記法もあって MIT 記法 という.

(define (linear a b x)
  (+ (* a x) b))
(write linear)
(newline)
(write (linear 2 3 5))

RESULT

#<procedure linear (a b x)>
13

この手の省略記法は糖衣構文 (syntax sugar) と呼ばれる.

トップレベルは対話的入力時のプロンプトに象徴される領域で,
大域環境 (global environment) と呼び,
この環境下で定義された変数を大域変数 (global variable) と呼ぶ.
これと対になるのが局所環境 (local environment),
局所変数 (local variable) だ.

アルファ変換した linear# も書いておこう.

(define (linear# u v w)
  (+ (* u w) v))
(write linear#)
(newline)
(write (linear# 2 3 5))

RESULT

#<procedure #{linear#}# (u v w)>
13

アルファ変換は局所変数を別の文字 (列) に置き換えてもいいとか,
とりあえずそういう雑な理解をしている.
計算機科学的にもっと面倒なところまでカバーしている可能性があり,
そこまで調べていないからいまの理解の雑さは割と真剣に警戒している.

B.4.1 define

用語の定義があるから適当に書いておこう.
対象を挿入する場所 (スロット) は本文と同じくを角括弧 (<>) で書きたいが,
いろいろな事情から隅括弧 ([]) で書くことにする¹.

Lambda 抜きの糖衣構文を使った define の一般形は次の通り.

定義方法: (define ([name] [fps]) [body])
利用方法: ([name] [aps])

本の記述が死ぬほどわかりづらいが,
とりあえず引用しよう.

手続の作用の対象となるのが引数 (parameter, argument) だ.
[fps] は関数内部で使われる仮引数 (formal parameters) の略記で,
[aps] は実際の処理対象である実引数 (actual parameters) の略記.
[body] は任意個数の式 (expression) で構成される手続の本体だ.
Scheme での式はアトムやリテラルを含めて評価値が戻ってくるもの全てを指す.

とりあえずここまでくり返し書いてきた関数定義を.

(define (linear a b x)
  (+ (* a x) b))

linear が [name], [fps] は a, b, x で,
[body] が (+ (* a x) b) だ.
[name] は要は関数の名前,
[fps] は定義した関数の引数,
[body] は関数で実際にやる処理のこと.

よくプログラミングのマニュアルでは上のタイプのよくわからない説明書きがある.
こういうやつ.

array explode ( string $delimiter , string $string [, int $limit = PHP_INT_MAX ] )

こういうのを見たらとりあえず実際にコード片を書いて実行して確認してみた方がいい.
めちゃくちゃ引数がたくさんあってそんなことやっていられないこともよくあるけれども.

Scheme の一般評価規則にしたがわない対象,
つまり特定の対象の評価値を求めないものを特殊形式 (special form),
あるは構文 (syntax) と呼ぶ.

スペシャルフォームと片仮名書きされているのをよく見かける.
ここからは代表的な特殊形式を紹介していくようだ.

一応改めて Python や Haskell での関数定義を書いておこう.

Python での変数・関数定義

まずは変数定義.

a = 1
print(a)

RESULT

1

数を 2 乗する関数を定義する.

def f(x):
    return x ** 2

print(f(2))
print(f(3))

RESULT

4
9

Haskell での変数・関数定義

私が理解している限り, いわゆる変数はない.
定数関数があってそれが定数の役割をしてくれるという理解.

two :: Int
two = 2

main = do
  print two

RESULT

2

こちらは整数を 2 乗する関数を定義する.

mySquare :: Int -> Int
mySquare x = x ^ 2

main = do
  print $ mySquare 2
  print $ mySquare 3

RESULT

4
9

JavaScript の変数・関数定義

use strict がないバージョン.
グローバル変数になるのでよくないと言われるやつ.

a = 2;
console.log(a);

RESULT

2

use strict はどこまで使えるようになっているのだろうか.
use strict をつけると上のキーワードなしの宣言でエラーになる.
次のキーワードはスコープとかの問題で詳しくはこことかで適当に調べる.

"use strict";
var a0 = 1;
console.log(a0);
var a = 2;
console.log(a);
let b = 3;
console.log(b);
const c = 4;
console.log(c);

RESULT

1
2
3
4

略号まとめ

• proc: procedure
• exp: expression
• num: number
• predi: predicate
• func: function
• var: variable
• int: integer
• consq: consequent
• args: argument
• val: value
• str: string
• altna: alternative
• char: character
• obj: object
• lst: list
• stm: stream

引数の有効範囲

変数定義的な意味での define の使い方.
正確には次のように言うべきのようだ.

記憶領域のある場所に a という名前を与え, その場所と値 3.14 を結びつける.

値を参照するラベルが a とかいうやつだろう.

(define a 3.14)
(write a)

RESULT

3.14

define の次の用法の例でもある模様.

定義方法: (define [name] [exp])

次のように読めばいいようだ.

[name] とは [exp] の名前である.

束縛と環境

a を定義したあとなら a を入力してもエラーが出ない.
REPL 的なアレで挙動確認しているわけではないので,
次のコード片では write を使っている.

(define a 3.14)
(write a)

RESULT

3.14

このように変数に束縛された値を確認する方法を変数参照 (variable reference) という.
次の実行結果を見ると a と定数 3.14 が関連づけられていることがわかる.

(define a 3.14)
(write a)
(newline)
(write (* 2 a))

RESULT

3.14
6.28

この a に値を格納するのを束縛 (bind) と呼ぶ.
この束縛情報の全体を環境 (environment) と呼ぶ.

B.4.2 lambda

定義方法: (lambda ([fps]) [body])
利用方法: ((lambda ([fps]) [body]) [aps])

改めてコード例を書いておこう.
数を 2 乗する関数を定義する.

(lambda (x) (* x x))
(write ((lambda (x) (* x x)) 2))

RESULT

4

関数定義の実験として前置記法 (prefix notation) を中置記法や後置記法で書いている.
前置記法について prefix を作っている.

(define prefix
  (lambda (proc a b)
    (proc a b)))
(write (prefix + 2 3))
(newline)
(write (prefix * 2 3))

RESULT

5
6

これを中置記法 (infix notation), 後置記法 (postfix notation) で書く.

(define infix
  (lambda (a proc b)
    (proc a b)))
(write (infix 2 + 3))
(newline)

RESULT

5

(define postfix
  (lambda (a b proc)
    (proc a b)))
(write (postfix 2 3 +))

RESULT

5

Python, Haskell, JavaScript のコード例はいらないだろう.

ブロック構造

手続の評価値は内部の最後の式で決まる.

(define (linear x)
  (define a 2)
  (define b 3)
  (+ (* a x) b))
(write (linear 5))
(newline)

RESULT

13

次の式では最後の (* a b) の結果が返る.

(define (linear1 x)
  (define a 2)
  (define b 3)
  (+ (* a x) b)
  (* a b))
(write (linear1 3))

RESULT

6

関数内部で定義した変数は外で参照できない.
a は関数の中で定義されているだけでトップレベルで定義されていないから,
関数の外で呼ぼうとするとエラーになる.

次のコードを org-babel で実行するとエラーになる.
よくわからないが guile -s で実行した結果を貼っておこう.

(define a 3.14)
(write a)
(newline)

(define (linear2 x)
  (define a 2)
  (define b 3)
  (+ (* a x) b)
  (* a b))
(write (linear2 3))
(newline)

(write a)

RESULT

An error occurred.

guile -s での実行結果

3.14
6
3.14

その他の言語

同じようなスコープの問題がある.
JavaScript だとグローバル変数に関する有名な問題がある.
昔は必ず var を使えというのがあった.
最近は var よりも use strict と let, const を使うのがいいのだろうか.
識者のご意見求む.

begin

lambda の持つ列挙機能を含む特殊形式が begin.
式を対象にする限りは同じらしい.
begin だとトップレベル定義になる.

(begin
  (define a 2)
  (define b 3))
(write a)
(newline)
(write b)

上のコード, org-babel で実行できない.
guile -s での実行結果を書いておこう.

guile -s での実行結果

2
3

その他の言語

Python, Haskell, JavaScript で似たようなのがあるだろうか?

今回はこの辺で終わろう.

はじめに: なぜ素数夜曲か

数学・物理学習とプログラミングと絡められないかと試行錯誤している.

数学からの取っつきやすさ,
物理からの取っつきやすさ,
プログラミングからの取っつきやすさをそれぞれ考えないといけない.
ある程度の体系性もほしい.

数学や物理としても面白い内容にしたいし,
プログラミングから見ても意味がある内容にしたい.

どうしたものかとずっと思っていたのだが,
素数という数学のキラーコンテンツとプログラミングを絡めた素数夜曲があった.

微妙なところも多いとは思いつつ,
メインエディタとして Emacs を使っているし,
LISP 系の言語はきちんとやりたいとも思っている.

そんなところでいい感じの落とし所という気がしたので,
少しずつ読み進めつつコードの記録をしていこうと決めた.

数学・物理の数値計算との相性の良さ,
私の勉強してみたさとも合わせて Python や Haskell のコードも書いていけたらいいな,
と思っている.
あと何となく JavaScript もやってみよう.
JavaScript は動きが速すぎて何かやってもすぐに動かなくなりそうで嫌なのだが,
ここでやるくらいのことならそう簡単に陳腐化しないだろうと勝手に信じてやっていこう.

基本的には付録のプログラミングパート,
特に付録 B から記録をつけていく予定だ.

Emacs の org-babel で書いているので,
素数夜曲本編とは見た目ちょっと違うコードを書いていくかもしれない.
Scheme, org-babel ともにあまりよくわかっていないがとりあえず進める.

org-babel の Scheme が標準で Guile を使っていて,
その変更の仕方がわからなかったのでとりあえず Guile を使う.
これまで入れていた Gauche を使いたかったが org-babel が対応していないようだ.
そうでないなら MIT/GNU Scheme が良かった気もするがこれも設定がわからない.

でははじめよう.

出力用関数

(write "write test")
(newline)
(display "display test")

RESULT

"write test"
display test

B.1 評価値を得る

とりあえず Hello, World! で.

(write "Hello, Scheme!")

RESULT

"Hello, Scheme!"

B.1.2 四則計算

基本的な書き方

加減乗除は次の通り.
前置記法なのがポイント.
割り算で分数にしてくれるのは割とポイント高い気がする.

(write (+ 5 3))
(newline)
(write (- 5 3))
(newline)
(write (* 5 3))
(newline)
(write (/ 5 3))

RESULT

8
2
15
5/3

Python

print(5 + 3)
print(-5 + 3)
print(5 * 3)
print(5 / 3)

RESULT

8
-2
15
1.6666666666666667

Haskell

まだ (?) org-babel との相性がよくないっぽい.
ここ を参考にちょっと改造.

Haskell でのあまりの計算には mod を使う.

main = do
  print $ 5 + 3
  print $ -5 + 3
  print $ 5 + 3
  print $ 5 / 3
  print $ mod 5 3
  print $ 5 `mod` 3

RESULT

8
-2
8
1.6666666666666667
2
2

JavaScript

console.log(5 + 3);
console.log((-5 + 3));
console.log(5 * 3);
console.log(5 / 3);

RESULT

8
-2
15
1.6666666666666667

長めの計算をどう書くか

例えば次の式.

\begin{align}
2 \div 3 + 5 \times 7 – 11
\end{align}

Scheme (LISP 系言語) だと括弧で細かく区切っていくから,
演算の優先度みたいな面倒なことをあまり考えなくても済む.

(define a (- (+ (/ 2 3) (* 5 7)) 11))
(write a)

RESULT

74/3

Python

Python だと普通に書く.

a = 2 / 3 + 5 * 7 - 11
print(a)

RESULT

24.666666666666664

Haskell

Python っぽくも Scheme っぽくも書ける.
演算子を括弧でくくると Scheme のように演算子を前に置けるから.

main = do
  print $ 2 / 3 + 5 * 7 - 11
  print $ (-) ((+) ((/) 2 3) ((*) 5 7)) 11

RESULT

24.666666666666664
24.666666666666664

JavaScript

console.log(2 / 3 + 5 * 7 - 11);

RESULT

24.666666666666664

平方根を取る関数 (演算子?)

素数夜曲 P.389 によると Scheme で sqrt は単項演算子らしい.

(write (sqrt 2))

RESULT

1.4142135623730951

入れ子にすれば複数回適用できる.
Scheme は関数合成あるのだろうか.
ここを見ると Gauche ならあるようだが.

(write (sqrt (sqrt 4)))

RESULT

1.4142135623730951

Python

Python 版は次の通り.
Python は math をインポートしないといけないのがめんどい.
Python 3.5.1 を使っているが関数合成はないのだろうか.
ちょっと調べたところでは標準ではなさそうだった.

import math
print(math.sqrt(2))
print(math.sqrt(math.sqrt(4)))

RESULT

1.4142135623730951
1.4142135623730951

Haskell

Haskell は関数合成 (.) がある.

main = do
  print $ sqrt 2
  print $ sqrt $ sqrt 4
  print $ (sqrt . sqrt) 4

RESULT

1.4142135623730951
1.4142135623730951
1.4142135623730951

JavaScript

console.log(Math.sqrt(2));
console.log(Math.sqrt(Math.sqrt(4)));

RESULT

1.4142135623730951
1.4142135623730951

自然対数の底, ネイピア数

Scheme では exp を使えば出せる.
$e$ 自体は定義されていない?

(write (exp 1))

RESULT

2.718281828459045

Python

Python の場合はやはり math モジュールにある.

import math
print(math.e)

RESULT

2.718281828459045

NumPy にもある.

import numpy as np
print(np.e)

RESULT

2.718281828459045

Haskell 版

$e$ 自体は定義されていないので Scheme と同じく指数関数から近似値を出す.

main = do
  print $ exp 1

RESULT

2.718281828459045

JavaScript 版

Math.exp() が自然対数の底による指数関数で,
Math.pow() は一般の底と指数の関数.

console.log(Math.exp(1));
console.log(Math.pow(2, 3));

RESULT

2.718281828459045
8

2 項演算子をいくつか

まずは等号 = を.

(write (= 1 1))
(newline)
(write (= 1 2))

RESULT

#t
#f

ここで #t は true, #f は false を意味している.
== ではないのかとちょっと驚いた.

ちなみに引数がたくさんある場合にも適用できる.

(write (= 1 2 3 4 5 6))
(newline)
(write (= 1 1 1))
(newline)
(write (= 1 1 1 2))

RESULT

#f
#t
#f

不等号 > >= などもある.
不等号はそれぞれ隣の項に対して適用させていった結果を出力するようだ.

(write (< 1 2 2 3))
(newline)
(write (< 1 2 3 4))

RESULT

#f
#t

Python

等しくないことの判定は != だ.

print(1 == 2)
print(1 == 1)
print(1 != 1)
print(1 < 2)

RESULT

False
True
False
True

こちらは = だと代入になってしまうので == と重ねる.

Haskell

Scheme の (= 1 2 3 4) みたいなのはどう書けばいいのだろう.
foldr で書けると思ったので foldr (==) 1 [1, 2, 3, 4] と書いてみたら怒られた.
相談したら「それ型エラー起こしてるから. ちゃんとして」と言われた.
Haskell, ちょっとしたところですぐこけるのでとてもつらい.

結論からいうと適当に 2 つリストを作り,
その要素を比較していく形で対処するのが普通らしい.
他のところでもそういう処理をするのがいいというコメントを頂いたことがあるので,
道具箱におさめておこう.

main = do
  print $ 1 == 1
  print $ 1 /= 1
  print $ 1 < 2
  let xs = [1, 2, 3, 4]
  print $ and $ zipWith (==) xs (tail xs)
  let ys = [1, 2, 3, 4]
  print $ and $ zipWith (<) ys (tail ys)
--  print $ foldr (==) 1 [1, 2, 3, 4] -- エラーになった

RESULT

True
False
True
False
True

let を使うのが癪なので次回やる予定の lambda を使って書いてみる.

main = do
  print $ (\xs -> and $ zipWith (==) xs (tail xs)) [1, 2, 3, 4]
  print $ (\xs -> and $ zipWith (<) xs (tail xs)) [1, 2, 3, 4]

RESULT

False
True

見づらい気もするので無理せず関数定義した方がいい気もする.

mycompare :: [Int] -> Bool
mycompare xs = and $ zipWith (<) xs (tail xs)

main = do
  print $ mycompare [1, 2, 3, 4]

RESULT

True

Haskell 追記

またコメントを頂いてしまった.
これ.

and $ ap (zipWith (<)) tail [1..4]
True

and $ ap (zipWith (<)) tail [1,2,2,3]
False

実行してみよう.
しばらくはまったが何となく ap を使うためにインポートが必要っぽい.

import Control.Monad

main = do
  print $ and $ ap (zipWith (<)) tail [1..4]
  print $ and $ ap (zipWith (<)) tail [1,2,2,3]

RESULT

True
False

最高か.

そして「素人はこんなこともわからない」というのを思い出せさてくれるし,
とてもいい体験だった.

ちょっと調べはしたが ap が何なのかあまりよくわかっていない.
とりあえずこれ.

myap f g = \x -> f x (g x)
main = do
  print $ and $ myap (zipWith (<)) tail [1..4]
  print $ and $ myap (zipWith (<)) tail [1,2,2,3]

RESULT

True
False

stackoverflow もきちんと全部読んだわけではないし,
この雑な理解でいいとも思わないがとりあえずこれで掴まえられるところもある.
「適当にしか理解していない (そして半端な理解だと割とどうでもいいところで無駄にはまる)」ことさえ理解しておけば,
あとでいくらでも調節は効くと数学でいつも経験することをいつも通り信じて追記を終える.

JavaScript

比較には === と == がある.
基本的に === でやるのが安全.

console.log(1 === 2);
console.log(1 === 1);
console.log(1 !== 1);
console.log(1 < 2);

RESULT

false
true
false
true

JavaScript で複数の比較はどう書くといいだろうか.
reduce を使おうと思ったが,
それは Haskell の最初の foldr でエラーになるのと同じ理由で駄目だ.
ここを見ると zip がないようだ.
ふつうにループを回すのでは面白くない.

大文字小文字の区別

~~素数夜曲 P.390 の記述によると,~~
~~Scheme は原則として大文字小文字を区別しないらしいが実装により異なるとのこと.~~
いわゆる処理系で変わるとかいうやつか?

安全性を考えるなら小文字に統一するのがいいらしい.
区別しないことを前提にキャメルケースを使うのも一手とか何とか.

今回はこのくらいにしよう.

Scheme 追記

下にあるようにコメントを頂いた.

Scheme の仕様は改定を重ねられているので、どの版であるかによって挙動が異なる部分があります。 Scheme の仕様はその正式名称を略して RnRS と呼ばれていて、 n の部分に何回目の改定であるかの番号が入ります。 最新は R7RS です。
「大文字小文字を区別しない」というのは R5RS までの仕様です。 (ただ、 R5RS 処理系を名乗る処理系でも区別する処理系や、切り替えられる処理系はあります。) R6RS 以降では区別するのがデフォルトです。
有理数や無限長整数などは R6RS 以外ではオプショナルな仕様です。 (R6RS で必須になった後、 R7RS では再びオプショナルになりました。) 処理系によっては桁あふれに配慮が必要な場合もあります。 有理数や無限長整数は Guile や Gauche では問題なく使えますので気にする必要はありませんが、その他に色々なところで仕様では未規定の部分があるので処理系を乗り換える機会にはつまらないことで躓くかもしれません。

思っていたよりも面倒そうな話だった.
ただ「ハマる可能性があるかもしれない」
「ハマるところはこの辺」というのが頭の片隅にあるかないかだけでも
全く違うことはこれまでの経験でよくわかっている.
こんなありがたいことはない.
こういうコメントを頂けるのが記事にしておく醍醐味だ.

地道に続けよう.