2016-03-20

プログラミングGauche mit-formとprimitive-formの変換

Scheme

最近、「プログラミングGauche」を読み直しています。SICPを読んでいて行き詰まってしまったのと、実践で使えるSchemeを修得したいという考えからです。

今日はSchemeにおける関数の記法の変換をやってみました。

(define (mit-form->primitive-form expr)
  (list 'define (caadr expr)
        (list 'lambda (cdadr expr) (caddr expr))))

(define (primitive-form->mit-form expr)
  (list 'define (cons (cadr expr) (cadr (caddr expr)))
        (caddr (caddr expr))))

util.matchを使うと、もっと簡単に書けます。

(use util.match)

(define (mit-form->primitive-form expr)
  (match expr
         [('define (func . args) . body)
          (list 'define func (list* 'lambda args body))]))

(define (primitive-form->mit-form expr)
  (match expr
         [('define func ('lambda args . body))
          (list* 'define (cons func args) body)]))

list*っていう関数は、はじめて使いました。(list* a b c)は(cons a (cons b c))になります。cがリストのときに便利ですね。

2016-01-04

PLAI 第6章環境の導入

Scheme

interp関数の(extend-env (bind (fdC-arg fd) (interp a env fds)) mt-env)を(extend-env (bind (fdC-arg fd) (interp a env fds)) env)とするとダイナミックスコープになってしまうので注意。(schemeはダイナミックスコープではなく、レキシカルスコープ)

#lang plai-typed

(define-type ExprC
  [numC (n : number)]
  [idC (s : symbol)]
  [appC (fun : symbol) (arg : ExprC)]
  [plusC (l : ExprC) (r : ExprC)]
  [multC (l : ExprC) (r : ExprC)])

(define-type FunDefC
  [fdC (name : symbol) (arg : symbol) (body : ExprC)])

(define-type Binding
  [bind (name : symbol) (val : number)])

(define-type-alias Env (listof Binding))

(define mt-env empty)

(define extend-env cons)

(define (get-fundef [n : symbol] [fds : (listof FunDefC)]) : FunDefC
  (cond
    [(empty? fds) (error 'get-fundef "reference to undefined function")]
    [(cons? fds) (cond
                   [(equal? n (fdC-name (first fds))) (first fds)]
                   [else (get-fundef n (rest fds))])]))

(define (lookup [for : symbol] [env : Env]) : number
  (cond
    [(empty? env) (error 'lookup "name not found")]
    [else (cond
            [(symbol=? for (bind-name (first env))) (bind-val (first env))]
            [else (lookup for (rest env))])]))

(define (interp [e : ExprC] [env : Env] [fds : (listof FunDefC)]) : number
  (type-case ExprC e
    [numC (n) n]
    [idC (n) (lookup n env)]
    [appC (f a) (local ([define fd (get-fundef f fds)])
                  (interp (fdC-body fd)
                          (extend-env (bind (fdC-arg fd) (interp a env fds)) mt-env)
                          fds))]
    [plusC (l r) (+ (interp l env fds) (interp r env fds))]
    [multC (l r) (* (interp l env fds) (interp r env fds))]))

2016-01-03

一次合同式の解

数学

一次合同式とは以下である。　
$ax \equiv b\,\,mod\,n$
$GCD(a,n)=d$ のとき $a=a'd$ 、 $n=n'd$ と書ける。
$ax-b=nt$ （ $t$ は整数)にこれを代入すると、 $a'dx-b=n'dt$ 即ち、 $b=a'dx-n'dt$ より、 $b$ は $d$ を約数として持たなければならない。よって、 $b=b'd$ と書くと、 $a'dx \equiv b'd\,\, mod\,n'd$ なる。 $d$ で割ると以下のようになる。
$a'x \equiv b'\,\, mod\,n'$
この一次合同式の唯一つの解を $x_{0}$ とすると、 $a'x_{0} \equiv b'\,\, mod\,n'$ より $a'x_{0}-b'=n't$
両辺に $d$ 掛けて、 $a'dx_{0}-b'd=n'dt$ 即ち $ax_{0}-b=nt$ となり
$ax_{0} \equiv b\,\, mod\,n$
よって、 $x_{0}$ も元の一次合同式の解である。
ここで、 $x=x_{0}+n't$ とすると $ax=ax_{0}+an't=ax_{0}+a'nt \equiv b\,\, mod\,n$
よって、 $x=x_{0}+n't$ も元の一次合同式の解である。 $x_{0}+n'd \equiv x_{0}\,\, mod\,n$ より、以下の $d$ 個の整数が解である。
$x_{0},\,x_{0}+n',\,x_{0}+2n',\,\cdots,\,x_{0}+(d-1)n'$

2016-01-01

PLAI by Shriram Krishnamurthiを5章まで読んだ

Scheme

「Programming Languages: Application and Interpretation by Shriram Krishnamurthi」というPDFを読んでいます。http://cs.brown.edu/~sk/Publications/Books/ProgLangs/
これは、言語処理系に関する本のようです。インターネットで調べたところCPS変換についても詳しく書かれているようです。

使用するプログラミング環境はRacketで、言語はplai-typedという型付きのSchemeのような言語です。本の題名を略すとPLAIとなるので、そこから名付けているのだと思います。LISPの基本が理解できれば、読んでいくうちにわかるので、plai-typedについての知識は全く必要ありません。

わかりやすい英語で書かれていて、英語の苦手な僕でも、辞書を引きながら読み進むことができています。普段、英語をあまり読まないので、とても勉強になっています。

5章までで、以下の簡単なインタープリタを作成します。

#lang plai-typed

(define-type ExprC
  [numC (n : number)]
  [idC (s : symbol)]
  [appC (fun : symbol) (arg : ExprC)]
  [plusC (l : ExprC) (r : ExprC)]
  [multC (l : ExprC) (r : ExprC)])

(define-type FunDefC
  [fdC (name : symbol) (arg : symbol) (body : ExprC)])

(define (subst [what : ExprC] [for : symbol] [in : ExprC]) : ExprC
  (type-case ExprC in
    [numC (n) in]
    [idC (s) (cond
               [(symbol=? s for) what]
               [else in])]
    [appC (f a) (appC f (subst what for a))]
    [plusC (l r) (plusC (subst what for l) (subst what for r))]
    [multC (l r) (multC (subst what for l) (subst what for r))]))

(define (get-fundef [n : symbol] [fds : (listof FunDefC)]) : FunDefC
  (cond
    [(empty? fds) (error 'get-fundef "reference to undefined function")]
    [(cons? fds) (cond
                   [(equal? n (fdC-name (first fds))) (first fds)]
                   [else (get-fundef n (rest fds))])]))

(define (interp [e : ExprC] [fds : (listof FunDefC)]) : number
  (type-case ExprC e
    [numC (n) n]
    [idC (_) (error 'interp "shouldn't get here")]
    [appC (f a) (local ([define fd (get-fundef f fds)])
                  (interp (subst a
                                 (fdC-arg fd)
                                 (fdC-body fd))
                          fds))]
    [plusC (l r) (+ (interp l fds) (interp r fds))]
    [multC (l r) (* (interp l fds) (interp r fds))]))

以下のように実行します。

> (define double (fdC 'double 'x (plusC (idC 'x) (idC 'x))))
> (interp (appC 'double (numC 3)) (list double))
- number
6

2015-11-18

Javaで作曲した (題名："837799")

Java

初期値837799のコラッツ数列をmod 127を演算してMIDIの音階にしてみました。
こちらで聴けます。
https://soundcloud.com/user783056320/837799a

package collatz;

import java.math.BigInteger;

import javax.sound.midi.Instrument;
import javax.sound.midi.MidiChannel;
import javax.sound.midi.MidiSystem;
import javax.sound.midi.Synthesizer;

public class Collatz {
	  public static void main(String[] args){
		    MidiChannel channel = null;
		    try {
		      Synthesizer synthesizer = MidiSystem.getSynthesizer();
		      synthesizer.open();
		      Instrument[] instruments = synthesizer.getDefaultSoundbank().getInstruments();
		      synthesizer.loadInstrument(instruments[0]);
		      channel = synthesizer.getChannels()[0];
              soundCollatz(channel, new BigInteger("837799"));
		      synthesizer.close();
		    } catch(Exception e){
		      if(channel != null)  channel.allNotesOff();
		    }
		    System.exit(0);
		  }
	  
	  public static BigInteger collatz(BigInteger n){
		  if(n.mod(new BigInteger("2")).compareTo(new BigInteger("0")) == 0){
			  return n.divide(new BigInteger("2"));
		  }else{
			  return n.multiply(new BigInteger("3")).add(new BigInteger("1"));
		  }
	  }
	  
	  public static void soundCollatz(MidiChannel channel, BigInteger n) throws InterruptedException{
		  BigInteger a = n;
		  while(a.compareTo(new BigInteger("1")) != 0){
			  System.out.println(a);
			  sound(channel, a.mod(new BigInteger("127")).intValue());
			  a = collatz(a);
		  }
	  }
	  
	  public static void sound(MidiChannel channel, int n) throws InterruptedException{
	      channel.noteOn(n , 127);
	      Thread.currentThread();
		  Thread.sleep(256);
	      channel.noteOff(128);
	  }
}

2015-11-09

近況

秋から冬になろうとしています。少し肌寒いですね。
最近は、SICPとAwodeyの圏論を読んでいます。
SICPは面白いけれど、問題がとても難しいです。
最初は全問解こうと思っていたのですが、2章後半であきらめました。
今は3章の「標準部品化力、オブジェクトおよび状態」を読んでいます。
今年中には読み終わらないかもしれません。
Schemeを学んでいて面白いのは、問題にとって本質的な部分だけを考えればよいところです。
Schemeを読むことに慣れると、どこに集中力を使ったらいいかがわかるようになります。
集中しなくてよいところは、後で個別に考えるという癖がつきました。
このような思考法は仕事で仕様書を読むときにも役立っています。
最初から順番に理解しながら読んでいくということはしなくなりました。
プログラムを書くときもそうです。
インターフェースの部分は最初は考えません。
難しいところから書きます。

圏論の方はHaskellのモナドから興味を持ちました。
どうやら「プログラミングに圏論などという純粋数学を学ぶ必要はない。」という意見の人が多いようですが僕の考えは少し違います。
背伸びをすることは常に良いことだと思っています。
高校生のころ、授業とは全く関係のない論理学の本を背伸びをして読んでいました。
なぜか論理学にピンときたのです。
論理学は今の仕事(デジタル回路)の基礎にもなっていて、とても役立っています。
高校生の自分は将来役立つとは思いませんでした。
量子力学だって最初はわからなかったけど常識になったのだから、圏論もものにすることができるはず・・・と思いたいです。
もちろん、圏論の方が量子力学よりずっと難しいですが・・・

圏論を使って物理やプログラムを定式化したい。
そして、新しい世界を見るのだ！！！

2015-11-09

SICP問題3.6 乱数

Scheme

乱数生成のアルゴリズムとしてメルセンヌツイスターを使うときにはsrfi-27を使います。
テストをするときなど、乱数列を再現させたいときがあります。
以下のrand関数は((rand 'reset) <非負の整数i> <非負の整数j>)で乱数源を初期化します。
(rand 'generate)を複数回実行することにより、乱数列が得られます。
この乱数列を再現させたいときには、((rand 'reset) <非負の整数i> <非負の整数j>)を再実行してから(rand 'generate)します。

(use srfi-27)

(define (rand x)
  (cond [(eq? x 'generate) (random-real)]
        [(eq? x 'reset) (lambda (i j)
                          (random-source-pseudo-randomize!
                           default-random-source i j))]
        [else (error "Incorrect argument -- RAND" x)]))