I am trying to implement an automated checking procedure for programming assignments. For example, I may ask a user to write function my_sum() for computing the sum of elements of a vector, then verify that he did not use the sum() function. Then I ask to write function to compute the mean of a vector’s elements, and would like to automatically verify that he used my_sum(), rather than copy-pasting its internal implementation.
All that is implemented in a Pluto notebook, so I can’t analyze the Expr tree. So, as suggested in this discussion, I look at the IR:
A sneaky student who’s aware of your testing methodology might write something like
julia> function totally_not_base_sum(x)
return sum(x)
end;
julia> function my_sum(x)
return totally_not_base_sum(x)
end;
which the code_... approach would fail to detect:
julia> Base.code_lowered(my_sum, (AbstractVector,)) # no sum here
1-element Vector{Core.CodeInfo}:
CodeInfo(
1 ─ %1 = Main.totally_not_base_sum(x)
└── return %1
)
There’s probably a lot of downsides, but you could override sum to make sure it does not work:
julia> Base.sum(x::AbstractVector) = error("I KNOW WHAT YOU DID")
julia> my_sum(rand(3))
ERROR: I KNOW WHAT YOU DID
Stacktrace:
[1] error(s::String)
@ Base .\error.jl:35
[2] sum(x::Vector{Float64})
@ Main .\REPL[4]:1
[3] totally_not_base_sum(x::Vector{Float64})
@ Main .\REPL[1]:2
[4] my_sum(x::Vector{Float64})
@ Main .\REPL[2]:2
[5] top-level scope
@ REPL[5]:1
Maybe you could use TraceFuns.jl to check if a particular function got used:
julia> using TraceFuns
julia> function totally_not_base_sum(x)
return sum(x)
end;
julia> function my_sum(x)
return totally_not_base_sum(x)
end;
julia> @trace my_sum(1:10) Base.sum
2: sum(1:10) -- Method sum(r::AbstractRange{<:Real}) @ Base range.jl:1405 of sum
2: sum(1:10) -> 55
55
julia> function my_real_sum(x)
reduce(+, x)
end
my_real_sum (generic function with 1 method)
julia> @trace my_real_sum(1:10) Base.sum
55
# Success: No printout, i.e., sum was not called!
That’s what I am looking for.
It relies on fairly advanced infrastructure of Cassete.jl. I wonder if MWE may be created using only build-in Julia introspection tools?
How far does this sum(input) check go though? Would mapreduce(identity, +, input) also be an unacceptable cop-out?
Base names are only implicitly imported, so why not shadow it in the first place with sum = nothing if we want sum to not be usable yet Base.sum’s implementation to exist? Could tell the students to paste lines at the start, and that’s easy to check.
code_info(ex::Symbol)=Base.code_lowered(eval(ex))
code_info(exs::AbstractVector{Symbol})=reduce(vcat, code_info.(exs))
global_references(ci::Core.CodeInfo) = Symbol[c.name for c in ci.code if isa(c, GlobalRef)]
global_references(ci::AbstractVector{Core.CodeInfo})=unique(reduce(vcat,global_references.(ci)))
followed by the loop
for k in 1:recursion_depth_limit
ci=code_info(s)
s=global_references(ci)
if any(x->x===bad_symbol, s)
return :bad
end
end
return :good
and quickly found out that methods of / call sum. If there’s a way to exclude calls to functions imported into the module, that would fix this problem.
So far as I understood it, Cassette.jl uses generated functions to alter the function calls, so it will only see the methods that are actually called.
After some trial and error, the solution so far looks like this:
code_info(x, tp=Tuple) = Base.CodeInfo[]
code_info(fun::Function, t=Tuple) = Base.code_lowered(fun, t)
function code_info(s::Symbol, tp=Tuple)
local fun
try
fun = eval(s)
catch
return Base.CodeInfo[]
else
code_info(fun, tp)
end
end
function code_info(v::AbstractVector, t=Tuple)
unique(mapreduce(x->code_info(x, t), vcat, v,init=Base.CodeInfo[]))
end
global_refs(x) = Core.GlobalRef[]
global_refs(r::GlobalRef) = [r]
global_refs(ex::Expr) = global_refs(ex.args)
global_refs(ci::Base.CodeInfo) = global_refs(ci.code)
function global_refs(cis::AbstractVector)::Vector{GlobalRef}
refs = mapreduce(global_refs, vcat, cis, init=Core.GlobalRef[])
unique(refs)
end
Using these functions, I can check for the “bad” (or “good”) calls:
function search_main_calls(fun::Symbol, sym::Symbol, types=Tuple; recursion_limit=5)
for k in 1:recursion_limit
ci = code_info(fun, types)
refs = global_refs(ci)
if any(r.name===sym for r in refs if r.mod===Main)
return :found
end
fun = [r.name for r in refs if r.mod===Main]
end
return :not_found
end
This does not try to recurse into standard library and detects your attempt to cheat:
julia> search_main_calls(:my_sum, :sum)
:found
If there’re any counterexamples to that solution, I’d appreciate hearing about them.
