2.3. Semantics

This chapter specifies the semantics of Kink programs as transformation into abstract instructions of the abstract stack machine. The transformation is comprised of the two steps desugaring and translation.

desugaring

Transformation of a program into the desugared form.

desugared form

The program which is the result of desugaring of another program.

translation

Transformation of the desugared form of the program into a sequence of abstract instructions.

The following is an example program.

:foo <- {
  :Vec = [10 20 30]
  Vec.each{(:E) bar(E) }
}

The program above is desugared as follows.

\binding:foo.op_store({
  { [\binding:Vec].op_store(\binding._Args)
    \binding.Vec.each({
      [\binding:E].op_store(\binding._Args)
      \binding.bar[()](\binding.E)
    })
  }.call(() [[10 20 30]])
})

Then translated into abstract instructions as follows.

(binding)
(varref "foo")
(dup)
(load "op_store")
(dup)
(checkfun)
(flip)
(emptyvec)
(binding)
(fun
  (enclosingbinding)
  (clonebinding)
  (dup)
  (setbinding)
  (storerecvargs)

  (binding)
  (fun
    (enclosingbinding)
    (clonebinding)
    (dup)
    (setbinding)
    (storerecvargs)

    (emptyvec)
    (binding)
    (varref "Vec")
    (add)
    (dup)
    (load "op_store")
    (dup)
    (checkfun)
    (flip)
    (emptyvec)
    (binding)
    (load "_Args")
    (add)
    (call "op_store")
    (remove)

    (binding)
    (load "Vec")
    (dup)
    (load "each")
    (dup)
    (checkfun)
    (flip)
    (emptyvec)

    (binding)
    (fun
      (enclosingbinding)
      (clonebinding)
      (dup)
      (setbinding)
      (storerecvargs)

      (emptyvec)
      (binding)
      (varref "E")
      (add)
      (dup)
      (load "op_store")
      (dup)
      (checkfun)
      (flip)
      (emptyvec)
      (binding)
      (load "_Args")
      (add)
      (call "op_store")
      (binding)
      (load "bar")
      (dup)
      (checkfun)
      (nada)
      (emptyvec)
      (binding)
      (load "E")
      (add)
      (call "bar")
    )
    (add)
    (call "each")
  )
  (dup)
  (load "call")
  (dup)
  (checkfun)
  (flip)
  (emptyvec)
  (nada)
  (add)
  (emptyvec)
  (num 10)
  (add)
  (num 20)
  (add)
  (num 30)
  (add)
  (add)
  (call "call")
)
(add)
(call "op_store")

2.3.1. Desugaring

This section defines desugaring in informal style.

Programs

A Kink program is composed of zero or more toplevel expressions.

When a program is composed of expressions E1, E2, ,,, En, the program is desugared to a parentheses expression (E1 E2 ,,, En).

Let clauses

A let clause in the form E1 = E2 S, where E1 and E2 are expressions and S is a substantial_seq, is desugared to {(E1) S }.call(() [E2]).

Example program with let clauses:

:fun <- {
  :add = {(:X :Y) X + Y }
  :Sum = add(10 20)
  stdout.print_line(Sum.show)  # => 30
}

The program above is desugared to the following program.

:fun <- {
  {(:add)
    {(:Sum)
      stdout.print_line(Sum.show)
    }.call(() [add(10 20)])
  }.call(() [{(:X :Y) X + Y }])
}

Operator expressions

Operator expressions are syntactic sugar for attributional call expressions (attr_call).

Here is the list of operators.

Priority	Token type	Operators	Associativity
Lowest	store_op	<-	Non-associative
	logor_op	||	Right-associative
	logand_op	&&	Right-associative
	relation_op	==, !=, <, >, <=, >=	Non-associative
	add_op	+, -, |, ^	Left-associative
	multiply_op	*, /, //, %, &, <<, >>	Left-associative
Highest	unary_op	-, !, ~	Unary

Each operator expression is desugared as follows.

Operator expression	Desugared as
X <- Y	(X).op_store(Y)
X || Y	\binding.op_logor[()](X { Y })
X && Y	\binding.op_logand[()](X { Y })
X == Y	(X).op_eq(Y)
X != Y	\binding.op_lognot[()]((X).op_eq(Y))
X < Y	(X).op_lt(Y)
X > Y	(Y).op_lt(X)
X <= Y	op_lognot((Y).op_lt(X))
X >= Y	op_lognot((X).op_lt(Y))
X + Y	(X).op_add(Y)
X - Y	(X).op_sub(Y)
X | Y	(X).op_or(Y)
X ^ Y	(X).op_xor(Y)
X * Y	(X).op_mul(Y)
X / Y	(X).op_div(Y)
X // Y	(X).op_intdiv(Y)
X % Y	(X).op_rem(Y)
X & Y	(X).op_and(Y)
X << Y	(X).op_shl(Y)
X >> Y	(X).op_shr(Y)
- U	(U).op_minus()
! U	\binding.op_lognot[()](U)
~ U	(U).op_not()

Function bodies

Formal receivers and formal arguments in function bodies (fun_body) are syntactic sugar for attributional call expressions (attr_call).

Function bodies are categorized in four groups: with or without the formal receiver, and with or without the formal arguments. The following table describes how each group is desugared. In the table, C denotes a sequence (seq), E denotes an expression, and VB denotes a vector body (vec_body),

Formal receiver	Formal arguments	Seq after formal receiver and arguments	Desugared as
∅	∅	C	C
∅	(VB)	C	[VB].op_store(\binding._Args) (C)
[E]	∅	C	(E).op_store(\binding._Recv) (C)
[E]	(VB)	C	(E).op_store(\binding._Recv) [VB].op_store(\binding._Args) (C)

Therefore, fun1 and fun2 in the following example are equivalent.

:fun1 <- {[:Self](:X :Y :Z)
  'result'
}

:fun2 <- {
  :Self <- _Recv
  [:X :Y :Z] <- _Args
  'result'
}

Actual arguments vectors

Actual arguments vectors (args) are categorized in two groups: those with parentheses (paren_args) and without parentheses.

The following table describes how each group of actual arguments vectors are desugared. In the table, E1, E2, ... En denotes zero or more elements producers (elements_producer). FB1, FB2, ... FBm denotes function bodies (fun_body) of zero or more function arguments (fun_arg) in the original form. or zero or more functions (fun) in the desugared form.

Original form	Desugared as
(E1 E2 ‹...snip...› En){ FB1 }{ FB2 }‹...snip...›{ FBm }	(E1 E2 ‹...snip...› En { FB1 } { FB2 } ‹...snip...› { FBm })
{ FB1 }{ FB2 }‹...snip...›{ FBm }	({ FB1 } { FB2 } ‹...snip...› { FBm })

Therefore, in the following example, each pair of invocations of show, if and fold are mutually equivalent.

Num.show
Num.show()

if(Str.empty?){ stdout.print_line('empty') }
if(Str.empty? { stdout.print_line('empty') })

Vec.fold(0){(:X :Y) X + Y}
Vec.fold(0 {(:X :Y) X + Y})

Local load expressions

Local load expressions (local_load) are syntactic sugar for attributional load expressions (attr_load) of the local binding. The local load expression in the form Noun is desugared to \binding.Noun. The local load expression in the form $verb is desugared to \binding$verb.

In the following example, fun1 and fun2 are equivalent, thus the invocations of both functions output 42 to the standard output.

:fun1 <- {(:Val :output)
  :output_copy = $output
  output_copy(Val)
}
fun1(42 {(:X) stdout.print_line(X.show) })  # => 42

:fun2 <- {(:Val :output)
  :output_copy = \binding$output
  output_copy(\binding.Val)
}
fun2(42 {(:X) stdout.print_line(\binding.X.show) })  # => 42

Local reference expressions

Local reference expressions (local_varref) are syntactic sugar for attributional reference expressions (attr_varref) of the local binding. The local reference expression in the form :Noun is desugared to \binding:Noun. The local reference expression in the form :verb is desugared to \binding:verb.

In the following example, fun1 and fun2 are equivalent, thus the invocations of both functions output 42 to the standard output.

:fun1 <- {
  :Val = 42
  :output = {(:X) stdout.print_line(X.show) }
  output(Val)
}
fun1  # => 42

\binding:fun2 <- {
  \binding:Val = 42
  \binding:output = {(\binding:X) stdout.print_line(X.show) }
  output(Val)
}
fun2  # => 42

Local call expressions

Local call expressions (local_call) are syntactic sugar for attributional call expressions (attr_call) of functions owned by the local binding.

The local call expression in the form fun(VB) is desugared to \binding.fun[()](VB), where VB is a vector body.

The local call expression in the form fun[R](VB) is desugared to \binding.fun[R](VB), where R is an expression and VB is a vector body.

In the following example, fun1 and fun2 are equivalent, thus the invocations of both functions output hello world to the standard output.

:print_arg <- {(:Arg)
  stdout.print_line(Arg.show)
}

:print_recv <- {[:R]
  stdout.print_line(R.show)
}

:fun1 <- {
  print_arg('hello ')
  print_recv['world']
}
fun1  # => hello world

:fun2 <- {
  \binding.print_arg[()]('hello ')
  \binding.print_recv['world']()
}
fun2  # => hello world

2.3.2. Translation

This section defines translation as transformation from the desugared form of the program into abstract instruction <abstract instruction>.

Programs

In the desugared form, a program is composed of a single parentheses expression.

Translation of a program P to a sequence of abstract instructions tprogram(P) is defined as follows.

Composition of P	Where	tprogram(P)
T	T : paren	«tparen(T)»

Sequences without let clauses

In the desguared form, thus without let clauses, a sequence (seq) is a sequence of zero ore more expressions. If the sequence consists of no expressions, it produces the value () (called “nada”). If the sequence consists of one or more expressions, it evaluates the expressions in the order they appears, and produces the result of the last expression.

Grammatically, a sequence is composed of either empty or a substantial sequence (substantial_seq). A substantial sequence is composed of a single expression, or a pair of an expression and a substantial sequence.

Translation of a sequence S to an instruction sequence tseq(S) is defined as follows.

Composition of S	Where	tseq(S)
∅	∅ : empty	(nada)
SS	SS : substantial_seq	«tsubstantial_seq(SS)»

Translation of a substantial sequence SS to an instruction sequence tsubstantial_seq(SS) is defined as follows.

Composition of SS	Where	tsubstantial_seq(SS)
E	E : expression	«texpression(E)»
E SSS	E : expression SSS : substantial_seq	«texpression(E)» (remove) «tsubstantial_seq(SSS)»

In the following example, fun1 outputs the result of an empty sequence, which is nada. fun2 outputs the result of a sequence comprising three expressions 'foo', 'bar' and 'baz'; the result is 'baz'.

:fun1 <- {
  :Result = ()
  stdout.print_line(Result.repr)  # => nada
}
fun1

:fun2 <- {
  :Result = ('foo' 'bar' 'baz')
  stdout.print_line(Result.repr)  # => "baz"
}
fun2

Expressions

In the normalized form, an expression can be eventually reduced to a single primary expression (primary).

Therefore, translation of an expression E to an instruction sequence texpression(E) is defined as follows.

Composition of E	Where	texpression(E)
P	P : primary	«tprimary(P)»

Primary expressions

Translation of a primary expression P to an instruction sequence tprimary(P) is defined as follows.

Composition of P	Where	tprimary(P)
N	N : num	«tnum(N)»
S	S : str	«tstr(S)»
CE	CE : binding	«tbinding(CE)»
P	P : paren	«tparen(P)»
V	V : vec	«tvec(V)»
F	F : fun	«tfun(F)»
D	D : attr_load	«tattr_load(D)»
R	R : attr_varref	«tattr_varref(R)»
AC	AC : attr_call	«tattr_call(AC)»

Number expressions

A number expression (num) produces a number value.

Translation of a number expression N to an instruction tnum(N) is defined as follows.

Composition of N	Where	tnum(N)
NN	NN : NUM	(num «NN as num»)

In the following example, fun1 outputs the result of the integer number expression 42. fun2 outputs the result of the decimal number expression 3.14.

:fun1 <- {
  :Result = 42
  stdout.print_line(Result.show)  # => 42
}
fun1

:fun2 <- {
  :Result = 3.14
  stdout.print_line(Result.show)  # => 3.14
}
fun2

String expressions

A string expression (str) produces a string value.

Translation of a string expression S to an instruction tstr(S) is defined as follows.

Composition of S	Where	tstr(S)
SS	SS : STRING	(str «SS as str»)

The following example outputs the result of the string expression 'foo'.

:Result <- 'foo'
stdout.print_line(Result)  # => foo

Binding expressions

A binding expression produces the current binding.

Translation of a binding expression CE to an instruction tbinding(CE) is defined as follows.

Composition of CE	tbinding(CE)
'\binding'	(binding)

The following example outputs the value of the variable Val of the current binding, namely, the local variable Val.

:Val <- 42
stdout.print_line(\binding.Val.show)  # => 42

Parentheses expressions

A pair of parentheses is used to enclose a sequence as a primary expression.

Translation of a parentheses expression P to an instruction sequence tparen(P) is defined as follows.

Composition of P	Where	tparen(P)
OPENPAREN S ')'	S : seq	«tseq(S)»
WS_OPENPAREN S ')'	S : seq	«tseq(S)»

In the following example, the addition 2 + 4 is calculated before the mulliplication.

:Val <- 7 * (2 + 4)
stdout.print_line(Val.show)  # => 42

Vector expressions

A vector expression is used to make a vector.

Translation of a vector expression V to an instruction sequence tvec(V) is defined as follows.

Composition of V	Where	tvec(V)
OPENBRACKET VB ']'	VB : vec_body	(emptyvec) «tvec_body(VB)»
WS_OPENBRACKET VB ']'	VB : vec_body	(emptyvec) «tvec_body(VB)»

Vector bodies

A vector body (vec_body) is used in vector expressions and actual arguments in function calls (and formal arguments in not normalized forms) to produce elements of vectors.

Translation of a vector body VB to an instruction sequence tvec_body(VB) is defined as follows.

Composition of VB	Where	tvec_body(VB)
∅	∅ : empty	∅
EP VVB	EP : elements_producer VVB : vec_body	«telements_producer(EP)» «tvec_body(VVB)»

In the following example, the vector Spreaded is expanded in the second vector literal.

:Spreaded <- [42 3.14]
:Vec <- ['foo' ...Spreaded 'bar']
stdout.print_line(Vec.repr)  # => ["foo" 42 3.14 "bar"]

In the following example, the vector Spreaded is spreaded in the arguments vector for the function call of fun.

:fun <- {
  stdout.print_line(_Args.repr)
}
:Spreaded <- [42 3.14]
fun('foo' ...Spreaded 'bar')  # => ["foo" 42 3.14 "bar"]

Elements producers

An elements producer (elements_producer) is a content of vector bodies.

Translation of an element producer EP to an instruction sequence telements_producer(EP) is defined as follows.

Composition of EP	Where	telements_producer(EP)
E	E : expression	«texpression(E)» (add)
'...' E	E : expression	«texpression(E)» (concat)

Function expressions

A function expression (fun) produces a function value.

Translation of a function expression F to an instruction sequence tfun(F) is defined as follows.

Composition of F	Where	tfun(F)
OPENBRACE S '}'	S : seq	(binding) (fun (enclosingbinding) (clonebinding) (dup) (setbinding) (storerecvargs) «tseq(S)»)
WS_OPENBRACE S '}'	S : seq	(binding) (fun (enclosingbinding) (clonebinding) (dup) (setbinding) (storerecvargs) «tseq(S)»)

Attributional load expressions

An attributional load expression (attr_load) loads a variable of the owner.

Translation of an attributional load expression D to an instruction sequence tattr_load(D) is defined as follows.

Composition of D	Where	tattr_load(D)
P '.' N	P : primary N : NOUN	«tprimary(P)» (load «N as str»)
P DOLLAR V	P : primary V : VERB	«tprimary(E)» (load «V as str»)

Attributional reference expressions

An attributional reference expression (attr_varref) produces a variable reference of the owner.

Translation of an attributional reference expression R to an instruction sequence tattr_varref(R) is defined as follows.

Composition of R	Where	tattr_varref(R)
P COLON N	P : primary N : NOUN	«tprimary(P)» (varref «N as str»)
P COLON V	P : primary V : VERB	«tprimary(P)» (varref «V as str»)

Attributional call expressions

An attributional call expression (attr_call) invokes a function.

Translation of an attributional call expression C to an instruction sequence tattr_call(C) is defined as follows.

Composition of C	Where	tattr_call(C)
P '.' V OPENBRACKET R ']' OPENPAREN VB ')'	P : primary V : VERB R : expression VB : vec_body	«tprimary(P)» (load «V as str») (dup) (checkfun) «texpression(R)» (emptyvec) «tvec_body(VB)» (call «V as str»)
P '.' V OPENPAREN VB ')'	P : primary V : VERB VB : vec_body	«tprimary(P)» (dup) (load «V as str») (dup) (checkfun) (flip) (emptyvec) «tvec_body(VB)» (call «V as str»)