2018-10-31

Object.assign はプロトタイプ汚染攻撃に対して安全

古いlodash#merge()にはプロトタイプ汚染に対する脆弱性(修正済み)がありましたが、Object.assign() の動作について調べてみました。

var a = {};
console.log(Object.assign({},JSON.parse(`{"__proto__":{"foo":"bar"},"a":"b"}`)));
console.log(a.foo);

{a: "b"}
undefined

~~よかった！安全ですね。~~

こちらを参照ください

qiita.com

参考

2018-10-21

Lispインタープリター「Liyad」における末尾再帰最適化

テクノロジー development 言語

拙作のLisp インタープリター「Liyad」においても、 (無いとLisp処理系として格好が付かないので) 非常に限定的に末尾再帰最適化を実装しています。

Liyadにおける末尾再帰最適化

Liyadでは、単純にASTのS式が特定のパターン(1種類)に合致するときのみ末尾再帰最適化を行い、関数の再帰呼び出しをループに展開します。

パターンの疑似コード:

($lambda (f-arg-1 ... f-arg-N)
    expr-a-1 ... expr-a-M
    ($if cond-expr
        expr-t
        ($self r-arg-expr-1 ... r-arg-expr-N) ))

これを次のようにASTを変換します。

疑似コード:

($lambda (f-arg-1 ... f-arg-N)
    ($until cond-expr
        ($clisp-let (tempsym-1 ... tempsym-N)
            expr-a-1 ... expr-a-M
            ($set tempsym-1 r-arg-expr-1) ... ($set tempsym-N r-arg-expr-N)
            ($set f-arg-1 tempsym-1) ... ($set f-arg-N tempsym-N) ))
    expr-a-1 ... expr-a-M
    expr-t )

手抜きですね。

一般的な処理系における末尾再帰最適化

当たり前ですが、if 以外の条件文(switch 等)でも最適化します。
また、静的に決定できるならば、関数のシンボル名に関係なく最適化してくれることでしょう (Liyadでは $self という名前で参照していなければ最適化しません)。
関数内の複数のコードパスのうち、1つ以上の末尾が自身の呼び出しであれば適用できます。
また頭の良いコンパイラならば、2つの関数が相互に呼び合っている場合も最適化します。

処理系によっては、何かしらの形 (キーワードやデコレーターの類) で明示的に指示する必要があります。

参考

Pythonで末尾再帰最適化
末尾再帰最適化の正体
関数型電卓プログラム fncalc の作成 (4) ←ジオシティーズなので2019/3以降アクセスできなくなります。

2018-10-21

各言語におけるクロージャー

テクノロジー development 言語

Liyad v0.0.13をリリースしました。今回のリリースでは、クロージャー(関数閉包)関連のオペレーターが追加になりました。

($closure (arg1 argN) use (var1 varM) expr)
(|-> (arg1 argN) use (var1 varM) expr)

($capture (var1 varM) ($lambda (arg1 argN) expr))
($capture (var1 varM) (-> (arg1 argN) expr))

$closure および |-> はクロージャーとしてラムダ式を作成します。これは、$capture と $lambda または -> を組み合わせた式と等価です。
$capture は、その括弧内において、引数で指定されたシンボルを括弧内で定義される関数およびラムダ式のスコープに引き渡します。指定されたシンボルでアクセスされる変数は、関数およびラムダ式の中から参照および変更が可能です。

Liyadでは上述の文法を取りますが、他の言語においてはどのような文法を取るのか調べてみました。

Liyad

($let fn ($local ((counter 0))
    (|-> () use (counter) ($set counter (+ counter 1))) ))

(fn)

クロージャーにキャプチャーさせる変数を明示することで、 $local のスコープにアクセスできます。
原則、関数内部からは自身の関数スコープとグローバルスコープ以外にアクセスできません。
但し、 $defun はスコープに影響されません (常にグローバルです)。
Liyadは Lisp-2 であるため、 $defun された関数の名前空間と $let で定義される変数の名前空間は独立しています。

Liyadでは、通常、実行時のスタックでしかスコープを管理していませんが、字句解析時に上記オペレーターによってキャプチャーされたシンボルがある場合は、該当スコープへの参照を束縛させるようにしています。

Common Lisp

(setf fn (let ((counter 0))
    (lambda () (incf counter)) ))

(fn)

特に意識することなく、let のスコープから抜けた後、fn を通して let のスコープにアクセスできます。
すべてのラムダ式は、字句解析時のスコープ(レキシカルスコープ)を記憶しています。

JavaScript

let fn = void 0;
{
    let counter = 0;
    fn = () => ++counter;
}

fn();

こちらも、自動的にブロックスコープにアクセスしています。
Common Lisp同様、すべてのラムダ式は、字句解析時のスコープ(レキシカルスコープ)を記憶しています。
他の例と記述を合わせて、即時関数で書くと次のようになります。

const fn = (() => {
    let counter = 0;
    return (() => ++counter);
})();

fn();

Python

def makeFn():
    counter = 0
    def inner():
        nonlocal counter
        counter = counter + 1
        return counter
    return inner
fn = makeFn()

fn()

クロージャー内で外側の変数について値を変更するためには、nonlocal で明示的に示す必要があります。

PHP

<?php

$fn = (function() {
    $counter = 0;
    return (function() use (&$counter) {
        return ++$counter;
    });
})();

$fn();

use でキャプチャーする変数を指定する必要があります。

C＃

using System;
namespace MyApp
{
    public class MyClass 
    {
        public static Func<int> MakeFn()
        {
            int counter = 0;
            return () => ++counter;
        }

        static void Main(string[] args)
        {
            var fn = MakeFn();
            fn();
        }
    }
}

Java

Javaのクロージャーは「パチモン」と謂われています。

public class MyClass {
    public static Supplier<Int> makeFn() {
        final int[] counter = {0};
        return () -> { return ++(counter[0]); };
    }

    public static int main(String[] args) {
        Supplier<Int> fn = makeFn();
        fn();
    }
}

final または、実質的に final (初期化後、代入されているオブジェクト参照またはプリミティブ値が変更されない) ことが、クロージャーに変数を引き渡せる条件となっています。
つまり、実装としてはスコープを渡しているのではなく、単に見えない引数として渡しているということです(つまり、関数の部分適用ですよね)。

クロージャーの定義は、関数の定義された環境(静的スコープ)の変数への 参照を束縛 していることなので「パチモン」と謂われるわけです。

ただ、変数への再代入を認めないタイプの関数型言語では、部分適用による新しい関数の生成、つまり 値の束縛 による環境の引き渡しをクロージャーであるとされる場合もあるので、これが絶対にクロージャーではないとも言えないですね。

C++

C++11 でラムダ式とクロージャーをサポートしたんですね (最近、C++ 書いてないので…)。

#include <functional>
int counter = 0;
std::function<int()> fn = [&counter] () -> { return ++counter; };

int main(int argc, char* argv[]) {
    fn();
}

変数のキャプチャーと動作(コピーor参照)を指定する必要があります。
クロージャーを作ったからと言って、関数スコープの寿命が変更されるわけではないので、auto変数を参照した場合、スコープを抜けた後の動作は未定義です。

#include <functional>

std::function<int()> makeFn() {
    int counter = 0;
    return [&counter] () -> { return ++counter; };
}

int main(int argc, char* argv[]) {
    auto fn = makeFn();
    fn(); // 未定義!
}

参考

2018-10-16

🚧RawGitからjsDelivrへの切り替え🚧

テクノロジー development

Qiitaに書きましたが、RawGitが終了する模様です😿

最近作った、Ménneu Markdown Notebookで使っていたので、参照先をjsDelivrに切り替えました。
記事も直さないと…

2018-10-14

進行中のプロジェクト

テクノロジー development

現在、私の進めているプロジェクトの概要と当面のゴールについて説明したいと思います。

Ménneu

f:id:shellyln:20181014170720p:plain:w150

Markdownやhtmlのドキュメントテンプレートから、動的にドキュメント生成するためのCLIおよびAPIです。

ドキュメントはhtml、画像、pdfとして出力できます。

後述の RedAgate によるコンポーネントを、LispによるJSX記法(=LSX)を使って配置してドキュメントをデザインします。

ゴール

使い勝手の向上
- フラグメントのインポート
- 一括処理への考慮
可視化コンポーネントの追加

Liyad

f:id:shellyln:20181014170756p:plain:w150

独自DSLを作成するためのLisp インタープリター実装です。
DSLを作る上で必要なホスト側関数を組み込めるように、APIが提供されています。

上述 LSXのリファレンス実装も提供しています。

ゴール

~~クロージャー(関数閉包)の実装~~
- v0.0.13 で対応済み!
高速化
- 現状、関数の呼び出しコストが高いです。

RedAgate

f:id:shellyln:20181014170806p:plain:w150

静的ドキュメント専用のhtmlドキュメントをレンダリングするライブラリーです。
最も簡単に説明すると、Reactクローンです。
ただし、非同期リソースの取得・生成を待つ機構を持っていて、例えば、画像を取得して出力のhtmlに埋め込むことができます。
また、SVGをHTML5 Canvas API経由で操作する仕組みも持っています。
すべて、サーバー側／クライアント側問わずに動作します。

ゴール

コンポーネントの追加・改善

2018-10-14

ブログ作りました

最近、Qiitaなどで投稿していましたが、少し、自由な内容でも書いていきたいと思い、ブログを作ってみました。

技術のこと、現在進めているプロジェクトのこと、ポエムや雑記を書き残せたら、と思っています。

生暖かく見守ってもらえたら嬉しいです。