本を読む

読書やコンピュータなどに関するメモ

bashでGrassをキメたら悪酔いしたwww

そろそろ誰かが bash で Grass を書くと見た。
                           ,r;;;;ミミミミミミヽ,,_
                         ,i':r"    + `ミ;;,
       __,、           ≡     彡        ミ;;;i
    〃ニ;;::`lヽ,,_           ≡  彡 ,,,,,、 ,,,,、、 ミ;;;!
    〈 (lll!! テ-;;;;゙fn    __,,--、_  ..   ,ゞi" ̄ フ‐! ̄~~|-ゞ, ≡
   /ヽ-〃;;;;;;;llllll7,,__/"  \三=ー"."ヾi `ー‐'、 ,ゝ--、' 〉;r'  ≡  bashは自分を評価することができるんです
   >、/:::/<;;;lllメ   \ヾ、  ヽTf=ヽ  `,|  / "ii" ヽ  |ノ
  j,, ヾて)r=- | ヾ:   :ヽ;;:     | l |  l  ''t ←―→ )/イ^    ≡ awkとは違うんです
 ,イ ヽ二)l(_,>" l|    ::\;::    | |  |  ヽ,,-‐、i'  / V
 i、ヽ--イll"/ ,, ,//,,    :;;   l //  l く> /::l"'i::lll1-=:::: ̄\
 ヾ==:"::^::;;:::/;;;;;;;;;:::::::::::::: :::::ゞ ノ/   L/〈:::t_イ::/ll|─-== ヾ
  \__::::::::/::::::::::::_;;;;;;;;;;;;;;;;;ノノ   ヘ   >(゙ )l:::l-┴ヾ、ヽ  )
      ̄~~ ̄ ̄/ :::|T==--:::::  //  / ト=-|:|-─ ( l   /
         / ::  ::l l::::::::::::::::::/ /:::::::::::/:::::(ヽ--─  / |  /
         ヽ_=--"⌒ ゙゙̄ヾ:/ /:::::::/:::::::::`<==-- ノ / /

 …すみません、言ってみたかっただけです。

 というわけで、ちょっと草植えときますね型言語Grassの処理系をpure bashで書いてみました。

前置き:シェルスクリプトはLispである

 みなさんご存知のとおり、シェルスクリプトはLispの一方言です。つまり、空白で区切った要素からなるリストを基本構造として、それを評価すると先頭が関数(手続き、コマンド)と解釈されます。

 たとえば、以下のシェルスクリプトをbashやPOSIX-shで実行すると、現在の日時が表示されます。

car() {
    echo $1
}

cdr() {
    shift
    echo $*
}

list='go to date and smile'

eval $(car $(cdr $(cdr $list)))

 という線で、クロージャーとかメタプログラミングとかの方向で実装してみます。

注意

  • In(入力)は未実装です
  • ちょっと複雑なラムダ計算(grass.elのサンプルにあるgrass-sample-helloでも)をすると、すぐマシンリソースを食い尽くしますので、注意してください
  • trueとfalseは、わかってないので適当です

 このあたりの不出来さが、タイトルの「悪酔い」の所以です。

実装の説明

 次のようなプログラムをパースします。

wwWWwWWWwvwWWwwWwwwWwwwwwWwwwwwwww

 すると、次のような文字列を生成します。

Abs 2 'App 2 1;App 3 1;';Abs 1 'App 2 2;App 1 3;App 1 5;App 1 8;';

 これはシェルスクリプトでもあります(言語内DSL?)。これを評価します。

 まず、先頭のAbsを実行すると、次のような文字列(クロージャ)が生成されてスタックに積まれます。

lambda 2 5 'App 2 1;App 3 1;' x

 lambdaの後に、未束縛の引数の数、スタック上のクロージャの位置、ボディ、(束縛済みの引数...)、「x」が続く、という書式です。

 これはシェルスクリプトでもあります。Appは、スタックから関数としてクロージャ文字列を参照すると、最後の「x」の前に引数を追加してから、文字列を評価します。

ソースコード

#!/bin/bash
# grass.bash
#   version 2008-09-13
# Copyright (C) 2008 emasaka. All rights reserved.

shopt -s extglob

declare debug                   # debug flag
declare parseonly               # only parse and exit

declare -a stack
declare -i stackptr=0

function errorout() {
    (echo "$@" >&2) > /dev/null
}

function log.debug() {
    [ -n "$debug" ] && errorout "$@"
}

function pushstack() {
    stack[$((stackptr++))]=$1
}

function getstack() {
    echo ${stack[$((stackptr - $1))]}
}

# DSL

function App() {
    local -i fun_offset=$1
    local -i arg_offset=$2

    local fun=$(getstack $fun_offset)
    local arg=$(getstack $arg_offset)
    log.debug "App: stackptr=<$stackptr> fun=<#$fun_offset: $fun)> arg=<#$arg_offset: $arg)>"

    local suffix
    if [[ $fun == *\ x ]];then
        fun=${fun% x}
        suffix=' x'
    fi
    local res=$(eval $fun \""$arg"\"$suffix)
    pushstack "$res"
}

function Abs() {
    local -i nargs=$1
    local body=$2

    log.debug "Abs: nargs=<$nargs> stackptr=<$stackptr> body=<$body>"
    pushstack "lambda $nargs $stackptr '$body' x"
}

function lambda() {
    log.debug "lambda: $*"
    local -i nargs=$1
    shift

    if [ $nargs = 1 ];then
        local -i stackptr=$1    # mask stackptr by local one
        local body=$2
        shift 2
        local -a stack=("${stack[@]}") # copy stack to local one

        while [ $# != 0 ];do
            local e=$1
            shift
            case "$e" in
            lambda)
                local -i level=1
                while ((level > 0));do
                    local elm=$1
                    [ $# = 0 ] && break
                    case "$elm" in
                    lambda)   ((level++)) ;;
                    x)        ((level--)) ;;
                    *\ *|'')  elm="'$elm'" ;;
                    esac
                    e="$e $elm"
                    shift
                done
                ;;
            x)
                continue
                ;;
            esac
            pushstack "$e"
        done
        eval "$body"
        getstack 1
    else
        echo -n "lambda $((nargs - 1)) $1 '$2'"
        shift 2
        local e
        for e in "$@";do
            if [[ $e == lambda* ]] || [[ $e != *\ * ]] || [ -z "$e" ];then
                echo -n " $e"
            else
                echo -n " '$e'"
            fi
        done
        echo
    fi
}

function Identity() {
    echo "$1"
}

function In() {
    errorout 'function In is not implemented'
}

function Char() {
    local self=$1
    set $2
    if [ "$1" = Char ] && [ "$2" = "$self" ];then
        echo "lambda 2 1 'App 3 1'" # true
    else
        echo "lambda 2 1 'App 3 2'" # false
    fi
}

function Succ() {
    local c=$1
    set $c
    if [ "$1" = Char ] && [[ $2 == +([0-9]) ]];then
        echo Char $(($2 == 255 ? 0 : $2 + 1))
    else
        errorout "function Succ is called with '$c'"
    fi
}

function Out() {
    local c=$1
    set $c
    if [ "$1" = Char ] && [[ $2 == +([0-9]) ]];then
        errorout -ne "\x$(printf '%x' $2)"
    else
        errorout "function Out is called with '$c'"
    fi
    echo "$c"
}

# parser

function trim_split() {
    local s=$1

    s=${s//w/w}                # 全角→半角
    s=${s//W/W}
    s=${s//v/v}
    if [[ $s == *w* ]];then
        s=${s//[^Wwv]/}
        s=${s#+([^w])}
        echo ${s//v/ }
    fi
}

function parse1() {
    local s=$1
    local arg

    while [ -n "$s" ]; do
        case "$s" in
        W*)
            echo -n 'App '
            arg=${s##+(W)}
            echo -n $((${#s} - ${#arg})) ' '
            s=${arg##+(w)}
            echo -n $((${#arg} - ${#s}))';'
            ;;
        w*)
            echo -n 'Abs '
            arg=${s##+(w)}
            echo -n $((${#s} - ${#arg})) "'"$(parse1 "$arg")"';"
            return
            ;;
        esac
    done
}

function parse() {
    local s
    for s in $(trim_split "$1");do
        parse1 "$s"
    done
}

# main

function toplevel() {
    local s

    pushstack Identity
    pushstack In
    pushstack 'Char 119'
    pushstack Succ
    pushstack Out

    read -d '' s                # slurp
    local parsed=$(parse "$s")
    log.debug "parsed: $parsed"
    [ -n "$parseonly" ] && return
    eval $parsed
    App 1 1
}

declare opt
while getopts 'dp' opt;do
    case "$opt" in
    d) debug=1;;
    p) parseonly=1;;
    esac 
done
shift $((OPTIND - 1))

if [ $# = 0 ];then
    toplevel
else
    toplevel < $1
fi

まとめ

 Grassをシェルスクリプトに変換して評価するとシェルスクリプトが得られ、それを評価すると…という方法でGrassを実装してみました。前述のとおり、サンプルも実行しきれない効率の悪さなので、awk版を元に作り直したほうがまともなものになると思います。

 そもそもが、「シェルスクリプトはLispの方言」「自分を評価することができるんです」の2ネタをやりたいがためのネタ実装ですので、ご了承ください。そうそう、「シェルスクリプトはLispの方言」はもちろん冗談ですので、念のため。

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://emasaka.blog65.fc2.com/tb.php/446-dca98e24

 | HOME | 

Categories

Recent Entries

Recent Comments

Recent Trackbacks

Appendix

emasaka

emasaka

フリーター。
連絡先はこのへん

Monthly


FC2Ad