Práctica 9: Sistema Operativo
Recursos
nadavge/nand_ex11: nand-2-tetris project 11 - Jack compiler (github.com)
The Elements of Computing Systems
Introducción
El front-end del compilador, como bien se dijo anteriormente consta de un analizador de sintaxis, desarrollado en la práctica anterior, y un generador de código, el tema a tratar en la primera parte de la actual practica. Específicamente, en la practica 8 creamos un analizador de sintaxis capaz de "comprender" (analizar) los programas de Jack. Para el proyecto 11 abarcado en la actual practica tenemos como objetivo ampliar el analizador a un compilador a gran escala que convierte cada construcción de alto nivel "entendido" en una serie equivalente de operaciones de VM.
Por otro lado tenemos el proyecto 12 en el cual trataremos la última interfaz importante que falta, el sistema operativo (SO). El sistema operativo está diseñado para "cerrar" las brechas entre el software y el hardware de los computadores, y para hacer que el computador en general sea más accesible tanto para los programadores como para los usuarios por lo que el objetivo principal de este proyecto es implementar el sistema operativo Jack.
Proyecto 11. Compiler II - Code Generation
Desarrollo
Primeramente hay que tratar los temas necesarios para completar el desarrollo del compilador: administrar una tabla de símbolos; representar y generar código para variables, objetos y matrices.
Tabla de símbolos: los programas de alto nivel introducen y manipulan muchos identificadores. Cada vez que el compilador encuentra un identificador, digamos xxx, necesita saber qué significa xxx. ¿Es un nombre de variable, un nombre de clase o un nombre de función? Si es una variable, ¿Qué tipo de variable es: un entero, un valor booleano o quizás un carácter? El compilador debe resolver estas preguntas antes de poder representar la semántica de xxx en el idioma de destino. Además, todas estas preguntas deben responderse cada vez que se encuentre xxx en el código fuente. Claramente, es necesario realizar un seguimiento de todos los identificadores introducidos por el programa y, para cada uno, registrar qué significa el identificador en el programa fuente y en qué construcción se mapea en el idioma de destino. La mayoría de los compiladores mantienen esta información utilizando una abstracción de tabla de símbolos.
Figura 1. Tabla de símbolos.
Manejo de variables: ¿Cómo mapear los diversos tipos de variables declaradas en el programa fuente en la memoria de la plataforma de destino? Primero, los diferentes tipos de variables requieren diferentes tamaños de fragmentos de memoria, por lo que el mapeo no es uno a uno. En segundo lugar, diferentes tipos de variables tienen diferentes ciclos de vida. Por el contrario, cada instancia de objeto de una clase debe tener una copia diferente de todas sus variables de instancia (campos) y, cuando se desecha, la memoria del objeto debe reciclarse. Además, cada vez que se llama a una subrutina, se deben crear nuevas copias de sus variables locales y de argumento, una necesidad que se ve claramente en la recursividad. La buena noticia es que ya hemos manejado todas estas dificultades. La asignación de memoria de las variables se delegó en la máquina virtual de los proyectos 7 y 8. Lo único que se requiere del compilador es mapear las variables que se encuentran en el programa fuente en los segmentos de memoria virtual y expresar los comandos de alto nivel que los manipulan usando comandos de VM.
Manejo de matrices: las matrices casi siempre se almacenan como secuencias de ubicaciones de memoria consecutivas (las matrices multidimensionales se aplanan en unidades unidimensionales). El nombre de la matriz generalmente se trata como un puntero a la dirección base del bloque de RAM asignado para almacenar la matriz en la memoria. La matriz propiamente dicha se crea en la memoria más tarde, siempre y cuando la matriz se construya realmente en tiempo de ejecución. Por lo general, el sistema operativo tiene una función de asignación (tamaño) que sabe cómo encontrar un bloque de memoria disponible de tamaño y devolver su dirección base a la persona que llama. Por lo tanto, al compilar una instrucción de alto nivel como bar=new int [10], el compilador genera código de bajo nivel que efectúa la operación bar=alloc(10). Esto da como resultado la asignación de la dirección base del bloque de memoria de la matriz a la barra, que es exactamente lo que se busca.
Figura 2. Manejo de matrices.
Por lo tanto basándonos en lo anterior y del proyecto 10, el compilador general se puede construir utilizando cinco clases:
JackCompiler: esta clase funciona como un controlador de nivel superior que configura e invoca las otras clases.
JackTokenizer: tokenizador.
SymbolTable: tabla de símbolos.
VMWriter: clase para generar código VM.
CompilationEngine: esta clase hace la compilación por sí misma. Lee la entrada del JackTokenizer y escribe su salida en un VMWriter.
Figura 3. Estructura del compilador Jack para el proyecto 11
CompilationEngine.py
from SymbolTable import SymbolTable
from VMWriter import VMWriter
from LabelCounter import LabelCounter
from Operator import Operator
class CompilationEngine():
"""
compila un archivo fuente jack de un tokenizador jack en formato xml en archivo_salida
"""
SYMBOL_KINDS = {
'parameter_list': 'argument',
'var_dec': 'local'
}
CLASS_VAR_DEC_TOKENS = [ "static", "field" ]
SUBROUTINE_TOKENS = [ "function", "method", "constructor" ]
STATEMENT_TOKENS = [ 'do', 'let', 'while', 'return', 'if' ]
STARTING_TOKENS = {
'var_dec': ['var'],
'parameter_list': ['('],
'subroutine_body': ['{'],
'expression_list': ['('],
'expression': ['=', '[', '('],
'array': [ '[' ],
'conditional': ['if', 'else']
}
TERMINATING_TOKENS = {
'class': ['}'],
'class_var_dec': [';'],
'subroutine': ['}'],
'parameter_list': [')'],
'expression_list': [')'],
'statements': ['}'],
'do': [';'],
'let': [';'],
'while': ['}'],
'if': ['}'],
'var_dec': [';'],
'return': [';'],
'expression': [';', ')', ']', ','],
'array': [']']
}
OPERATORS = [
'+',
'-',
'*',
'/',
'&',
'|',
'<',
'>',
'='
]
UNARY_OPERATORS = [ '-', '~' ]
TOKENS_THAT_NEED_LABELS = ['if', 'while']
def __init__(self, tokenizer, output_file):
self.tokenizer = tokenizer
self.output_file = output_file
self.class_symbol_table = SymbolTable()
self.subroutine_symbol_table = SymbolTable()
self.vm_writer = VMWriter(output_file)
self.label_counter = LabelCounter(labels=self.TOKENS_THAT_NEED_LABELS)
self.class_name = None
def compile_class(self):
"""
todo lo necesario para compilar una clase, la unidad básica de compilación
"""
# saltar todo hasta el comienzo de la clase
while not self.tokenizer.class_token_reached():
self.tokenizer.advance()
# dado que la unidad de compilación es una clase, tiene sentido almacenar esto como variable de instancia
self.class_name = self.tokenizer.next_token
while self.tokenizer.has_more_tokens:
self.tokenizer.advance()
if self.tokenizer.current_token in self.CLASS_VAR_DEC_TOKENS:
self.compile_class_var_dec()
elif self.tokenizer.current_token in self.SUBROUTINE_TOKENS:
self.compile_subroutine()
def compile_class_var_dec(self):
"""
ejemplo: field int x;
"""
symbol_kind = self.tokenizer.keyword()
# obtener tipo de símbolo
self.tokenizer.advance()
symbol_type = self.tokenizer.keyword()
# get all identifiers
while self._not_terminal_token_for('class_var_dec'):
self.tokenizer.advance()
if self.tokenizer.identifier():
# add symbol to class
symbol_name = self.tokenizer.identifier()
self.class_symbol_table.define(
name=symbol_name,
kind=symbol_kind,
symbol_type=symbol_type
)
def compile_subroutine(self):
"""
ejemplo: methoid void dispose() { ...
"""
# nueva subrutina significa nuevo alcance de subrutina
self.subroutine_symbol_table.reset()
# obtener el nombre de la subrutina
self.tokenizer.advance()
self.tokenizer.advance()
subroutine_name = self.tokenizer.current_token
# lista de parámetros de compilación
self.tokenizer.advance()
self.compile_parameter_list()
# compilar cuerpo
self.tokenizer.advance()
self.compile_subroutine_body(subroutine_name=subroutine_name)
# el resto cuenta desde la subrutina
self.label_counter.reset_counts()
def compile_subroutine_body(self, subroutine_name):
self.tokenizer.advance()
num_locals = 0
while self._starting_token_for('var_dec'):
num_locals += self.compile_var_dec()
self.tokenizer.advance()
self.vm_writer.write_function(
name='{}.{}'.format(self.class_name, subroutine_name),
num_locals=num_locals
)
while self._not_terminal_token_for('subroutine'):
self.compile_statements()
def compile_parameter_list(self):
"""
ejemplo: disponer(int a, int b)
devuelve el número de parámetros encontrados
"""
### symbol table
while self._not_terminal_token_for('parameter_list'):
self.tokenizer.advance()
# symbol table
if self.tokenizer.token_type_of(self.tokenizer.next_token) == "IDENTIFIER":
symbol_kind = self.SYMBOL_KINDS['parameter_list']
symbol_type = self.tokenizer.current_token
symbol_name = self.tokenizer.next_token
self.subroutine_symbol_table.define(
name=symbol_name,
kind=symbol_kind,
symbol_type=symbol_type
)
# 'var' type varName (',' varName)* ';'
def compile_var_dec(self):
"""
ejemplo: var int a;
"""
self.tokenizer.advance()
symbol_type = self.tokenizer.current_token
num_vars = 0
while self._not_terminal_token_for('var_dec'):
self.tokenizer.advance()
if self.tokenizer.identifier():
num_vars += 1
symbol_kind = self.SYMBOL_KINDS['var_dec']
symbol_name = self.tokenizer.identifier()
self.subroutine_symbol_table.define(
name=symbol_name,
kind=symbol_kind,
symbol_type=symbol_type
)
return num_vars
def compile_statements(self):
"""
llamar la declaración correcta
"""
statement_compile_methods = {
'if': self.compile_if,
'do': self.compile_do,
'let': self.compile_let,
'while': self.compile_while,
'return': self.compile_return
}
while self._not_terminal_token_for('subroutine'):
if self.tokenizer.current_token in self.STATEMENT_TOKENS:
statement_type = self.tokenizer.current_token
statement_compile_methods[statement_type]()
self.tokenizer.advance()
def compile_do(self):
"""
ejemplo: do square.dispose();
"""
self.tokenizer.advance()
caller_name = self.tokenizer.current_token
symbol = self._find_symbol_in_symbol_tables(symbol_name=caller_name)
self.tokenizer.advance()
self.tokenizer.advance()
subroutine_name = self.tokenizer.current_token
if symbol: # user defined Method
segment = 'local'
index = symbol['index']
symbol_type = symbol['type']
self.vm_writer.write_push(segment=segment, index=index)
else:
symbol_type = caller_name
subroutine_call_name = symbol_type + '.' + subroutine_name
self.tokenizer.advance()
num_args = self.compile_expression_list()
if symbol:
num_args += 1
self.vm_writer.write_call(name=subroutine_call_name, num_args=num_args)
self.vm_writer.write_pop(segment='temp', index='0')
def compile_let(self):
self.tokenizer.advance()
symbol_name = self.tokenizer.current_token
symbol = self._find_symbol_in_symbol_tables(symbol_name=symbol_name)
array_assignment = self._starting_token_for(keyword_token='array', position='next')
if array_assignment:
self.tokenizer.advance()
self.tokenizer.advance()
self.compile_expression()
self.vm_writer.write_push(segment=symbol['kind'], index=symbol['index'])
self.vm_writer.write_arithmetic(command='+')
while not self.tokenizer.current_token == '=':
self.tokenizer.advance()
while self._not_terminal_token_for('let'):
self.tokenizer.advance()
self.compile_expression()
if not array_assignment:
# store expression evaluation in symbol location
self.vm_writer.write_pop(segment=symbol['kind'], index=symbol['index'])
else:
self.vm_writer.write_pop(segment='temp', index='0')
self.vm_writer.write_pop(segment='pointer', index='1') # pointer 1 => array
self.vm_writer.write_push(segment='temp', index='0')
self.vm_writer.write_pop(segment='that', index='0')
def compile_while(self):
"""
example: while (x > 0) { ... }
"""
self.vm_writer.write_label(label='WHILE_EXP{}'.format(self.label_counter.get('while')))
self.tokenizer.advance()
self.tokenizer.advance()
self.compile_expression()
self.vm_writer.write_unary(command='~')
self.vm_writer.write_ifgoto(label='WHILE_END{}'.format(self.label_counter.get('while')))
while self._not_terminal_token_for('while'):
self.tokenizer.advance()
if self._statement_token():
self.compile_statements()
self.vm_writer.write_goto(label='WHILE_EXP{}'.format(self.label_counter.get('while')))
self.vm_writer.write_label(label='WHILE_END{}'.format(self.label_counter.get('while')))
self.label_counter.increment('while')
def compile_if(self):
self.tokenizer.advance()
self.tokenizer.advance()
self.compile_expression()
self.vm_writer.write_ifgoto(label='IF_TRUE{}'.format(self.label_counter.get('if')))
self.vm_writer.write_goto(label='IF_FALSE{}'.format(self.label_counter.get('if')))
self.vm_writer.write_label(label='IF_TRUE{}'.format(self.label_counter.get('if')))
self.compile_conditional_body()
if self._starting_token_for(keyword_token='conditional', position='next'):
self.tokenizer.advance()
self.vm_writer.write_goto(label='IF_END{}'.format(self.label_counter.get('if')))
self.vm_writer.write_label(label='IF_FALSE{}'.format(self.label_counter.get('if')))
self.compile_conditional_body()
self.vm_writer.write_label(label='IF_END{}'.format(self.label_counter.get('if')))
else:
self.vm_writer.write_label(label='IF_FALSE{}'.format(self.label_counter.get('if')))
def compile_conditional_body(self):
while self._not_terminal_token_for('if'):
self.tokenizer.advance()
if self._statement_token():
if self.tokenizer.current_token == 'if':
self.label_counter.increment('if')
self.compile_statements()
self.label_counter.decrement('if')
else:
self.compile_statements()
def compile_expression(self):
ops = []
while self._not_terminal_token_for('expression'):
if self._subroutine_call():
self.compile_subroutine_call()
elif self._array_expression():
self.compile_array_expression()
elif self.tokenizer.current_token.isdigit():
self.vm_writer.write_push(segment='constant', index=self.tokenizer.current_token)
elif self.tokenizer.identifier():
self.compile_symbol_push()
elif self.tokenizer.current_token in self.OPERATORS and not self._part_of_expression_list():
ops.insert(0, Operator(token=self.tokenizer.current_token, category='bi'))
elif self.tokenizer.current_token in self.UNARY_OPERATORS:
ops.insert(0, Operator(token=self.tokenizer.current_token, category='unary'))
elif self.tokenizer.string_const():
self.compile_string_const()
elif self.tokenizer.boolean(): # boolean case
self.compile_boolean()
elif self._starting_token_for('expression'): # nested expression
# skip starting (
self.tokenizer.advance()
self.compile_expression()
elif self.tokenizer.null():
self.vm_writer.write_push(segment='constant', index=0)
self.tokenizer.advance()
for op in ops:
self.compile_op(op)
def compile_op(self, op):
if op.unary():
self.vm_writer.write_unary(command=op.token)
elif op.multiplication():
self.vm_writer.write_call(name='Math.multiply', num_args=2)
elif op.division():
self.vm_writer.write_call(name='Math.divide', num_args=2)
else:
self.vm_writer.write_arithmetic(command=op.token)
def compile_boolean(self):
self.vm_writer.write_push(segment='constant', index=0)
if self.tokenizer.boolean() == 'true':
# negate true
self.vm_writer.write_unary(command='~')
def compile_string_const(self):
string_length = len(self.tokenizer.string_const())
self.vm_writer.write_push(segment='constant', index=string_length)
self.vm_writer.write_call(name='String.new', num_args=1)
for char in self.tokenizer.string_const():
if not char == self.tokenizer.STRING_CONST_DELIMITER:
ascii_value_of_char = ord(char)
self.vm_writer.write_push(segment='constant', index=ascii_value_of_char)
self.vm_writer.write_call(name='String.appendChar', num_args=2)
def compile_symbol_push(self):
symbol = self._find_symbol_in_symbol_tables(symbol_name=self.tokenizer.identifier())
segment = symbol['kind']
index = symbol['index']
self.vm_writer.write_push(segment=segment, index=index)
def compile_array_expression(self):
symbol_name = self.tokenizer.current_token
symbol = self._find_symbol_in_symbol_tables(symbol_name=symbol_name)
self.tokenizer.advance()
self.tokenizer.advance()
self.compile_expression()
self.vm_writer.write_push(segment='local', index=symbol['index'])
self.vm_writer.write_arithmetic(command='+')
self.vm_writer.write_pop(segment='pointer', index=1)
self.vm_writer.write_push(segment='that', index=0)
def compile_subroutine_call(self):
subroutine_name = ''
while not self._starting_token_for('expression_list'):
subroutine_name += self.tokenizer.current_token
self.tokenizer.advance()
num_args = self.compile_expression_list()
self.vm_writer.write_call(name=subroutine_name, num_args=num_args)
# (expression (',' expression)* )?
def compile_expression_list(self):
num_args = 0
if self._empty_expression_list():
return num_args
self.tokenizer.advance()
while self._not_terminal_token_for('expression_list'):
num_args += 1
self.compile_expression()
if self._another_expression_coming(): # would be , after compile expression
self.tokenizer.advance()
return num_args
def compile_return(self):
if self._not_terminal_token_for(keyword_token='return', position='next'):
self.compile_expression()
else: # push constant for void
self.vm_writer.write_push(segment='constant', index='0')
self.tokenizer.advance()
self.vm_writer.write_return()
def _not_terminal_token_for(self, keyword_token, position='current'):
if position == 'current':
return not self.tokenizer.current_token in self.TERMINATING_TOKENS[keyword_token]
elif position == 'next':
return not self.tokenizer.next_token in self.TERMINATING_TOKENS[keyword_token]
def _starting_token_for(self, keyword_token, position='current'):
if position == 'current':
return self.tokenizer.current_token in self.STARTING_TOKENS[keyword_token]
elif position == 'next':
return self.tokenizer.next_token in self.STARTING_TOKENS[keyword_token]
def _statement_token(self):
return self.tokenizer.current_token in self.STATEMENT_TOKENS
def _operator_token(self, position='current'):
if position == 'current':
return self.tokenizer.current_token in self.OPERATORS
elif position == 'next':
return self.tokenizer.next_token in self.OPERATORS
def _another_expression_coming(self):
return self.tokenizer.current_token == ","
def _find_symbol_in_symbol_tables(self, symbol_name):
if self.subroutine_symbol_table.find_symbol_by_name(symbol_name):
return self.subroutine_symbol_table.find_symbol_by_name(symbol_name)
elif self.class_symbol_table.find_symbol_by_name(symbol_name):
return self.class_symbol_table.find_symbol_by_name(symbol_name)
def _empty_expression_list(self):
return self._start_of_expression_list() and self._next_ends_expression_list()
def _start_of_expression_list(self):
return self.tokenizer.current_token in self.STARTING_TOKENS['expression_list']
def _next_ends_expression_list(self):
return self.tokenizer.next_token in self.TERMINATING_TOKENS['expression_list']
def _subroutine_call(self):
return self.tokenizer.identifier() and self.tokenizer.next_token == '.'
def _array_expression(self):
return self.tokenizer.identifier() and self._starting_token_for(keyword_token='array', position='next')
def _part_of_expression_list(self):
return self.tokenizer.tokens_found[-3] in [',', '(']
JackCompiler.py
from JackTokenizer import JackTokenizer
from CompilationEngine import CompilationEngine
import sys
import os
import glob
class JackCompiler():
@classmethod
def run(cls, input_file, output_file):
tokenizer = JackTokenizer(input_file)
compiler = CompilationEngine(tokenizer, output_file)
compiler.compile_class()
@classmethod
def output_file_for(cls, input_file, ext_name='.vm'):
file_name = os.path.basename(input_file).split(".")[0]
dir_name = os.path.dirname(input_file).replace('./', '')
try:
os.mkdir("./compiled/{}".format(dir_name))
except OSError:
print("res directory already exists. continuing")
return dir_name + "/" + file_name + ext_name
if __name__ == "__main__" and len(sys.argv) == 2:
arg = sys.argv[1]
if os.path.isfile(arg):
files = [arg]
elif os.path.isdir(arg):
jack_path = os.path.join(arg, "*.jack")
files = glob.glob(jack_path)
try:
os.mkdir("./compiled")
except OSError:
print("output directory already exists. continuing")
for input_file_name in files:
output_file_name = JackCompiler.output_file_for(input_file_name)
output_file = open(output_file_name, 'w')
input_file = open(input_file_name, 'r')
JackCompiler.run(input_file, output_file)
JackTokenizer.py
class JackTokenizer():
KEYWORDS = [
'class',
'constructor',
'function',
'method',
'field',
'static',
'var',
'int',
'char',
'boolean',
'void',
'true',
'false',
'null',
'this',
'let',
'do',
'if',
'else',
'while',
'return'
]
COMMENT_OPERATORS = ["/", "*"]
STRING_CONST_DELIMITER = '"'
def __init__(self, input_file):
self.input_file = input_file
self.tokens_found = []
self.current_token = None
self.next_token = None
self.has_more_tokens = True
def advance(self):
char = self.input_file.read(1)
while char.isspace() or char in self.COMMENT_OPERATORS:
if char.isspace():
char = self.input_file.read(1)
elif char in self.COMMENT_OPERATORS:
last_pos = self.input_file.tell()
rest_of_line = self.input_file.readline()
self.input_file.seek(last_pos)
if not self._is_start_of_comment(char, rest_of_line):
self.input_file.seek(last_pos)
break
self.input_file.readline()
char = self.input_file.read(1)
continue
token = ""
if self._is_string_const_delimeter(char):
token += char
char = self.input_file.read(1)
while not self._is_string_const_delimeter(char):
token += char
char = self.input_file.read(1)
# get last "
token += char
elif char.isalnum():
while self._is_alnum_or_underscore(char):
token += char
last_pos = self.input_file.tell()
char = self.input_file.read(1)
self.input_file.seek(last_pos)
else: # symbol
token = char
if self.current_token:
self.current_token = self.next_token
self.next_token = token
self.tokens_found.append(token)
else: # initial setup
self.current_token = token
self.next_token = token
self.tokens_found.append(token)
# update next token
self.advance()
if not len(self.next_token) > 0:
self.has_more_tokens = False
return False
else:
return True
def part_of_subroutine_call(self):
if len(self.tokens_found) < 3:
return False
index = len(self.tokens_found) - 4
token = self.tokens_found[index]
if token == ".":
return True
else:
return False
def class_token_reached(self):
return self.current_token == 'class'
def token_type_of(self, token):
if token[0] == "\"":
return "STRING_CONST"
elif token in self.KEYWORDS:
return "KEYWORD"
elif token.isnumeric():
return "INT_CONST"
elif token.isalnum():
return "IDENTIFIER"
else:
return "SYMBOL"
def null(self):
if self.current_token == 'null':
return self.current_token
def boolean(self):
if self.current_token in ['true', 'false']:
return self.current_token
def keyword(self):
if self.token_type_of(self.current_token) == "KEYWORD":
return self.current_token
def identifier(self):
if self.token_type_of(self.current_token) == "IDENTIFIER":
return self.current_token
def string_const(self):
if self.token_type_of(self.current_token) == "STRING_CONST":
return self.current_token.replace('"', '')
def _is_alnum_or_underscore(self, char):
return char.isalnum() or char == "_"
def _is_string_const_delimeter(self, char):
return char == "\""
def _is_start_of_comment(self, char, rest_of_line):
single_line_comment = rest_of_line[0] == self.COMMENT_OPERATORS[0]
multi_line_comment = char == self.COMMENT_OPERATORS[0] and rest_of_line[0:2] == "**"
part_of_multi_line_comment = self._part_of_multiline_comment()
return single_line_comment or multi_line_comment or part_of_multi_line_comment
def _part_of_multiline_comment(self):
if not self.tokens_found:
return True
elif self.tokens_found[-1] == ';':
return True
else:
return False
VMWriter.py
class VMWriter():
ARITHMETIC_LOGICAL_OPERATORS = {
'+': 'add',
'-': 'sub',
'=': 'eq',
'>': 'gt',
'<': 'lt',
'&': 'and',
'|': 'or'
}
UNARY_OPERATORS = {
'-': 'neg',
'~': 'not'
}
def __init__(self, output_file):
self.output_file = output_file
def write_push(self, segment, index):
self.output_file.write('push {} {}\n'.format(segment, index))
def write_pop(self, segment, index):
self.output_file.write('pop {} {}\n'.format(segment, index))
def write_arithmetic(self, command):
self.output_file.write(
'{}\n'.format(self.ARITHMETIC_LOGICAL_OPERATORS[command])
)
def write_unary(self, command):
self.output_file.write(
'{}\n'.format(self.UNARY_OPERATORS[command])
)
def write_label(self, label):
self.output_file.write('label {}\n'.format(label))
def write_goto(self, label):
self.output_file.write('goto {}\n'.format(label))
def write_ifgoto(self, label):
self.output_file.write('if-goto {}\n'.format(label))
def write_call(self, name, num_args):
self.output_file.write(
'call {} {}\n'.format(name, num_args)
)
def write_function(self, name, num_locals):
self.output_file.write('function {} {}\n'.format(name, num_locals))
def write_return(self):
self.output_file.write('return\n')
SymbolTable.py
class SymbolTable():
"""
Represents the current symbols for a given class or subroutine for the JackCompiler
"""
def __init__(self):
self.symbols = []
def reset(self):
"""
Starts a new subroutine scope, i.e., resets the subroutine's scope
"""
self.symbols = []
def define(self, name, symbol_type, kind):
"""
defines a new identifier of the given name, type, and kind and assigns it a running index
"""
new_symbol = {
'name': name,
'type': symbol_type,
'kind': kind,
'index': self.var_count(kind)
}
self.symbols.append(new_symbol)
def var_count(self, kind):
"""
returns the number of variables of the given kind already defined in the current scope
"""
return sum(symbol['kind'] == kind for symbol in self.symbols)
def kind_of(self, name):
"""
returns the kind of the named identifer in the current scope
(STATIC, FIELD, ARG, VAR, NONE)
"""
return self.find_symbol_by_name(name).get('kind')
def type_of(self, name):
"""
returns the type of the named identifier in the current scope
"""
return self.find_symbol_by_name(name).get('type')
def index_of(self, name):
"""
returns the index assigned to the named identifier
"""
return self.find_symbol_by_name(name).get('index')
def find_symbol_by_name(self, value):
for symbol in self.symbols:
if symbol['name'] == value:
return symbol
Tests
Para testear el compilador se nos proporcionaron los programas:
Seven
Conversion to binary
Square dance
Average
Pong
Complex arrays
Debemos utilizar nuestro compilador para obtener los respectivos archivos .vm para cada unos de los programas .Jack para posteriormente ejecutarlos con la herramienta VMEmulator suministrada por nand2tetris y verificar si el programa se comporta de forma inesperada o el emulador muestra algún mensaje de error.
Resultados
Seven
Este programa calcula el valor de (3*2)+1 e imprime el resultado en la parte superior izquierda de la pantalla. Como vemos que el resultado es 7 se concluye que el compilador tradujo el programa correctamente.
Resultados obtenidos
main.vm
function Main.main 0
push constant 1
push constant 2
push constant 3
call Math.multiply 2
add
call Output.printInt 1
pop temp 0
push constant 0
return
Conversion to binary
Este programa convierte un número decimal de 16 bits en su representación binaria. Para probarlo debemos
Poner (interactivamente) un valor decimal de 16 bits en RAM[8000]
Ejecutar el programa durante unos segundos y luego pararlo
Y por último verificar (interactivamente) que RAM[8001..8016] contenga los resultados correctos y que ninguno de ellos contenga - 1
Resultados obtenidos
En nuestro caso en el valor de RAM[8000] colocamos el valor de 65, por lo que en los valores RAM[8001...8016] obtuvimos 1000001000000000. Realmente la parte que importa es hasta el 1000001 que es en decimal 65.
main.vm
function Main.main 1
push constant 8001
push constant 16
push constant 1
neg
call Main.fillMemory 3
pop temp 0
push constant 8000
call Memory.peek 1
pop local 0
push local 0
call Main.convert 1
pop temp 0
push constant 0
return
function Main.convert 3
push constant 0
not
pop local 2
label WHILE_EXP0
push local 2
not
if-goto WHILE_END0
push local 1
push constant 1
add
pop local 1
push local 0
call Main.nextMask 1
pop local 0
push local 1
push constant 16
gt
not
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push argument 0
push local 0
and
push constant 0
eq
not
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push constant 8000
push local 1
add
push constant 1
call Memory.poke 2
pop temp 0
goto IF_END1
label IF_FALSE1
push constant 8000
push local 1
add
push constant 0
call Memory.poke 2
pop temp 0
label IF_END1
goto IF_END0
label IF_FALSE0
push constant 0
pop local 2
label IF_END0
goto WHILE_EXP0
label WHILE_END0
push constant 0
return
function Main.nextMask 0
push argument 0
push constant 0
eq
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 1
return
goto IF_END0
label IF_FALSE0
push argument 0
push constant 2
call Math.multiply 2
return
label IF_END0
function Main.fillMemory 0
label WHILE_EXP0
push argument 1
push constant 0
gt
not
if-goto WHILE_END0
push argument 0
push argument 2
call Memory.poke 2
pop temp 0
push argument 1
push constant 1
sub
pop argument 1
push argument 0
push constant 1
add
pop argument 0
goto WHILE_EXP0
label WHILE_END0
push constant 0
return
Square dance
Este programa es un “juego” interactivo que permite mover un cuadrado negro alrededor de la pantalla usando las cuatro teclas de flecha del teclado. Mientras se mueve, el tamaño del cuadrado se puede aumentar y disminuir presionando las teclas "z" y "x", respectivamente. Para probarlo debemos asegurarnos de que funcione de acuerdo con esta descripción al momento de ejecutarlo en el VMEmulator.
Resultados obtenidos
main.vm
function Main.main 1
call SquareGame.new 0
pop local 0
push local 0
call SquareGame.run 1
pop temp 0
push local 0
call SquareGame.dispose 1
pop temp 0
push constant 0
return
Square.vm
function Square.new 0
push constant 3
call Memory.alloc 1
pop pointer 0
push argument 0
pop this 0
push argument 1
pop this 1
push argument 2
pop this 2
push pointer 0
call Square.draw 1
pop temp 0
push pointer 0
return
function Square.dispose 0
push argument 0
pop pointer 0
push pointer 0
call Memory.deAlloc 1
pop temp 0
push constant 0
return
function Square.draw 0
push argument 0
pop pointer 0
push constant 0
not
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 0
push this 2
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
push constant 0
return
function Square.erase 0
push argument 0
pop pointer 0
push constant 0
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 0
push this 2
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
push constant 0
return
function Square.incSize 0
push argument 0
pop pointer 0
push this 1
push this 2
add
push constant 254
lt
push this 0
push this 2
add
push constant 510
lt
and
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push pointer 0
call Square.erase 1
pop temp 0
push this 2
push constant 2
add
pop this 2
push pointer 0
call Square.draw 1
pop temp 0
label IF_FALSE0
push constant 0
return
function Square.decSize 0
push argument 0
pop pointer 0
push this 2
push constant 2
gt
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push pointer 0
call Square.erase 1
pop temp 0
push this 2
push constant 2
sub
pop this 2
push pointer 0
call Square.draw 1
pop temp 0
label IF_FALSE0
push constant 0
return
function Square.moveUp 0
push argument 0
pop pointer 0
push this 1
push constant 1
gt
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 0
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 2
add
push constant 1
sub
push this 0
push this 2
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
push this 1
push constant 2
sub
pop this 1
push constant 0
not
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 0
push this 2
add
push this 1
push constant 1
add
call Screen.drawRectangle 4
pop temp 0
label IF_FALSE0
push constant 0
return
function Square.moveDown 0
push argument 0
pop pointer 0
push this 1
push this 2
add
push constant 254
lt
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 0
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 0
push this 2
add
push this 1
push constant 1
add
call Screen.drawRectangle 4
pop temp 0
push this 1
push constant 2
add
pop this 1
push constant 0
not
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 2
add
push constant 1
sub
push this 0
push this 2
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
label IF_FALSE0
push constant 0
return
function Square.moveLeft 0
push argument 0
pop pointer 0
push this 0
push constant 1
gt
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 0
call Screen.setColor 1
pop temp 0
push this 0
push this 2
add
push constant 1
sub
push this 1
push this 0
push this 2
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
push this 0
push constant 2
sub
pop this 0
push constant 0
not
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 0
push constant 1
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
label IF_FALSE0
push constant 0
return
function Square.moveRight 0
push argument 0
pop pointer 0
push this 0
push this 2
add
push constant 510
lt
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 0
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 0
push constant 1
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
push this 0
push constant 2
add
pop this 0
push constant 0
not
call Screen.setColor 1
pop temp 0
push this 0
push this 2
add
push constant 1
sub
push this 1
push this 0
push this 2
add
push this 1
push this 2
add
call Screen.drawRectangle 4
pop temp 0
label IF_FALSE0
push constant 0
return
SquareGame.vm
function SquareGame.new 0
push constant 2
call Memory.alloc 1
pop pointer 0
push constant 0
push constant 0
push constant 30
call Square.new 3
pop this 0
push constant 0
pop this 1
push pointer 0
return
function SquareGame.dispose 0
push argument 0
pop pointer 0
push this 0
call Square.dispose 1
pop temp 0
push pointer 0
call Memory.deAlloc 1
pop temp 0
push constant 0
return
function SquareGame.moveSquare 0
push argument 0
pop pointer 0
push this 1
push constant 1
eq
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push this 0
call Square.moveUp 1
pop temp 0
label IF_FALSE0
push this 1
push constant 2
eq
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push this 0
call Square.moveDown 1
pop temp 0
label IF_FALSE1
push this 1
push constant 3
eq
if-goto IF_TRUE2
goto IF_FALSE2
label IF_TRUE2
push this 0
call Square.moveLeft 1
pop temp 0
label IF_FALSE2
push this 1
push constant 4
eq
if-goto IF_TRUE3
goto IF_FALSE3
label IF_TRUE3
push this 0
call Square.moveRight 1
pop temp 0
label IF_FALSE3
push constant 5
call Sys.wait 1
pop temp 0
push constant 0
return
function SquareGame.run 2
push argument 0
pop pointer 0
push constant 0
pop local 1
label WHILE_EXP0
push local 1
not
not
if-goto WHILE_END0
label WHILE_EXP1
push local 0
push constant 0
eq
not
if-goto WHILE_END1
call Keyboard.keyPressed 0
pop local 0
push pointer 0
call SquareGame.moveSquare 1
pop temp 0
goto WHILE_EXP1
label WHILE_END1
push local 0
push constant 81
eq
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 0
not
pop local 1
label IF_FALSE0
push local 0
push constant 90
eq
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push this 0
call Square.decSize 1
pop temp 0
label IF_FALSE1
push local 0
push constant 88
eq
if-goto IF_TRUE2
goto IF_FALSE2
label IF_TRUE2
push this 0
call Square.incSize 1
pop temp 0
label IF_FALSE2
push local 0
push constant 131
eq
if-goto IF_TRUE3
goto IF_FALSE3
label IF_TRUE3
push constant 1
pop this 1
label IF_FALSE3
push local 0
push constant 133
eq
if-goto IF_TRUE4
goto IF_FALSE4
label IF_TRUE4
push constant 2
pop this 1
label IF_FALSE4
push local 0
push constant 130
eq
if-goto IF_TRUE5
goto IF_FALSE5
label IF_TRUE5
push constant 3
pop this 1
label IF_FALSE5
push local 0
push constant 132
eq
if-goto IF_TRUE6
goto IF_FALSE6
label IF_TRUE6
push constant 4
pop this 1
label IF_FALSE6
label WHILE_EXP2
push local 0
push constant 0
eq
not
not
if-goto WHILE_END2
call Keyboard.keyPressed 0
pop local 0
push pointer 0
call SquareGame.moveSquare 1
pop temp 0
goto WHILE_EXP2
label WHILE_END2
goto WHILE_EXP0
label WHILE_END0
push constant 0
return
Average
Este programa calcula el promedio de una secuencia de números enteros proporcionada por el usuario. Para probarlo debemos ejecutar el código traducido en el VMEmulator y seguir las instrucciones que se muestran en la pantalla.
Resultados obtenidos
Main.vm
function Main.main 4
push constant 18
call String.new 1
push constant 72
call String.appendChar 2
push constant 111
call String.appendChar 2
push constant 119
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 109
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 110
call String.appendChar 2
push constant 121
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 110
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 109
call String.appendChar 2
push constant 98
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 63
call String.appendChar 2
push constant 32
call String.appendChar 2
call Keyboard.readInt 1
pop local 1
push local 1
call Array.new 1
pop local 0
push constant 0
pop local 2
label WHILE_EXP0
push local 2
push local 1
lt
not
if-goto WHILE_END0
push local 2
push local 0
add
push constant 16
call String.new 1
push constant 69
call String.appendChar 2
push constant 110
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 110
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 109
call String.appendChar 2
push constant 98
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
call Keyboard.readInt 1
pop temp 0
pop pointer 1
push temp 0
pop that 0
push local 3
push local 2
push local 0
add
pop pointer 1
push that 0
add
pop local 3
push local 2
push constant 1
add
pop local 2
goto WHILE_EXP0
label WHILE_END0
push constant 15
call String.new 1
push constant 84
call String.appendChar 2
push constant 104
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 118
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 103
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 105
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 32
call String.appendChar 2
call Output.printString 1
pop temp 0
push local 3
push local 1
call Math.divide 2
call Output.printInt 1
pop temp 0
push constant 0
return
Pong
Este programa es un juego. Una pelota se mueve aleatoriamente en la pantalla, rebotando en las “paredes” de la pantalla. El usuario puede mover una pequeña superficie presionando las teclas de flecha izquierda y derecha del teclado. Cada vez que la superficie golpea la pelota, el usuario anota un punto y esta se encoge un poco, para hacer el juego más difícil. Si el usuario falla y la pelota golpea la línea horizontal inferior, el juego termina. Para probarlo debemos ejecute el código traducido en el VMEmulator y jugar un poco.
Resultados obtenidos
Ball.vm
function Ball.new 0
push constant 15
call Memory.alloc 1
pop pointer 0
push argument 0
pop this 0
push argument 1
pop this 1
push argument 2
pop this 10
push argument 3
push constant 6
sub
pop this 11
push argument 4
pop this 12
push argument 5
push constant 6
sub
pop this 13
push constant 0
pop this 14
push pointer 0
call Ball.show 1
pop temp 0
push pointer 0
return
function Ball.dispose 0
push argument 0
pop pointer 0
push pointer 0
call Memory.deAlloc 1
pop temp 0
push constant 0
return
function Ball.show 0
push argument 0
pop pointer 0
push constant 0
not
call Screen.setColor 1
pop temp 0
push pointer 0
call Ball.draw 1
pop temp 0
push constant 0
return
function Ball.hide 0
push argument 0
pop pointer 0
push constant 0
call Screen.setColor 1
pop temp 0
push pointer 0
call Ball.draw 1
pop temp 0
push constant 0
return
function Ball.draw 0
push argument 0
pop pointer 0
push this 0
push this 1
push this 0
push constant 5
add
push this 1
push constant 5
add
call Screen.drawRectangle 4
pop temp 0
push constant 0
return
function Ball.getLeft 0
push argument 0
pop pointer 0
push this 0
return
function Ball.getRight 0
push argument 0
pop pointer 0
push this 0
push constant 5
add
return
function Ball.setDestination 3
push argument 0
pop pointer 0
push argument 1
push this 0
sub
pop this 2
push argument 2
push this 1
sub
pop this 3
push this 2
call Math.abs 1
pop local 0
push this 3
call Math.abs 1
pop local 1
push local 0
push local 1
lt
pop this 7
push this 7
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push local 0
pop local 2
push local 1
pop local 0
push local 2
pop local 1
push this 1
push argument 2
lt
pop this 8
push this 0
push argument 1
lt
pop this 9
goto IF_END0
label IF_FALSE0
push this 0
push argument 1
lt
pop this 8
push this 1
push argument 2
lt
pop this 9
label IF_END0
push constant 2
push local 1
call Math.multiply 2
push local 0
sub
pop this 4
push constant 2
push local 1
call Math.multiply 2
pop this 5
push constant 2
push local 1
push local 0
sub
call Math.multiply 2
pop this 6
push constant 0
return
function Ball.move 0
push argument 0
pop pointer 0
push pointer 0
call Ball.hide 1
pop temp 0
push this 4
push constant 0
lt
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push this 4
push this 5
add
pop this 4
goto IF_END0
label IF_FALSE0
push this 4
push this 6
add
pop this 4
push this 9
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push this 7
if-goto IF_TRUE2
goto IF_FALSE2
label IF_TRUE2
push this 0
push constant 4
add
pop this 0
goto IF_END2
label IF_FALSE2
push this 1
push constant 4
add
pop this 1
label IF_END2
goto IF_END1
label IF_FALSE1
push this 7
if-goto IF_TRUE3
goto IF_FALSE3
label IF_TRUE3
push this 0
push constant 4
sub
pop this 0
goto IF_END3
label IF_FALSE3
push this 1
push constant 4
sub
pop this 1
label IF_END3
label IF_END1
label IF_END0
push this 8
if-goto IF_TRUE4
goto IF_FALSE4
label IF_TRUE4
push this 7
if-goto IF_TRUE5
goto IF_FALSE5
label IF_TRUE5
push this 1
push constant 4
add
pop this 1
goto IF_END5
label IF_FALSE5
push this 0
push constant 4
add
pop this 0
label IF_END5
goto IF_END4
label IF_FALSE4
push this 7
if-goto IF_TRUE6
goto IF_FALSE6
label IF_TRUE6
push this 1
push constant 4
sub
pop this 1
goto IF_END6
label IF_FALSE6
push this 0
push constant 4
sub
pop this 0
label IF_END6
label IF_END4
push this 0
push this 10
gt
not
if-goto IF_TRUE7
goto IF_FALSE7
label IF_TRUE7
push constant 1
pop this 14
push this 10
pop this 0
label IF_FALSE7
push this 0
push this 11
lt
not
if-goto IF_TRUE8
goto IF_FALSE8
label IF_TRUE8
push constant 2
pop this 14
push this 11
pop this 0
label IF_FALSE8
push this 1
push this 12
gt
not
if-goto IF_TRUE9
goto IF_FALSE9
label IF_TRUE9
push constant 3
pop this 14
push this 12
pop this 1
label IF_FALSE9
push this 1
push this 13
lt
not
if-goto IF_TRUE10
goto IF_FALSE10
label IF_TRUE10
push constant 4
pop this 14
push this 13
pop this 1
label IF_FALSE10
push pointer 0
call Ball.show 1
pop temp 0
push this 14
return
function Ball.bounce 5
push argument 0
pop pointer 0
push this 2
push constant 10
call Math.divide 2
pop local 2
push this 3
push constant 10
call Math.divide 2
pop local 3
push argument 1
push constant 0
eq
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push constant 10
pop local 4
goto IF_END0
label IF_FALSE0
push this 2
push constant 0
lt
not
push argument 1
push constant 1
eq
and
push this 2
push constant 0
lt
push argument 1
push constant 1
neg
eq
and
or
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push constant 20
pop local 4
goto IF_END1
label IF_FALSE1
push constant 5
pop local 4
label IF_END1
label IF_END0
push this 14
push constant 1
eq
if-goto IF_TRUE2
goto IF_FALSE2
label IF_TRUE2
push constant 506
pop local 0
push local 3
push constant 50
neg
call Math.multiply 2
push local 2
call Math.divide 2
pop local 1
push this 1
push local 1
push local 4
call Math.multiply 2
add
pop local 1
goto IF_END2
label IF_FALSE2
push this 14
push constant 2
eq
if-goto IF_TRUE3
goto IF_FALSE3
label IF_TRUE3
push constant 0
pop local 0
push local 3
push constant 50
call Math.multiply 2
push local 2
call Math.divide 2
pop local 1
push this 1
push local 1
push local 4
call Math.multiply 2
add
pop local 1
goto IF_END3
label IF_FALSE3
push this 14
push constant 3
eq
if-goto IF_TRUE4
goto IF_FALSE4
label IF_TRUE4
push constant 250
pop local 1
push local 2
push constant 25
neg
call Math.multiply 2
push local 3
call Math.divide 2
pop local 0
push this 0
push local 0
push local 4
call Math.multiply 2
add
pop local 0
goto IF_END4
label IF_FALSE4
push constant 0
pop local 1
push local 2
push constant 25
call Math.multiply 2
push local 3
call Math.divide 2
pop local 0
push this 0
push local 0
push local 4
call Math.multiply 2
add
pop local 0
label IF_END4
label IF_END3
label IF_END2
push pointer 0
push local 0
push local 1
call Ball.setDestination 3
pop temp 0
push constant 0
return
Bat.vm
function Bat.new 0
push constant 5
call Memory.alloc 1
pop pointer 0
push argument 0
pop this 0
push argument 1
pop this 1
push argument 2
pop this 2
push argument 3
pop this 3
push constant 2
pop this 4
push pointer 0
call Bat.show 1
pop temp 0
push pointer 0
return
function Bat.dispose 0
push argument 0
pop pointer 0
push pointer 0
call Memory.deAlloc 1
pop temp 0
push constant 0
return
function Bat.show 0
push argument 0
pop pointer 0
push constant 0
not
call Screen.setColor 1
pop temp 0
push pointer 0
call Bat.draw 1
pop temp 0
push constant 0
return
function Bat.hide 0
push argument 0
pop pointer 0
push constant 0
call Screen.setColor 1
pop temp 0
push pointer 0
call Bat.draw 1
pop temp 0
push constant 0
return
function Bat.draw 0
push argument 0
pop pointer 0
push this 0
push this 1
push this 0
push this 2
add
push this 1
push this 3
add
call Screen.drawRectangle 4
pop temp 0
push constant 0
return
function Bat.setDirection 0
push argument 0
pop pointer 0
push argument 1
pop this 4
push constant 0
return
function Bat.getLeft 0
push argument 0
pop pointer 0
push this 0
return
function Bat.getRight 0
push argument 0
pop pointer 0
push this 0
push this 2
add
return
function Bat.setWidth 0
push argument 0
pop pointer 0
push pointer 0
call Bat.hide 1
pop temp 0
push argument 1
pop this 2
push pointer 0
call Bat.show 1
pop temp 0
push constant 0
return
function Bat.move 0
push argument 0
pop pointer 0
push this 4
push constant 1
eq
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push this 0
push constant 4
sub
pop this 0
push this 0
push constant 0
lt
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push constant 0
pop this 0
label IF_FALSE1
push constant 0
call Screen.setColor 1
pop temp 0
push this 0
push this 2
add
push constant 1
add
push this 1
push this 0
push this 2
add
push constant 4
add
push this 1
push this 3
add
call Screen.drawRectangle 4
pop temp 0
push constant 0
not
call Screen.setColor 1
pop temp 0
push this 0
push this 1
push this 0
push constant 3
add
push this 1
push this 3
add
call Screen.drawRectangle 4
pop temp 0
goto IF_END0
label IF_FALSE0
push this 0
push constant 4
add
pop this 0
push this 0
push this 2
add
push constant 511
gt
if-goto IF_TRUE2
goto IF_FALSE2
label IF_TRUE2
push constant 511
push this 2
sub
pop this 0
label IF_FALSE2
push constant 0
call Screen.setColor 1
pop temp 0
push this 0
push constant 4
sub
push this 1
push this 0
push constant 1
sub
push this 1
push this 3
add
call Screen.drawRectangle 4
pop temp 0
push constant 0
not
call Screen.setColor 1
pop temp 0
push this 0
push this 2
add
push constant 3
sub
push this 1
push this 0
push this 2
add
push this 1
push this 3
add
call Screen.drawRectangle 4
pop temp 0
label IF_END0
push constant 0
return
Main.vm
function Main.main 1
call PongGame.newInstance 0
pop temp 0
call PongGame.getInstance 0
pop local 0
push local 0
call PongGame.run 1
pop temp 0
push local 0
call PongGame.dispose 1
pop temp 0
push constant 0
return
PongGame.vm
function PongGame.new 0
push constant 7
call Memory.alloc 1
pop pointer 0
call Screen.clearScreen 0
pop temp 0
push constant 50
pop this 6
push constant 230
push constant 229
push this 6
push constant 7
call Bat.new 4
pop this 0
push constant 253
push constant 222
push constant 0
push constant 511
push constant 0
push constant 229
call Ball.new 6
pop this 1
push this 1
push constant 400
push constant 0
call Ball.setDestination 3
pop temp 0
push constant 0
push constant 238
push constant 511
push constant 240
call Screen.drawRectangle 4
pop temp 0
push constant 22
push constant 0
call Output.moveCursor 2
pop temp 0
push constant 8
call String.new 1
push constant 83
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 111
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 48
call String.appendChar 2
call Output.printString 1
pop temp 0
push constant 0
pop this 3
push constant 0
pop this 4
push constant 0
pop this 2
push constant 0
pop this 5
push pointer 0
return
function PongGame.dispose 0
push argument 0
pop pointer 0
push this 0
call Bat.dispose 1
pop temp 0
push this 1
call Ball.dispose 1
pop temp 0
push pointer 0
call Memory.deAlloc 1
pop temp 0
push constant 0
return
function PongGame.newInstance 0
call PongGame.new 0
pop static 0
push constant 0
return
function PongGame.getInstance 0
push static 0
return
function PongGame.run 1
push argument 0
pop pointer 0
label WHILE_EXP0
push this 3
not
not
if-goto WHILE_END0
label WHILE_EXP1
push local 0
push constant 0
eq
push this 3
not
and
not
if-goto WHILE_END1
call Keyboard.keyPressed 0
pop local 0
push this 0
call Bat.move 1
pop temp 0
push pointer 0
call PongGame.moveBall 1
pop temp 0
push constant 50
call Sys.wait 1
pop temp 0
goto WHILE_EXP1
label WHILE_END1
push local 0
push constant 130
eq
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push this 0
push constant 1
call Bat.setDirection 2
pop temp 0
goto IF_END0
label IF_FALSE0
push local 0
push constant 132
eq
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push this 0
push constant 2
call Bat.setDirection 2
pop temp 0
goto IF_END1
label IF_FALSE1
push local 0
push constant 140
eq
if-goto IF_TRUE2
goto IF_FALSE2
label IF_TRUE2
push constant 0
not
pop this 3
label IF_FALSE2
label IF_END1
label IF_END0
label WHILE_EXP2
push local 0
push constant 0
eq
not
push this 3
not
and
not
if-goto WHILE_END2
call Keyboard.keyPressed 0
pop local 0
push this 0
call Bat.move 1
pop temp 0
push pointer 0
call PongGame.moveBall 1
pop temp 0
push constant 50
call Sys.wait 1
pop temp 0
goto WHILE_EXP2
label WHILE_END2
goto WHILE_EXP0
label WHILE_END0
push this 3
if-goto IF_TRUE3
goto IF_FALSE3
label IF_TRUE3
push constant 10
push constant 27
call Output.moveCursor 2
pop temp 0
push constant 9
call String.new 1
push constant 71
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 109
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 79
call String.appendChar 2
push constant 118
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 114
call String.appendChar 2
call Output.printString 1
pop temp 0
label IF_FALSE3
push constant 0
return
function PongGame.moveBall 5
push argument 0
pop pointer 0
push this 1
call Ball.move 1
pop this 2
push this 2
push constant 0
gt
push this 2
push this 5
eq
not
and
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push this 2
pop this 5
push constant 0
pop local 0
push this 0
call Bat.getLeft 1
pop local 1
push this 0
call Bat.getRight 1
pop local 2
push this 1
call Ball.getLeft 1
pop local 3
push this 1
call Ball.getRight 1
pop local 4
push this 2
push constant 4
eq
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
push local 1
push local 4
gt
push local 2
push local 3
lt
or
pop this 3
push this 3
not
if-goto IF_TRUE2
goto IF_FALSE2
label IF_TRUE2
push local 4
push local 1
push constant 10
add
lt
if-goto IF_TRUE3
goto IF_FALSE3
label IF_TRUE3
push constant 1
neg
pop local 0
goto IF_END3
label IF_FALSE3
push local 3
push local 2
push constant 10
sub
gt
if-goto IF_TRUE4
goto IF_FALSE4
label IF_TRUE4
push constant 1
pop local 0
label IF_FALSE4
label IF_END3
push this 6
push constant 2
sub
pop this 6
push this 0
push this 6
call Bat.setWidth 2
pop temp 0
push this 4
push constant 1
add
pop this 4
push constant 22
push constant 7
call Output.moveCursor 2
pop temp 0
push this 4
call Output.printInt 1
pop temp 0
label IF_FALSE2
label IF_FALSE1
push this 1
push local 0
call Ball.bounce 2
pop temp 0
label IF_FALSE0
push constant 0
return
Complex arrays
Este programa realiza cinco cálculos complejos utilizando matrices. Para cada cálculo de este tipo, el programa imprime en la pantalla el resultado esperado frente al resultado real (tal como lo realiza el programa compilado). Para probar probarlo debemos utilizar el .vm traducido y ejecutarlo en el VMEmulator y asegurarnos de que los resultados reales sean idénticos a los resultados esperados.
Resultados obtenidos
Main.vm
function Main.main 3
push constant 10
call Array.new 1
pop local 0
push constant 5
call Array.new 1
pop local 1
push constant 1
call Array.new 1
pop local 2
push constant 3
push local 0
add
push constant 2
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 4
push local 0
add
push constant 8
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 5
push local 0
add
push constant 4
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 3
push local 0
add
pop pointer 1
push that 0
push local 1
add
push constant 3
push local 0
add
pop pointer 1
push that 0
push constant 3
add
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 3
push local 0
add
pop pointer 1
push that 0
push local 1
add
pop pointer 1
push that 0
push local 0
add
push constant 5
push local 0
add
pop pointer 1
push that 0
push local 0
add
pop pointer 1
push that 0
push constant 7
push constant 3
push local 0
add
pop pointer 1
push that 0
sub
push constant 2
call Main.double 1
sub
push constant 1
add
push local 1
add
pop pointer 1
push that 0
call Math.multiply 2
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 0
push local 2
add
push constant 0
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 0
push local 2
add
pop pointer 1
push that 0
pop local 2
push constant 43
call String.new 1
push constant 84
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 49
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 120
call String.appendChar 2
push constant 112
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 100
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 53
call String.appendChar 2
push constant 59
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
call Output.printString 1
pop temp 0
push constant 2
push local 1
add
pop pointer 1
push that 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
push constant 44
call String.new 1
push constant 84
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 50
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 120
call String.appendChar 2
push constant 112
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 100
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 52
call String.appendChar 2
push constant 48
call String.appendChar 2
push constant 59
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
call Output.printString 1
pop temp 0
push constant 5
push local 0
add
pop pointer 1
push that 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
push constant 43
call String.new 1
push constant 84
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 51
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 120
call String.appendChar 2
push constant 112
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 100
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 48
call String.appendChar 2
push constant 59
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
call Output.printString 1
pop temp 0
push local 2
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
push constant 0
pop local 2
push local 2
push constant 0
eq
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
push local 0
push constant 10
call Main.fill 2
pop temp 0
push constant 3
push local 0
add
pop pointer 1
push that 0
pop local 2
push constant 1
push local 2
add
push constant 33
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 7
push local 0
add
pop pointer 1
push that 0
pop local 2
push constant 1
push local 2
add
push constant 77
pop temp 0
pop pointer 1
push temp 0
pop that 0
push constant 3
push local 0
add
pop pointer 1
push that 0
pop local 1
push constant 1
push local 1
add
push constant 1
push local 1
add
pop pointer 1
push that 0
push constant 1
push local 2
add
pop pointer 1
push that 0
add
pop temp 0
pop pointer 1
push temp 0
pop that 0
label IF_FALSE0
push constant 44
call String.new 1
push constant 84
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 52
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 120
call String.appendChar 2
push constant 112
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 100
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 55
call String.appendChar 2
push constant 55
call String.appendChar 2
push constant 59
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
call Output.printString 1
pop temp 0
push constant 1
push local 2
add
pop pointer 1
push that 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
push constant 45
call String.new 1
push constant 84
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 53
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 120
call String.appendChar 2
push constant 112
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 100
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 49
call String.appendChar 2
push constant 49
call String.appendChar 2
push constant 48
call String.appendChar 2
push constant 59
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 99
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 97
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 32
call String.appendChar 2
push constant 114
call String.appendChar 2
push constant 101
call String.appendChar 2
push constant 115
call String.appendChar 2
push constant 117
call String.appendChar 2
push constant 108
call String.appendChar 2
push constant 116
call String.appendChar 2
push constant 58
call String.appendChar 2
push constant 32
call String.appendChar 2
call Output.printString 1
pop temp 0
push constant 1
push local 1
add
pop pointer 1
push that 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
push constant 0
return
function Main.double 0
push argument 0
push constant 2
call Math.multiply 2
return
function Main.fill 0
label WHILE_EXP0
push argument 1
push constant 0
gt
not
if-goto WHILE_END0
push argument 1
push constant 1
sub
pop argument 1
push argument 1
push argument 0
add
push constant 3
call Array.new 1
pop temp 0
pop pointer 1
push temp 0
pop that 0
goto WHILE_EXP0
label WHILE_END0
push constant 0
return
Proyecto 12. Operating System
Desarrollo
Los sistemas informáticos deben admitir operaciones matemáticas como la suma, la multiplicación y la división. Normalmente, la suma se implementa en hardware como lo vimos cuando trabajamos la ALU. Otras operaciones como la multiplicación y la división pueden ser manejadas por hardware o software es por eso que primeramente debemos ver cómo se pueden implementar de manera eficiente en el software, a nivel del sistema operativo.
Multiplicación: para la multiplicación se considerará el método estándar de multiplicación que nos enseñan. Para calcular 356 por 27, alineamos los dos números uno encima del otro. Luego, multiplicamos cada dígito de 356 por 7. Luego, “desplazamos hacia la izquierda” una posición y multiplicamos cada dígito de 356 por 2. Finalmente, sumamos las columnas y obtenemos el resultado. Todo esto en binario lo podemos ver en la siguiente figura
Figura 4. Multiplicación de dos números de n bits
Figura 5. Algoritmo de multiplicación
División: la forma sencilla de calcular la división de dos números de n bits x/y es restar repetidamente y de x hasta que sea imposible continuar (es decir, hasta que x < y). Pero podemos acelerar este algoritmo, podemos intentar restar grandes porciones de y de x en cada iteración. Por ejemplo, si x = 891 e y = 5, podemos decir de inmediato que podemos deducir cien 5 de x y el resto seguirá siendo mayor que 5, eliminando así 100 iteraciones del enfoque ingenuo. Formalmente, en cada iteración tratamos de restar de x el mayor desplazamiento posible de y, a saber, y * T donde T es la mayor potencia de 10 tal que y * T ≤ x.
Figura 6. Algoritmo de división
Raíz cuadrada: para las raíces cuadradas, bastará un algoritmo simple. La función raíz cuadrada y = √x tiene dos propiedades. Primero, es monótonamente creciente. Segundo, su función inversa, x = y^2 , es algo que ya sabemos calcular (multiplicación). O sea tenemos todo lo que necesitamos para calcular raíces cuadradas mediante lo se llama "búsqueda binaria".
Figura 7. Algoritmo para el cálculo de raíces cuadradas usando búsqueda binaria
Otro aspecto que debemos tener en cuenta para el desarrollo del SO es que, los computadores generalmente están conectadas a una variedad de dispositivos como teclado, pantalla, mouse, discos, etc. Cada uno de estos dispositivos de tiene sus propias idiosincrasias electromecánicas y físicas y, por lo tanto, leer y escribir datos en ellos implica muchos detalles técnicos. Por lo tanto, una función importante del sistema operativo es manejar los diversos dispositivos conectados al computador. Esto se hace encapsulando los detalles de la interfaz del dispositivo y brindando acceso conveniente a su funcionalidad básica, utilizando un conjunto de rutinas de O/S conocidas los controladores (drivers) del dispositivo. Por lo que debemos ver cómo manejaremos los dispositivos más frecuentes como: una pantalla y un teclado.
Se divide el manejo de la pantalla en dos partes lógicamente separadas: el manejo de la salida de gráficos y el manejo de la salida de caracteres.
Salida de gráficos
Dibujo de píxeles: dibujar un píxel se logra escribiendo el valor binario adecuado en la ubicación de RAM que representa el píxel requerido en la memoria. Por lo que hay que formular un algoritmo drawPixel Entonces, ahora que sabemos cómo dibujar un solo píxel, pasemos a describir cómo dibujar líneas y círculos.
Figura 8. Dibujar un píxel
Manejo de salida de caracteres
Salida de caracteres: para desarrollar la capacidad de escribir texto en una pantalla de mapa de bits, primero tenemos que dividir la pantalla física orientada a píxeles en una pantalla lógica orientada a caracteres adecuada para escribir caracteres completos. Por ejemplo, consideremos una pantalla de 256 filas por 512 columnas. Si asignamos una cuadrícula de 11 * 8 píxeles para dibujar un solo carácter (11 filas, 8 columnas), nuestra pantalla puede mostrar 23 líneas de 64 caracteres cada una (con 3 filas adicionales de píxeles sin usar). Luego, para cada carácter que queremos mostrar en la pantalla, podemos diseñar una fuente atractiva y luego implementar la fuente usando una serie de mapas de bits de caracteres. Por ejemplo, la siguiente figura da un posible mapa de bits para la letra 'A'.
Figura 9. Mapa de bits de la letra “A”.
Dicho todo lo anterior podemos decir que el desarrollo del el sistema operativo Jack se divide en ocho clases:
Matemáticas: proporcionará operaciones matemáticas básicas
String: implementará el tipo String y las operaciones relacionadas con cadenas
Array: implementará el tipo Array y las operaciones relacionadas con los arrays
Salida: manejará la salida de texto a la pantalla
Pantalla: manejará la salida gráfica a la pantalla
Teclado: manejará la entrada del usuario desde el teclado
Memoria: manejará las operaciones de memoria
Sys: proporcionará algunos servicios relacionados con la ejecución.
Las funciones que tiene cada clase podremos verlas en su respectivo código.
Math.jack
class Math {
static Array twoToThe;
function void init() {
let twoToThe = Array.new(16);
let twoToThe[0] = 1;
let twoToThe[1] = 2;
let twoToThe[2] = 4;
let twoToThe[3] = 8;
let twoToThe[4] = 16;
let twoToThe[5] = 32;
let twoToThe[6] = 64;
let twoToThe[7] = 128;
let twoToThe[8] = 256;
let twoToThe[9] = 512;
let twoToThe[10] = 1024;
let twoToThe[11] = 2048;
let twoToThe[12] = 4096;
let twoToThe[13] = 8192;
let twoToThe[14] = 16384;
let twoToThe[15] = 16384 + 16384;
return;
}
function int two_to_the(int power) {
return twoToThe[power];
}
function boolean bit(int x, int j) {
return ~((x & twoToThe[j]) = 0);
}
function int abs(int x) {
if (x < 0) {
let x = -x;
}
return x;
}
function int multiply(int x, int y) {
var int j;
var int sum;
var int shiftedX;
let j = 0;
let sum = 0;
let shiftedX = x;
while (j < 16) { //each number is 16 bits
if (Math.bit(y, j) = true) {
let sum = sum + shiftedX;
}
let shiftedX = shiftedX + shiftedX;
let j = j + 1;
}
return sum;
}
function int divide(int x, int y) {
var int q;
var int result;
var int negX;
var int negY;
let negX = x < 0;
let negY = y < 0;
let x = Math.abs(x);
let y = Math.abs(y);
if(y > x) {
return 0;
}
let q = Math.divide(x, y + y);
if(x - (Math.multiply(q + q, y)) < y) {
let result = q + q;
}
else {
let result = q + q + 1;
}
if(negX = negY) {
return result;
}
else {
return -result;
}
}
function int sqrt(int x) {
var int result;
var int j;
var int checked;
var int squared;
let result = 0;
let j = 7;
while(~(j < 0)) {
let checked = result + twoToThe[j];
let squared = Math.multiply(checked, checked);
if(~(squared > x) & (squared > 0)) {
let result = checked;
}
let j = j - 1;
}
return result;
}
function int max(int a, int b) {
if (a > b) {
return a;
}
else {
return b;
}
}
function int min(int a, int b) {
if (a < b) {
return a;
}
else {
return b;
}
}
}
String.jack
class String {
field Array str;
field int length;
field int max;
constructor String new(int maxLength) {
if( maxLength = 0 ) {
let maxLength = 1;
}
let str = Array.new(maxLength);
let length = 0;
let max = maxLength;
return this;
}
method void dispose() {
do Array.dispose(str);
return;
}
method int length() {
return length;
}
method char charAt(int j) {
return str[j];
}
method void setCharAt(int j, char c) {
let str[j] = c;
return;
}
method String appendChar(char c) {
if (length < max) {
let str[length] = c;
let length = length + 1;
}
return this;
}
method void eraseLastChar() {
if (length > 0) {
let length = length - 1;
}
return;
}
method int intValue() {
var int i;
var int sum;
var boolean neg;
let sum = 0;
if ((length > 0) & (str[0] = 45)) { //'-' sign in ascii
let neg = true;
let i = 1;
}
else {
let neg = false;
let i = 0;
}
while (i < length) {
if (str[i] > 47 & str[i] < 58) { //the char is a digit between 0 to 9 in ascii
let sum = (sum * 10) + (str[i] - 48);
}
let i = i + 1;
}
if (neg) {
return -sum;
}
else {
return sum;
}
}
method void setInt(int number) {
let length = 0;
if (number < 0) {
let number = -number;
do appendChar(45); //add leading '-'
}
do recSetInt(number);
return;
}
method void recSetInt(int number) {
var int mod;
var int div;
let div = number / 10;
let mod = number - (div * 10);
if (number < 10)
{
do appendChar(mod + 48);
}
else{
do recSetInt(div);
do appendChar(mod + 48);
}
return;
}
function char newLine() {
return 128;
}
function char backSpace() {
return 129;
}
function char doubleQuote() {
return 34;
}
}
Array.jack
class Array {
function Array new(int size) {
return Memory.alloc(size);
}
method void dispose() {
do Memory.deAlloc(this);
return;
}
}
Output.jack
class Output {
static Array charMaps;
static Array lineLength;
static Array screen;
static Array align;
static int row, col;
static boolean whitePixel, blackPixel;
function void init() {
let row = 0;
let col = 0;
let screen = 16384;
let whitePixel = 0;
let blackPixel = 1;
let align = Array.new(2);
let align[0] = 255;
let align[1] = -1 & 255;
do Output.initMap();
do Output.initLineLength();
return;
}
function void initLineLength() {
let lineLength = Array.new(12);
let lineLength[0] = 0;
let lineLength[1] = 0;
let lineLength[2] = 0;
let lineLength[3] = 0;
let lineLength[4] = 0;
let lineLength[5] = 0;
let lineLength[6] = 0;
let lineLength[7] = 0;
let lineLength[8] = 0;
let lineLength[9] = 0;
let lineLength[10] = 0;
let lineLength[11] = 0;
return;
}
function void initMap() {
var int i;
let charMaps = Array.new(127);
do Output.create(0,63,63,63,63,63,63,63,63,63,0,0);
do Output.create(32,0,0,0,0,0,0,0,0,0,0,0); //
do Output.create(33,12,30,30,30,12,12,0,12,12,0,0); // !
do Output.create(34,54,54,20,0,0,0,0,0,0,0,0); // "
do Output.create(35,0,18,18,63,18,18,63,18,18,0,0); // #
do Output.create(36,12,30,51,3,30,48,51,30,12,12,0); // $
do Output.create(37,0,0,35,51,24,12,6,51,49,0,0); // %
do Output.create(38,12,30,30,12,54,27,27,27,54,0,0); // &
do Output.create(39,12,12,6,0,0,0,0,0,0,0,0); // '
do Output.create(40,24,12,6,6,6,6,6,12,24,0,0); // (
do Output.create(41,6,12,24,24,24,24,24,12,6,0,0); // )
do Output.create(42,0,0,0,51,30,63,30,51,0,0,0); // *
do Output.create(43,0,0,0,12,12,63,12,12,0,0,0); // +
do Output.create(44,0,0,0,0,0,0,0,12,12,6,0); // ,
do Output.create(45,0,0,0,0,0,63,0,0,0,0,0); // -
do Output.create(46,0,0,0,0,0,0,0,12,12,0,0); // .
do Output.create(47,0,0,32,48,24,12,6,3,1,0,0); // /
do Output.create(48,12,30,51,51,51,51,51,30,12,0,0); // 0
do Output.create(49,12,14,15,12,12,12,12,12,63,0,0); // 1
do Output.create(50,30,51,48,24,12,6,3,51,63,0,0); // 2
do Output.create(51,30,51,48,48,28,48,48,51,30,0,0); // 3
do Output.create(52,16,24,28,26,25,63,24,24,60,0,0); // 4
do Output.create(53,63,3,3,31,48,48,48,51,30,0,0); // 5
do Output.create(54,28,6,3,3,31,51,51,51,30,0,0); // 6
do Output.create(55,63,49,48,48,24,12,12,12,12,0,0); // 7
do Output.create(56,30,51,51,51,30,51,51,51,30,0,0); // 8
do Output.create(57,30,51,51,51,62,48,48,24,14,0,0); // 9
do Output.create(58,0,0,12,12,0,0,12,12,0,0,0); // :
do Output.create(59,0,0,12,12,0,0,12,12,6,0,0); // ;
do Output.create(60,0,0,24,12,6,3,6,12,24,0,0); // <
do Output.create(61,0,0,0,63,0,0,63,0,0,0,0); // =
do Output.create(62,0,0,3,6,12,24,12,6,3,0,0); // >
do Output.create(64,30,51,51,59,59,59,27,3,30,0,0); // @
do Output.create(63,30,51,51,24,12,12,0,12,12,0,0); // ?
do Output.create(65,12,30,51,51,63,51,51,51,51,0,0); // A
do Output.create(66,31,51,51,51,31,51,51,51,31,0,0); // B
do Output.create(67,28,54,35,3,3,3,35,54,28,0,0); // C
do Output.create(68,15,27,51,51,51,51,51,27,15,0,0); // D
do Output.create(69,63,51,35,11,15,11,35,51,63,0,0); // E
do Output.create(70,63,51,35,11,15,11,3,3,3,0,0); // F
do Output.create(71,28,54,35,3,59,51,51,54,44,0,0); // G
do Output.create(72,51,51,51,51,63,51,51,51,51,0,0); // H
do Output.create(73,30,12,12,12,12,12,12,12,30,0,0); // I
do Output.create(74,60,24,24,24,24,24,27,27,14,0,0); // J
do Output.create(75,51,51,51,27,15,27,51,51,51,0,0); // K
do Output.create(76,3,3,3,3,3,3,35,51,63,0,0); // L
do Output.create(77,33,51,63,63,51,51,51,51,51,0,0); // M
do Output.create(78,51,51,55,55,63,59,59,51,51,0,0); // N
do Output.create(79,30,51,51,51,51,51,51,51,30,0,0); // O
do Output.create(80,31,51,51,51,31,3,3,3,3,0,0); // P
do Output.create(81,30,51,51,51,51,51,63,59,30,48,0);// Q
do Output.create(82,31,51,51,51,31,27,51,51,51,0,0); // R
do Output.create(83,30,51,51,6,28,48,51,51,30,0,0); // S
do Output.create(84,63,63,45,12,12,12,12,12,30,0,0); // T
do Output.create(85,51,51,51,51,51,51,51,51,30,0,0); // U
do Output.create(86,51,51,51,51,51,30,30,12,12,0,0); // V
do Output.create(87,51,51,51,51,51,63,63,63,18,0,0); // W
do Output.create(88,51,51,30,30,12,30,30,51,51,0,0); // X
do Output.create(89,51,51,51,51,30,12,12,12,30,0,0); // Y
do Output.create(90,63,51,49,24,12,6,35,51,63,0,0); // Z
do Output.create(91,30,6,6,6,6,6,6,6,30,0,0); // [
do Output.create(92,0,0,1,3,6,12,24,48,32,0,0); // \
do Output.create(93,30,24,24,24,24,24,24,24,30,0,0); // ]
do Output.create(94,8,28,54,0,0,0,0,0,0,0,0); // ^
do Output.create(95,0,0,0,0,0,0,0,0,0,63,0); // _
do Output.create(96,6,12,24,0,0,0,0,0,0,0,0); // `
do Output.create(97,0,0,0,14,24,30,27,27,54,0,0); // a
do Output.create(98,3,3,3,15,27,51,51,51,30,0,0); // b
do Output.create(99,0,0,0,30,51,3,3,51,30,0,0); // c
do Output.create(100,48,48,48,60,54,51,51,51,30,0,0); // d
do Output.create(101,0,0,0,30,51,63,3,51,30,0,0); // e
do Output.create(102,28,54,38,6,15,6,6,6,15,0,0); // f
do Output.create(103,0,0,30,51,51,51,62,48,51,30,0); // g
do Output.create(104,3,3,3,27,55,51,51,51,51,0,0); // h
do Output.create(105,12,12,0,14,12,12,12,12,30,0,0); // i
do Output.create(106,48,48,0,56,48,48,48,48,51,30,0); // j
do Output.create(107,3,3,3,51,27,15,15,27,51,0,0); // k
do Output.create(108,14,12,12,12,12,12,12,12,30,0,0); // l
do Output.create(109,0,0,0,29,63,43,43,43,43,0,0); // m
do Output.create(110,0,0,0,29,51,51,51,51,51,0,0); // n
do Output.create(111,0,0,0,30,51,51,51,51,30,0,0); // o
do Output.create(112,0,0,0,30,51,51,51,31,3,3,0); // p
do Output.create(113,0,0,0,30,51,51,51,62,48,48,0); // q
do Output.create(114,0,0,0,29,55,51,3,3,7,0,0); // r
do Output.create(115,0,0,0,30,51,6,24,51,30,0,0); // s
do Output.create(116,4,6,6,15,6,6,6,54,28,0,0); // t
do Output.create(117,0,0,0,27,27,27,27,27,54,0,0); // u
do Output.create(118,0,0,0,51,51,51,51,30,12,0,0); // v
do Output.create(119,0,0,0,51,51,51,63,63,18,0,0); // w
do Output.create(120,0,0,0,51,30,12,12,30,51,0,0); // x
do Output.create(121,0,0,0,51,51,51,62,48,24,15,0); // y
do Output.create(122,0,0,0,63,27,12,6,51,63,0,0); // z
do Output.create(123,56,12,12,12,7,12,12,12,56,0,0); // {
do Output.create(124,12,12,12,12,12,12,12,12,12,0,0); // |
do Output.create(125,7,12,12,12,56,12,12,12,7,0,0); // }
do Output.create(126,38,45,25,0,0,0,0,0,0,0,0); // ~
return;
}
function void create(int index, int a, int b, int c, int d, int e,
int f, int g, int h, int i, int j, int k) {
var Array map;
let map = Array.new(11);
let charMaps[index] = map;
let map[0] = a;
let map[1] = b;
let map[2] = c;
let map[3] = d;
let map[4] = e;
let map[5] = f;
let map[6] = g;
let map[7] = h;
let map[8] = i;
let map[9] = j;
let map[10] = k;
return;
}
function Array getMap(char c) {
if ((c < 32) | (c > 126)) {
let c = 0;
}
return charMaps[c];
}
function void moveCursor(int i, int j) {
if (i > -1 & i < 23) {
let row = i;
}
else {
let row = 0;
}
if (j > -1 & j < 64) {
let col = j;
}
else {
let col = 0;
}
return;
}
function void printChar(char c) {
var Array map;
var int address;
var int pixel;
var int left;
var int i;
let map = Output.getMap(c);
let address = (row * 32 * 11) + (col / (16 / 8));
let left = col & 1;
let i = 0;
while (i < 11) {
let pixel = map[i];
if (left = 1) {
let pixel = pixel * 256;
}
let screen[address] = screen[address] & align[left] | pixel;
let address = address + 32;
let i = i + 1;
}
if (col = 63) {
if (row = 22) {
do Output.moveCursor(0,0);
}
else {
do Output.println();
}
}
else {
let col = col + 1;
}
return;
}
function void printString(String s) {
var int i;
let i = 0;
while (i < s.length()) {
do Output.printChar(s.charAt(i));
let i = i + 1;
}
return;
}
function void printInt(int i) {
var String s;
let s = String.new(16);
do s.setInt(i);
do Output.printString(s);
do s.dispose();
return;
}
function void println() {
if (row < 22) {
let lineLength[row] = col;
let row = row + 1;
}
else {
let row = 0;
}
let col = 0;
return;
}
function void backSpace() {
if (col = 0) {
if (row > 0) {
let row = row - 1;
let col = lineLength[row];
}
return;
}
if (col > 0) {
let col = col - 1;
}
do Output.printChar(" ");
let col = col - 1;
return;
}
}
Screen.jack
class Screen {
static boolean whitePixel;
static boolean blackPixel;
static boolean color;
static Array screen;
function void init() {
let screen = 16384;
let whitePixel = false;
let blackPixel = true;
let color = blackPixel;
return;
}
function void clearScreen() {
var int i;
let i = 0;
while (i < 8192) {
let screen[i] = whitePixel;
}
return;
}
function void setColor(boolean b) {
let color = b;
return;
}
function void drawPixel(int x, int y) {
var int address;
var int mask;
let address = (y * 32) + (x / 16);
let mask = Math.two_to_the(x & 15);
if (color) {
let screen[address] = screen[address] | mask;
}
else {
let screen[address] = screen[address] & ~mask;
}
return;
}
function void drawLine(int x1, int y1, int x2, int y2) {
var int dx, dy;
var int startX, startY;
var int i, j;
var int proportion;
let dx = x2 - x1;
let dy = y2 - y1;
let startX = Math.min(x1, x2);
let startY = Math.min(y1, y2);
// draw diagonal lines
if (((dx < 0) & (dy > 0)) | ((dx > 0) & (dy < 0))) {
if (dy < 0) {
do Screen.drawDiagonalLine(x1, y1, dx, dy);
} else {
do Screen.drawDiagonalLine(x2, y2, -dx, -dy);
}
return;
} else {
let dx = Math.abs(dx);
let dy = Math.abs(dy);
}
// When dx = 0 or dy = 0, use special functions
if (dy = 0) {
do Screen.drawVerticalLine(startX, startY, dx);
return;
}
if (dx = 0) {
do Screen.drawHorizontalLine(startX, startY, dy);
return;
}
let i = 0;
let j = 0;
let proportion = 0;
while (~(i > dx) & ~(j > dy)) {
do Screen.drawPixel(startX + i, startY + j);
if (proportion < 0) {
let i = i + 1;
let proportion = proportion + dy;
}
else {
let j = j + 1;
let proportion = proportion - dx;
}
}
return;
}
function void drawHorizontalLine(int x, int y, int dy) {
var int i;
let i = 0;
while (~(i > dy)) {
do Screen.drawPixel(x, y + i);
let i = i + 1;
}
return;
}
function void drawVerticalLine(int x, int y, int dx) {
var int i;
let i = 0;
while (~(i > dx)) {
do Screen.drawPixel(x + i, y);
let i = i + 1;
}
return;
}
function void drawDiagonalLine(int x, int y, int dx, int dy) {
var int proportion, i, j;
let proportion = 0;
let i = 0;
let j = 0;
while ((~(i > dx)) & (~(j < dy))) {
do Screen.drawPixel(x + i, y + j);
if (proportion < 0) {
let j = j - 1;
let proportion = proportion + dx;
} else {
let i = i + 1;
let proportion = proportion + dy;
}
}
return;
}
function void drawRectangle(int x1, int y1, int x2, int y2) {
var int dx, dy;
var int startX, startY;
var int i;
let dx = Math.abs(x2 - x1);
let dy = Math.abs(y2 - y1);
let startX = Math.min(x1, x2);
let startY = Math.min(y1, y2);
let i = 0;
while (i < dy) {
do Screen.drawVerticalLine(startX, startY + i, dx);
let i = i + 1;
}
return;
}
function void drawCircle(int cx, int cy, int r) {
var int dy;
var int sqrtDist;
let dy = -r;
while (~(dy > r)) {
let sqrtDist = Math.sqrt((r * r) - (dy * dy));
do Screen.drawVerticalLine(cx - sqrtDist, cy + dy, 2 * sqrtDist);
let dy = dy + 1;
}
return;
}
}
Keyboard.jack
class Keyboard {
static Array keyboard;
function void init() {
let keyboard = 24576;
return;
}
function char keyPressed() {
return keyboard[0];
}
function char readChar() {
var int c;
while (Keyboard.keyPressed() = 0) {}
let c = keyboard[0];
while (Keyboard.keyPressed() = c) {}
do Output.printChar(c);
return c;
}
function String readLine(String message) {
var String s;
var int c;
do Output.printString(message);
let s = String.new(100); //arbitrary length
let c = Keyboard.readChar();
while (~(c = String.newLine())) {
if (c = String.backSpace()) {
do s.eraseLastChar();
}
else {
do s.appendChar(c);
}
let c = Keyboard.readChar();
}
return s;
}
function int readInt(String message) {
var String s;
let s = Keyboard.readLine(message);
return s.intValue();
}
}
Memory.jack
class Memory {
static Array memory;
static int base, max;
static int length;
static int nextNode;
static int endOfList;
function void init() {
let memory = 0;
let base = 2048;
let max = 16384;
let length = base;
let nextNode = base + 1;
let endOfList = -1;
let memory[length] = max - base;
let memory[nextNode] = endOfList;
return;
}
function int peek(int address) {
return memory[address];
}
function void poke(int address, int value) {
let memory[address] = value;
return;
}
function int alloc(int size) {
var int currNode;
var int prevNode;
var int next;
var int returnAddress;
let prevNode = length;
let currNode = length;
let next = nextNode;
let returnAddress = -1;
while (~(memory[currNode] > size) & ~(memory[next] = endOfList)) {
let prevNode = currNode;
let currNode = memory[next];
let next = memory[next + 1];
}
if (~(next = endOfList)) { //found free block in the middle of the list
if (currNode < (size + 3)) {
let memory[prevNode + 1] = memory[currNode + 1];
let memory[currNode] = size + 1;
let returnAddress = currNode + 1;
}
else {
let memory[currNode] = memory[currNode] - size - 1;
let returnAddress = currNode + memory[currNode];
let memory[returnAddress - 1] = size + 1;
}
}
return returnAddress;
}
function void deAlloc(int object) {
let memory[object] = memory[object - 1];
let memory[object + 1] = memory[length + 1];
let memory[length + 1] = object;
return;
}
}
Sys.jack
class Sys {
function void init() {
do Memory.init();
do Math.init();
do Screen.init();
do Output.init();
do Keyboard.init();
do Main.main();
do Sys.halt();
return;
}
function void halt() {
while (true) {}
return;
}
function void wait(int duration) {
var int i;
var int j;
if (duration < 0) {
do Sys.error(1);
}
let i = 0;
while (i < duration) {
let j = 0;
while (j < 200) {
let j = j + 1;
}
let i = i + 1;
}
return;
}
function void error(int errorCode) {
do Output.printString("ERR");
do Output.printInt(errorCode);
do Sys.halt();
return;
}
}
Tests
Para cada clase del sistema operativo, se nos proporciona un archivo de clase xxx.jack con todas las subrutinas requeridas y con las clases main.jack junto con los scripts de prueba que siguen unas pautas que nos ayudan a verificar si los resultados son los esperados por medio de la herramienta VMEmulator por lo que hay que compilar cada clase y sus respectivos archivos de prueba .jack
Resultados obtenidos
Memory.jack
Como vemos en la figura, la comparación con el archivo de comparación finaliza correctamente.
Array.jack
Como vemos en la figura, la comparación con el archivo de comparación finaliza correctamente.
Math.jack
Como vemos en la figura, la comparación con el archivo de comparación finaliza correctamente.
Los siguientes programas de prueba restantes no incluyen scripts de prueba. Se deben probar directamente en el VMEmulato. Para comprobar que obtenemos los resultados esperados el proyecto nos proporciona imágenes sobre los resultados que debemos obtener
String.jack
Resultados esperados
Resultados obtenidos
Output.jack
Resultados esperados
Resultados obtenidos
Screen.jack
Resultados esperados
Resultados obtenidos
Keyboard.jack
Resultados esperados
Resultados obtenidos
Sys.jack
Resultados obtenidos
Una vez haber testeado con éxito cada clase del sistema operativo Jack de forma independiente, pasaremos a probar toda la implementación del sistema operativo utilizando el juego Pong, suministrado en el proyecto 11.
