pineapple blog

You may want to know how to run loop in Scheme. To illustrate, let’s take computation of n!

(define (! n) (if (<= n 1) 1 (* n (! (- n 1)))))

That’s all. There’s no trick there. Just use recursion. I know you are going to ask “is this practical?” Yes, I can surely answer “it is practical.” But why? Before going deeper, I need to explain local variables —- C wizards/witches sometimes, and C++ wizards/witches never, call them automatic variable.

During the stone age, C wizards/witches used to write a code like this:

func(begin, end, index) {
  for (index = begin; index <= end; ++index) {
    /* do something */
  }
}
main() {
  func(1, 10);
  /* do other thing */
}

Amazingly we needed to handle local variables as arguments of the function. Of course this was unsafe in C and thus banned. However, by combining lambda, this mixture of arguments and local variables of a function can make syntax very simple. Here’s an example.

((lambda (x y) (do-something-with x)) 100 200)

In this code variables x and y are local to the lambda and they are also initialized by 100 and 200 respectively. Thus this is equivalent to the following C code.

func() {
  int x = 100;
  int y = 200;
  do_something_with(x, y);
}

Though lambda works perfectly well for introducing local variables, the lambda expression separates the names of the variables and their initial values. To avoid this separation, Scheme has an alternative as follows.

(let ((x 100) (y 200)) (do-something-with x y))

This let procedure has yet another function called named-let. The named-let is used for describing loop as in the following code.

(define (print-n-periods n) (let loop ((i n)) (print “.”) (if (> i n) (print “end”) (loop (+ i 1)))))

そろそろループにとりかかろう．例題としてn!を書いてみる．

(define (! n) (if (<= n 1) 1 (* n (! (- n 1)))))

これだけだ．なんのトリックも無い．再帰するだけ．本当にこれでいいのって聞かれるかもしれない．問題ない．でもこれでどうしていいの？その質問の前に，ローカル変数について説明しておきたい．Cウィザード（ただしC++ウィザードを除く）は自動変数と呼ぶやつだ．

石器時代のCウィザードは次のようなコードを書いていた．

func(begin, end, index) {
  for (index = begin; index <= end; ++index) {
    /* do something */
  }
}
main() {
  func(1, 10);
  /* do other thing */
}

信じられないかもしれないが，関数の引数とローカル変数は区別されなかった（だって両方ともスタックの上でしょ）．もちろんCではこれは安全ではないし，それゆえこの書き方は禁止された．しかしながら，λと組み合わせれば，関数引数とローカル変数の混在は可能などころか，言語をシンプルにする．これがその例だ．

((lambda (x y) (do-something-with x)) 100 200)

このコードではxとyがローカル変数で，それぞれ初期値100と200を与えられている．このSchemeコードは次のCコードと同じ意味だ．

func() {
  int x = 100;
  int y = 200;
  do_something_with(x, y);
}

このようにλはローカル変数の導入に完璧な役割をはたすわけだが，しかし変数名と初期値が離れ離れというのは読みづらくもある．Schemeには次の手続きがあって，これを使えば変数名と初期値をくっつけられる．

(let ((x 100) (y 200)) (do-something-with x y))

このletにはもうひとつバリエーションがあって，それは名前付きletと呼ばれている．名前付きletは次のようにループに使える．

(define (print-n-periods n) (let loop ((i n)) (print “.”) (if (> i n) (print “end”) (loop (+ i 1)))))

We have seen lambda and data structure. This is the time to see control structure of Scheme.

As you are C wizards/witches, you know if and goto cover all language features. In short, if and goto make a language Turing complete. Dijkstra used to say goto considered harmful, and proposed use of basic loop syntax like for and while.

There is if in Scheme. There is no goto in Scheme. You might think that the Scheme designer carefully removed such harmful goto and added some safer for or while instead, but this is not true. First there is no explicit loop in Scheme. Second there is more powerful feature than goto, which is called first-class continuation, in Scheme.

So how Scheme programmer write loops without for or while? They use recursion. No, I’m not kidding. We write a recursive function when we need a loop. Afraid of stack overflow? Scheme ALWAYS optimize tail recursion so that it won’t eat stack.

Before talking about loop, let us see how if works in Scheme. The following code returns the bigger value out of x and y.

(if (> x y) x y)

We can name this procedure as max.

(define max (lambda (x y) (if (> x y) x y)))

Here we did: max := \xy . x if x > y, y otherwise. There are syntax sugar to write the above code shorter as follows.

(define (max x y) (if (> x y) x y))

We will discuss about loops in Scheme shortly.

これまでλとデータ構造を見てきた．そろそろ制御構造に眼をやる時間だ．

Cウィザードは言語にifとgotoさえあれば何でも出来ることは知っている．一方，gotoに対するダイクストラの警告も知っている．

もちろんSchemeにもifはある．しかしSchemeにgotoは無い．というと，多分「ああJavaのようにgotoを取り除いてループ構文だけ残したのだな」と思われるかもしれない．これは二つの意味で異なっている．第一にSchemeにループ構文は無い．第二にSchemeにはgotoよりも強力な機能（第一級継続）が与えられている．

さて，Schemeにforやwhileが無いとすると，Schemeプログラマはどうやってループを書くのだろうか？実は再帰関数を使うのである．Cウィザードならそんなバカな！と思われるだろう．たしかにCで気軽に再帰を行うとスタックを使いきってしまう．しかしSchemeは「常に」末尾再帰を最適化するため，スタックを消費する問題は無い．

ループに関して話を進める前に，ifについて見ておかねばならない．次のコードはxとyのうち大きいほうを返す．

(if (> x y) x y)

この式にmaxという名前をつけよう．

(define max (lambda (x y) (if (> x y) x y)))

このコードの意味は max := \xy . x if x > y, y otherwise である．Schemeにはすこしばかりの構文糖が用意されていて，上述のコードは以下のように書き直せる．

(define (max x y) (if (> x y) x y))

次回はループについて勉強しよう．

A spoonful of sugar makes programming language sweet. Scheme has little syntax sugar, however, it has many sugar provided by libraries from list processing to web services.

One good example everybody loves is this: you can make a linked list of first, second, and third item by

(list first second third)

instead of writing

(cons first (cons second (cons third ())))

Other my favorite sugar is this:

(make-list n_elements initial_value)

The procedure make-list makes a list of n_elements elements whose value are filled with initial_value.

Procedures car and cdr return the first and the second item of a pair respectively. For example (car ‘(a . b)) returns a, and (cdr ‘(a . b)) returns b.

These cons, car, and cdr procedures are the core feature for list processing in Scheme. You can do almost everything on list processing, including tree and other graphs, on top of them.

There also are non-list data structures in Scheme: vector and hash table. Vector is like C’s pointer (void *) array. It can mix any types of elements in a single array. (Some implementation of Scheme has a special vector named uniform vector. It is more like C’s array.)

プログラミング言語に構文糖はつきものだが，Schemeに構文糖は殆ど無い．といっても，ライブラリには豊富な糖が用意されている．それこそリスト操作から，ウェブサービスまでだ．

例えば，前回紹介したリスト構造の生成は次のようなライブラリ手続きが使える．

(list first second third)

これは次のコードと同じ事をする．

(cons first (cons second (cons third ())))

他にこんなものもある．

(make-list n_elements initial_value)

手続き make-list は n_elements 要素のリストを作り，各要素の初期値を initial_value で埋める．

手続き car と cdr はそれぞれペアの1番目の要素と2番目の要素を返す．例えば (car ‘(a . b)) はaを返し (cdr ‘(a . b)) はbを返す．

これまで見てきた cons, car, cdr の組み合わせでほぼすべてのリスト操作を構築できる．リンクリストだけでなく，木構造や他のグラフ構造も含めてだ．

もちろん，リスト構造ではないデータ構造もSchemeにビルトインされている．それらにはベクタとハッシュテーブルがある．ベクタはCのポインタ配列と似ていて，あらゆる型のオブジェクトを配列に入れることができる．（一部の処理系はユニフォームベクタというデータ構造を提供しており，これはよりCの配列に近い．）

struct pair {
  void *item;
  struct pair *next;
};

C wizard/witch will soon recognize this structure is a node of linked list, and that is so true. The member item is a pointer to some item. The member next points to the next pair or null if there is no next pair.

This is the very fundamental structure of Scheme (and other Lisp dialects). Thus there is a very simple way to write a pair in Scheme like

(define p ‘(first_item . second_item))

instead of writing this:

struct pair *p = { first_item, second_item };

Remember, in Scheme, every function (procedure) call is written in (function argument argument…) format. The notation (define p …) means p := … in Scheme. The pair of first_item and second_item can be denoted as (first_item . second_item), however, Scheme interprets this as (function argument argument argument) if you don’t put quote (‘) before the open parenthesis.

You may want to ask, how do we write in Scheme when we want to do this:

typedef struct pair PAIR;
PAIR *p = malloc(sizeof(PAIR));
p->item = first_item;
p->next = second_item;

Obviously the memory pointed by p is dynamically allocated. For doing this in Scheme, we use cons procedure.

(define p (cons first_item second_item))

Notice: first_item and second_item must be previously defined or we’ll get an error.

A simple linked list will look like this:

‘(first . (second . (third . ())))

where () is an empty pair which is equivalent to C’s null.

struct pair {
  void *item;
  struct pair *next;
};

Cウィザードならこの構造体pairを見てすぐにリンクリストを思い浮かべるだろう．その通りだ．ポインタitemは何がしかの値へのポインタだし，ポインタnextは次のpair構造体へのポインタだ．

このpairはSchemeや他のLips方言において最も基本的な構造なので，シンプルな記法が用意されている．Schemeでは

(define p ‘(first_item . second_item))

と書けばCの

struct pair *p = { first_item, second_item };

とだいたい同じ意味になる．Schemeではすべての関数（正しくは手続きと呼ぶ）の呼び出しは (function argument argument…) の形を取るので，pの定義も (define p …) と書いて p := … となる．ここで first_item と second_item からなるペアは (first_item . second_item) と書くのだが，このままだと手続き first_item の呼び出しと区別できないので，クォート記号 (‘) をつけることでリテラルにしてやる．

たぶんあなたは「じゃあダイナミックにメモリ確保したいときはどうすればいいの？」と思うだろう．Cならこんな具合にしたいときだ．

typedef struct pair PAIR;
PAIR *p = malloc(sizeof(PAIR));
p->item = first_item;
p->next = second_item;

ダイナミックにメモリを確保したいときに，Schemeではcons手続きを使う．

(define p (cons first_item second_item))

注意：first_item と second_item は事前に定義されているものと仮定している．

簡単なリンクリストは次のようになる．

‘(first . (second . (third . ())))

ここに()は空のペアで，Cで言えばヌルポインタだ．

No variables are type-checked. Every function is lambda.

C wizards and witches love practical aspects of programming. They are able to use a new language only after they learn fundamental language feature like if and for, and basic library feature like I/O and handling of command-line arguments.

Those features are never fundamental in Scheme world, however, you are C wizards and witches and let’s walk along as you usually do.

We’ve already seen how we print text by a procedure named print.

(print “Hello, World!”)

Since Scheme’s print procedure can eat any number of arguments —-and arguments have no type—- you can do this.

(print “Hello ” 123 4.5)

This print procedure puts LF at the end of the text. If you don’t want an LF, you can use display instead. Whichever you choose, they put text to standard output (stdout) by default.

Of course Scheme can read text from standard input (stdin). Scheme, however, has a unique procedure named read.

(read)

This read procedure reads S-expression from stdin by default. S-expression is a data type, however, Scheme also expresses its program by S-expression, thus S-expression is a program simultaneously.

Now we know we must learn S-expression. To be continued.

Schemeに型は無く，関数はλであることを我々は見てきた．

ともかく実践を好むCウィザードは，言語機能として条件分岐とループ，ライブラリ機能やシステム機能としてテキストの入出力とコマンドライン引数の取り扱いさえわかってしまえば，あとはリファレンスを見ながらなんとか使えるだろうと思うことだろう．

Schemeの本質的なところは，条件分岐やループ，入出力では無いのだが，あなたはCウィザードだ．ひとまずCの流儀にあわせよう．

我々はすでにテキストを出力する方法を見てきた．それはprint手続き（Schemeでは関数のことを手続きと呼ぶ）で，

(print “Hello, World!”)

という風に使うのだった．Schemeのprint手続きは好きなだけ引数をとれるし，Schemeには型が無いのでこんな事が可能である．

(print “Hello ” 123 4.5)

このprint手続きは最後に改行文字を出力する．これを避ける最も簡単な方法はprintの代わりにdisplay手続きを使うことだ．いずれを使っても（デフォルトで）テキストは標準出力に出力される．

Schemeはもちろんファイルからの入力も扱える．ただし，Cには見られないユニークな入力方法が標準的に使われる．次のコード

(read)

は（デフォルトで）標準入力からS式を1個読み込む．S式はデータの形式だが，Schemeは構文木をS式で表現するので，すなわちプログラムの形式でもある．

ここで，S式について勉強しておかねばならない．続く．

It is time to explain lambda.

The closest concept to lambda in C language is a function. For example, a C function that takes one argument x and returns x+1 is as follows.

int plus1(int x) { return x+1; }

When you want to handle this function as a variable, you use a function pointer.

typedef int (*pfii)(int);
pfii pplus1 = plus1;

If C had any syntax to define a function pointer in situ, it would be like this.

pfii pplus1 = plus1(x) { return x+1; }

In this case, the name plus1 is no longer necessary. Thus we can rewrite this as follows.

pfii pplus1 = ^(x) { return x+1; }

Carat (^) is just a symbol for expressing unnamed function. Computer scientists write the above pseudo code in the following way:

This equation has the same meaning of the previous pseudo code. Actually Haskell almost accepts the above notation.

But computer scientists are also hackers themselves. Though they love to write in C, they hate to parse C. A good news is that they’ve already invented good ways to avoid such parsing before inventing C language. One is a stack machine (you must have an HP calculator somewhere in your home), and another is an S expression, which expresses parsing tree directly.

Scheme is based on S expression. The lambda \x.x+1 can be written as follows in S expression.

Let’s give a name to this lambda.

(define pplus1 (lambda (x) (+ x 1)))

You may want to ask “what is type of pplus1?” No, there are no compile-time type-check on Scheme. Everything is void pointer. Do you think this is crazy?

λ（ラムダ）を説明する．

C言語でλに一番近いものは普通の関数である．例えば引数xをとり，x+1を返すC関数は

int plus1(int x) { return x+1; }

と書けるだろう．この関数を変数としてハンドリングするには関数ポインタを使う．

typedef int (*pfii)(int);
pfii pplus1 = plus1;

もしC言語に関数ポインタを直接定義する方法があれば，次のように書けるだろう．

pfii pplus1 = plus1(x) { return x+1; }

作ってすぐに代入するので，名前plus1は必要ない．そこで次のように書いてみる．

pfii pplus1 = ^(x) { return x+1; }

キャラット(^)はいま恣意的に持ち出した記号で，もともとのplus1の代わりだ．（C言語に最近施された拡張はこれとほぼ同じ書き方を認める．）計算機科学者は上の擬似コードと同じことを次のように書く．

書き方が変わっただけで，本質的な意味は変わらない．むしろ，このような数学風の書き方がそのまま出来る言語だと便利である．実のところHaskellだとほぼそのまま書ける．

しかし計算機科学者はここでもう一ひねりを加える．Cウィザードなら誰もが自虐的になる言語パーザの実装を楽にするために，言語から文法というものを追放してしまうのだ．その流儀は主に二通りあって，ひとつはスタックマシンにしてしまうこと（HPの電卓持ってたでしょ？），もうひとつは構文木を陽に記述することだ．

後者の代表的な記法がS式で，SchemeもS式を採用している．元々のλ式であった \x.x+1 はS式で書くと次のようになる．

この式にpplus1という名前をつける（Schemeでは束縛すると言う）には，次のようなコードを書く．

(define pplus1 (lambda (x) (+ x 1)))

Cウィザードなら「型はどうなってる？」と疑問に思うだろう．Schemeにおいては，型は実行時にチェックされる．クレイジーに聞こえるかもしれないが，全てはvoidポインタだ．

You are a C wizard/witch. You must have your favorite editor. Is it vi? If so, leave it for C. If you are an Emacs user, keep it.

I know C wizards/witches have their favorite C compilers. So Scheme hackers do. My personal recommendation is Gauche. Gauche is practical, with lots of supporting libraries, and Mac friendly.

Want to try Hello World now? Here’s an example. Type the following code into helloworld.scm.

(define main (lambda (args) (print “Hello, World!”)))

Now run gosh helloworld.scm on a terminal. The Gauche interpreter will find an entry point named main and execute the function.

Theoretically, the above code can be described as follows.

where the backslash (\) means lambda.

So, what is lambda at all?

To be continued.

あなたはCウィザードだ．既に手に馴染んだエディタがあるだろう．それはviだろうか？もしそうなら，viはCのために取っておくべきだ．あなたがEmacsユーザなら，そのまま使い続けるといい．

CウィザードがCコンパイラを選ぶように，SchemeハッカーもSchemeインタプリタを選ぶ．有名所がいくつかあるが，僕はGaucheを勧める．十分に高性能で，ライブラリも充実しており，Macで扱いやすく，日本語文献が豊富だからだ．

ここで恒例の Hello, World! と行こう．以下のコードを helloworld.scm として保存する．

(define main (lambda (args) (print “Hello, World!”)))

コマンドラインで gosh helloworld.scm とすればGaucheインタプリタが起動して，上記のプログラムを読み込み，エントリポイントmainを見つけて，実行してくれる．

理論的に，上述のコードは以下の式と同じである．

ここにバックスラッシュ(\)はλの意味だ．

さて，λとはなんだろう？

続く．

When a C wizard/witch seeks a new language to learn, he/she will choose one from C++, Java, or Python. (If he/she already got used to C++, Java, or Python, he/she is no longer C wizard/witch.)

C++ is as powerful as C is in terms of run-time speed and low-level access; Java has portability (write-once-run-anywhere) and smart memory management; Python gives you cleanness of codes.

So, why should you learn a language which is hard to access low-level hardware, is not very sophisticated in memory management, is famous by its too many parenthesis?

One reason why we should learn Scheme is its simplicity. Actually Scheme is the most simple language among all practical programming languages. This guarantee a technique you can use with Scheme is acceptable by any other languages.

Another reason is that it is practical. For some situations Scheme would be the best solution. Such situations include writing a web server.

Yet another reason is that Scheme has always been loved by computer scientists. Thus new theories in computer science have been, and will have been, written or translated in Scheme sooner or later.

I’ll occasionally post an introductory series of Scheme for C wizards ad witches in this blog.

Cウィザードがそろそろ新しい言語を始めるとすると，選択肢は C++, Java, Python といったところから選ぶことになると思う．（既に C++, Java, Python を習得している元CウィザードはもはやCでプログラムを書けないから，現役のCウィザードが C++, Java, Python を知らないという仮定は妥当である．）

C++ならばCと変わらぬ実行速度と低レベルハードウェアへのアクセス性を手に入れられるし，Javaならばポータビリティとメモリ管理からの自由を得られる．Pythonに手を出せば，多少の実行速度を犠牲にするかもしれないが，驚くほどの読みやすさと書きやすさを手に入れるだろう．

それに比べたら，C++のような低レベルハードウェアのアクセスは困難だし，Javaほどは高効率なメモリ管理を期待できないし，Pythonほどの取っ付き易さも無いSchemeを取得するメリットはあるのだろうか．

Schemeを学習する一つ目の理由は，それがとてもシンプルな言語である—-実際，実用言語としては最もシンプルである—-ことだ．言語がシンプルであれば，その言語で使えるテクニックはプログラミングにおいて本質的なものとなる．

Schemeを学習する二つ目の理由は，それが実際に使える言語であることだ．あるシチュエーションでは，それが最適な言語であることもある．そのような例のひとつにウェブサーバが挙げられる．

Schemeを学習する三つ目の理由は，それが計算機科学者によって大切に扱われている言語であることだ．つまり，優れた計算機科学の知見は遅かれ早かれSchemeで書かれる．

このブログで，CウィザードのためのScheme入門を気の向くままに書いていこうと思う．