Skip to content

Instantly share code, notes, and snippets.

@hyperswine

hyperswine/Prolog Execution Trace

Created December 17, 2023 07:07
Show Gist options
  • Save hyperswine/fe11a1567a27bd67439fc860c70e9884 to your computer and use it in GitHub Desktop.
Save hyperswine/fe11a1567a27bd67439fc860c70e9884 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Prolog Execution Trace
[trace] ?- test_1(Res).
Call: (10) test_1(_25790) ? creep
Call: (11) program(test1, _27100) ? creep
Exit: (11) program(test1, [program, test1, ;, begin, write, x, +, y|...]) ? creep
Call: (11) parse_and_assemble([program, test1, ;, begin, write, x, +, y|...], _25790) ? creep
Call: (12) parse([program, test1, ;, begin, write, x, +, y|...], _29610) ? creep
Call: (13) pl_program(_29610, [program, test1, ;, begin, write, x, +, y|...], _30498) ? creep
Call: (14) identifier(_31310, [test1, ;, begin, write, x, +, y, -|...], _31236) ? creep
Call: (15) atom(test1) ? creep
Exit: (15) atom(test1) ? creep
Call: (15) _31236=[;, begin, write, x, +, y, -, z|...] ? creep
Exit: (15) [;, begin, write, x, +, y, -, z|...]=[;, begin, write, x, +, y, -, z|...] ? creep
Exit: (14) identifier(test1, [test1, ;, begin, write, x, +, y, -|...], [;, begin, write, x, +, y, -, z|...]) ? creep
Call: (14) [;, begin, write, x, +, y, -, z|...]=[;|_36102] ? creep
Exit: (14) [;, begin, write, x, +, y, -, z|...]=[;, begin, write, x, +, y, -, z|...] ? creep
Call: (14) statement(_29610, [begin, write, x, +, y, -, z, /|...], _37724) ? creep
Call: (15) statement(_38542, [write, x, +, y, -, z, /, 2|...], _38546) ? creep
Call: (16) identifier(_39364, [write, x, +, y, -, z, /, 2|...], _39368) ? creep
Call: (17) atom(write) ? creep
Exit: (17) atom(write) ? creep
Call: (17) _39368=[x, +, y, -, z, /, 2, end] ? creep
Exit: (17) [x, +, y, -, z, /, 2, end]=[x, +, y, -, z, /, 2, end] ? creep
Exit: (16) identifier(write, [write, x, +, y, -, z, /, 2|...], [x, +, y, -, z, /, 2, end]) ? creep
Call: (16) [x, +, y, -, z, /, 2, end]=[:=|_44234] ? creep
Fail: (16) [x, +, y, -, z, /, 2, end]=[:=|_44234] ? creep
Redo: (15) statement(_38542, [write, x, +, y, -, z, /, 2|...], _38546) ? creep
Call: (16) expression(_46672, [x, +, y, -, z, /, 2, end], _38546) ? creep
Call: (17) pl_constant(_46672, [x, +, y, -, z, /, 2, end], _38546) ? creep
Call: (18) identifier(_48304, [x, +, y, -, z, /, 2, end], _38546) ? creep
Call: (19) atom(x) ? creep
Exit: (19) atom(x) ? creep
Call: (19) _38546=[+, y, -, z, /, 2, end] ? creep
Exit: (19) [+, y, -, z, /, 2, end]=[+, y, -, z, /, 2, end] ? creep
Exit: (18) identifier(x, [x, +, y, -, z, /, 2, end], [+, y, -, z, /, 2, end]) ? creep
Exit: (17) pl_constant(name(x), [x, +, y, -, z, /, 2, end], [+, y, -, z, /, 2, end]) ? creep
Exit: (16) expression(name(x), [x, +, y, -, z, /, 2, end], [+, y, -, z, /, 2, end]) ? creep
Exit: (15) statement(write(name(x)), [write, x, +, y, -, z, /, 2|...], [+, y, -, z, /, 2, end]) ? creep
Call: (15) rest_statements(_38544, [+, y, -, z, /, 2, end], _37724) ? creep
Fail: (15) rest_statements(_38544, [+, y, -, z, /, 2, end], _37724) ? creep
Redo: (17) pl_constant(_46672, [x, +, y, -, z, /, 2, end], _38546) ? creep
Call: (18) pl_integer(_58052, [x, +, y, -, z, /, 2, end], _38546) ? creep
Call: (19) integer(x) ? creep
Fail: (19) integer(x) ? creep
Fail: (18) pl_integer(_58052, [x, +, y, -, z, /, 2, end], _38546) ? creep
Fail: (17) pl_constant(_46672, [x, +, y, -, z, /, 2, end], _38546) ? creep
Redo: (16) expression(_46672, [x, +, y, -, z, /, 2, end], _38546) ? creep
Call: (17) pl_constant(_62926, [x, +, y, -, z, /, 2, end], _62930) ? creep
Call: (18) identifier(_63748, [x, +, y, -, z, /, 2, end], _62930) ? creep
Call: (19) atom(x) ? creep
Exit: (19) atom(x) ? creep
Call: (19) _62930=[+, y, -, z, /, 2, end] ? creep
Exit: (19) [+, y, -, z, /, 2, end]=[+, y, -, z, /, 2, end] ? creep
Exit: (18) identifier(x, [x, +, y, -, z, /, 2, end], [+, y, -, z, /, 2, end]) ? creep
Exit: (17) pl_constant(name(x), [x, +, y, -, z, /, 2, end], [+, y, -, z, /, 2, end]) ? creep
Call: (17) arithmetic_op(_176, [+, y, -, z, /, 2, end], _1338) ? creep
Exit: (17) arithmetic_op(+, [+, y, -, z, /, 2, end], [y, -, z, /, 2, end]) ? creep
Call: (17) expression(_180, [y, -, z, /, 2, end], _168) ? creep
Call: (18) pl_constant(_180, [y, -, z, /, 2, end], _168) ? creep
Call: (19) identifier(_4598, [y, -, z, /, 2, end], _168) ? creep
Call: (20) atom(y) ? creep
Exit: (20) atom(y) ? creep
Call: (20) _168=[-, z, /, 2, end] ? creep
Exit: (20) [-, z, /, 2, end]=[-, z, /, 2, end] ? creep
Exit: (19) identifier(y, [y, -, z, /, 2, end], [-, z, /, 2, end]) ? creep
Exit: (18) pl_constant(name(y), [y, -, z, /, 2, end], [-, z, /, 2, end]) ? creep
Exit: (17) expression(name(y), [y, -, z, /, 2, end], [-, z, /, 2, end]) ? creep
Exit: (16) expression(expr(+, name(x), name(y)), [x, +, y, -, z, /, 2, end], [-, z, /, 2, end]) ? creep
Exit: (15) statement(write(expr(+, name(x), name(y))), [write, x, +, y, -, z, /, 2|...], [-, z, /, 2, end]) ? creep
Call: (15) rest_statements(_166, [-, z, /, 2, end], _160) ? creep
Fail: (15) rest_statements(_166, [-, z, /, 2, end], _160) ? creep
Redo: (18) pl_constant(_180, [y, -, z, /, 2, end], _168) ? creep
Call: (19) pl_integer(_15160, [y, -, z, /, 2, end], _168) ? creep
Call: (20) integer(y) ? creep
Fail: (20) integer(y) ? creep
Fail: (19) pl_integer(_15160, [y, -, z, /, 2, end], _168) ? creep
Fail: (18) pl_constant(_180, [y, -, z, /, 2, end], _168) ? creep
Redo: (17) expression(_180, [y, -, z, /, 2, end], _168) ? creep
Call: (18) pl_constant(_20034, [y, -, z, /, 2, end], _20038) ? creep
Call: (19) identifier(_20856, [y, -, z, /, 2, end], _20038) ? creep
Call: (20) atom(y) ? creep
Exit: (20) atom(y) ? creep
Call: (20) _20038=[-, z, /, 2, end] ? creep
Exit: (20) [-, z, /, 2, end]=[-, z, /, 2, end] ? creep
Exit: (19) identifier(y, [y, -, z, /, 2, end], [-, z, /, 2, end]) ? creep
Exit: (18) pl_constant(name(y), [y, -, z, /, 2, end], [-, z, /, 2, end]) ? creep
Call: (18) arithmetic_op(_20032, [-, z, /, 2, end], _26532) ? creep
Exit: (18) arithmetic_op(-, [-, z, /, 2, end], [z, /, 2, end]) ? creep
Call: (18) expression(_20036, [z, /, 2, end], _168) ? creep
Call: (19) pl_constant(_20036, [z, /, 2, end], _168) ? creep
Call: (20) identifier(_29792, [z, /, 2, end], _168) ? creep
Call: (21) atom(z) ? creep
Exit: (21) atom(z) ? creep
Call: (21) _168=[/, 2, end] ? creep
Exit: (21) [/, 2, end]=[/, 2, end] ? creep
Exit: (20) identifier(z, [z, /, 2, end], [/, 2, end]) ? creep
Exit: (19) pl_constant(name(z), [z, /, 2, end], [/, 2, end]) ? creep
Exit: (18) expression(name(z), [z, /, 2, end], [/, 2, end]) ? creep
Exit: (17) expression(expr(-, name(y), name(z)), [y, -, z, /, 2, end], [/, 2, end]) ? creep
Exit: (16) expression(expr(+, name(x), expr(-, name(y), name(z))), [x, +, y, -, z, /, 2, end], [/, 2, end]) ? creep
Exit: (15) statement(write(expr(+, name(x), expr(-, name(y), name(z)))), [write, x, +, y, -, z, /, 2|...], [/, 2, end]) ? creep
Call: (15) rest_statements(_166, [/, 2, end], _160) ? creep
Fail: (15) rest_statements(_166, [/, 2, end], _160) ? creep
Redo: (19) pl_constant(_20036, [z, /, 2, end], _168) ? creep
Call: (20) pl_integer(_41168, [z, /, 2, end], _168) ? creep
Call: (21) integer(z) ? creep
Fail: (21) integer(z) ? creep
Fail: (20) pl_integer(_41168, [z, /, 2, end], _168) ? creep
Fail: (19) pl_constant(_20036, [z, /, 2, end], _168) ? creep
Redo: (18) expression(_20036, [z, /, 2, end], _168) ? creep
Call: (19) pl_constant(_46042, [z, /, 2, end], _46046) ? creep
Call: (20) identifier(_46864, [z, /, 2, end], _46046) ? creep
Call: (21) atom(z) ? creep
Exit: (21) atom(z) ? creep
Call: (21) _46046=[/, 2, end] ? creep
Exit: (21) [/, 2, end]=[/, 2, end] ? creep
Exit: (20) identifier(z, [z, /, 2, end], [/, 2, end]) ? creep
Exit: (19) pl_constant(name(z), [z, /, 2, end], [/, 2, end]) ? creep
Call: (19) arithmetic_op(_46040, [/, 2, end], _52540) ? creep
Exit: (19) arithmetic_op(/, [/, 2, end], [2, end]) ? creep
Call: (19) expression(_46044, [2, end], _168) ? creep
Call: (20) pl_constant(_46044, [2, end], _168) ? creep
Call: (21) identifier(_55800, [2, end], _168) ? creep
Call: (22) atom(2) ? creep
Fail: (22) atom(2) ? creep
Fail: (21) identifier(_55800, [2, end], _168) ? creep
Redo: (20) pl_constant(_46044, [2, end], _168) ? creep
Call: (21) pl_integer(_59858, [2, end], _168) ? creep
Call: (22) integer(2) ? creep
Exit: (22) integer(2) ? creep
Call: (22) _168=[end] ? creep
Exit: (22) [end]=[end] ? creep
Exit: (21) pl_integer(2, [2, end], [end]) ? creep
Exit: (20) pl_constant(number(2), [2, end], [end]) ? creep
Exit: (19) expression(number(2), [2, end], [end]) ? creep
Exit: (18) expression(expr(/, name(z), number(2)), [z, /, 2, end], [end]) ? creep
Exit: (17) expression(expr(-, name(y), expr(/, name(z), number(2))), [y, -, z, /, 2, end], [end]) ? creep
Exit: (16) expression(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))), [x, +, y, -, z, /, 2, end], [end]) ? creep
Exit: (15) statement(write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2))))), [write, x, +, y, -, z, /, 2|...], [end]) ? creep
Call: (15) rest_statements(_166, [end], _160) ? creep
Exit: (15) rest_statements(void, [end], []) ? creep
Exit: (14) statement((write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))));void), [begin, write, x, +, y, -, z, /|...], []) ? creep
Exit: (13) pl_program((write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))));void), [program, test1, ;, begin, write, x, +, y|...], []) ? creep
Exit: (12) parse([program, test1, ;, begin, write, x, +, y|...], (write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))));void)) ? creep
Call: (12) encode((write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))));void), _5646, _5648) ? creep
Call: (13) encode(write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2))))), _5646, _6466) ? creep
Call: (14) encode_expression(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))), _5646, _7286) ? creep
Call: (15) single_instruction(+, expr(-, name(y), expr(/, name(z), number(2))), _5646, _8114) ? creep
Fail: (15) single_instruction(+, expr(-, name(y), expr(/, name(z), number(2))), _5646, _8114) ? creep
Redo: (14) encode_expression(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))), _5646, _7286) ? creep
^ Call: (15) not(single_instruction(+, expr(-, name(y), expr(/, name(z), number(2))), _5646, _10574)) ? creep
Call: (16) single_instruction(+, expr(-, name(y), expr(/, name(z), number(2))), _5646, _10574) ? creep
Fail: (16) single_instruction(+, expr(-, name(y), expr(/, name(z), number(2))), _5646, _10574) ? creep
^ Exit: (15) not(user:single_instruction(+, expr(-, name(y), expr(/, name(z), number(2))), _5646, _10574)) ? creep
Call: (15) single_operation(+, name(x), _5646, _13854, _7286) ? creep
Call: (16) commutative(+) ? creep
Exit: (16) commutative(+) ? creep
Call: (16) single_instruction(+, name(x), _5646, _14682) ? creep
Call: (17) memory_operation(+, _17116) ? creep
Exit: (17) memory_operation(+, add) ? creep
Call: (17) lookup(x, _5646, _17118) ? creep
Call: (18) _19558=_17118 ? creep
Exit: (18) _17118=_17118 ? creep
Exit: (17) lookup(x, dict(x, _17118, _19560, _19562), _17118) ? creep
Exit: (16) single_instruction(+, name(x), dict(x, _17118, _19560, _19562), instr(add, _17118)) ? creep
Exit: (15) single_operation(+, name(x), dict(x, _17118, _19560, _19562), _13854, (_13854;instr(add, _17118))) ? creep
Call: (15) encode_expression(expr(-, name(y), expr(/, name(z), number(2))), dict(x, _17118, _19560, _19562), _13854) ? creep
Call: (16) single_instruction(-, expr(/, name(z), number(2)), dict(x, _17118, _19560, _19562), _24456) ? creep
Fail: (16) single_instruction(-, expr(/, name(z), number(2)), dict(x, _17118, _19560, _19562), _24456) ? creep
Redo: (15) encode_expression(expr(-, name(y), expr(/, name(z), number(2))), dict(x, _17118, _19560, _19562), _13854) ? creep
^ Call: (16) not(single_instruction(-, expr(/, name(z), number(2)), dict(x, _17118, _19560, _19562), _26916)) ? creep
Call: (17) single_instruction(-, expr(/, name(z), number(2)), dict(x, _17118, _19560, _19562), _26916) ? creep
Fail: (17) single_instruction(-, expr(/, name(z), number(2)), dict(x, _17118, _19560, _19562), _26916) ? creep
^ Exit: (16) not(user:single_instruction(-, expr(/, name(z), number(2)), dict(x, _17118, _19560, _19562), _26916)) ? creep
Call: (16) single_operation(-, name(y), dict(x, _17118, _19560, _19562), _30196, _13854) ? creep
Call: (17) commutative(-) ? creep
Fail: (17) commutative(-) ? creep
Redo: (16) single_operation(-, name(y), dict(x, _17118, _19560, _19562), _30196, _13854) ? creep
^ Call: (17) not(commutative(-)) ? creep
Call: (18) commutative(-) ? creep
Fail: (18) commutative(-) ? creep
^ Exit: (17) not(user:commutative(-)) ? creep
Call: (17) lookup('$temp', dict(x, _17118, _19560, _19562), _33476) ? creep
Call: (18) '$temp'@<x ? creep
Exit: (18) '$temp'@<x ? creep
Call: (18) lookup('$temp', _19560, _33476) ? creep
Call: (19) _40000=_33476 ? creep
Exit: (19) _33476=_33476 ? creep
Exit: (18) lookup('$temp', dict('$temp', _33476, _40002, _40004), _33476) ? creep
Exit: (17) lookup('$temp', dict(x, _17118, dict('$temp', _33476, _40002, _40004), _19562), _33476) ? creep
Call: (17) encode_expression(name(y), dict(x, _17118, dict('$temp', _33476, _40002, _40004), _19562), _33480) ? creep
Call: (18) lookup(y, dict(x, _17118, dict('$temp', _33476, _40002, _40004), _19562), _44072) ? creep
Call: (19) y@<x ? creep
Fail: (19) y@<x ? creep
Redo: (18) lookup(y, dict(x, _17118, dict('$temp', _33476, _40002, _40004), _19562), _44072) ? creep
Call: (19) y@>x ? creep
Exit: (19) y@>x ? creep
Call: (19) lookup(y, _19562, _44072) ? creep
Call: (20) _49760=_44072 ? creep
Exit: (20) _44072=_44072 ? creep
Exit: (19) lookup(y, dict(y, _44072, _49762, _49764), _44072) ? creep
Exit: (18) lookup(y, dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), _44072) ? creep
Exit: (17) encode_expression(name(y), dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), instr(load, _44072)) ? creep
Call: (17) op_code(name(y), -, _33486) ? creep
Call: (18) memory_operation(-, _33486) ? creep
Exit: (18) memory_operation(-, sub) ? creep
Exit: (17) op_code(name(y), -, sub) ? creep
Exit: (16) single_operation(-, name(y), dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), _30196, (_30196;instr(store, _33476);instr(load, _44072);instr(sub, _33476))) ? creep
Call: (16) encode_expression(expr(/, name(z), number(2)), dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), _30196) ? creep
Call: (17) single_instruction(/, number(2), dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), _58716) ? creep
Call: (18) literal_operation(/, _59538) ? creep
Exit: (18) literal_operation(/, divc) ? creep
Exit: (17) single_instruction(/, number(2), dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), instr(divc, 2)) ? creep
Call: (17) encode_expression(name(z), dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), _58714) ? creep
Call: (18) lookup(z, dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), _62798) ? creep
Call: (19) z@<x ? creep
Fail: (19) z@<x ? creep
Redo: (18) lookup(z, dict(x, _17118, dict('$temp', _33476, _40002, _40004), dict(y, _44072, _49762, _49764)), _62798) ? creep
Call: (19) z@>x ? creep
Exit: (19) z@>x ? creep
Call: (19) lookup(z, dict(y, _44072, _49762, _49764), _62798) ? creep
Call: (20) z@<y ? creep
Fail: (20) z@<y ? creep
Redo: (19) lookup(z, dict(y, _318, _326, _328), _346) ? creep
Call: (20) z@>y ? creep
Exit: (20) z@>y ? creep
Call: (20) lookup(z, _328, _346) ? creep
Call: (21) _5216=_346 ? creep
Exit: (21) _346=_346 ? creep
Exit: (20) lookup(z, dict(z, _346, _5218, _5220), _346) ? creep
Exit: (19) lookup(z, dict(y, _318, _326, dict(z, _346, _5218, _5220)), _346) ? creep
Exit: (18) lookup(z, dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), _346) ? creep
Exit: (17) encode_expression(name(z), dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), instr(load, _346)) ? creep
Exit: (16) encode_expression(expr(/, name(z), number(2)), dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), (instr(load, _346);instr(divc, 2))) ? creep
Exit: (15) encode_expression(expr(-, name(y), expr(/, name(z), number(2))), dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), ((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290))) ? creep
Exit: (14) encode_expression(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))), dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), (((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260))) ? creep
Exit: (13) encode(write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2))))), dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), ((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260));instr(write, 0))) ? creep
Call: (13) encode(void, dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), _234) ? creep
Exit: (13) encode(void, dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), no_op) ? creep
Exit: (12) encode((write(expr(+, name(x), expr(-, name(y), expr(/, name(z), number(2)))));void), dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), (((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260));instr(write, 0));no_op)) ? creep
Call: (12) assemble((((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260));instr(write, 0));no_op), dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), _18) ? creep
Call: (13) tidy_and_count((((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260));instr(write, 0));no_op), 1, _16610, _18\(instr(halt, 0);block(_16632))) ? creep
Call: (14) tidy_and_count(((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260));instr(write, 0)), 1, _17452, _18\_17458) ? creep
Call: (15) tidy_and_count((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260)), 1, _18278, _18\_18284) ? creep
Call: (16) tidy_and_count(((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290)), 1, _19104, _18\_19110) ? creep
Call: (17) tidy_and_count((instr(load, _346);instr(divc, 2)), 1, _19930, _18\_19936) ? creep
Call: (18) tidy_and_count(instr(load, _346), 1, _20756, _18\_20762) ? creep
Call: (19) _20756 is 1+1 ? creep
Exit: (19) 2 is 1+1 ? creep
Exit: (18) tidy_and_count(instr(load, _346), 1, 2, (instr(load, _346);_20762)\_20762) ? creep
Call: (18) tidy_and_count(instr(divc, 2), 2, _19930, _20762\_19936) ? creep
Call: (19) _19930 is 2+1 ? creep
Exit: (19) 3 is 2+1 ? creep
Exit: (18) tidy_and_count(instr(divc, 2), 2, 3, (instr(divc, 2);_19936)\_19936) ? creep
Exit: (17) tidy_and_count((instr(load, _346);instr(divc, 2)), 1, 3, (instr(load, _346);instr(divc, 2);_19936)\_19936) ? creep
Call: (17) tidy_and_count((instr(store, _290);instr(load, _318);instr(sub, _290)), 3, _19104, _19936\_19110) ? creep
Call: (18) tidy_and_count(instr(store, _290), 3, _28960, _19936\_28966) ? creep
Call: (19) _28960 is 3+1 ? creep
Exit: (19) 4 is 3+1 ? creep
Exit: (18) tidy_and_count(instr(store, _290), 3, 4, (instr(store, _290);_28966)\_28966) ? creep
Call: (18) tidy_and_count((instr(load, _318);instr(sub, _290)), 4, _19104, _28966\_19110) ? creep
Call: (19) tidy_and_count(instr(load, _318), 4, _33066, _28966\_33072) ? creep
Call: (20) _33066 is 4+1 ? creep
Exit: (20) 5 is 4+1 ? creep
Exit: (19) tidy_and_count(instr(load, _318), 4, 5, (instr(load, _318);_33072)\_33072) ? creep
Call: (19) tidy_and_count(instr(sub, _290), 5, _19104, _33072\_19110) ? creep
Call: (20) _19104 is 5+1 ? creep
Exit: (20) 6 is 5+1 ? creep
Exit: (19) tidy_and_count(instr(sub, _290), 5, 6, (instr(sub, _290);_19110)\_19110) ? creep
Exit: (18) tidy_and_count((instr(load, _318);instr(sub, _290)), 4, 6, (instr(load, _318);instr(sub, _290);_19110)\_19110) ? creep
Exit: (17) tidy_and_count((instr(store, _290);instr(load, _318);instr(sub, _290)), 3, 6, (instr(store, _290);instr(load, _318);instr(sub, _290);_19110)\_19110) ? creep
Exit: (16) tidy_and_count(((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290)), 1, 6, (instr(load, _346);instr(divc, 2);instr(store, _290);instr(load, _318);instr(sub, _290);_19110)\_19110) ? creep
Call: (16) tidy_and_count(instr(add, _260), 6, _18278, _19110\_18284) ? creep
Call: (17) _18278 is 6+1 ? creep
Exit: (17) 7 is 6+1 ? creep
Exit: (16) tidy_and_count(instr(add, _260), 6, 7, (instr(add, _260);_18284)\_18284) ? creep
Exit: (15) tidy_and_count((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260)), 1, 7, (instr(load, _346);instr(divc, 2);instr(store, _290);instr(load, _318);instr(sub, _290);instr(add, _260);_18284)\_18284) ? creep
Call: (15) tidy_and_count(instr(write, 0), 7, _17452, _18284\_17458) ? creep
Call: (16) _17452 is 7+1 ? creep
Exit: (16) 8 is 7+1 ? creep
Exit: (15) tidy_and_count(instr(write, 0), 7, 8, (instr(write, 0);_17458)\_17458) ? creep
Exit: (14) tidy_and_count(((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260));instr(write, 0)), 1, 8, (instr(load, _346);instr(divc, 2);instr(store, _290);instr(load, _318);instr(sub, _290);instr(add, _260);instr(..., ...);_17458)\_17458) ? creep
Call: (14) tidy_and_count(no_op, 8, _16610, _17458\(instr(halt, 0);block(_16632))) ? creep
Exit: (14) tidy_and_count(no_op, 8, 8, (instr(halt, 0);block(_16632))\(instr(halt, 0);block(_16632))) ? creep
Exit: (13) tidy_and_count((((((instr(load, _346);instr(divc, 2));instr(store, _290);instr(load, _318);instr(sub, _290));instr(add, _260));instr(write, 0));no_op), 1, 8, (instr(load, _346);instr(divc, 2);instr(store, _290);instr(load, _318);instr(sub, _290);instr(add, _260);instr(..., ...);...;...)\(instr(halt, 0);block(_16632))) ? creep
Call: (13) _52744 is 8+1 ? creep
Exit: (13) 9 is 8+1 ? creep
Call: (13) allocate(dict(x, _260, dict('$temp', _290, _310, _312), dict(y, _318, _326, dict(z, _346, _5218, _5220))), 9, _54366) ? creep
Call: (14) allocate(dict('$temp', _290, _310, _312), 9, _260) ? creep
Call: (15) allocate(_310, 9, _290) ? creep
Exit: (15) allocate(void, 9, 9) ? creep
Call: (15) _57630 is 9+1 ? creep
Exit: (15) 10 is 9+1 ? creep
Call: (15) allocate(_312, 10, _260) ? creep
Exit: (15) allocate(void, 10, 10) ? creep
Exit: (14) allocate(dict('$temp', 9, void, void), 9, 10) ? creep
Call: (14) _61700 is 10+1 ? creep
Exit: (14) 11 is 10+1 ? creep
Call: (14) allocate(dict(y, _318, _326, dict(z, _346, _5218, _5220)), 11, _54366) ? creep
Call: (15) allocate(_326, 11, _318) ? creep
Exit: (15) allocate(void, 11, 11) ? creep
Call: (15) _65770 is 11+1 ? creep
Exit: (15) 12 is 11+1 ? creep
Call: (15) allocate(dict(z, _346, _5218, _5220), 12, _54366) ? creep
Call: (16) allocate(_354, 12, _346) ? creep
Exit: (16) allocate(void, 12, 12) ? creep
Call: (16) _1984 is 12+1 ? creep
Exit: (16) 13 is 12+1 ? creep
Call: (16) allocate(_356, 13, _476) ? creep
Exit: (16) allocate(void, 13, 13) ? creep
Exit: (15) allocate(dict(z, 12, void, void), 12, 13) ? creep
Exit: (14) allocate(dict(y, 11, void, dict(z, 12, void, void)), 11, 13) ? creep
Exit: (13) allocate(dict(x, 10, dict('$temp', 9, void, void), dict(y, 11, void, dict(z, 12, void, void))), 9, 13) ? creep
Call: (13) _374 is 13-9 ? creep
Exit: (13) 4 is 13-9 ? creep
Exit: (12) assemble((((((instr(load, 12);instr(divc, 2));instr(store, 9);instr(load, 11);instr(sub, 9));instr(add, 10));instr(write, 0));no_op), dict(x, 10, dict('$temp', 9, void, void), dict(y, 11, void, dict(z, 12, void, void))), (instr(load, 12);instr(divc, 2);instr(store, 9);instr(load, 11);instr(sub, 9);instr(add, 10);instr(write, 0);instr(..., ...);block(...))) ? creep
Exit: (11) parse_and_assemble([program, test1, ;, begin, write, x, +, y|...], (instr(load, 12);instr(divc, 2);instr(store, 9);instr(load, 11);instr(sub, 9);instr(add, 10);instr(write, 0);instr(..., ...);block(...))) ? creep
Exit: (10) test_1((instr(load, 12);instr(divc, 2);instr(store, 9);instr(load, 11);instr(sub, 9);instr(add, 10);instr(write, 0);instr(..., ...);block(...))) ? creep
Res = (instr(load, 12);instr(divc, 2);instr(store, 9);instr(load, 11);instr(sub, 9);instr(add, 10);instr(write, 0);instr(halt, 0);block(4)) .
@hyperswine
Copy link
Author

The program was taken from Evan's aop implementation.

/*
  compile(Tokens,ObjectCode) :-
  ObjectCode is the result of compilation of a list of tokens
  representing a PL program.
*/

:- op(40,xfx,\).
:- op(800,fx,#).
:- op(780,xf,^).

program(test1,[program,test1,';',begin,write,x,'+',y,'-',z,'/',2,end]).

program(test2,[program,test2,';',
	begin,if,a,'>',b,then,max,':=',a,else,max,':=',b,end]).

parse_and_assemble(Tokens, Res) :- parse(Tokens, Structure), encode(Structure, Dictionary, Code), assemble(Code, Dictionary, Res).

test_1(Res) :- program(test1, Tokens), parse_and_assemble(Tokens, Res).

compile(String,ObjectCode) :-
  string_to_list(String, Codes),
  phrase(lexer(Tokens), Codes),
  parse(Tokens,Structure),
  encode(Structure,Dictionary,Code),
  assemble(Code,Dictionary,ObjectCode).

/*    The parser
      parse(Tokens,Structure) :-
      Structure represents the successfully parsed list of Tokens.
*/
lexer(Ts) --> whitespace, lexer(Ts).

lexer([T|Ts]) --> lexem(T), lexer(Ts).

lexer([]) --> [].

whitespace --> [W], {char_type(W,space)}. % space is whitespace

% key(K) is a lexem
% if K is a key
lexem(K) --> key(K).
% sep(S) is a lexem
% if S is a separator
lexem(S) --> sep(S).

% the middle cut finds the longest input match apparently
lexem(IA) --> lidentifier(I), !, {atom_chars(IA,I)}.
lexem(NA) --> number(A), !, {number_chars(NA,A), integer(NA)}.


% rules for your keywords here
key(program) --> "program".
key(read) --> "read".
key(write) --> "write".
key(if) --> "if".
key(then) --> "then".
key(else) --> "else".
key(begin) --> "begin".
key(while) --> "while".
key(while) --> "end".

lidentifier([C|Cs]) --> alpha(C), ident(Cs).

ident([C|Cs]) --> alpha(C), ident(Cs).
ident([]) --> [].

alpha(C) --> [C], {char_type(C,alpha)}.

number([D|Ds]) --> digit(D), digits(Ds).

digits([D|Ds]) --> digit(D), digits(Ds).
digits([]) --> [].

digit(D) --> [D], {char_type(D,digit)}.

% rules for your seperators
sep(';') --> ";".
sep(':=') --> ":=".
sep('+') --> "+".
sep('-') --> "-".
sep('*') --> "*".
sep('/') --> "/".

parse(Source,Structure) :- pl_program(Structure, Source,Z).

pl_program(S) --> [program], identifier(X), [';'], statement(S).

statement((S;Ss)) -->
        [begin], statement(S), rest_statements(Ss).
statement(assign(X,V)) -->
        identifier(X), [':='], expression(V).
statement(if(T,S1,S2)) -->
        [if], test(T), [then], statement(S1), [else], statement(S2).
statement(while(T,S)) -->
        [while], test(T), [do], statement(S).
statement(read(X)) -->
        [read], identifier(X).
statement(write(X)) -->
        [write], expression(X).

rest_statements((S;Ss)) --> [';'], statement(S), rest_statements(Ss).
rest_statements(void) --> [end].

expression(X) --> pl_constant(X).
expression(expr(Op,X,Y)) --> pl_constant(X), arithmetic_op(Op), expression(Y).

arithmetic_op('+') --> ['+'].
arithmetic_op('-') --> ['-'].
arithmetic_op('*') --> ['*'].
arithmetic_op('/') --> ['/'].

pl_constant(name(X)) --> identifier(X).
pl_constant(number(X)) --> pl_integer(X).

identifier(X) --> [X], {atom(X)}.
pl_integer(X) --> [X], {integer(X)}.

test(compare(Op,X,Y)) --> expression(X), comparison_op(Op), expression(Y).

comparison_op('=') --> ['='].
comparison_op('\\=') --> ['\\='].
comparison_op('>') --> ['>'].
comparison_op('<') --> ['<'].
comparison_op('>=') --> ['>='].
comparison_op('=<') --> ['=<'].

/*   The code generator

     encode(Structure,Dictionary,RelocatableCode) :-
     RelocatableCode is generated from the parsed Structure
     building a Dictionary associating variables with addresses.
*/
encode((X;Xs),D,(Y;Ys)) :-
        encode(X,D,Y), encode(Xs,D,Ys).
encode(void,D,no_op).
encode(assign(Name,E),D,(Code; instr(store,Address))) :-
        lookup(Name,D,Address), encode_expression(E,D,Code).
encode(if(Test,Then,Else),D,
       (TestCode; ThenCode; instr(jump,L2); label(L1); ElseCode; label(L2))) :-
        encode_test(Test,L1,D,TestCode),
        encode(Then,D,ThenCode),
        encode(Else,D,ElseCode).
encode(while(Test,Do),D,
       (label(L1); TestCode; DoCode; instr(jump,L1); label(L2))) :-
        encode_test(Test,L2,D,TestCode), encode(Do,D,DoCode).
encode(read(X),D,instr(read,Address)) :-
        lookup(X,D,Address).
encode(write(E),D,(Code; instr(write,0))) :-
        encode_expression(E,D,Code).

/*   encode_expression(Expression,Dictionary,Code) :-
     Code corresponds to an arithmetic Expression.
*/
encode_expression(number(C),D,instr(loadc,C)).
encode_expression(name(X),D,instr(load,Address)) :-
        lookup(X,D,Address).
encode_expression(expr(Op,E1,E2),D,(Load;Instruction)) :-
        single_instruction(Op,E2,D,Instruction),
        encode_expression(E1,D,Load).
encode_expression(expr(Op,E1,E2),D,Code) :-
        not(single_instruction(Op,E2,D,Instruction)),
        single_operation(Op,E1,D,E2Code,Code),
        encode_expression(E2,D,E2Code).

single_instruction(Op,number(C),D,instr(OpCode,C)) :-
        literal_operation(Op,OpCode).
single_instruction(Op,name(X),D,instr(OpCode,A)) :-
        memory_operation(Op,OpCode), lookup(X,D,A).

single_operation(Op,E,D,Code,(Code;Instruction)) :-
        commutative(Op), single_instruction(Op,E,D,Instruction).
single_operation(Op,E,D,Code,
                 (Code;instr(store,Address);Load;instr(OpCode,Address))) :-
        not(commutative(Op)),
        lookup('$temp',D,Address),
        encode_expression(E,D,Load),
        op_code(E,Op,OpCode).

op_code(number(C),Op,OpCode) :-  literal_operation(Op,OpCode).
op_code(name(X),Op,OpCode) :-  memory_operation(Op,OpCode).

literal_operation('+',addc).
literal_operation('-',subc).
literal_operation('*',mulc).
literal_operation('/',divc).

memory_operation('+',add).
memory_operation('-',sub).
memory_operation('*',mul).
memory_operation('/',div).

commutative('+').
commutative('*').

encode_test(compare(Op,E1,E2),Label,D,(Code; instr(OpCode,Label))) :-
        comparison_opcode(Op,OpCode),
        encode_expression(expr('-',E1,E2),D,Code).

comparison_opcode('=',jumpne).
comparison_opcode('\\=',jumpeq).
comparison_opcode('>',jumple).
comparison_opcode('>=',jumplt).
comparison_opcode('<',jumpge).
comparison_opcode('=<',jumpgt).

lookup(Key,dict(Key,X,Left,Right),Value) :-
        !, X = Value.
lookup(Key,dict(Key1,X,Left,Right),Value) :-
        Key @< Key1 , lookup(Key,Left,Value).
lookup(Key,dict(Key1,X,Left,Right),Value) :-
        Key @> Key1, lookup(Key,Right,Value).

/*  The assembler

    assemble(Code,Dictionary,TidyCode) :-
    TidyCode is the result of assembling Code removing
    no_ops and labels, and filling in the Dictionary.
*/

assemble(Code,Dictionary,TidyCode) :-
        tidy_and_count(Code,1,N,TidyCode\(instr(halt,0);block(L))),
        N1 is N + 1,
        allocate(Dictionary,N1,N2),
        L is N2 - N1, !.

tidy_and_count((Code1;Code2),M,N,TCode1\TCode2) :-
        tidy_and_count(Code1,M,M1,TCode1\Rest),
        tidy_and_count(Code2,M1,N,Rest\TCode2).
tidy_and_count(instr(X,Y),N,N1,(instr(X,Y);Code)\Code) :-
        N1 is N + 1.
tidy_and_count(label(N),N,N,Code\Code).
tidy_and_count(no_op,N,N,Code\Code).

allocate(void,N,N).
allocate(dict(Name,N1,Before,After),N0,N) :-
        allocate(Before,N0,N1),
        N2 is N1 + 1,
        allocate(After,N2,N).

print_asm((instr(X,Y);Rest)) :- format("~w ~w~n", [X,Y]), print_asm(Rest).
print_asm(block(X)).

%  Program 24.1:  A compiler from PL to machine language

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment