如何将嵌套函数调用树转换为状态机? [英] How to convert nested function call tree to state machine?

查看：26
本文介绍了如何将嵌套函数调用树转换为状态机?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

假设你有这样的系统:

const input = [0, [1, 2, [3, 4, [8, 9], 6, 7], 4], [5, 6, 7], 3, 4, [8, 9], 6, 7, [1], 9]const 输出 = 解析(输入)console.log(output.join('-'))函数解析(输入){常量输出 = []迭代(输入，值 => {check(() => isArray(value),() =>{//是数组const 孩子 = 解析(值)output.push(...儿童)},() =>{//不是数组check(() => isEven(value), () => {输出.推(值)})})})返回输出}函数 isArray(value) {返回 Array.isArray(value)}函数是偶数(值){返回值 % 2 == 0}功能检查(条件，成功，失败){如果(条件())成功()否则如果(失败)失败()}函数迭代(数组，块){array.forEach(块)}

本质上这就像一个树语法:

parse =迭代输入，值 =>检查 isArray(value)调用解析(值)检查 isNumber(value)检查 isEven(值)推(值)

你可以把它想象成 JSON:

<代码>{类型:'功能'，名称:'解析'，孩子们: [{类型:'迭代'，孩子们: [{类型:'检查'，检查器:'isArray'，孩子们: [{类型:'呼叫'，功能:'解析'}]},{类型:'检查'，检查器:'isNumber'，孩子们: [{类型:'检查'，检查器:'isEven'，孩子们: [{类型:'推'，}]}]}]}]}

<块引用>

基本上我真正的问题是我在自定义编程语言中有这样的 JSON，我想将它转换为状态机器而不是像我们这样的嵌套/递归函数调用从这篇文章开始.

所以我的问题是，如何重写本文开头的递归函数系统，使其使用状态机?

<块引用>

您不必一路走来从JSON(在这个例子中是不完整的，因为我没有一个好的简化的示例).

相反，如果您能展示如何从本文开头将这个递归或嵌套函数系统重写为状态机，那就足够了.

我的想象是这样的:

let transitions = [功能1，功能2，...]let transition = transitions[0]//理论上的启动函数让 currentInput = 输入让 someStack = []而(过渡){[currentInput, transition] = transition(someStack, currentInput)}

但是我很快就会迷失在如何跟踪我们在输入中所处的位置，以及如何处理迭代(如在 iterator 中)或;if 语句"(如check).

函数迭代(输入){//你不能在这里进行递归调用，//因为原来的 while 循环应该处理这个.//但是，我们应该返回一些对当前输入的引用，//以及下一个转换.}

如果必须选择一种语言，那么在 JavaScript 中执行此操作将是最简单的.但它甚至可以用伪代码来完成，以大致展示它是如何完成的.

解决方案

正如前面所说，你不能使用状态机，但如果我理解你的例子，你就不需要状态机.您想要一种从数据构造谓词的方法；这些谓词适用于复杂的不规则数据结构.

  • 其中一些谓词会产生副作用.
  • 其中一些谓词将传播对数据子部分的操作.
  • 我假设您有一种有限的方式来表达您的谓词，因此您可以组合一组有限的谓词来获得您想要的谓词.

如果 Java 流有一个递归"的 flatMap，那就足够了.

我是 Java 专家，所以我将尝试用 Java 编写.主要思想是有一个 Op 功能接口，将一个对象映射到一个对象列表中.

然后你只需计算一个固定点.

interface Op{ List的(对象 t)；}A类{Op push(List res){return o->{res.add(o);return List.of();};}操作 isArray(){返回 t->{if (!(t instanceof Object[] os)){ return List.of();}返回 List.of(os);};}Op isNumber(Op more){返回 t->{if (!(t instanceof Integer i)){ return List.of();}返回 more.of(i);};}Op isEven(Op more){返回 t->{if (!(t instanceof Integer i) || i%2==1){ return List.of();}返回 more.of(i);};}void engine1(List query,Object input){//非递归Listedge=new ArrayList<>();ListnextEdge=new ArrayList<>();边缘添加(输入)；while(!edge.isEmpty()){for(var e:edge){for(var f:query){nextEdge.addAll(f.of(e));}}边缘=下一个边缘；nextEdge=new ArrayList<>();}}无效示例1(){列表<对象>res=new ArrayList();列表<操作>查询=List.of(isArray(),isEven(push(res)));对象输入=新对象[]{1,2,新对象[]{3,4},5,6};引擎1(查询，输入)；System.out.println(res);}public static void main(String[]arg) {new A().example1();//这将打印2,6,4}}
从您的问题中不清楚您是否可以接受此订单.即访问副作用是广度优先如果没有，我想我可以得到 Deapth First 的订单，但必须在 12 小时左右，因为现在我的时区已经晚了.
Say you have this sort of system:






const input = [0, [1, 2, [3, 4, [8, 9], 6, 7], 4], [5, 6, 7], 3, 4, [8, 9], 6, 7, [1], 9]
const output = parse(input)
console.log(output.join('-'))

function parse(input) {
  const output = []
  iterate(input, value => {
    check(() => isArray(value),
      () => { // yes array
        const children = parse(value)
        output.push(...children)
      },
      () => { // not array
        check(() => isEven(value), () => {
          output.push(value)
        })
      })
  })
  return output
}

function isArray(value) {
  return Array.isArray(value)
}

function isEven(value) {
  return value % 2 == 0
}

function check(condition, success, failure) {
  if (condition()) success()
  else if (failure) failure()
}

function iterate(array, block) {
  array.forEach(block)
}








Essentially this is like a tree grammar:
parse =
  iterate input, value =>
    check isArray(value)
      call parse(value)
    check isNumber(value)
      check isEven(value)
        push(value)

You can imagine this as JSON:
{
  type: 'function',
  name: 'parse',
  children: [
    {
      type: 'iterate',
      children: [
        {
          type: 'check',
          checker: 'isArray',
          children: [
            {
              type: 'call',
              function: 'parse'
            }
          ]
        },
        {
          type: 'check',
          checker: 'isNumber',
          children: [
            {
              type: 'check',
              checker: 'isEven',
              children: [
                {
                  type: 'push',
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}





Basically my real problem is I have something like this JSON in a custom programming language, and I want to convert it into a state
machine rather than the nested/recursive function calls like we
started with in this post.


So my question is, how can you rewrite the recursive function system from the beginning of this post, such that it uses a state machine instead?


You don't have to go all the way and make the state machine from the
JSON (which in this example is incomplete, as I don't have a good
example to simplify from).


Instead, just if you could show how to rewrite this recursive or nested function system from the beginning of this post as  a state machine, that would be all.


What I am imagining is something like this:
let transitions = [
  function1,
  function2,
  ...
]

let transition = transitions[0] // the start function in theory
let currentInput = input
let someStack = []
while (transition) {
  [currentInput, transition] = transition(someStack, currentInput)
}

But I quickly get lost on how I would keep track of the position we are at in the input, as well as how to handle things like iteration (as in the iterator), or "if statements" (as in the check).
function iterate(input) {
  // you can't do the recursive call here,
  // as the original while loop should handle this.
  // but, we should return some reference to the current input,
  // as well as the next transition.
}

If a language must be chosen then doing this in JavaScript would be simplest. But it can even be done in pseudocode to show generally how it's done.
 解决方案 
As it was said, you can not use a state machine, but if I understand your example, you do not need one.
You want a way to construct predicates from data;
those predicates will work on a complex irregular data structure.


    

  • Some of those predicates will have side effects.
    • 

  • Some of those predicates will propagate the operation on sub parts of the data.
    • 

  • I'm assuming you have a finite way to express your predicates, so you can compose a finite set of predicates to obtain your desired ones.
    • 



If Java streams had a 'recursive' flatMap, that would be enough.


I'm a Java expert so I will write an attempt in Java.
The main idea is to have an Op functional interface that maps an Object into a list of objects.


Then you just compute a fix-point.
interface Op{ List<Object> of(Object t); }
class A{
  Op push(List<Object> res){
    return o->{res.add(o);return List.of();};
    }  
  Op isArray(){
    return t->{
      if (!(t instanceof Object[] os)){ return List.of(); }
      return List.of(os);
      };
    }
  Op isNumber(Op more){
    return t->{
      if (!(t instanceof Integer i)){ return List.of(); }
      return more.of(i);
      };
    }
  Op isEven(Op more){
    return t->{
      if (!(t instanceof Integer i) || i%2==1){ return List.of(); }
      return more.of(i);
      };
    }
  void engine1(List<Op> query,Object input){//not recursive
    List<Object>edge=new ArrayList<>();
    List<Object>nextEdge=new ArrayList<>();
    edge.add(input);
    while(!edge.isEmpty()){
      for(var e:edge){
        for(var f:query){
          nextEdge.addAll(f.of(e));
          }
        }
      edge=nextEdge;
      nextEdge=new ArrayList<>();
      }
    }
  void example1() {
    List<Object> res=new ArrayList<>();
    List<Op> query=List.of(isArray(),isEven(push(res)));
    Object input= new Object[]{1,2,new Object[]{3,4},5,6};
    engine1(query,input);
    System.out.println(res);
    }
  public static void main(String[]arg) {
    new A().example1();//this would print 2,6,4
    }
  }

It is unclear from your question if  this order is acceptable for you.
That is, the visit side effects are Breadth First
If not, I think I can get the Deapth First order instead, but it will have to be in 12 hours or so, since it is now getting late in my timezone.


                        
这篇关于如何将嵌套函数调用树转换为状态机?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

                        
                    
                    

                        查看全文
                    

                
				

                            
                        

                

            
        
        

            



        

        

            
相关文章

            
        

        

            



        

    
    

        

            
前端开发最新文章

            
        

        

            

                热门教程
            

            
        

        

            

                热门工具
            

            
        

        
    



    


    

        

            登录
            关闭
        

        

            

                扫码关注1秒登录
            

            

                
            

            

                
                
            

            

                发送“验证码”获取
                |
                15天全站免登陆