Module:Sandbox/AbstractWikipedia/UnifiableFeatures

Module documentation

This module is part of user:AGutman-WMF's work to create a prototype implementation of Abstract Wikipedia's template language in Scribunto. The main module is Module:Sandbox/AbstractWikipedia.

This module specifically implements the data-structure needed to support unifiable features, which is similar to a disjoint-set data structure. These unifiable features are then used by the Module:Sandbox/AbstractWikipedia/Lexemes module.

local p = {}

-- All features are stored in an array of features, similar to a
-- disjoint-set data structure (union-find data structure)
-- The features themselves are strings, but to support unification features
-- can point to other features using numeric indexes to other array cells.
local features = {}

-- Add a new feature to the array, and return its index
function p.createNewFeature ( feature )
	if type(feature) ~= 'string' then
		error("Features must be strings. Got: "..tostring(feature))
	end
	table.insert(features, feature)
	return #features
end

-- Helper function to find the index that actually points to a feature
-- As a side effect, updates all indexes on the path to point to the 
-- representative index (containing the actual feature)
local function findRepresentative ( index )
	if type(features[index]) == 'number' then
		features[index] = findRepresentative(features[index])
		return features[index]
	else
		return index
	end
end

-- retrieves the feature at a given index
function p.getFeature ( index )
	return features[findRepresentative(index)]
end		

-- Returns true if feature1 subsumes (is more general than) feature2.
-- Ideally there should be a type hierarchy of features, but for the prototype
-- only empty features are considered more general than any other feature
-- For more information about subsumption and unification, see
-- http://www.ale.cs.toronto.edu/docs/man/ale_trale_man/ale_trale_man-node21.html

local function subsumes ( feature1, feature2 )
	if (feature1 == '') or (feature1 == feature2) then
		return true
	else
		return false
	end
end

-- same as above, but operates on indexes
function p.subsumes (index1, index2)
	index1 = findRepresentative(index1)
	index2 = findRepresentative(index2)
	return subsumes(features[index1], features[index2])
end

-- Returns whether two features are unifiable
-- In this prototype unification is only possible through subsumption
function p.unifiable (index1, index2)
	return (p.subsumes(index1, index2) or p.subsumes(index2, index1))
end

-- Unifies two features, returning nil if they are incompatible
-- Ideally there should be a type hierarchy of features, but for the prototype
-- we allow only unification of identical features or unification with an empty
-- feature
local function unifyFeatures ( feature1, feature2 )
	mw.log("Unify '"..tostring(feature1).."' with '"..tostring(feature2).."'")
	if subsumes(feature2, feature1) then
		return feature1
	elseif subsumes(feature1, feature2) then
		return feature2
	else
		-- In theory, unification could result in a third type, but this is not
		-- possible in this prototype.
		return nil
	end
end

-- Unify the features in index1 and index2 and return result
-- This is achieved by pointing one index to the other and possibly updating
-- the value
function p.unify( index1, index2 )
	index1 = findRepresentative(index1)
	index2 = findRepresentative(index2)
	if (index1 == index2) then
		return features[index1]
	end
	local feature1 = features[index1]
	local feature2 = features[index2]
	local result = unifyFeatures(feature1, feature2)
	if result == nil then
		return nil
	end
	if result == feature1 then
		features[index2] = index1
	elseif result == feature2 then
		features[index1] = index2
	else -- result is different than both: update one cell
		features[index2] = result
		features[index1] = index2
	end
	return result
end

-- Unify the feature at index with a new feature, updating its value
function p.unifyWithFeature ( index, feature )
	index = findRepresentative(index)
	feature_i = features[index]
	local result = unifyFeatures(feature, feature_i)
	if result ~= nil then
		features[index] = result
	end
	return result
end

-- For debugging purposes
function p.listFeatures ()
	mw.log("Size: "..#features)
	for index, feature in ipairs(features) do
		if type(feature) == 'string' then
			mw.log(index.." == '"..feature.."'")
		else
			mw.log(index.." -> "..feature)
		end
	end
end

return p