サンプルプログラム9（PL JavaScript編）

初歩的な電卓（３）

メインプログラム

標準入力から一行読んで結果を標準出力に印字するループ。大枠は過程の冒頭で示したものを使う。
字句解析、構文解析、評価器、の連絡は、前章の 2. に示したメソッドチェーンの書き方をするが、印字については、 console.log() をそのまま流用することにしておく。
```
require('readline').createInterface({
  input: process.stdin
}).on('line',(line)=>{
   console.log(line.scan().parse().val())
}).on('close',()=>{
  console.log('bye')
  process.exit(0)
})
```

構文解析（２）：優先度のある数式を扱う

トークン列の先頭から順にparse1 に渡して処理していく。
- （優先度の低い）演算子が渡されると、スタック上部に積まれた３つ組（演算子と２つの被演算子）を Nodeとして包み、それをあらためてスタックに積む。
  
  その後、その演算子の処理はまだ完了していないため、parse1 が再帰的に呼ばれる。
- 再帰呼出が一段深くなるごとにスタックの高さは２ずつ減るので、再帰はいつか末端に達する。
終わりを表す記号（END、演算子に準じて扱われている）が出てくると、END記号は、最も優先度が低い演算子の扱いなので、スタックに残る演算子や被演算子が全部処理され（つまり１つのNodeオブジェクトに集約されスタックに戻され）たあと、そのEND記号がスタックに積まれてparse1 が完結する。
- その結果、stk の上から２番目に、parse の結果として返すべき値が置かれていることになる。

Array.prototype.parse=function(){
  var stk=[]
  function parse1(tk){
     // console.log('parse1:',tk,stk)
     switch(typeof tk) {
       case 'number': case 'string':
         stk.push(tk) ; break
       case 'symbol' :    // 演算子
         let op1=stk[stk.length-2]      // スタックの上から２番目
         // console.log('op1=',op1)
         if(prior(tk)>prior(op1)) stk.push(tk)
         else {
           var r=stk.pop(), op=stk.pop(), l=stk.pop()
           stk.push(new Node(op,l,r))
           parse1(tk)
         }
         break;
       default: console.log(`unknown token ${tk.toString()}`)
     }
  // return nothing
  }
  // トークン列（末尾にENDマークを追加しておいて）を前から順にparse1に渡す
  [...this,sym('END')].forEach(e=>parse1(e))
  // スタックの上から２番目に残るデータが計算結果となる
  return stk[stk.length-2]      // or   stk[0]
}

スタックに積まれている演算子のうち一番上のものを取り出して op1 としている（tk が演算子の時、スタックの一番上 = 配列の末尾）には被演算子が入っている筈なので配列の末尾から２つめの要素を覗いている）。
- 配列 stkの末尾から２つめを取り出す記法として、JSでは（Rubyのようにブラケットの中に負の数を書いてのアクセスができないので代わりに） stk.slice(-2)[0] という書き方も使われることがあるが、この場合、配列の寸法が１以下の時に正しく動作しない（末尾の要素を取り出してしまう）。
- ベタな書き方ではあるが、ここではstk[stk.length-2] を使っておく。
なお、上記で使う関数 prior() は、演算子の優先度を整数値で返す関数を想定している。それを実際に実装するとしたら、たとえば以下のような記述になるだろう。
- 一覧表は、各プログラミング言語の仕様でもよく見かけるような、優先度毎の、演算子一覧表に近い形で記述できるようにするとして、
- でも prior() では、演算子を与えると優先度を返すという対応関係なので、それを簡単に（検索をせずにワンステップで）得られるデータ形式として、マップ的なもの（JavaScriptには Map型もあるが、それを使わずに単なるオブジェクトとして実現しても大丈夫）として持っておくのが望ましい。ので、変換を行うという作り方をしている。
```
// まず、優先度毎の演算子のリスト（文字列の配列として用意する）
const OPERlist={0: ['(', ')', 'END'], 1: ['='],
                2: ['+', '-'], 3: ['*', '/']}
// リストからマップへの変換
function list2map(ls){  
  let m={}    // マップ形式（実は単なるオブジェクト）の容器
  for(pr in ls)   // オブジェクトの各メンバー毎
    for(op of ls[pr]) // 配列の各要素毎
      m[sym(op)]=pr  // マップに登録
  // console.log(m)
  return m
}
// 変換したものを変数に保存しておいて、
const OPERmap=list2map(OPERlist)
// マップ（連想配列）を引くだけの関数
const prior=(op)=>OPERmap[op]
const prior=(op)=>{
  console.log('prior:', op,OPERmap[op])
  return OPERmap[op]||-3}
}
```

ここまでに示したプログラムを１つにまとめたソースコードをここに置いた。

さらに改良

括弧への対応
- 変更すべき場所（parse1 で、tkがSymbolである時の分岐で、op1 を得た後）を抜粋して以下に示す。
```
  if(! op1 || tk==sym('(') ||  // 条件を増やした（括弧を扱うため） ***
       prior(tk)>prior(op1) ) stk.push(tk)
  else if(op1==sym('(') && tk==sym(')') ) {
                 // 対向する括弧の間に要素が１つ  ***
    let r=stk.pop(),  _=stk.pop()
    stk.push(r)  // op1 は破棄し、要素だけをスタックに戻す ***
  } else {
     //   ... ３つ組を縮約するフェーズは、変更なし
  }
```
- 左括弧は無条件にスタックに積む（上記リストの１行目）
- 右括弧については、
  1. 上記リストの２番目の分岐、つまり op1 が左括弧である場合、向かい合った括弧の対を取り除く（左括弧をスタックから取り除いて破棄、tk も破棄）処理を行う。
  2. それ以外の場合は、普通にこれまで通りの（演算子同様の）処理を行うが、括弧の優先度は低いので、1. の条件が満たされるまで３つ組の縮約を parse1 の再帰呼出で繰り返すことになる。
- これらを反映させたコードはここ。
変数を使う
- 変数は、名前（変数名）とその値の一覧表なので、JSではオブジェクトを１つ作ればその中でデータが保持できる。
  - が、値を set, get する場面でややコードが煩雑になる。
  - また、set, get において追加の処理を行うなどの変更を行うとしたら、コードの維持が煩雑（変更すべき箇所が多くなる可能性がある）。
  これを回避するためには、
- 変数をクラスとして定義し、
  
  アクセッサー（もしくは setter, getter ）を用意するのが定跡。
- 最近のJSの、class 構文を使うと、以下のような定義になるだろう。
```
class Var {
  constructor() {
    this.map={}
  }
  set(name,val) {
    return this.map[name]=val
  }
  get(name) {
    return this.map[name]||0       // 未定義の変数に対しては、とりあえず
  }                        // デフォルト値として 0 を返すことにしておく
}                          // （エラーを発生させるという手もあるが）
// と、定義しておいて、コードの先頭近い箇所で
const vars=new Var
```
  - クラス名 Var は、JSのキーワード var と酷似している（case-sensitiveなので機能的には問題ないが、読む人が混乱する可能性はある）ので、気になる人は名前を変えて使って下さい（変数名 vars も然り）。
- 値を取り出す場面：（変更すべき箇所を抜粋して示す）
```
function val0(n){
  switch(typeof n) {
    case 'string': // （トークンが文字列の時は変数とみなす という前提で）
      return vars.get(n)   // ここで値を取り出して返す
```
- 左辺値としての特別扱い：
  - 演算子 ‘=’ は（RubyやJSでも、ここで制作している電卓的言語でも）、左辺に変数名（などの「左辺値」として利用可能な、式のようなもの）が置かれていることを前提として、副作用（変数が保持している値が変更される）を引き起こす。
  - ついでに（これも多くの言語で、ただしPythonは別）、‘=’ を含む代入式は代入された値がその式全体の値となる、ということにしよう。
  - これを実現するために、評価器（ここでは関数 val）で、演算子 ‘=’ の扱いと、その左辺に置かれたときの動作（val0 に渡して評価させるのではない、別の扱い）をさせる必要がある。（以下のコードを加える）
```
function val0(n){
  // ...
        default:
          let op,l,r ;   ({op,l,r}=n)
          // ここから書き換え
          if(op!=sym('='))         // = 以外の演算子について、
            return val1(op,val0(l),val0(r)) // ここは変更なし
          else if(typeof l=='string')
            return(vars.set(l,val0(r)))
            // 値を変数に記憶させた上、その値を返す
          else {  // 左辺が変数名以外のとき エラー扱い
            console.log(`invalid left-hand side: ${l.toString()}`)
            return(val0(r))
          }
```
若干の不都合の解消
- 単項式への対応：
  
  これまでの parse は、演算子を含まない単項式を入力すると、Nodeオブジェクトではなく number なり string なりのプリミティブ型の値を返すことになり、そこから val メソッドを呼べない。
  
  これに対応する策は１つ考えられる。
  1. string, number にもメソッド valを定義する。
```
String.prototype.val=Number.prototype.val=
  Node.prototype.val=function() { ... }
```
    - function キーワードで定義した関数は呼出時に this の束縛を行うため、呼出ておしてはこれで大丈夫そうだ。
    - が、ここにはもう１つ、JS固有の落し穴がある。
      
      stringなりnumberなりのプリミティブ型データからメソッドを呼び出す時には、自動的にそれに対応するオブジェクトに変換されたものが this に束縛される。 typeof 演算子はプリミティブ型のデータを識別するための演算子で、オブジェクトに対しては、ただ ‘object’ とだけ返し、 NumberオブジェクトなのかStringオブジェクトなのかそれ以外のオブジェクトなのか、判別してくれない。
    - ここは typeof　の代わりに instanceof ２項演算子（真偽値を返す）を使うことになる（これらの演算子の文法がまちまちなのはJSのちぐはぐな所の１つだろう）
```
function val0(n){
  // ...          変更すべき箇所を示す
  //              switch文の default:  までを以下のように
  if(typeof n == 'string' || n instanceof String)
    return vars.get(n) 
  else if(typeof n == 'number' || n instanceof Number)
    return n
  else { // then 'this' is Node object
    // ...    ここからは変更不要
```
  2. sym('TERM')(例えば)を演算子の位置に置き、l に終端記号の名前や値を保持する。
```
Array.prototype.parse=function(){
  // ...
    case 'number': case 'string':
      stk.push(new Node(sym('TERM'),tk)) ; break    //  Nodeの第３引数は略
function val0(n){ 
  // ...
    if(op==sym('TERM')) return val0(l)  // この行を挿入
    else if(op!=sym('='))
      return val1(op,val0(l),val0(r)) // この分枝は変更なし
    else if(typeof l.l=='string') 
      // この判定と処理の対象を l でなく
      //   l.l （Nodeに包まれた文字列を取り出す）に変更（エラー処理も）
      return(vars.set(l.l,val0(r))) 
    else {
      console.log(`invalid left-hand side: ${l.l}`)
      return(val0(r))
    }
```
- var を減らす：
  
  以前のJSでは変数宣言は var キーワードを使うしかなかった（グローバル変数以外）が、今は let, const も使えるので、必要に応じて使い分けていく。
  
  上記の変更を施したコードがここにあるので参照されたい

寄り道３再帰の例

階乗

const fact=(n)=>n<=1?1:n*fact(n-1)
// または
function fact(n) {
  if(n<=1) return n
  else return n*fact(n-1)
}

再帰を使わないならば、

// n に対して
[...Array(n+1).keys()].slice(1).reduce((x,y)=>x*y)
  // RubyやHaskellより若干面倒かな

末尾再帰で書くならば、

const fact=(n,r=1)=>n<=1?r:fact(n-1,r*n)
// または
function fact(n,r=1) {
  if(n<=1) return r
  else return fact(n-1,r*n)
}

アッカーマン関数

var x, y, test, count=0
function ack(x,y) {
  test>0 && (count+=1) 
  test>1 && console.log(`ack(${x},${y})`)
  if(x==0) return y+1
  else if(y==0) return ack(x-1,1)
  else return ack(x-1,ack(x,y-1))
}
var args=process.argv.slice(2)
console.log(args)
x=parseInt(args.shift||'3')
y=parseInt(args.shift||'3')
test=parseInt(args.shift||'0')
console.log(`ack(${x},${y})=${ack(x,y)}`)
test>0 && console.log(`(${count} times)`)

(ソースはここ)

サンプルプログラム9（PL JavaScript編）

初歩的な電卓（３）

メインプログラム

構文解析（２）：優先度のある数式を扱う

さらに改良

寄り道３ 再帰の例

寄り道３再帰の例