Skip to content

Instantly share code, notes, and snippets.

@Determinant
Last active August 29, 2015 14:03
Show Gist options
  • Save Determinant/cda8f040bde0bd9839b7 to your computer and use it in GitHub Desktop.
Save Determinant/cda8f040bde0bd9839b7 to your computer and use it in GitHub Desktop.

Enhanced Calculator Project

Overview

Write an S-expression calculator with following functionalities:

  • Reads the expressions from stdin and prints the output to stdout

    • Note that you should guarantee that your program only writes revelant answers to stdout without debugging/dump messages. However, you could write those messages to stderr which will be simply omitted in our final evaluation.
  • Basic calculation:

    Input: (display (* (+ 1 2) (+ 3 4)))
    Output: 21
    
    Input: (display (sin 3))
    Output: 0.141120008059867
    
  • Simple lambda functions:

    Input: (display ((lambda (x) (* x x)) 3))
    Output: 9
    Input: (display (((lambda (x) (lambda (y) (* x y))) 3) 4))
    Output: 12
    
  • Built-ins:

    • Addition, subtraction, multiplication, division
    • sin, cos, arcsin, arccos, tan, arctan, ln
    • High precision
      • Integers (decimal, binary, octal and hexadecimal)
      • Fractions
    • Numeric constants
    • Conditional and logical operator: (if, and, or)

Checkpoints

  • Phase I
    • A simple calculator which can perform basic arithmetic operations
    • Model and implement the hierarchy of different numeric types
  • Phase II
    • Conditional and logical operator support
    • High precision support
    • Lambda functions
  • Optional (depends on the progress)
    • Support for vectors and matrices
    • Better user interface

Syntax Specification

Top Level

expression
    : variable
    | number
    | boolean
    | character
    | string
    | procedure_call
    | lambda_expression
    | conditional
    | logical

Variables

variable : < any identifier that is not also a keyword>
identifier : initial subsequent* | '+' | '-'
subsequent : initial | [0-9] | '+' | '-' | '.'
keyword : 'lambda' | 'if' | 'and' | 'or'
initial
    : 'a' | 'b' | 'c' | ... | 'z'
    | '!' | '$' | '%' | '&' | '*' | '/' | ':' | '<' | '=' | '>' | '?' | '^' | '_' | '~'

Numbers

number : complex
complex
    : real
    | real @ real
    | real '+' ureal 'i'
    | real '-' ureal 'i'
    | real '+i'
    | real '-i'
    | '+' ureal 'i'
    | '-' ureal 'i'
    | '+i'
    | '-i'

real : sign ureal
sign : empty | + | -
ureal
    : uinteger | uinteger / uninteger | decimal

decimal : IEEE 754 double format
uinteger : uint_bin | uint_oct | uint_dec | uint_hex
uint_bin : '#b' [0-1]+
uint_oct : '#o' [0-7]+
uint_dec : '#d'? [0-9]+
uint_hex : '#x' [0-9a-f]+

boolean : '#t' | '#f'
character : '#\' <any character> | '#\' 'space' | '#\ 'newline'
string : '"' string_element* '"'
string_element : <any character other than " or \> | '\"' | '\\'

Operations

procedure_call : '(' operator operand* ')'
operator : expression
operand : expression

lambda_expression : '(' 'lambda' '(' variables* ')' expression+ ')'
conditional : '(' 'if' test consequence alternative ')'
test : expression
consequence : expression
alternative : expression

logical : '(' ('and' | 'or') test* ')'

Lexical Analysis (in a nutshell)

  • Tokens are separated by delimiters
  • Delimiters include '(' , ')' and blanks such that isspace returns true

Required Procedures

  • (equal? obj1 obj2)
  • (number? obj)
  • (complex? obj)
  • (real? obj)
  • (rational? obj)
  • (integer? obj)
  • (exact? z)
  • (inexact? z)
  • (= z1 z2 z3 ...)
  • (< x1 x2 x3 ...)
  • (> x1 x2 x3 ...)
  • (<= x1 x2 x3 ...)
  • (>= x1 x2 x3 ...)
  • (zero? z)
  • (positive? x)
  • (negative? x)
  • (odd? n)
  • (even? n)
  • (max x1 x2 ...)
  • (min x1 x2 ...)
  • (+ z1 ...)
  • (* z1 ...)
  • (- z1 z2)
  • (- z)
  • (- z1 z2 ...)
  • (/ z1 z2)
  • (/ z)
  • (/ z1 z2 ...)
  • (abs x)
  • (quotient n1 n2)
  • (remainder n1 n2)
  • (modulo n1 n2)
  • (gcd n1 ...)
  • (lcm n1 ...)
  • (numerator q)
  • (denominator q)
  • (floor x)
  • (ceiling x)
  • (truncate x)
  • (round x)
  • (exp z)
  • (log z)
  • (sin z)
  • (cos z)
  • (tan z)
  • (asin z)
  • (acos z)
  • (atan z)
  • (atan y x)
  • (sqrt z)
  • (expt z1 z2)
  • (make-rectangular x1 x2)
  • (make-polar x3 x4)
  • (real-part z)
  • (imag-part z)
  • (magnitude z)
  • (angle z)
  • (exact->inexact z)
  • (inexact->exact z)
  • (number->string z)
  • (number->string z radix)
  • (string->number string)
  • (string->number string radix)
  • (not obj)
  • (boolean? obj)
  • (char? obj)
  • (char=? char1 char2)
  • (char<? char1 char2)
  • (char>? char1 char2)
  • (char<=? char1 char2)
  • (char>=? char1 char2)
  • (char-ci=? char1 char2)
  • (char-ci<? char1 char2)
  • (char-ci>? char1 char2)
  • (char-ci<=? char1 char2)
  • (char-ci>=? char1 char2)
  • (char-alphabetic? char)
  • (char-numeric? char)
  • (char-whitespace? char)
  • (char-upper-case? letter)
  • (char-lower-case? letter)
  • (char->integer char)
  • (integer->char n)
  • (char-upcase char)
  • (char-downcase char)
  • (string? obj)
  • (make-string k)
  • (make-string k char)
  • (string char ...)
  • (string-length string)
  • (string-ref string k)
  • (string=? string1 string2)
  • (string-ci=? string1 string2)
  • (string<? string1 string2)
  • (string>? string1 string2)
  • (string<=? string1 string2)
  • (string>=? string1 string2)
  • (string-ci<? string1 string2)
  • (string-ci>? string1 string2)
  • (string-ci<=? string1 string2)
  • (string-ci>=? string1 string2)
  • (substring string start end)
  • (string-append string ...)
  • (string-copy string)
  • (procedure? obj)
  • (display obj)
  • (newline)

See Also

[S-expression]http://en.wikipedia.org/wiki/S-expression
[Scheme]http://en.wikipedia.org/wiki/Scheme_(programming_language)
[R5RS]http://www.schemers.org/Documents/Standards/R5RS/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment