Introspection for checking an implementation

General Usage
1

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:

ci=Base.code_typed(my_mean,(AbstractVector,))[1][1]

Is it enough to verify that one of Expr elements of ci.code

a=[c.args[1] for c in ci.code if isa(c,Expr) && c.head===:call]

matches my_sum?

any(x->x.name===:my_sum, a)
1 Like
2

Small note: I suggest using code_lowered instead of code_typed. That way you avoid some transformations of the source, inlining in particular.

3

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
3 Likes
4

Yeah, well, if a student is that good, he’ll ace the assignment without sneaky tricks. It’s really a preliminary check before I grade the assignment.

But since you’ve mentioned it, can this test be applied recursively to all calls?

There’s probably a lot of downsides, but you could use override sum to make sure it does not work:

I’ve considered this approach. Can this override be limited in scope within the checking block?

5

Fair point! :slight_smile:

Presumably, but I don’t know if there’s a relatively easy way.

I’m not fully sure this is what you mean, but you could restore Base.sum by invoking from a previous world:

julia> world_age = Base.get_world_counter()
0x0000000000006882

julia> x = rand(3);

julia> sum(x)
0.8830781962330426

julia> Base.sum(x::AbstractVector) = error()

julia> sum(x)
ERROR:
Stacktrace:
 [1] error()
   @ Base .\error.jl:44
 [2] sum(x::Vector{Float64})
   @ Main .\REPL[4]:1
 [3] top-level scope
   @ REPL[5]:1

julia> Base.sum(x::AbstractVector) = Base.invoke_in_world(world_age, sum, x)

julia> sum(x)
0.8830781962330426
1 Like
6

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!
4 Likes
7

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?

8

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.

1 Like
9

I tried to do it in the following way:


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.

1 Like
10

Why would that be undesirable?

11

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.

1 Like