Question

我在F#中写了一些小字符串解析功能- 以便让F# 感觉更好, 并看看如何解决这些任务。我试图在字符串中走过一条线, 通过递归搜索具体字符。

逻辑确实有效,但释放结构(优化打开)产生的 IL 代码在我看来确实有点奇怪。所以我想在F#里有更好的写法。

这就是分析函数看起来像的部分 :

let eatTag (input : string) index =
    let len = input.Length
    let nothing = 0, null, TagType.Open

    // more functions used in the same way
    // ...

    let rec findName i =
        if i >= len then nothing
        else
            let chr = input.[i]
            if isWhitespace chr then
                findName (i+1)
            elif chr =  /  then
                getName (i+1) (i+1) true
            else getName (i+1) i false

    let rec findStart i =
        if i >= len then nothing
        elif input.[i] =  <  then findName (i+1)
        else findStart (i+1)

    findStart index

查找 Start 函数生成的 IL 代码看起来像 :

 // loop start
    IL_0000: nop
    IL_0001: ldarg.2
    IL_0002: ldarg.1
    IL_0003: blt.s IL_000e

    IL_0005: ldc.i4.0
    IL_0006: ldnull
    IL_0007: ldc.i4.0
    IL_0008: newobj instance void class [mscorlib]System.Tuple`3<int32, string, valuetype TagType>::.ctor(!0, !1, !2)
    IL_000d: ret

    IL_000e: ldarg.0
    IL_000f: ldarg.2
    IL_0010: call instance char [mscorlib]System.String::get_Chars(int32)
    IL_0015: ldc.i4.s 60
    IL_0017: bne.un.s IL_0024

    IL_0019: ldarg.0
    IL_001a: ldarg.1
    IL_001b: ldarg.2
    IL_001c: ldc.i4.1
    IL_001d: add
    IL_001e: call class [mscorlib]System.Tuple`3<int32, string, valuetype TagType> findName@70(string, int32, int32)
    IL_0023: ret

    IL_0024: ldarg.0
    IL_0025: ldarg.1
    IL_0026: ldarg.2
    IL_0027: ldc.i4.1
    IL_0028: add
    IL_0029: starg.s i
    IL_002b: starg.s len
    IL_002d: starg.s input
    IL_002f: br.s IL_0000
// end loop

此函数的 C # 视图( ILSpy) 显示以下代码 - 这尤其是为什么我认为我在这里做错了事。显然, 函数参数是自己被指派的...!!

internal static Tuple<int, string, TagType> findStart@80(string input, int len, int i)
{
        while (i < len)
        {
                if (input[i] ==  < )
                {
                        return findName@70(input, len, i + 1);
                }
                string arg_2D_0 = input;
                int arg_2B_0 = len;
                i++;
                len = arg_2B_0;
                input = arg_2D_0;
        }
        return new Tuple<int, string, TagType>(0, null, TagType.Open);
}

同样的问题可以从以延续方式处理的其他功能中看出。任何关于我的行为或假设我错了的指点都会受到高度赞赏 :-)

Answer 1

这是尾巴呼叫消除。

删除尾巴调用和将尾巴调用到函数开始跳跃的过程。 (对应一个 , 而( true) {/code> 构造 ) 。



您看到相同任务的原因, 是为了保持语义与您正常调用函数相同。 几乎无法确定一个任务是否会有效影响另一个任务, 因此使用临时变量, 然后重新分配给它们 。

Answer 2

如前所述,编纂者在此情况下将递归函数变成非递归函数。只有在递归呼叫出现在“尾声”位置和函数自己调用时才可能。一般而言,编纂者有以下选项:

<强度 > compile 函数是一个循环 - 当函数调用本身且调用在尾声调用位置时。这是最有效的替代方法, 因为它消除了创建新堆叠框架, 并使用标准循环。
.tail call IL 指示 - 当调用尾号位置时,您调用不同的函数(例如,如果您使用 let recolfo () =... 和 bar () = < syntax) 宣布了两个相互递解的函数) 。这样可以避免创建新的堆叠框架(您不会得到堆叠溢溢出),但效率较低,因为 .tail call 指示在.NET 没有如此优化。
使用正常的递转重现 < / 坚固 >, < 坚固 > compile 使用正常的重现 < / 坚固 > - 当函数反复调用本身, 且 < em> 进行更多的计算时, 代码会使用标准的递转调来编译, 而不是使用 < em> later- later- call < / em > (需要为每次调用指定一个新的书架框架, 以便您得到堆叠溢溢) 。

(以你为例)第一种情况下的优化(以你为例)看起来是这样的:一般而言,尾部递归功能看起来是这样的:

let rec foo x = 
  if condition then 
    let x  = calculateNewArgument x // Run some computation
    foo x                           // (Tail-)recursively calls itself
  else 
    calculateResult x               // Final calculation in the branch that returns

代码被翻译成以下循环, 将参数存储为可变变量 :

let foo x = 
  let mutable x = x
  while condition do                // Check condition using current argument value
    x <- calculateNewArgument x     // Instead of recursion, run next iteration
  calculateResult x                 // Final calculation in the branch that returns

Answer 3

基本上, 而不是创造一个链类的链类

findstart(findstart(findstart(findstart.....

编译器转换为删除函数调用的循环。

这是""https://en.wikipedia.org/wiki/Tail_call" rel="nofollow">Tail呼叫消除 ,这是一个相当标准的功能性编程优化。这相当于将调派到一个函数的间接间接责任,低于调用产生新堆叠框架的新函数。

友情链接