summaryrefslogtreecommitdiff
path: root/prolog/problems/algol
diff options
context:
space:
mode:
authorTimotej Lazar <timotej.lazar@fri.uni-lj.si>2016-05-22 17:48:30 +0200
committerTimotej Lazar <timotej.lazar@fri.uni-lj.si>2016-05-22 17:48:30 +0200
commitbbcb29a202436fc0e222e187f1fadf0b1f305465 (patch)
treefed504361df37c4ce01b5b13c1082d5f3234de79 /prolog/problems/algol
parent4973979e40dfdc26dafe1cdeddf8e0bce859ba5d (diff)
Prolog: update denotational_semantics problems
Diffstat (limited to 'prolog/problems/algol')
-rw-r--r--prolog/problems/algol/algol_3/common.py78
-rw-r--r--prolog/problems/algol/algol_3/en.py32
-rw-r--r--prolog/problems/algol/algol_for_3/common.py92
-rw-r--r--prolog/problems/algol/algol_for_3/en.py18
-rw-r--r--prolog/problems/algol/algol_if_3/common.py85
-rw-r--r--prolog/problems/algol/algol_if_3/en.py19
-rw-r--r--prolog/problems/algol/common.py2
-rw-r--r--prolog/problems/algol/en.py2
8 files changed, 328 insertions, 0 deletions
diff --git a/prolog/problems/algol/algol_3/common.py b/prolog/problems/algol/algol_3/common.py
new file mode 100644
index 0000000..415e1e5
--- /dev/null
+++ b/prolog/problems/algol/algol_3/common.py
@@ -0,0 +1,78 @@
+id = 176
+number = 10
+visible = False
+facts = None
+
+solution = '''\
+algol(fun(S0,S,apply176([printout=[]|S0],S,Minstructs))) -->
+ [begin], instructs176(Minstructs), [end].
+
+instructs176(Minstr) --> instr176(Minstr).
+instructs176(fun(S0,S,
+ (apply176(S0,S1,Minstr),
+ apply176(S1,S,Minstructs))))
+ -->
+ instr176(Minstr), instructs176(Minstructs).
+
+instr176(Massign) --> assign176(Massign).
+instr176(fun(S0,[printout = L1|S1],
+ (memb(X = V,S0),
+ del(printout = L0,S0,S1),
+ conc(L0,[V],L1))))
+ -->
+ [print(X)].
+instr176(fun(S0,S,
+ loop176(S0,Mcond,Minstructs,S)))
+ -->
+ [while], cond176(Mcond), [do,begin], instructs176(Minstructs), [end].
+
+assign176(fun(S0,[X = Value|S1],
+ (apply176(S0,Value,Mexpr),
+ del(X = _,S0,S1))))
+ -->
+ var176(X), [:=], expr176(Mexpr).
+
+cond176( fun( S, TruthVal,
+ (apply176(S,Val1,ME1),
+ apply176(S,Val2,ME2),
+ (Val1 < Val2,!,TruthVal = true ; TruthVal = false))))
+ -->
+ expr176(ME1), [<], expr176(ME2).
+
+var176(X) --> [X], {atom(X)}.
+
+expr176(fun(S,Value,eval(Expr,S,Value))) -->
+ [Expr].
+
+apply176(In, Out, fun(In, Out, Goals)) :-
+ call(Goals).
+
+loop176(State0, Mcond, _, State0) :-
+ apply176( State0, false, Mcond), !.
+loop176(S0, Mcond, MBody, S) :-
+ copy_term( MBody, MBodyCopy),
+ apply176( S0, S1, MBody),
+ loop176( S1, Mcond, MBodyCopy, S).
+
+eval176(N, _, N) :-
+ number176( N), !.
+eval176(X, State, Val) :- % A program variable
+ atom(X), !,
+ memb(X = Val, State).
+eval176(E1 + E2, State, Val) :- !,
+ eval176(E1, State, V1),
+ eval176(E2, State, V2),
+ Val is V1 + V2.
+eval176(E1 - E2, State, Val) :- !,
+ eval176(E1, State, V1),
+ eval176(E2, State, V2),
+ Val is V1 - V2.
+eval176(E1 * E2, State, Val) :- !,
+ eval176(E1, State, V1),
+ eval176(E2, State, V2),
+ Val is V1 * V2.
+eval176(E1 / E2, State, Val) :- !,
+ eval176(E1, State, V1),
+ eval176(E2, State, V2),
+ Val is V1 / V2.
+'''
diff --git a/prolog/problems/algol/algol_3/en.py b/prolog/problems/algol/algol_3/en.py
new file mode 100644
index 0000000..3b91a47
--- /dev/null
+++ b/prolog/problems/algol/algol_3/en.py
@@ -0,0 +1,32 @@
+name = 'algol/3'
+slug = 'interpreter for mini-algol'
+
+description = '''\
+<p>A DCG for mini-algol.</p>
+<pre>
+% apply a function to a starting state
+?- apply([a=2], Out, fun(_In, Out, eval(a+3, _In, Out))).
+ Out = 5.
+
+% a := a+b
+% b := a-b
+% a := a-b
+?- _Program = [begin,a,:=,a+b,b,:=,a-b,a,:=,a-b,end],
+ algol(_F, _Program, []),
+ apply([a=3,b=5], Output, _F).
+ Output = [a=5,b=3,printout=[]].
+
+% a := 0
+% while a < 10 do
+% begin
+% print(a)
+% a := a+1
+% end
+?- _Program = [begin,a,:=,0,while,a,<,10,do,begin,print(a),a,:=,a+1,end,end],
+ algol(_F, _Program, []),
+ apply([a=3], Output, _F).
+ Output = [a=10,printout=[0,1,2,3,4,5,6,7,8,9]].
+</pre>
+'''
+
+hint = {}
diff --git a/prolog/problems/algol/algol_for_3/common.py b/prolog/problems/algol/algol_for_3/common.py
new file mode 100644
index 0000000..654d478
--- /dev/null
+++ b/prolog/problems/algol/algol_for_3/common.py
@@ -0,0 +1,92 @@
+id = 178
+number = 30
+visible = False
+facts = None
+
+solution = '''\
+algol_for(fun(S0,S,apply178([printout=[]|S0],S,Minstructs))) -->
+ [begin], instructs178(Minstructs), [end].
+
+instructs178(Minstr) --> instr178(Minstr).
+instructs178(fun(S0,S,
+ (apply178(S0,S1,Minstr),
+ apply178(S1,S,Minstructs))))
+ -->
+ instr178(Minstr), instructs178(Minstructs).
+
+instr178(Massign) --> assign178(Massign).
+instr178(fun(S0,[printout = L1|S1],
+ (memb(X = V,S0),
+ del(printout = L0,S0,S1),
+ conc(L0,[V],L1))))
+ -->
+ [print(X)].
+instr178(fun(S0,S,
+ loop178(S0,Mcond,Minstructs,S)))
+ -->
+ [while], cond178(Mcond), [do,begin], instructs178(Minstructs), [end].
+instr178(fun(S0, S,
+ (apply178(S0, S1, Minit),
+ for178(S1, Mcond, Mstep, Mbody, S))))
+ -->
+ [for], assign178(Minit), [&], cond178(Mcond), [&], assign178(Mstep), [do, begin], instructs178(Mbody), [end].
+
+assign178(fun(S0,[X = Value|S1],
+ (apply178(S0,Value,Mexpr),
+ del(X = _,S0,S1))))
+ -->
+ var178(X), [:=], expr178(Mexpr).
+
+cond178( fun( S, TruthVal,
+ (apply178(S,Val1,ME1),
+ apply178(S,Val2,ME2),
+ (Val1 < Val2,!,TruthVal = true ; TruthVal = false))))
+ -->
+ expr178(ME1), [<], expr178(ME2).
+
+var178(X) --> [X], {atom(X)}.
+
+expr178(fun(S,Value,eval(Expr,S,Value))) -->
+ [Expr].
+
+apply178(In, Out, fun(In, Out, Goals)) :-
+ call(Goals).
+
+loop178( State0, Mcond, _, State0) :-
+ apply178( State0, false, Mcond), !.
+loop178( S0, Mcond, MBody, S) :-
+ copy_term( MBody, MBodyCopy),
+ apply178( S0, S1, MBody),
+ loop178( S1, Mcond, MBodyCopy, S).
+
+for178(S0, Mcond, _, _, S0) :-
+ apply178(S0, false, Mcond), !.
+for178(S0, Mcond, Mstep, Mbody, S) :-
+ copy_term(Mbody, Mbody2),
+ copy_term(Mstep, Mstep2),
+ apply178(S0, S1, Mbody),
+ apply178(S1, S2, Mstep),
+ for178(S2, Mcond, Mstep2, Mbody2, S).
+
+eval178( N, _, N) :-
+ number178( N), !.
+eval178( X, State, Val) :- % A program variable
+ atom( X), !,
+ memb( X = Val, State).
+eval178( E1 + E2, State, Val) :- !,
+ eval178( E1, State, V1),
+ eval178( E2, State, V2),
+ Val is V1 + V2.
+eval178( E1 - E2, State, Val) :- !,
+ eval178( E1, State, V1),
+ eval178( E2, State, V2),
+ Val is V1 - V2.
+eval178( E1 * E2, State, Val) :- !,
+ eval178( E1, State, V1),
+ eval178( E2, State, V2),
+ Val is V1 * V2.
+eval178( E1 / E2, State, Val) :- !,
+ eval178( E1, State, V1),
+ eval178( E2, State, V2),
+ Val is V1 / V2.
+'''
diff --git a/prolog/problems/algol/algol_for_3/en.py b/prolog/problems/algol/algol_for_3/en.py
new file mode 100644
index 0000000..2f46d36
--- /dev/null
+++ b/prolog/problems/algol/algol_for_3/en.py
@@ -0,0 +1,18 @@
+name = 'algol_for/3'
+slug = 'interpreter for mini-algol with for-statement'
+
+description = '''\
+<p>Extend the given DCG for mini-algol to support the for-statement. Example:</p>
+<pre>
+% for a := 0 & a < 5 & a := a + 1 do
+% begin
+% print(a)
+% end
+?- _Program = [begin,for,a,:=,0,&,a,<,5,&,a,:=,a+1,do,begin,print(a),end,end],
+ algol_for(_F, _Program, []),
+ apply([a=2], Output, _F).
+ Output = [a=5,printout=[0,1,2,3,4]].
+</pre>
+'''
+
+hint = {}
diff --git a/prolog/problems/algol/algol_if_3/common.py b/prolog/problems/algol/algol_if_3/common.py
new file mode 100644
index 0000000..6678743
--- /dev/null
+++ b/prolog/problems/algol/algol_if_3/common.py
@@ -0,0 +1,85 @@
+id = 177
+number = 20
+visible = False
+facts = None
+
+solution = '''\
+algol_if(fun(S0,S,apply177([printout=[]|S0],S,Minstructs))) -->
+ [begin], instructs177(Minstructs), [end].
+
+instructs177(Minstr) --> instr177(Minstr).
+instructs177(fun(S0,S,
+ (apply177(S0,S1,Minstr),
+ apply177(S1,S,Minstructs))))
+ -->
+ instr177(Minstr), instructs177(Minstructs).
+
+instr177(Massign) --> assign177(Massign).
+instr177(fun(S0,[printout = L1|S1],
+ (memb(X = V,S0),
+ del(printout = L0,S0,S1),
+ conc(L0,[V],L1))))
+ -->
+ [print(X)].
+instr177(fun(S0,S,
+ loop177(S0,Mcond,Minstructs,S)))
+ -->
+ [while], cond177(Mcond), [do,begin], instructs177(Minstructs), [end].
+instr177(fun(S0, S,
+ (apply177(S0, true, Mcond), !,
+ apply177(S0, S, MinstructsA)
+ ;
+ apply177(S0, S, MinstructsB))))
+ -->
+ [if], cond177(Mcond), [then], instructs177(MinstructsA), [else], instructs177(MinstructsB), [end].
+
+assign177(fun(S0,[X = Value|S1],
+ (apply177(S0,Value,Mexpr),
+ del(X = _,S0,S1))))
+ -->
+ var177(X), [:=], expr177(Mexpr).
+
+cond177( fun( S, TruthVal,
+ (apply177(S,Val1,ME1),
+ apply177(S,Val2,ME2),
+ (Val1 < Val2,!,TruthVal = true ; TruthVal = false))))
+ -->
+ expr177(ME1), [<], expr177(ME2).
+
+var177(X) --> [X], {atom(X)}.
+
+expr177(fun(S,Value,eval(Expr,S,Value))) -->
+ [Expr].
+
+apply177(In, Out, fun(In, Out, Goals)) :-
+ call(Goals).
+
+loop177( State0, Mcond, _, State0) :-
+ apply177( State0, false, Mcond), !.
+loop177( S0, Mcond, MBody, S) :-
+ copy_term( MBody, MBodyCopy),
+ apply177( S0, S1, MBody),
+ loop177( S1, Mcond, MBodyCopy, S).
+
+eval177( N, _, N) :-
+ number177( N), !.
+eval177( X, State, Val) :- % A program variable
+ atom( X), !,
+ memb( X = Val, State).
+eval177( E1 + E2, State, Val) :- !,
+ eval177( E1, State, V1),
+ eval177( E2, State, V2),
+ Val is V1 + V2.
+eval177( E1 - E2, State, Val) :- !,
+ eval177( E1, State, V1),
+ eval177( E2, State, V2),
+ Val is V1 - V2.
+eval177( E1 * E2, State, Val) :- !,
+ eval177( E1, State, V1),
+ eval177( E2, State, V2),
+ Val is V1 * V2.
+eval177( E1 / E2, State, Val) :- !,
+ eval177( E1, State, V1),
+ eval177( E2, State, V2),
+ Val is V1 / V2.
+'''
diff --git a/prolog/problems/algol/algol_if_3/en.py b/prolog/problems/algol/algol_if_3/en.py
new file mode 100644
index 0000000..bd5b732
--- /dev/null
+++ b/prolog/problems/algol/algol_if_3/en.py
@@ -0,0 +1,19 @@
+name = 'algol_if/3'
+slug = 'interpreter for mini-algol with if-statement'
+
+description = '''\
+<p>Extend the given DCG for mini-algol to support the if-statement. You can assume that both branches are present in every if-statement. Example:</p>
+<pre>
+% if a < b then
+% print(a)
+% else
+% print(b)
+% end
+?- _Program = [begin,if,a,<,b,then,print(a),else,print(b),end,end],
+ algol_if(_F, _Program, []),
+ apply([a=3,b=5], Output, _F).
+ Output = [a=3,b=5,printout=[3]].
+</pre>
+'''
+
+hint = {}
diff --git a/prolog/problems/algol/common.py b/prolog/problems/algol/common.py
new file mode 100644
index 0000000..2885432
--- /dev/null
+++ b/prolog/problems/algol/common.py
@@ -0,0 +1,2 @@
+id = 1001
+number = 12
diff --git a/prolog/problems/algol/en.py b/prolog/problems/algol/en.py
new file mode 100644
index 0000000..340eb4a
--- /dev/null
+++ b/prolog/problems/algol/en.py
@@ -0,0 +1,2 @@
+name = 'Mini-ALGOL'
+description = 'Syntax and semantics for a simple imperative programming language.'