Parsing simple scm from stdin

010-inc.scm

(((lambda (zero inc) (inc (inc zero)))
  (lambda (next zero) zero))
 (lambda (num next zero) (next (num next zero))))

README.md

$ chmod +x ./playtorial07.js
$ ./playtorial.js < 010-inc.scm
Result: 2
(zero => (inc => inc(inc(zero))))((next => (zero => zero)))((num => (next => (zero => next(num(next)(zero))))))

playtorial07.js

#!/usr/bin/env node

const nonsense =
  _any => {
    throw Error('nonsense')
  }

const compose =
  fun1 => fun2 => arg =>
    fun1(fun2(arg))

const pipe =
  fun1 => fun2 => arg =>
    fun2(fun1(arg))

const Pair = (() => {
  const make =
    first => second => pair =>
      pair(first)(second)

  const first =
    pair =>
      pair
        (first => _second =>
          first)

  const second =
    pair =>
      pair
        (_first => second =>
          second)

  return {
    make,
    first,
    second
  }
})()

const Logic = (() => {
  const truthful =
    truthful => _falseful =>
      truthful

  const falseful =
    _truthful => falseful =>
      falseful

  const and =
    pred1 => pred2 =>
      pred1(pred2)(pred1)

  const or =
    pred1 => pred2 =>
      pred1(pred1)(pred2)

  const not =
    pred =>
      pred(falseful)(truthful)

  const ifthenelse =
    pred => then_clause => else_clause =>
      pred(then_clause)(else_clause)

  const from_native =
    bool => {
      if (bool) {
        return truthful
      }
      else {
        return falseful
      }
    }

  const to_native =
    term =>
      term(true)(false)

  return {
    truthful,
    falseful,
    and,
    or,
    not,
    ifthenelse,
    from_native,
    to_native
  }
})()

const { truthful, falseful, or, not, and } = Logic
const to_bool = Logic.to_native

const Nat = (() => {
  const zero =
    _next => zero =>
      zero

  const fold =
    op => init => nat =>
      nat(op)(init)

  const is_zero =
    fold
      (_acc =>
        falseful)
      (truthful)

  const inc =
    nat => next => zero =>
      next
        (nat(next)(zero))

  const plus =
    nat1 => nat2 => next => zero =>
      nat1
        (next)
        (nat2(next)(zero))

  const plus_2 =
    nat1 => nat2 =>
      fold(inc)(nat2)(nat1)

  const mult =
    nat1 => nat2 => next => zero =>
      nat1
        (nat2(next))
        (zero)

  const mult_2 =
    nat1 => nat2 =>
      fold
        (acc =>
          plus(acc)(nat2))
        (zero)
        (nat1)

  const pow =
    nat1 => nat2 =>
      nat2(nat1)

  const pow_2 =
    nat1 => nat2 =>
      fold
        (acc =>
          mult(acc)(nat1))
        (inc(zero))
        (nat2)

  const dec =
    nat => next => zero =>
      nat
        (g => h => h(g(next)))
        (_any => zero)
        (same => same)

  const monus =
    nat1 => nat2 =>
      fold(dec)(nat1)(nat2)

  const leq =
    nat1 => nat2 =>
      is_zero
        (monus(nat1)(nat2))

  const eq =
    nat1 => nat2 =>
      and
        (leq(nat1)(nat2))
        (leq(nat2)(nat1))

  const from_native =
    num => {
      if (num === 0) {
        return zero
      }
      else {
        return inc(from_native(num - 1))
      }
    }

  const to_native =
    nat =>
      fold(num => num + 1)(0)(nat)

  return {
    zero,
    inc,
    dec,
    fold,
    plus,
    mult,
    pow,
    monus,
    is_zero,
    leq,
    eq,
    from_native,
    to_native
  }
})()

const List = (() => {
  const cons =
    Pair.make

  const head =
    Pair.first

  const tail =
    Pair.second

  const empty =
    _cons => empty =>
      empty

  const singletone =
    term =>
      cons(term)(empty)

  const fold =
    op => init => list => {
      const step =
        head => tail => init =>
          op
            (head)
            (tail(step)(init))

      return list
        (step)
        (init)
    }

  const map =
    op =>
      fold
        (elem => acc =>
          cons
            (op(elem))
            (acc))
        (empty)

  const filter =
    pred =>
      fold
        (elem => acc =>
          pred
            (elem)
            (cons(elem)(acc))
            (acc))
        (empty)

  const reverse =
    list =>
      fold
        (head => cont => tail =>
          cont
            (cons(head)(tail)))
        (x => x)
        (list)
        (empty)

  const append =
    list1 => list2 =>
      fold(cons)(list2)(list1)

  const concat =
    fold(append)(empty)

  const length =
    fold
      (_elem => acc =>
        Nat.inc(acc))
      (Nat.zero)

  const is_empty =
    list =>
      list
        (_head => _tail => _init =>
          falseful)
        (truthful)

  const is_empty_2 =
    list =>
      Nat.is_zero
        (length(list))

  const is_member =
      elem1 =>
        fold
          (elem2 => acc =>
            or
              (Nat.eq(elem1)(elem2))
              (acc))
          (falseful)

  const from_native =
    array => {
      if (array.length === 0) {
        return empty
      }
      else {
        const elem =
          array[0]

        const rest =
          from_native(array.slice(1))

        return cons(elem)(rest)
      }
    }

  const to_native =
    fold
      (elem => acc =>
        [elem].concat(acc))
      ([])

  return {
    cons,
    head,
    tail,
    empty,
    singletone,
    fold,
    map,
    filter,
    reverse,
    append,
    concat,
    is_empty,
    is_member,
    length,
    from_native,
    to_native
  }
})()

const Char = (() => {
  const eq =
    Nat.eq

  const is_white =
    char =>
      List.is_member
        (char)
        (Charlist.from_native(' \n'))

  const new_line =
    Nat.from_native(10)

  const space =
    Nat.from_native(32)

  const open_paren =
    Nat.from_native(40)

  const close_paren =
    Nat.from_native(41)

  return {
    eq,
    is_white,
    new_line,
    space,
    open_paren,
    close_paren
  }
})()

const Charlist = (() => {
  const eq =
    list1 => list2 => {
      const step =
        chars1 => chars2 => {
          const left_is_empty_not_right =
            and
              (List.is_empty(chars1))
              (not(List.empty(chars2)))

          const right_is_empty_not_left =
            and
              (not(List.is_empty(chars1)))
              (List.is_empty(chars2))

          const condition1 =
            or(left_is_empty_not_right)(right_is_empty_not_left)

          const condition2 =
            and
              (List.is_empty(chars1))
              (List.is_empty(chars2))

          if (to_bool(condition1)) {
            return falseful
          }
          else if (to_bool(condition2)) {
            return truthful
          }
          else {
            return and
            (Char.eq
             (List.head(chars1))
             (List.head(chars2)))

            (step
             (List.tail(chars1))
             (List.tail(chars2)))
          }
        }

      return step(list1)(list2)
    }

  const from_native =
    string => {
      const charlist =
        string
          .split('')
          .map(char => char.charCodeAt(0))
          .map(num => Nat.from_native(num))

    return List.from_native(charlist)
  }

  const to_native =
    List.fold
      (char => acc =>
        String.fromCharCode(Nat.to_native(char)) + acc)
      ('')

  return {
    eq,
    from_native,
    to_native
  }
})()

const IO = {
  input: function(handler) {
    const stdin = process.stdin
    const chunks = []

    stdin.resume()
    stdin.setEncoding('ascii')

    stdin
      .on('data', chunk => {
        chunks.push(chunk)
      })
      .on('end', () => {
        const input = chunks.join('')
        handler(input)
      })
  }
}

const Tag = (() => {
  const init =
    Nat.zero

  const next =
    Nat.inc

  const eq =
    Nat.eq

  const tag_with =
    Pair.make

  const untag =
    Pair.second

  const tagged_with =
    tag => term =>
      eq
       (Pair.first(term))
       (tag)

  return {
    init,
    next,
    tag_with,
    untag,
    tagged_with
  }
})()

const Sexp = (() => {
  const Symbol = (() => {
    const tag =
      Tag.next(Tag.init)

    const make =
      Tag.tag_with(tag)

    const is =
      Tag.tagged_with(tag)

    const to_charlist =
      Tag.untag

    return {
      tag,
      is,
      make,
      to_charlist
    }
  })()

  const Container = (() => {
    const tag =
      Tag.next(Symbol.tag)

    const make =
      Tag.tag_with(tag)

    const is =
      Tag.tagged_with(tag)

    return {
      tag,
      is,
      make
    }
  })()

  const fold =
    symbol_folder => list_folder => sexp => {
      if (to_bool(Symbol.is(sexp))) {
        return symbol_folder(Tag.untag(sexp))
      }
      else if (to_bool(Container.is(sexp))) {
        return list_folder(Tag.untag(sexp))
      }
      else {
        return nonsense
      }
    }

  const untag =
    fold
      (symbol =>
        symbol)
      (list =>
        List.map(untag)(list))

  const is_symbol_delimiter =
    char =>
      or
        (Char.is_white(char))
        (List.is_member
          (char)
          (Charlist.from_native('()')))

  const is_symbol_char =
    char =>
      not(is_symbol_delimiter(char))

  const read_symbol_naive_2 =
    input => acc => {
      if (to_bool(List.is_empty(input))) {
        return Symbol.make(List.reverse(acc))
      }
      else {
        const char =
          List.head(input)

        const rest =
          List.tail(input)

        if (to_bool(is_symbol_delimiter(char))) {
          return Symbol.make
            (List.reverse(acc))
        }
        else {
          return read_symbol
            (rest)
            (List.cons(char)(acc))
        }
      }
    }

  const State = (() => {
    const empty =
      Pair.make(List.empty)(List.empty)

    const make =
      acc => leftover =>
        Pair.make(acc)(leftover)

    const get_acc =
      Pair.first

    const get_leftover =
      Pair.second

    return {
      empty,
      make,
      get_acc,
      get_leftover
    }
  })()

  const read_symbol =
    input => state => {
      const acc =
        State.get_acc(state)

      const leftover =
        State.get_leftover(state)

      if (to_bool(List.is_empty(input))) {
        const symbol =
          Symbol.make(List.reverse(acc))

        return State.make(symbol)(List.empty)
      }
      else {
        const char =
          List.head(input)

        const rest =
          List.tail(input)

        if (to_bool(is_symbol_delimiter(char))) {
          const symbol =
            Symbol.make(List.reverse(acc))

          return State.make(symbol)(input)
        }
        else {
          const new_acc =
            List.cons(char)(acc)

          return read_symbol
            (rest)
            (State.make
              (new_acc)
              (leftover))
        }
      }
    }

  const read_list =
    input => state => {
      const acc =
        State.get_acc(state)

      const leftover =
        State.get_leftover(state)

      const char =
        List.head(input)

      const rest =
        List.tail(input)

      if (to_bool(Nat.eq(char)(Char.close_paren))) {
        const list =
          Container.make(List.reverse(acc))

        return State.make(list)(rest)
      }
      else {
        const inner_state =
          read_any(input)(State.empty)

        const expr =
          State.get_acc(inner_state)

        const new_leftover =
          State.get_leftover(inner_state)

        const new_acc =
          List.cons(expr)(acc)

        const new_state =
          State.make(new_acc)(List.empty)

        return read_list(new_leftover)(new_state)
      }
    }

  const read_any =
    input => state => {
      const acc =
        State.get_acc(state)

      const leftover =
        State.get_leftover(state)

      const char =
        List.head(input)

      const rest =
        List.tail(input)

      if (to_bool(Char.is_white(char))) {
        return read_any(rest)(state)
      }
      else if (to_bool(Nat.eq(char)(Char.open_paren))) {
        return read_list(rest)(State.empty)
      }
      else if (to_bool(is_symbol_char(char))) {
        const inner_state =
          State.make
            (List.singletone(char))
            (List.empty)

        return read_symbol(rest)(inner_state)
      }
      else {
        return nonsense
      }
    }

  const from_charlist =
    input =>
      State.get_acc
        (read_any(input)(State.empty))

  const to_charlist =
    fold
      (symbol => symbol)
      (list => {
        const space =
          List.singletone(Char.space)

        const new_line =
          List.singletone(Char.new_line)

        const open_paren =
          List.singletone(Char.open_paren)

        const close_paren =
          List.singletone(Char.close_paren)

        const add_spaces =
          list => {
            if (to_bool(List.is_empty(list))) {
              return List.empty
            }
            else {
              const elem =
                List.head(list)

              const rest =
                List.tail(list)

              if (to_bool(List.is_empty(rest))) {
                return List.singletone(elem)
              }
              else {
                return List.cons
                  (elem)
                  (List.cons
                    (space)
                    (add_spaces(rest)))
              }
            }
          }

        const add_parens =
          list =>
            List.cons
              (open_paren)
              (List.append
                (list)
                (List.singletone(close_paren)))

        const list1 =
          List.map(elem => to_charlist(elem))(list)

        const list2 =
          add_parens(add_spaces(list1))

        return List.concat(list2)
      })

  return {
    Symbol,
    Container,
    untag,
    fold,
    from_charlist,
    to_charlist
  }
})()

const Id = (() => {
  const eq =
    Charlist.eq

  const make =
    id =>
      id

  return { eq, make }
})()

const Var = (() => {
  const tag =
    Tag.init

  const is =
    Tag.tagged_with(tag)

  const make =
    id =>
      Tag.tag_with(tag)(id)

  const get_id = Tag.untag

  return { tag, is, make, get_id }
})()

const Abs = (() => {
  const tag =
    Tag.next(Var.tag)

  const is =
    Tag.tagged_with(tag)

  const make =
    id => body =>
      Tag.tag_with
        (tag)
        (Pair.make(id)(body))

  const make_chain =
    args => body => {
      const step =
        args => acc => {
          if (to_bool(List.is_empty(args))) {
            return acc
          }
          else {
            const id =
              List.head(args)

            const rest =
              List.tail(args)

            return step
              (rest)
              (Abs.make(id)(acc))
          }
        }

      return step(List.reverse(args))(body)
    }

  const get_id =
    pipe(Tag.untag)(Pair.first)

  const get_body =
    pipe(Tag.untag)(Pair.second)

  return { tag, is, make, make_chain, get_id, get_body }
})()

const App = (() => {
  const tag =
    Tag.next(Abs.tag)

  const is =
    Tag.tagged_with(tag)

  const make =
    abs => arg =>
      Tag.tag_with(tag)(Pair.make(abs)(arg))

  const get_abs =
    pipe(Tag.untag)(Pair.first)

  const get_arg =
    pipe(Tag.untag)(Pair.second)

  return { tag, is, make, get_abs, get_arg }
})()

const Term = (() => {
  const fold =
    var_folder => abs_folder => app_folder => term => {
      if (to_bool(Var.is(term))) {
        return var_folder(Var.get_id(term))
      }
      else if (to_bool(Abs.is(term))) {
        return abs_folder(Abs.get_id(term))(Abs.get_body(term))
      }
      else if (to_bool(App.is(term))) {
        return app_folder(App.get_abs(term))(App.get_arg(term))
      }
      else {
        return nonsense
      }
    }

  return {
    fold
  }
})()

const concat_native =
  pipe(List.from_native)(List.concat)

const to_js =
  term => {
    const open_paren =
      List.singletone(Char.open_paren)

    const close_paren =
      List.singletone(Char.close_paren)

    const var_folder =
      id =>
        id

    const abs_folder =
      id => body =>
        concat_native
          ([
            open_paren,
            id,
            Charlist.from_native(' => '),
            to_js(body),
            close_paren
          ])

    const app_folder =
      abs => arg =>
        concat_native
          ([
            to_js(abs),
            open_paren,
            to_js(arg),
            close_paren
          ])

    return Term.fold(var_folder)(abs_folder)(app_folder)(term)
  }

// -- new code --

const app_extract =
  Sexp.fold
    (symbol =>
      Var.make(symbol))
    (list => {
      const make_app =
        list => {
          const abs =
            pipe(List.head)(app_extract)(list)

          const arg =
            app_extract(List.head(List.tail(list)))

          return App.make(abs)(arg)
        }

      const elem =
        List.head(list)

      return Sexp.fold
        (symbol =>
          make_app(list))
        (_ =>
          make_app(list))
        (elem)
    })

const simple_extract =
  Sexp.fold
    (symbol =>
      Var.make(symbol))
    (list => {
      const make_app =
        list => {
          const abs =
            simple_extract(List.head(list))

          const arg =
            simple_extract(List.head(List.tail(list)))

          return App.make(abs)(arg)
        }

      const elem =
        List.head(list)

      return Sexp.fold
        (symbol => {
          const lambda =
            Charlist.from_native('lambda')

          if (to_bool(Charlist.eq(lambda)(symbol))) {
            const rest =
              List.tail(list)

            const args =
              List.head(rest)

            return Sexp.fold
              (_ =>
                nonsense)
              (args => {
                const arg =
                  List.head(args)

                const body =
                  List.head(List.tail(rest))

                return Sexp.fold
                  (symbol =>
                    Abs.make
                     (symbol)
                     (simple_extract(body)))
                  (_ =>
                    nonsense)
                  (arg)
              })
              (args)
          }
          else {
            return make_app(list)
          }
        })
        (_ =>
          make_app(list))
        (elem)
    })

const extract =
  Sexp.fold
    (symbol =>
      Var.make(symbol))
    (list => {
      const make_app =
        sexp => {
          const step =
            terms => acc => {
              if (to_bool(List.is_empty(terms))) {
                return acc
              }
              else {
                const term =
                  List.head(terms)

                const rest =
                  List.tail(terms)

                return step
                  (rest)
                  (App.make
                    (acc)
                    (extract(term)))
              }
            }

          const abs =
            List.head(sexp)

          const arg =
            List.head(List.tail(sexp))

          const rest =
            List.tail(List.tail(sexp))

          return step
            (rest)
            (App.make
              (extract(abs))
              (extract(arg)))
        }

      const elem =
        List.head(list)

      return Sexp.fold
        (symbol => {
          const lambda =
            Charlist.from_native('lambda')

          if (to_bool(Charlist.eq(lambda)(symbol))) {
            const rest =
              List.tail(list)

            const args =
              Sexp.untag(List.head(rest))

            const body =
              List.head(List.tail(rest))

            return Abs.make_chain
              (args)
              (extract(body))
          }
          else {
            return make_app(list)
          }
        })
        (_ =>
          make_app(list))
        (elem)
    })

const term_to_native =
  term =>
    eval(Charlist.to_native(to_js(term)))

const main =
  input => {
    const sexp =
      Sexp.from_charlist(input)

    const term =
      extract(sexp)

    const fun =
      term_to_native(term)

    console.log('Result:', Nat.to_native(fun))

    const output =
      to_js(term)

    return output
  }

IO.input
  (native_input => {
    const input =
      Charlist.from_native(native_input)

    const output =
      main(input)

    const result =
      Charlist.to_native(output)

    console.log(result)
  })