Principles Of Programming Languages > Theory > Flashcards
Theory Flashcards
What are some aspects of programming language that influence other aspects of it?
What is the first language to introduce OO
Simula
What is the first language to formalize the concept of OO
Smalltalk
What is the difference between C++ and Objective-C?
What is the unique aspect of Earlang?
What are scripting languages?
What is the difference between procedural programming and functional programming?
What is Scheme used for? Describe its uniqueness. What is it good for?
What is the main particularity in function structure in Scheme
How do we write “x == y + 3*x + Z;” in Scheme?
How the basic types of Scheme (Boolean, Int, Nums, Chars, Vectors, Strings, Lists, Pairs) are written?
What is the difference between statements and expressions?
What does “call by value” means?
What is let used for? How?
How would a lambda function such as “x^2 + y^2” written?
What is static scope rules? What about dynamic scope rules?
What is the result of the following expression:
(let ((a 1))
(let ((f (lambda ()
(display a))))
(let ((a 2))
(f))))
1
What does it means that schema let binds in parallel?
What is the result of the following expression:
(let ((x 1)
(y 2)
(let ((x y)
(y x))))
Schema is homoiconic. What does it means?
There is no distinction between data and code
How can you add syntax to Scheme?
What does the “quote” command does in Scheme? Why do we need it?
What is the “eval” command used for in Scheme?
What is the “begin” command used for in Scheme?
What is the “define” command used for in Scheme and what is the difference from the “let” command?
How can we use define to define a function in Scheme?
How can we change the value of a variable in Scheme?
What the char ! Indicates?
How can we define list in scheme?
‘(…)
(list (…))
What does the functions “car” and “cdr” do? In the following expressions, what do they return?
How can we define a function that receives a variable number of parameters?
What can we use “apply” for in scheme? What is the result of the following expression: (apply + ‘(1 2 3))
How can we design a loop using “let”?
What is a tail recursive operation?
What is the proper tail operation? Why is it called proper?
How can we use a “for-each” command to loop through a list?
What is the difference between “for-each” and “vector-for-each”?
What is the difference between a list and a vector? Why are they this different?
What are some signs to use either a list or a vector?
What are some of the Schemes equivalence predicates and what do they mean? What are the costs of each of them?
Define a function to calculate the length of the list. Is the function recursive? Why? How could you make it recursive? Why do we want to turn this function into a recursive one?
Non recursive
(define (list_legth L)
(if (null? L)
0
(+ 1 (list_legth (cdr L)))))
The key difference between a tail recursive function and a non-tail recursive function lies in how they handle recursion and maintain stack frames during execution:
- A function is tail recursive when the recursive call is the last operation in the function.
- In other words, after the recursive call, there is nothing else to be done. No operations or computations are pending.
-
Tail call optimization (TCO) can be applied here: the compiler or interpreter can optimize by reusing the current function’s stack frame instead of creating a new one for the recursive call, reducing memory usage and preventing stack overflow.Example (Tail Recursion in Kotlin):
kotlin tailrec fun factorial(n: Int, accumulator: Int = 1): Int { return if (n == 0) accumulator else factorial(n - 1, n * accumulator) }Here, the recursive callfactorial(n - 1, n * accumulator)is the last operation in the function.
- A function is non-tail recursive if the recursive call is not the last operation in the function.
- After the recursive call returns, there is still more work to be done (e.g., additional computations).
- This prevents tail call optimization, so each recursive call adds a new frame to the call stack. If the recursion depth is large, this can lead to a stack overflow.Example (Non-Tail Recursion in Kotlin):
kotlin fun factorial(n: Int): Int { return if (n == 0) 1 else n * factorial(n - 1) }In this case, after the recursive callfactorial(n - 1), the multiplicationn *still needs to happen, so it’s not a tail recursion.
- Performance: Tail recursion is generally more memory efficient because it can reuse the current stack frame, while non-tail recursion requires maintaining a separate stack frame for each call.
- Optimization: Many modern compilers (including Kotlin’s) can optimize tail recursive functions, transforming them into loops to improve performance.
Recursive
(define (rec_list_legth list)
(define (helper_length list result)
(if (null? list)
0
(helper_length (cdr list) (+ 1 result))))
(helper_length list 0))
Define a function to return the “n” objects in the starting of a list. Although the code is stack optimized, there is another cost in it that is high. What is it? How can we avoid it?
(define (first_n n List)
(define (helper n List result)
(if (null? list)
result
(helper (- 1 n) (cdr List) (append result (list (car List))))))
(helper n List ‘()))
Everytime you want to append a value to a list you need to go through all of its content. In this case it would be faster if the function was not tail recursive.
(define (stack_first_n n L)
(if (= n 0)
‘()
(cons (car L) (stack_first_n (- 1 n) (cdr L)))))
In this case we traverse the list only once.
Why can not we do the following operation: (append r (car L))? How can we solve it?
Because (car L) is not a list
(append r (list (car L)))
Define a function that returns the kth value of a list.
(define (ref k l)
(if (= k 0)
(car l)
(ref (- k 1) (cdr l))))
Define a function that returns a list from an initial value to an end value. If the starting value is not determined, consider it zero.
First we define a function that returns the values between a max and a min
(define (range max min)
(if (= max min)
(list max)
(cons min (range max (+ min 1)))))
The final function that checks if we received a min value:
(define (range max . min)
(define (helper max min)
(if (= max min)
(list max)
(cons min (helper max (+ min 1)))))
(if (null? min)
(helper max 0)
(helper max (car min))))
What is a thunk? How can we use it? Give an example.
It is a function without parameters.
Define a function for a while operation. And another one to test it
(define (while condition body)
(when (condition)
(body)
(while condition body)))
(define (test-while)
(let ((x 0))
(while (lambda () (< x 10))
(lambda ()
(displayln x)
(set! x (+ 1 x))))))
Define a function for reversing the order of a list.
(define (reverse l)
(if (null? l)
‘()
(append (reverse (cdr l)) (list (car l)))))
Define a function that flattens a list. Exclude other lists inside it.
(define (flatten l)
(if (null? l)
‘()
(if (list? (car l))
(append (flatten (car l)) (flatten (cdr l)))
(cons (car l) (flatten (cdr l))))))
How can we use “case” in Scheme? Create a case to verify if the first value of the list (c, d) is in the list (a, e, I, o, u).
What is the “cons” command in Scheme? Create a cond to compare two numbers.
How do objects and variables refer to memory? What does it means? What other options are there?
Scheme is garbage collected. What does it means?
What is the difference between literals and constructed variables? In the example how the usage of literals affects the memory? Compare with the following code, what is the difference in behavior?
How can we create a mutable list? How can we change it?
How is the evaluation strategy in Scheme? What does it means? Why do we have this type of evaluation?
Given the following code what happens and why. What is the difference from the following one?
How can we define new types in Scheme?
Define a type called “being” with an immutable attribute and a mutable one called name and age respectively.
What procedures does Scheme creates when a new type is created?
How can we use inheritance in Scheme? Create a structure called “my-being” that inherits from “being” with the addition of the “alive” mutable attribute.
What are the differences between OO and structures?
What is closure?
How does closure affects the following code?
How can we use closure to implement a loop?
What are the higher order functions in Scheme?
What are the “folds” commands? What is the difference between them and the rest of the other higher order functions?
If you could choose between fold left and fold right which one would you choose? Why?
How can we make fold right tail recursive? Is it better than the original version?
How can we use “case” in Scheme? Create a case statement to verify if the first value of the list “(c,d)” is in the list “(a,e,I,o,u)”.
What is the “cond” commmand in Schema? Create a cond statement to compare two numbers.
In Scheme, cond is a conditional expression, similar to if in other programming languages, but more versatile. It allows you to specify multiple conditions and their corresponding expressions. The general syntax is:
(cond
(condition1 expression1)
(condition2 expression2)
…
(else default-expression))
Each condition is evaluated in order, and when the first true condition is found, the corresponding expression is evaluated, and the result is returned. If none of the conditions are true, the else clause is executed. The else clause is optional but is usually used to handle all other cases.
Here’s an example:
(cond
((> 5 10) ‘greater)
((< 5 10) ‘less)
(else ‘equal))
In this example, since 5 is less than 10, the expression returns ‘less.
(cond
((> 3 3) ’greater)
((< 3 3) ’less)
(else ’equal)) ; => equal
How do objects and variables refer to memory in Scheme? What does it means? What other options are there?
In Scheme, objects and variables handle memory in a way that reflects its minimalist and functional nature. Let’s break down how this works:
- Variables and Memory References• In Scheme, variables are bound to objects, and these objects are stored in memory. A variable is essentially a name that references a value or object in memory.
• When you define a variable with something like (define x 10), the variable x refers to the object 10, which is stored in memory.
• Variables in Scheme do not hold the actual value directly; instead, they point to objects in memory. This concept is similar to pointer-based referencing in lower-level languages like C, though it is abstracted away in Scheme. - Immutability of Objects• In a functional programming language like Scheme, objects are generally immutable (unchangeable). This means that once an object is created (like a list or number), it cannot be altered.
• If you need to “change” the value of a variable, you create a new object and update the variable to refer to that new object, rather than modifying the original object. - Memory Models in Scheme• Scheme typically uses heap memory to store objects. When an object is created (such as a list or a number), it is placed in the heap. Variables are references (or pointers) to those objects.
• Garbage collection is automatically handled by the Scheme runtime, meaning memory that is no longer referenced by any variable is freed up for future use. - Other Memory-Reference Models in Programming
In contrast to Scheme’s memory model, other languages offer alternative ways to manage variables and objects:
• Direct memory access (lower-level languages): In languages like C, variables can directly refer to specific memory addresses, allowing for direct memory manipulation (e.g., using pointers). This offers more control but also more complexity, as you have to manually manage memory. • Value semantics (languages like C or Rust): In some languages, variables directly hold the value, not just a reference. This means that when you assign one variable to another, a copy of the value is made. Scheme, like most functional languages, avoids this due to the preference for immutability. • Mutable objects (languages like Python, Java): In languages with mutable objects, you can change the object’s contents without creating a new object. This can make memory management more complex but allows for more flexible data structures.
- What Does This Mean in Practice?• Scheme encourages you to think of variables as names for objects rather than containers that hold values.
• When you work with lists, for example, modifying a list (using operations like set! or set-car!) does not change the variable itself, but rather the memory object that the variable is pointing to. Most operations in Scheme are designed to create new objects rather than modify existing ones.
Example:
(define x ‘(1 2 3)) ; x refers to the list (1 2 3)
(define y x) ; y refers to the same object as x
(set-car! x 0) ; changes the first element of the list that x points to
x ; now evaluates to (0 2 3)
y ; also evaluates to (0 2 3), because x and y refer to the same object
In this example, both x and y refer to the same list object in memory. Changing the list via x also changes it for y, because they both point to the same memory location.
Summary
• Objects in Scheme are stored in memory, and variables refer to these objects. • Scheme variables do not store values directly; instead, they act as references (similar to pointers in lower-level languages). • Objects are typically immutable in Scheme, with any changes resulting in the creation of new objects. • Memory management, including garbage collection, is handled automatically in Scheme.
This approach contrasts with languages that use pointers, value semantics, or mutable objects directly.
What is the difference in Scheme of using literals and constructors when creating a variable?
In Scheme, creating variables with literals and constructors can have different implications in terms of memory management, mutability, and behavior when you manipulate the variable. Let’s break down the differences between the two.
- Literals
A literal is a direct representation of a value in Scheme code. For example:
• Numbers, characters, strings, and booleans are common literals. • Lists and vectors can also be written as literals.
Examples of literals:
(define x ‘(1 2 3)) ; A list literal
(define y 42) ; A numeric literal
(define z “hello”) ; A string literal
When you use a literal, the object is directly included in the program’s memory at compile or run time.
Key characteristics of literals:
• Shared storage: In Scheme, literals are often stored in a shared, read-only section of memory. For example, multiple occurrences of the same string literal might refer to the same memory location. • Immutable: Modifying literals is discouraged or undefined behavior. If you attempt to modify a literal (like a list or vector literal), it can result in unpredictable behavior, because these objects are often placed in a read-only section of memory. • Performance: Using literals can be faster than constructors, as they are typically pre-allocated and don’t require memory allocation at runtime.
Example of potential issues with modifying literals:
(define lst ‘(1 2 3)) ; List literal
(set-car! lst 0) ; This can cause undefined behavior, since ‘lst’ is a literal
In this example, modifying the literal list lst is undefined behavior in Scheme.
- Constructors
Constructors in Scheme are functions that create new objects in memory at runtime. The most common constructors are list, vector, and cons, which allocate memory dynamically for the new objects.
Examples of constructors:
(define x (list 1 2 3)) ; Creates a new list object dynamically
(define v (vector 1 2 3)) ; Creates a new vector dynamically
(define p (cons 1 2)) ; Creates a new pair dynamically
Key characteristics of constructors:
• New memory allocation: Every time you use a constructor, Scheme allocates new memory for the object. This means that even if two lists contain the same elements, they will be distinct objects in memory. • Mutable: Objects created with constructors can be freely modified using operations like set-car!, set-cdr!, or vector-set!. • No shared storage: Unlike literals, objects created with constructors do not share memory with other instances (unless explicitly referenced or copied).
Example of safe modification with constructors:
(define lst (list 1 2 3)) ; A list created with the ‘list’ constructor
(set-car! lst 0) ; This is allowed and modifies the first element
Here, the list was created using the list constructor, so modifying the list using set-car! is valid.
- Differences in Practice• Memory Allocation: Literals typically don’t require memory allocation during execution, whereas constructors do.
• Literals refer to predefined, read-only objects.
• Constructors create new objects that occupy memory at runtime.
• Mutability:
• Literals should not be modified; doing so may result in errors or undefined behavior.
• Constructed objects are generally mutable, allowing for safe modifications of their contents.
• Efficiency:
• Literals are more efficient in terms of performance because they are often reused, but they are static and immutable.
• Constructors incur a runtime cost for memory allocation but provide flexibility and modifiability. - Example Demonstrating the Difference
Here’s an example illustrating how two variables can behave differently when created using literals versus constructors:
(define a1 ‘(1 2 3)) ; List literal
(define a2 ‘(1 2 3)) ; Another list literal
(define b1 (list 1 2 3)) ; List created using constructor
(define b2 (list 1 2 3)) ; Another list created using constructor
(eq? a1 a2) ; #t, because both literals point to the same memory location
(eq? b1 b2) ; #f, because two separate lists are created using ‘list’
• a1 and a2 are equal because they are the same literal list stored in the same memory location. • b1 and b2 are not equal because they are two distinct lists created by the list constructor, each in its own memory location.
Summary
• Literals are static, immutable objects stored in a shared memory space and should not be modified. • Constructors create new, mutable objects at runtime, allowing for dynamic memory allocation and object modification. • The choice between using literals or constructors depends on whether you need immutable, shared objects (literals) or mutable, dynamically created objects (constructors).
