#!/usr/bin/env mars
# -------------------------------------------------------------------------- #
# Brainf*** Interpreter in Mars
# Copyright (C) 2008 Matt Giuca
# 9/6/2008
# -------------------------------------------------------------------------- #
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
# -------------------------------------------------------------------------- #
# This is intended as a demonstration of the Mars programming language,
# particularly its turing completeness, its simple IO, and array manipulation.
#
# Note that at present, Mars does not allow files to be opened (only input is
# through stdin). This is similar to Brainf*** itself. In order to write
# Brainf*** in itself, authors commonly separate the code and data with a "!",
# as shown here:
# http://www.hevanet.com/cristofd/08.html
# We take this same approach.
#
# This implementation is loosely based on the C++ algorithm at the above
# address. It has undefined behaviour in the following circumstances:
# - Non-matching brackets.
# - Using negative elements of the array, or elements beyond 30,000.
# It stores 0 on EOF, and has wrapping 256-valued cells.
# -------------------------------------------------------------------------- #
# -------------------------------------------------------------------------- #

import prelude
import impure       # Allow impure functions

def array_size :: Int = 30000

# get_till_bang()
# Reads from stdin, storing the characters in an array.
# Stops reading once it sees a '!' character, or EOF. Consumes the '!'.
# Returns the array.
def get_till_bang() :: Array(Int):
    var s :: Array(Int)
    var c :: Int
    s = array(0, 0)     # Empty array
    c = get_char()
    while and(ne(c, eof), ne(c, '!')):     # while c != -1 and c != '!'
        s = array_append(s, c)
        c = get_char()
    return s

# init_array()
# Creates a new array of size array_size, and initialises all elements to 0.
def init_array :: Array(Int) = array(array_size, 0)

# main program
def main() :: Int:
    var ip :: Int       # Instruction pointer
    var dp :: Int       # Data pointer
    var program :: Array(Int)
    var array :: Array(Int)

    # Read the file up until the '!'
    program = get_till_bang()
    array = init_array

    # Execute the program
    return main_loop(program, array)

# main_loop(program, array)
# Executes the program.
# Side-effects: stdin, stdout, mutates array.
def main_loop(program :: Array(Int), array :: Array(Int)) :: Int:
    var c :: Int    # Temporary character
    var ip :: Int   # Instruction pointer
    var dp :: Int   # Data pointer

    ip = 0
    dp = 0

    while lt(ip, array_length(program)):
        switch array_ref(program, ip):
            case '>':
                dp = add(dp, 1)
            case '<':
                dp = sub(dp, 1)
            case '+':
                # array[dp]++
                array_set(array, dp, add(array_ref(array, dp), 1))
            case '-':
                # array[dp]--
                array_set(array, dp, sub(array_ref(array, dp), 1))
            case '.':
                put_char(array_ref(array, dp))
            case ',':
                c = get_char()
                if eq(c, eof):
                    array_set(array, dp, 0)
                else:
                    array_set(array, dp, c)
            case '[':
                # Skip to ']' if false
                if eq(array_ref(array, dp), 0):
                    ip = seek_close_bracket(program, ip, 1)
            case ']':
                # Skip to '[' if true
                if ne(array_ref(array, dp), 0):
                    ip = seek_open_bracket(program, ip, 1)
            case _:
                pass

        ip = add(ip, 1)

    return 0

# Moves the program counter forwards, looking for a ']' to match '['.
# Returns the updated program counter.
# No side-effects.
def seek_close_bracket(program :: Array(Int), ip :: Int, nest :: Int) :: Int:
    while gt(nest, 0):
        ip = add(ip, 1)
        switch array_ref(program, ip):
            case '[':
                nest = add(nest, 1)
            case ']':
                nest = sub(nest, 1)
            case _:
                pass
    return ip

# Moves the program counter backwards, looking for a '[' to match ']'.
# Returns the updated program counter.
# No side-effects.
def seek_open_bracket(program :: Array(Int), ip :: Int, nest :: Int) :: Int:
    while gt(nest, 0):
        ip = sub(ip, 1)
        switch array_ref(program, ip):
            case '[':
                nest = sub(nest, 1)
            case ']':
                nest = add(nest, 1)
            case _:
                pass
    return ip