lqt0223

/*
  parsing arithmetic expressions containing 1 digit integers as operands
  and '+','-','*','/' as operators

  context free grammar for arithmetic expressions with left-recursion eliminated:
  - expr -> term + expr | term - expr | term
  - term -> factor * term | factor / term | factor
  - factor -> num | ( expr )
*/

lqt0223

This gist contains the implmentation of a eval-apply metacircular evaluator for Lisp.

Brief introduction on the following files:

test.js       - where you play with the evaluator
index.js      - where the global environment is set and the AST is constructed and evaulated
env.js        - the data structure for environment used in evaluation
parse.js      - tokenizing and parsing Lisp code
eval.js       - where the eval / apply mechanisms are implemented
primitives.js - where some primitive values and procedures of Lisp language are implemented

lqt0223

var curry = (f) => {
  var argc = f.length
  var _curry = (fn) => {
    return (...args) => {
      if (args.length == argc) {
        return fn(...args)
      } else {
        return fn.bind(null, ...args)
      }
    }

lqt0223

// the backtracking (one kind of recursion) code paradigm: 
// - build a helper function with extra arguments to pass on choices and other useful information during recursive calls
// - in the helper function, the base case is for handling the result after series of choices
// - in the helper function, the recursive case is usually in the 'choose-explore-unchoose' pattern

function queen(size) {
  var result = queenHelper(size, [], [])
  return result
}

lqt0223

function queen(n) {
  // a array of numerical sequence from 0 to n - 1
  var sequence = enumerateInterval(0, n - 1)
  // returns the sub-solution for n-queen's problem while placing k(k < n) queens on the first k rows of the board
  function queenRow(k) {
    if (k == 0) {
      return [[]]
    } else {
      var restQueens = queenRow(k - 1)
      // just place the nth queen on any place of the new row to generate a bunch of new solutions

lqt0223

// constructors
function isNull(stream) {
  return Array.isArray(stream) && stream.length == 0
}

function isAllNull(streams) {
  return streams.every((stream) => isNull(stream))
}

function isSomeNull(streams) {

lqt0223

// This gist shows implementation of the Promise class in JavaScript. The implementation includes:
// 1. **basic**: a promise is an object that receives a function as parameter. When created, the function will be fired immediately
// 2. **job scheduling**: a promise is 'Thenable' and can call 'Promise.prototype.then' to schedule deferred jobs. When the promise is resolved, the callback in 'then' body will be called and the resolved value will be retrieved
// 3. **chaining**: a 'then' body will return a new Promise, which is also 'Thenable'. Once the first promise is fired, the promise chain will do the resolution towards its end automatically
// 4. **status control**: a promise has a initial state of 'pending', and will shift either to 'resolved' or 'rejected'
// 5. **error handling**: Promise.prototype.then' with error handler & Promise.prototype.catch' are ways to handle errors
// 6. **error propagation**: a rejected reason will be propagated to the nearest error handler or catch body. Jobs between the reje

lqt0223

// arithmetic expression (in infix notation) parsing & evaluation & transformation into prefix notation
// and implementation of algebraic expression AST transformation rules (derivative & simplification)
// * for numerical values, only integer is supported

var TOKEN_TYPE = {
  'op': Symbol('op'),
  'num': Symbol('num'),
  'var': Symbol('var'),
  'paren': Symbol('paren')
}

lqt0223

// solving 'longest common sequence' problem using dynamic programming
// will return lcs, and ses (shortest edit script) for the two string arguments
function dp_lcs(str1, str2) {
  var len1 = str1.length
  var len2 = str2.length
  var lcsLengths = initMatrix(len1, len2)

  fill(lcsLengths, str1, str2)

  var info = backtrack(lcsLengths, str1, str2)

lqt0223

// ------ data structure: pair ------ //

// constructor for compound data structure: pair
function cons(a, b) {
  var pair = []
  pair[0] = a
  pair[1] = b
  return pair
}