javascript - 存在输出问题的 Lambda 演算解释器

Question

以下代码是 lambda 演算解释器。

我无法让程序将代码结果打印到 console.log。

  class Token {
    // type should be one of the valid token types listed 
    //  below, and value is an optional value that can carry
    //  any extra information necessary for a given token type. 
    //  (e.g. the matched string for an identifier)
  constructor(type, value) {
    this.type = type;
    this.value = value;
  }
};

[
  'EOF', // we augment the tokens with EOF, to indicate the end of the input.
  'LAMBDA',
  'LPAREN',
  'RPAREN',
  'LCID', //lower case identifier
  'DOT', //the . symbol
].forEach(token => Token[token] = token);

class Lexer {
  `enter code here`
  constructor(input) {
    this._input = input;
    this._index = 0;
    this._token = undefined;
    this._nextToken();
  }

  //Return the next char of the input or '\0' if we've reached the end
  _nextChar() {
    if (this._index >= this._input.length) {
      return '\0';
    }

    return this._input[this._index++];
  }

  //Set this._token based on the remaining of the input
  //This method is meant to be private, it doesn't return a token, just sets
  //up the state for the helper functions.
  _nextToken() {
    let c;
    do {
      c = this._nextChar();
    } while (/\s/.test(c));

    switch (c) {
    case 'λ':
    case '\\':
      this._token = new Token(Token.LAMBDA);
      break;

    case '.':
      this._token = new Token(Token.DOT);
      break;

    case '(':
      this._token = new Token(Token.LPAREN);
      break;

    case ')':
      this._token = new Token(Token.RPAREN);
      break;

    case '\0':
      this._token = new Token(Token.EOF);
      break;

    default:
      if (/[a-z]/.test(c)) {
        let str = '';
        do {
          str += c;
          c = this._nextChar();
        } while (/[a-zA-Z]/.test(c));

        // put back the last char which is not part of the identifier
        this._index--;

        this._token = new Token(Token.LCID, str);
      }
      /*else {
                   this.fail();
                 }*/
    }
  }

  //Assert that the next token has the given type, return it, and skip to the
  //next token.   
  token(type) {
    if (!type) {
      return this._token;
    }

    const token = this._token;
    this.match(type);
    return token;
  }

  //throw an unexpected token error - ideally this would print the source location
  /*fail() {
    throw new Error(`Unexpected token at offset ${this._index}`);
  }*/

  //returns a boolean indicating whether the next token has the given type.
  next(type) {
    return this._token.type == type;
  }

  //Assert that the next token has the given type and skip it.
  match(type) {
    if (this.next(type)) {
      this._nextToken();
      return;
    }
    //console.error(`${this._index}: Invalid token: Expected '${type}' found '${this.token().type}'`);
    //throw new Error('Parse Error');
  }

  //Same as `next`, but skips the token if it matches the expected type.
  skip(type) {
    if (this.next(type)) {
      this._nextToken();
      return true;
    }
    return false;
  }
}

class Parser {
  constructor(lexer) {
    this.lexer = lexer;
  }

  parse() {
    const result = this.term();

    // make sure we consumed all the program, otherwise there was a syntax error
    this.lexer.match(Token.EOF);

    return result;
  }

  // Term ::= LAMBDA LCID DOT Term
  //        | Application
  term() {
    if (this.lexer.skip(Token.LAMBDA)) {
      const id = new Identifier(this.lexer.token(Token.LCID).value);
      this.lexer.match(Token.DOT);
      const term = this.term();
      return new Abstraction(id, term);
    } else {
      return this.application();
    }
  }

  // Application ::= Atom Application'
  application() {
    let lhs = this.atom();

    // Application' ::= Atom Application'
    //                | ε
    while (true) {
      const rhs = this.atom();
      if (!rhs) {
        return lhs;
      } else {
        lhs = new Application(lhs, rhs);
      }
    }
  }

  // Atom ::= LPAREN Term RPAREN
  //        | LCID
  atom() {
    if (this.lexer.skip(Token.LPAREN)) {
      const term = this.term(Token.RPAREN);
      this.lexer.match(Token.RPAREN);
      return term;
    } else if (this.lexer.next(Token.LCID)) {
      const id = new Identifier(this.lexer.token(Token.LCID).value);
      return id;
    } else {
      return undefined;
    }
  }
}

class Abstraction {
  //param here is the name of the variable of the abstraction. Body is the
  //subtree  representing the body of the abstraction.

  constructor(param, body) {
    this.param = param;
    this.body = body;
  }

  toString() {
    return `(λ${this.param.toString()}. ${this.body.toString()})`;
  }
}

class Application {
  //(lhs rhs) - left-hand side and right-hand side of an application.
  constructor(lhs, rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  toString() {
    return `${this.lhs.toString()} ${this.value.toString()}`;
  }
}

class Identifier {
  //name is the string matched for this identifier.
  constructor(name) {
    this.name = name;
  }

  toString() {
    return this.name;
  }
}

const isValue = node => node instanceof Abstraction;

const eval = (ast, context = {}) => {
  while (true) {
    if (ast instanceof Application) {
      if (isValue(ast.lhs) && isValue(ast.rhs)) {
        //if both sides of the application are values we can proceed and
        //actually rhs value to the param name and evaluate the lhs
        //abstraction's body
        context[ast.lhs.param.name] = ast.rhs;
        ast = eval(ast.lhs.body, context);
      } else if (isValue(ast.lhs)) {
        /*We should only evaluate rhs once lhs has been reduced to a value
        here we have to clone the context to prevent the bindings that might
        be defined while evaluating the body of rhs from leaking to the top
        context. This way, once we finish evaluating rhs we automatically
        "pop" the child context, and resto the original context.*/
        ast.rhs = eval(ast.rhs, Object.assign({}, context));
      } else {
        //Keep reducing lhs until it becomes a value
        ast.lhs = eval(ast.lhs, context);
      }
    } else if (ast instanceof Identifier) {
      //Once we find an identifier, we simply replace it with the appropriate bound value.
      ast = context[ast.name];
    } else {
      //`ast` is an abstraction, and therefore a value. That means we're done
      //reducing it, and this is the result of the current evaluation.

      return ast;
    }
  }
};

const source = '(λx. λy. x) (λx. x) (λy. y)';

// wire all the pieces together
const lexer = new Lexer(source);
const parser = new Parser(lexer);
const ast = parser.parse();
const result = eval(ast);

//stringify the resulting node and print it
console.log(result.toString());

Answer 1

class Lexer {
  `enter code here`

带来错误，因为它将字符串视为意外的模板字符串。除此之外，它应该可以完美运行(按运行代码片段将(λx.x)写入控制台):

  class Token {
    // type should be one of the valid token types listed 
    //  below, and value is an optional value that can carry
    //  any extra information necessary for a given token type. 
    //  (e.g. the matched string for an identifier)
  constructor(type, value) {
    this.type = type;
    this.value = value;
  }
};

[
  'EOF', // we augment the tokens with EOF, to indicate the end of the input.
  'LAMBDA',
  'LPAREN',
  'RPAREN',
  'LCID', //lower case identifier
  'DOT', //the . symbol
].forEach(token => Token[token] = token);

class Lexer {
  constructor(input) {
    this._input = input;
    this._index = 0;
    this._token = undefined;
    this._nextToken();
  }
  //Return the next char of the input or '\0' if we've reached the end
  _nextChar() {
    if (this._index >= this._input.length) {
      return '\0';
    }

    return this._input[this._index++];
  }

  //Set this._token based on the remaining of the input
  //This method is meant to be private, it doesn't return a token, just sets
  //up the state for the helper functions.
  _nextToken() {
    let c;
    do {
      c = this._nextChar();
    } while (/\s/.test(c));

    switch (c) {
    case 'λ':
    case '\\':
      this._token = new Token(Token.LAMBDA);
      break;

    case '.':
      this._token = new Token(Token.DOT);
      break;

    case '(':
      this._token = new Token(Token.LPAREN);
      break;

    case ')':
      this._token = new Token(Token.RPAREN);
      break;

    case '\0':
      this._token = new Token(Token.EOF);
      break;

    default:
      if (/[a-z]/.test(c)) {
        let str = '';
        do {
          str += c;
          c = this._nextChar();
        } while (/[a-zA-Z]/.test(c));

        // put back the last char which is not part of the identifier
        this._index--;

        this._token = new Token(Token.LCID, str);
      }
      /*else {
                   this.fail();
                 }*/
    }
  }

  //Assert that the next token has the given type, return it, and skip to the
  //next token.   
  token(type) {
    if (!type) {
      return this._token;
    }

    const token = this._token;
    this.match(type);
    return token;
  }

  //throw an unexpected token error - ideally this would print the source location
  /*fail() {
    throw new Error(`Unexpected token at offset ${this._index}`);
  }*/

  //returns a boolean indicating whether the next token has the given type.
  next(type) {
    return this._token.type == type;
  }

  //Assert that the next token has the given type and skip it.
  match(type) {
    if (this.next(type)) {
      this._nextToken();
      return;
    }
    //console.error(`${this._index}: Invalid token: Expected '${type}' found '${this.token().type}'`);
    //throw new Error('Parse Error');
  }

  //Same as `next`, but skips the token if it matches the expected type.
  skip(type) {
    if (this.next(type)) {
      this._nextToken();
      return true;
    }
    return false;
  }
}

class Parser {
  constructor(lexer) {
    this.lexer = lexer;
  }

  parse() {
    const result = this.term();

    // make sure we consumed all the program, otherwise there was a syntax error
    this.lexer.match(Token.EOF);

    return result;
  }

  // Term ::= LAMBDA LCID DOT Term
  //        | Application
  term() {
    if (this.lexer.skip(Token.LAMBDA)) {
      const id = new Identifier(this.lexer.token(Token.LCID).value);
      this.lexer.match(Token.DOT);
      const term = this.term();
      return new Abstraction(id, term);
    } else {
      return this.application();
    }
  }

  // Application ::= Atom Application'
  application() {
    let lhs = this.atom();

    // Application' ::= Atom Application'
    //                | ε
    while (true) {
      const rhs = this.atom();
      if (!rhs) {
        return lhs;
      } else {
        lhs = new Application(lhs, rhs);
      }
    }
  }

  // Atom ::= LPAREN Term RPAREN
  //        | LCID
  atom() {
    if (this.lexer.skip(Token.LPAREN)) {
      const term = this.term(Token.RPAREN);
      this.lexer.match(Token.RPAREN);
      return term;
    } else if (this.lexer.next(Token.LCID)) {
      const id = new Identifier(this.lexer.token(Token.LCID).value);
      return id;
    } else {
      return undefined;
    }
  }
}

class Abstraction {
  //param here is the name of the variable of the abstraction. Body is the
  //subtree  representing the body of the abstraction.

  constructor(param, body) {
    this.param = param;
    this.body = body;
  }

  toString() {
    return `(λ${this.param.toString()}. ${this.body.toString()})`;
  }
}

class Application {
  //(lhs rhs) - left-hand side and right-hand side of an application.
  constructor(lhs, rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  toString() {
    return `${this.lhs.toString()} ${this.value.toString()}`;
  }
}

class Identifier {
  //name is the string matched for this identifier.
  constructor(name) {
    this.name = name;
  }

  toString() {
    return this.name;
  }
}

const isValue = node => node instanceof Abstraction;

const eval = (ast, context = {}) => {
  while (true) {
    if (ast instanceof Application) {
      if (isValue(ast.lhs) && isValue(ast.rhs)) {
        //if both sides of the application are values we can proceed and
        //actually rhs value to the param name and evaluate the lhs
        //abstraction's body
        context[ast.lhs.param.name] = ast.rhs;
        ast = eval(ast.lhs.body, context);
      } else if (isValue(ast.lhs)) {
        /*We should only evaluate rhs once lhs has been reduced to a value
        here we have to clone the context to prevent the bindings that might
        be defined while evaluating the body of rhs from leaking to the top
        context. This way, once we finish evaluating rhs we automatically
        "pop" the child context, and resto the original context.*/
        ast.rhs = eval(ast.rhs, Object.assign({}, context));
      } else {
        //Keep reducing lhs until it becomes a value
        ast.lhs = eval(ast.lhs, context);
      }
    } else if (ast instanceof Identifier) {
      //Once we find an identifier, we simply replace it with the appropriate bound value.
      ast = context[ast.name];
    } else {
      //`ast` is an abstraction, and therefore a value. That means we're done
      //reducing it, and this is the result of the current evaluation.

      return ast;
    }
  }
};

const source = '(λx. λy. x) (λx. x) (λy. y)';

// wire all the pieces together
const lexer = new Lexer(source);
const parser = new Parser(lexer);
const ast = parser.parse();
const result = eval(ast);

//stringify the resulting node and print it
console.log(result.toString());