SillyCon
SillyCon is a rather silly language for expressing numerical constraint problems, created by Rick van der Meiden.
Language
The SillyCon language is used to represent integer constraint problems. An integer constraint problem is an expression with numbers, variables and operators (such as addition, multiplication, boolean operations, comparisons and special constraint solving operations). A constraint problem defines the allowed values of the variables. A constraint problem is solved by a constraint solver, which is part of the SillyCon interpreter. The constraint solver returns all the solutions, i.e. values for the variables, if there are any.
The language uses a prefix notation for operators (e.g. +4 5 means 4+5, =x3 means x=3). All operators and variables are single characters. All punctuation characters are operators. All alphabetic characters are variables. All sequences of digits are numbers. Whitespace is ignored (but may be used to separate numbers). Note that its not possible to declare variable names (or operators) of more than one character.
The input is a sequence of expressions. Each expression is interpreted as a separate problem and solved separately, i.e. constraints on variables in one problem are not passed to then next problem.
An expression is a variable, a constant, or a composite expression consisting of an operator and one or more subexpressions.
Constants are sequences of digits; e.g 1 100 828527 00027
Variables are single alphabetic characters a-z and A-Z; so 'Foo' and 'bar' are just sequences of three variables, the interpretation depends on the context (i.e. preceding operator). For example, '+xy' or '*px' are complete expressions; i.e. one operator with two operands.
Constants and variables are signed integer numbers. Negative constants are entered using the unary - operator. The result of an operator is also a signed integer number. The internal binary representation (i.e. after integer problems are converted to binary problems) is two's compliment. (You may want to know this if you use the boolean operators on numbers).
Variables currently have a fixed size, i.e. the number of bits. This is currently hard-coded in the SillyCon interpreter (9 bits in the current implementation, i.e. from -256 to +255) but this will probably be made dynamic in the future. Results of operands can have more bits.
Operators are single punctuation characters; operators have 1 or 2 operands. Operands can be any expression, i.e. a constant, a variables or an operator-expression.
The accepted operators are the following:
symbol name arity meaning
-------------------------------
integer arithmetic:
- NEG 1 integer negation
+ ADD 2 integer addition
* MUL 2 integer multiplication
/ DIV 2 integer division (quotient)
% MOD 2 integer floor modulus (remainder)
integer comparison:
= EQUAL 2 1 if operands are equal (bit for bit), otherwise 0
> GT 2 1 if operand 1 greater than operand 2, otherwise 0
< LT 2 1 if operand 1 less than operand 2, otherwise 0
boolean logic:
! NOT 1 binary NOT
& AND 2 binary AND
| OR 2 binary OR
^ XOR 2 binary XOR
: IMPL 2 binary IMPL
solving:
@ CON 1 constrain the operand equal to 1
# COUNT 1 number of solutions of operand 1
$ MAX 2 maximum value of operand 1 for all solutions of operand 2
_ MIN 2 minimum value of operand 1 for all solutions of operand 2
' EVAL 2 set of values of operand 1 for all solutions of operand 2
` IND 2 union of constraints of operand 1 where variables in operand 1
are replaced by variables pointed to by values of those
variables in solutions of operand 2
special:
? PNTR 1 A pointer. Convert a number to variable (vice versa in an IND)
" comment
reserved:
. , \ [] () ~ ;
Comments are enclosed in a pair of double quotes: "this is a comment"
The root expression is implicitly constrained to 1 (see @ operator) if it starts with a boolean operator or comparator (EQ, NOT, GREATER, etc.). If the root expression is a numerical expression (see ADD, SUB, etc.) the result will be constrained equal to a variable '?1'.
So, the following numerical expression:
+ 3 4
will be interpreted as the following problem
@=?1+3 4
(and the solution will be ?1=7)
And the following boolean expression:
=x3
will be interpreted as the following problem:
@=x3
(and the solution will be x=3)
Also, the problem solving operators (see EVAL, IND, MIN, MAX and COUNT) will implicitly constrain the subproblem expression (one of the input expressions) to 1.
The COUNT, EVAL, MIN, MAX and IND operators will interpret one operand (the only one for COUNT, or the second one for the others) as a sub-problem and solve it. After solving this sub-problem, the first operand (of MIN,MAX,EVAL,IND) will be converted into a new expression, which will be solved in a second solving step.
Note that MIN and MAX operators do not generate all solutions for the subproblem. In fact, they are quite efficient. The boolean variables are ordered such that the first solution found is the desired solution. On the other hand, the COUNT, EVAL and IND operators will generate all solutions for he sub-problem, so these can be very expensive operations.
The '?' (PNTR, short for 'pointer') symbol, followed by a number, can be used for numbered variables. So '?1' refers to a variable and '?2' refers to another variable. Variable '?65' to '?90' are the same as variables 'A' to 'Z' and '?97' to '?122' equal 'a' to 'z'. Note that the number following '?' cannot be determined by solving a sub-expression. It must be a literal, positive number. However, the IND expression can be used to create problems with a variable that is pointed to by another variable. The maximum variable number is currently hard-coded to 999, but this may change in future releases.
The IND expression (short for indirection) first solves the right operand. For all the solutions of the right operand, it will create a new expression based on the left operand and replacing all variables in it with a new variable pointed to by the value of the variable in that solution. Effectively, all variables in the left operand that are also in the right operand, will be replaced with a PNTR operator and a number. All these expression will be joined by a union operator, creating a new problem to be solved.
Note that Inside the left operand of an IND expression, the PNTR operator works the other way around. It converts the name of a variable (again, not a complete expression, but a single character variable name) to a number, i.e. the value of that variable in the solution of right operand. (It would actually more logical to use the PNTR in an IND as it works outside, but allow variables used in a PNTR. Normal variables will than simply take on a value, and pointers can be used to refer to variables. We might do this in the future, However, this will break backwards compatibility.)
Example Code
The following expression represents the problem: x*y = 10
=10*xy
The result is:
x = 10, y = 1 x = 5, y = 2 x = 2, y = 5 x = 1, y = 10 x = -1, y = -10 x = -2, y = -5 x = -5, y = -2 x = -10, y = -1
The following expression approximates x = sqrt(z) (x is the smallest positive integer for which x*x <= z)
&<z*+1x+1x&>+1z*xx&>x-1=z200
And this one:
`&=A1=y+1x&=y+1x&>x64<x90
Results in:
A=1 B=2 C=3 D=4 E=5 F=6 G=7 H=8 I=9 J=10 K=11 L=12 M=13 N=14 O=15 P=16 Q=17 R=18 S=19 T=20 U=21 V=22 W=23 X=24 Y=25 Z=26
Implementation
A SillyCon interpreter/solver (also called SillyCon) has been implemented in C. It converts the problem into a Boolean Propagation Problem, and uses a Boolean Propagation Solver to determine the solutions.
The SillyCon interpreter program accepts input from the stdin stream or from a file given as the first command line argument. As soon as a complete expression has been entered (i.e. each operator has the required number of operands), it will be considered a problem and it will be solved.
Turing Completeness
No. SillyCon programs always terminate, therefore you cannot implement a Turing machine. It might be possible to implement a time and space and symbol bounded Turing machine.