Although InCoder performs comparatively better on Python, it still struggles
greatly to understand the objective of the prompt and actually generate the
function. Instead, for Python code, the InCoder models seem to simply
regurgitate the summary of the Python function that can be found in the
prompt. For instance, here is a sample InCoder output for the function
absolute_clonal:

⬇

1 # summary: Returns the number of copies of a chromosome in reference and in
sample.

2# param: chrom (string) - the chromosome to be evaluated

3# param: ploidy (int) - the ploidy of the chromosome

4# param: is_reference_male (bool) - indicates if the reference is male or not

5# return: tuple - a pair of integers indicating the number of copies in the
reference and in the sample.

6#def _log2_ratio_to_absolute(cnarr, ref_copies, expect_copies, purity):

7# summary: Converts log2 ratio values into absolute copy number values.

8# param: cnarr (array-like) - Copy number segments or bins

9# param: ref_copies (array-like) - An array of integers indicating the number
of copies in the reference for each segment or bin.

10# param: expect_copies (array-like) - An array of integers indicating the
number of copies in the expected for each segment or bin.

11# param: purity (float) - estimated tumor pur

Overall, it seems that InCoder struggles to understand longer and more complex
prompts, and t struggles to understand the objective of the prompts. Often it
simply defaults to regurgitating parts of the prompt that it has encountered,
without generating the desired function.

  2. 2.

SantaCoder:

Similar to many other models, SantaCoder also has poor Java performance, due
to the fact that it was trained and fine-tuned on a Python corpus. Therefore,
SantaCoder achieves 0% Pass@K for the Java prompts. The main issue that
SantaCoder runs into is that Java seems to struggle to understand the
objective in the prompt and fails to generate the full function, only
generating parts of the function. This may also be due to the smaller context
limit of SantaCoder, resulting in it being unable to fully generate the
functions. For instance, here is a sample SantaCoder output for the function
getReverseComplementSequence:

⬇

1 # double x = perc;

2# int a = (int) x;

3# int b = (int) (x - a);

4# int c = (int) (b - a);

5# if(c==0){

6# return 0;

7# }else if(c==1){

8# return 1;

9# }else{

10# return 2;

11# }

12# //return getColor(value, perc);

13

14# int c1 = (int) ((perc - a)/b);

15# int c2 = (int) ((perc - a - b)/a);

16# return 1 + c1 * 3 + c2 * 5;

17

18# int a1 = (int) (c1 / 2);

19# int a2 = (int) ((c1 - a1) / 2);

20# int a3 = (int) (c2 / 2);

21# int a4 = (int) ((c2 - a3) / 2);

22# int a5 = (int) (c1 +

Although SantaCoder performs comparatively better on Python, especially
considering its small model size, it still struggles greatly to generate many
of the functions. Often due to the small context size of the SantaCoder model,
thus for more complicated functions, SantaCoder is unable to generate the
model. Overall, it seems that SantaCoder struggles to understand the longer
and more complex prompts, and it often struggles to understand the objective
of the prompts. Furthermore, the small context limit of SantaCoder limits its
ability to generate more complex and more context-rich code.

  3. 3.

StarCoder:

Similar to many of the other models, StarCoder has very poor Java performance,
due to the fact that it was trained and finetuned on a Python corpus.
Therefore, StarCoder achieves 0% Pass@K for the Java prompts. However, unlike
some of the other models, it seems to understand the objective of the prompt
and uses the context appropriately. For instance, using the reverseComplement
helper function correctly when generating the getReverseComplementedSequence
function, as can be seen below:

⬇

1 def getReverseComplementedSequence(samRecord, startIndex, length):

2 if startIndex < 0:

3 startIndex = samRecord.getReadLength() + startIndex

4 rangeBytes = samRecord.getReadBases().getBytes()[startIndex : startIndex +
length]

5 reverseComplemented = SequenceUtil.reverseComplement(rangeBytes)

6 return reverseComplemented.toString()

However, StarCoder, being finetuned on Python, seems to have a hard time
generating proper Java syntax, and instead generates a Python function.
Although StarCoder performs comparatively better on Python, it still struggles
greatly to generate many of the functions. Python seems to understand the
objective in the prompt and generates proper syntax, however, some of its
logic is incorrect, resulting in some failed tests. For instance, here is a
sample StarCoder output for the function absolute_clonal:

⬇

1 #Write your function here!

2def absolute_clonal(cnarr, ploidy, purity, is_reference_male,
is_sample_female):

3 absolutes = np.zeros(len(cnarr), dtype=np.float_)

4 for i, row in enumerate(cnarr):

5 chromosome, log2_value = row

6 ref_copies, expect_copies = _reference_expect_copies(chromosome, ploidy,
is_sample_female, is_reference_male)

7 absolute_value = _log2_ratio_to_absolute(log2_value, ref_copies,
expect_copies, purity)

8 absolutes[i] = absolute_value

9 return absolutes

  4. 4.

StarCoder+: Unlike many of the other models, StarCoder+ has nonzero Pass@K
performance on Java. This is likely because StarCoder+ is trained and
finetuned on a larger corpus that consists of more languages than just Python.
It seems to understand the objective of the prompt and uses the context
appropriately, for instance using the reverseComplement helper function
correctly when generating the getReverseComplementedSequence function, as can
be seen below:

⬇

1 import htsjdk.samtools.util.SequenceUtil;

2public class getReverseComplementedSequence

3{

4public static String getReverseComplementedSequence(SAMRecord samRecord, int
startIndex, int length)

5{

6if(startIndex < 0)

7{

8startIndex = samRecord.getReadLength() + startIndex;

9}

10byte[] rangeBytes = new byte[length];

11samRecord.getReadBases(rangeBytes, startIndex, length);

12byte[] rcBytes = SequenceUtil.reverseComplement(rangeBytes);

13return new String(rcBytes);

14}

15}

Unlike StarCoder, it seems to understand and be able to generate Java syntax.

  5. 5.

CodeGen: The performance of CodeGen1 was not great. This could be due to a
variety of factors, including the fact that CodeGen models are not intended
for full multi-line function generation, or the fact that the dataset used to
train CodeGen models does not contain much Java code. This is demonstrated in
some of the generations, as CodeGen ended up generating Python code, despite
us mentioning that this prompt is in Java, and using Java code in the context.
Sometimes, it also generates the comment again, such as below:

⬇

1#Note: This is not a string method.

  6. 6.

CodeGen2: CodeGen2 outperformed CodeGen as expected in our normal test cases;
however, it was unexpectedly slightly outperformed in the Rosalind benchmark.

  7. 7.

GPT-3.5: GPT clearly performs the best out of all models tested, on both Java
and Python and across all prompt types. The version we used on Azure had an 8k
context size, so it had an advantage over some of the models due to being able
to understand more of the context. Furthermore, the fact that some of the
function descriptions were generated by GPT might mean that it had an easier
time generating code from its own description. Furthermore, given the size of
the model, it is possible that some of the functions were memorized, although
we tried to combat this by changing the function signature slightly in some
cases. Here is an example of the GPT output

⬇

1def FindLocalPeaks(signal):

2 peakLoc = []

3 maxSuspect = None

4 minSuspect = None

5 for i in range(1, len(signal)-1):

6 if signal[i] > 0:

7 if signal[i] > signal[i-1] and signal[i] == signal[i+1]:

8 maxSuspect = i

9 elif signal[i] == signal[i-1] and signal[i] > signal[i+1]:

10 if maxSuspect is not None:

11 peakLoc.append(maxSuspect)

12 maxSuspect = None

13 elif signal[i] > signal[i-1] and signal[i] > signal[i+1]:

14 peakLoc.append(i)

15 elif signal[i] < 0:

16 if signal[i] < signal[i-1] and signal[i] == signal[i+1]:

17 minSuspect = i

18 elif signal[i] == signal[i-1] and signal[i] < signal[i+1]:

19 if minSuspect is not None:

20 peakLoc.append(minSuspect)

21 minSuspect = None

22 elif signal[i] < signal[i-1] and signal[i] < signal[i+1]:

23 peakLoc.append(i)

24 return np.array(peakLoc, dtype=int)

It is also important to note that in every prompt, GPT-3.5 generated usable,
cleaner code without comments as directed. Therefore, most test cases were run
without syntax errors, but mostly logic errors.

Next, we performed a horizontal analysis on a single prompt to compare the
outputs of each of the models with each other in order to understand the
differences between the models and gain insight into what parts of the prompts
the various models seem to understand. We applied the following problem for
the horizontal analysis:

⬇

1@property

2def outlines(self):

3 """Get a mask of all the points on the border of objects"""

4 if self._outlines is None:

5 for i, labels in enumerate(self.labels):

6 if i == 0:

7 self._outlines = centrosome.outline.outline(labels) != 0

8 else:

9 self._outlines |= centrosome.outline.outline(labels) != 0

10 if self.line_width is not None and self.line_width > 1:

11 hw = float(self.line_width) / 2

12 d = scipy.ndimage.distance_transform_edt(~self._outlines)

13 dti, dtj = numpy.where((d < hw + 0.5) & ~self._outlines)

14 self._outlines = self._outlines.astype(numpy.float32)

15 self._outlines[dti, dtj] = numpy.minimum(1, hw + 0.5 - d[dti, dtj])

16 return self._outlines.astype(numpy.float32)

The reasons we chose this function for the horizontal analysis are the
following:

  1. 1.

It is a Python function, and all of the model’s generally seem to be fine-
tuned on Python code and thus will perform better on Python code; therefore,
it would be a more fair comparison to use a Python function for this analysis.

  2. 2.

Furthermore, this is also a relatively tricky function to generate as it has
many moving parts and relies on many different levels of understanding of the
context. First, it is important to note that this has a @property decorator
and is a function that is part of a class; thus, the models must understand
this and generate the @property decorator accordingly. Furthermore, the model
must understand and correctly use the self._outlines, self._line_width, and
self.labels instance variables. Finally, the model must understand and use
correctly the highly bioinformatics-specific external library that is
centrosome.

The prompt that we used for the horizontal analysis is the following "Summary
Only" prompt:

⬇

1#This is in python

2#Write a function called "get_border_mask" that takes in a class object as an
argument and returns a binary mask of all the points on the border of objects.
The function should check if the instance variable "_outlines" is None and if
it is, then use the labels attribute of the class object to generate the
outlines mask using "centrosome.outline.outline(labels)" method. If the
"_outlines" variable is not None, then it should iterate over
"centrosome.outline.outline(labels)" for each i, and update the "_outlines"
variable using the bitwise OR operator with the new mask. If the line_width
attribute of the class object is not None and greater than 1, the function
should calculate the distance transform using the "~self._outlines" mask and
compute the binary mask for borders with the given line width (hw) using
numpy.where(). Finally, the function should return the mask as a float32 numpy
array. Make sure to import the necessary dependencies including
"centrosome.outline" and "numpy" and also initialize the "_outlines" variable
in the class.

3#

4#The function is located in the class OutlinesMixin

5#

6#@property

7#def get_border_mask(self):

We chose the "Summary Only" format of the prompt because generally, the models
performed best when the prompt was written in the "Summary Only" format. The
outputs of the various models for this prompt are as follows:

  1. 1.

InCoder:

⬇

1def get_border_mask(self):

2 #If outlines is none, generate outlines using
centrosome.outline.outline(labels) method and set outlines to the generated
mask.

3 if self.outlines is None:

4 self.outlines = self.outline.outline(labels=self.labels)

5

6 # Get the mask using numpy

7 border_mask = np.where(self.outlines > 0, 1, 0 )

8

9 # Check if line width is greater than 1

10 if self.line_width > 1:

11 # Get distance transform

12 dt = np.abs(self.outlines - border_mask) * 255

13 dt[dt==0] = 255

14

15 # Use np.where to create border mask

16 border_mask = np.where(

17 dt > 0,

18 1,

19 0

20 )

21

22 # Return border mask as float32 numpy array

23 return border_mask.astype(np.float32)

  2. 2.

SantaCoder:

⬇

1def get_border_mask(self):

2 if self._outlines is None:

3 self._outlines = centrosome.outline.outline(self.labels)

4 outlines_mask = np.where(self._outlines, self._outlines, self.labels)

5 #outlines_mask = np.where(self._outlines, self._outlines, self._outlines)

6 #outlines_mask = np.where(outlines_mask > 0, outlines_mask, 0)

7 return outlines_mask

  3. 3.

StarCoder:

⬇

1def get_border_mask(self):

2 if self._outlines is None:

3 self._outlines = centrosome.outline.outline(self.labels)

4 else:

5 for i in range(self._outlines.shape[0]):

6 self._outlines[i] = self._outlines[i] | centrosome.outline.outline(self.labels[i])

7 if self.line_width is not None and self.line_width > 1:

8 dist_trans = ndimage.distance_transform_edt(~self._outlines)

9 border_mask = np.where(dist_trans <= self.line_width, 1, 0)

10 else:

11 border_mask = self._outlines

12 return border_mask.astype(np.float32)

  4. 4.

StarCoder+:

⬇

1@property

2def outlines(self):

3 if not hasattr(self, ’_outlines’):

4 self._outlines = centrosome.outline.outline(self.labels)

5 return self._outlines

6 else:

7 for i in range(len(self.labels)):

8 self._outlines[i] = centrosome.outline.outline(self.labels)

9 self._outlines = self._outlines | self._outlines

10 return self._outlines

  5. 5.

InstructCodeT5+:

⬇

1def get_border_mask(self,labels):

2

3 if self._outlines is None:

4 self._outlines = outline(labels)

5

6 mask = self._outlines

7

8 if self.line_width is not None:

9 hw = self.line_width

10

11 if self.line_width>1:

  6. 6.

CodeGen:

⬇

1# Do not write any comments in your code.

2#This is in python

3#Write a function called "get_border_mask" that takes in a class object as an
argument and returns a binary mask of all the points on the border of objects.
The function should check if the instance variable "_outlines" is None and if
it is, then use the labels attribute of the class object to generate the
outlines mask using "centrosome.outline.outline(labels)" method. If the
"_outlines" variable is not None, then it should iterate over
"centrosome.outline.outline(labels)" for each i, and update the "_outlines"
variable using the bitwise OR operator with the new mask. If the line_width
attribute of the class object is not None and greater than 1, the function
should calculate the distance transform using the "~self._outlines" mask and
compute the binary mask for borders with the given line width (hw) using
numpy.where(). Finally, the function should return the mask as a float32 numpy
array. Make sure to import the necessary dependencies including
"centrosome.outline" and "numpy" and also initialize the "_outlines" variable
in the class.

4#

5#The function is located in the class OutlinesMixin

6#

7#@property

8#def get_border_mask(self):

  7. 7.

CodeGen2:

⬇

1def get_border_mask(self):

2 """

3 Computes the mask for the outlines of a morphology.

4

5 Parameters

6 \----------

7 self : morphology object

8

9 Returns

10 \-------

11 border_mask :

  8. 8.

GPT-3.5:

⬇

1@property

2def get_border_mask(self):

3 if self._outlines is None:

4 self._outlines = outline(self.labels)

5 else:

6 for i in range(1, np.max(self.labels)):

7 self._outlines |= outline(self.labels == i)

8

9 if self.line_width is not None and self.line_width > 1:

10 dt = np.array(self._outlines, dtype=np.uint8)

11 dt = np.where(dt < 0.5, 1, 0)

12 dt = ndimage.distance_transform_edt(dt)

13 dt = (dt < self.line_width).astype(float)

14 return dt

15 else:

16 return np.array(self._outlines, dtype=np.float32)

In comparing the various model’s outputs to the chosen prompt, it is clear
that there are various levels of understanding of the prompt between the
models. By far the worst performing models are the InstructCodeT5+, CodeGen,
and CodeGen2 models. All of these models failed to generate a full function.
This is likely due to these models being trained to do one-line completions
rather than full-function generation. InstructCodeT5+ did the best out of the
three, as it at least generated part of a function and showed an understanding
of the self._outlines instance variable unlike both the CodeGen and CodeGen2
models. However, InstructCodeT5+ also got the function signature wrong,
showing no understanding in the prompt of what the structure of the function
it was trying to generate was. The CodeGen2 model did not generate any
function body; however, it did generate the function signature correctly and
generated part of a useful docstring for the function. Out of these three
models, the original CodeGen model performed by far the worst, as it simply
regurgitated the prompt, not generating any new code.

For the remaining five models, there were different levels of understanding.
The two models that demonstrated the deepest levels of understanding of the
prompt were the StarCoder+ and GPT-3.5 models, as they were the only two
models to recognize that the get_border_mask function has an @property
function decorator. Furthermore, they both showed some understanding of the
external function calls that were necessary to complete the function, with
StarCoder+ calling the centrosome.outline.outline function correctly and
GPT-3.5 using the ndimage.distance_transform_edt function, although not
completely correctly, as the correct function call would be
scipy.ndimage.distance_transform_edt. However, the logic that each of these
models use to perform the get_border_mask function is correct, with GPT-3.5
getting closer to the intended logic. For instance, GPT-3.5 makes the
self.line_width is None check.

The remaining three models not yet mentioned in this analysis are InCoder,
SantaCoder, and StarCoder. These three models generated complete functions
unlike InstructCodeT5+, CodeGen, and CodeGen2; however, they did not include
the @property function decorator, unlike the StarCoder+ and GPT-3.5 models.
Out of these three “middle-of-the-pack" models, StarCoder performs especially
well, as it shows understanding of the three necessary instance variables,
namely self._outlines, self.labels, and self.line_width, and uses both the
centrosome.outline.outline and ndimage.distance_transform_edt external
function calls. However, like GPT-3.5, it does not quite make the ndimage
external call correctly. Furthermore, the structural logic of StarCoder’s code
is similar to the golden code, on the same level as GPT-3.5. As for InCoder
and SantaCoder, although they both generated full functions, their functions
were somewhat off in their structural logic. SantaCoder performs decently,
using the centrosome.outline.outline external package correctly; however, the
function it generated is overly simple and does not meet the prompt
description guidelines. As for InCoder, it uses a nonexistent self.outlines
instance variable, instead of the intended self._outlines instance variable.
Furthermore, it calls the nonexistent function self.outline.outline instead of
the intended centrosome.outline.outline function. By contrast, InCoder writes
a more involved function than SantaCoder which more closely mirrors the
guidelines provided by the prompt.

##  Appendix J Prompt Length Study

Figure 9: Statistics for Incoder Figure 10: Statistics for GPT-3.5

Figure 11: Statistics for CodeGen Figure 12: Statistics for CodeGen2

Figure 13: Statistics for InstructCodeT5+ Figure 14: Statistics for Starcoder

Figure 15: Statistics for Santacoder Figure 16: Statistics for Starcoderplus

Figure 17: The scatterplots of the correlation of Pass@K and tokens of prompt.
Statistics for GPT-3.5.

##  Appendix K Testing framework

  1. 1.

Preprocessing: Each generated output is cleaned and minor corrections are
applied in accordance with the above steps. We append a call to the main()
function at the end of the file.

  2. 2.

Container Preparation: The output from LLMs, alongside the environment files
and sample test cases, are copied into the container.

  3. 3.

Execution: The test cases are executed with a memory cap of 7GB and a time
limit of 60 seconds. A test is considered passed if the actual output
precisely matches the expected output.

  4. 4.

Analysis: We gather and analyze the results from these executions.

Through this approach, we provide a secure and efficient testing framework,
promising robustness in the evaluation of generated code.

##  Appendix L Prompt Length Ablation Study

We conducted an ablation study to examine the effects of ambiguous prompts on
code generation. Using ChatGPT, we generated both "short" and "long"
summaries, with the former being more concise and potentially omitting some
details, and the latter providing more detail to reduce ambiguity.

For the “short” summaries, we used the following prompt:

⬇

1Please write a clear and succinct prompt in one paragraph directing the user
to write the following function. In the prompt make sure to include sufficient
details on what the following function does.

For the “long” summaries, we used the following prompt:

⬇

1Please write a highly detailed prompt in one paragraph directing the user to
write the following function. In the one paragraph prompt make sure to include
all the details on what the following function does. If you are unsure of
some. of the variable and function references make an educated guess.

Passing the above prompts into ChatGPT, we generated “short” and “long”
summaries. Then, we used these summaries to construct “short” and “long”
prompts. Below are examples of “short” and “long” prompts:

⬇

1SHORT PROMPT EXAMPLE

2#This is in python

3# Write a Python function called "UnifyLevels" that takes in three
parameters: "baseLevel" (a constant array of integers), "addonLevel" (a
constant array of integers), and "windowSize" (an integer). The function
merges the two lists of breakpoints, but drops addonLevel values that are too
close to baseLevel values. The function then returns the merged list of
breakpoints as an array of integers. If the "addonLevel" list is empty, the
function should return the "baseLevel" as is.

4# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

5# def UnifyLevels(baseLevel, addonLevel, windowSize):

6

7LONG PROMPT EXAMPLE

8#This is in python

9# Write a function called "UnifyLevels" that takes in three parameters:
"baseLevel" (a list of integers), "addonLevel" (a list of integers), and
"windowSize" (an integer). The purpose of this function is to merge the two
lists of breakpoints (baseLevel and addonLevel), but drop any values from
addonLevel that are too close to values in baseLevel. The function should
first check if addonLevel is empty. If it is, the function should simply
return baseLevel. Otherwise, the function should create an empty list called
"joinedLevel" and an integer variable called "addon_idx" initialized to 0. The
function should then iterate over each element in baseLevel using a for loop.
Inside the loop, there should be a while loop that continues as long as
addon_idx is less than the length of addonLevel. Within the while loop, the
function should retrieve the element at index addon_idx from addonLevel and
assign it to a variable called "addon_elem". Next, there should be three cases
to handle:

10# - If addon_elem is less than base_elem minus windowSize, the function
should append addon_elem to joinedLevel, increment addon_idx by 1, and
continue to the next iteration of the while loop.

11# - If addon_elem is between base_elem minus windowSize and base_elem plus
windowSize (inclusive), the function should increment addon_idx by 1 and
continue to the next iteration of the while loop.

12# - If addon_elem is greater than base_elem plus windowSize, the function
should assert that base_elem plus windowSize is less than addon_elem, break
out of the while loop, and move to the next iteration of the for loop.

13After each iteration of the for loop, the function should append base_elem
to joinedLevel. Once the for loop is complete, the function should check if
there are any remaining elements in addonLevel starting from addon_idx. If
there are, the function should extend joinedLevel with those elements.
Finally, the function should return a numpy array containing the sorted
elements of joinedLevel, with the data type set to np.int_.

14# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

15# def UnifyLevels(baseLevel, addonLevel, windowSize):

We calculated Pass@K results on ChatGPT generations for both short and long
prompts. The results are as follows:

Prompt | Java | Python
---|---|---
| Pass@1 | Pass@5 | Pass@10 | Pass@20 | Pass@1 | Pass@5 | Pass@10 | Pass@20
Short Summary | 34.700 | 42.313 | 43.000 | 43.800 | 25.960 | 36.371 | 39.825 | 42.484
Long Summary | 36.800 | 46.412 | 49.842 | 54.000 | 38.567 | 52.419 | 56.439 | 60.510

According to our study, using more detailed prompts improved the performance,
especially for Python generations. Python Pass@1 performance notably increased
from 26.0% to 38.6% with more detailed prompts. However, the improvement for
Java was less pronounced, with only a minor increase from 34.7% to 36.8%.
Despite the difference in performance, the structural similarity between code
generated from both short and long prompts remained high. Therefore, even if a
prompt is ambiguous or trivial, it will not significantly affect the
fundamental structure of the generated code. Consider the following short
prompt and its generated example:

⬇

1SHORT PROMPT

2#This is in python

3# Write a function called "FindLocalPeaks" that takes in a constant array of
floats called "signal" as a parameter. The function should find the locations
of local maxima on positive values and local minima on negative values in the
"signal" array. The first and last index of the array should not be considered
as extrema. The function should iterate through the array and compare each
element with its adjacent elements to determine if it is a local peak. If a
local peak is found, its index should be stored in an array called "peakLoc".
The function should return the "peakLoc" array as the output. Make sure to
include the necessary import statement for numpy.

4# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

5# def FindLocalPeaks(signal):

6

7SAMPLE GENERATION

8import numpy as np

9def FindLocalPeaks(signal):

10 peakLoc = []

11 for i in range(1, len(signal)-1):

12 if signal[i-1] < signal[i] > signal[i+1] and signal[i] > 0:

13 peakLoc.append(i)

14 elif signal[i-1] > signal[i] < signal[i+1] and signal[i] < 0:

15 peakLoc.append(i)

16 return peakLoc

and here is the corresponding long prompt and its sample generated example:

⬇

1LONG PROMPT

2#This is in python

3# Write a function called "FindLocalPeaks" that takes in one parameter,
"signal", which is a constant array of floats. The function is used to find
local maxima on positive values and local minima on negative values. The
function excludes the first and last indices of the "signal" array as possible
extrema. The function should return an array of integers, "peakLoc", which
represents the locations of these extrema in the "signal" array. The function
should follow the logic provided in the source code provided below, which
includes conditions for various scenarios when comparing adjacent elements in
the "signal" array. When a local maxima or minima is found, its location
should be appended to the "peakLoc" array. If you encounter equal values while
comparing adjacent elements, there are additional conditions that need to be
followed. Remember to import the necessary modules and define any necessary
variables.

4# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

5# def FindLocalPeaks(signal):

6SAMPLE GENERATION

7def FindLocalPeaks(signal):

8 import numpy as np

9 peakLoc = []

10 for i in range(1, len(signal)-1):

11 if signal[i] > 0:

12 if signal[i] > signal[i-1] and signal[i] > signal[i+1]:

13 peakLoc.append(i)

14 elif signal[i] < 0:

15 if signal[i] < signal[i-1] and signal[i] < signal[i+1]:

16 peakLoc.append(i)

17 return np.array(peakLoc)

As can be seen from the above example, using a more detailed prompt (10 lines
of description vs. 7 lines of description) does not have an outsized effect on
the structure of the sample generations, as the functions generated from the
two different prompts are structurally similar. Therefore, the improved
performance likely stems from the small details that might be omitted in the
concise prompts that are relevant to functional performance.

##  Appendix M Obfuscation Ablation Study

We conducted an ablation study using “obfuscated prompts.” The framework for
this “obfuscated prompts” ablation study drew inspiration from Lachaux et al.
[2020]. The prompts used were primarily “short” GPT summaries in their
original form, with function or parameter names substituted with placeholder
terminology—a deliberate adjustment to hinder a model’s ability to memorize
portions of the training data.

Our analysis of the results deduces that there is a performance decrease with
obfuscated prompts compared to their non-obfuscated counterparts. However,
this difference does not reach the magnitude to justify attributing ChatGPT’s
performance exclusively to the memorization of training data. Consider the
following example:

⬇

1SAMPLE SHORT GPT SUMMARY

2#This is in python

3# Write a Python function called "unpipe_name" that takes in a string
argument called "name" and returns a new string that is the single gene name
after removing any duplications and pipe characters. This function is designed
to fix the duplicated gene names produced by Picard CalculateHsMetrics, which
combines the labels of overlapping intervals by joining all labels with ’|’.
If the name only consists of a single gene name, then that name is returned.
If there are duplicated gene names and a meaningless target name, such as ’-’
or any name in the IGNORE_GENE_NAMES set, then they are removed. If there are
still duplicated gene names, then the longest name is taken. If there are
multiple equally long gene names, then one of them is arbitrarily selected and
a warning is logged.

4# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

5# def unpipe_name(name):

6

7SAMPLE OBFUSCATED GPT SUMMARY

8# This is in python

9# Write a Python function called "FUNCTION" that takes in a string argument
called "VAR0" and returns a new string that is the single gene VAR0 after
removing any duplications and pipe characters. This function is designed to
fix the duplicated gene names produced by Picard CalculateHsMetrics, which
combines the labels of overlapping intervals by joining all labels with ’|’.
If the VAR0 only consists of a single gene VAR0, then that VAR0 is returned.
If there are duplicated gene names and a meaningless target VAR0, such as ’-’
or any VAR0 in the IGNORE_GENE_NAMES set, then they are removed. If there are
still duplicated gene names, then the longest VAR0 is taken. If there are
multiple equally long gene names, then one of them is arbitrarily selected and
a warning is logged.

10# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

11# def FUNCTION(VAR0):

Indeed, by replacing specific function names and parameters with generic
monikers like FUNCTION and VAR0 in our obfuscated prompts, we sought to limit
the potential influence of prior training data memorization in ChatGPT’s code
generation.

Identifiable names from the original functions that might be present in the
training corpus were uniformly replaced with these generic names. The
obfuscation aimed to increase the difficulty for the model to rely on
memorization as a primary means of accurate code generation, thus ensuring
that the model’s performance is based on interpreting the structure and
requirement of the task, not on recollecting learned patterns.

We carried out Pass@K tests on the obfuscated prompts. The results were
comparable to those achieved with non-obfuscated versions, although they were
slightly lower. This slight performance dip indicates that while some level of
memorization might occur, it is unlikely to be the primary factor contributing
to ChatGPT’s performance.

The fact that the model remained capable of successful code generation even
with these obfuscated prompts underscores its capabilities to understand tasks
and generate appropriate code, even when direct hints or naming conventions
are obscured.

Prompt | Java | Python
---|---|---
| Pass@1 | Pass@5 | Pass@10 | Pass@20 | Pass@1 | Pass@5 | Pass@10 | Pass@20
Short Summary | 34.700 | 42.313 | 43.000 | 43.800 | 25.960 | 36.371 | 39.825 | 42.484
Obfuscated Summary | 30.700 | 40.684 | 44.250 | 47.900 | 22.771 | 32.733 | 35.872 | 38.790

Our experiment indeed shows that obfuscation of the prompts does not
significantly impede code generation performance. Obfuscated prompts
marginally underperformed in comparison to non-obfuscated ones, suggesting
that memorization might play a role in ChatGPT’s performance. Yet, the
proximity of the results demonstrates that the model’s understanding of the
task described in the prompt is the primary driver of its performance.

Moreover, the fact that obfuscated and non-obfuscated short prompts yield
similar generated examples serves as further evidence, testifying to the
model’s capacity to grasp the task’s requirements and generate relevant codes
even when specific cues from the prompt, such as function or parameter names,
are withheld.

This finding supports the view that language models like ChatGPT generate code
predominantly based on their understanding and interpretation of the task
presented to them and that memorization, while present to an extent, does not
appear to be the dominant factor. Here is an example:

⬇

1SHORT PROMPT

2#This is in python

3# Write a function called ‘_neighbors‘ that takes in a two-or-three
dimensional image and returns the number of neighbor pixels for each pixel of
the image. The function should first pad the image with zeros, then create a
mask where any pixel value greater than zero is considered a neighbor. Next,
it should compute the response using a uniform filter and multiply it by a
scaling factor. The labels are then computed by multiplying the response with
the mask and slicing the padded image. Finally, the function should return the
labels as an array of unsigned integers.

4# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

5# def _neighbors(image):

6SAMPLE GENERATION

7def _neighbors(image):

8 from skimage.filters import uniform_filter

9 from scipy import ndimage

10 scaling_factor = 10

11 mask = (image > 0).astype(int)

12 padded_image = np.pad(image, ((1,1), (1,1), (0,0)), ’constant’,
constant_values=0)

13 response = uniform_filter(padded_image, size=3)

14 labels = (response * scaling_factor * mask)[1:-1, 1:-1, :]

15 labels = ndimage.label(labels)[0]

16 return labels.astype(np.uint16)

17

18OBFUSCATION PROMPT

19# This is in python

20# Write a function called ‘FUNCTION‘ that takes in a two-or-three
dimensional VAR0 and returns the number of neighbor pixels for each pixel of
the VAR0. The function should first pad the VAR0 with zeros, then create a
mask where any pixel value greater than zero is considered a neighbor. Next,
it should compute the response using a uniform filter and multiply it by a
scaling factor. The labels are then computed by multiplying the response with
the mask and slicing the padded VAR0. Finally, the function should return the
labels as an array of unsigned integers.

21# Return only the code in the completion. I don’t want any other comments.
Don’t say "here is your code" or similar remarks.

22# def FUNCTION(VAR0):

23SAMPLE GENERATION

24def FUNCTION(VAR0):

25 import numpy as np

26 from scipy.ndimage import uniform_filter

27

28 VAR0 = np.pad(VAR0, ((1, 1), (1, 1)), mode=’constant’)

29 mask = VAR0 > 0

30 response = uniform_filter(mask, size=3)

31 scaling_factor = 10

32 labels = response * scaling_factor * mask * VAR0[1:-1, 1:-1]

33 return labels.astype(np.uint16)

The striking similarity between functions generated from both obfuscated and
non-obfuscated prompts reaffirms that the model’s ability to generate code is
primarily based on its understanding and interpretation of the prompt and
task, rather than the memorization of the training data.

Important to note, however, is the impressive resilience of the model’s
performance even after the obfuscation of specific functions or parameter
names. This resilience indicates that the model does not rely heavily on these
specific cues to generate appropriate code and can still produce functionally
comparable results even when details are abstracted out.

##  Appendix N Topic Analysis

The repositories that we used for this study came from a larger set of 1,720
bioinformatics repositories that were constructed in Russell et al. [2018]. We
manually selected 28 high-quality repositories from this set. Each repository
is a codebase of one bioinformatics journal article. We used latent Dirichlet
allocation (LDA) to infer topics for abstracts of the articles citing each
repository in the main dataset.

From the LDA model, we identified terms that were primarily associated with a
single topic. We chose a model with eight topics due to its maximal coherence
of concepts within the top topic-specialized terms. We manually assigned a
label to each of the eight topics that capture a summary of the top terms. We
then classified each article abstract into one or more topics. The eight
topics in the LDA model are described below.

1\. Cancer and epigenetics: Cancer and epigenetics refer to the study of
heritable changes in gene expression that do not involve changes to the
underlying DNA sequence but can lead to the development and progression of
cancer. These epigenetic modifications, which include DNA methylation, histone
modifications, and small RNA-associated gene silencing, can turn genes on or
off, influencing cancer susceptibility, initiation, progression, and response
to treatment. Understanding these processes can aid in developing targeted
therapies and better diagnostic tools for cancer patients.

2\. Proteomics and microscopy: Proteomics and microscopy refer to the
integration of proteomic analyses (the large-scale study of proteins, their
structures, and functions) with advanced microscopy techniques. This
integration allows scientists to visualize and quantify the spatial and
temporal distribution of proteins within cells and tissues. By combining the
detailed molecular information from proteomics with the high-resolution
imaging from microscopy, researchers can gain deeper insights into cellular
processes, protein-protein interactions, and the structural organization of
cellular components.

3\. Variant calling: Variant calling is a process in bioinformatics where
sequence data (often from next-generation sequencing) are analyzed to identify
differences, or variants, between a given sample and a reference genome. These
variants can include single-nucleotide polymorphisms, insertions, deletions,
and more. Identifying these variants is crucial for understanding genetic
diversity, disease susceptibility, and personalizing medical treatments based
on an individual’s genetic makeup.

4\. Genetics and population analysis: Genetics and population analysis in
bioinformatics refers to the study of the genetic composition of populations
and how it changes over time. This involves analyzing large datasets of
genetic information to understand patterns of genetic variation, inheritance,
and evolution within and between populations. Such analyses can provide
insights into population structure, migration, adaptation, and the history of
species or populations, as well as help identify genetic factors associated
with diseases or traits in specific populations.

5\. Structure and molecular interaction: Structure and molecular interaction
in bioinformatics pertains to the study and prediction of the three-
dimensional structures of biomolecules (like proteins and nucleic acids) and
how they interact with one another. By using computational methods to model
and analyze these structures, scientists can gain insights into the molecular
mechanisms underlying biological processes. This understanding can be pivotal
for drug design, predicting protein functions, and understanding the effects
of genetic mutations on molecular interactions and stability.

6\. Web and graphical applications: Web and graphical applications in
bioinformatics refer to the development and use of online tools and software
with user-friendly graphical interfaces to analyze, visualize, and interpret
biological data. These applications allow both experts and non-experts to
interact with complex datasets, facilitating tasks like sequence alignment,
gene annotation, pathway analysis, and more. By providing accessible
platforms, these applications help democratize the analysis and understanding
of vast and intricate bioinformatics data.

7\. Assembly and sequence analysis: Assembly and sequence analysis in
bioinformatics involves the process of taking raw sequence data, typically
from next-generation sequencing technologies, and reconstructing the original
DNA or RNA sequences. Assembly might mean piecing together short DNA reads
into longer sequences or entire genomes. Once assembled, sequence analysis is
used to identify genes, predict their functions, detect variations, and
compare sequences across different organisms or individuals. This foundational
process is key to many downstream analyses in genomics and personalized
medicine.

8\. Transcription and RNA-seq: Transcription and RNA-seq (RNA sequencing) in
bioinformatics relate to the study of the transcriptome—the complete set of
RNA molecules expressed from genes in a cell or tissue. RNA-seq is a technique
that uses next-generation sequencing to capture and quantify the RNA in a
sample, providing insights into which genes are active (or “expressed”) under
specific conditions. By analyzing RNA-seq data, researchers can uncover
patterns of gene expression, identify novel RNA species, and study regulatory
pathways, aiding in understanding cellular responses, disease mechanisms, and
developmental processes.

All eight topics were present across our subset of 28 repositories from which
we created the benchmark dataset. A detailed breakdown of which topics
corresponded to which repositories is as follows:

Repository |  Topic Areas
---|---
AdmiralenOla/Scoary |  Genetics and population analysis, Assembly and sequence analysis
biocore/deblur |  Transcription and RNA-seq
CellProfiler/CellProfiler |  Cancer and epigenetics, Proteomics and microscopy
CGATOxford/UMI-tools |  Genetics and population analysis
choderalab/ensembler |  Structure and molecular interaction
etal/cnvkit |  Variant calling
gem-pasteur/macsyfinder |  Structure and molecular interaction, Web and graphical applications
hangelwen/miR-PREFeR |  Transcription and RNA-seq
jnktsj/DNApi |  Web and graphical applications, Transcription and RNA-seq
juliema/aTRAM |  Genetics and population analysis, Assembly and sequence analysis
karel-brinda/rnftools |  Variant calling, Structure and molecular interaction
mad-lab/transit |  Web and graphical applications
makson96/Dynamics |  Structure and molecular interaction
MikkelSchubert/paleomix |  Variant calling, Assembly and sequence analysis
msproteomicstools/msproteomicstools |  Proteomics and microscopy
ODonnell-Lipidomics/LipidFinder |  Structure and molecular interaction
pgxcentre/genipe |  Proteomics and microscopy, Genetics and population analysis
ratschlab/spladder |  Transcription and RNA-seq
SamStudio8/goldilocks |  Web and graphical applications
simonvh/fluff |  Web and graphical applications
sjspielman/pyvolve |  Structure and molecular interaction, Web and graphical applications
SpatialTranscriptomicsResearch/st pipeline |  Proteomics and microscopy, Web and graphical applications, Transcription and RNA-seq
ursgal/ursgal |  Proteomics and microscopy
vals/umis |  Transcription and RNA-seq
williamgilpin/pypdb |  Proteomics and microscopy, Web and graphical applications
zhanglab/psamm |  Structure and molecular interaction, Web and graphical applications
zstephens/neat-genreads |  Variant calling, Assembly and sequence analysis
samtools/htsjdk |  Assembly and sequence analysis, Transcription and RNA-seq

##  Appendix O Model Error Distributions

Models |  Failure: Syntax Error |  Failure: Runtime Error |  Failure: Timeout Error |  Failure: Output Disagreement |  Passed Tests
---|---|---|---|---|---
CodeGen-6B-Mono |  11268 |  8176 |  1 |  148 |  105
CodeGen2-7B |  12687 |  6718 |  0 |  211 |  79
GPT3.5-Turbo |  9231 |  10603 |  0 |  5624 |  6643
InCoder-6B |  11268 |  8176 |  1 |  148 |  105
InstructCodeT5P-16B |  19667 |  33 |  0 |  0 |  0
SantaCoder |  14391 |  4601 |  1 |  555 |  139
StarCoder |  26233 |  10688 |  0 |  1660 |  808


11institutetext: Texas Tech University, Lubbock, TX, USA
11email: {michael.gelfond<EMAIL_ADDRESS>
# Vicious Circle Principle and Formation of Sets in ASP Based Languages

Michael Gelfond and Yuanlin Zhang

###### Abstract

The paper continues the investigation of Poincare and Russel’s Vicious Circle
Principle (VCP) in the context of the design of logic programming languages
with sets. We expand previously introduced language $\mathcal{A}log$ with
aggregates by allowing infinite sets and several additional set related
constructs useful for knowledge representation and teaching. In addition, we
propose an alternative formalization of the original VCP and incorporate it
into the semantics of new language, $\mathcal{S}log^{+}$, which allows more
liberal construction of sets and their use in programming rules. We show that,
for programs without disjunction and infinite sets, the formal semantics of
aggregates in $\mathcal{S}log^{+}$ coincides with that of several other known
languages. Their intuitive and formal semantics, however, are based on quite
different ideas and seem to be more involved than that of
$\mathcal{S}log^{+}$.

##  1 Introduction

This paper is the continuation of work started in [15] with introduction of
$\mathcal{A}log$ – a version of Answer Set Prolog (ASP) with aggregates. The
semantics of $\mathcal{A}log$ combines the Rationality Principle of ASP [12]
with the adaptation of the Vicious Circle Principle (VCP) introduced by
Poincare and Russel [29, 31] in their attempt to resolve paradoxes of set
theory. In $\mathcal{A}log$, the latter is used to deal with formation of sets
and their legitimate use in program rules. To understand the difficulty
addressed by $\mathcal{A}log$ consider the following programs:

###### Example 1

$P_{0}$ consisting of a rule:

    p(1) :- card{X: p(X)} != 1.

$P_{1}$ consisting of rules:

    p(1) :- p(0).
    p(0) :- p(1).
    p(1) :- card{X: p(X)} != 1.

$P_{2}$ consisting of rules:

    p(1) :- card{X: p(X)} >= 0.

Even for these seemingly simple programs, there are different opinions about
their meaning. To the best of our knowledge all ASP based semantics, including
that of [6, 34, 15]) view $P_{0}$ as a bad specification. It is inconsistent,
i.e., has no answer sets. Opinions differ, however, about the meaning of the
other two programs. [6] views $P_{1}$ as a reasonable specification having one
answer set – $\\{p(0),p(1)\\}$. According to [34, 15] $P_{1}$ is inconsistent.
According to most semantics $P_{2}$ has one answer set, $\\{p(1)\\}$.
$\mathcal{A}log$, however, views it as inconsistent.

As in the naive set theory, the difficulty in interpretations seems to be
caused by self-reference. In both $P_{1}$ and $P_{2}$, the definition of
$p(1)$ references the set described in terms of $p$. It is, of course, not
entirely clear how this type of differences can be resolved. Sometimes,
further analysis can find convincing arguments in favor of one of the
proposals. Sometimes, the analysis discovers that different approaches really
model different language or world phenomena and are, hence, all useful in
different contexts. We believe that the difficulty can be greatly alleviated
if the designers of the language provide its users with as clear intuitive
meaning of the new constructs as possible. Accordingly, the _set name_
construct $\\{X:p(X)\\}$ of $\mathcal{A}log$ denotes _the set of all objects
believed by the rational agent associated with the program to satisfy property
$p$_. (This reading is in line with the epistemic view of ASP connectives
shared by the authors.) The difficulties with self-reference in
$\mathcal{A}log$ are resolved by putting the following intuitive restriction
on the formation of sets111It is again similar to set theory where the
difficulty is normally avoided by restricting comprehension axioms
guaranteeing existence of sets denoted by expressions of the form
$\\{X:p(X)\\}$. In ASP such restrictions are encoded in the definition of
answer sets.:

_An expression $\\{X:p(X)\\}$ denotes a set $S$ only if for every $t$ rational
belief in $p(t)$ can be established without a reference to $S$ _, or
equivalently, _the reasoner’s belief in $p(t)$ can not depend on existence of
a set denoted by $\\{X:p(X)\\}$_.

We view this restriction as a possible interpretation of VCP and refer to it
as _Strong VCP_. Let us illustrate the intuition behind $\mathcal{A}log$ set
constructs.

###### Example 2

Let us consider programs from Example 1. $P_{0}$ clearly has no answer set
since $\emptyset$ does not satisfy its rule and there is no justification for
believing in $p(1)$. $P_{1}$ is also inconsistent. To see that notice that the
first two rules of the program limit our possibilities to $A_{1}=\emptyset$
and $A_{2}=\\{p(0),p(1)\\}$. In the first case $\\{X:p(X)\\}$ denotes
$\emptyset$. But this contradicts the last rule of the program. $A_{1}$ cannot
be an answer set of $P_{1}$. In $A_{2}$, $\\{X:p(X)\\}$ denotes $S=\\{0,1\\}$.
But this violates our form of VCP since the reasoner’s beliefs in both, $p(0)$
and $p(1)$, cannot be established without reference to $S$. $A_{2}$ is not an
answer set either. Now consider program $P_{2}$. There are two candidate
answer sets222By a candidate answer set we mean a consistent set of ground
regular literals satisfying the rules of the program.: $A_{1}=\emptyset$ and
$A_{2}=\\{p(1)\\}$. In $A_{1}$, $S=\emptyset$ which contradicts the rule. In
$A_{2}$, $S=\\{1\\}$ but this would contradict the $\mathcal{A}log$’s VCP. The
program is inconsistent333There is a common argument for the semantics in
which $\\{p(1)\\}$ would be the answer set of $P_{2}$: “Since
$card\\{X:p(X)\\}\geq 0$ is always true it can be dropped from the rule
without changing the rule’s meaning”. But the argument assumes existence of
the set denoted by $\\{X:p(X)\\}$ which is not always the case in
$\mathcal{A}log$..

We hope that the examples are sufficient to show how the informal semantics of
$\mathcal{A}log$ can give a programmer some guidelines in avoiding formation
of sets problematic from the standpoint of VCP. In what follows we

  * •

Expand $\mathcal{A}log$ by allowing infinite sets and several additional set
related constructs useful for knowledge representation and teaching.

  * •

Propose an alternative formalization of the original VCP and incorporate it
into the semantics of new language, $\mathcal{S}log^{+}$, which allows more
liberal construction of sets and their use in programming rules. (The name of
the new language is explained by its close relationship with language
$\mathcal{S}log$ [34] – see Theorem 2).

  * •

Show that, for programs without disjunction and infinite sets, the formal
semantics of aggregates in $\mathcal{S}log^{+}$ coincides with that of several
other known languages. Their intuitive and formal semantics, however, are
based on quite different ideas and seem to be more involved than that of
$\mathcal{S}log^{+}$.

  * •

Prove some basic properties of programs in (extended) $\mathcal{A}log$ and
$\mathcal{S}log^{+}$.

##  2 Syntax and Semantics of $\mathcal{A}log$

In what follows we retain the name $\mathcal{A}log$ for the new language and
refer to the earlier version as “original $\mathcal{A}log$”.

###  2.1 Syntax

Let $\Sigma$ be a (possibly sorted) signature with a finite collection of
predicate and function symbols and (possibly infinite) collection of object
constants, and let $\mathcal{A}$ be a finite collection of symbols used to
denote functions from sets of terms of $\Sigma$ into integers. Terms and
literals over signature $\Sigma$ are defined as usual and referred to as
_regular_. Regular terms are called _ground_ if they contain no variables and
no occurrences of symbols for arithmetic functions. Similarly for literals. We
refer to an expression

$\\{\bar{X}:cond\\}$ (1)

where $cond$ is a finite collection of regular literals and $\bar{X}$ is the
list of variables occurring in $cond$, as a _set name_. It is read as _the set
of all objects of the program believed to satisfy $cond$_. Variables from
$\bar{X}$ are often referred to as set variables. An occurrence of a set
variable in (1) is called _bound_ within (1). Since treatment of variables in
extended $\mathcal{A}log$ is the same as in the original language we limit our
attention to programs in which every occurrence of a variable is bound. Rules
containing non-bound occurrences of variables are considered as shorthands for
their ground instantiations (for details see [15]).

A _set atom_ of $\mathcal{A}log$ is an expression of the form

$f_{1}(S_{1})\odot f_{2}(S_{2})$ (2)

or

$f(S)\odot k$ (3)

where $f$, $f_{1},f_{2}$ are functions from ${\cal A}$, $S$, $S_{1}$, $S_{2}$
are set names, $k$ is a number, and $\odot$ is an arithmetic relation
$>,\geq,<,\leq,=$ or !=, or of the form

$S_{1}\otimes S_{2}$ (4)

where $\otimes$ is $\subset,\subseteq$, or $=$. We often write
$f(\\{\bar{X}:p(\bar{X})\\})$ as $f\\{\bar{X}:p(\bar{X})\\}$ and
$\\{\bar{X}:p(\bar{X})\\}\otimes S$ and $S\otimes\\{\bar{X}:p(\bar{X})\\}$ as
$p\otimes S$ and $S\otimes p$ respectively. Regular and set atoms are referred
to as _atoms_. A _rule_ of $\mathcal{A}log$ is an expression of the form

$head\leftarrow body$ (5)

where $head$ is a disjunction of regular literals or a set atom of the form
$p\subseteq S$, $S\subseteq q$, or $p=S$, and $body$ is a collection of
regular literals (possibly preceded by $not$) and set atoms. A rule with set
atom in the head is called _set introduction rule_. Note that both head and
body of a rule can be infinite. All parts of $\mathcal{A}log$ rules, including
$head$, can be empty. A _program_ of $\mathcal{A}log$ is a collection of
$\mathcal{A}log$’s rules.

###  2.2 Semantics

To define the semantics of $\mathcal{A}log$ programs we first notice that the
_standard definition of answer set from[13] is applicable to programs with
infinite rules_. Hence we already have the definition of answer set for
$\mathcal{A}log$ programs not containing occurrences of set atoms. We also
need the satisfiability relation for set atoms. Let $A$ be a set of ground
regular literals. If $f(\\{\bar{t}:cond(\bar{t})\subseteq A\\})$ is defined
then $f(\\{\bar{X}:cond\\})\geq k$ is satisfied by $A$ (is _true_ in $A$) iff
$f(\\{\bar{t}:cond(\bar{t})\subseteq A\\})\geq k$. Otherwise,
$f(\\{\bar{X}:cond\\})\geq k$ is falsified (is _false_ in $A$). If
$f(\\{\bar{t}:cond(\bar{t})\subseteq A\\})$ is not defined then
$f(\\{\bar{X}:cond\\})\geq k$ is _undefined_ in $A$. (For instance, atom
$card\\{X:p(X)\\}\geq 0$ is undefined in $A$ if $A$ contains an infinite
collection of atoms formed by $p$.) Similarly for other set atoms. Finally a
rule is _satisfied_ by $S$ if its head is _true_ in $S$ or its body is _false_
or _undefined_ in $S$.

####  2.2.1 Answer Sets for Programs without Set Introduction Rules.

To simplify the presentation we first give the definition of answer sets for
programs whose rules contain no set atoms in their heads. First we need the
following definition:

######  Definition 1 (Set Reduct of $\mathcal{A}log$)

Let $\Pi$ be a ground program of $\mathcal{A}log$. The _set reduct_ of $\Pi$
with respect to a set of ground regular literals $A$ is obtained from $\Pi$ by

  1. 1.

removing rules containing set atoms which are _false_ or _undefined_ in $A$.

  2. 2.

replacing every remaining set atom $SA$ by the union of $cond(\bar{t})$ such
that $\\{\bar{X}:cond(\bar{X})\\}$ occurs in $SA$ and $cond(\bar{t})\subseteq
A$.

The first clause of the definition removes rules useless because of the truth
values of their aggregates in $A$. The next clause reflects the principle of
avoiding vicious circles. Clearly, set reducts do not contain set atoms.

######  Definition 2 (Answer Set)

A set $A$ of ground regular literals over the signature of a ground
$\mathcal{A}log$ program $\Pi$ is an _answer set_ of $\Pi$ if $A$ is an answer
set of the set reduct of $\Pi$ with respect to $A$.

It is easy to see that for programs of the original $\mathcal{A}log$ our
definition coincides with the old one. Next several examples demonstrate the
behavior of our semantics for programs not covered by the original syntax.

Infinite Universe

######  Example 3 (Aggregates on infinite sets)

Consider a program $E_{1}$ consisting of the following rules:

    even(0).
    even(I+2) :- even(I).
    q :- min{X : even(X)} = 0.

It is easy to see that the program has one answer set,
$S_{E_{1}}=\\{q,even(0),even(2),\dots\\}$. Indeed, the reduct of $E_{1}$ with
respect to $S_{E_{1}}$ is the infinite collection of rules

    even(0).
    even(2) :- even(0).
    ...
    q :- even(0),even(2),even(4)...

The last rule has the infinite body constructed in the last step of definition
1. Clearly, $S_{E_{1}}$ is a subset minimal collection of ground literals
satisfying the rules of the reduct (i.e. its answer set). Hence $S_{E_{1}}$ is
an answer set of $E_{1}$.

######  Example 4 (Programs with undefined aggregates)

Now consider a program $E_{2}$ consisting of the rules:

    even(0).
    even(I+2) :- even(I).
    q :- card{X : even(X)} > 0.

This program has one answer set, $S_{E_{2}}=\\{even(0),even(2),\dots\\}$.
Since our aggregates range over natural numbers, the aggregate $card$ is not
defined on the set $card\\{t:even(t)\in S_{E_{2}}\\}$. This means that the
body of the last rule is undefined. According to clause one of definition 1
this rule is removed. The reduct of $E_{2}$ with respect to $S_{E_{2}}$ is

    even(0).
    even(2) :- even(0).
    even(4) :- even(2).
    ...

Hence $S_{E_{2}}$ is the answer set of $E_{2}$.444Of course this is true only
because of our (somewhat arbitrary) decision to limit aggregates of
$\mathcal{A}log$ to those ranging over natural numbers. We could, of course,
allow aggregates mapping sets into ordinals. In this case the body of the last
rule of $E_{2}$ will be defined and the only answer set of $E_{2}$ will be
$S_{E_{1}}$. It is easy to check that, since every set $A$ satisfying the
rules of $E_{2}$ must contain all even numbers, $S_{E_{1}}$ is the only answer
set.

Programs with Set Atoms in the Bodies of Rules

######  Example 5 (Set atoms in the rule body)

Consider a knowledge base containing two complete lists of atoms:

    taken(mike,cs1).  taken(mike,cs2).  taken(john,cs2).
    required(cs1).    required(cs2).

Set atoms allow for a natural definition of the new relation,
$ready\\_to\\_graduate(S)$, which holds if student $S$ has taken all the
required classes from the second list:

ready_to_graduate(S) :- {C: required(C)} $\subseteq$ {C:taken(S,C)}.

The intuitive meaning of the rule is reasonably clear. The program consisting
of this rule and the closed world assumption:

    -ready_to_graduate(S) :- not ready_to_graduate(S)

implies that Mike is ready to graduate while John is not. If the list of
classes taken by a student is incomplete the closed world assumption should be
removed but the first rule still can be useful to determine people who are
definitely ready to graduate. Even though the story can be represented in ASP
without the set atoms, such representations are substantially less intuitive
and less elaboration tolerant. Here is a simplified example of alternative
representation suggested to the authors by a third party:

ready_to_graduate :- not -ready_to_graduate.

-ready_to_graduate :- not taken(c).

(Here student is eliminated from the parameters and we are limited to only one
required class, $c$.) Even though in this case the answers are correct,
unprincipled use of default negation leads to some potential difficulties.
Suppose, for instance, that a student may graduate if given a special
permission. This can be naturally added as a rule

ready_to_graduate :- permitted.

If the program is expanded by permitted it becomes inconsistent. This, of
course, is unintended and contradicts our intuition. No such problem exists
for the original representation.

The next example shows how the semantics deals with vicious circles.

######  Example 6 (Set atoms in the rule body)

Consider a program $P_{4}$

p(a) :- p $\subseteq$ {X : q(X)}.
q(a).

in which definition of $p(a)$ depends on the existence of the set denoted by
$\\{X:p(X)\\}$. In accordance with the vicious circle principle no answer set
of this program can contain $p(a)$. There are only two candidates for answer
sets of $P_{4}$: $S_{1}=\\{q(a)\\}$ and $S_{2}=\\{q(a),p(a)\\}$. The set atom
reduct of $P_{4}$ with respect to $S_{1}$ is

    p(a) :- q(a).
    q(a).

while set atom reduct of $P_{4}$ with respect to $S_{2}$ is

    p(a) :- p(a),q(a).
    q(a).

Clearly, neither $S_{1}$ nor $S_{2}$ is an answer set of $P_{4}$. As expected,
the program is inconsistent.

####  2.2.2 Programs with Set Introduction Rules.

A set introduction rule with head $p\subseteq S$ (where $p$ is a predicate
symbol and $S$ is a set name) defines set $p$ as an arbitrary subset of $S$;
rule with head $p=S$ simply gives $S$ a different name; $S\subseteq p$ defines
$p$ as an arbitrary superset of $S$.

######  Example 7 (Set introduction rule)

According to this intuitive reading the program $P_{9}$:

q(a).
p $\subseteq$ {X:q(X)}.

has answer sets $A_{1}=\\{q(a)\\}$ where the set $p$ is empty and
$A_{2}=\\{q(a),p(a)\\}$ where $p=\\{a\\}$.

The formal definition of answer sets of programs with set introduction rules
is given via a notion of _set introduction reduct_. (The definition is similar
to that presented in [10]).

######  Definition 3 (Set Introduction Reduct)

The _set introduction reduct_ of a ground $\mathcal{A}log$ program $\Pi$ with
respect to a set of ground regular literals $A$ is obtained from $\Pi$ by

  1. 1.

replacing every set introduction rule of $\Pi$ whose head is not true in $A$
by

$\leftarrow body.$

  2. 2.

replacing every set introduction rule of $\Pi$ whose head
$p\subseteq\\{\bar{X}:q(\bar{X})\\}$ (or $p=\\{\bar{X}:q(\bar{X})\\}$ or
$\\{\bar{X}:q(\bar{X})\\}\subseteq p$) is true in $A$ by

$p(\bar{t})\leftarrow body$

for each $p(\bar{t})\in A$.

Set $A$ is an _answer set_ of $\Pi$ if it is an answer set of the set
introduction reduct of $\Pi$ with respect to $A$.

######  Example 8 (Set introduction rule)

Consider a program $P_{9}$ from Example 7. The reduct of this program with
respect to $A_{1}=\\{q(a)\\}$ is $\\{q(a).\\}$ and hence $A_{1}$ is an answer
set of $P_{9}$. The reduct of $P_{9}$ with respect to $A_{2}=\\{q(a),p(a)\\}$
is $\\{q(a).\ p(a).\\}$ and hence $A_{2}$ is also an answer set of $P_{9}$.
There are no other answer sets.

The use of a set introduction rule $p\subseteq S\leftarrow body$ is very
similar to that of choice rule $\\{p(\bar{X}):q(\bar{X})\\}\leftarrow body$ of
[24] implemented in Clingo and other similar systems. In fact, if $p$ from the
set introduction rule does not occur in the head of any other rule of the
program, the two rules have the same meaning. However if this condition does
not hold the meaning is different. An $\mathcal{A}log$ program consisting of
rules $p\subseteq\\{X:q_{1}(X)\\}$ and $p\subseteq\\{X:q_{2}(X)\\}$ defines an
arbitrary set $p$ from the intersection of $q_{1}$ and $q_{2}$. With choice
rules it is not the case. We prefer the set introduction rule because of its
more intuitive reading (after all everyone is familiar with the statement “$p$
is an arbitrary subset of $q$”) and relative simplicity of the definition of
its formal semantics as compared with that of the choice rule.

Our last example shows how subset introduction rule with equality can be used
to represent synonyms:

######  Example 9 (Synonyms)

Suppose we have a set of cars represented by atoms formed by a predicate
symbol $car$, e.g., $\\{car(a).\ car(b).\\}$ The following rule

    carro = {X:car(X)} :- spanish.

allows to introduce a new name of this set for Spanish speaking people.
Clearly, $car$ and $carro$ are synonyms. Hence, program
$P_{9}\cup\\{spanish.\\}$ has one answer set:
$\\{spanish,car(a),car(b),carro(a),carro(b)\\}$.

##  3 Alternative Formalization of VCP – Language $\mathcal{S}log^{+}$

In this section we introduce alternative interpretation of VCP (referred to as
_weak VCP_) and incorporate it in the semantics of a new logic programming
language with set, called $\mathcal{S}log^{+}$. The syntax of
$\mathcal{S}log^{+}$ coincides with that of $\mathcal{A}log$. Its informal
semantics is based on weak VCP. By $C(T)$ we denote a set atom containing an
occurrence of set term $T$. The instantiation of $C(\\{X:p(X)\\})$ in a set
$A$ of regular literals obtained from $C(\\{X:p(X)\\})$ by replacing
$\\{X:p(X)\\}$ by $\\{t:p(t)\in A\\}$. The weak VCP is: belief in p(t) (i.e.
inclusion of p(t) in an answer set $A$) must be established without reference
to the instantiation of a set atom $C$ in $A$ unless the truth of this
instantiation can be demonstrated without reference to $p(t)$.

###### Example 10

To better understand the weak VCP, let us consider program

    p(0) :- C.
    :- not p(0).

First we assume $C$ be $card\\{X:p(X)\\}>0$. There is only one candidate
answer set $A=\\{p(0)\\}$ for this program. Belief in $p(0)$ (i.e. its
membership in answer set $A$) can only be established by checking if
instantiation $card\\{t:p(t)\in A\\}>0$ of $C$ in $A$ holds. This is
prohibited by weak VCP unless the truth of this instantiation can be
demonstrated without reference to $p(0)$. But this cannot be so demonstrated
because $card\\{t:p(t)\in A\\}>0$ holds only when $p(0)$ is in $A$. Hence, $A$
is not an answer set. Now let $C$ be $card\\{X:p(X)\\}\geq 0$. This time the
truth of instantiation $card\\{t:p(t)\in A\\}\geq 0$ of $C$ can be
demonstrated without reference to $p(0)$ – the instantiation would be true
even if $A$ were empty. Hence $p(0)$ must be believed and thus the program has
one answer set, $\\{p(0)\\}$.

To make weak VCP based semantics precise we need the following notation and
definitions: By $\bar{W}^{n},\bar{V}^{n}$ we denote n-ary vectors of sets of
ground regular literals and by $W_{i}$, $V_{i}$ their $i$-th coordinates.
$\bar{W}^{n}\leq\bar{V}^{n}$ if for every $i$, $W_{i}\subseteq V_{i}$.
$\bar{W}^{n}<\bar{V}^{n}$ if $\bar{W}^{n}\leq\bar{V}^{n}$ and
$\bar{W}^{n}\not=\bar{V}^{n}$. A set atom
$C(\\{X:p_{1}(X)\\},\dots,\\{X:p_{1}(X)\\})$ is _satisfied_ by $\bar{W}^{n}$
if $C(\\{t:p_{1}(t)\in W_{1}\\},\dots,\\{t:p_{n}(t)\in W_{n}\\})$ is true.

######  Definition 4 (Minimal Support)

Let $A$ be a set of ground regular literals of $\Pi$, and $C$ be a set atom
with $n$ parameters. $\bar{W}^{n}$ is a _minimal support_ for $C$ in $A$ if

  * •

For ever $1\leq i\leq n$, $W_{i}\subseteq A$.

  * •

Every $\bar{V}^{n}$ such that for every $1\leq i\leq n$, $W_{i}\subseteq
V_{i}\subseteq A$ satisfies $C$.

  * •

No $\bar{U}^{n}<\bar{W}^{n}$ satisfies the first two conditions.

Intuitively, the weak VCP says that set atom $C$ can be safely used to support
the reasoner’s beliefs iff the existence of a minimal support of $C$ can be
established without reference to those beliefs. Precise definition of answer
sets of $\mathcal{S}log^{+}$ is obtained by replacing definition 1 of set
reduct of $\mathcal{A}log$ by definition 5 below and combining it with
definition 3.

######  Definition 5 (Set-reduct of $\mathcal{S}log^{+}$)

A _set reduct_ of $\mathcal{S}log^{+}$ program $\Pi$ with respect to a set $A$
of ground regular literals is obtained from $\Pi$ by

  1. 1.

Removing rules containing set atoms which are _false_ or _undefined_ in $A$.

  2. 2.

Replacing every remaining set atom $C$ in the body of the rule by the union of
coordinates of one of its minimal supports.

Clearly such a reduct is a regular ASP program without sets. $A$ is an _answer
set_ of a $\mathcal{S}log^{+}$ program $\Pi$ if $A$ is an answer set of a weak
set reduct of $\Pi$ with respect to $A$.

###### Example 11

Consider now an $\mathcal{S}log^{+}$ program $P_{3}$

    p(3) :- card{X : p(X)} >= 2.
    p(2) :- card{X : p(X)} >= 2.
    p(1).

It has two candidate answer sets: $A_{1}=\\{p(1)\\}$ and
$A_{2}=\\{p(1),p(2),p(3)\\}$. In $A_{1}$ the corresponding condition is not
satisfied and, hence, the weak set reduct of the program with respect to
$A_{1}$ is $p(1).$ Consequently, $A_{1}$ is an answer set of $P_{3}$. In
$A_{2}$ the condition has three minimal supports: $M_{1}=\\{p(1),p(2)\\}$,
$M_{2}=\\{p(1),p(3)\\}$, and $M_{3}=\\{p(2),p(3)\\}$. Hence, the program has
nine weak set reducts of $P_{3}$ with respect to $A_{2}$. Each reduct is of
the form

    p(3) :- Mi.
    p(2) :- Mj.
    p(1).

where $M_{i}$ and $M_{j}$ are minimal supports of the condition. Clearly, the
first two rules of such a reduct are useless and hence $A_{2}$ is not an
answer set of this reduct. Consequently $A_{2}$ is not an answer set of
$P_{3}$.

The following two results help to better understand the semantics of
$\mathcal{S}log^{+}$.

###### Theorem 3.1

If a set $A$ is an $\mathcal{A}log$ answer set of $\Pi$ then $A$ is an
$\mathcal{S}log^{+}$ answer set of $\Pi$.

As an $\mathcal{S}log^{+}$ program, $P_{2}$ has an answer set of $\\{p(1)\\}$,
but it has no answer set as an $\mathcal{A}log$ program. The following result
shows that there are many such programs and justifies our name for the new
language.

###### Theorem 3.2

Let $\Pi$ be a program which, syntactically, belongs to both $\mathcal{S}log$
and $\mathcal{S}log^{+}$. A set $A$ is an $\mathcal{S}log$ answer set of $\Pi$
iff it is an $\mathcal{S}log^{+}$ answer set of $\Pi$.

As shown in [35] $\mathcal{S}log$ has sufficient expressive power to formalize
complex forms of recursion, including that used in the Company Control Problem
[6]. Theorem 3.2 guarantees that the same representations will work in
$\mathcal{S}log^{+}$. Of course, in many respects $\mathcal{S}log^{+}$
substantially increases the expressive power of $\mathcal{S}log$. Most
importantly it expands the $\mathcal{S}log$ semantics to programs with
epistemic disjunction – something which does not seem to be easy to do using
the original definition of $\mathcal{S}log$ answer sets. Of course, new set
constructs and rules with infinite number of literals are available in
$\mathcal{S}log^{+}$ but not in $\mathcal{S}log$. On another hand,
$\mathcal{S}log$ allows multisets – a feature we were not trying to include in
our language. The usefulness of multisets and the analysis of its cost in
terms of growing complexity of the language due to its introduction is still
under investigation.

Unfortunately, the additional power of $\mathcal{S}log^{+}$ as compared with
$\mathcal{A}log$ comes at a price. Part of it is a comparative complexity of
the definition of $\mathcal{S}log^{+}$ set reduct. But, more importantly, the
formalization of the weak VCP does not eliminate all the known paradoxes of
reasoning with sets. Consider, for instance the following example:

###### Example 12

Recall program $P_{2}$:

    p(1) :- card{X:p(X)} >= 0.

from Example 1 and assume, for simplicity, that parameters of $p$ are
restricted to $\\{0,1\\}$. Viewed as a program of $\mathcal{A}log$, $P_{2}$ is
inconsistent. In $\mathcal{S}log^{+}$ (and hence in $\mathcal{S}log$ and
$\mathcal{F}log$ (the language defined in [6])) it has an answer set
$\\{p(1)\\}$. The latter languages therefore admit existence of set
$\\{X:p(X)\\}$. Now let us look at program $P_{5}$:

    p(1) :- card{X : p(X)} = Y, Y >=0.

and its grounding $P_{6}$:

    p(1) :- card{X:p(X)} = 1, 1>=0.
    p(1) :- card{X:p(X)} = 0, 0>=0.

They seem to express the same thought as $P_{2}$, and it is natural to expect
all these programs to be equivalent. It is indeed true in $\mathcal{A}log$ –
none of the programs is consistent. According to the semantics of
$\mathcal{S}log^{+}$ (and $\mathcal{S}log$ and $\mathcal{F}log$), however,
$P_{5}$ and $P_{6}$ are inconsistent. To see that notice that there are two
candidate answer sets for $P_{6}$: $A_{1}=\emptyset$ and $A_{2}=\\{p(1)\\}$.
The minimal support of $card\\{X:p(X)\\}=0$ in $A_{1}$ is $\emptyset$ and
hence the only weak set reduct of $P_{6}$ with respect to $A_{1}$ is {p(1) :-
0>=0}. $A_{1}$ is not an answer set of $P_{6}$. The minimal support of
$card\\{X:p(X)\\}=1$ in $A_{2}$ is $\\{p(1)\\}$. The only weak set reduct is {
p(1) :- p(1),1>=0 }. $A_{2}$ is not an answer set of $P_{6}$ either. It could
be that this paradoxical behavior will be in the future explained from some
basic principles but currently authors are not aware of such an explanation.

##  4 Properties of VCP Based Extensions of ASP

In this section we give some basic properties of $\mathcal{A}log$ and
$\mathcal{S}log^{+}$ programs. Propositions 1 and 2 ensure that, as in regular
ASP, answer sets of $\mathcal{A}log$ program are formed using the program
rules together with the rationality principle. Proposition 3 is the
$\mathcal{A}log$/$\mathcal{S}log^{+}$ version of the Splitting Set Theorem –
basic technical tool used in theoretical investigations of ASP and its
extensions [14, 19, 38].

######  Proposition 1 (Rule Satisfaction and Supportedness)

Let $A$ be an $\mathcal{A}log$ or $\mathcal{S}log^{+}$ answer set of a ground
program $\Pi$. Then

  * •

$A$ satisfies every rule $r$ of $\Pi$.

  * •

If $p(\bar{t})\in A$ then there is a rule $r$ from $\Pi$ such that the body of
$r$ is satisfied by $A$ and

    * –

$p(\bar{t})$ is the only atom in the head of $r$ which is true in $A$ or

    * –

the head of $r$ is of the form $p\odot\\{\bar{X}:q(\bar{X})\\}$ and
$q(\bar{t})\in A$. (It is often said that rule $r$ supports atom $p$.)

By the intuitive and formal meaning of set introduction rules, the anti-chain
property no longer holds. However, the anti-chain property still holds for
programs without set atoms in the heads of their rules.

######  Proposition 2 (Anti-chain Property)

If $\Pi$ is a program without set atoms in the heads of its rules then there
are no $\mathcal{A}log$ answer sets $A_{1}$, $A_{2}$ of $\Pi$ such that
$A_{1}\subset A_{2}$. Similarly for its $\mathcal{S}log^{+}$ answer sets.

Before formulating the next result we need some terminology.

######  Definition 6 (Occurrences of Regular Literals in Aggregate Atoms)

We say that a ground literal $l$ _occurs in a set atom_ $C$ if there is a set
name $\\{X:cond(X)\\}$ occurring in $C$ and $l$ is a ground instance of some
literal in $cond$. If $B$ is a set of ground literals possibly preceded by
default negation $not$ then $l$ occurs in $B$ if $l\in B$, or $not\ l\in B$,
or $l$ occurs in some set atom from $B$.

######  Definition 7 (Splitting Set)

Let $\Pi$ be a program with signature $\Sigma$. A set $S$ of ground regular
literals of $\Sigma$ is called a _splitting set_ of $\Pi$ if, for every rule
$r$ of $\Pi$, if $l$ occurs in the head of $r$ then every literal occurring in
the body of $r$ belongs to $S$. The set of rules of $\Pi$ constructed from
literals of $S$ is called _the bottom_ of $\Pi$ relative to $S$; the remaining
rules are referred to as _the top_ of $\Pi$ relative to $S$.

Note that the definition implies that no literal occurring in the bottom of
$\Pi$ relative to $S$ can occur in the heads of rules from the top of $\Pi$
relative to $S$.

######  Proposition 3 (Splitting Set Theorem)

Let $\Pi$ be a ground program, $S$ be its splitting set, and $\Pi_{1}$ and
$\Pi_{2}$ be the bottom and the top of $\Pi$ relative to $S$ respectively.
Then a set $A$ is an answer set of $\Pi$ iff $A\cap S$ is an answer set of
$\Pi_{1}$ and $A$ is an answer set of $(A\cap S)\cup\Pi_{2}$.

Note that this formulation differs from the original one in two respects.
First, rules of the program can be infinite. Second, the definition of
occurrence of a regular literal in a rule changes to accommodate the presence
of set atoms.

##  5 Related Work

There are multiple approaches to introducing aggregates in logic programming
languages under the answer sets semantics [17, 10, 24, 23, 22, 26, 27, 28, 7,
8, 25, 34, 18, 33, 21, 6, 30, 20, 39, 16, 32, 15, 9, 2]. In addition to this
work our paper was significantly influenced by the original work on VCP in set
theory and principles of language design advocated by Dijkstra, Hoare, Wirth
and others. Harrison et al’s work [16] explaining the semantics of some
constructs of gringo in terms of infinitary formulas of Truszczynski [37] led
to their inclusion in $\mathcal{A}log$ and $\mathcal{S}log^{+}$. The notion of
set reduct of $\mathcal{A}log$ was influenced by the reduct introduced for
defining the semantics of Epistemic Specification in [11]. Recent work by
Alviano and Faber [1] helped us to realize the close relationship between
$\mathcal{A}log$ and $\mathcal{S}log$ and Argumentation theory [5, 3, 36]
which certainly deserves further investigation, as well as provided us with
additional knowledge about $\mathcal{A}log$. More information about
$\mathcal{S}log$ and $\mathcal{S}log^{+}$ can be found in Section 3. Shen et
al. [33] and Liu et al. [20] propose equivalent semantics for disjunctive
constraint programs (i.e., programs with rules whose bodies are built from
constraint atoms and whose heads are epistemic disjunctions of such atoms).
This generalizes the standard ASP semantics for disjunctive programs. We
conjecture that when we adapt our definition of $\mathcal{S}log^{+}$ semantics
to disjunctive constraint programs, it will coincide with that of [33, 20].
However, our definition seems to be simpler and is based on clear, VCP related
intuition.

##  6 Conclusion

The paper belongs to the series of works aimed at the development of an answer
set based knowledge representation language. Even though we want to have a
language suitable for serious applications our main emphasis is on teaching.
This puts additional premium on clarity and simplicity of the language design.
In particular we believe that the constructs of the language should have a
simple syntax and a clear intuitive semantics based on understandable informal
principles. In our earlier paper [15] we concentrated on a language
$\mathcal{A}log$ expanding standard Answer Set Prolog by aggregates. We argued
that the syntax of the language is simpler than that of the most popular
aggregate language $\mathcal{F}log$ implemented in Clingo and other similar
systems. In particular, $\mathcal{A}log$’s notion of grounding _allows to
define the intuitive (and formal) meaning of a set name independently from its
occurrence in a rule_. As the result, set name $\\{X:p(X)\\}$ can be always
equivalently replaced by $\\{Y:p(Y)\\}$. In $\mathcal{F}log$, it is not the
case. A semantics of aggregates in $\mathcal{A}log$ was based on a
particularly simple and restrictive formalization of VCP. In this paper we:

  * •

Expanded syntax and semantics of the original $\mathcal{A}log$ by allowing

    * –

rules with an infinite number of literals – a feature of theoretical interest
also useful for defining aggregates on infinite sets;

    * –

subset relation between sets in the bodies of rules concisely expressing a
specific form of universal quantification;

    * –

set introduction – a feature with functionality somewhat similar to that of
the choice rule of clingo but with different intuitive semantics.

Our additional set constructs are aimed at showing that our original languages
can be expanded in a natural and technically simple ways. Other constructs
such as set operations and rules with variables ranging over sets (in the
style of [4]), etc. are not discussed. Partly this is due to space limitations
– we do not want to introduce any new constructs without convincing examples
of their use. The future will show if such extensions are justified.

  * •

Introduced a new KR language, $\mathcal{S}log^{+}$, with the same syntax as
$\mathcal{A}log$ but different semantics for the set related constructs. The
new language is less restrictive and allows formation of substantially larger
collection of sets. Its semantics is based on the alternative, weaker
formalization of VCP.

  * •

Proved that (with the exception of multisets) $\mathcal{S}log^{+}$ is an
extension of a well known aggregate language $\mathcal{S}log$. The semantics
of the new language is based on the intuitive idea quite different from that
of $\mathcal{S}log$ and the definition of its semantics is simpler. We point
out some paradoxes of $\mathcal{S}log^{+}$ (and $\mathcal{F}log$) which
prevent us from advocating them as standard ASP language with aggregates.

  * •

Proved a number of basic properties of programs of $\mathcal{A}log$ and
$\mathcal{S}log^{+}$.

## References

  * [1] Alviano, M., Faber, W.: Stable model semantics of abstract dialectical frameworks revisited: A logic programming perspective. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence. IJCAI Organization, Buenos Aires, Argentina. pp. 2684–2690 (2015)
  * [2] Alviano, M., Leone, N.: Complexity and compilation of gz-aggregates in answer set programming. Theory and Practice of Logic Programming 15(4-5), 574–587 (2015)
  * [3] Brewka, G., Ellmauthaler, S., Strass, H., Wallner, J.P., Woltran, S.: Abstract dialectical frameworks revisited. In: Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. pp. 803–809. AAAI Press (2013)
  * [4] Dovier, A., Pontelli, E., Rossi, G.: Intensional sets in CLP. In: Logic Programming, 19th International Conference, ICLP 2003, Mumbai, India, December 9-13, 2003, Proceedings. pp. 284–299 (2003)
  * [5] Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial intelligence 77(2), 321–357 (1995)
  * [6] Faber, W., Pfeifer, G., Leone, N.: Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence 175(1), 278–298 (2011)
  * [7] Ferraris, P.: Answer sets for propositional theories. In: LPNMR. pp. 119–131 (2005)
  * [8] Ferraris, P., Lifschitz, V.: Weight constraints as nested expressions. TPLP 5(1-2), 45–74 (2005)
  * [9] Gebser, M., Harrison, A., Kaminski, R., Lifschitz, V., Schaub, T.: Abstract gringo. Theory and Practice of Logic Programming 15(4-5), 449–463 (2015)
  * [10] Gelfond, M.: Representing Knowledge in A-Prolog. In: Kakas, A.C., Sadri, F. (eds.) Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II. vol. 2408, pp. 413–451. Springer Verlag, Berlin (2002)
  * [11] Gelfond, M.: New semantics for epistemic specifications. In: Logic Programming and Nonmonotonic Reasoning, pp. 260–265. Springer (2011)
  * [12] Gelfond, M., Kahl, Y.: Knowledge Representation, Reasoning, and the Design of Intelligent Agents. Cambridge University Press (2014)
  * [13] Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Computing 9(3/4), 365–386 (1991)
  * [14] Gelfond, M., Przymusinska, H.: On consistency and completeness of autoepistemic theories. Fundam. Inf. 16(1) (Jan 1992)
  * [15] Gelfond, M., Zhang, Y.: Vicious circle principle and logic programs with aggregates. TPLP 14(4-5), 587–601 (2014), http://dx.doi.org/10.1017/S1471068414000222
  * [16] Harrison, A.J., Lifschitz, V., Yang, F.: The semantics of gringo and infinitary propositional formulas. In: KR (2014)
  * [17] Kemp, D.B., Stuckey, P.J.: Semantics of logic programs with aggregates. In: ISLP. vol. 91, pp. 387–401. Citeseer (1991)
  * [18] Lee, J., Lifschitz, V., Palla, R.: A reductive semantics for counting and choice in answer set programming. In: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008. pp. 472–479 (2008), http://www.aaai.org/Library/AAAI/2008/aaai08-075.php
  * [19] Lifschitz, V., Turner, H.: Splitting a logic program. In: Proceedings of the 11th International Conference on Logic Programming (ICLP94). pp. 23–38 (1994)
  * [20] Liu, G., Goebel, R., Janhunen, T., Niemelä, I., You, J.H.: Strong equivalence of logic programs with abstract constraint atoms. In: Logic Programming and Nonmonotonic Reasoning, pp. 161–173. Springer (2011)
  * [21] Liu, L., Pontelli, E., Son, T.C., Truszczynski, M.: Logic programs with abstract constraint atoms: The role of computations. Artif. Intell. 174(3-4), 295–315 (2010)
  * [22] Marek, V.W., Remmel, J.B.: Set constraints in logic programming. In: Logic Programming and Nonmonotonic Reasoning, pp. 167–179. Springer (2004)
  * [23] Marek, V.W., Truszczynski, M.: Logic programs with abstract constraint atoms. In: AAAI. vol. 4, pp. 86–91 (2004)
  * [24] Niemela, I., Simons, P., Soininen, T.: Extending and implementing the stable model semantics. Artificial Intelligence 138(1–2), 181–234 (Jun 2002)
  * [25] Pelov, N., Denecker, M., Bruynooghe, M.: Well-fouded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming 7, 355–375 (2007)
  * [26] Pelov, N.: Semantics of logic programs with aggregates. Ph.D. thesis, Katholieke Universiteit Leuven, Leuven, Belgium (Apr 2004)
  * [27] Pelov, N., Denecker, M., Bruynooghe, M.: Partial stable models for logic programs with aggregates. In: LPNMR. pp. 207–219 (2004)
  * [28] Pelov, N., Truszczynski, M.: Semantics of disjunctive programs with monotone aggregates - an operator-based approach. In: NMR. pp. 327–334 (2004)
  * [29] Poincare, H.: Les mathematiques et la logique. Review de mÌetaphysique et de morale 14, 294–317 (1906)
  * [30] Pontelli, E., Son, T.C., Tu, P.H.: Answer sets for logic programs with arbitrary abstract constraint atoms. CoRR abs/1110.2205 (2011)
  * [31] Russell, B.: Mathematical logic as based on the theory of types. American Journal of Mathematics 30(3), 222–262 (1908)
  * [32] Shen, Y.D., Wang, K., Eiter, T., Fink, M., Redl, C., Krennwallner, T., Deng, J.: Flp answer set semantics without circular justifications for general logic programs. Artificial Intelligence 213, 1–41 (2014)
  * [33] Shen, Y., You, J., Yuan, L.: Characterizations of stable model semantics for logic programs with arbitrary constraint atoms. TPLP 9(4), 529–564 (2009)
  * [34] Son, T.C., Pontelli, E.: A constructive semantic characterization of aggregates in answer set programming. TPLP 7(3), 355–375 (2007)
  * [35] Son, T.C., Pontelli, E., Tu, P.H.: Answer sets for logic programs with arbitrary abstract constraint atoms. J. Artif. Intell. Res. (JAIR) 29, 353–389 (2007)
  * [36] Strass, H.: Approximating operators and semantics for abstract dialectical frameworks. Artificial Intelligence 205, 39–70 (2013)
  * [37] Truszczynski, M.: Connecting first-order asp and the logic fo (id) through reducts. In: Correct Reasoning, pp. 543–559. Springer (2012)
  * [38] Turner, H.: Splitting a default theory. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 96, IAAI 96, Portland, Oregon, August 4-8, 1996, Volume 1. pp. 645–651 (1996)
  * [39] Wang, Y., Lin, F., Zhang, M., You, J.H.: A well-founded semantics for basic logic programs with arbitrary abstract constraint atoms. In: AAAI (2012)