spec.md

Sleepy Language Specification

Table of contents

• Sleepy Language Specification
  • Table of contents
  • Introduction
  • Syntax
  • Types
    • Bool
    • Integer
    • String
    • Lambda
  • Definitions
  • Intrinsics
    • Logical operators
    • Integer Comparisons
    • Input
    • Output
  • Examples
    • Problem 1
    • Problem 2

Introduction

Syntax

Grammar expressed in ANTLR4 notation can be found in sleepy.g4.

There are inline comments supported via ; keyword.

Types

This section explains all core types of the Sleepy Language: Integer, String and Lambda.

Bool

true
false

Integer

Integer number. It is an immutable type. Literal can be prefixed with a sign '+' or '-'. Type is written as int.

Example of valid integer literals:

 123  0  9987658754345689098765
+123  1 -9987658754345689098765
-123 -1 

Example of invalid integer literals:

-0  01  -01231
+0  001 +01231

Usage:

(eq (sum 2 2)  4)
(eq (sum 2 -2) 0)
(def a (sum a 1))

String

String is a an immutable list of characters. Type is written as string.

Example of valid strings:

"ITMO University."
"Sleepy 1.0.0 is coming!"
"" "a" "."
"Hello, World?!"

Example of invalid strings:

"lalala
oqoqq"
"
"""

Usage:

(print "Hello, CArch!")

Lambda

Lamda is a function. It is a value, so you can store it in your variable. Closures are not supported yet or maybe even would not ever due to feature of calling itself, as it is hard to come up with an idea how to capture environment.

Lambda call itself to make a recusive call using keyword self.

Last expression in labda body is return expression.

Example of valid lambdas:

(lambda (x int)   (sum x 1))
(lambda (y int z int) (sum x y))
(lambda (x int)   
  (if (eq x 1) 
    1 
    (mul x (self (sum x -1)))))

Definitions

Variable definition associates a name with a specific value. Variables are immutable and can be defined only once. But they can be redefined.

Usage:

(def x 1)
(def hello "Wake up, Sleepy")
(def is_even (lambda (n int) 
  (eq (rem n 2) 0)))
(def inc (lambda (n int) (sum n 1)))

Intrinsics

Intrinsics special are functions that are implemented via compiler.

Logical operators

(not false)     ; not: (Bool) -> Bool
(or true false) ; or: (Bool, Bool) -> Bool
(and true true) ; and: (Bool, Bool) -> Bool

Integer Comparisons

(eq 4 4) ; eq: (T, U) -> Bool
(lt 1 2) ; lt: (T, U) -> Bool

Input

(def a (input)) ; input: () -> Integer

Output

(print "Hello, World!") ; print: (String) -> Integer

Examples

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

(def result (
  (lambda (number int) 
    (sum 
      (if (eq (rem number 3)) 
        number 
        (if (eq (rem number 5))
          number 
          0)))
      (if (not (eq number 0))
        (self (sum number -1))
        0))
  (sum 1000 -1)))

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

(def fibb (lambda (n int)
  (if (or (eq n 0) (eq n 1))
    1
    (sum 
      (self (sum n -1))
      (self (sum n -2))))))

(def iseven (lambda (x int) 
  (eq (rem x 2) 0)))

(def sumfrom (lambda (n int) 
  (def current 
    (fibb n))
  (def addition
    (if (iseven current) current 0))
  (def hasnext 
    (lt current 4000000000))
  (def next 
    (if hasnext (self (sum n +1)) 0))
  (sum next addition)))

(def x (input))
(def r (sumfrom x))
(print r)