CS152 Midterm Study Guide

key traits of scheme

functional, dynamically typed, minimal, lists

what is scheme?

functional and minimal language; dialect of Lisp

Lisp

list processing language

racket simple data types

booleans, numbers, characters

racket compunds data types

strings, pairs, lists

s-expressions

simple and compound data types

cons

makes a pair from a obj and a list

append

puts together 2 lists

car

get head of list

cdr

get tail of list

list

a pair made of "head of list" and "tail of list"

head of list

first obj in list

tail of list

list containing everything except head

keyword define

defines a global variable

keyword displayln

displays value

let*

allows previous variable definitions to be used in following variable definitions

letrec

allows later variable definitions to use previous variable definitions

lamdas can be used like

functions

alternate format for (define square (lambda (x) (* x x)))

(define (square x) (* x x))

higher-order function

function that takes functions as arguments; returns a function as its result; dynamically construct new functions

when the second item of cons is not list, will create a pair (T/F)

T

recursion consists of

base case, recursive step

base case

when to stop

recursive step

calls function with a smaller version of the same problem

goal of recursive step

to move the problem closer to the base case

in tail recursion,

the recursive call is the last step performed before returning a value

functional languages

treat programs as mathematic functions

qualities of functional programming

functions clearly distinguish input from outputs, result depend only on input values, no assignments or loops

most important feature of functional programming

functions are first class values/objects

functions are first class values/objects

functions can be treated as any other value

referential transparency

abiility to replace an expression with its value, write code free of side-effects

packages

provide units of code

exports

specify public values

imports

specify code dependencies

keyword provide

specifies public values

keyword require

specifies code dependencies

structures

allow us to create more sophisticated data structures

keyword match

access to structure by destructuring

hash

map of key/value pairs

Scheme hashes are immutable (T/F)

T

Java lambdas only close over values, not variables (T/F)

T

supplier interface parameter and return types

none; T

consumer interface parameter and return types

T; void

biconsumer interface parameter and return type

T, U; void

predicate interface parameter and return type

T; boolean

stream API

pipeline of collection of objects and methods returned as stream

exception handling

unwinds the stack and transfers control possibly to a different function/file

setjmp

sets a "bookmark" in the code

longjmp

returns to bookmark

goto in C

allows execution to jump to any point within function

setjmp(jmp_buf env)

bookmarks point in code by saving current execution context into a buffer

longjmp(jmp_buf env, int val)

returns back to setjmp location, replaces setjmp call with given value and restores execution context

continuations

"the rest of the program"

components of continuation

return point, call stack, remainder of program

keyword call/cc

"bookmarks" location in code, saves current execution state, invokes lambda function with continuation

contracts

establishes who is to blame when something goes wrong by setting responsibilies for each party to guarantee what to expect from others

preconditions

requirements for the input

postconditions

promises for the output

holds blame for failing preconditions

caller

holds blame for failing postconditions

library

blaming

error message to indicate which file broke contract

how is type checking different from contracts?

enforcement at compile time, less flexible, and less runtime overhead

how are contracts different from type checking?

enforcement at run time, more flexible, more runtime overhead

flat contracts

simple predicates

contract combinator

function that combines contracts to make new contracts

examples of contract combinators

and/c; listof; cons/c

what is the benefit to using contracts on functions?

able to catch internal errors

what is the drawback to using contracts on functions?

repeats checking of contracts, especially in recursive functions

Programming contracts are useful for estabilishing blame when things go wrong (T/F)

T

If a precondition is not satisfied, then the library writer is at fault for any errors (T/F)

F

Contracts may only be specified on modules (T/F)

F

Specifying a contract for a function is more efficient than specifying one for a module, since it avoids repeated checks on the contract for a recursive call (T/F)

F

In Racket, the ->i operator is used to specify contracts on functions where the validity of the arguments or result depend on each other (T/F)

T

syntax

structure of a program

semantics

meaning of a program

2 aspects of a language

syntax; semantics

2 parts of syntax

lexemes or tokens; grammar

lexemes or tokens

"words" of the language

grammar

the way that words can be ordered

what does the lexer/tokenizer do?

filters out spaces and comments

what does the parser do?

filters out syntax sugar

input of lexer/tokenizer

source code

input of parser

tokens

output of lexer/tokenizer

keywords, literals, valid variables

output of parser

abstract syntax tree

types of tokens

identifiers, numbers, reserved words, special characters

AST

abstract syntax tree

use of ASTs

meaning is derived by compilers and interpreters to turn programs into actions

example of syntactic sugar

y++ => y + y

The job of a parser is to take in tokens and produce an abstract syntax tree (AST) (T/F)

T

Abstract syntax trees are sometimes called "lexemes" (T/F)

F

Tokens may be though of as the "words" of a language (T/F)

T

Once an abstract syntax tree is produced, it is only useful for evaluations by an interpreter; for efficiency, compilers typically work directly from the stream of tokens (T/F)

F

A transpiler is a compiler that translates one high-level language to another (T/F)

T

Louden & Lambert's Design Criteria

efficiency, regularity, security, extensibility

efficiency

machine efficiency, programmer efficiency, reliability

machine efficiency

tips to the compiler

programmer efficiency

writing speed, expressive, concise

reliability

code maintenance

regularity

generality, orthogonal design, uniformity