Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

OSSU > ProgrammingLanguagesA > Flashcards

ProgrammingLanguagesA Flashcards

1
Q

Syntax

A

is just how you write something

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Semantics

A

is what something that you write means

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

for variable bindings

A
  • type-check expression and extend static environment

- evaluate expression and extend dynamic environment

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

comments on ML

A

(* comment text *)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

variables on ML

A

val r = 4
(* static environment: r : int )
( dynamic environment: r –> 4 *)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

conditions on ML

A

val abs_of_z = if z < 0 then 0 - z else z;
(* static environment: abs_of_z–>int, z–>int )
( dynamic environment: abs_of_z–>70, z–>70 *)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

VALUES

A
  • all values are expressions
  • not all expressions are values
  • every value “evaluates to itself” in “zero steps”
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

conditions syntax and type-checking

A

if e1 then e2 else e3
where if, then, else - keywords and e1, e2, e3 - subexpressions
Type-checking:
e1 must have type bool,
e2 and e3 - may be any of type but both should have same type
Evaluation rules:
first evaluate e1 to a value call it v1
if its true - evaluate e2
else - evaluate e3

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

REPL

A

read eval print loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Shadowing

A

Это когда одна переменная переобъявляется заново
val a = 5
val b = a * 10
val a = 10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Example: function binding

A

fun pow (x:int, y:int) =
if y=0
then 1
else x * pow(x, y-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

FUNCTION

A

Syntax:
- fun x0(x1: t1, …, xn : tn) = e
Evaluation: A function is a value!(No evaluation yet)
- adds x0 to environment
- function call semantics also will also allow recursion
Type-checking:
- adds binding x0 : (t1 * … * tn) -> t if:
- can type-check body e to have type t in the static environment containing:
“Enclosing” static environment (earlier bindings)
x1 : t1, …, xn : tn (arguments with their types)
x0 : (t1 * … * tn)-> tn ( for recursion)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Tuples create

A 
Syntax:
(e1,e2)
Evaluation:
Evaluate e1 to v1 and e2 to v2; result is(v1, v2)
- A pair of values is a value
Type-checking:
if e1 has type ta and e2 has type tb, then the pair expression has type ta * tb
- A new kind of type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Tuples access

A

Syntax:
#1 e and #2 e
Evaluation:
Evaluate e to a pair of values and return first or second piece
- Example: if e is a variable x, then look up x in environment
Type-checking:
if e has type ta * tb, then #1 e has type ta and #2 e has type tb

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Building lists

A

The empty list is a value:
[]
In general, a list of values is a value; elements separated by commas:
[v1, v2, v3,…,vn]
if e1 evaluates to v and e2 evaluates to a list [v1, …, vn], then e1::e2 evaluated to [v, …, vn]
e1::e2 (* pronounced cons *)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Accessing lists

A

null e evaluates to true if and only if e evaluates to []
if e evaluates to [v1, v2, …, vn] then hd e evaluates to v1
- ( raise exception if e evaluates to [])
if e evaluates to [v1, v2, …, vn] then tl e evaluates to [v2, …, vn]
- ( raise exception if e evaluates to [])
- Notice - result is a list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Type-checking list operations

A

For any type t, the type t list describes lists where all elements have type t
So [] list can have type t list list of any type
- SML uses type ‘a list to indicate this

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

List functions

A

fun sum_list(xs : int list) =
if null xs
then 0
else hd xs + sum_list(tl xs)

fun countdown(x : int) =
   if x=0
   then []
   else x :: countdown(x-1)

fun append(xs : int list, ys : int list) =
if null xs
then ys
else (hd xs) :: (append((tl xs), ys))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Let expressions

A

Syntax:
let b1 b2 … bn in e end
each bi is a binding and e is any expression
Type-checking:
Type-check each bi and e in a static environment that includes the previous bindings. Type of whole let-expression is the type of e
Evaluation:
Evaluate each bi and e in a dynamic environment that includes the previous bindings. Result of whole let-expression is result of evaluating e

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Nested Functions

A 
fun countup_from1(x : int) = 
   let
      fun count(from : int, to : int) =
         if from=to
         then to::[]
         else from :: count(from+1, to)
   in
      count(1,x)
   end
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Options

A 
fun max1(xs : int list) = 
   if null xs
   then NONE
   else 
      let val tl_ans = max1(tl xs)
      in if isSome tl_ans andalso valof tl_ans > hd xs
          then tl_ans
          else SOME (hd xs)
      end
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Boolean operations

A

e1 andalso e2
e1 orelse e2
not e1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Comparison operations

A

= <> > < >= <=

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Compound types

A

one of, each of, selfreference

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Records

A 
val x = {bar=(3,true),baz=(false,9),foo=8}
#bar x
#bi x -> TypeError
26
Q

Tuples are just

A

syntactic sugar for records

27
Q

Datatype binding

A

datatype mytype = TwoInts of int * int | Str of string

1) adds a new type mytype
2) adds constructors to the environment: TwoInts, Str
3) constructor is a function that makes values of the new type

Example
datatype id = StudentNum of int
| Name of string * (string option) * string

28
Q

Using datatypes

A

1) Check what variant it is

2) Extract the data

29
Q

Case expressions

A 
fun f x = 
    case x of 
              Pizza => 3
            | Str s => 8
            | TwoInts(i1, i2) => i1 + i2
30
Q

enumerations in datatypes

A

datatype suit = Club | Diamond | Heart | Spade

datatype rank = Jack | Queen | King | Ace | Num of int

31
Q

Expression trees

A

datatype exp = Constant of int
| Negate of exp
| Add of exp * exp
| Multiply of exp * exp

Usage:
Add (Constant(10), Negate(Constant 4))

fun eval e =
case e of
Constant i => i
| Negate e2 => ~ (eval e2)
| Add(e1,e2) => (eval e1) + (eval e2)
| Multiply(e1,e2) => (eval e1) * (eval e2)

32
Q

Type synonim

A

type aname = t

33
Q

Recursive datatypes

A

datatype my_int_list = Empty | Cons of int * my_int_list

val x = Cons(4, Cons(23, Cons(1988,Empty)))

34
Q

Options are datatypes

A

fun inc_or_zero intoption =
case intoption of
NONE => 0
| SOME i => i + 1

35
Q

null

A

fun mystery x =
case x of
[] => true
x::xs => false

36
Q

polymorphic datatypes

A

datatype a option = NONE | SOME of a
datatype a mylist = Empty | Cons of a * a mylist datatype (a,b) tree = Node of a * (a,b) tree * (a,b) tree | Leaf of `b

fun num_leaves tr =
case tr of
Leaf i => 1
| Node(i,lft,rgt) => num_leaves lft + num_leaves rgt

37
Q

Pattern matching

A

fun sum_triple triple =
case triple of
(x, y, z) => x + y + z

fun full_name r =
case r of
{first=x, middle=y, last=z} => x ^ “ “ ^ y ^ “ “ ^ z

38
Q

Function-argument pattern

A 
fun sum_triple(x, y, z) =
    x + y + z

fun full_name{first=x,middle=y,last=z} =
x ^ “ “ ^ y ^ “ “ ^ z

39
Q

“Zero arguments” is a

A

unit pattern () matching the unit value

40
Q

Unexpected polymorphism

A 
(* int * 'a * int -> int *)
fun partial_sum(x,y,z) =
   x + z
41
Q

Polymorphic and Equality types

A 
(* 'a list * 'a list -> 'a list *)
fun append(xs,ys) =
    case xs of
        [] => xs
      | x::xs' => x :: append(xs', ys)
(* ''a list * ''a list -> string *)
fun same_thing(x, y) =
    if x=y then "yes" else "no
42
Q

Fun patterns

A

fun eval(Constant i) = i
| eval(Negate e2) = ~ (eval e2)
| eval(Add(e1,e2)) = (eval e1) + (eval e2)
| eval(Multiply(e1,e2)) = (eval e1) * (eval e2)

just syntactic sugar for case expression

43
Q

Exceptions

A 
exception MyException
exception MyExceptionTwo of int * int
e1 handle p => e2
fun hd xs =
    case xs of
        [] => raise List.Empty
      | x::_ => x
44
Q

Tail recursion example

A 
fun fact n = 
    let fun aux(n,acc) = 
        if n=0
        then acc
        else aux(n-1, acc*n)
    in
        aux(n, 1)
    end
45
Q 
What is the result of evaluating this expression, in SML/NJ?
#h {f=3,g=12}
A

TypeError
This will result in a type error, as the type checker can tell statically that there is no field named h within a record with field names f and g.

46
Q

Фу́нкция вы́сшего поря́дка

A

функция, принимающая в качестве аргументов другие функции или возвращающая другую функцию в качестве результата. Основная идея состоит в том, что функции имеют тот же статус, что и другие объекты данных.

47
Q

Замыкание

A

функция первого класса, в теле которой присутствуют ссылки на переменные, объявленные вне тела этой функции в окружающем коде и не являющиеся её параметрами. Говоря другим языком, замыкание — функция, которая ссылается на свободные переменные в своей области видимости.

48
Q

Пример передачи в функцию функцию-аргумент

A 
fun double x = x + x
fun n_times(f,n,x) =
	if n=0
	then x
	else f (n_times(f, n-1, x))

n_times(double, 1, 1)

49
Q

Anonymous functions

A 
fun triple_n_times(n, x) =
    n_times(fn x => 3 * x, n, x)

(* minuses => cannot call recursively *)

50
Q

Lexical scope(example)

A 
(* 1 *) val x = 1
		(* x maps to 1 *)
(* 2 *) fun f y = x + y
		(* f maps to a function that adds 1 to its argument *)
(* 3 *) val x = 2
		(* x maps to 2 *)
(* 4 *) val y = 3
		(* y maps to 3 *)
(* 5 *) val z = f (x + y) (* call the function defined on line 2 with 5 *)
		(* z maps to 6 *)
51
Q

Closures and recomputation

A 
(* Not bad *)
fun allShorterThan1(xs, s) =
	filter(fn x => String.size x < String.size s, xs)
(* Good - i not evaluate for every element *)
fun allShorterThan2(xs, s) =
	let 
		val i = String.size s
	in
		filter(fn x => String.size x < i, xs)
	end
52
Q

function composition

A

fun compose(f,g) = fn x => f(g, x)

infix !>
fun x !> f = f x

fun sqrt_of_abs i = i !> abs !> Real.fromInt !> Math.sqrt

53
Q

currying

A

val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x;

sorted3 1 2 3 (* return true *)

54
Q

Mutable references

A 
t ref (* where t is type *)
ref e (* to create a reference with initial contents e *)
e1 := e2 (* to update contents *)
!e (* to retrieve contents *)
55
Q

Type inference

A

правила как выводится тип передаваемого принимаемого значения

56
Q

Mutual Recursion

A

Allow f to call g and g to call f

57
Q

Mutually recursive functions

A

fun f1 p1 = e1
and f2 p2 = e2
and f3 p3 = e3

58
Q

Mutually recursive datatype bindings

A

datatype t1 = …
and t2 = …
and t3 = …

59
Q

Namespace management

A 
structure MyMathLib = 
struct
	fun fact x =
		if x=0
		then 1
		else x * fact(x-1)
	val half_pi = Math.pi / 2.0
	fun doubler y = y + y
end

val pi = MyMathLib.half_pi + MyMathLib.half_pi
val twenty_eight = MyMathLib.doubler 14

60
Q

Example of State Machines

A 
fun match xs =
	let 
		fun s_need_one xs =
			let 
				fun s_need_two xs =
					case xs of 
						[] => false
					|	2::xs' => s_need_one xs'
					|	_ => false
			in
				case xs of
					[] => true
				|	1::xs' => s_need_two xs'
				|	_ => false
			end
	in
		s_need_one xs
	end

OSSU (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions