example.scm

(let* ((inc (lambda (num succ zero) (succ (num succ zero))))
       (+ (lambda (num1 num2 succ zero) (num1 succ (num2 succ zero))))
       (* (lambda (num1 num2 succ zero) (num1 (num2 succ) zero)))
       (0 (lambda (succ zero) zero))
       (1 (inc 0))
       (2 (+ 1 1))
       (4 (* 2 2)))
  (* 4 4))

playtorial05.js

#!/usr/bin/env node

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

// const Pair = require('./pair')
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 = require('./logic')
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 = require('./nat/church')
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 = require('./list/cons')(Nat)
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 =
    trans => init => list => {
      const step =
        head => tail => init =>
          trans
            (head)
            (tail(step)(init))

      return list
        (step)
        (init)
    }

  const map =
    trans =>
      fold
        (elem => acc =>
          cons
            (trans(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 Charlist = require('./charlist')(Nat)(List)
const Charlist = (() => {
  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 {
    from_native,
    to_native
  }
})()

// const IO = require('./io')
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 Char = (() => {
  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 {
    is_white,
    new_line,
    space,
    open_paren,
    close_paren
  }
})()

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_tag =
    Tag.next(Tag.init)

  const list_tag =
    Tag.next(symbol_tag)

  const make_symbol =
    Tag.tag_with(symbol_tag)

  const is_symbol =
    Tag.tagged_with(symbol_tag)

  const make_list =
    Tag.tag_with(list_tag)

  const is_list =
    Tag.tagged_with(list_tag)

  const fold =
    symbol_folder => list_folder => sexp => {
      if (to_bool(is_symbol(sexp))) {
        return symbol_folder(Tag.untag(sexp))
      }
      else if (to_bool(is_list(sexp))) {
        return list_folder(Tag.untag(sexp))
      }
      else {
        return nonsense
      }
    }

  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 make_symbol(List.reverse(acc))
      }
      else {
        const char =
          List.head(input)

        const rest =
          List.tail(input)

        if (to_bool(is_symbol_delimiter(char))) {
          return make_symbol
            (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 =
          make_symbol(List.reverse(acc))

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

        const rest =
          List.tail(input)

        if (to_bool(is_symbol_delimiter(char))) {
          const symbol =
            make_symbol(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 =
          make_list(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))) {
        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_spaces(list1)

        const list3 =
           add_parens(list2)

        return List.concat(list3)
      })

  return {
    from_charlist,
    to_charlist
  }
})()

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

    const output =
      Sexp.to_charlist(sexp)

    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)
  })

run.sh

$ chmod +x playtorial05.js
$ ./playtorial05.js < example.scm