Compile-time calculation

Some programming languages allow calculation of values at compile time. For this task, calculate 10! at compile time. Print the result when the program is run.

Discuss what limitations apply to compile-time calculations in your language.

Ada

Here's a hardcoded version: <lang ada> with Ada.Text_Io; procedure CompileTimeCalculation is

  Factorial : constant Integer := 10*9*8*7*6*5*4*3*2*1;

begin

  Ada.Text_Io.Put(Integer'Image(Factorial));

end CompileTimeCalculation; </lang> And here's a recursive function version that prints the exact same thing. <lang ada> with Ada.Text_Io; procedure CompileTimeCalculation is

  function Factorial (Int : in Integer) return Integer is
  begin
     if Int > 1 then
        return Int * Factorial(Int-1);
     else
        return 1;
     end if;
  end;
    
    Fact10 : Integer := Factorial(10);

begin

  Ada.Text_Io.Put(Integer'Image(Fact10));

end CompileTimeCalculation;</lang> Since I don't know anything about inspecting the compiled files, I'm assuming that the numbers are being computed at compile time because of the way that ada programs are structured. If someone could confirm this...

C++

This is called Template metaprogramming. In fact, templates in C++ are Turing-complete, making deciding whether a program will compile undecidable. <lang cpp>#include <iostream>

template<int i> struct Fac {

   static const int result = i * Fac<i-1>::result;

};

template<> struct Fac<1> {

   static const int result = 1;

};

int main() {

   std::cout << "10! = " << Fac<10>::result << "\n";
   return 0;

}</lang>

Compile-time calculations in C++ look quite different from normal code. We can only use templates, type definitions and a subset of integer arithmetic. It is not possible to use iteration. C++ compile-time programs are similar to programs in pure functional programming languages, albeit with a peculiar syntax.

D

In D (here V.2) many functions can be run at compile time too: <lang d>import std.stdio: writeln;

long fact(long x) {

   long result = 1;
   foreach (i; 2 .. x+1)
       result *= i;
   return result;

}

void main() {

   enum fact10 = fact(10); // enum is D2's word for "constant symbol"
   writeln(fact10);

}</lang>

Common Lisp

Assuming a definition from Factorial function#Common Lisp:

<lang lisp>(defmacro ct-factorial (n)

 (factorial n))

...

(print (ct-factorial 10))</lang>

The factorial function must be defined before any use of the ct-factorial macro is evaluated or compiled.

If the data resulting from the compile-time calculation is not necessarily a number or other self-evaluating object, as it is in the factorial case, then the macro must quote it to avoid it being interpreted as code (a form):

<lang lisp>(defmacro ct-factorial (n)

 `(quote ,(factorial n)))

or, equivalently,

(defmacro ct-factorial (n)

 `',(factorial n))</lang>

It is also possible to have a value computed at load time, when the code is loaded into the process, rather than at compile time; this is useful if the value to be computed contains objects that do not yet exist at compile time, or the value might vary due to properties which might be different while yet using the same compiled program (e.g. pathnames), but it is still constant for one execution of the program:

<lang lisp>(print (load-time-value (factorial 10)))</lang>

Further it's also possible to have the value computed at read time using the read macro #. .

<lang lisp>(print (#. (factorial 10)))</lang>

Factor

Technically, this calculation happens at parse-time, before any compilation takes place. Calculating factorial at compile-time is not useful in Factor.

<lang factor>: factorial ( n -- n! ) [1,b] product ;

CONSTANT: 10-factorial $[ 10 factorial ]</lang>

Forth

During a word definition, you can drop out of the compilation state with [ and go back in with ]. (This is where the naming conventions for [CHAR] and ['] come from.) There are several flavors of LITERAL for compiling the result into the word.

<lang forth>: fac ( n -- n! ) 1 swap 1+ 2 max 2 ?do i * loop ;

main ." 10! = " [ 10 fac ] literal . ;

see main

main

 .\" 10! = " 3628800 . ; ok</lang>

Outside of a word definition, it's fuzzy. If the following code is itself followed by a test and output, and is run in a script, then the construction of the bignum array (and the perhaps native-code compilation of more) happens at runtime. If the following code is followed by a command that creates an executable, the array will not be rebuilt on each run.

more ( "digits" -- ) \ store "1234" as 1 c, 2 c, 3 c, 4 c,

 parse-word bounds ?do
   i c@ [char] 0 - c,
 loop ;

create bignum more 73167176531330624919225119674426574742355349194934 more 96983520312774506326239578318016984801869478851843 ...</lang>

J

J is an interpreter, and not a compiler, so could be said to not have any "compile time". Nevertheless, J tacit programs are stored using an internal representation -- the program is parsed once, well before it is used.

Thus, a program which prints 10 factorial:

<lang J>pf10=: smoutput bind (!10)</lang>

When the definition of pf10 is examined, it contains the value 3628800. J has several ways of representing tacit programs. Here all five of them are presented for this program (the last two happen to look identical for this trivial case):

<lang J> 9!:3]1 2 4 5 6

  pf10

┌───────────────────────────────────────┐ │┌─┬───────────────────────────────────┐│ ││@│┌────────┬────────────────────────┐││ ││ ││smoutput│┌─┬────────────────────┐│││ ││ ││ ││"│┌────────────┬─────┐││││ ││ ││ ││ ││┌─┬────────┐│┌─┬─┐│││││ ││ ││ ││ │││0│3.6288e6│││0│_││││││ ││ ││ ││ ││└─┴────────┘│└─┴─┘│││││ ││ ││ ││ │└────────────┴─────┘││││ ││ ││ │└─┴────────────────────┘│││ ││ │└────────┴────────────────────────┘││ │└─┴───────────────────────────────────┘│ └───────────────────────────────────────┘ ┌────────┬─┬──────────────┐ │smoutput│@│┌────────┬─┬─┐│ │ │ ││3.6288e6│"│_││ │ │ │└────────┴─┴─┘│ └────────┴─┴──────────────┘

     ┌─ smoutput

── @ ─┤ ┌─ 3628800

     └─ " ──────┴─ _

smoutput@(3628800"_) smoutput@(3628800"_)</lang>

Finally, when this program is run, it displays this number:

Objeck

Objeck will fold constants at compiler time as long as the -s2 or -s3 compiler switches are enabled.

bundle Default {

 class CompileTime {
   function : Main(args : String[]) ~ Nil {
     (10*9*8*7*6*5*4*3*2*1)->PrintLine();
   }
 }

} </lang>

OCaml

OCaml does not calculate operations that involve functions calls, as for example factorial 10, but OCaml does calculate simple mathematical operations at compile-time, for example in the code below (24 * 60 * 60) will be replaced by its result 86400.

<lang ocaml>let days_to_seconds n =

 let conv = 24 * 60 * 60 in
 (n * conv)

</lang>

It is easy to verify this using the argument -S to keep the intermediate assembly file:

ocamlopt -S sec.ml 
grep 86400 sec.s
        imull   $86400, %eax

If you wish to verify this property in your own projects, you have to know that integer values most often have their OCaml internal representation in the assembly, which for an integer x its OCaml internal representation will be (((x) << 1) + 1). So for example if we modify the previous code for:

<lang ocaml>let conv = 24 * 60 * 60

let days_to_seconds n =

 (n * conv)

</lang>

# (24 * 60 * 60) lsl 1 + 1 ;;
- : int = 172801

grep 172801 sec.s
        movl    $172801, camlSec

Oz

<lang oz>functor import

  System Application

prepare

  fun {Fac N}
     {FoldL {List.number 1 N 1} Number.'*' 1}
  end
  Fac10 = {Fac 10}

define

  {System.showInfo "10! = "#Fac10}
  {Application.exit 0}

end</lang>

Code in the prepare section of a functor is executed at compile time. External modules that are used in this code must be imported with a require statement (not shown in this example). Such external functors must have been compiled before the current functor is compiled (ozmake will automatically take care of this).

It is possible to export variables that are defined in the prepare statement. However, such variables must not be stateful entities, e.g. it is not possible to export a cell that was defined at compile time.

Pascal

All the variants of pascal have always been able to calculate the values of constants at compile time as long as the values can be resolved.

<lang pascal> program in out;

const

X = 10*9*8*7*6*5*4*3*2*1 ;

begin

writeln(x);

end; </lang>

Perl

There are few limits on code you can put in BEGIN blocks, which are executed at compile-time. Unfortunately, you can't in general save the compiled form of a program to run later. Instead, perl recompiles your program every time you run it.

<lang perl>my $tenfactorial; print "$tenfactorial\n";

BEGIN

  {$tenfactorial = 1;
   $tenfactorial *= $_ foreach 1 .. 10;}</lang>

Note however that all constant folding is done at compile time, so this actually does the factorial at compile time.

<lang perl>my $tenfactorial = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2;</lang>

Perl 6

Works with: pugs

<lang perl6>constant $tenfact = [*] 2..10; say $tenfact; </lang>

Like Perl 5, we also have a BEGIN block, but it also works to introduce a blockless statement, the value of which will be stored up to be used in the surrounding expression at run time:

<lang perl6> say(BEGIN [*] 2..10);</lang>

PicoLisp

The PicoLisp "compiler" is the so-called "reader", which converts the human-readable source code into nested internal pointer structures. When it runs, arbitrary expressions can be executed with the backqoute and tilde operators (read macros). <lang PicoLisp>(de fact (N)

  (apply * (range 1 N)) )

(de foo ()

  (prinl "The value of fact(10) is " `(fact 10)) )</lang>

Output:

: (pp 'foo)  # Pretty-print the function
(de foo NIL
   (prinl "The value of fact(10) is " 3628800) )
-> foo

: (foo)  # Execute it
The value of fact(10) is 3628800
-> 3628800

PL/I

<lang PL/I> /* Factorials using the pre-processor. */ test: procedure options (main);

%factorial: procedure (N) returns (fixed);

  declare N fixed;
  declare (i, k) fixed;

  k = 1;
  do i = 2 to N;
     k = k*i;
  end;
  return (k);

%end factorial;

%activate factorial;

  declare (x, y) fixed decimal;
  x = factorial (4);
  put ('factorial 4  is ', x);
  y = factorial (6);
  put skip list ('factorial 6 is ', y);

end test; </lang>

Output from the pre-processor:

<lang> /* Factorials using the pre-processor. */ test: procedure options (main);

  declare (x, y) fixed decimal;
  x =       24;
  put ('factorial 4  is ', x);
  y =      720;
  put skip list ('factorial 6 is ', y);

end test; </lang>

Execution results:

<lang> factorial 4 is 24 factorial 6 is 720 </lang>

PureBasic

PureBasic will do most calculation during compiling, e.g. <lang PureBasic>a=1*2*3*4*5*6*7*8*9*10</lang> could on a x86 be complied to

MOV    dword [v_a],3628800

Ruby

Assuming a definition from Factorial function#Ruby: <lang Ruby> puts factorial(10) </lang>

Tcl

In Tcl, compilation happens dynamically when required rather than being a separate step. That said, it is possible to use the language's introspection engine to discover what code has been compiled to, making it easy to show that known-constant expressions are compiled to their results. Generating the expression to compile is then simple enough.

Works with: Tcl version 8.5

<lang tcl>proc makeFacExpr n {

   set exp 1
   for {set i 2} {$i <= $n} {incr i} {
       append exp " * $i"
   }
   return "expr \{$exp\}"

} eval [makeFacExpr 10]</lang> How to show that the results were compiled? Like this: <lang tcl>% tcl::unsupported::disassemble script [makeFacExpr 10] ByteCode 0x0x4de10, refCt 1, epoch 3, interp 0x0x31c10 (epoch 3)

 Source "expr {1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10}"
 Cmds 1, src 45, inst 3, litObjs 1, aux 0, stkDepth 1, code/src 0.00
 Commands 1:
     1: pc 0-1, src 0-44
 Command 1: "expr {1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10}"
   (0) push1 0 	# "3628800"
   (2) done

</lang> As you can see, that expression was transformed into just a push of the results (and an instruction to mark the end of the bytecode segment).

Ursala

Any user-defined or library function callable at run time can also be called at compile time and evaluated with no unusual ceremony involved. <lang Ursala>#import nat

x = factorial 10

executable&

comcal = ! (%nP x)--<></lang> some notes:

x is declared as a constant equal to ten factorial using the factorial function imported from the nat library.
%nP is a function derived from the type expression %n, for natural numbers, which takes a natural number as an argument and maps it to a list of character strings suitable for printing
The #executable& directive causes the function following to be compiled as a free standing executable transforming standard input to standard output thereby.
The -- operator represents list concatenation.
The list containing the empty string is concatenated with (%nP x) so that the output will be terminated with a line break.
The ! operator makes a constant function of its operand, so that the compiled program will ignore its input and print x regardless.

Here is a bash session showing compilation of the above code into a simple command line filter, and running it as the next command.

$ fun comcal.fun
fun: writing `comcal'
$ comcal < /dev/null
3628800

Similarly to the Ocaml and Tcl solutions, we can confirm that the calculation has been performed at compile time by inspecting the object code.

$ fun comcal --decompile
main = constant <'3628800',''>